2.7. ИССЛЕДОВАНИЕ МОДЕЛЕЙ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ЧУВСТВИТЕЛЬНОСТЬ
Теория двойственности позволяет анализировать модели ЛП на чувствительность.
Рассмотрим обычную задачу ЛП в виде
максимизировать 
(2.7.1)
(2.7.2)
xj³0.
Напомним ее экономическую интерпретацию. Целевая функция L(x) -это доход от реализации плана производства x; aij -интенсивность расходования i-го ресурса при j-м способе производства; bi- имеющийся уровень i-го ресурса.
1. Варьирование ограниченных ресурсов. Предположим, что величины ресурсов b=|| bi || варьируются. Тогда возникают вопросы: при каких вариациях правых частей ограничений найденный оптимальный план x0 не изменяется; как эти вариации влияют на функцию максимального дохода Lmax? Ответ на эти вопросы дает анализ соответствующей задачи ЛП на чувствительность.
Пусть ограничение bi получают некоторые вариации Dbi, что приводит к вариациям плана x0, x0= x0(b+Db) и функции Lmax (x0(b0+Db)). Предположим, эти вариации Db таковы, что план x0(b+Db) остается допустимым ( т.е. удовлетворяет условию неотрицательности). Найдем отношения приращения
DLmax(b)= Lmax (x0(b0+Db))- Lmax (x0(b)) к Db.
Имеем
(2.7.3)
где b рассматривается как варьируемый параметр.
Вспомним, что в соответствии с основной теоремой двойственности
, (2.7.4)
и, подставляя (2.7.4) в (2.7.3), получим
. (2.7.5)
Таким образом, оптимальные значения двойственных переменных 
определяют вклад каждого ресурса в доход Lmax при оптимальном решении x0. Эта величина численно равна дополнительному доходу при увеличении i-го ресурса bi на единицу при условии, что ресурсы используются оптимальным образом.
Итак, величины служат показателями важности соответствующих ресурсов для системы. Чем большее значение при некотором i, тем существеннее вклад i-го ресурса в функцию максимального дохода Lmax и тем выгоднеее его увеличение. Если для некоторого =0, то i-й ресурс не является существенным ограничением для системы.
Заметим, что этот вывод хорошо согласуется с результатами теоремы 2.6 двойственности, которая связывает величины с ограничениями прямой задачи.
Обозначим через Ax матрицу оптимального базиса задачи ЛП при векторе ресурсов b. Очевидно соответствующее оптимальное решение
xопт= A-1x b.
Предположим, что мы изменили вектор ресурсов b=|| bi || на bн=b+ Db и хотим узнать, как это повлияет на оптимальное решение. Для этого найдем новое соответствующее базисное решение
xн = А-1хbн = А-1х(b+Db).
Если все компоненты xiн ³ 0, то это решение xн = [xiн] оптимально (т.е. оптимальный базис не изменился). В противном случае нужно произвести поиск нового решения, для этого можно применить двойственный симплекс-метод, начиная с текущего базисного решения xн.
2. Варьирование целевой функции. Теперь рассмотрим случай, когда варьируются коэффициенты {cj}, j= 1,2,.,n... Попытаемся выяснить условия, при которых найденный ранее оптимальный план останется оптимальным при таких вариациях.
Пусть вариациям 
подвергнется коэффициент 
. Обозначим через Jб, Jнеб множество индексов базисных и небазисных векторов в оптимальном плане x0 соответственно.
Найдем значения оценок 
после вариации cr для двух случаев:
1) rÎ Jнеб , тогда 
для всех j¹r ;
для j=r ; (2.7.6)
2) rÎ Jб,
jÎJнеб (2.7.7)
Очевидно, что для сохранения оптимальности прежнего плана при вариациях коэффициента cr необходимо и достаточно сохранение знаков оценок для всех небазисных переменных. Поэтому из условий 
³0 в соответствии с формулами (2.7.6) и (2.7.7) можно определить допустимые вариации коэффициента , при которых сохраняется прежнее оптимальное решение.
До сих пор мы рассматривали вариации лишь одного коэффициента целевой функции. Этот же подход можно применить, когда варьируются одновременно несколько коэффициентов ci.
В таком случае получим соотношения, аналогичные (2.7.7), в которых оценки 
будут функциями уже нескольких параметров (d1, d2,.,dr)...
Решая совместно систему неравенств вида (c1, c2,.,cr)³0,jÎJнебы находим условия для вариаций , при которых прежний оптимальный базис сохраняется.
Эта задача относится к классу задач параметрического программирования [12].
3. Варьирование элементов матрицы ограничений A. Рассмотрим лишь случай вариации компонентов небазисных векторов Aj=[aij], i=1,2,...,m, поскольку исследование вариаций компонент базисных векторов Ai довольно сложное, легче заново решить задачу с новыми условиями.
Итак, пусть небазисный вектор Aj=[amj] изменился. Нужно выяснить, останется ли оптимальным текущий базис. Для этого полезно применить теорию двойственности. Пусть оптимальный базис прямой задачи Ax, а соответствующие оптимальные значения двойственных переменных . Как известно, условие оптимальности ³0, " jÎ Jнеб Вместе с тем в соответствии с (2.6.11), 
. Значит если 
,то прежний оптимальный базис сохраняется.
4. Добавление еще одного способа производства. Предположим, что первоначально задача имеет вид
максимизировать 
(2.7.8)
при условиях
, (2.7.9)
xj³0.
Предположим, что найден оптимальный базис {Ai}, iÎ Jб и соответствующие оптимальные решения прямой 
и двойственной задач.
Пусть прибавляется еще один (n+1)-й способ производства, которому отвечает вектор технологических затрат An+1=[ai n+1] и коэффициент целевой функции cn+1. Тогда будем иметь следующую задачу:
максимизировать 
(2.7.10)
, (2.7.11)
xj³0, j=1, 2,., n+1. (2.7.12)
Нужно определить, изменится ли при этом прежнее оптимальное решение и при каком значении коэффициента cn+1 выпуск (n+1)-го продукта будет рентабельным (то есть 
).
Чтобы оптимальное решение после ввода вектора An+1 не изменилось , необходимо, чтобы вектор An+1 и переменная xn+1 оставались небазисными, т.е., чтобы Dn+1³0. На основании теории двойственности получим
.
Если 
, то прежний оптимальный план не изменится после включения выпуска (n+1)-го вида продукции.
Если же 
, то выпуск (n+1)-го вида продукции становится рентабельным, и прежний оптимальный план изменяется.
Пример 2.10.
Предприятие выпускает изделия двух видов, для изготовления которых используются ресурсы двух типов. Пусть прибыль от продажи изделий составляет соответственно c1=2 и c2=3, объем ресурсов равняются b1=32, b2=24 соответственно. Нормы затрат ресурсов на единицу выпуска задаются такой матрицей:
1. Нужно найти оптимальный план выпуска, который максимизирует суммарный доход и исследовать чувствительность целевой функции к вариации ограниченных ресурсов, т.е. как изменится суммарный доход при увеличении на единицу любого из видов ресурсов.
2. Пусть первый ресурс b1 увеличился до 35, а второй уменьшился до 20. Как изменится при этом оптимальное решение, останется ли оптимальным прежний базис?
3. Пусть вводится дополнительное ограничение на выпуск первого продукта x1³ 6. Определить новый оптимальный план.
4. Пусть предприятие может дополнительно выпускать третий вид продукции, для которого c3=4, а нормы затрат ресурсов составляют a13=3; a23=2. Найти оптимальный план с учетом этого условия и определить, при каком значении c3 производство третьего вида изделий будет рентабельным.
Решение. Математическая модель задачи:
max (2 x1+3 x2)
при условиях
3 x1+2 x2 £ 32;
1 x1+2 x2 £ 24;
x1³0, x2³0.
Решим эту задачу симплекс-методом и через две итерации найдем оптимальный план (табл.2.27).
Получим
=4; 
=10; max (2 x1+3 x2)=38.
Матрица 
образована небазисными векторами A4, A5 в табл.2.27.
Таблица2.27
|
cj |
2 |
3 |
0 |
0 |
||
|
Bx |
A0 |
A1 |
A2 |
A4 |
A5 |
|
|
2 |
х1 |
4 |
1 |
0 |
|
|
|
3 |
х2 |
10 |
0 |
1 |
|
|
|
D |
38 |
0 |
0 |
|
|
Оптимальные значения двойственных переменных находим в индексной строке табл.2.27: 
;
. Анализируя значения 
, 
, видим, что при увеличении на единицу первого ресурса мы получим приращение ц.ф. 
а при увеличении на единицу второго ресурса 
. Итак, второй ресурс оказывается более важным для системы и его повышение выгоднее.
Пусть первый ресурс увеличен до 35 единиц, а второй уменьшен до 20 единиц, тогда новый вектор 
=[ 35; 20 ]T. Найдем новое базисное решение для этого вектора:
Поскольку
, то это решение будет оптимально (так как не изменились оценки D4 и D5 для небазисных векторов).
Пусть введено дополнительное ограничение x1³6. Приведем его к стандартному виду:
x1-x6=6R-x1+x6=-6. Допишем эту строку в симплекс-таблице 2.27, и одновременно справа от нее столбец A6. Получим главную часть табл.2.28.
Таблица 2.28.
|
ci |
2 |
3 |
|||||
|
Bx |
A0 |
A1 |
A2 |
A4 |
A5 |
A6 |
|
|
2 |
x1 |
4 |
1 |
0 |
|
- |
0 |
|
3 |
x2 |
10 |
0 |
1 |
|
|
0 |
|
x6 |
-6 |
-1 |
0 |
0 |
0 |
1 |
|
|
|
|
-2 |
0 |
0 |
|
|
1 |
Анализируя ее видим, что базисный столбец A1 не является единичным, и нужно исключить переменную x1 в строке x6. Для этого прибавим к строке x6 строку x1, в результате получим новую строку 
, которую дописываем в табл.2.28 внизу, а строку x6 можно вычеркнуть.
Так как компонента 
= -2<0, то базисное решение { x1 , x6 , x'6} -это псевдоплан: и дальше для продолжения итераций применим двойственный симплекс-метод.
Направляющая строка , направляющий столбец A4. Выполнив одну итерацию двойственного симплекс-метода, получим симплекс-таблицу 2.29.
Таблица 2.29.
|
ci |
2 |
3 |
|||||
|
Bx |
A0 |
A1 |
A2 |
A4 |
A5 |
A6 |
|
|
2 |
x1 |
6 |
1 |
0 |
0 |
0 |
-1 |
|
3 |
x2 |
7 |
0 |
1 |
|
0 |
|
|
x4 |
4 |
0 |
0 |
-1 |
1 |
-2 |
|
|
D |
33 |
0 |
0 |
|
0 |
|
Так как
=6>0,
=7>0, то это новое решение оптимально. При этом Lmax==33.
Проверим целесообразность введения третьего способа производства. Для этого рассмотрим столбец 
В соответствии с теорией двойственности 
. Так как D3<0 , то столбец A3 целесообразно ввести в базис. В соответствии с методом обратной матрицы вычисляем его вид 
, в котором его можно дописать в таблицу 2.27:
Дописав столбец A3 в симплекс-таблиу оптимального решения исходной задачи (табл.2.27), получим табл. 2.30. При этом 
.
Таблица 2.30.
|
ci |
2 |
3 |
4 |
||||
|
Bx |
A0 |
A1 |
A2 |
A4 |
A5 |
A3 |
|
|
|
x1 |
4 |
1 |
0 |
|
|
|
|
3 |
x2 |
10 |
0 |
1 |
|
|
|
|
D |
38 |
0 |
0 |
|
|
|
Выполнив одну итерацию симплекс-метода, получим симплекс-таблицу 2.31.
Таблица 2.31.
|
ci |
2 |
3 |
4 |
||||
|
Bx |
A0 |
A1 |
A2 |
A4 |
A5 |
A3 |
|
|
4 |
x3 |
8 |
2 |
0 |
1 |
-1 |
1 |
|
3 |
x2 |
4 |
|
1 |
-1 |
|
0 |
|
D |
44 |
|
0 |
1 |
|
0 |
Поскольку все элементы ее индексной строки Dj ³ 0, то это решение оптимально: 
=8; =4. При этом значение ц.ф. увеличилось до 44 единиц.
