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

414 гл : 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ п р о г р а м м и р о в а н и е

Заметим, что решения задачи (30), полученные с использова­ нием этих периодических поправок, являются оптимальными целочисленными тогда и только тогда, когда

х в = B -1b — B _1Nx^ ^ 0.

В настоящем случае / [41, 47] = g3, так что

x N = (0, 0, 0, 1, 1).

Используя значения для В _1Ь и B -1N из оптимальной таблицы; задачи линейного программирования, получаем

является оптимальным решением.

Хотя у нас имеются достаточные условия (теорема 19.8) приме­ нимости асимптотического алгоритма, реальные вычисления пока­ жут, что алгоритм дает оптимальное решение и в большинствеслучаев, когда достаточные условия не выполнены. На рис. 19.4 зачерненные точки обозначают пра­ вые части Ь, для которых асимптоти­ ческий алгоритм дает оптимальное решение, а светлые кружки указы­ вают правые части, где алгоритм не

дает решения.

19.3. Алгоритм групповой миними­ зации (Ху [112])

В этом параграфе мы рассмотрим, алгоритм решения задачи групповой; минимизации:

минимизировать

2 c*(g)-t(g)

Очевидно, что задача (1) охватывает случай g (; ц cz (3 \ 0. Действительно, для элемента g' $ ц можно взять в качестве его стоимости с* (g') еколь угодно большое число, так что g' в опти­

Мы предполагаем, что группа G является циклической группой порядка D.

Заметим, что g0 является одним из элементов группы G. Поэто­ му, решение задачи (1) определяет представление группового элемента g0 через другие элементы группы с наименьшей стоимо­ стью; gQ = g0 со стоимостью с* (g0) является одним из возмож­ ных представлений элемента g0. Вместо того, чтобы решать зада­ чу (1) для одного g0 мы решим ее для всех возможных правых частей go = gi, g2, . . ., gD-i. Другими словами, каждый эле­ мент группы мы хотим выразить с наименьшей стоимостью через другие групповые элементы, на которых эта стоимость дости­ гается. Эту задачу мы будем решать по этапам. Информация, рас­ сматриваемая на каждом этапе, называется текущей. Пусть с (go) — наименьшая (текущая) стоимость представления ga через другие элементы, известная к данному текущему моменту. Пару, образованную из с (ga) и числа, указывающего (кодирующего) 3) представление ga в виде комбинации со стоимостью с (ga), будем называть пометкой группового элемента ga. Пометку назовем временной, если она может-быть изменена в процессе вычислений, т. е.| если может быть найдено представление для ga в виде ком­

бинации элементов из G \ 0 со стоимостью, меньшей текущей стои­ мости с (ga)- В противном случае пометку назовем постоянной.

Вычисления начинаются с пометок [с* (^а), а]. Эти помет­ ки — временные, поскольку нет уверенности, что стоимость с* ( g a ) представления g a = g a элемента g a наименьшая. Первую компо­

ненту пометки будем называть ее стоимостью. Будем говорить, что пометка элемента g a меньше пометки элемента £р, -если стоимость

пометки элемента ga меньше стоимости пометки элемента gp. Алгоритм (Ху [112]) состоит в следующем.

х) с* (g) неотрицательно, так как оно равно компоненте вектора ciy

оценок небазисных переменных относительно оптимального базиса В. См. задачу (5) из предыдущего параграфа,— Прим. ред.

2)Нулевые стоимости заменяются стоимостями ег > 0 только для удоб­ ства доказательства. Нет необходимости делать такие замены при вычисле­ ниях.

3)Кодировка представления элемента в виде суммы с соответствующей стоимостью осуществляется специальным образом посредством запоминания лишь одного слагаемого этого представления, по которому рекурсивна можно восстановить остальные. Подробнее об этом будет сказано далее.—

Прим. ред.

416гл. 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

Ша г 1. Сравнить стоимости всех временных пометок, объя­ вить пометку с минимальной стоимостью постоянной и выделить

ными пометками и пусть gir—последний групповой элемент, получивший постоянную пометку. Найти суммы

текущей пометки элемента g i . 1). (Можно также заменить вторую компоненту пометки (gi + gir) второй компонентой пометки g ir).

Перейти к шагу 1. Работа алгоритма заканчивается, когда все пометки станут постоянными.

Прежде чем привести доказательство и подсчитать число опе­ раций в алгоритме, рассмотрим численный пример. Предположим, что группа G — циклическая порядка 10; соответствующие стои­ мости приведены ниже:

Сначала заполним ряд из D — 1 пар, соответствующих D — 1 элементам группы. Все пометки — временные:

1.Сравниваем стоимости всех временных пометок и выделяем

i г j u j

янную пометку, ее стоимость может не совпадать с исходной c * { g i ) . Стоимость пометки определяется представлением элемента с наименьшей стоимостью, информация о котором и дается второй компонентой q .— П р и м . р е д .

418 ГЛ. 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

повторяем шаг 1 и шаг 2. В дальнейшем замен не происходит, так что в конце концов мы получим

Предлолржим, что мы хотим найти представление группового элемента gi, имеющее наименьшую стоимость. Второй компонентой пометки gi является 3. Следовательно, мы знаем, что в искомое

представление gi — 2 * (ё)'ё входит t (g3) ^ 1 . Возвращаясь назад, получаем gt — g3 = gs и видим, что второй компонентой пометки элемента g8 является 2. Это означает, что t (g2) ^ 1. Возвращаясь назад, получаем gs — g2 = ge и видим, что второй компонентой