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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

290

ГЛ. 13. ЦИКЛИЧЕСКИЙ

АЛГОРИТМ

Если s-й столбец является ведущим, то

 

1 + 1

1

1

/ 00

 

#оо

= #оо— #о

 

7os

или

aot^aoo — /оо, поскольку a Qs> f 0s,

или

i+i ^ *

«оо -<геоо-

Другими словами, а00 уменьшится по крайней мере до ближайшего

целого. Следовательно, а00 не может уменьшаться на е (t) при

ОО

2 е (t) < с. Если а00 каждый раз уменьшается до ближайшего i=i

целого или на целую величину, то после конечного числа шагов оно станет меньше любого наперед заданного М (М — предпола­ гаемая нижняя граница). Если алгоритм бесконечен, то а00 должно

оставаться некоторым фиксированным целым числом для t > 10. Предположим, что это произошло.

Тогда рассмотрим а10. Так же как и a00, а10 не может оставаться нецелым значением. Если бы это было так, то, поскольку а00 —

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

 

 

<+1

<

t

А 0

»

 

 

#10 —#10

#1s

f

 

 

 

 

 

hs

 

где 0 < / i o < l

и 0 < / i s< l .

Здесь a\s— неотрицательное число,

большее f\s.

(Если а\$—отрицательно

и

а\ —лексикографически

положителен,

то a*s положительно и, следовательно, а' 0 не может

не измениться.)

Отсюда

 

 

 

 

 

 

1+1 ^ - 1

 

Л

г 1 1

 

 

аю <aio —/io = laioJi

т. е. ai0 уменьшается по крайней мере до ближайшего целого. Поэтому а10 либо будет оставаться некоторым фиксированным

целым числом, либо после конечного числа шагов станет отрица­ тельным. Если а10 станет отрицательным, то первая строка будет

ведущей и

i+i

1

Д10

1

сео = ао

—

as.

 

 

«is

 

Из того, что as > 0 и als <

0,

следует, что aos > 0, т. е. зна­

чение а0о строго уменьшится, что противоречит допущению о неиз­

менности значения а00. Если aXj

^ 0 для всех / =

1, . . ., s, . . .

. . ., п,

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

(Заметьте, что

ведущий

элемент должен быть

отрицательным.)

 

13.2.

ПРИМЕРЫ

291

Таким образом, остается

единственная

возможность — а10

через конечное число шагов должно стать некоторым неотрица­ тельным целым числом и больше не меняться.

Аналогичные рассуждения можно провести и для остальных компонент вплоть до (п + т)-й, что завершит доказательство конечности. Заметим, что нам надо, чтобы только первые п + 1 компонент вектора ос0 были целыми неотрицательными числами,

а00 Jg 0 и ai0 (i =

п +

1 , . . ., п + т) — неотрицательные.

В приведенном

ниже

числовом примере все дополнительные

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

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

13.2. Примеры (Гомори [79])

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

элемент — (*).

Для того чтобы

ускорить

получение решения,

в отдельных

примерах порядок

выбора

производящей строки

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

Пример 1. Рассмотрим задачу целочисленного программи­ рования:

максимизировать

Х0 = 4#! + Ъх2 + х3

1 9 *

292 ГЛ . 13. Ц И К Л И Ч Е С К И Й А ЛГО РИ ТМ

при условиях

 

 

 

Зж1 + 2 ж2

< 1 0 ,

 

 

 

 

 

 

Xi + 4 г2

<

1 1 ,

 

 

 

 

 

?>xv+ За:2 + х3<

13,

 

 

 

 

 

 

а?1, х2, х3> 0 (целые).

 

 

Вводя слабые переменные я4, х5, хв, получаем:

 

 

 

1

—

x i

—

х 2

— * 3

 

 

 

х о

0

— 4

— 5

— 1

 

 

 

X l

0

-

1

 

0

0

D = 1

 

 

х 2

0

 

0

— 1

0

 

 

Х 3

0

 

0

 

0

— 1

 

 

 

Х к

10

 

3

 

2

0

 

 

 

Х ц

И

 

1

 

4

0

 

 

 

х в

13

 

3

 

3

1

 

 

 

 

1

—

X i

—

X i

— х з

 

 

 

х 0

5 5 /4

— 1 1 /4

 

5 /4

- 1

 

 

 

Х\

0

— 1

0

0

-1

0 0

0

х г

1 1 /4

 

1 /4

 

1 /4

0

х 3

0

0

0

- 1

0 —1 0 0

я 4

18/4

10/ 4 *

-

2 /4

0

11

1 4

0

х5

0

0

- 1

 

0

0

0 0 - 1

Х в

19 /4

 

9 /4

-

3 /4

1

 

 

 

 

1

— X 4

—

х 5

— х 3

 

 

 

 

187/10

11/10

— 7 /1 0

— 1

£ > = 4 x 1 0 /4 = 10

 

Х 1

1 8 /10

 

4 /1 0

— 2 /1 0

0

 

 

 

х 2

2 3 /10

— 1/1 0

3 /1 0

0

 

 

 

Х 3

0

0

0

— 1

 

 

 

x k

0

— 1

0

0

 

 

 

Х Ъ

0

0

— 1

0

 

 

 

Х в

7/10

— 9/1 0

- 3/1 0

1 *

 

 

 

Ведущий столбец

 

 

 

1

— хв

£)= 10 X 1 = 1 0

 

1

~Xk

— Хь

х 0

194/10

2/10

4/10

1

Группа неравенств F

Xi

18/10

4/10

—2/10

0

Пр,и„о„»-ТО<0’ 0' 0'°1<5' 5’ 5’ 0>

*2

23/10

—1/10

3/10

0

х3

7/10

—9/10

—3/10

1

<------------(7,1, 7, 0) (2, 6, 2, 0)

*4

0

- 1

0

0

щая строка

(4j 2i 4 , о) (9, 7, 9, 0)

Xi

0

0

- 1

0

 

(1, 3, 1, 0) (6, 8, 6, 0)

Xi

0

0

0

—1

 

(8, 4, 8, 0) (3, 9, 3, 0)

ч

-7 /1 0

—1/10

—7/10 *

0

Например:

 

 

 

 

 

(7,1,7,0) + (4 , 2,4, 0) =

 

 

 

 

 

=

(1,3,10) (mod 10)

13.2. ПРИМЕРЫ

293

Оптимальное решение задачи линейного программирования: х0 =

= 194/10,

хх =

18/10, я2 =

23/10,

х3

=

7/10.

 

1

— X i

— si

—

X i

 

 

 

Х 0

19

1/7

4/7

 

1

Группа неравенств F

X i

2

3/7

—2/7

 

0

 

 

 

х 2

2

- 1 / 7

3/7

 

0

- 1 (0 ,1 ,4 ,0 ) (0, 5, 6,0)

х 3

1

— 6/7

— 3/7

 

1

 

(0, 2, 1, 0) (0, 6, 3, 0)

x k

0

— 1

0

 

0

 

 

 

(0,

3, 5, 0) (0, 0, 0, 0

х ъ

1

1/7

— 10/7

 

0

 

 

 

(О, 4, 2, 0)

X i

0

0

0

— 1

 

 

 

 

*1

0

0

— 1

 

0

 

 

 

Оптимальное целочисленное решение:

 

 

 

х0 =

19, xt

=

2, х2 =

2,

х3 - 1.

Заметим, что, выразив ж4, хь и х6 через исходные небазисные пере­ менные Xi, х2 и х3, получим неравенство s. ^ 0 с целыми коэф­

фициентами:

— 1 0 1 Тб — ^Xl х 1 Тб ^ Xi

^

или Xi -f- Зх2 ^ 8 . Этот вопрос обсуждается в § 13.4. Чтобы полу­

чить матрицу, полностью целочисленную, просто продолжим введение отсечений:

 

1

— X i

— s i

— * 6

 

 

l

— S2

— * i

— * e

X q

19

1/7

4/7

1

 

# 0

19

l

0

1

X i

2

3/7

— 2/7

0

 

X i

2

3

— 2

0

x 2

2

-1 / 7

3/7

0

 

x 2

2

— i

1

0

x 3

1

— 6/7

-3 / 7

1

Производящая x 3

1

— 6

3

1

X i

0

- 1

0

0

<---------------------------- X i

 

0

— 7

4

0

X i

1

1/7

— 10/7

0

строка

Хъ

1

1

— 2

0

X i

0

0

0

— 1

 

X i

0

0

0

— 1

*1

0

0

— 1

0

 

4

0

0

— 1

0

S2

0

- 1 / 7 *

-4 / 7

0

 

s2

0

- 1

0

0

Пример 2. Рассмотрим задачу:

максимизировать х0 =

3xi —

х2,

при условиях

 

 

 

3 # !

—

2хг <

3 ,

—5xt — 4а:2- < — Ю,

2х1 —{-

х2

5 ,

хи х2 > 0 (целые).

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