double arrow

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

3

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

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

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

Теорема 2.

Теорема 1.

Теоремы

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

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

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

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

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




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

F = c1x1 + c2x2 + … cnxn ® min сводится к

F = -F = - c1x1 - c2x2 - … cnxn ® max;

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

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

ai1х1 + ai2 х2 + ai3x3 + … ain × хn £ (³) bi преобразуется в

ai1х1 + ai2 х2 + ai3x3 + ain× хn + xn+1 = bi

Число вводимых дополнительных неотрицательных переменных при преобразовании ограничений – неравенств в ограничение – равенства равно числу преобразуемых неравенств.

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

ai1х1 + ai2 х2 + ain хn = bi

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

ai1х1 + ai2 х2 + … ain хn £ bi

- ai1х1 - ai2 х2 - … ain хn ³ - bi

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

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

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

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

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



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

Таким образом, решением задачи будет та угловая точка ОДР, которая является крайней в направлении линии уровня.

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



3




Сейчас читают про: