Монотонность и конечность алгоритма симплекс метода.
Покажем , что применяя алгоритм симплекс метода к З.Л.П. мы получим , что значение функции монотонно убывает. Предположим, что на кокаком то шаге симплекс метода выбран разрешающий столбец rj<0 , а за разрешающую строку выбрана i строка. Покажем что значение функции не возрастает , если мы применим один шаг симплекс метода. Qнов=aij*Q-bi*rj/aij= Q-bi-rj/aij<=0 (bi>=0 rj<0 aij>=0) Qнов>=Q -Qнов<=-Q
Так как многогранник имеет конечное число вершин , то алгоритм симплекс метода будет конечен.
Проблема выражденности.
Если получено в опорном плане число положительных координат меньше чем m , то решение является выражденным , и если полученный план не является оптимальным , т.е. возникает необходимость к новому опорному плану и при этом за разрешающую строку выбирается строка в которой bi=0 Тогда моежт быть проблема зацикливания, т.е. возврат к прежней вершине , для того чтобы избежать этого нужно «расклеить» точки для чего служит ипсилон метод. На ипсилон величину сдвигают прямые , таким образом чтобы раздвигаются вершины. Находят оптимальное решение новой задачи и учитывая ипсилон переходя к страой задаче.
Если в конце преобразований получена таблица , то столбец соответсвующем столбце нет ни одного положительного элемента то Zmin->- бесконечности ( нет решения)
Если в результате преобразований сстрока превратилась ( 0 0 0 0 = 7), то задача не имеет решения по причине не совместимости систем . Нет ОДР.
Если оптимальное решение и соответствующий ему вектор (r) имеет 0 координату то задача на альтернативный оптимум. Что бы найти второе решение берем за разрешающий столбец 0.
Метод искусственного базиса.
Z
=CX->min
В данной задаче нет естественного
базиса. Введем в каждое ограничение
Ax=b искусственную переменную «у»>=0 Z преобразуем в T. М – полож. большое чис
X>=0 -Z задача.
Ах+у=b
Х>=0 у>=0
T=CX+M*y->min (М –задача)
Теорема . Если М задача имеет оптимальное решение , то Z – задача : а) тоже имеет решение , если все искусственные переменные = 0. Б) Z- задача не имеет решения если хотя бы одна из искусственных переменных не равна 0, систем ограничений будет не совместна. Если М задача не имеет решения ,т.е. Tmin ->-бесконечности , то и Z- задача тоже не имеет решения.
Теория двойственности .
Каждой задаче Л.П. можно поставить в соответствие двойственную задачу , решения которой дает немедленное решение прямой задачи.
Стандартная форма.
Z=CX->max
Ax<=b
x>=0 1)
Двойственной задачей к данной З.Л.П. называется задача вида
w=yb->min
YA>=C
Y>=0 2)
Задача 1) и 2) называется пара двойственных задач.
Если по этим правилам построить двойственную задачу к 2) то получим 1) . И в этом смысле задачи называются взаимозаменяемыми или сопряженными.
(y- строка)
(
y1,y2..ym)
a11
a21
am1
Экономический смысл : Экономически двойственную и прямую задачу можно интерпретировать прямая на max прибыль. , при выпуске х1 х2 х3 , а двойственную min -> расходов на ресурсы.
b – сырье ; у1 у2 – оценка ресурсов.