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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

 

 

19.3.

АЛГОРИТМ ГРУППОВОЙ МИНИМИЗАЦИИ

423

, ,

„ ,

.

оч

(D— 1) (D —2)

•

В2

сложении

и та­

1 +

2 +

. . . +

(D — 2) ==

- -------у --------

=

-у -

кое же число сравнений. В нашем алгоритме, следовательно,

Z)2

необходимо всего D 2 сравнений и -у- сложений. Если на шаге 1

мы каждый раз насчитываем D сравнений, тогда необходимо всего 1,5 D 2 сравнений и 0,5 D 2 сложений. Итак, в худшем слу­ чае, нам необходимо 2Л2 операций независимо от того, является D простым числом или нет. Таким образом, предлагаемый алго­ ритм имеет следующие преимущества.

1.Число операций в данном алгоритме меньше числа операций

валгоритме Гомори (2D2 вместо числа, заключенного между 2D2

и 4D 2).

2.Шаги одинаковы при выборе постоянных групповых эле­

ментов. Они не зависят от порядка группы G или элемента g.

3.Когда фиксированное g0 в (1) принадлежит Р, то вычисле­ ния могут быть при желании прекращены.

4.Необходим меньший объем памяти.

ГЛАВА 20

ГРАНИ ЦЕЛОЧИСЛЕННОГО МНОГОГРАННИКА

20Л. Введение В гл. 19 мы рассматривали три задачи; первая из них:

максимизировать при условии

С ВХВ + c Nx N

 

В хв +

Nx^ = b,

( 1 )

х в, x N ^

0 (целые).

 

Выпуклая оболочка неотрицательных целочисленных точек, кото­ рые удовлетворяют ограничениям задачи (1), обозначается через Р. Вторая задача:

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

при условии

с вВ -1Ь — c%xN

 

хв +

B^Nxjyr = ВЧ),

(2)

 

x N ^

0, х в,

Хдг (целые),

 

где cJv = dBB _1N —

^

О, а

В — оптимальный базис

задачи

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

Рх (В, N, Ь). Третья задача:

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

2 с* U ) t (g)

геч

при условии

 

 

2

t{g)-g = g0,

(3)

g£

В

 

t(g)^ 0 (целые).

Выпуклая оболочка неотрицательных целочисленных решений, удовлетворяющих / ограничениям задачи (3), обозначается через Р (G, г], g0). Било показано, что оптимальное решение задачи (3) естественным образом соответствует оптимальному решению зада­ чи (2). Если у£в ^3= 0, то оптимальное решение задачи (2) является

 

 

 

 

 

20.1.

ВВЕДЕНИЕ

 

 

 

425

также

оптимальным

решением задачи

 

(1).

Многогранники

Р х (В,

N, Ь) и Р (G, т), g0) по существу одинаковы.

Точка ( хв, x N}

является

вершиной многогранника Р х (В, N, Ь),

тогда

и только

тогда, когда t

— F (хв, x N) — вершина многогранника Р (G, р, g0).

Если /

(аг) =

/ (aj),

i ф ] , то либо xt =

0,

либо Xj = 0. В этой

главе мы изучим

многогранник Р (G,

т),

g0)

независимо от мини­

мизации

целевой

функции

2 е* (§)

t (&)•

Выпуклая

оболочка'

Р (G, ц, g0) представляет особый интерес, поскольку все ее вер­ шины являются оптимальными решениями задачи (1) с некоторой достаточно большой правой частью Ь. Сформулируем это свойствоболее точно. Если с = ( с в, с^) — некоторый вектор, где В — оптимальный невырожденный базис задачи линейного програм­

мирования,

соответствующей

задаче (1),

т. е. с вВ -1Ь — c N =

= c.v ^ 0 и

В _1Ь > 0, то

оптимальное

решение х задачи (1)-

совпадает с оптимальным решением задачи (2), которое является вершиной многогранника Рх (В, N, Ь), при условии, что Ь — доста­ точно большое. Эта вершина многогранника Рх (В, N, Ь) может

быть

получена из

соответствующей

вершины

многогранника-

Р (G,

ц, g0). Если

v — некоторая

вершина

многогранника.

Р (G, ц, g0), то в задаче (1) существует вектор с, оптимальный базис В и Ь, такие, что оптимальное решение задачи (1) получается; из вершины V.

Другое важное свойство многогранника Р (G, ц, g0) состоит в том, что его грани являются в некотором смысле самыми силь­ ными отсекающими плоскостями для задачи (1).

В гл. 13 мы сформировали отсечение Гомори после получения: оптимального решения задачи линейного программирования. Любая отсекающая плоскость, сформированная без использова­ ния условий х в ^ 0, является просто неотрицательной взвешен­ ной комбинацией граней.

Заметим, что многогранник Р (G, ц, g0) либо пустой, либо- n'-мерный. Если g0 не лежит в подгруппе, порожденной элемен­ тами ц, то Р (G, т), g0) — пустой, или, что то же самое, задача (З)1 не имеет допустимых решений. Отсюда следует, что многогранник: Рх ( В , N, Ь ) также пуст и что исходная задача целочисленного-

программирования (1) не имеет решения. Если Р (G, ц, g0) не пуст,

то пусть t = [t (gi), . . ., t (gk), . . ., t (£„<)] — его точка, s (h) —

порядок группового элемента h, a u (h) есть n'- мерный вектор,,

такой,

что t (h) = 1, а все остальные компоненты равны 0.

Тогда,

вектор

ц,

t +

s (h) • u

(h)

также

является

точкой

многогранника

Р (G,

g0).

Для

каждого h £ г\

точка t

+ s (h)■u (h)

является

допустимой. Ясно, что эти п'

= | ц | точек независимы;

следова­

тельно,

многогранник

Р (G,

ц,

g0) — «'-мерный.

 

будем,

Поскольку Р (G,

ц, go) — «'-мерный

многогранник,

использовать слово «грань»

для

обозначения

(«' — 1)-мернош

гиперплоскости, такой, что

 

 

 

 

 

 

426

ГЛ. 20. ГРАНИ ЦЕЛОЧИСЛЕННОГО МНОГОГРАННИКА

1)все точки Р (G, т], g0) лежат по одну сторону этой гипер­ плоскости;

2)каждая точка гиперплоскости записывается как взвешен­ ная сумма п' точек из Р (G, r|, g0).

Каждую грань многогранника Р (G, т), g0) можно представить

ввиде неравенства (точки грани удовлетворяют равенству, а все

точки из Р (G, г), g0) — неравенству)

 

H y ( g ) 4 g ) > V о-

(4)

 

гел

 

 

Докажем, что (а)

у (g) ^ 0

и (б) у0 ^ 0. Предположим, что

в (4) имеется коэффициент у (К) < 0. Пусть

s (К) — порядок

группового элемента

h. Тогда

t + ks (h) u (h)

также является

решением задачи (3) и, следовательно, принадлежит Р (G, т), g0).

Так

как все точки

многогранника Р (G, ц, g0) располагаются

по одну сторону грани, то

 

 

2

y{g)t{g) + V{h)[t(h) + ks{h)]^iy0

(5)

для

любого положительного к . Однако при достаточно больших

к неравенство (5) не выполняется в силу у (h) < 0. Таким образом,

отрицательных у (g) в соотношении

(4) нет. Поскольку у (g) ^ 0

и t (g) ^ 0, мы заключаем, что в ( 4 )

у0 ^ 0.

Обозначим грань 'многогранника Р (G,

ц, g0) через (у* Yo)> где

у есть и'-мерный вектор, а у0— скаляр, В

х-пространстве обозна­

чим грань многогранника Р х (В, N, Ь) через ( у'в, \ n , Yo)- Посколь­ ку х в — В -1 (Ь — Nx.y), неравенство в х-пространстве эквивалент­

но неравенству для небазисных переменных x N. Обозначим соот­

ветствующее неравенство для переменных x N через

(0,

y N, у0).

Заметим,

что (0,

y N,

уа) является (п — 1)-мерной гранью много­

гранника

Р х (В,

N,

Ь) тогда и только тогда, когда

(у,

у0) есть

(п' — 1)-мерная грань многогранника Р (G, ц, g0),

гДе Y I/ (а*)] =

= уг. Чтобы получить грань многогранника Рх (В,

N,

Ь),

мы про­

сто запишем значения компонент у (g) на всех соответствующих местах в y N.

Неравенство

2 У ( ё ) Н ё ) > У а ,

(6 )

гел

 

 

где у (g) ^ ’0 для всех g £ Ц и у0

0, определяет

ту часть про­

странства, где содержится грань многогранника Р (G, ц, gQ). Грань обладает следующими свойствами:

1)все точки многогранника Р (G, т), go) расположены по одну сторону от этой грани и

2)все точки грани могут быть записаны как взвешенные суммы

вершин Р (G, ц, g0).

20.1. ВВЕДЕНИЕ

427

Обозначим множество неотрицательных целочисленных

реше­

ний задачи (3) через Т. Легко показать, что (6) дает грань много­

гранника

Р (G, т), g0) тогда и только тогда, когда

Г) для каждого t £ Т выполняется у*

 

То и

2') имеется п' векторов tl 6 Т , которые порождают гиперпло­

скость у-1 = То-

 

 

 

Теорема 20.1. Неравенство Yt ^ у0 >

0 дает грань Р (G,ri, g0)

тогда и

только тогда,

когда у — базисное

допустимое решение

системы

неравенств

 

 

 

 

yt ^

То (для всех t g

Т).

(7)

Эта система предполагает наличие одного неравенства для каж­ дого t £ Т. (Напомним, что базисное допустимое решение есть решение, которое удовлетворяет всем неравенствам и образует

равенства на множестве строк ранга п'.)

 

 

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

Докажем

сначала,

что если (у, у0) — грань,

то

(у, Уо)— базисное

допустимое

решение

системы (7).

Если

(у,

у0) — грань,

то

из

1') следует

yt

^ у0 для всех t 6 Т,

а из

2')

следует, что

имеется п' различных векторов С 6 Т , которые

удовлетворяют

соотношению

yt{ =

у0

и порождают гиперпло­

скость yt = у0.

Поскольку

у0 >

0,

граць

не проходит

через

начало координат. Отсюда заключаем, что п' векторов t* линейно

независимы.

Следовательно,

у — базисное

решение системы (7).

то

Если у — базисное допустимое решение системы неравенств (7),

yt ^

у0

для всех

t 6

Т

и, следовательно, 1') выполнено.

Поскольку

у — базисное

допустимое

решение,

имеется п'

неза­

висимых строк в (7),

 

которые обращаются в равенства. Мы можем

тогда взять эти строки в

качестве

векторов

tl. Поскольку t*

линейно

независимы,

они

должны

порождать

гиперплоскость

yt

= у0,

так что 2')

также выполнено.

Следовательно, (у,

у0) —

грань. |

 

сделать

несколько

замечаний

относительно

теоре­

 

Можно

мы 20.1.

 

 

 

можно считать у0

= 1, поскольку положи­

 

1. В теореме 20.1

 

тельные

множители

(у, у0) не меняют грани.

 

 

 

2. Хотя

имеется

бесконечно много векторов t, принадлежа­

щих Т , все t, для которых t

(g)

^ s (g),

излишни. Следовательно,

в

качестве

общего

числа

 

неравенств

системы

(7) можно

взять

II* (£)•

3.С большим, но конечным числом неравенств системы (7) придется иметь дело при вычислениях с помощью строко-порож­

дающих методов, подобных описанным в работах [82] и [91]. В основном мы используем либо прямой, либо двойственный симп­ лекс-метод, но строки порождаем только, когда это необходимо.

428 ГЛ . 20. ГРА Н И Ц ЕЛ О Ч И СЛ ЕН Н О ГО М НОГОГРАННИКА

(Вычисления, проводимые для получения грани многогранника,

описаны в § 2 0 .2 .)

 

 

 

Предположим, например, что м ы

намереваемся получить отсе­

к а ю щ у ю

плоскость для

задачи

целочисленного программирова­

ния (2), такую, что угол между

у и

с минимальный. И н ы м и сло­

вами, м ы

хотим

 

 

 

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

 

 

 

 

 

су

 

 

 

II С II

II Yll

 

при условии

 

 

 

 

yt ^

Уо для всех t '6 Т.

Предположим; что м ы располагаем всеми t £ Т . Тогда это задача

линейного программирования со многими неравенствами, по одному неравенству для каждого t, принадлежащего Т. Если

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

текущее у не удовлетворяет. Таким образом, вычисления состоят из двух частей. Первая часть — вычисление двойственной допу­ стимой симплексной таблицы для целевой функции (су)/(|| с|| ||у||), ограниченной подмножеством неравенств из (7). Вторая часть — вспомогательные вычисления (порожденных) неравенств, исполь­

зуемых в первой части. Если воспользоваться текущим у в графе

Н (G, ц, у), можно найти кратчайший путь от 0 до gQ длины yt <

< у0.Тогда неравенство yt ^ у0 не выполняется. Это неравенство

добавляется к неравенствам первой части. (Неравенство необхо­ димо видоизменить, прежде чем записать его в конец двойствен­ ной симплексной таблицы.) Затем м ы производим основной шаг

двойственного симплекс-метода первой части и получаем новое у.

Это новое у интерпретируется как длины дуг при вспомогатель­ ных вычислениях. Если, используя у как длины дуг, м ы не смо­ жем найти кратчайшего пути от 0 до g0 с общей длиной yt < у0,

то это у является также прямо допустимым и, следовательно, оно оптимально.

Поскольку м ы ограничиваемся у0 > 0 при обсуждении нера­ венства в теореме 20.1, остается еще возможность у0 = 0. Вер­ немся теперь к случаю у0 = 0 .

Теорема 20.2. Единственно возможными гранями (у , у0) мно­

гогранника Р (G , т), go) при уо =

0 являются п' гиперплоскостей

у = и (h) или, что эквивалентно,

t (h) = 0 (т. е. гиперплоскости,

содержащие координатные оси).

 

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