Послеоптимизационный анализ задачи линейного программирования

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

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

Послеоптимизационный анализ предполагает решение следующих задач:

• · Анализ чувствительности оптимального решения к изменению правых частей ограничений (запасов ресурсов);
• · Анализ чувствительности оптимального решения к изменению коэффициентов критерия (цен);
• · Анализ чувствительности оптимального решения к изменению технологических коэффициентов;
• · Добавление новых переменных;
• · Добавление нового ограничения.

Пусть исходная задача дана в канонической форме.

Двойственная к ней будет иметь вид.

Первый вид анализа — анализ чувствительности оптимального решения к изменению правых частей ограничений уже рассмотрен в разделе 5.3. Он является основой для понимания смысла двойственных переменных.

Рассмотрим другие виды анализа.

Добавление нового ограничения

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

Возможны две ситуации:

• · Если прежнее оптимальное решение удовлетворяет новому ограничению, то это решение оптимальное и для измененной задачи:
• · Если прежнее оптимальное решение не удовлетворяет новому ограничению, то в таком случае прежнее оптимальное решение является базисным недопустимым решением и является псевдо-планом. Поэтому решение новой задачи может быть получено двойственным симплексным методом.

Для этого требуется новое ограничение привести к виду уравнения.

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

Пример:

В задаче о работе ЦБК учтем ограничения на кислотные выбросы в атмосферу. Известно, что по первой технологии за 1 смену выбрасывается 1 кг кислотных выбросов, по второй — 3 кг. При этом предельно допустимые годовые нормы выброса составляют 360 кг.

В математической модели появится новое ограничение.

.

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

Проверим, удовлетворяет ли прежнее оптимальное решение новому ограничению:

Ограничение не выполняется.

Преобразуем его к виду уравнения, введя балансовую переменную x₆

Заменим в этом уравнении базисные переменные x1, x2 их значениями через свободные из оптимальной симплекс-таблицы.

Уравнение примет вид.

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

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

В новых условиях комбинат должен работать 240 смен по первой технологии, 40 смен по второй. Расход древесины возрастет до 28 800 м³.