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


[Старт] [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]


129

л;, + х2 > 1 (улица А),

х2 + х3 > 1 (улица В),

xt + x6 > 1 (улица С),

х7 + хе>1 (улица D),

х6 + х7 > 1 (улица £),

x2 + л;6 > 1 (улица F),

хг + хе > 1 (улица G),

x4 + л;7 > 1 (улица Н),

х2 + xt > 1 (улица /),

xs + xs > 1 (улица J),

д:3 + х& > 1 (улица ЛГ),

xt = 0 или 1,= 1, 2,8.

В соответствии с оптимальным решением задачи (полученным с помощью программы TORA, файл Ch9ToraSetCoverEx9-l-3.txt) необходимо установить телефоны на перекрестках 1, 2, 5 и 7.

Рассмотренная выше модель является типичным представителем общего класса задач, именуемых задачами о покрытии. В этой модели все переменные являются двоичными. Все коэффициенты левой части каждого ограничения равны 0 или 1, а правая часть ограничений имеет вид ">1". Целевая функция всегда имеет вид с1х1 + сгх2 + ...+спхп, где с;>0 для всех j = 1, 2 п, и подлежит минимизации. В рассмотренном примере с; = 1 для всех Однако если величина с; будет равна стоимости установки телефона на ;-м перекрестке, то эти коэффициенты могут принимать значения, отличные от 1.

УПРАЖНЕНИЯ 9.1.3

1. Компания ABC занимается доставкой грузов пяти потребителям. Можно выбрать следующие маршруты перевозки грузов.

Маршрут

Потребители

1, 2, 3, 4

4, 3, 5

1, 2, 5

2, 3, 5

1, 4, 2

1, 3, 5

Эти маршруты определяются грузоподъемностью автомобиля, доставляющего грузы. Например, на маршруте 1 автомобиль имеет грузоподъемность, достаточную для доставки грузов лишь потребителям 1, 2, 3 и 4. Следующая таблица содержит расстояния (в милях) между терминалом компании ABC и потребителями.



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

2. Американский университет формирует комитет по рассмотрению жалоб студентов. В соответствии с указаниями, полученными из администрации, в эту комиссию необходимо включить по крайней мере одну женщину, одного мужчину, одного студента, одного администратора и одного преподавателя. Выдвинуты десять кандидатур (обозначенных для удобства буквами от а до ;). Принадлежность этих кандидатур к различным категориям отражена в следующей таблице.

Категория

Кандидатуры

Женщины

а, о, с, d, в

Мужчины

f, 9, h, i, j

Студенты

a, b, c, j

Администраторы

e, f

Преподаватели

d, g, h, i

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

3. Округ Вашингтон определил шесть городов, которые нуждаются в службе скорой помощи. Станции скорой помощи могут быть расположены в некоторых или во всех шести городах. Однако в силу территориальной близости некоторых городов одна станция может обслуживать более одного населенного пункта. Единственным условием является время поездки; оно не должно превышать 15 минут. Приведенная ниже таблица содержит время поездки в минутах между шестью городами.



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

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

I I I

-I г

I Т т

Рис. 9.2. План музея

Пример 9.1.4. Ограничения типа "или-или"

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

Заказ

Время выполнения заказа (дни)

Срок сдачи заказа (дни)

Штраф за задержку заказа (долл./день)

Требуется определить последовательность выполнения заказов, которая минимизирует штраф за задержку сдачи заказов.

Определим переменную х/ как дату завершения заказа /, измеряемую в днях от начальной даты. Задача имеет два типа ограничений: 1) ограничения, которые гарантируют, что никакие два заказа не выполняются одновременно; 2) ограничения по срокам сдачи заказов. Сначала рассмотрим первый тип ограничений.

Два заказа i и /, время выполнения которых pt и pjt не будут выполняться одновременно, если

или xt > Xj + Pj, или х} > xt + pt,

в зависимости от того, будет ли заказ i предшествовать выполнению заказа или наоборот.

[Старт] [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]