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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

17.2. ПРИМЕР

359

Введя слабые переменные х±, х5, х$ и х7 и L -строку, получим

табл. 17.6. Константа 10 в L -строке определена грубой оценкой

задачи. В табл.

17.6 гЖ1 -< rx.Q = 2, 3), поэтому ведущим столб­

цом становится столбец под xt. Проверка отношения

для Xj дает

V 2. Строка х7

является единственной, для которой

^ тщ

откуда

V (Xi) =

{строка х7} и выбор производящей строки одно­

значен.

Теперь,

разделив строку х7 на ав$ = 2 и выписав целые

части полученных коэффициентов, получим отсечение (ведущую строку). Новая базисная переменная в строке отсечения является слабой переменной, соответствующей этому отсечению. После преобразования получим табл. 17.7. Задача решается за 7 циклов, которые приведены в табл. 17.8— 17.13, справа от которых выписа­ ны множества V (s). Заметим, что в табл. 17.11 использование

строки xk приводит к оптимальной таблице. М ы выбираем другую строку, чтобы лучше показать действие правила выбора произво­ дящей строки.

В табл. 17.12 строка х4 должна быть выбрана в качестве произ­ водящей, потому что она входила в V (s3)для предыдущей таблицы,

а

строка хе нет.

 

 

 

 

 

 

 

 

 

 

Таблица 17.12

 

Таблица 17.13

 

1

—s6 —s4 —*5

 

 

1

--S6 —si —*5

X0

5

1 —1

1

F(s4) = {строка я4, строка xe}

х0

5

0

1

0

 

6

—8

17

—2

Производящая строка

*4

&

9

--17

15

 

1

—2

1

0

 

Хъ

1

—1

—1

1

хе

1

—1

3

—2

 

Хе

1

2

- 3

1

х7 5

+ 2 - 1

0

 

х7

5

1

1 -1

XI

3

—1 3

0

 

x i

3

2

- 3

3

х2 2

0 1 0

 

х2 2

1 —1 1

Х 3 0 + 2 —5 1

 

х3

0

—3

5 - 4

XL

5

—1

1 —1

 

XL

5

0

—1

0

Sl

0

—1

1 —1

Отсечение и ведущая строка

 

 

 

 

 

 

Таблица

17.13

является оптимальной. Чтобы

показать,

как

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

по правилу выбора производящей строки требуется,-

чтобы

строка xk была выбрана вновь.

 

Оптимальное решение: х4 = 3 , хг = 2, х3 = 0, х0 =

5.

360

ГЛ. 17. ПРЯМОЙ АЛГОРИТМ

17.3.

Доказательство конечности

Доказательство конечности прямого алгоритма состоит из двух частей, связанных необходимым порядком следования. Сначала используя правило выбора ведущего столбца, докажем, что rs лексикографически возрастает от таблицы к таблице. Затем при помощи этого результата и свойств, которыми обладают допусти­ мые правила выбора производящей строки, покажем, что условие rs >- 0 (условие оптимальности) должно иметь место после конеч­

ного числа преобразований.

При доказательстве будет удобно пользоваться следующими определениями.

Пусть

 

 

Ix + A x n = а 0, или,

иначе, lx + ^ a i x j = ао

(16)х)

 

j£J

 

описывает текущую таблицу; и пусть

 

lx +

Axn = а0

(17)

описывает таблицу, которая получается в результате одного преобразования, примененного к (16). Все элементы из (17) обозна­ чаются черточкой наверху, например, а^ — ведущий столбец из (17), тогда как а- — столбец из (16), соответствующий перемен­

ной s, которая выбирается для введения в базис в таблице (17). Пусть J обозначает "множество индексов строк в (16) и (17); J содержит всего п + 2 индексов. Время от времени в контексте, где не может возникнуть недоразумение, будем употреблять А

для краткого обозначения табл.

табл. (17).

Определим 2)

Pi

a is

<*-Ls ’

Тогда

(16) и А — для обозначения

(18)

Po

pi

rs=

(19)

Pn

______________

_ p b _

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

2) Смысл параметров р, и Дj разъясняется и обсуждается в § 17.4.

17.3. ДОКАЗАТЕЛЬСТВО КОНЕЧНОСТИ

361

Далее, определим

 

 

6„ —Рia L j + a i j ,

i € J ,

(20)

и

 

 

6o j

 

 

Aj = •

 

-(21)

S n j

 

 

Эти определения вместе с формулами

преобразования

таблиц

в прямом алгоритме дают следующие соотношения для всех j £ J:

 

 

&Lj^&— '--A/l

 

(2 2 )

 

 

aLjTa=

&j-

 

 

(23)

 

 

 

Ts —rs -1

1

A

(24)

 

 

 

 

 

 

Ls

 

 

A

 

A

“W A

 

 

(25)

 

— A j

_

A

)

 

 

 

 

 

aLs-

 

 

 

 

 

A j =

a L j (щ —r-)

при

aLj ф 0 .

(26)

Вывод формул (22),

(23),

(24),

(25)

и

(26) приводится в §

17.4.

На основании этих соотношений формулируются следующие три теоремы.

Т е о р е м а

17.2.

Если rs -< 0

и Aj >- 0 для всех /

(^=s)£ J и А —

неоптимальная

таблица, то

существует

такой

индекс

jdiJ,

что aLj > 0

и Гт < 0 .

 

 

 

 

 

Т е о р е м а

17.3.

Если rs «•' 0

и Aj >- 0 для

всех

 

j {=^s)^J

и А

неоптимальна, то Aj >- 0 для всех j {Ф s) £ J.

Т е о р е м а 17.4. Если rs 0 и Aj >- 0 для всех j (^/=s) £ J и А неоптималъна, то г- >■ rs.

Основной результат содержится в заключении теоремы 17.4. Чтобы доказать факт, формулируемый как условие этой теоремы,

мы рассуждаем по индукции.

Покажем, что в первой таблице

rs «< 0 и Aj >- 0 для всех j (фв)

6 J • Тогда условие теоремы 17.4

всегда верно для последующих таблиц на основании теорем 17.2

и 17.3.

362

 

 

 

ГЛ. 17. ПРЯМОЙ АЛГОРИТМ

 

 

 

 

В

первой таблице

a L} =

1 для всех

/ £ / .

Поэтому

г7 =

а7

для

всех

/ 6 /

и

а7

= г; >-

rs =

as..

Подставляя в (22)

соответ­

ствующие

величины,

получим А}

=

а7 — а„ >

0.

Заметим,

что

rs =

as

Sj =

Г;

для

всех

/ (=й=«) € /■

Поэтому

если

rs >- 0,

то а7

>- 0

для

всех j

£

/ , что является

условием

оптимальности

исходной таблицы. Следовательно, если исходная таблица неопти­

мальна, то г., -< 0

и Aj >

0 для всех / {¥=s) £ J.

Д о к а з а т е л ь с т в о

т е о р е м ы

17.2. Справедливость теоремы 17.2

следует из (23). Предположим, что теорема неверна из-за того, что aLj<Z.0 для всех y(^ = s)£J (очевидно, что aLs< 0 ) . Тогда левая часть в (23) лексикографически неотрицательна при любом

Поскольку А;- >- 0

для j (фв) 6 J

(и As = 0, в то время как aLs<C0),

то

из rs -< 0 следует

а} >- 0

для

всех

/' 6 / . Но

если а7 >- 0 для

всех /,

 

то

А оптимальна, а-это

противоречит условию теоремы.

Отсюда следует, что при некотором j

 

 

и

можно найти

соответствующие а- и г-.

 

 

 

 

 

 

 

 

 

 

 

 

Пусть

теперь теорема

17.2

неверна

из-за того,

 

что

г - > 0 .

В

первой части доказательства было

показано,

что

если

 

0

то а;->

0.

Если г- >- 0,

то для всех j

с aLjy> 0

имеем

—а7 =

 

=

_

_

 

 

 

 

 

_

 

 

влечет

за

 

 

aLi

 

r7 > - r - > 0 .

Следовательно, aLj->> 0

собой

а7 >- 0.

Итак,

в случае

rs >- 0

всегда а7- >- 0 для

Последнее означает,

что А —оптимальна,

что

опять-таки

противоречит

условию тео­

ремы. ш

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Д о к а з а т е л ь с т в о

т е о р е м ы

17.3.

Справедливость

теоремы 17.3

следует непосредственно из (25) и (26).

Если ащ ^О ,

то условие

Aj

>- 0

 

можно

вывести

из

(25),

поскольку

А7 ^=0,

А- >■ 0

и aL- > 0.

Если

>

0,

то из (26)

получаем

А7 >- 0,

поскольку

из

aLj >

0

следует

 

-< г7 по правилу выбора столбца г-. а

 

 

Д о к а з а т е л ь с т в о

т е о р е м ы

17.4.

Эта

теорема

непосредственно

выводится

из

(24).

Действительно,

г- >- rs,

поскольку

aLi >

0

и А- >

0.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Следствием из теоремы 17.2 является тот факт, что первая

таблица,

для

которой либо

нельзя

определить

rs,

либо

rs >-

0 ,

будет оптимальной. Чтобы показать, что такая таблица обяза­

тельно будет

получена, докажем следующие две теоремы. ш

Т е о р е м а

17.5. Если используется допустимое

правило выбора

производящей

строки, то через конечное число

преобразований

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