назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [ 140 ] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


140

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

УПРАЖНЕНИЯ 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.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [ 140 ] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]