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

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

Постановка задачи. Пусть задана целевая функция для двух проектных параметров x₁ и x₂:

Для определенности положим . И пусть задана система линейных неравенств:

(6.9)

Требуется среди допустимых решений системы неравенств (ОДР) найти такое, при котором целевая функция принимает минимальное значение.

Последовательность действий:

1. Строим область допустимых решений системы (6.9). В общем виде – это выпуклая замкнутая многоугольная область на плоскости x ₁ x ₂, лежащая в первой четверти.

Предположим, что эта область имеет вид, как показано на рис. 6.9.

Рис. 6.9. Графический метод поиска экстремума функции

Стоящую перед нами задачу (6.8-6.9) можно сформулировать следующим образом.

Среди всех точек (x _1, x ₂ ) Î найти такую, координаты которой минимизирует функцию цели (6.8).

В зависимости от области допустимых решений (ОДР) возможны следующие варианты решения задачи линейного программирования (рис.6.10).

Рис.6.10. Варианты решения задач ЛП.

2. Приравняем выражение функции цели какой-либо постоянной величине R:

.

Это уравнение определяет на плоскости прямую, в точках которой функция цели Z принимает постоянное значение R. Такая прямая называется линией уровня функции цели.

3. Будем изменять величину R, т.е. перемещать найденную прямую параллельно самой себе в направлении увеличения (при поиске максимума) или уменьшения (при поиске минимума) целевой функции. Направление движения прямой для нашего примера (с₂ > 0) указано на рисунке стрелкой (рис.6.11, а).

4. Таким образом, можно сказать, что при возрастании R от –¥ до +¥ линия уровня (6.10), смещаясь параллельно самой себе в одну и ту же сторону, “зачерчивает” всю плоскость.

Рис.6.11. Линии уровня целевой функции

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

6. Определим координаты точки экстремума функции цели и вычислим ее значение в этой точке.

Очевидно, что в нашем случае это будет первая точка встречи линии уровня функции с областью (рис. 6.9) при ее смещении от меньших значений Rк большим, и эта точка совпадает с началом координат. Для любой другой точки из области значение функции цели Z_min будет больше, чем в точке (0, 0).

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

n Пример 6.2. Минимизировать целевую функцию

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

Строим полуплоскости P_i, i =1, 2, 3, 4, 5 соответствующие каждому неравенству системы ограничений (6.12).

Рис.6.12. Область допустимых решений - (к примеру 6.2)

Полуплоскость Р₁ ограничена прямой x – y+ 1 =0 и распо-ложена «снизу» от этой прямой. Аналогично строим полуплоскости Р ₂ и Р ₃. Пересечение полуплоскостей Р ₁, Р ₂, Р ₃ и дает многоугольник (Рис.6.12).

Записываем прямую линии уровня функции цели

и строим прямые, соответствующие R= –1, R=0 и R= 1. Из рис.6.12 видно, что линию уровня нужно перемещать в сторону уменьшения значения R до встречи с «последней» точкой области, т.е. М (2, 3) в которой функция цели принимает значение Z_min= – 4.

Таким образом, решением задачи является: x= 2, y= 3, Z_min= – 4.

Решение данной задачи с использованием электронных таблиц Excel приведено в разделе 6.5.

n Пример 6.3. Минимизировать целевую функцию

при ограничениях примера 6.2.

Область допустимых решений уже построена в предыдущем примере. Строим линии уровня для R= 0 и R= –1.

Рис.6.13. К примеру 6.3.

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

n Пример 6.4. Минимизировать функцию цели

Система ограничений имеет вид

Построим область допустимых решений, определяемую системой неравенств (6.15), аналогично примеру 6.2 (рис.6.14).

Рис.6.14. К примеру 6.4.

Строим линии уровня –x=R для R=0, R= –1, R= –2. Очевидно, что для всех R Î [–¥, 0 ] линии уровня пересекают область . Следовательно, функция цели не ограничена снизу, т.е. .

n Пример 6.5. Рассмотрим предыдущую задачу на поиск максимума функции цели, т.е. ограничения описываются системой (6.15), а функция цели имеет вид

Из рис.6.14 видно, что максимальное значение функция цели достигает в начале системы координат, т.е. решением задачи является x=0, y=1 и соответственно Z_max=0.

Обобщим результаты приведенных выше решений задач линейного программирования (6.8-6.9). При решении этих задач возможны различные случаи:

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

2. Область является неограниченной фигурой, и прямая уровня для сколь угодно больших по абсолютной величине отрицательных R имеет общие точки с областью . В этом случае минимальное значение функции цели в области равно –¥. Линия уровня – x=R при всех значениях R пересекает область . Следовательно, функция цели в области не ограничена снизу, т.е. , иначе говоря, минимум функции не достигается. Такой случай приведен в примере 6.4.

3. Область допустимых решений пуста, и задача (6.8-6.9) в этом случае не имеет решения.

4. Область допустимых решений содержит единственную точку. В этом случае не приходится говорить об оптимальном решении.

В случае n неизвестных (n ³ 3) все построения теряют наглядность. Однако геометрическая формулировка задачи в случае n неизвестных остается той же самой, что и в случае двух переменных. Различие состоит в том, что понятие «линия уровня» для n =2 заменяется понятием «плоскость уровня» для n =3 и «гиперплоскость» – для n > 3.