Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 161
Скачиваний: 0
60 |
ГЛ. 2. СИМПЛЕКС-МЕТОД |
метод представляет собой конечный алгоритм, поскольку суще
ствует конечное число базисов, не превышающее |
. Таким |
образом, значения (—z), соответствующие базисам, задают линей ный порядок на множестве базисов.
Пусть z и г' — значения функции цели в двух следующих друг за другом таблицах. Значение (—z) может не измениться при переходе от одной таблицы к другой, если базисное решение
вырождено, поскольку проверка |
отношения дает min |
= О |
и (—z') = (—z) — 0• Uqs = (—z). |
Когда это происходит, |
a i s |
необхо |
димо принять меры предосторожности для того, чтобы один и тот же базис не повторился и тем самым была бы гарантирована конеч ность.
Пусть в начальной таблице все строки, кроме, быть может, нулевой, лексикографически положительные. (Если нет, то можно добавить искусственные переменные или переставить местами столбцы и переобозначить переменные.) Тогда конечность будет обеспечена, если принять следующее, немного более сложное пра вило выбора ведущего элемента. При выборе ведущего столбца
выбирается любое Cj < |
0, в то время как в обычном симплекс-мето |
||||
де использовалось cs, |
такое, что min с] = |
cs < 0. Допустим, что |
|||
в качестве |
ведущего |
выбран s-й столбец. Тогда |
среди |
строк |
|
с ais > 0 (г = |
1, . . ., |
т), поделенных на ais, выбирается лексико |
|||
графически минимальная. Строка становится ведущей, |
т. е. лекси |
||||
кографически минимальный вектор — , |
— , . . . |
, ^ |
опре- |
||
|
|
L#is |
a i s |
a i s J |
|
деляет ведующую строку. Заметим, что первая компонента этого вектора получается из обычной проверки отношений. Другими словами, если проверка отношений приводит к нулевому резуль тату, то проверяются отношения с числителем, взятым из следую щего столбца, и так до тех пор, пока не будет получен ненулевой результат. Если принять это усложненное правило выбора веду щего элемента, то необходимо доказать два свойства: 1) в каждой таблице все строки, кроме, быть может, нулевой, лексикографи чески положительны; 2) нулевая строка лексикографически возра стает после каждой итерации.
Для |
того |
чтобы |
доказать |
свойство |
1, |
вычтем |
|
Г |
|||
|
|
|
|
|
|
|
|
|
|
|
L«rs ’ |
— |
a r s J |
из |
каждой строки |
i с |
aiS> 0 . |
Поскольку |
Г |
||||
a r s |
|
|
|
|
|
|
|
|
|
L <Hs’ |
|
^ , . . . , |
^ 1 |
лексикографически больше, |
чем Г— |
, |
|
a r n 1 |
|||||
а 13 |
^13 Л |
|
|
|
|
|
^ ^Гз |
^Г8 |
|
ers J» |
|
эта разность, |
являющаяся г-й строкой в следующей |
таблице, |
|||||||||
лексикографически |
положительна. |
Для |
строк |
с |
aiS < 0 |
эта раз |
|||||
ность есть фактически |
сумма двух лексикографически |
положи- |
|||||||||
2.4. СИМПЛЕКС-МЕТОД В МАТРИЧНОЙ ФОРМЕ ЗАПИСИ |
61 |
тельных строк и дает лексикографически положительную строку. Для доказательства свойства 2 заметим, что к нулевой строке
прибавляется r-я строка, умноженная на flQs Поскольку г-я
ars
строка лексикографически положительна, нулевая строка лексико графически возрастает после каждой итерации. Нулевая строка в последовательности симплексных таблиц служит для установле ния линейного порядка на множестве всех базисов. В случае вырожденности, несмотря на то, что значение ( —z) остается постоянным, все базисы, соответствующие этому значению ( — z), упорядочены.
Таким образом, ни один базис не может повториться, а значит, симплекс-метод конечен. 'Рассмотрим для примера следующую таблицу:
Нулевой столбец
I
0 |
0 |
0 |
0 |
—3 |
—3 |
Нулевая строка |
0 |
1 |
0 |
0 |
3* |
3 |
|
0 |
0 |
1 |
0 - |
1 |
2* |
|
со
0 |
0 |
1 |
2 |
1 |
В качестве ведущего столбца можно выбрать четвертый или пятый столбец, поскольку оба они имеют одинаковые отрицательные относительные оценки (—3).
Если выбирается четвертый столбец, то ведущей строкой ста новится первая. Если выбирается пятый столбец, то ведущей строкой преобразования выбирается вторая строка.
Существуют примеры, построенные таким образом, что если при нулевом результате в проверке отношения всегда выбирать в качестве ведущей строки первую из строк-кандидатов, то обыч
ный процесс может быть бесконечным. |
|
|
2.4. Симплекс-метод в матричной форме записи |
|
|
Рассмотрим задачу линейного программирования: |
|
|
минимизировать |
|
|
z = |
сх — а0о |
(1) |
при условиях |
Ь, х ^ 0. |
|
Ах = |
|
|
62 |
ГЛ. 2. СИМПЛЕКС-МЕТОД |
Эту задачу можно представить в следующем виде:
«00 |
с |
' — 1 ' |
|
Z |
(2) |
|
_b |
А |
X |
|
0_ |
||
|
|
|||||
Пусть |
|
|
|
|
|
|
А* = |
«00 |
С |
^00 |
«07 |
(3) |
|
Ь |
А |
_&i0 |
« й '_ |
|||
|
|
Матрица А* состоит из т + 1 строк и п + 1 столбцов. Итерация симплекс-метода, рассмотренная в этой главе, эквивалентна умно
жению уравнения (2) слева на следующую квадратную матрицу: i г ... г. ... «**1
где г ф 0 и s ф 0.
Если все столбцы матрицы А разделить на базисные В и неба зисные N, то соотношение (2) можно записать как
- — 1-|
«00 |
св |
" z |
Ь |
Хд |
(4) |
В |
0 |
Xjv .
где св и c N — соответствующие компоненты вектора с;х г и х „ — базисные и небазисные переменные. Выбор хв в качестве началь ных базисных переменных эквивалентен умножению системы (4) слева на матрицу
“1 - C BB-!-
0 |
B 1 |
”kl |
— я “ |
|
I0 |
1 _ |
|
1сом |
(5>
где свВ 1 обозначено через я.
Результатом умножения (4) на (5) слева является уравнение
а0о свВ !Ь |
0 |
Cjy — свВ JN |
z |
В-!Ь |
I |
B_1N |
L.0 J ) |
где относительные оценки Cj задаются посредством
Cj = Cj — яаj = с■j —Zj, где Zj = naj,
2.5. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ |
63 |
a Cj появляются в нулевой строке текущей таблицы. Базис являет
ся допустимым, если В -1Ь ^ 0, |
и оптимальным, еслис;- ^ 0 |
для |
|
всех /. |
|
|
|
Каждая |
строка умножается |
на вектор текущих цен |
я = |
= (iti, . . ., |
ят ) и вычитается из строки коэффициентов стоимости |
||
для того, чтобы исключить коэффициенты стоимости при базисных переменных.
Пусть имеется следующая задача: минимизировать
Z |
= |
сх |
при условиях |
|
|
Ах ^ |
Ь, |
х 0. |
Вводя слабые переменные, ее можно записать в виде
s
[I, А] х = Ь.
Метод исключения по строкам для матрицы А* — [I, А] эквивалентен умножению А* слева на В -1, где В — базис ( В - подматрица А):
В ХА* = [ В 1, В -1А].
Таким образом, матрица, полученная на месте единичной, являет ся обратной для текущего базиса.
Более того, относительные оценки, расположенные над единич
ной матрицей I, равны [—свВ -1] или (—я), |
так как cj = cj — |
— свВ_1а^, и коэффициенты стоимости при |
слабых переменных |
равны нулю, т. е. с) = 0, а столбцы матрицы I есть единичные |
|
векторы ег. Заметим, что z = свхв = свВ _1Ь = яЬ, т. е. на каж |
|
дом шаге вычислений значение целевой функции равно произведе нию вектора текущих цен матрицы I на исходный вектор Ь. Напри
мер, в табл. |
2.2 значение целевой функции равно |
21/2 |
= |
11 + |
||||
+ |
(—0) 2 + |
(—1/2) • 1; в табл. |
2.3 |
оно равно 3 ,= 11 |
+ (—3) 2 -j- |
|||
+ |
(—2)1; в табл. 2.6 равно 9 = |
37 + (—8) у + ( - 0 ) - ^ - ; |
в |
табл. |
||||
2.7 |
равно 3 = 37 + ( - 2 ) 1 + |
( - |
** . |
|
|
|
||
2.5. |
Геометрическая интерпретация симплекс-метода |
|
|
|
||||
|
|
Рассмотрим неравенство Х\ |
+ |
х2 ^ Ъ\ при условиях |
xt ^ 0, |
|||
х 2 ^ 0. Область решений этого неравенства показана на рис. 2.1. Это неравенство можно преобразовать в уравнение введением слабой переменной sj. Тогда получим следующую систему: xi + + х г + sj = bi, Xi ^ 0, х2 > 0, Si ^ 0. Областью решений этой системы является треугольник, показанный на рис. 2.2.