Этапы решения задачи ЛП на основе ее геометрической

Нахождение минимального значения F отличается от нахождения максимального ее значения при тех же ограничениях лишь тем, что ЛУ передвигается не в направлении С, а в противоположном.

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

Отметим свойства целевой функции и ограничений

1. Целевую функцию можно умножать на любую положительную const.

2. К целевой функции можно добавлять любую const.

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

Пример: Найти решение задачи ЛП при следующих данных:

F = 2 X ₁+ 3 X ₂ ® max при

4 X₁ + 3 X₂ £ 12 (1)

X ₁ - X ₂ ³ 1 (2)

- X ₁ + 6 X ₂ £ 12 (3)

X ₁, X ₂ ³ 0 (4)

Область допустимых решений задачи (ОДР), или множество планов задачи представляет собой многоугольник, ограниченный прямыми – геометрическим выражением уравнений, преобразованных из неравенств (1)-(3). Поочередно приравнивая в уравнениях (1)-(3) Х ₁ и Х ₂ к нулю, а также используя условие (4), строим прямые, определяем полуплоскости, соответствующие каждому ограничению задачи и получаем многоугольник ABCD (см. рис.1). Каждая вершина многоугольника представляет собой опорный план.

Примечание: чтобы правильно определить допустимую полуплоскость, удобно ориентироваться по знаку при переменной X₂. Если это минус, а в неравенстве знак £, то допустимые решения будут лежать ниже прямой, если знак ³, полуплоскость строится вверх от прямой. Если знак при второй переменной плюс, то, соответственно, плоскости строятся в противоположных направлениях).

В одной из вершин многоугольника (т.е. в одном из опорных планов) значение целевой функции является максимальным (при условии, что функция ограничена сверху на множестве планов). Пункты 1-3 выполнены. Строим направляющий вектор. Начало его совпадает с началом координат, а конец имеет координаты (С₁; С ₂), соответствующие коэффициентам в целевой функции. В нашем случае (2; 3).

Рис. 1

Вектор (2; 3) показывает направление роста целевой функции. Для определения вершины многоугольника построим линию уровня F =2 X ₁+ 3 X ₂ = h, проходящую через многоугольник решений. Вначале положим h = 6. Нетрудно видеть, что линия уровня перпендикулярна направляющему вектору. Задав новое значение h, больше предыдущего, мы передвигаем линию уровня по направлению вектора . Точка, в которой линия уровня покидает ОДР (в нашем случае это точка С) и будет решением задачи, т.е. оптимальным планом. Однако, определив точку на чертеже, необходимо определить точное значение ее координат, т.е. переменных X₁ и X₂. Поскольку точка С находится на пересечении прямых, соответствующих уравнениям (1) и (3), решая совместно эти уравнения, получим значения X₁ = 1,33 и X₂ = 2,22.

Решение записывается в виде X(1,33; 2,22).

Подставив найденные значения переменных в выражение для целевой функции, вычисляем ее максимальное значение: F = 9,33.