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

Рассмотрим математическую модель общей задачи ЛП в стандартной форме:

 

(3.1)

( ) (3.2)

( ) (3.3)

Выполнить геометрическую интерпретацию задачи ЛП означает
поставить в соответствие каждой части математической модели задачи —
системе ограничений (3.2), условию неотрицательности переменных
(3.3), целевой функции (3.1) —геометрические образы. Для математической модели вида (3.1) — (3.3) с двумя переменными (п = 2)
это будет геометрическая интерпретация на плоскости х1ох2 такой задачи:

(3.4)

(3.5)

. (3.6)

 

Каждое неравенство системы (3.5) с геометрической точки зрения
представляет собой полуплоскость с граничной прямой аi1х1 + аi2 х2= bi (i=1,2,....,т). Условия неотрицательности переменных (3.6)
также определяют полуплоскости соответственно с граничными прямыми

х1 = 0, х2 = 0, общая часть этих полуплоскостей образует, первый квадрант.[1] Если рассматриваемая система (3.5) — (3.6) совместна
(имеет хотя бы одно решение), то полуплоскости как выпуклые множества, пересекаясь, образуют общую часть, которая также является выпуклым множеством и представляет собой совокупность точек, координаты которых являются решениями данной системы. Совокупность этих точек, образующих область допустимых решений, назовем многоугольником решений (L). В частных случаях он может быть точкой, отрезком, лучом, неограниченной многоугольной областью.

Если в системе ограничений (3.2) — (3.3) п = 3, то каждое неравенство геометрически представляет полупространство трехмерного
пространства, граничная плоскость которого аi1х1 + аi2 х2+ аi3 x3= bi
(i=1,2,....,т), а условия неотрицательности — полупространства
с граничными плоскостями xj = 0 (j = 1,2, 3). Если система ограничений совместна, то все эти полупространства, пересекаясь, образуют
в трехмерном пространстве общую часть, которая называется многогранником решений.

В системе ограничений (3.2) — (3.3) при п >3 каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью ai1 х1 + ai2 х2 + ... + ain xn = bi, а условия
неотрицательности — полупространства с граничными гиперплоскостями xj = 0 (i = 1, 2, ..., п). Если система ограничений совместна, то
по аналогии с трехмерным пространством образуется общая часть п-мерного пространства, называемая гипермногогранником решений.

Выясним теперь, что с геометрической точки зрения представляет
собой целевая функция задачи (3.1). Для этого при Z — const = a
введем понятие линии уровня ЦФ как совокупности точек пространства, в каждой из которых ЦФ принимает одно и то же наперед заданное
значение а. Для линейных функций все линии уровня параллельны,
представляют собой семейство прямых (п = 2), плоскостей (п = 3),
гиперплоскостей (п >3). Линия уровня Z = аиспользуется дляотыскания в области Lточки (точек), доставляющей экстремум ЦФ и поэтому часто называется разрешающей прямой. Предельным положением
разрешающей прямой будет такое ее положение, при котором она проходит хотя бы через одну точку области L, но не содержит ни одной
ее внутренней точки.

Для отыскания предельного положения разрешающей прямой линию уровня следует перемещать в направлении наискорейшего возрастания функции Z, которое указывается ее градиентом. Градиент – (в линейном программировании) вектор, составленный из коэффициентов целевой функции и показывающий направление ее наискорейшего возрастания.

Запишем градиент линейной ЦФ (3.1): grad Z = (c1, с2, ...,сп) = С.
Таким образом, в каждой точке пространства градиент линейной ЦФ
постоянен и совпадает с вектором, составленным из коэффициентов
при переменных данной ЦФ. Очевидно, что градиент линейной ЦФ перпендикулярен линии ее уровня.

Для нахождения предельного положения разрешающей прямой
(n = 2) нужно построить какую-либо линию уровня ЦФ (3.4) (например, Z = с1х1 + с2х2 = а) и, передвигая ее параллельно самой себе
в направлении градиента в области L, определить экстремум Z.

Подведём итог выше сказанному: геометрический образ ЦФ (3.4) – это прямая. Геометрическим образом одного из неравенств (3.5) с 2-я неизвестными является одна из 2-х полуплоскостей, на которые делит всю плоскость соответствующая прямая. Чтобы определить точки, какой полуплоскости удовлетворяют заданному неравенству нужно в его левую часть подставить координаты, какой-нибудь точки, не лежащей на прямой l , если её координаты удовлетворяют заданному неравенству, то ему будут удовлетворять координаты всех точек расположенных в той же полуплоскости, что и взятая, если же нет, то берём другую полуплоскость.

Геометрическим образом системы линейных уравнений (3.5) является общая часть полуплоскостей заданных всеми неравенствами (выпуклый многоугольник).

Геометрическим образом условия неотрицательности переменных является первая четверть координатной плоскости.

Рисунок 1. Декартовая система координат.

Приведенные рассуждения являются основой графического метода решения задачи ЛП.

Графический метод – метод решения задачи линейного программирования , заданной на плоскости, т.е. содержащей только две переменные.

 

Рассмотрим различные случаи вида многоугольника решений и предельных положений линии уровня целевой функции Z. Многоугольник L может быть замкнутым (рис. 2., а - в) и незамкнутым (рис. 2.,
г - з). Замкнутый многоугольник может содержать множество допустимых решений задачи ЛП (см. рис. 2., а), область допустимых решений может быть пустой (см. рис. 2., б), т. е. не содержать ни одного
решения, — это случай, когда система ограничивающих условий задачи несовместна и задача называется недопустимой. Предположим,
что система (3.2) при условии (3.3) совместна и ее многоугольник ограничений замкнут. Пусть линия уровня ЦФ (3.1) соответствует положению, обозначенному (Z) на рис. 2., а. Из рисунка следует, что
прямая Z становится разрешающей по отношению к многоугольнику
решений дважды: в точках А и D, причем минимальное значение ЦФ принимает в точке А. Координаты точки А (х1, х2) находим, решая
систему уравнений, соответствующих прямым АВ и AF. Координаты
точки D, соответствующей максимальному значению Z, найдем, решая
систему уравнений, соответствующих прямым BD и DE.

Может быть случай, когда линия уровня ЦФ покидает многоугольник ограничений при максимизации на одной из сторон L (см. рис. 2,е). В этом случае максимальному значению ЦФ соответствует множество оптимальных планов, которые называются альтернативными. Альтернативные планы могут быть и при незамкнутом многоугольнике (см. рис. 2., г). Здесь имеет место альтернативный минимум, а при максимизации той же ЦФ значение ее неограниченно возрастает, в этом случае говорят, что ЦФ неограниченна на множестве L сверху. Случай, когда ЦФ неограниченна на множестве L только снизу, показан на рис. 2., ж, противоположный этому случай приведен на рис. 2.,з. При неограниченности значения ЦФ задача называется неразрешимой. Незамкнутая многоугольная область L может быть такого вида, что ЦФ неограниченна на ней как снизу, так и сверху (см. рис. 2., е), либо ограничена и снизу, и сверху (см. рис. 2., д), но оба экстремума альтернативные.

Таким образом, знакомство с геометрической интерпретацией и графическим методом решения задач ЛП убеждает нас в том, что если значение ЦФ ограничено, то оптимум достигается на границе области допустимых решений.

 

Рисунок 2. Различные случаи геометрической интерпретации задачи ЛП.

 

 

Пример.

Найти допустимую область задачи линейного программирования, определяемую ограничениями:

(3.7)

 

Рисунок 3. Геометрический образ неравенств, входящих в структурные ограничения.

Решение

1. Рассмотрим прямую . При а при Таким образом, эта прямая проходит через точки (0,1) и (-1,0). Для определения интересующей нас полуплоскости, принимаем и подставляем в неравенство по условию, получим, что -0+0<1 и поэтому интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 3а.

2. Рассмотрим прямую . При , а при . Таким образом, эта прямая проходит через точки (0, -1/2) и (1,0), проверяем опять интересующую нас полуплоскость, для этого берём координаты точки не лежащей на прямой х1= 0, х2=0, так как 0-2*0<1 то интересующая нас полуплоскость лежит выше прямой рис.3.б.

3. Наконец, рассмотрим прямую. Она проходит через точки (0,3) и (3,0) и так как 0-0<3, то интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 3.в.

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

Рисунок 4. Геометрический образ системы ограничений – выпуклый многоугольник (ОДР).

Обратите внимание на то, что получившаяся область имеет вид выпуклого многоугольника.

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

,

, (3.8)

………………..

,

.

Не приводя строгих доказательств, укажем те случаи, которые тут могут получиться.

1. Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника (см. рис. 5).

2. Не основной случай - получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 6. Такая ситуация, например, получится, если в рассмотренном выше примере убрать ограничение . Оставшаяся часть будет неограниченным выпуклым многоугольником.

Рисунок 6.
Рисунок 5.

 

3. Наконец, возможен случай, когда неравенства (3.7) противоречат друг другу, и допустимая область вообще пуста.

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

 

Рисунок 7. Геометрический образ ЦФ.

Рассмотрим прямую . Будем увеличивать L. Что будет происходить с нашей прямой? Легко догадаться, что прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором , так как это - вектор нормали к нашей прямой и одновременно вектор градиента функции .

Ограничения задачи вырезают на плоскости некоторый многоугольник. Пусть при некотором L - прямая пересекает допустимую область. Это пересечение дает какие-то значения переменных , которые являются планами.

Увеличивая L мы начнем двигать нашу прямую, пересечение прямой с допустимой областью будет изменяться (см. рис. 8). В конце концов, эта прямая выйдет на границу допустимой области - как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение прямой с допустимой областью будет пустым.

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

Рисунок 8. ОДР и оптимальное значения ЦФ.

 

Пример.

Решить задачу графическим методом:

,

,

,

 

Решение.

Допустимую область мы уже строили - она изображена на рис. 4.

Повторим еще раз этот рисунок, оставив только допустимую область и нарисовав дополнительно прямые - линии уровня ЦФ: см. рис.9.

Рисунок 9. Линии уровня ЦФ.

Пусть, например, L=2. Тогда прямая проходит через точки (2,0) и (0,1) и изображена на рис. 9. Будем теперь увеличивать L. Тогда прямая начнёт двигаться параллельно самой себе в направлении, указанном стрелкой. Легко догадаться, что максимальное значение L получится тогда, когда прямая пройдет через вершину многоугольника, указанную на рисунке. Дальнейшее увеличение L приведет к тому, что прямая выйдет за пределы многоугольника и её пересечение с допустимой областью будет пустым.

Выделенная вершина лежит на пересечении прямых:

x1=3-x2; -1(3-x2)+x2=1; 2х2=4; х2=2, х1=1

И имеет координаты . Это и есть решение нашей задачи, т.е. есть оптимальный план задачи. При этом значение целевой функции , что и дает её максимальное значение.

Обратите внимание на то, что оптимальный план, как правило, соответствует какой-то вершине многоугольника, изображающего допустимую область. Таким образом, вершины допустимой области играют в решении задач линейного программирования особую роль. Получить значения оптимального плана можно 2-мя способами: снять координаты х1 и х2 с графика, либо решить систему уравнений прямых, пересечение которых нам и дало выделенную вершину.

Подводя итог этим примером, можно сформулировать следующие положения:

1. допустимая область - это выпуклый многоугольник;

2. оптимум достигается в вершине допустимой области (если допустимая область ограничена и не пуста);

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

Алгоритм решения задач ЛП графически.

1. Строим ОДР (область допустимых решений)

2. Строим линию уровня ЦФ (проще построить Z=0)

3. Определяем направление перемещения ЦФ.

4. Строим вектор – градиент.

5. При решении задачи на max перемещаем ЦФ на ОДР в направлении возрастания. Находим точку в которой ЦФ становится опорной - искомая точка max. Если решение задачи на min, то перемещаем ЦФ в сторону убывания и находим искомую точку min.

6. Для нахождения оптимального плана (точку экстремума) составить систему уравнений и решить ее, найти численные значения оптимального плана.

7. Рассчитать значение ЦФ для найденного плана.


Вопросы по теме:

1. Что вы понимаете под выражением выполнить геометрическую интерпретацию задачи ЛП?

2. Что с геометрической точки зрения представляет собой каждое неравенство системы ограничений задачи с 2-мя переменными?

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

4. Что обозначает понятие: рассматриваемая система ограничений и условие неотрицательности переменных – совместна?

5. Какой геометрический образ образует система ограничений задачи при (n = 2), имеющая общую часть заданную всеми неравенствами?

6. Что мы называем многоугольникомом решений (L)?

7. Какой геометрический образ может принимать многоугольник решений в частных случаях?

8. Геометрическим образом условия неотрицательности переменных является?

9. Что с геометрической точки зрения представляет собой каждое неравенство системы ограничений задачи с 3-мя переменными?

10. Что с геометрической точки зрения представляет собой каждое неравенство системы ограничений задачи более чем с 3-мя переменными?

11. При каких условиях ОДР - называется многогранником решений?

12. При каких условиях ОДР - называется гипермногогранником решений?

  1. При каких условиях ОДР – называется многоугольникомом решений?
  2. Что с геометрической точки зрения представляет собой ЦФ задачи при (n = 2)?
  3. Что с геометрической точки зрения представляет собой ЦФ задачи при (n = 3)?
  4. Что с геометрической точки зрения представляет собой ЦФ задачи при (n >3)?
  5. Линия уровня Z для отыскания в области L точки (точек), доставляющей экстремум ЦФ называется?
  6. Какое положение разрешающей прямой - называется предельным?
  7. Дайте определение понятию градиент.
  8. Графический метод - это метод?
  9. Какая задача называется недопустимой?
  10. Какие планы называются альтернативными? В каких случаях они возникают?
  11. Какая задача называется неразрешимой?
  12. Какими способами можно получить значения искомого оптимального плана?
  13. Если допустимая область ограничена и не пуста, то оптимум ЦФ достигается?
  14. Необходимым и достаточным условием разрешимости задачи является?
  15. Перечислите алгоритм решения задач ЛП графически.

 


[1] Квадра́нт (от лат. quadrans, род. падеж quadrantis — четвёртая часть, четверть). Квадрант плоскости — любая из 4 областей (углов), на которые плоскость делится двумя взаимно перпендикулярными прямыми, принятыми в качестве осей координат