Решение двойственной задачи и определение интервалов устойчивости двойственных оценок оптимального решения

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

Пример 11. При решении двойственной задачи, составленной в примере 9, симплексным методом, получаются следующие результаты.

Базисные переменные: y₁, y₂, неосновные переменные: y_3, y₄, y₅.

(2.8)

Выражение целевой функции на оптимальном решении:

(2.9)

Предположим, что запасы b_i ресурсов каждого вида изменились на ∆b_i единиц (i=1, 2, 3). Запишем исходное выражение целевой функции (1.42) с новыми коэффициентами:

(2.10)

Подставим в это выражение полученные выражения для оптимальных решений у₁ и у₂ из системы (1.42), и после преобразований получим:

(2.11)

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

(2.12)

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

Например, если , то решение останется оптимальным, т.к. все неравенства удовлетворены. При этом . Решение исходной задачи следует из соответствия решений взаимно-двойственных задач (см. таблицу 21): оптимальное значение x₁ равнокоэффициенту при переменной y₄, значение x₂ равнокоэффициенту при переменной y₅, значение x₅ равнокоэффициенту при переменной y₃ в выражении целевой функции (1.46):

. (2.13)

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

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

1) Полагая , получаем систему неравенств

(2.14)

Следовательно, решение останется оптимальным, если

. (2.15)

2) Полагая , получаем систему неравенств

(2.16)

Следовательно, решение останется оптимальным, если

. (2.17)

3) Полагая , получаем неравенство

. (2.18)

Следовательно, решение останется оптимальным, если

. (2.19)

Итак, формулы (2.15), (2.17) и (2.19) определяют интервалы устойчивости двойственных оценок по каждому ресурсу при условии, что остальные ресурсы остаются в неизменном количестве.

Дата добавления: 2015-06-27