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

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

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

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

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

К каким последствиям приведет сокращение объема ресурсов?

Что произойдет, если ввести в рассмотрение новую управляемую переменную?

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

Исходная и двойственная задачи.

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

n

максимизировать  cj xj (1)

j=1

при наличии ограничений

n

 a ij x j <= b i (i=1,2, ... , m), (2)

j=1

xj >= 0 (j=1,2, ... , n). (3)

и

m

минимизировать  bi yi (4)

i=1

при ограничениях

n

 a ij yi >= cj ( i=1,2, ... , n), (5)

j=1

yi >= 0 ( i=1,2, ... , m ). (6)

В теории линейного программирования первую задачу [ cоотношения (1)-(3)] называют исходной , а вторую [соотношения (4)-(6)] двойственной по отношению к первой.

Двойственная задача - это на 90 градусов повернутая исходная задача. Верны утверждения:

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

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

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

4. направление знаков неравенства в исходной модели противоположно направлению знаков неравенства в двойственной модели; требование максимизации в исходной задачи в двойственной заменено требованием минимизации.

Пример:

исходная задача:

максимизировать: 4 x1 + 5x2 + 9x3 (7)

при следующих ограничениях:

1x1 + 1x2 + 2x3 <=16

7x1 + 5x2 + 3x3<=25 (8)

x1>=0, x2>=0, x3>=0

двойственная задача:

минимизировать: 16y1 + 25y2 (9)

при следующих ограничениях:

1y1 + 7y2 >=4,

1y1 + 5y2>=5, (10)

2y1 + 3y2 >=9,

y1 >=0, y2>=0.