Промежуточные вычислении 12 страница

Пример 9.3.1

Дневной график работы предприятия, производящего краски, включает изготов­ление партий белой (Б), желтой (Ж), красной (К) и черной (Ч) красок. Так как предприятие использует одно и то же оборудование для изготовления всех четырех типов краски, необходима его надлежащая чистка между изготовлением различ­ных партий краски. Приведенная ниже таблица содержит время чистки оборудо­вания в минутах, если за изготовлением краски, указанной в строке, следует изго­товление краски, указанной в столбце. Например, если за белой краской следует желтая, то время чистки равно 10 минут. Поскольку за определенным цветом краски не может следовать такой же цвет, то соответствующее время чистки пола­гается равным бесконечности. Необходимо определить оптимальную последова­тельность дневного производства четырех типов краски, которая минимизирует суммарное время чистки оборудования.

Время чистки в мин., если следующий цвет
Текущий цвет	белый	желтый	черный	красный
Белый	оо
Желтый		ОО
Черный			ОО
Красный				оо

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

Эту задачу можно решить путем полного перебора шести [(4-1)! = 3! = 6] возмож­ных контуров сети. Приведенная ниже таблица показывает, что последователь­ность узлов Б-»Ж—>К—>Ч—>Б определяет оптимальный контур.

Производственный цикл (контур) Суммарное время чистки

Б->Ж->Ч->К-»Б 10 + 19 + 25 + 45 = 99

Б-»Ж->К->Ч->Б 10 + 18 + 20 + 50 = 98

Б->Ч->Ж->К->Б 17 + 44 + 18 + 45 = 124

Б->Ч->К-»Ж->Б 17 + 25 + 40 + 20 = 102

Б->К->Ч-»Ж->Б 15 + 20 + 44 + 20 = 99

Б->К->Ж->Ч->Б 15 + 40 + 19 + 50 = 124

9.3. Задача коммивояжера

Метод полного перебора контуров практически применим лишь для задач малой размерности. Например, сеть с 11 узлами имеет 10! = 3 628 800 контуров. Следова­тельно, требуется более эффективный подход к решению таких задач.

Определим переменные х_ц равными 1, если узел; достигается из узла г, и 0 в про­тивном случае. Необходимым условием для контура (цикла) является то, что узел I связывается лишь с одним узлом и узел j достигается лишь из одного узла. Считая М достаточно большим положительным числом, мы можем записать задачу пред­приятия, производящего краски, следующим образом.

Минимизировать г = Мх_ББ + 10д:_БЖ + Пх_БЧ + 15a:_£/f + 20х_ЖБ + Мх_жж + \9х_жч + \х_ЧБ + 44д

при ограничениях

+ 18х_жк + 50х_ЧБ + 44х_чж + Мх_чч + 25х_чк + 4Ьх_КБ + 40х_кж + 20х_кч + Мх_кк

^ХББ ^ХБЖ ^ХБЧ ^ХБК ~~ ^ '

^ХЖБ ^ХЖЖ ^ХЖЧ ^ХЖК ~ ^ >

^ХЧБ ^ХЧЖ ^ХЧЧ ^ХЧК ~~

^ХКБ ^ХКЖ ^ХКЧ ^ХКК ~ ^ '

^ХББ ^ХЖБ ^ХЧБ ^ХКБ ⁼ 1» X 4- X + X 4- X ~ 1

ЛГ_£Ч 4- Х_ж1/ + X_t/1J + Х_кч — 1, •"-як ^ХЖК ^ХЧК~^~ ^ХКК ~ 1 '

х_ц = 0 или 1 для всех i и

решение должно быть контуром (полным циклом).

Использование константы М в целевой функции гарантирует, что производство краски одного цвета не будет повторяться подряд.

УПРАЖНЕНИЯ 9.3.1

1. Менеджер проектов имеет 10 сотрудников, которые работают над шестью проектами, причем каждый работает одновременно над несколькими проек­тами, как показано в следующей таблице.

Сотрудники

Глава 9. Целочисленное линейное программирование

Менеджер должен встретиться с каждым из 10 сотрудников один раз в неделю для обсуждения их проблем. Беседа с каждым из них длится примерно 20 ми­нут, т.е. на разговоры со всеми сотрудниками уходит 3 часа 20 минут. Пред­лагается проводить встречи менеджера с группами сотрудников, работаю­щих над одним и тем же проектом, чтобы уменьшить суммарное время, которое тратится на совещания. Менеджер планирует составить график об­суждения проектов таким образом, чтобы уменьшить движение в офисе, т.е. сократить число сотрудников, входящих и выходящих из комнаты для со­вещаний. В какой последовательности необходимо рассматривать проекты?

2. Продавец книг, проживающий в городе А, один раз в месяц должен посетить своих четырех клиентов, которые проживают в городах Б, В, Г и Д соответст­венно. Приведенная ниже таблица содержит расстояния в милях между раз­личными городами.

	А	Б	В	Г	Д
А
Б
В
Г
Д

Необходимо составить маршрут движения продавца книг, минимизирую­щий суммарное расстояние. Сформулируйте задачу в виде задачи о назна­чениях ЦЛП.

3. Пусть в предыдущем упражнении города Б, В, Г и Д обозначены через 1,2,3 и 4, а город А разделен на два, которые обозначены через 0 и 5. Пусть мар­шрут продавца книг начинается в городе 0, проходит (в некотором порядке) через города 1, 2, 3 и 4 и заканчивается в городе 5. Определим переменную v_t для города i (i = 0, 1, 5), которая удовлетворяет условиям 0 < и₍ < 5. Пусть x_tj = 1, если в маршруте город j следует за городом г, и 0 в противном случае. Покажите, что ограничения

v-v+bx_:<4., i = 0,l.....4, У= 1, 2.....5,

гарантируют исключение вчсех неполных маршрутов в решении задачи.

9.3.1. Применение метода ветвей и границ для решения задачи коммивояжера

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

9.3. Задача коммивояжера

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

Следующий пример проясняет детали применения метода ветвей и границ для решения задачи коммивояжера.

Пример 9.3.2

В следующей матрице записаны расстояния между 5 городами задачи коммивояжера.

ш=

ю

оо

9^ 2

Решение начальной задачи о назначениях (полученное с помощью TORA) следующее:

2 = 15, (х_п = x_3l = 1), (л:₂₅ = л:₅₄ = лг₄₂ = 1), все остальные переменные равны 0.

Это решение порождает два частичных цикла (1-3-1) и (1-5-4-2). Это же решение обозначено как узел 1 дерева подзадач на рис. 9.14. Полученное значение целевой функции 2=15 принимаем в качестве нижней границы длины оптимального цик­ла, проходящего через все 5 городов.

(Т)

z = 15 (1-3-1)(2-5-4-2)

z=17 (2-5-2)(1-4-3-1)

z= 16 (1-3-4-2-5-1)

z = 21 (1-4-5-2-3-1)

z=19 (1-4-2-5-3-1)

Рис. 9.14. Дерево подзадач решения задачи коммивояжера методом ветвей и границ

Глава 9. Целочисленное линейное программирование

Прямолинейный способ определения верхней границы оптимального цикла за­ключается в том, чтобы выбрать какой-либо полный цикл и подсчитать его длину. Например, полный цикл 1-2-3-4-5-1 (выбран произвольно) дает общую длину 10 + 5 + 7+ 4+ 3 = 29. (Можно получить лучшее значение верхней границы, если взять другой полный цикл. Помните, что наименьшая верхняя граница — цель поиска методом ветвей и границ.)

Вычисленные нижняя и верхняя границы показывают, что длина оптимального полного цикла лежит в интервале от 15 до 29. Подзадачи, дающее решение с дли­ной цикла больше 29, отбрасываются как "не оправдавшие надежд".

Чтобы исключить частичные циклы в задаче узла 1, надо "разбить" эти частичные циклы путем принудительного приравнивания переменных х, задающих эти цик­лы, нулю. Частичный цикл 1-3-1 можно разбить, если положить х₁₃ = 0 или х₃₁ = О (одновременно только одну переменную). Аналогично частичный цикл 2-5-4-2 можно разбить, если ввести ограничения х_2Ь = 0, х_Ь4 = 0 или x_i2 = 0. Каждое из по­добных ограничений порождает отдельную ветвь дерева подзадач (и, конечно, от­дельную подзадачу). Важно заметить, что нет необходимости разбивать все имею­щиеся частичные циклы — достаточно исключить только один частичный цикл. Причина этого в том, что введение в задачу нового ограничения автоматически влияет на значения всех переменных этой задачи, что создает "благоприятные" ус­ловия для формирования полного цикла. На основании этого аргумента обычно разбивают один частичный цикл, наименьший по количеству составляющих его дуг, поскольку это приводит к меньшему количеству новых ветвей в дереве подзадач.

Выбирая для удаления короткий цикл 1-3-1, получаем на дереве подзадач две вет­ви, определяемые условиями х₁₃ = 0 и л:₃₁ = 0, выходящие из узла 1. Новые задачи о назначениях строятся путем удаления из последней задачи переменной ветвления (т.е. х_п или л:₃₁), что уменьшает размер подзадач. Другой путь построения подзадач (который дает тот же самый результат при решении этих подзадач и который со­храняет их размер) заключается в том, чтобы назначить переменным ветвления значения расстояний, равные бесконечности. Например, в подзадаче с ограничени­ем л;₁₃ = 0 расстоянию d₁₃ присваивается значение °°.

Из двух имеющихся подзадач решим сначала задачу с условием л:₁₃ = 0 (узел 2 на рис. 9.14) — порядок решения подзадач произвольный. Получаем решение 2=17, которое формирует два частичных цикла (2-5-2) и (1-4-3-1). Эту подзадачу разбива­ем на две путем введения дополнительных ограничений x_2S = 0 и х₅₂ = 0 так же, как это сделано в задаче узла 1.

Теперь имеется три нерешенные подзадачи, которые соответствуют узлам 3, 4 и 5 на рис. 9.14. Произвольно выбираем для решения подзадачу узлаЗ. В исходных данных для этой подзадачи устанавливаем d_l3 = °° и d_2b = °°. Ее решение дает 2 = 21 с полным циклом 1-4-5-2-3-1. Поскольку получено решение с полным циклом, то ветвления в узле 3 не будет.

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

Из нерассмотренных подзадач 4 и 5 выбираем для решения подзадачу 4. Для ее ре­шения в данных исходной задачи о назначениях положим d_n = °° и d₅₂ = °°. Получа­ем решение этой подзадачи с 2 = 19 и полным циклом 1-4-2-5-3-1. Это решение предлагает новую верхнюю границу г = 19.

9.3. Задача коммивояжера

Осталась нерассмотренной только подзадача узла 5. Для ее решения в данных ис­ходной задачи о назначениях положим d₃₁ = °°. Получаем решение с г = 16 и пол­ным циклом 1-3-4-2-5-1, а также новую верхнюю границу г = 16.

Нерассмотренных подзадач не осталось. Оптимальным циклом будет цикл 1-3-4-2-5-1 с длиной в 16 миль.

Сделаем замечание. Излишне длинная последовательность решения подзадач 1—» 2-> 3-> 4—> 5, приведшая к оптимальному решению в данном примере, снова пока­зывает основной недостаток метода ветвей и границ — невозможно предсказать по­следовательность выбора подзадач, ведущую к оптимальному решению наиболее коротким путем. Например, если первой была бы решена подзадача узла 5, то это дало бы значение верхней границы, равное 16. Это автоматически отбрасывает возможные подзадачи, порождаемые в узле 2.

Конечно, существуют эвристические подходы, позволяющие помочь в "предсказа­нии" последовательности подзадач, ведущей к оптимальному решению наиболее эффективным путем. Например, после того, как определены все ветви (подзадачи), выходящие из некоторого узла дерева подзадач, первой решается та подзадача, у которой исключаемой переменной х_ц соответствует наибольшее зна­чения расстояния d_tj среди рассматриваемых подзадач. Если воспользоваться этим правилом в данном примере, то после определения подзадач узла 1 первой надо решать подзадачу 5, что приведет к оптимальному решению всего за два этапа. (Первый этап — решение подзадачи 5, второй этап — решение подзада­чи 2, которое дает худшее значение целевой функции (г = 17), чем существующая на тот момент верхняя граница, равная 16.)

УПРАЖНЕНИЯ 9.3.2

1. Решите задачу примера9.3.2, начав с удаления частичного цикла 2-5-4-2. При прохождении дерева подзадач примените следующие правила.

a) На каждом уровне дерева подзадач исследуйте подзадачи слева направо. Переходите на следующий уровень только после того, как будут рассмот­рены все подзадачи текущего уровня.

b) Исследуйте подзадачи "вертикально", начиная от нулевого узла и после­довательно проходя по ветвям, пока не будут рассмотрены все подзадачи одной последовательности ветвей.

2. Решите методом ветвей и границ задачу из упражнения 9.3.1.1.

3. Решите методом ветвей и границ задачу из упражнения 9.3.1.2.

4. Решите методом ветвей и границ задачу из упражнения 9.3.1.3.

9.3.2. Применение метода отсекающих плоскостей для решения задачи коммивояжера

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

Глава 9. Целочисленное линейное программирование

вится в соответствие непрерывная неотрицательная переменная и,. Тогда допол­нительные ограничения имеют вид

и, - ц. + nx_IJ<n - 1, i = 2, 3, n,j = 2, 3, п, j.

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

Пример 9.3.3

В следующей матрице записаны расстояния между 4 городами задачи коммивояжера.

'~ 13 21 26"

10 ~ 29 20

30 20 оо 5

Л2 30 7 о»

ш=

Данная задача коммивояжера формализуется как соответствующая задача о назна­чениях плюс следующие дополнительные ограничения, исключающие из решения частичные циклы. Все переменные x_tj двоичные, все переменные u_t неотрицательные. Задача решается как частично-целочисленная задача линейного программирования.

х Л12

*и

X Л21

*22

X Л23

X •*-24

х%\

*33

X Л34

*41

^42

*43

*44

«1

и2

и»

-1

<3

-1

<3

-1

<3

-1

<3

-1

<3

-1

<3

Оптимальное решение этой задачи (полученное с помощью TORA) следующее:

и₂ = 0, и₃ = 1, u_t = 2, л:₁₂ = л:₂₃ = x_3i = х₄₁ = 1, длина полного цикла = 59.

Это решение формирует полный цикл 1-2-3-4-1. Решение удовлетворяет всем до­полнительным ограничениям (проверьте!).

Чтобы показать, что частичные циклы не удовлетворяют дополнительным ограничени­ям, рассмотрим решение с частичными циклами (1-2-1) и (3-4-3): х₁₂ = х₂₁ = 1, х_м = x_a = 1. Теперь рассмотрим ограничения 4 и 6, представленные в выше приведенной таблице.

4x₃₄ + u₃-u₄<3,

4х₄₃-ц₃ + ц₄<3.

Подставив в эти выражения значения л:₃₄ = x_i3 = 1 и сложив их, получим невыпол­нимое неравенство 8 < 6, что говорит о невозможности частичного цикла 3-4-3.

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

Комплексные задачи

УПРАЖНЕНИЯ 9.3.3

1. Решите следующие задачи коммивояжера методом отсекающих плоскостей.

' -о 43 21 20Л

а) Задача с матрицей расстояний \d,\ =

b) Задача из упражнения 9.3.1.2.

c) Задача из упражнения 9.3.1.3.

10 оо 9 22 20 10 оо 5 42 50 27 оо

ЛИТЕРАТУРА

1. Nemhauser G., Wolsey L. Integer and Combinatorial Optimization, Wiley, New York, 1988.

2. Salkin H., Mathur K. Foundations of Integer Programming, North-Holland, New York, 1989.

3. Taha H. Integer Programming: Theory, Applications, and Computations, Academic Press, Orlando, FL, 1975.

4. Wolsey L. Integer Programming, Wiley, New York, 1998.

Литература, добавленная при переводе

1. Белоусов Е. Г. Введение в выпуклый анализ и целочисленное программирова­ние. — М.: Изд-во МГУ, 1977.

2. Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. — М.: Наука, 1968.

3. Ху Т. Целочисленное программирование и потоки в сетях. — М.: Мир, 1974.

КОМПЛЕКСНЫЕ ЗАДАЧИ

9.1. Развивающаяся компания владеет 90 акрами земли в растущей столичной зоне, где планирует построить офисные здания и торговый центр. Создан­ная собственность сдается в аренду на 7 лет и затем продается. Цена каждо­го здания оценивается в 10 раз выше суммы чистого дохода, полученного за последний год от сдачи здания в аренду. Компания оценивает, что проект будет включать торговый центр площадью в 4,5 миллиона квадратных фу­тов. Бизнес-план предусматривает строительство трех высотных офисных зданий и четырех зданий с садом.

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

Глава 9. Целочисленное линейное программирование

Потребность (тыс. кв. футов)

Год В высотных зданиях В офисах с садом

1 200
2 220
3 242
4 266
5 293
6 322
7 354
Следующая таблица содержит предложения по площадям семи зданий.
Здания с садом Площадь (кв. футы)	Высотные здания	Площадь (кв. футы)
1 60 ООО		350 000
2 60 000		450 000
3 75 000		350 000
4 75 000	—	—

Суммарный доход от ренты оценивается в 25 долл. за квадратный фут. Те­кущие затраты равны 5,75 и 9,75 долл. за квадратный фут для офисов с са­дом и высотных зданий соответственно. Затраты на строительство равны 70 и 105 долл. за квадратный фут соответственно. Считается, что и стоимость строительства, и рентный доход возрастают примерно в соответствии с про­центом инфляции, равным 4%.

Каким образом компания должна спланировать строительство семи зданий?

9.2. ⁴ В Национальной университетской ассоциации женской спортивной гимна­стики проводятся соревнования, которые включают четыре вида спортив­ных состязаний: опорный прыжок, упражнения на разновысоких брусьях и бревне, а также вольные упражнения. Каждая команда может выставить шесть участников на каждый вид. Выступления гимнасток оцениваются по десятибалльной шкале. Статистика по университетской команде дает сле­дующие показатели по отдельным гимнасткам.

Показатели гимнасток

Опорный прыжок
Брусья
Бревно
Вольные упражнения

Общее число очков команды определяется путем суммирования пяти луч­ших индивидуальных показателей для каждого вида состязаний. Участник соревнований может выступать в одном виде или во всех четырех сразу. Эти

⁴ Задача основана на материалах статьи Ellis P., Corn R. "Using Bivalent Integer Pro--ramming to Select Teams of Intercollegiate Women's Gymnastic Competition", Interfaces, Vol.14, No. 3, 1984, pp. 41-46.

Комплексные задачи

две возможности взаимно исключают друг друга. Спортсмену разрешается участвовать максимум в трех видах, и по меньшей мере четыре участника команды должны соревноваться по четырем видам. Сформулируйте задачу ЦЛП, которую можно использовать для формирования гимнастической ко­манды, и найдите ее оптимальное решение, используя программу TORA.

9.3. ⁵ В 1990 году в Соединенных Штатах на телевидении функционировало при­мерно 180 ООО центров рекламы, что позволяло предоставить работу 2 миллио­нам человек. Исследования показывают, что в 2000 году более 700 000 компа­ний будут использовать труд примерно 8 миллионов человек для рекламы своей продукции на телевидении. Вопросами первостепенной важности являются необходимое количество центров рекламы на телевидении и их размещение.

Компания ABC занимается решением поставленных вопросов. Рекламный центр может быть расположен в одном из нескольких районов, выбранных компанией, и может обслуживать (частично или полностью) одну или не­сколько географических зон. Обычно понятие географической зоны ассо­циируется с одним или несколькими телефонными кодами. Центры рекла­мы на телевидении, которыми занимается компания ABC, расположены в восьми зонах с кодами 501, 918, 316, 417, 314, 816, 502 и 606. Следующая таблица содержит информацию о кандидатах на размещение центра; зонах, которые они обслуживают; и стоимости организации центра.

Размещение центра	Коды обслуживаемых зон	Стоимость (долл.)
Даллас	501, 918, 316, 417	500 000
Атланта	314, 816, 502, 606	800 000
Луисвилл	918, 316, 417, 314, 816	400 000
Денвер	501, 502, 606	900 000
Литл-Рок	417, 314, 816, 502	300 000
Мемфис	606, 501,316, 417	450 000
Сан-Луис	816, 502, 606, 314	550 000

Клиенты всех зон имеют доступ к каждому из рекламных центров 24 часа в сутки. Стоимость связи между центрами и соответствующими зонами (в долл. за час) приведена в следующей таблице.

Из зоны с кодом

В центр
Даллас
Атланта
Луисвилл
Денвер
Литл-Рок
Мемфис
Сан-Луис

⁵ Задача базируется на работе Spenser Т., Brigandi A., Dargon D., Sheehan М. "AT&T's Telemarketing Site Selection System Offers Customer Support", Interfaces, Vol. 20, No. 1, 1990, pp. 83-96.