Задача линейного программирования. Проверка оптимальности текущего плана, страница 19

3.Находим координаты т. А из решения системы уравнений

где т. А=(L1)Ç(L2). Отсюда А=(1,1), а Zmin =Z(A)= 3∙1+5∙1 = 8.

Следовательно, max Z(X) = +∞, min Z(X)=8 при Х*=А=(1, 1).

Пример 9. Найти максимум и минимум функции Z=4x1-6x2+1  при ограничениях:

                                                                                     (1)

                                                                                  (2)

                                                                                 (3)

                                                                                             (4)

.                                                                                             (5)

Решение.1.Строим прямые, уравнения, которых получаются в результате замены в ограничениях (1)…(5) знаков неравенств на знаки равенств (см. рис. 9).

2.Строим прямую Z = 1. Для этого строим вектор  и через т. О(0, 0) проводим прямую, перпендикулярную ему.

3. Перемещаем прямую в направлении противоположном вектору. Прямая Z всегда будет пересекать многоугольник решений. Следовательно, линейная функция неограниченно убывает, и конечного оптимума у нее нет, т.е. min Z = -∞.

4.Перемещаем прямую в направлении вектора. И в этом случае прямая Z всегда будет пересекать многоугольник решений. Следовательно, конечного оптимума отсутствует, т.е. mах Z = ∞.

Пример 10. Найти максимум и минимум функции Z=-2x1+2x2  при условиях:

                                                                                     (1)

                                                                                  (2)

                                                                                             (3)

.                                                                                             (4)

Решение.1.Строим прямую  (L1), соответствующую ограничению (1). Не трудно заметить, что прямая проходит через точки (0,2) и (2,0) (см. рис. 10).

2.Строим прямую  (L2), соответствующую ограничению (2). Эта прямая проходит через точки (0,1) и (-1,0).

3.Так как прямые (L1) и (L2) не проходят через точку О(0,0), подставляем координаты т. О в первое и второе ограничения.Получаем: 0≥2 и 0≥1. Это неверно, следовательно т.О не лежит в плоскости решений. Таким образом, стрелки на концах прямых (L1) и (L2) должны быть направлены в полуплоскость не содержащую т. О(0,0).

4.Строим прямую Z=0. Для этого строим вектор  и через т. О(0, 0) проводим прямую, перпендикулярную ему (см. рис. 10).

5.Перемещаем прямую Z в направлении вектора . Эта прямая встретит область решений в точке А=(L1) Ç (L2) (прямая Z совпадает с граничной прямой (L2) области допустимых решений и проходит через одну угловую точку этой области А). Из рис. 10 видно, что прямая Z принимает минимальное значение в любой точке ,находящейся  в области решений, и лежит на прямой (L2), начиная с т.А и заканчивая т. В. Для нахождения общего оптимального решения находим координаты т. А и координаты произвольной точки, лежащей на оптимальной части прямой (L2).

6.Определяем координаты точки А=(L1) Ç (L2)

2 = 3

Определяем координаты, например т.С. Полагая в уравнении  (L2),  (число 1 выбрано произвольно и больше ), получим -1+х2=1 Þ х2=2; .

7.Вычисляем.

Согласно рис. 10 задача имеет бесконечное множество оптимальных решений

Х* = (1-t) + t, 0 ≤ t ≤ ∞, общая формула для определения любого оптимального решения задачи (общее решение) 

Придавая параметру t любые числовые значения от 0 до ∞, будем получать различные оптимальные решения задачи, при любом из которых  Z = Zmin = 2.

8.Перемещаем прямую Z в направлении ее возрастания (т.е. в направлении вектора ). В виду того, что в этом направлении область допустимых решений не ограничена, прямая уходит в бесконечность. Задача не имеет решения вследствие неограниченности целевой функции, т.е. max Z(X)= + ∞.