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


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


128

Пример 9.1.2. Задача с постоянными затратами

Три телефонные компании предложили мне подписаться на их услуги по дальней связи в пределах Соединенных Штатов. Услуги компании MaBell стоят 16 долл. в месяц плюс 0,25 долл. за каждую минуту связи. Компания PaBell оценивает свои услуги в 25 долл. в месяц, но имеет поминутную оплату в 0,21 долл. Что касается компании BabyBell, месячная плата равна 18 долл., а стоимость минуты связи - 0,22 долл. Мои телефонные звонки на дальние расстояния в среднем составляют обычно 200 минут в месяц. Предполагается, что я не вношу помесячной платы, если не использую телефон для звонков на дальние расстояния, и что я могу распределять звонки между тремя компаниями, как мне хочется. Как я должен использовать три компании, чтобы минимизировать свой месячный телефонный счет?

Эта задача может быть легко решена без использования методов ЦЛП. Тем не менее поучительно сформулировать ее как целочисленную задачу.

Пусть

л:, - количество минут разговора (на дальние расстояния) в месяц через компанию MaBell,

х2- количество минут разговора в месяц через компанию PaBell, х3- количество минут разговора в месяц через компанию BabyBell, (/, = 1, если х, > 0, и у, = 0 при х, = 0, у2 = 1, если х2 > 0, и у2 = 0 при х2 = 0, у3 = 1, если х3 > 0, и у3 = 0 при х3 = 0.

Для обеспечения равенства ys = 1 при положительном значении переменной xj используем ограничение х Myjt j - 1, 2, 3, где М- достаточно большое число, которое не должно ограничивать величину х. Так как звонки на дальние расстояния занимают около 200 минут в месяц, т.е. х1 < 200 для всех j, поэтому достаточно положить М= 200.

Теперь можно сформулировать следующую задачу.

Минимизировать г = 0,25л:, + 0,21х2 + 0,22х3 + 16у, + 2Ьу2 + 18у3 при ограничениях

х, + х2 + х3 = 200,

<200г/„

x2<200j/2, х3<200у3,

гл. у 2 г/3 = 0или 1-

Формулировка задачи показывает, что помесячная /-я оплата за пользование телефоном является частью целевой функции г лишь при условии У,= , которое по определению может выполняться лишь тогда, когда х} > 0. Если в оптимальном решении будет Xj = 0, то минимума функции z (с учетом положительности коэффициента при у} можно достичь только при равенстве нулю yjt что и требуется.

Оптимальным решением данной задачи (получено с помощью TORA, файл Ch9ToraFixedChargeEx9-l-2.txt) является х3 = 200, у3 = 1, все остальные переменные равны нулю. Это значит, что копания BabyBell должна быть выбрана для



услуг по дальней связи. Следует подчеркнуть, что информация, которую несет значение переменной j/3 = 1, является избыточной, так как такой же результат следует из хг > 0 (= 200). В самом деле, основной причиной использования переменных «/,, у2 и у3 является лишь учет месячной платы за телефон. В сущности, только эти двоичные переменные преобразуют исходную нелинейную задачу в частично-целочисленную, поддающуюся аналитическому решению.

Изложенная концепция "твердого гонорара" является типичной для задачи, известной в литературе как задача с постоянными затратами.

УПРАЖНЕНИЯ 9.1.2

1. Компания планирует производство некоторой продукции на трех станках, которой должно быть изготовлено не менее 2000 единиц. Минимальная производительность любого станка равна 500 единиц. Следующая таблица содержит необходимую информацию для рассматриваемой задачи.

Станок

Расходы на переналадку

Затрать! на производство единицы продукции

Производительность (в единицах продукции)

1200

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

2. Нефтедобывающая компания изучает вопрос о бурении четырех нефтяных скважин на двух нефтеносных участках. Издержки подготовки к бурению на каждом участке и затраты на бурение скважины ; на участке i (i=l, 2; j=l, 2, 3, 4) приведены в следующей таблице.

Затраты на бурение скважины (млн. долл.)

Издержки подготовки

Участок

12 3 4

к бурению (млн. долл.)

2 18 5

4 6 3 1

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

3. Рассматриваются три промышленных участка для размещения обрабатывающих заводов, которые снабжают своей продукцией трех потребителей. Данные об объемах производства продукции, объемах потребления и себестоимости (в долл.) перевозки продукции от заводов к потребителям содержатся в следующей таблице.

1 2 3 Объем производства

1800

1400

1300

Спрос 1200 1700 1600



В дополнение к транспортным, существуют еще фиксированные затраты в объеме 10 ООО, 15 ООО и 12 ООО долл., связанные с 1, 2 и 3 заводом соответственно. Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение, используя программу TORA.

4. Повторите упражнение 3, предполагая, что спрос потребителей 2 и 3 уменьшился до 800 единиц.

Пример 9.1.3. Задача о покрытии

Для обеспечения безопасности студентов отдел безопасности американского университета устанавливает телефоны экстренного вызова на территории студенческого городка. Отделу желательно установить минимальное количество телефонов таким образом, чтобы на каждой из основных улиц этого городка был расположен по крайней мере один телефон. На рис. 9.1 представлены основные улицы (от А до К) студенческого городка.

Улица А

ев Я К

Улица В

®

Улица Е

ев Я Я

Улица С

ев Я К

Улица D

©

Рис. 9.1. Схема улиц студенческого городка

Логично расположить телефоны на пересечениях улиц так, чтобы каждый телефон мог обслуживать по меньшей мере две улицы. Из рис. 9.1 видно, что данное расположение улиц требует не более восьми телефонов.

Определим, что переменная х} равна 1, если телефон расположен на перекрестке / (j =1,2, 8), и 0 в противном случае.

Условия задачи требуют установки по меньшей мере одного телефона на каждой из 11 улиц (от А до К). Поэтому задачу можно сформулировать следующим образом.

Минимизировать г = хг + х2 + х3 + xt + xs + х6 + х7 + xs

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

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