Комплексные задачи
УПРАЖНЕНИЯ 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 лет, вычисленные на основе соответствующего изучения рынка, показаны в следующей таблице.
Потребность (тыс. кв. футов)
Год В высотных зданиях В офисах с садом
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. 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.
Комплексные задачи
две возможности взаимно исключают друг друга. Спортсмену разрешается участвовать максимум в трех видах, и по меньшей мере четыре участника команды должны соревноваться по четырем видам. Сформулируйте задачу ЦЛП, которую можно использовать для формирования гимнастической команды, и найдите ее оптимальное решение, используя программу TORA.
9.3. 5 В 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 часа в сутки. Стоимость связи между центрами и соответствующими зонами (в долл. за час) приведена в следующей таблице.
Из зоны с кодом
В центр | | | | | | | | |
Даллас | | | | | | | | |
Атланта | | | | | | | | |
Луисвилл | | | | | | | | |
Денвер | | | | | | | | |
Литл-Рок | | | | | | | | |
Мемфис | | | | | | | | |
Сан-Луис | | | | | | | | |
5 Задача базируется на работе Spenser Т., Brigandi A., Dargon D., Sheehan М. "AT&Ts Telemarketing Site Selection System Offers Customer Support", Interfaces, Vol. 20, No. 1, 1990, pp. 83-96.