Тема 2. Графический метод решения задач линейного программирования

Графический метод основан на геометрической интерпрета­ции задачи линейного программирования (ЗЛП) и применяется или решения задач с двумя переменными, когда ограничения выражены неравенствами.

Рассмотрим графический метод решения на примере.

Пример 3. ЗЛП имеет вид:

Целевая функция

при ограничениях

Решение: Каждое из неравенств системы ограничений геометрически определяет полуплоскость. Пере­сечение этих полуплоскостей задает область допустимых решений- планов ЗЛП.

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

Для построения данной области необходимо начертить гра­ничные прямые по уравнениям системы ограничений, в кото­рых неравенства заменяются равенствами.

(I)

I уравнение:

рис. 2.1.

Пример построения такой области для решаемой задачи при­веден на рис. 2.1. Первым неравенством из примера 3 определяются две области на плоскости.

Одна из них — это область возможных планов задачи, другая — область, где этих планов нет. Границей между ними будет прямая, которую мы построим, заменив неравенство равенством (прямая I). Подставив точку O(0,0) в неравенство и проверив его справедливость, определяем область возможных решений. По знаку первого неравенства находим область решения задачи. Аналогично, заменив не­равенства равенствами, строим остальныеи определяем область решений задачи, учитывая знаки неравенств.

(III)

(II)

рис. 2.3

рис. 2.2

(V)

(IV)

рис. 2.5

рис. 2.4

(I)

(III)

(V)

(II)

(IV)

E

L

D

C

B

A

рис. 2.6

На рисунке номер прямой определяет порядковый номер огра­ничения. Латинскими буквами обозначены точки пересечения прямых. Неравенства означают, что область определения будет расположена в 1-м квадранте координатной плоско­сти. Таким образом, выделенная на рис. 2.6 область ABCDE будет областью допустимых решений, определенной ограничениями задачи. Крайние точки полученной выпуклой многогранной области будут соответствовать допустимым базис­ным решениям задачи.

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

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

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

Для определения оптимального решения необходимо постро­ить прямую L= , перпендикулярную линии градиента и перемещать ее параллельно вдоль линии градиента до самой удаленной точки области. Такие прямые, перемещаемые вдоль линии градиента являются не чем иным, как линиями уровня плоскости. Если ре­шается задача поиска максимума, то линии уровня перемещаются в направлении возрастания градиента до поиска самой удаленной точки области ограничений. В случае поиска минимума — линии перемещаются в направлении, противоположном возрастанию градиента до самой удаленной точки. На рисунке показана ли­ния уровня L, определяющая оптимальную точку B, в которой значение целевой функции достигает своего максимума.

Зная, какая точка задает оптимальное решение, можно точно вычислить ее координаты. Для данного примера точка B нахо­дится на пересечении прямых III и I. Записав систему уравнений этих прямых, определяем координаты точки пересечения:

В результате получаем Х_опт=( 1,17; 5,68 ). Подставляя найденный результат в целевую функцию, имеем искомое оптимальное значение F(Х_опт)=1·1,17+2·5,68=12,53.

В зависимости от вида области ограничений и типа целевой функции решением может быть не одна точка, а бесконечное множество точек отрезка. Так, если в приведенном выше приме­ре градиент будет перпендикулярен линии ВС (см. рис. 2.6), то линия уровня целевой плоскости будет включать в себя весь от­резок BC полностью и, следовательно, в качестве решения мож­но брать любую из точек этого отрезка.

Пример 4. ЗЛП имеет вид:

Целевая функция

при ограничениях

Решение:

Построив область допустимых решений, получаем, что она пуста из-за несовместности ограничений. Решений нет.

(II)

(I)

(III)

(IV)

рис. 2.7

Иногда решения может не быть вовсе. Так, очевидно, реше­ние будет отсутствовать в случае несовместности ограничений, когда область допустимых решений является пустым множе­ством. Кроме того, решение может отсутствовать в том случае, когда область допустимых решений задана бесконечной полу­плоскостью. Если она не ограничена сверху, то для нее невоз­можно отыскать максимум, а если снизу — мини­мум.

Пример 5. ЗЛП имеет вид:

Целевая функция

при ограничениях

Решение:

A

рис. 2.8

G

(III)

(II)

(I)

Из графика видно, что область допустимых решений одна точка A(0;2) - она и является оптимальным решением, так как целевая функция стремится к минимуму и оптимальная точка на области допустимых решений ищется в направлении, противоположном вектору-градиенту. Если бы целевая функция стремилась к максимуму, то ЗЛП не имела бы решения.

Дата добавления: 2014-12-26