Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 181

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Таблица 6.2. До" преобразования

Таблица 6.3- После преобразования

.. а . .

р . .

— xn+ i

У)

 

У ■ .

б . .

 

 

= 'Jj

Таблица 6.4

 

 

1

Х{

 

 

1

аоо

«01

 

 

Уп+i

аю

« и

•

 

Уп+т аш0 а'т1

*

 

 

= Уо

= г/1

 

 

Таблица 6.5

 

 

1 '

Xi

 

х3

 

-2 1 /2

1/2 -3 /2 -3 /2

х0

xn+i

.. а " 1

а - 1 Р

— у а -1

6 — 7 а _1р . .

— Уп+i

хп

а0п = х0

а1п — ~ хп+ 1

атп = — Xп + т

Уп

 

Таблица 6.6

 

 

1

Х1

хк

х3

 

г

2

3

3

х0

- 1 8

- 5 /2

1/2

1/2*

3/2 — хк

- 5

1

2

3

— х2

-1 /2

1/2

- 1 /2

- 1 /2

- 3

1

1

1

—х5

Уо

У\

г/2

Уз

УО

У1

Уь

Уз

112

ГЛ. G. МЕТОД ОДНОВРЕМЕННОГО РЕШ ЕНИЯ

 

 

 

Базисное решение прямо допустимо,

если a'i0 ^

0 (i =

1,

. .

т),

и двойственно допустимо, если

> о (7 =

1, . .

.,

п).

Если

одновременно а\0 ^ 0 (г = 1, . . .,

т) и a'oj ^

0 (/ =

1,

. . ., п),

то получено оптимальное решение обеих задач.

 

 

 

 

Для

примера рассмотрим табл. 6.5. Одна итерация с помечен­

ным звездочкой ведущим элементом приводит к оптимальной

табл. 6.6. Заметим,

что табл. 6.5 прямо допустима, поскольку

a i0 ^ 0 (£ = 1,

2),

но

условие

двойственной допустимости не

выполнено, так

как

a0j

< 0 для

некоторых j.

Симплекс-метод,

используемый для решения прямой и двой­

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

Пусть 0 и 0 обозначают соответственно неотрицательные и неположительные элементы. Тогда последняя в последователь­ ности таблиц может быть лишь одной из следующих: 6.7, 6.8, 6.9.

Таблица 6.7.

 

Таблица 6.8.

Таблица 6.9.

Оптимальная

Ограничения прямой

Ограничения

таблица

 

задачи

несовместны

двойственной

 

 

 

 

 

задачи несовместны

 

 

 

 

 

 

 

—

0

 

 

 

 

 

 

0

 

 

 

+

е е

••• е

 

 

0

 

 

 

 

 

 

0

Начальная таблица прямого симплекс-метода прямо допустима,

т. е. ai0 ^ 0

(i ^

1). В нулевой строке выбирается а0} <

0. (Если

а0j ^ 0 для

всех

/ ^

1, то таблица оптимальна.)

Если

ai} ^ 0

для всех i,

то система

ограничений

двойственной

задачи несов­

местна, а целевая функция прямой задачи на множестве решений

не ограничена. Если ai} >

0 для некоторого i, то в качестве веду­

щего выбирается элемент arj по правилу

 

•J2- =

max ^

{аи > 0).

(5)

a rj

х a lJ

 

 

Указанное правило выбора ведущего элемента сохраняет прямую допустимость каждой таблицы из последовательности таблиц и обычно уменьшает значение а0о- В вырожденном случае аг0 = 0, т. е. после итерации значение а0о не изменяется.

6.1.

ВЗАИМНЫЙ МЕТОД РЕШЕНИЯ

113

Доказательство конечности симплекс-метода основывается на

том, что существует

не более

различных

возможных

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

Начальная таблица двойственного симплекс-метода двойствен­ но допустима, т. е. a0j ^ 0 (у ^ 1). В нулевом столбце выбирается a io > 0. Если а,ц ^ 0 для всех у, то система ограничений прямой задачи несовместна, а целевая функция двойственной задачи на

множестве допустимых решений не ограничена.

Если atj < 0

для некоторого у, то ведущий элемент ais

выбирается по правилу

= min

(ац<.

0).

(6)

з

аИ

 

 

Правило проверки отношения сохраняет двойственную допусти­ мость последовательности таблиц и обычно увеличивает значе­ ние а00.

Используя в качестве начальной любую таблицу, можно с помощью метода одновременного решения прямой и двойственной задач указать последовательность итераций, которая приводит к одному из трех видов симплексной таблицы, представленных табл. 6.7, 6.8 или 6.9. Для обоснования этого факта необходимо ввести следующие определения и обозначения.

Верхнюю строку таблицы Т обозначим через R (Т) и будем называть характеристической строкой, а левый столбец обозначим через С (Т) и назовем характеристическим столбцом. Левый верхний элемент таблицы Т назовем характеристическим и обозна­ чим через d, (Т). Характеристическая строка R (Т) без d (Т) обозна­

чается через

R'

(Т), а характеристический

столбец С (Т) без

d (Т) — через С

(Т). Таким образом, таблица

Т является прямо

допустимой,

если С (Т) ^ 0, и двойственно допустимой, если

R ’ (Т) ^ 0.

Если начальная таблица прямо или двойственно

допустима, то использование соответственно прямого или двой­ ственного симплекс-метода приведет к заключительной таблице одного из трех видов: табл. 6.7, 6.8 или 6.9.

Если начальная таблица Т0не является прямо или двойственно допустимой, то выделим такую последовательность таблиц Ту, . . .

. .

., Тп, что 1) каждая таблица Th является подтаблицей в

2)

все Т i (i нечетно)

прямо допустимы и 3) все

Т} (у

четно) двой­

ственно допустимы.

Например, если Т0 не является прямо допу­

стимой, то выделим такие строки в Т0, что ai0 ^ 0 ,

а в качестве

характеристической

строки возьмем строку

с alQ>

0. Получен­

ная таким образом подтаблица Ту таблицы Т0 будет прямо допусти­ мой. Если Ту содержит С (Ту) < 0 или принадлежит одному из типов, указанных в табл. 6.7, 6.8 или 6.9, то последовательность

8 т. Ху

114

 

 

ГЛ. 6. МЕТОД ОДНОВРЕМЕННОГО РЕШЕНИЯ

 

подтаблиц обрывается на Тj. Если С

(Ti) ^

0,

то составим табли­

цу Тг из

строк,

для

которых

ai0 =

0.

Столбцами

Г2

станут те

столбцы

 

Ти для

которых

 

 

 

 

 

 

 

 

 

а0] ^ 0.

В качестве харак­

 

 

 

 

 

 

 

 

 

теристического

столбца

+

 

-

©

 

©

©

©

таблицы Т2 возьмем любой

 

0

 

 

 

 

 

 

 

столбец

 

Т\,

у

которого

 

0

 

 

 

 

h

 

 

a-оj <L 0.

 

Описанная

про­

 

0

 

 

 

 

 

 

 

цедура

схематически

изо­

-

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

бражена

 

на рис.

6.1.

-

 

 

 

 

 

 

 

 

+

 

 

 

 

 

 

 

Столбцы

 

и

строки

пере­

 

 

 

 

 

 

 

 

+

 

 

 

 

 

 

 

ставлены, чтобы яснее по­

 

 

 

 

 

 

 

 

 

казать структуру таблиц.

 

 

 

 

 

 

 

 

 

Если

 

двойственно

до­

 

 

 

 

 

 

 

 

 

пустимая

подтаблица

Т 2

 

 

 

строке,

то

рассмотрим

содержит

нули

в

характеристической

характеристический

столбец

и

те столбцы Т 2,

верхние элементы

которых равны нулю.

Из этих столбцов

выберем элементы, стоя­

щие в строках с неположительными левыми членами.

Эти элементы

вместе с

характеристической

строкой,

выбранной из строк Т2

с положительными

левыми

членами,

образуют

подтаблицу Т 3.

 

 

 

 

 

 

Таблица 6.10

 

 

 

 

 

 

 

 

 

 

 

 

 

-

0 0

D

! +

+

+

 

 

 

 

 

 

0

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

h

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

г,

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

 

 

+

 

 

 

 

 

 

 

 

 

 

 

 

 

 

©

h

 

 

 

 

 

 

 

 

 

 

 

 

 

©

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Результат описанного процесса показан в табл. 6.10. Последо­

вательность таблиц

обрывается на Г2, если Т3 имеет вид 6.7

или 6.8, или R' (Т)

> 0.

Необходимо сделать ряд замечаний.

1. Если рассматривать каждую из подтаблиц как прямо или двойственно допустимую симплексную таблицу, то, согласно пред­ писаниям прямого или двойственного симплекс-метода, в каждой из них можно указать единственный ведущий элемент. Отсюда следует, что для любой последовательности таблиц существует последовательность ведущих элементов.

6.1. ВЗАИМНЫЙ МЕТОД РЕШЕНИЯ

115

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

3.Так как каждая Тк содержит либо меньше столбцов, либо меньше строк, чем Тк.\, то последовательность подтаблиц всегда

конечна.

4. На рис. 6.1 и в табл. 6.10 строка и столбцы были переставле­ ны только для наглядности. Для того чтобы последовательность таблиц определилась однозначно, необходимо лишь указать характеристический элемент каждой из таблиц.

5. Для каждой прямо допустимой таблицы Тк с положитель­ ным характеристическим элементом используется прямой симп­ лекс-метод. Правило выбора ведущего элемента сохранит С (Тк)

неположительным. (Здесь знак

* используется

для обозначения

таблицы

после

итерации.)

С

другой

стороны,

d ( T h) ' ^ d ( T |).

(Если С

(Тк)

не содержит

нулей,

то d (Тh) > d (Тк).) Если

d (Тк) ^ 0, то характеристический столбец таблицы T%-i содер­ жит на один неположительный элемент больше, чем характеристи­

ческий столбец ГА_1 . В результате итерации таблица

i «при­

ближается» к виду прямо допустимой таблицы.

 

6. Подобным же образом для двойственно допустимой табли­ цы Tk с отрицательным характеристическим элементом мы исполь­ зуем двойственный симплекс-метод. Правило выбора ведущего

элемента сохранит R' (Т*)

неотрицательной. С другой стороны,

d (Тк) ^ d (Г*). (Если R'

(Tk) ^ 0 не содержит нулей, то d (Тк) <

< i d (Тк)-) Если d (Тк) ^

0,

то характеристическая строка табли­

цы Th-i содержит на один неотрицательный элемент больше, чем характеристическая строка таблицы 7Vi- В результате итерации таблица Тk-i «приближается» к виду двойственно допустимой таблицы.

Таким образом, вместе с любой таблицей и последовательностью ее подтаблиц возникает как бы иерархия «задач», где к-я «задача» служит для «улучшения» к-й подтаблицы. «Улучшение» подтабли­ цы Th не изменит «задач», связанных с предыдущими подтаблица­ ми ввиду предложенного способа построения последовательности

Ti, Т 2, ■• ■,

Тк, ■•

Тп х). Далее через а (Тк) будем обозначать

число

строк

в таблице Тк,

если к нечетно, и число столбцов

в Тк,

если к

четно.

 

 

х)

Преобразование

подтаблиц

(рассмотрение соответствующих задач

иерархии) совершается не автономно, а одновременно. Процесс решения

задачи таков: а) по исходной таблице Т 0 строится (как указано

в тексте)

конечная цепочка прямо

(двойственно) допустимых подтаблиц Т , ,

.

. ., Т п

и их ведущих элементов

а ; ; б) вся таблица Т0 подвергается симплексному

преобразованию с ведущим элементом а „ (из последней подтаблицы);

в) если

полученная после преобразования таблица Т% не оптимальна, то,

 

беря ее

за исходную, повторяем

процесс с п. а )).— Прим. ред.

 

 

8*

Смотрите также файлы