Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 176
Скачиваний: 0
5.1. ВВЕДЕНИЕ |
101 |
дующей таблицы. Приведенные рассуждения лежат в основе
модифицированного симплекс-метода. Модифицированный сим плекс-метод сохраняет исходную таблицу, а на каждой итерации
определяются: строка относительных оценок с, вводимый в базис
вектор и текущее значение Ь. Эта информация вместе с обращени ем текущего базиса определяет В -1 для следующей таблицы. Если
имеются |
В -1, aj и Ь (сведенные в таблицу размера (т 1) X |
X (т + |
2)), то с помощью проверки отношения можно определить |
ведущий элемент и произвести преобразование таблицы, чтобы получить В -1 для следующей таблицы. Таким образом, на каждой итерации вычисляется не более чем п — т относительных оце
нок Cj, столбец b и вектор as. Поскольку исходная таблица содер жит единичную матрицу размера т X т, а все относительные оценки, соответствующие столбцам этой матрицы, равны нулю, то в дальнейших вычислениях на месте единичной матрицы будут появляться элементы матрицы В -1, а на месте относительных оценок — элементы вектора (—л) для текущей таблицы (см. § 2.4). Зная л и В -1 данной таблицы, можно найти с; по формуле Cj — ~ Cj — я&]. Если Cj неотрицательно, то aj вычислять не следует. Найдя Cj < 0, вычислим соответствующий ему вектор aj для вве дения в базис. Заметим, что
|
л |
Ч ‘ |
Cj — Я'А] |
|
и |
В 1 |
_а./_ |
. в ч |
. |
|
|
|
|
|
1 |
— л |
"0" |
' — лЬ~ |
—Z |
о |
в -1 |
ь |
В П) ^ |
. Б_ |
В исходной таблице обращением единичной матрицы является сама матрица, а л = 0, поскольку л = свВ -1 и св = 0. Поэтому к единичной матрице в исходной таблице можно добавить стол бец [1, 0, . . ., 0]:
_1 |
0 |
1 |
— Jt |
0 |
I |
0 |
В"1 |
Это делается для того, чтобы исходная таблица использовалась так же, как и все другие. Решим сначала следующий числовой пример, используя обычный симплекс-метод, а затем тот же самый пример решим при помощи модифицированного симплексметода:
максимизировать х0
102 ГЛ. 5. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД
при условиях
х 0 |
+ 2 х 3 — 2х4— х5 = 0, |
|
X i |
|
— 2я3- г ж4+ х $ = 4, |
|
^г-гЗ^з— ;г4 - (- 2.г'5 = 2, |
|
ж / > 0 |
(/ = 1, • • 5 ) . |
|
Таблица 5.1 х) является исходной. Заметим, что рассматриваемая матрица В* — единичная, следовательно, ее обращением будет тоже единичная матрица. Приведенный числовой пример решается обычным симплекс-методом, как показано в табл. 5.2, 5.3, 5.4 (обратите внимание на небольшое видоизменение формы таблиц). Для проверки убедимся, что для базиса В* последней таблицы и его обращения В *-1 выполняется условие В *-В *-1 = I 2):
-1 |
- 2 |
2' |
1 |
4 |
2" |
0 |
1 - 2 |
. |
0 |
3 |
2 |
. 0 |
— 1 |
з. |
О |
|
н-т |
•«гн 0
.0
|
о |
о |
1 0
0 1.
Для того чтобы выявить основную структуру модифицированного симплекс-алгоритма, достаточно переписать только часть исход ной таблицы так, как если бы это была к-я итерация, и показать, что остальная часть может быть получена из имеющейся информа ции (табл. 5.5) и исходной таблицы (исходная табл. 5.1 должна храниться все время).
Имеем
|
|
|
1 0 |
0- |
|
|
|
|
|
В* |
0 |
1 |
0 , |
|
|
|
|
|
.0 |
0 |
1J |
|
|
с3 = |
с з - я а 3 = |
[1, |
0, |
0] [2, - 2 , |
3] = 2, |
||
с4 = |
с4- я а 4 = |
[1, |
0, |
0] [ - 2 , |
1, |
— 1 ] = - 2 , |
|
~сь — съ—яа5 = |
[1, |
0, |
0] [ - 1 , |
1, 2] = — 1 3). |
|||
!) Вместо (—хп) стоит х0, т. |
к. |
исходная задача максимизации х0 экви |
|||||
валентна задаче минимизации |
(—х0).— Прим. |
ред. |
|
||||
2) В каждой таблице на месте, где в исходной таблице был начальный |
|||||||
базис (в столбцах под х0, |
xt , . . |
.), формируется обратная матрица текущего |
|||||
базиса.— Прим. ред. |
|
|
|
__ |
|
|
|
3) В данном примере при |
вычислении cj используется тот факт, что |
||||||
cj = 0 для всех j Ф |
0 .В |
силу этого cj — с вВ -1а7- = |
р,а,-, когда ха — базис |
||||
ная переменная и j |
Ф 0; |
р, — первая строка матрицы В -1.— Прим. ред. |
|||||
Строка оценок ко
Базисные XI
переменные |
х 2 |
Строка оценок |
х 0 |
х1
х2
Строка оценок х 0
*4
Т а б л и ц а 5 . 1 |
|
|
||
х0 #1 *2 |
*3 |
Xft |
*5 |
константы |
1 |
2 |
— 2 |
— 1 |
0 |
1 |
— 2 |
1 |
1 |
4 |
1 |
3 |
— 1 |
2 |
2 |
Таблица 5.2
х 0 x l х 2 |
х 3 |
x i |
|
х 5 |
константы |
1 |
2 |
— 2 |
|
— 1 |
0 |
1 |
— 2 |
1 |
* |
1 |
4 |
1 |
3 |
— 1 |
|
2 |
2 |
Таблица 5.3
Хд |
X l |
Х 2 |
Х3 |
х ^ |
х § |
константы |
1 |
to |
0 |
— 2 |
0 |
1 |
00 |
|
1 |
|
|
|
|
|
0 |
1 |
0 |
to |
1 |
1 |
4 |
|
|
|
1 |
|
|
|
Х 2 |
0 |
1 |
1 |
|
1 * |
0 |
3 |
6 |
|
|
|
|
Таблица |
5.4 |
|
|
|
|
|
|
х 0 |
x i |
х 2 |
х 3 |
x i |
х 5 |
константы |
|
|
Строка оценок |
1 |
|
4 |
2 |
0 |
0 |
7 |
20 |
j' Хд = 20 |
|
0 |
|
3 |
2 |
|
|
7 |
16 |
I |
|
|
0 |
1 |
{Iж4 = 16 |
|||||
|
0 |
' 1 |
1 |
1 |
0 |
3 |
6 |
I х 3 = 6 |
|
104 |
ГЛ. 5. |
МОДИФИЦИРОВАННЫЙ |
СИМПЛЕКС-МЕТОД |
|||||
|
|
|
|
Таблица 5.5 |
|
|
||
|
|
х0 |
х1 |
х 2 |
х 3 |
Xi, |
x s Константы |
|
Строка оце-х |
1 |
|
|
|
|
|
< |
|
нок |
0 |
|
1 |
|
|
|
|
|
|
х 1 |
|
|
1 |
|
|
\ |
|
|
Хг |
|
|
|
|
|
||
|
|
|
|
|
|
|
||
Таким образом, в базис должен |
быть введен вектор |
|||||||
|
|
|
|
■1 0 0- ■_1to |
’ — 2' |
|||
|
а* = В*-1а4 = |
0 1 0 |
1 _ _ |
1 |
||||
|
|
|
|
О |
О |
1. |
- 1 . |
1. |
|
|
|
|
■1 |
|
0 0 - |
-0- |
О |
|
ь* = В* хь* = 0 1 0 |
4 — |
4 |
|||||
|
|
|
|
_0 |
|
0 1 |
. 2 . |
2 |
Поскольку |
а14 = |
1 — единственная |
положительная компонента |
|||||
вектора а*, то вектор ai выводится из базиса. Исключение по
строкам с ведущим элементом а14 |
= 1 |
эквивалентно |
умножению |
|||||
слева на матрицу |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
2 |
О' |
|
|
|
|
|
|
|
|||
О |
|
|
|
|
0 |
1 |
0 , |
|
О |
|
|
|
|
0 |
1 1 , |
|
|
|
|
|
|
|
|
|
|
|
1 2 0- - 1 0 0 0- |
|
1 2 0 8" |
|
|||||
0 1 0 0 1 0 |
4 = 0 1 0 4 |
|
||||||
_0 1 1. .0 0 1 2. |
|
.0 1 1 6_ |
|
|||||
Таким образом, получаем следующую |
таблицу (табл. |
5.6). Обра |
||||||
щением нового базиса является матрица |
|
|
|
|||||
|
|
"1 |
2 |
0" |
|
|
|
|
|
|
0 |
1 |
0 , |
|
|
|
|
|
|
_0 |
1 |
1J |
|
|
|
|
ci = |
(l, |
2, 0) |
[0, 1, |
0] = 2, |
|
|||
с.= |
(1, 2, 0) [2, - 2 , 3 ] = |
-2, |
|
|||||
с5 = (1, 2, 0) [ - 1 , 1, 2] = 1.
5.1. ВВЕДЕНИЕ |
405 |
Для контроля вычислим с2 и с4:
с2 = (1, 2, 0) [0, 0, 1] = 0,
с4=(1, 2, 0) [- 2 , 1, - 1 ] = 0.
Таблица 5.6
Строка |
Хо |
Х\ |
Xi |
х3 |
Х4 |
х5 Константы |
1 |
г |
о |
|
|
8 |
|
оценок |
|
|
||||
Ч |
0 |
1 |
0 |
|
|
4 |
*г |
0 |
1 |
1 |
|
|
6 |
В базис следует ввести |
|
|
1 |
2 |
0- |
0 |
1 |
0 |
|
о |
Н-Ь. |
|
|
1 |
см |
|
to |
|
__ |
1 |
|
со |
|
|
1 |
|
■— 2'
---О
=L*
1
Поскольку а2з = 1 — единственная положительная компонента вектора а3, то из базиса выводится а 2. Исключение по строкам
с ведущим элементом а 23 эквивалентно умножепию слева матрицы
условий на матрицу
|
|
1 0 - ( V 1M/ l |
|
1 0 |
|
2' |
|
|
||||||
|
|
0 |
1 |
|
V |
1 |
/ |
|
0 |
1 |
|
2 |
ч |
|
|
|
0 |
0 |
|
|
/ \ |
\ |
|
_0 |
0 |
|
1 |
|
|
|
|
|
|
-- |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
\ 1 / |
|
|
|
|
|
|
|
|
-1 |
0 |
2" |
"1 |
2 |
0 |
8~ |
|
■1 |
4 |
2 |
20 |
- |
||
0 1 2 |
|
0 1 0 4 = 0 3 2 |
16 |
|
||||||||||
_0 0 1 . -0 1 1 6_ |
|
_0 1 1 |
6 _ |
|||||||||||
|
|
|
с, = |
(1, |
4, |
2) |
[ |
0, |
1 , 0 ] |
= |
4, |
|
|
|
|
|
|
с2 = (1, |
4, |
2) [ |
0, |
0 , 1 ] |
= |
2, |
|
|
|||
|
|
|
с5 = |
( 1, |
4, |
2) |
[ - 1 , |
1, |
2] = |
7. |
|
|
||
Для контроля вычислим с3, с4:
с3 = |
(1 ,4 , |
2)[ 2 , - 2 , |
3] = |
0, |
|
с4 = |
(1, 4, |
2) [ —2, |
1, |
— 1] = |
0. |