Алгоритм симплекс-метода

Экономический смысл процедур симплекс-метода.

Итак, находились в точке Е, выпускаем только первый продукт, второй не выпускаем (Х1=5, Х2=0). Первый ресурс израсходовали полностью Х3=0, второй ресурс в избытке Х4=1, сурпласовая вторая переменная равна 4. Начинаем выпускать второй продукт до тех пор, пока хватит 2-ого ресурса Х4, при этом первый ресурс расходуется полностью. Итак, мы перешли в точку D со следующими параметрами. L (D) = 6,86

L(D)=6,86+0,14Х3-1,86Х4

Нормированная стоимость для Х3 0,14,для Х4 -1.86, есть смысл Х4 оставить равным нулю, а Х3 увеличить от нуля. Т.е. двигаться по грани Х4=0. Двигаясь по грани Х4=0 будем уменьшать значение Х1 до нуля. Т.е. заменим переменную Х3 на Х1, т.е. перейдем в точку К. Точка имеет следующие координаты К=….

L(К)=9-0,5Х1-1,5Х4

Имеем нормированные стоимости для Х1 -0,5, для Х4 -1,5, для остальных равно нулю. Следовательно нельзя увеличить функцию цели от 9. Следовательно точка К оптимальная, а минус 0,5 и минус 1,5 редуцированные цены.

1. Пусть есть некакая угловая точка

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

3. Переменная, выбранная в пункте 2, теперь пойдет в базис, т.е. она будет увеличиваться от нуля. Теперь ищется первая переменная из базиса, которая обнулится или станет равной нулю.

4. Эти две переменные меняем местами (т.е. новую небазисную переменную обнуляем и ищем новую угловую точку и переходим к пункту 2).

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

****

То вспомогательная задача имеет вид *

Сделать задачу в симплекс-методе, привести в каноническому виду.

Каноническое понятие двойственности

Можно рассматривать исходную задачу, как задачу распределения ресурсов на максимум доходов.

Экстенсивный путь развития любого предприятия включает в себя следующие стратегии:

1. Докупать ресурс ясно по такой цене, чтобы доход от нового ресурса превысил затраты на его покупку.

2. Продавать излишки ресурсов по любой цене.

3. Подать часть ресурсов по «хорошей цене», потерять в продукции, но компенсировать продажей ресурсов.

4. Продать все ресурсы, но по таким ценам, чтобы получить больше, чем L_{оптимальное}.

5. Выпускать Х_опт получать L_опт.

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

Двойственная задача как бы противник, который нам не дает заработать больше, чем L_опт. По последней стратегии всегда получим, т.е. двойственная задача описывает виртуальный рынок ресурсов.

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