Графический метод решения ЗЛП




Л3. Методы решения задач линейного программирования

Наиболее простым и наглядным методом решения ЗЛП является графический метод. Он применим для решения ЗЛП с двумя переменными. На плоскости х21 строится многоугольник решений АBCDEF:

Рис.1

Среди точек этого многоугольника надо найти такую, в которой линейная функция F = c1x1+ c2x2 принимает максимум (минимум).

Рассмотрим линию уровня линейной функции F, т.е. линию, вдоль которой функция F принимает фиксированное значение С:

c1x1 + c2x2 = С. (1)

Примерами линий уровня являются линии постоянной температуры (изотермы) на картах прогноза погоды, параллели (линии уровня широты) и меридианы (линии уровня долготы) на географической карте.

Пусть надо найти самую северную точку страны. Это будет точка, имеющая наибольшую широту, т.е. точка, через которую проходит параллель с самой большой широтой. Именно так надо поступать при геометрическом решении ЗЛП. На многоугольнике решений ищется точка, через которую проходит линия уровня с наибольшим значением, если ищется максимум целевой функции.

Линии уровня (1) представляют собой параллельные прямые при различных значениях С, т.к. их угловой коэффициент определяется только соотношением между с1 и с2. Другими словами, линии уровня – это своеобразные параллели, расположенные под углом к осям координат.

При смещении линии уровня в одну сторону уровень только возрастает, а при смещении в другую – только убывает. Направление наибольшего возрастания функции показывает вектор-градиент, координаты которого равны частным производным функции:

. (2)

Градиент ориентирован перпендикулярно линиям уровня.

Если провести линию уровня через ноль и перемещать ее параллельно самой себе в направлении градиента, то можно найти точку максимума целевой функции подобно тому, как на географической карте находится самая северная точка.

Таким образом, графический метод решения ЗЛП сводится к следующим этапам:

1. На координатной плоскости х21 строится многоугольник решений.

2. Находится градиент целевой функции .

3. Линия уровня c1x1 + c2x2 = С, перпендикулярная градиенту, передвигается в его направлении до тех пор, пока не покинет пределы многоугольника решений. Предельная точка этого движения и является точкой максимума целевой функции.

4. Для нахождения координат точки максимума решается система двух уравнений, описывающих пересекающиеся в этой точке прямые.

В случае минимизации целевой функции линию уровня надо передвигать в направлении, противоположном направлению градиента.

При графическом решении ЗЛП возможны случаи, когда область допустимых решений системы ограничений представляет пустое множество (условия задачи противоречивы) или не ограничена. В этих случаях оптимального решения не существует.

Пример 1. Мебельный цех выпускает изделия двух типов Т1 и Т2. На каждое изделие типа Т1 расходуется 1 единица ресурса Р1, 1 единица ресурса Р2 и единица ресурса Р3. На каждое изделие типа Т2 расходуется 1 единица ресурса Р1 и 4 единицы ресурса Р2. Ресурсы мебельного цеха ограничены: в день можно расходовать не более 8 единиц ресурса Р1, 20 единиц ресурса Р2 и 5 единиц ресурса Р3. Какое количество изделий типа Т1 и Т2 должен выпускать цех ежедневно, чтобы обеспечить максимальную прибыль, если прибыль от реализации изделия Т1 – 1 денежная единица, а от реализации Т2 – 2 денежные единицы.

Решение

Введем обозначения: х1 – число изделий типа Т1; х2 – число изделий типа Т2. Прибыль от реализации изделий Т1 составляет х1, а от реализации изделий типа Т2 - 2х2, т.е. необходимо максимизировать целевую функцию:

F = x1 + 2x2 → max.

Ограничения задачи имеют вид:

Первому ограничению соответствует прямая, проходящая через точки (0;8) и (8;0) (рис.2).

Рис.2

Второму ограничению соответствует прямая, проходящая через точки (0;5) и (20;0).

Решением неравенства х1≤ 5 (ограничение по количеству изделий типа Т1) является полуплоскость, лежащая слева от прямой х1 = 5. Таким образом, область допустимых решений ЗЛП представляет собой пятиугольник.

Для определения направления движения к оптимуму построим вектор – градиент = (1;2). При максимизации целевой функции следует двигаться в направлении вектора . В крайней угловой точке этого движения (точка А на рис.2) достигается максимум целевой функции.

Для нахождения координат точки А достаточно решить систему уравнений соответствующих прямых:

Отсюда легко получается решение ЗЛП: максимум целевой функции F = 12 достигается при х1 = 4 и х2 = 4.

Графический метод решения ЗЛП прост, нагляден, позволяет быстро и легко получить ответ. Однако он неприемлем для решения практических задач, т.к. его можно применять только в том случае, когда число переменных в стандартной задаче равно двум, или когда ЗЛП в канонической форме удовлетворяет условию n – r = 2, где n – число неизвестных задачи, r – ранг матрицы системы ограничений.

Поэтому необходимы аналитические методы, позволяющие решать ЗЛП с любым числом переменных.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-10-25 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: