15.3. ПРИЛОЖЕНИЯ |
327 |
является транспортная задача, в которой стоимость |
перевозки |
по некоторому маршруту складывается из двух частей. Первую часть составляют фиксированные расходы, связанные с исполь зуемым маршрутом. Они не зависят от количества груза. Вторая часть пропорциональна количеству груза, провозимого по дан ному маршруту. Таким образом, общая стоимость zj перевозки по данному маршруту / задается как
kj |
] cxj, |
если |
Xj >> 0 , |
{ |
О, |
если |
Xj —О, |
где kj — фиксированные расходы, |
a Xj — количество груза, пере |
возимого по маршруту ]. |
Стоимость Zj можно записать по-другому: |
Zj = |
8 k j -f - c x j , |
X j |
б M , |
0 |
^ 6 ^ 1 |
(целое), |
|
где M — верхняя граница Xj.
Пусть требуется аппроксимировать произвольную нелинейную целевую функцию кусочно-линейной функцией, как показано
Р и с . 15.4.
на рис. 15.4. Значение функции на отрезке, где она линейна, задается выпуклой линейной комбинацией значений функции на концах этого отрезка. Таким образом, пусть
X= к()Хй |
—)—. . . —кпХп, |
/ (X) = к0 |
/ (Хо) + |
kif (Xi) + • • • + k„f (хп), |
1 = ^0 |
^1 |
кП1 |
h > 0 (i = 0 , . .., п),
328 |
ГЛ. |
15. СМЕШАННЫЙ АЛГОРИТМ |
|
^-0^ бд, |
|
|
|
“Ь 6j |
|
|
^-2 ^ |
6i —|—б2, |
|
|
^n-i^Ss |
бп_2“Ь Sn_j, |
|
^■71^ |
|
$П-Ь |
|
^0 + • • • 4 “ 6n_j = 1 , |
|
О ^ бг ^ 1 |
(целые) (г = |
0 , 1 , . .., п — 1 ). |
Заметим, |
что если бг = 1, то А,* |
и Яг+ 1 могут принимать нену |
левые значения, а в сумме дают единицу; остальные к равны нулю. Четвертый класс задач можно назвать смешанным классом.
Не существует стандартного способа превращения задач этого класса в целочисленные программы. При одной формулировке может получиться намного меньше переменных, чем при другой. Для примера приведем некоторые из таких задач. Это задача об ортогональных латинских квадратах, задача коммивояжера, задача о минимальном числе цветов для раскраски карты, неко торые задачи кодирования и другие. Обсудим лишь задачу о комми вояжере и задачу о раскраске, так как они являются наиболее известными. Свести некоторую задачу к задаче целочисленного программирования еще не значит ее решить, поскольку в послед ней может оказаться слишком много переменных, слишком много ограничений и т. д. Тем не менее стоит отметить,, что в терминах целочисленного программирования формулируется множество раз личных задач.
Одной из наиболее известных нерешенных проблем в матема тике является задача о раскраске карты, в которой требуется доказать или опровергнуть тот факт, что любую карту на пло скости можно раскрасить, используя четыре цвета или меньше. Карта делит плоскость на много областей; ограничение состоит в том, что две области, имеющие общую границу, должны быть раскрашены в разные цвета. Если бы существовал алгоритм, позволяющий найти минимальное количество цветов для любой карты, то он мог бы служить для построения примеров и контр примеров.
Допустим, что карта может быть раскрашена четырьмя цве тами и пусть 0, 1, 2 и 3 соответствуют этим цветам. Каждая область i представлена целочисленной переменной xt. Для двух соседних областей i и j мы хотим, чтобы xt ф Xj. Это эквивалентно объеди нению ограничений:
Либо X i — X j ^ 1, Либо X j — x t ^ 1.
Используя обсужденную ранее технику формализации, можно записать
X f |
X j |
1 |
46^*, |
X j |
X i |
1 |
4 (1 |
6^*). |
Кроме того, |
мы хотим, чтобы |
|
|
|
|
|
|
|
О |
xi |
3 |
(целые), |
|
|
|
|
О ^ |
^ 1 |
(целые). |
|
|
Поскольку все ограничения являются неравенствами, можно ввести слабые переменные и искусственные переменные, а целевой функцией сделать сумму искусственных переменных. Если целе вая функция достигнет нулевого значения, то карту можно раскра сить четырьмя цветами.
Задача коммивояжера может быть поставлена следующим образом. Даны п городов и расстояния dtj от города i до города ). Каков должен быть маршрут коммивояжера, если он начинает путешествовать из города, где он живет, посещает каждый город ровно один раз и возвращается в свой город, причем общая длина его пути должна быть минимальной. Мы не требуем, чтобы dtj =
= |
dji, |
но требуем, чтобы dtj ^ 0 и dtj + djh |
^ dik для |
всех |
г, |
к. |
Допустим, что коммивояжер начинает из |
города 1. |
Тогда |
любая перестановка из 2 , 3, . . ., п дает возможный маршрут.
Таким образом, существует (п — 1)! маршрутов, которые требуется перебрать.
Можно не требовать, чтобы dl} + djh ^ dih, и сформулировать задачу так: коммивояжеру требуется побывать в каждом городе по меньшей мере один раз, прежде чем вернуться в свой город. Однако если сначала найти кратчайший путь между каждой парой городов и заменить исходные расстояния между ними на полу ченные, то задача станет в точности такой, какой она дана в пер
вой формулировке. Таким образом, будем считать, что |
всегда |
dij + |
djk ^ dik. |
и ком |
В |
нашем случае допустим, что имеется п + 1 городов, |
мивояжер начинает свой путь в городе 0 , посещает каждый город
в точности один раз и заканчивает его в городе п, не возвращаясь домой. Требуется минимизировать общую длину маршрута. В та кой постановке маршрут называется открытым в отличие от упо мянутого выше, где маршрут был замкнутым. Для того чтобы превратить замкнутый маршрут в открытый, достаточно предста вить начальный город в виде двух городов, один из них будет городом 0, другой п. Поэтому рассуждения будут проведены применительно к открытому маршруту, начинающемуся в горо де 0 и кончающемуся в городе п. Положим хц = 1, если комми вояжер едет из города i в город /, и хц = 0, если нет. Так как
330 |
ГЛ. 15. СМЕШАННЫЙ АЛГОРИТМ |
каждый город можно посетить только однажды, получим
п - 1
2 |
~ 1 U ~ П . . щ i j). |
г=0 |
|
Поскольку из каждого города (кроме города п) коммивояжер должен уехать, имеем
п |
xij = 1 |
(£ = 0 , 1 , . . п 1 i =7^ /)•* |
2 |
3 |
= 1 |
|
Эти два множества ограничений показывают, что в графе, иллю стрирующем маршрут коммивояжера, города 0 и п имеют сте пень 1 , а все остальные города — степень 2 .
Однако указанные выше два множества ограничений могут выполняться и в том случае, когда коммивояжер посетит лишь часть городов, после чего окончит маршрут, а оставшиеся города соединит петлей или несколькими петлями Ц,- Чтобы сделать подобные подмаршруты невозможными, введем третье множество ограничений. Во-первых, сопоставим с каждым городом i дей ствительное число jji (0 ^ y t ^ п). Затем потребуем выполнения следующих условий:
У1 — Уз + пхи < п — 1 (0 < i < п — 1 ; 1 < j < п; i ф j).
Чтобы увидеть, что это множество ограничений исключает возможность замкнутого подмаршрута, рассмотрим такой зам кнутый подмаршрут, состоящий из к городов. Для каждой дуги этого подмаршрута имеется 'введенное неравенство. Если сложить все неравенства, соответствующие к дугам подмаршрута, все y t взаимно уничтожатся и в итоге получится заведомо неверное неравенство пк ^ . ( п — 1) к, что невозможно. Таким образом, решение, содержащее замкнутый подмаршрут, не удовлетворяет третьему множеству ограничений. С другой стороны, чтобы пока зать, что любой открытый маршрут может удовлетворять третьему
множеству |
ограничений, положим |
y t = t, |
если |
город i |
есть t-ж |
город по порядку в данном маршруте. Тогда |
y t — у} |
^ п — 1 |
для |
всех г, |
/, и, следовательно, |
если x tj |
= |
0 , |
все ограничения |
третьего множества выполняются. Для x |
t j |
= 1 |
получим y t = t |
и У} |
= £ + |
1- Поэтому t — (£ + |
1) + п = |
п — 1. Целевой функ |
цией |
задачи коммивояжера |
является |
|
|
|
|
|
|
|
71- 1 |
71 |
|
|
|
|
|
______________ |
2 — |
2 |
2 |
dijXijm |
|
|
|
|
|
г=0 j —12 |
|
|
|
|
2) В этом случае граф, изображающий маршрут коммивояжера, будет несвязным.— Прим. ред.
ГЛАВА 16
ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ С ПАРАБОЛИЧЕ СКИМИ ОГРАНИЧЕНИЯМИ
16Л. Введение (Витцгалл [215])
В этой главе будут изучены задачи целочисленного програм мирования е параболическими ограничениями. Сначала дадим
Определение. Параболическим ограничением ранга к назы вается ограничение, которое можно представить в форме .
а00 — L 0 (х ) — |
bi (Z,j ( х ) ) 2. — . . . — bh {Lk ( х ) ) 2 > |
0, |
(1) |
где |
|
|
|
Ls (х) = aslxi |
+ . . . + asnxn (s = 0, 1, . . ., |
к) |
(2) |
есть линейно независимые однородные линейные функции от п пере менных и bt ^ 0 (i = 1, . . ., к).
Заметим, что (1) можно привести линейным преобразованием к виду
Уо— у 1-— --- — у1 > 0 . |
( 3 ) |
Параболическое ограничение ранга 0 является линейным огра ничением, а параболическое ограничение ранга п — 1 определяет
выпуклый и-мерный параболоид.
Многие задачи целочисленного программирования могут быть представлены в такой форме. В частности, иногда можно предста вить в такой форме задачу, в которой целевая функция является квадратичной положительной полуопределенной функцией, а огра ничения линейны. Например, пусть целевая функция в. задаче на минимум имеет вид
П71
Z = а + 2 a i x i + |
2 a i j X i X j . |
(4) |
i = l |
i, j = 1 |
|
Можно считать z новой переменной и преобразовать целевую функцию в параболическое ограничение:
минимизировать z |
|
|
* |
|
|
при условии |
|
|
п |
п |
|
z —а — 2 aixi — |
2 aijXiXj^0. |
(5) |
