Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 193
Скачиваний: 0
388 ГЛ. 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ '
задачи линейного программирования, то ее оптимальным реше нием является
|
|
ХВ = |
В -1!), |
x N = |
О, |
|
|
причем cBB _1N — с * > |
0. |
Если |
В _1Ь — целочисленный |
вектор, |
|||
то |
х'в = В _1Ь, х Лт = 0 |
является |
также |
оптимальным решением |
|||
задачи целочисленного программирования (2в). Если |
В -1Ь — |
||||||
нецелочисленный |
вектор, |
необходимо |
увеличить x N от нуля |
||||
до |
некоторого неотрицательного целочисленного вектора, |
такого, |
|||||
что |
|
|
|
|
|
|
|
|
х в |
= В -1Ь — B -1 Nxw ^ |
0 (целые). |
|
|||
Возникает два вопроса:
1) |
когда В _1Ь — B -1Nxjy ^ 0? |
|
|
2) |
когда В_1Ь — В _1 Кх^ — целочисленный вектор? |
|
|
Рассмотрим сначала второй вопрос. Пусть B-1N есть мат |
|||
рица [аь а 2, . . ., a j , а В _1Ь — вектор р0. Тогда второй |
воп |
||
рос можно сформулировать как задачу нахождения таких |
Xj, |
||
что |
|
|
|
|
Zi a ixi = Ро (mod 1 )*), |
(3) |
|
|
3 |
|
|
|
Xj s 0 (mod 1), x j ^ 0 |
(/ = l , . . . , r a ) . |
|
Так как целые части компонент вектора aj, умноженные на целое число Xj, равны нулю по модулю 1 , интерес представляют лишь
дробные части компонент векторов aj и Р0. Пусть ф (aj) — aj
и ф (Ро) — РоТогда (3) эквивалентно
2 a JxJ — Ро(mod 1), |
(4) |
|
Xj = 0 (mod 1 ), X j^O |
() = |
1 , ... ,ri). |
Заметим, что (4) можно было бы получить, применяя отображение / = ф в 1 к ограничениям задачи (26).
Так как в (2в) |
с%- = |
CbB _1N — c N ^ 0, мы стремимся увели |
|||
чивать x N как можно |
меньше. Таким образом, если отброшено |
||||
требование |
х в ^ |
0 , |
задача целочисленного программирования |
||
примет вид |
|
|
|
|
|
!) |
Переменными |
в |
(3) |
являются компоненты xN — небазисные относи |
|
тельно |
оптимального базиса В непрерывной (нецелочисленной) задачи (2в). |
||||
Здесь и далее, |
очевидно для удобства, автор отождествляет переменные x N |
||||
с переменными |
|
хп задачи (1).— Прим. ред. |
|||
19.2. АСИМПТОТИЧЕСКИЙ АЛГОРИТМ |
389 |
|
максимизировать |
|
|
Св В _1Ь — CjvXjy |
|
|
при условии |
|
|
2 a.jXj = Ро (mod 1), |
(5) |
|
О |
|
|
Xj = 0 (mod 1 ), x j ^ O |
(j = 1 , . . ., |
п). |
С каждой задачей целочисленного программирования (26) сопо ставим соответствующую ей задачу линейного программирования, получаемую отбрасыванием требования целочисленности х. Допустимые решения задачи линейного програм мирования, соответствую щей (26), образуют выпуклый многогранник, который будем обозначать Р ' . Выпуклую оболочку всех целочисленных точек, принадлежащих Р ', обозначим через Р. Известно, что оптимальное решение задачи (26) является верши
ной Р 1). На рис. 19.1(a) Р' —
четырехугольник, а Р — ше стиугольник внутри Р ' .
Задача целочисленного программирования (5) полу чается из (26) отбрасыванием
требования хв ^ 0. Допустимые решения задачи линейного про граммирования, соответствующей задаче (5), образуют конус, который обозначим буквой С 2). Выпуклую оболочку всех целочисленных точек С, называемую многогранником крайних точек, обозначим через Рх-(В, N, Ь). На рис. 19.1(a) С — нео граниченная область с вершиной к, а Рх>(В, N, Ь) — неогра ниченная заштрихованная область.
Многогранник крайних точек имеет принципиальное значение и будет детально изучаться в гл. 20. Чтобы облегчить изучение многогранника крайних точек, введем еще одно пространство.
Ч Точнее говоря, существует оптимальное решение задачи (26), являю
щееся |
вершиной многогранника Р.— Прим, перев. |
|
(хв, |
xN) = (В_1Ь, 0), |
|||
2) |
Имеется в виду выпуклый конус с вершиной г = |
||||||
образованный решениями |
системы Вхв + Nx_Y = |
b,x v ^ 0 |
в х-простран- |
||||
стве размерности п + |
т. |
Конус с вершиной в точке |
Р 0 |
— это такое мно |
|||
жество Q, что если Р , |
(j Q и X > 0, то [ Р 0 + к ( P j |
— Р 0)] |
6 Q.— Прим. ред. |
||||
390 г л . 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ
Как было показано в § 19.1, вектор-столбцы а;- из (5) являются элементами некоторой абелевой группы G.
Рассмотрим образы / (а;) (j = |
1, |
. . ., |
п) всех небазисных век |
тор-столбцов a j задачи ( 2 6 ) , где / |
= |
< £ В - 1 . |
Среди них мы выделим |
подмножество ц ненулевых элементов группы G. Очевидно, п' = =■ | т] | ^ и, поскольку два вектора а; могут отображаться в один
и тот же групповой элемент g. |
Введем |
п' |
переменных |
t (g), |
|
по одной для каждого g £ т), и |
пусть t |
есть |
«'-мерный |
вектор |
|
с компонентами t (g). Если все векторы |
а7- |
отображаются в раз |
|||
личные ненулевые элементы g, то t-пространство точно такое же, как пространство x N. Если x N удовлетворяет ограничениям (5), то переменные t (g) удовлетворяют групповому соотношению
h t { g ) g = g0,
g e v |
(6) |
t { g ) ^ 0 |
(целые), |
где Ро из (5) заменено элементом группы goПоскольку порядок группы G равен | G | = | det В | = D, то п' ^ D, так как в G могут быть элементы, не являющиеся образами ни одного из неба зисных векторов а, при отображении /.
Пусть
с* (g) = |
min cf |
(J = { j \ f (a,) = g}). |
Другими словами, |
если в |
элемент g £ G отображается более, |
чем один столбец, то сопоставим с этим элементом минимальную из стоимостей этих столбцов. Тогда получим следующую задачу минимизации в t-пространстве, соответствующую задаче (5):
минимизировать |
|
|
TiC*(g)t(g) |
(c* (g )> 0 ) |
|
g£r) |
|
|
при условии |
|
|
T i H s ) g = g o |
(7) |
|
t { g ) ^ 0 , |
целые. |
|
Соответствие между х-пространством переменных |
задачи (2а) |
|
и t-пространством переменных задачи (7) является |
естественным. |
|
Для каждой задачи целочисленного программирования существует базис В, являющийся оптимальным базисом соответствующей ей задачи линейного программирования. Поэтому вектор х предста вим в виде [хв, х^]. Если x N известно, то значение хв однозначно определяется соотношением хв = В -1 (Ь — Nxw). С ^отношение