Добавление новой переменной

Пусть в математической модели (1-3) появилась новая переменная

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

Если в исходной задаче появляется новая переменная, то в двойственной задаче появляется новое ограничение

(6)

или

Вектор – прежнее оптимальное решение с нулевой n+1-ой компонентой является допустимым решением новой задачи (1’-3’). Если выполняется условие (6), то вектор – прежний вектор оптимальных двойственных оценок – допустимое решение двойственной к (1’-3’) задачи. Соотношения дополняющей нежесткости для этих двух решений пополнились условием

и выполняются за счет . Значит, по второй теореме двойственности,решение – оптимальное для новой задачи.

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

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

Для получения нового оптимального решения следует дополнить прежнюю оптимальную симплекс-таблицу новым столбцом

,
а оценку переменной найти как разность левой и правой части ограничения (6) двойственной задачи

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

Пример:

Предположим, что у ЦБК появилась возможность работать по третьей технологии с расходом за смену 103 кубометра древесины, производительностью в смену 60 тонн целлюлозы, 40 центнеров лигнитов и 20 килограммов отравляющих веществ.

, .

Обозначив – время работы по третьей технологии, ищем решение в виде для новой математической модели

(7)

Новая переменная порождает в двойственной задаче новое ограничение

(8)

Проверим, удовлетворяет ли этому ограничению вектор оптимальных двойственных оценок исходной задачи:

Ограничение (8) не выполняется, суммарная оценка полезности произведенной за смену продукции (104 м³) превышает затраты (103м³), значит прежнее решение не является оптимальным.

Для определения нового оптимального решения включим в прежнюю оптимальную симплекс таблицу столбец с переменной .

В исходную симплекс-таблицу новый вектор условий войдет в виде

, так как менялись знаки в первых двух уравнениях (см. раздел 5.5). В оптимальной симплекс-таблице он преобразуется к виду

Оценка переменной определится как разность левой и правой части ограничения двойственной задачи (8)

Оценка положительна, что нарушает условие оптимальности опорного плана. Решаем далее симплекс-методом

Исходная симплекс-таблица

На следующей итерации получим оптимальное решение новой задачи

Комбинат должен работать 75 смен по первой технологии, 187.5 смен по третьей дополнительной технологии. При этом расход древесины будет наименьшим и составит 26812.5 кубометров.