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

и, - ц. + nxIJ<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 .

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

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

и2 = 0, и3 = 1, ut = 2, х12 = х23 = х34 = х41 = 1, длина полного цикла = 59.

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

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

4x34 + u3-u4<3,

4x43-u3 + u4<3.

Подставив в эти выражения значения х34 = х 43 = 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 лет, вычисленные на основе соответствующего изучения рынка, показаны в следующей таблице.

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

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

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

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

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

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

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

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