Реализация принципов симплекс метода для канонической задачи

Универсальный способ решения ЗЛП-симплекс метод

Лекция 19.03.12

Идея симплекс метода заключается:

1. В переходе от одной угловой точки к другой угловой точке.

2. С возрастанием функции цели

3. По грани многогранника

Х₂

Произвольная ЗЛП, мы приводим к КЗЛП.

max

Итак, рассмотрим симплекс метод на примере нашей графической задачи

L=X₁+3X₂

; X₁,X₄,X₅ – базисные, X₂,X₃ – небазисные; L (E) = 5 (значение ф-ции цели)

Пусть, мы находимся в точке Е

Любой угловой точке всегда можно поставить соответствие, так называемые, нормированные стоимости (цен). Реальная цена на первый продукт единица, а на второй продукт тройка.

Эта нормированная цена вычисляется, как зависимость функции L (дохода) от небазисных переменных (любая базисная переменная выражается через небазисную и, подставив её в функцию цели L, получим нормированную стоимость. При этом нормированная стоимость для базисных переменных будет равна нулю. Для точки Е имеем Х1=5-1/6Х3-5/6Х2, тогда L в точке Е будет иметь следующий вид 5-1/6Х3+2*1/6Х2

Для точки Е нормированная стоимость для Х3=-1/6, а для Х2=2*1/6. По второму признаку симплекс метода мы ходим увеличить функцию цели, для этого можно увеличивать Х2, то есть двигаться по линии Х3=0, если мы хотим увеличить Х3, то мы двигаемся по линии Х2=0. Если мы будем двигаться по Х3, то функция цели будет возрастать. Очевидно, что переход надо осуществлять (увеличивать ту переменную) от нуля для, которой нормированная стоимость неотрицательна. Т.е. если цена больше нуля то функция цели увеличится, если меньше нуля – уменьшится, а если равна нулю – сохранится. Если мы попали в такую угловую точку для которой все нормированные стоимости отрицательны или нулевые значит данная точка оптимальная, а нормированные стоимости называются редуцированными ценами. Выбирается редуцированная цена положительная и самая большая, в нашем случае 2*1/6. Начинаем увеличивать соответствующую переменную от нуля, в нашем случае Х2, при этом начинает уменьшаться другая переменная, в нашем случае Х4, пока она не станет равной нулю, то есть базисная Х4 поменялась местами с небазисной Х2, то есть мы попадем в точку D

Увеличение функции цели – положительная нормированная стоимость.

Движение по грани многогранника (не наискосочек) смена одной базисной на одну небазисную.

Переход к новой угловой точке – обнуление старой базисной переменной.

Вот все три принципа мы реализовали.

Дата добавления: 2014-01-03