7. Исследование зависимости оптимальных планов от исходных данных задачи ЛП

С помощью симплекс-метода, обычного или двойственного, можно не только находить оптимальные планы задач двойственной пары, но и исследовать, как меняются эти планы при различных изменениях в ограничениях и целевых функциях рассматриваемых задач.

Покажем, как проводятся такие исследования на примере конкретной пары «задача о ресурсах – задача о ценности ресурсов» (см. примеры 11, 15, 20):

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

Пример 21 (Изменение правых частей ограничений). В исходной задаче о ресурсах изменились только запасы ресурсов (правые части ограничений), новые значения запасов равны

соответственно. Записать симплексную таблицу новой задачи в базисе таблицы сформулировать правила построения такой таблицы. Показать, что при достаточно малых значениях приращений ценности ресурсов не изменяются.

Решение. Введем обозначения

Тогда условия задачи с измененными запасами запишутся в виде

Эта запись отличается от записи уравнений в таблице только заменой

на cоответственно. Так как системы уравнений в таблицах

эквивалентны, уравнение новой задачи можно привести к виду

После замены на их выражения получим систему, соответствующую искомой таблице ,

Правила построения таблицы

Таблица отличается от только значениями элементов столбца свободных членов. К свободным членам таблицы надо прибавить поправки, зависящие линейно от приращений Приращения связаны с переменными которые были базисными в и стали свободными в

; эти приращения входят в поправки с коэффициентами, равными элементам

соответствующей строки таблицы из столбцов Приращение

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

При достаточно малых приращениях таблица удовлетворяет (строго) критерию оптимальности – в ней положительны как элементы столбца свободных членов (они близки к положительным значениям 4, 2, 1, 3 из ), так и элементы строки F (совпадают с значениями 2, 1, 3 из ). Совпадение ценностей ресурсов в исходной задаче и задаче с малыми изменениями запасов ресурсов следует из совпадения строк F (без свободных членов) в таблицах и

; в каждой их этих задач

Пример 22 (Изменение коэффициентов целевой функции). В исходной задаче о ресурсах изменились только доходы от реализации единицы готовой продукции (коэффициенты целевой функции), новые значения доходов равны соответственно.

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

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

К элементам строки F таблицы прибавляются поправки, зависящие линейно от приращений .

При достаточно малых приращениях элементы строки F положительны и таблица удовлетворяет критерию оптимальности. В этом случае оптимальный план задачи с измененными доходами совпадает с оптимальным планом исходной задачи о ресурсах.

Пример 23. В исходной задаче о ресурсах запасы 9, 10, 11, 13 изменились и составляют 9, 10, 14, 8 соответственно. Найти новый оптимальный план производства.

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

(см. пример 21). Поэтому всегда можно использовать как начальную для решения задачи с измененными запасами двойственным симплекс-методом.

Далее находим свободные члены таблицы :

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

Пример 24. В исходной задаче о ресурсах доходы 12, 4, 5 от реализации трех видов продукции изменились и составляют 12, 2, 7 соответственно. Найти новый оптимальный план производства.

Решение. Симплексная таблица задачи с измененными доходами, построенная с помощью таблицы исходной задачи, допустима при любых значениях приращений (см.

плекс-методом. В условиях данного примера

Далее находим элементы строки F таблицы :

Как и в предыдущем примере, использование заключительной таблицы исходной задачи позволяет найти новый оптимальный план быстрее, чем при «прямом» решении задачи с измененными условиями симплекс-методом. Таблица , содержащая новый оптимальный план , , ,

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

Пример 25. В условии изменилась только величина запаса самого ценного ресурса. При каких изменениях этой величины ценности ресурсов не меняются?

Решение. Ценности ресурсов найдены в примере 20, самым ценным оказался третий ресурс. Рассмотрим таблицу которая получается из таблицы примера 21 при

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

Таким образом ценности ресурсов не меняются, если запас самого ценного (третьего) ресурса изменяется в пределах от 11-1=10 до 11+(6/7).

Пример 26. В условии изменилась только величина максимального из доходов от реализации единицы продукции. При каких изменениях этой величины оптимальный план производства не меняется?

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

Таблице соответствует опорный план

, совпадающий с оптимальным планом исходной задачи о ресурсах. Этот опорный план будут оптимальным при тех значениях , для которых удовлетворяет условию оптимальности, т. е. при выполнении системы неравенств Решая эту систему, получим Таким образом оптимальный план производства не меняется, если доход от реализации первого вида продукции изменяется в пределах от 12 – 2=10 до 12+6=18.

Пример 27. Для улучшения качества продукции в процесс производства вводится новый (пятый) вид ресурса. Технологические коэффициенты и запас нового ресурса равны 1, 2, 3 и 9 соответственно. Найти оптимальный план производства и величину максимального дохода в новых условиях.

Решение. Ведению нового ресурса соответствует введение дополнительного ограничения в стандартную модель задачи о ресурсах. Если оптимальный план исходной задачи удовлетворяет дополнительному ограничению, то он, очевидно, остается оптимальным для задачи с этим дополнительным ограничением. В условии данного примера оптимальный план исходной задачи не удовлетворяет дополнительному ограничению, Чтобы найти новый оптимальный план, совсем не обязательно решать заново задачу ЛП с дополнительным ограничением. Гораздо быстрее приводит к цели (и не только в данном примере) введение дополнительного ограничения в таблицу исходной задачи.

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

таблицы . Тогда новое равенство запишется в виде

или, после приведения подобных членов,

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

Таблица удовлетворяет условию оптимальности (это следует из способа построения ). Применяя двойственный симплекс-метод, уже после первого преобразования получим таблицу , содержащую новый оптимальный план . Новый оптимальный план хуже старого – доход от реализации всей произведенной продукции уменьшился (). Этого и следовало ожидать, т. к. введение дополнительного ограничения не может привести к увеличению максимального значения целевой функции (попробуйте обосновать это утверждение и дать ему геометрическую интерпретацию).

Пример 28. Технологические коэффициенты и доход от реализации единицы нового (четвертого) вида продукции равны 1, 3, 1, 2 и 10 соответственно. Выгодно ли введение в план производства нового вида продукции? Если да, найти новый оптимальный план и величину максимального дохода.

Решение. Обозначим объем производства нового вида продукции через Стандартная модель задачи о ресурсах, учитывающая возможность производства нового вида продукции, отличается от модели исходной задачи дополнительными слагаемыми в ограничениях и целевой функции:

Переменной соответствует дополнительное ограничение

двойственной задачи о ценности ресурсов. Оптимальный план

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

Чтобы найти новый оптимальный план и , введем в таблицу дополнительный столбец, соответствующей переменной прямой задачи и переменной из канонической формы

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

выражаются через свободные переменные по формулам (см. столбцы таблицы ):

После подстановки этих выражений в равенство новое ограничение запишется в виде

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

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

Введение в план производства нового вида продукции привело к увеличению дохода на