Геометрический способ. Геометрическая интерпретация

Геометрическая интерпретация

Методы решения задач нелинейного программирования.

Переход от одной формы задачи ЛП к другой

Теорема 2.

Теорема 1.

Теоремы

Теперь сформулируем теоремы о свойствах основной задачи ЛП.

Множество планов основной задачи ЛП является выпуклым (если оно непусто).

Если основная задача ЛП имеет оптимальный план, то максимальное значение целевая функция принимает в одной из вершин многогранника решений.

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

Как уже было сказано выше, существуют стандартная форма задачи линейного программирования и каноническая форма. В любом случае ищется экстремум целевой функции, т.е. либо максимум, либо минимум. Таким образом, можно выделить задачи на максимум и задачи на минимум. Существуют правила перехода от одной формы задачи ЛП к другой, т.е. переход от задачи на поиск максимума целевой функции к задаче поиска минимума целевой функции целевой функции (Fmax «Fmin), а также переход от стандартной задачи ЛП к канонической и наоборот (стандартная «каноническая). Рассмотрим эти правила.

2.3.1. Сведение задачи минимизации к задаче максимизации:

F = c₁x₁ + c₂x₂ + … c_nx_n ® min сводится к

F = -F = - c₁x₁ - c₂x₂ - … c_nx_n ® max;

2.3.2. Переход от стандартной задачи к канонической.

Ограничение – неравенство (£) исходной задачи можно преобразовать в ограничение – равенство добавлением к его левой части дополнительной неотрицательной переменной, т.е.

a_i1х₁ + a_i2 х₂ + a_i3x₃ + … a_{in ×} х_n £ (³) b_i преобразуется в

a_i1х₁ + a_i2 х₂ + a_i3x₃ + a_in× х_n + x_n+1 = b_i

2.3.3. Переход от канонической задачи к стандартной:

a_i1х₁ + a_i2 х₂ + a_in х_n = b_i

можно записать в виде неравенств

a_i1х₁ + a_i2 х₂ + … a_in х_n £ b_i

- a_i1х₁ - a_i2 х₂ - … a_in х_n ³ - b_i

3.1. Геометрический способ

3.1.1. Пример геометрической интерпретации задачи ЛП

3.1.2. Этапы решения задачи

Существуют два основных метода решения задачи линейного программирования: решение на основе геометрической интерпретации (геометрический способ) и так называемый симплекс-метод.

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

Целевая функция позволяет провести семейство параллельных прямых - так называемых линий уровня, отвечающих определенному значению линейной формы (т.е. целевой функции). При этом, смещение прямой по направлению нормального вектора, координаты которого равны коэффициентам при соответствующих переменных в целевой функции приводит к увеличению значения целевой функции; в противоположном направлении – к уменьшению.

Непустое множество задачи ЛП образует выпуклый многогранник. Каждая вершина многогранника представляет собой опорный план. В одной из вершин многоугольника (т.е. для одного из опорных планов значения целевой функции является максимальным (при условии, что функция ограничивает сверху на множестве планов.