Гельруд Я.Д. Линейное программирование. Учебно-методический комплекс
Подождите немного. Документ загружается.
69
Таблица 3.7
Редуцированная симплекс-таблица
Итера-
ция
Базис
Пробное
решение
x
1
x
2
x
3
x
4
Строка
x
0
0
–
4
–
5
–
9
–
11 0
x
5
15 1 1 1 1 1
1 x
6
120 7 5 3 2 2
x
7
100 3 5 10 15 3
x
1
x
2
x
3
x
7
x
0
220/3 –9/5 –4/3 –5/3 –11/15 0
2 x
5
25/3 4/5 2/3 1/3 –1/15 1
x
6
320/3 33/5 13/3 5/3 –2/15 2
x
7
20/3 1/5 1/3 2/3 1/15 3
x
5
x
2
x
3
x
7
x
0
1105/12 9/4 1/6 –11/12 7/12 0
x
1
125/12 5/4 5/6 5/12 –1/12 1
3 x
6
455/12 –33/4 –7/6 –13/12 5/12 2
x
7
55/12 1/4 1/6 7/12 1/12 3
x
5
x
2
x
4
x
7
x
0
695/7 13/7 3/7 11/7 5/7 0
4
x
1
50/7 10/7 5/7
–
5/7
–
1/7 1
x
6
325/7
–
61/7
–
6/7 13/7 4/7 2
x
3
55/7
–
3/7 2/7 12/7 1/7 3
3.7. Матричное представление
Матричная запись линейной модели выглядит следующим образом:
максимизировать сх (3.7.1)
при ограничениях
Ах ≤ b, (3.7.2)
x≥0. (3.7.3)
Здесь с, х, b – вектора, составленные из коэффициентов целевой функции
(2.3.2), искомых значений переменных и заданных ограничений (2.3.1)
соответственно. Матрица А состоит из коэффициентов при
переменных в
системе ограничений (2.3.1). В принятых обозначениях соответствующую
70
симплекс-таблицу (аналогичную таблице, приведенной на рис. 3.6.) на этапе
первой итерации можно представить в виде
,
... ...
0 ... 0 0 ... 0
2121
21
⎥
⎦
⎤
⎢
⎣
⎡
−−−
nn
n
UUUAAAb
ссс
(3.7.4)
где [U
i
] – столбец с единицей на пересечении с i-й строкой и с нулями на
пересечении со всеми остальными строками. (Строке 0 в матрице (4) принято
отводить самую верхнюю позицию.) В еще более компактном виде вместо
(3.7.4) будем иметь
,
I
0 0
111
⎥
⎦
⎤
⎢
⎣
⎡
−
m
m
Ab
с
(3.7.5)
где 0
pq
– матрица с р строками и q столбцами, состоящая целиком из нулей, a
I
m
– m-мерная единичная матрица.
Тема 4. Анализ моделей на чувствительность
4.1. Анализ модели после нахождения оптимального решения
Опытный руководитель, использующий при решении задач
организационного управления методы линейного программирования, редко
довольствуется лишь численными значениями управляемых переменных, при
которых достигается оптимум, если та или иная модель не применялась им
многократно и, следовательно,
диапазон ее возможностей заранее не известен.
В большинстве же случаев руководитель хочет знать, в каком интервале
можно менять входные параметры без существенного отклонения от
найденного оптимума и без значительного нарушения структуры базиса, фор-
мирующего оптимальное решение. Исследование, позволяющее ответить на
эти вопросы, носит название анализ модели на чувствительность (или
анализ модели
при известном оптимальном решении).
На многие вопросы, связанные с анализом на чувствительность, легко
71
ответить, располагая численными данными на заключительной симплекс-
итерации. К числу таких вопросов относятся, в частности, следующие:
• останется ли решение оптимальным, если уменьшится удельный вклад в
прибыль одной из базисных переменных?
• к каким последствиям приведет сокращение объема ресурсов?
• что произойдет, если ввести в рассмотрение новую управляемую
переменную?
В последующих
разделах излагаются наиболее важные положения и
принципы, которые лежат в основе анализа на чувствительность моделей
линейного программирования. Предлагаемые здесь методы применимы к
задачам
максимизации
∑
=
n
j
jj
xc
1
(4.1.1)
при ограничениях
i
n
j
jij
bxа ≤
∑
=1
(i=l, 2, ..., m), (4.1.2)
x
j
≥ 0 (j=1, 2,..., n).
Приемы, используемые при анализе модели на чувствительность, по своей
сути весьма просты, хотя и отличаются некоторой громоздкостью.
Попытаемся разобраться в существе вопроса на примере, рассмотренном в
разд. 3.2, т. е. для задачи распределения ресурсов. Запишем для этой задачи
исходную и «заключительную» системы уравнений, обозначив их
соответственно через (I) и (F):
1
x
0
–4x
1
– 5x
2
– 9x
3
– 11x
4
=0 (строка 0),
1x
1
+ 1x
2
+ 1x
3
+ 1x
4
+1x
5
=15 (строка1), (I)
7x
1
+ 5x
2
+ 3x
3
+ 2x
4
+1 x
6
= 120 (строка 2),
3x
1
+ 5x
2
+ 10x
3
+15x
4
+ l x
7
= 100 (строка 3),
и
1x
0
+
7
3
x
2
+
7
11
x
4
+
7
13
x
5
+
7
5
x
7
=
7
695
(строка 0),
72
1x
1
+
7
5
x
2
–
7
5
x
4
+
7
10
x
5
–
7
1
x
7
=
7
50
(строка 1), (F)
–
7
6
x
2
+
7
13
x
4
–
7
61
x
5
+1x
6
+
7
4
x
7
=
7
325
(строка 2),
7
2
x
2
+ 1x
3
+
7
12
x
4
–
7
3
x
5
+
7
1
x
7
=
7
55
(строка 3),
где x
0
подлежит максимизации.
Мы рекомендуем читателю записать системы уравнений (I) и (F) на
отдельном листе бумаги и иметь их под рукой в процессе чтения следующего
раздела.
4.2. Целевая функция
Прежде всего, попытаемся выяснить, останется ли уже найденный
допустимый оптимальный базис оптимальным, если изменить коэффициенты
в выражении для целевой функции. При изменении этих коэффициентов
полученное решение по-прежнему является допустимым. Следовательно,
предположив, что данное решение можно «подправить», остается лишь
продолжить предписанную симплексным методом вычислительную
процедуру, начиная с заключительной итерации, уже выполненной в разд. 3.2.
Рассмотрим коэффициенты при небазисных переменных x
2
и x
4
в строке 0
системы уравнений (I). Интуиция подсказывает, что если уменьшить их
«удельную прибыльность», рассматриваемый пробный базис останется
оптимальным. Однако, если «прибыльность» x
2
и x
4
получит достаточно
большое положительное приращение, решение можно будет подправить. При
каком значении коэффициента при x
2
рассматриваемое решение становится
неоптимальным?
Предположим, что коэффициент при x
2
получает неотрицательное
приращение δ, т. е. становится равным 5+δ. Тогда строка 0 системы уравнений
(I) принимает следующий вид:
1x
0
–4x
1
– (5+δ)x
2
– 9x
3
– 11x
4
=0. (4.2.1)
73
При выполнении каждой симплекс-итерации мы прибавляли к строке 0
одну из остальных строк, предварительно умножив последнюю на некоторую
константу. Следовательно, на заключительной итерации строка 0 системы
уравнений (F) запишется в виде
1x
0
+(
7
3
– δ)x
2
+
7
11
x
4
+
7
13
x
5
+
7
5
x
7
=
7
695
, (4.2.2)
что нетрудно проверить, вновь проделав все операции, перечисленные в
разд. 3.2. Таким образом, член –δx
2
сохранится в строке 0 на любом этапе
вычислений.
Мы видим, что если δ >
3
/
7
, то коэффициент при x
2
в соотношении (4.2.2)
принимает отрицательное значение. В этом случае, согласно симплекс-
критерию I (максимизация), в очередное базисное решение вошла бы
переменная x
2
. Аналогично если бы коэффициент при x
4
принял значение,
превышающее
7
11
, то пробное базисное решение перестало бы быть
оптимальным.
Итак, коэффициенты при небазисных переменных в строке 0 на этапе
заключительной итерации показывают, в каких пределах соответствующие
коэффициенты в выражении для целевой функции могут принимать
положительные приращения без нарушения оптимальности ранее полученного
базиса.
Предположим, что существенным образом понизилась «прибыльность»
переменной x
1
или переменной x
3
, каждая из которых входит в базис.
Представляется вполне возможным, что найденное базисное решение
окажется при этом неоптимальным. Не является также очевидным, что при
увеличении значений коэффициентов при x
1
и x
3
ранее полученное решение
окажется неоптимальным. В каких пределах может меняться коэффициент при
x
1
без ущерба для оптимальности полученного решения?
Чтобы ответить на этот вопрос, необходимо выполнить операции,
аналогичные только что проделанным. При этом строка 0 системы уравнений
74
(I) примет вид
1x
0
–(4+δ)x
1
– 5x
2
– 9x
3
– 11x
4
=0, (4.2.3)
а строка 0 в (F) запишется соответственно в виде
1x
0
– δx
1
+
7
3
x
2
+
7
11
x
4
+
7
13
x
5
+
7
5
x
7
=
7
695
. (4.2.4)
Чтобы прийти к какому-либо выводу относительно того, в каких пределах
можно варьировать δ, не нарушая оптимальности полученного решения,
необходимо, прежде всего, обратить в нуль коэффициент при x
1
в строке 0.
Это достигается обычным образом. Умножим на δ строку 1 в (F) и прибавим
полученный результат к (4.2.4). В результате будем иметь
1x
0
+(
7
3
+
7
5
δ)x
2
+(
7
11
–
7
5
δ)x
4
+ (
7
13
+
7
10
δ)x
5
+ (
7
5
–
7
1
δ)x
7
=
7
695
+
7
50
δ (строка 0). (4.2.5)
Отсюда следует, что при выполнении условия
5
11
5
3
≤≤−
δ
(4.2.6)
полученное решение остается оптимальным. При δ≤ –
3
/
5
коэффициент при x
2
принимает отрицательное значение. В случае, когда δ≥
11
/
5
, отрицательным
становится коэффициент при x
4
. Следовательно, как только значение δ
выходит за пределы интервала, заданного соотношением (4.2.6), прежний
базис перестает быть оптимальным.
Рассмотрим теперь геометрическую интерпретацию понятия
устойчивости оптимального решения.
В примере (см. рис 2.1.) оптимальное решение находится в точке С,
которая является пересечением двух прямых, заданных уравнениями
2х
1
+ 1х
2
= 12, (I)
2х
1
+ 3х
2
= 18. (II)
Целевая функция F=5х
1
+ 6х
2
(здесь c
1
=5, c
2
=6) максимальное значение
приняла в точке С. После составления плана и его реализации в конкретной
производственной программе c
1
и c
2
(удельная прибыль или затраты) могут
изменяться. Зададимся следующим вопросом: при каком соотношении
75
коэффициентов целевой функции c
1
и c
2
оптимальное решение сохранится
(устоит) в точке С?
Из аналитической геометрии нам известно, что коэффициенты, стоящие
перед переменными х
1
и х
2
в уравнении прямой суть координаты вектора,
перпендикулярного данной прямой (т.н. нормаль). На рис. 2.1 нормаль к
целевой функции обозначена n, нормаль к ограничению (I) n
1
и нормаль к
ограничению (II) n
2
.
Чтобы оптимальное решение сохранялось в точке С при изменяющихся
коэффициентах c
1
и c
2
необходимо, чтобы вектор нормали n лежал между
векторами n
1
и n
2
. Для этого необходимо, чтобы тангенс угла между вектором
n и осью х
1
(обозначим через tg(n, х
1
)) был больше tg(n
1
, х
1
), но меньше tg(n
2
,
х
1
). Таким образом, для обеспечения устойчивости оптимального решения в
точке С необходимо выполнение условия:
tg(n
1
, х
1
) ≤ tg(n, х
1
) ≤ tg(n
2
, х
1
).
Так как tg(n, х
1
) = c
2
/
c
1
,
tg(n
1
, х
1
) = а
12
/а
11
=1/2,
tg(n
2
, х
1
) = а
22
/а
21
=3/2,
окончательно получаем для примера 2.1 соотношение устойчивости
оптимального решения в виде
1/2 ≤ c
2
/c
1
≤ 3/2.
В случае n переменных получаем множество соотношений аналогичного
вида между всеми с
k
и c
j
(k≠j) показывающих, при каких условиях изменение
коэффициентов целевой функции не повлечет изменение оптимального
решения.
Подставляя вместо c
1
и c
2
их значения получим проверочные
соотношения
1/2 ≤ 6 /5 ≤ 3/2.
Для второй задачи (пример 2.2) соотношение устойчивости оптимального
решения будет иметь вид
76
2/10 ≤ c
2
/c
1
≤ 1/0.5,
а проверочное соотношение
2/10 ≤ 2.5 /1.5 ≤ 1/0.5.
Анализ на чувствительность проводился пока путем варьирования
значений коэффициента только при одной переменной (либо базисной, либо
небазисной). Этот же прием анализа пригоден и в случае одновременного
изменения значений коэффициентов при нескольких базисных переменных.
При этом в соотношение, являющееся аналогом уравнения (4.2.5), войдет
несколько переменных
приращений δ
j
, каждое из которых влияет на способ
выбора нового базиса. Чтобы базис остался прежним, δ
j
должны подчиняться
определенным условиям, записанным в виде неравенств, аналогичных (4.2.6).
Другими словами, в этом случае будем иметь вместо одного неравенства
(4.2.6) систему неравенств, каждое из которых получается из условия
неотрицательности коэффициентов при небазисных переменных.
Многие машинные программы, построенные на базе симплексного метода,
автоматически обеспечивают так называемый классификационный анализ
(ранжировку) коэффициентов в
выражении для целевой функции.
Существует также ряд стандартных программ, предусматривающих более
тщательный анализ линейных моделей на чувствительность; при этом
используются специальные вычислительные приемы, такие, как метод
присоединенных целевых функций и параметрическое
программирование.
Метод присоединенных целевых функций позволяет находить решения
для некоторой последовательности линейных моделей, каждая из которых
характеризуется своим собственным
критерием эффективности. При анализе,
выполняемом методом параметрического программирования, в качестве
целевой функции берется выражение
∑
=
∗
+
n
j
jjj
xсc
1
)(
δ
,
где δ – параметр, варьируемый на некотором заданном интервале значений.
77
Метод параметрического программирования позволяет также проверить,
остается ли полученное решение оптимальным при некоторых наперед
заданных вариациях коэффициентов в выражении для целевой функции. При
проведении такого анализа c*
j
рассматривается как приращение с
j
; при этом δ
может принимать некоторую наперед заданную последовательность значений.
После этого легко удается проверить, остается ли полученное базисное
решение оптимальным при δ=1.
4.3. Константы в правых частях ограничений
Попытаемся теперь выяснить, остается ли допустимым полученный
оптимальный базис, если изменить значения констант в правых частях
соотношений, формирующих ту или иную
модель линейного
программирования. Если базис остается допустимым, то новое решение
является оптимальным, так как коэффициенты при неизвестных в строке 0 не
меняются.
Рассмотрим правую часть строки 2 системы уравнений (I). Произведем
замену 120 → 120 + δ. Заметим, что свободная переменная x
6
, фигурирующая
в указанной строке, входит в базис [см. (F)]. Следовательно, x
6
изменится на
величину δ. Таким образом, ранее полученное решение остается допустимым,
если δ≥ –
325
/
7
[см. строку 2 в (F)]. Читателю предлагается самостоятельно
вычислить значение x
6
при δ = –
325
/
7
и дать интерпретацию полученного
результата.
Рассмотрим теперь правую часть уравнения в строке 1 системы уравнений
(I). Произведем замену 15 → 15 + –
325
/
7
. При каких значениях δ полученный
базис остается допустимым?
Ответ на этот вопрос может быть получен, если при выполнении
симплекс-итераций всюду учитывать произведенную замену. Заметим, однако,
что на каждом этапе появление δ в правой части строки 1 сопровождается
78
появлением переменной x
5
в левой части данной строки. Следовательно, на
последней итерации будем иметь
1x
0
+
7
3
x
2
+
7
11
x
4
+
7
13
x
5
+
7
5
x
7
=
7
695
+
7
13
δ (строка 0),
1x
1
+
7
5
x
2
–
7
5
x
4
+
7
10
x
5
–
7
1
x
7
=
7
50
+
7
10
δ (строка 1), (4.3.1)
–
7
6
x
2
+
7
13
x
4
–
7
61
x
5
+1x
6
+
7
4
x
7
=
7
325
–
7
61
δ (строка 2),
7
2
x
2
+ 1x
3
+
7
12
x
4
–
7
3
x
5
+
7
1
x
7
=
7
55
–
7
3
δ (строка 3),
Полагая, как обычно, небазисные переменные x
2
, x
4
, x
5
и x
7
равными нулю,
получим значения базисных переменных, которые определяются теперь через
δ. Чтобы базис продолжал оставаться допустимым, константы в правых
частях уравнений (4.3.1) должны иметь неотрицательные значения. Отсюда
следует, что полученное пробное решение остается допустимым, если
61
325
10
50
≤≤−
δ
(4.3.2)
Действительно, при δ<–
50
/
10
значение базисной переменной x
1
становится
отрицательным; при δ >
325
/
61
отрицательное значение принимает базисная
переменная x
6
.
Положим δ=1, что можно интерпретировать как увеличение «ресурса» в
строке 2 на единицу. С помощью соотношения в строке 0 системы уравнений
(4.3.1) легко показать, что при этом значение целевой функции возрастет на
7
13
, причем значения всех базисных переменных останутся
неотрицательными. Другими словами, при увеличении объема ресурсов на
единицу дополнительная прибыль в оптимальном варианте составляет
7
13
.
Рассмотренный метод анализа можно обобщить на случай варьирования
одновременно нескольких констант в правых частях ограничений, входящих в
состав линейной модели. Произведем одновременно следующие замены:
15 → (15 + δ
1
) в строке 1, 120→ (120 + δ
2
) в строке 2, 100 → (100 + δ
3
) в