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


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


127

Предполагается, что каждый утвержденный проект Ьудет реализован за трехлетний период. Необходимо определить совокупность проектов, которой соответствует максимум суммарной прибыли.

Задача сводится к решению типа "да-нет" относительно каждого проекта. Определим двоичные переменные хг.

Г1, если проект j утвержден, Xj =<

(О, если проект j не утвержден. Задача ЦЛП будет записана следующим образом.

Максимизировать г = 20л:, + 40х2 + 20х3 + 15х4 + 30х5 при ограничениях

5*, + 4х2 + Зх3 + 7xt + 8х5 < 25,

хх + 7х2 + 9х3 + 4xt + 6xs < 25,

8х, + 10*2 + 2х3 + xt + 10хй < 25,

хх, х2, х3, xt, х5 = 0 или 1.

Оптимальным целочисленным решением (полученным с помощью программы TORA1) является хх = х2 = х3 = xt = 1, xs = 0 с z = 95 млн. долл. Это решение означает, что необходимо выбрать для финансирования все проекты, кроме пятого.

Интересно сравнить решение данной задачи ЦЛП с решением "обычной" задачи ЛП с теми же ограничениями, но без условия целочисленности переменных. Задача линейного программирования получается в результате замены условия х = О или 1 на ограничение 0<х;< 1 для всех у. Эта задача имеет решение *, = 0,5789, х2= х3= х( = 1, х5 = 0,7368 и 2 =108,68 млн. долл. Такое решение с точки зрения целочисленной задачи лишено смысла, так как две переменные принимают дробное значение. Можно было бы попытаться округлить полученный результат, что привело бы к хх = xs = 1. Полученное при этом решение является недопустимым, так как нарушаются ограничения задачи. Более существенным в этой ситуации является то, что округление применять нельзя, так как х} представляет решение типа "да-нет", для которого дробные значения лишены смысла.

УПРАЖНЕНИЯ 9.1.12

1. В модели распределения капиталовложений из примера 9.1.1 предположим, что проект 5 должен быть обязательно выбран, если выбирается либо проект 1, либо 3. Измените математическую модель, включив в нее новое ограничение, и решите полученную задачу с помощью программы TORA.

2. Рассмотрите задачу о загрузке самолета грузами пяти типов. Вес и»,, объем и,, а также стоимость г, единицы груза каждого типа приведены в следующей таблице.

1 Для решения задач ЦЛП в программе TORA из основного меню выберите команду Integer Programming (Целочисленное программирование). После ввода исходных данных (файл Ch9ToraCapitalBudgetEx9-l-l.txt) перейдите в выходное окно и для получения оптимального решения выберите Automated В&В (Автоматические вычисления методом ветвей и границ).

2 Задачи 3-6 в адаптированном виде заимствованы из книги Malba Tahan. El Hombre Que Calculaba, Editorial Limusa, Mexico City, 1994, pp. 39-182.



Груз / Вес единицы груза, Объем единицы груза, Стоимость единицы груза,

iv, (тонны) V/(куб. ярд) Г/ (100 долл.)

15 1 4

2 8 8 7

3 3 6 6

4 2 5 5

5 7 4 4

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

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

4. Эксцентричный шейх оставил завещание относительно распределения стада верблюдов между тремя детьми: Тарик получает не менее половины стада, Шариф - не менее одной трети, а Маиса - по меньшей мере одну девятую часть. Остаток завещался благотворительной организации. В завещании не упоминался размер стада, говорилось лишь, что количество верблюдов - число нечетное и благотворительная организация получает в точности одного верблюда. Сколько верблюдов оставил шейх и сколько получил каждый из его детей?

5. Супружеская пара фермеров посылает трех своих сыновей на базар продать 90 яблок, чтобы обучить их числам и обращению с деньгами. Самый старший Джим получил для продажи 50 яблок, Билл (средний) - 30 и самый младший Джон- лишь 10. Родители поставили пять условий. 1. Цена яблок должна быть равна либо 1 долл. за 7 яблок, либо 3 долл. за 1 яблоко. 2. Каждый ребенок может использовать один или оба варианта цен. 3. Все дети должны вернуться с одинаковой суммой денег. 4. Каждый ребенок приносит домой сумму, которая является четным числом (без центов). 5. Сумма денег, полученная каждым из детей, должна быть максимальной при сформулированных условиях. Считается, что дети могут продать все яблоки, которые они имеют. Как дети могут выполнить требования своих родителей?

6. Капитан торгового судна, который хотел наградить трех членов команды за их героические усилия по спасению груза корабля во время неожиданного шторма, взял некоторую сумму денег у казначея и отдал приказ старшему помощнику распределить их поровну между тремя матросами после того, как корабль достигнет берега. Однажды ночью один из матросов решил взять свою (справедливую) третью часть заранее. После деления денег на три равные части осталась одна монета, которую матрос решил оставить себе (в дополнение к третьей части денег). На следующую ночь второй мат-



рос решил осуществить такой же план и, повторив деление на три части оставшейся суммы, присвоил себе еще и монету, которая осталась после деления. На третью ночь третий матрос взял третью часть того, что осталось, и одну дополнительную монету, которая осталась после деления. Когда корабль достиг берега, старший помощник капитана разделил остаток денег поровну между тремя матросами и снова осталась одна монета. Старший помощник отложил эту монету в сторону и вручил матросам предназначенные им равные части. Сколько денег было в самом начале? Сформулируйте задачу в виде задачи ЦЛП и найдите оптимальное решение, используя программу TORA. (Совет. Задача имеет бесконечно много целочисленных решений. Предположите для удобства, что следует определить минимальную сумму денег, которая удовлетворяет условиям задачи. Увеличивая затем полученное решение на 1, рассмотрите его как нижнюю границу и получите новое минимальное решение. Продолжая таким образом, можно найти формулу для общего решения.)

7. Имеются следующие слова, состоящие из трех букв: AFT, FAR, TVA, ADV, JOE, FIN, OSF и KEN. Предположим, что буквам алфавита приписаны числа (метки), начиная с А = 1 и заканчивая Z = 26. Каждое слово помечается числом, равным сумме числовых меток составляющих его трех букв. Например, слово AFT имеет метку 1 + 6 + 20 = 27. Необходимо выбрать пять из заданных восьми слов таким образом, чтобы получить максимальную суммарную метку. Вместе с тем выбранные пять слов должны удовлетворять следующему условию: (сумма меток первых букв) < (сумма меток вторых букв) < (сумма меток третьих букв).

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

8. Фирма, специализирующаяся на грамзаписи песен, заключила договор с восходящей звездой эстрады на запись восьми песен. Продолжительность песен равна 8, 3, 5, 5, 9, 6, 7 и 12 минут соответственно. Фирма планирует использовать для записи двусторонние кассеты. Каждая сторона имеет длительность звучания 30 минут. Фирма намерена распределить песни на две стороны кассеты сбалансированным образом. Это значит, что продолжительность звучания песен на каждой стороне кассеты должна быть примерно одинаковой (насколько это возможно). Сформулируйте задачу в виде задачи ЦЛП и найдите оптимальное решение.

9. Рассмотрите задачу из предыдущего упражнения, предположив, что характер мелодий песен диктует условия, согласно которым третья и четвертая песни не могут быть записаны на одной стороне кассеты. Сформулируйте задачу в виде задачи ЦЛП. Возможно ли использование 25-минутной (для каждой стороны) кассеты для записи 8 песен? Если нет, используйте модель ЦЛП, чтобы определить минимальную емкость кассеты для записи.

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