33. Постановка двойственной задачи лп.

Двойственная задача Y1 >=0 Y2>=0 Y3 >=0

2 Y1+7 Y2+5 Y3 >=3 4 Y1+2 Y2+8 Y3 >=4

0 Y1+2 Y2+4 Y3 >=3 8 Y1+6 Y2+3 Y3 >=1

12Y1+8 Y2+48Y3 =min F1

в двойственной вначале запишем ограничения >=0, для каждой двойственной переменной Y. Далее под ними записываются неравенства относительно коэффициентов целевой функции, представленных ограничениями справа. Для этого в каждом столбце левой части ограничений прямой задачи выбираются коэффициенты при неизвестных и записываются, как левые части ограничений для двойственных переменных в транспонированном виде. Сравним типы неравенств в подстановке прямой и двойственных задач. Если в прямой для ресурсов первого вида реализуется равенство (12=12), то переменная оказывается больше 0: (Y1=1/4). Для ресурсов третьего вида реализуется уже неравенство вида <: (28<48), то здесь двойственная переменная уже оказывается равной 0: (Y3=0).

Если в прямой задаче реализуется ограничение как равенство, то двойственной задаче, соответствующее ограничение вводится как жесткое неравенство, и, наоборот, если в прямой имеется жесткое неравенство, то в двойственной соответствующее ограничение выглядит равенством.

34. Экономическое значение двойственных оценок

Коэффициенты в индексной строке для дополнительных переменных характеризуют эффективность используемых ресурсов и называются двойственными, или объективно обусловленными оценками ресурсов. Свойства двойственных оценок. Чем выше оценка, тем эффективнее используется ресурс. Двойственная оценка характеризует прирост прибыли на единицу прироста соответствующего ресурса. Например, ресурсы второго вида наиболее эффективны для производства. Каждая единица прироста этого ресурса обеспечивает увеличение целевой функции на 3/2 единицы. Двойственная оценка недоиспользуемых ресурсов всегда равна нулю. Логически рассуждая прирост ресурсов третьего вида привел бы к росту их недоиспользуемых остатков.

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

35. Модифицированный симплекс-метод.

Разновидностью симплекс-метода является модифицированный симплекс-метод (МСМ), позволяющий существенно снизить затраты времени на решение задач. При этом основной объём расчётов по симплексным преобразованиям ограничивается лишь частью чисел основания матрицы, состоящей только из столбцов, относящихся к дополнительным переменным.

Заполнение таблицы B1* начнем с формирования столбцов ci, pi, xi - составляющих базис плана , полученный при использовании канонической формы с дополнительными переменными x5, x6 , x7

Шаг 1 - формирование показателей корректирующей строки и расчет F

Шаг 2 - переход к таблице A* - заполнение столбца N1

Шаг 3 : Расчет показателей первой индексной строки табл.A*

Шаг 4 : Проверка условия оптимальности в табл.A*

Шаг 5 : Выбор ключевого столбца - переход к таблице B1*

Шаг 6 -Формирование показателей исходной строки

Шаг 7 -Формирование показателей ключевого столбца в таблице B1*

Шаг 8: Выбор ключевой строки - переход к таблице A*: min { 12/4; 8/2 ; 48/8}= 12/4 - переменная x2 вводится в базис, переменная x5 исключается из базиса. Переход к табл.B2*

Таблица A* Шаг 2 - переход к таблице A* - заполнение столбца N1

Шаг 3 : Расчет показателей первой индексной строки табл.A*

Шаг 4 : Проверка условия оптимальности в табл.A*.Нет.

Шаг 5 : Выбор ключевого столбца (X2) - переход к таблице B1*

Если все оценки переменных zj – cj≥ 0, значит получены оптимальный план и максимальная прибыль.