Случай n проектных параметров.

Сказанное выше можно обобщить для случая n проектных параметров. Система ограничений в этом случае имеет вид (6.5).

Каждое неравенство системы ограничений (6.5):

определяет некоторое полупространство P_i, а все неравенства - некоторую область в n-мерном пространстве, которая является пересечением конечного числа полупространств.

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

Совокупность точек n-мерного пространства, координаты которого удовлетворяют системе (6.5), есть замкнутая выпуклая многогранная область , получающаяся в результате пересечения всех m полупространств, отвечающих неравенствам системы. Если эта область ограничена, мы называем ее выпуклым многогранником в пространстве.

Опорной прямой (при n=2) называется прямая, которая имеет с областью , по крайней мере, одну общую точку. При этом вся область расположена по одну сторону от этой прямой. Например, на рис.6.8 приведены две опорные прямые: L1 и L2. Прямая L1 проходит через вершину области , а L2 – через сторону .

Рис. 6.8. К определе-нию опорной прямой

При n=3 уже говорят об опорной плоскости, которая может проходить через вершину многогранника, или его ребро, или его грань. Понятие опорной плоскости (гиперплоскости) легко обобщить на случай n>3.

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

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

Постановка задачи. Пусть задана целевая функция для двух проектных параметров 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)_.

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

• Пример 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.

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

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

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

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

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

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

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

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

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

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

• Пример 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.