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


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


130

Поскольку все математические модели имеют дело лишь с совместными ограничениями, мы преобразуем ограничения типа или-или, введя дополнительную двоичную переменную

fl, если заказ i предшествует заказу j, уи=\п

(0, если заказ j предшествует заказу i.

При достаточно большом М ограничение типа или-или преобразуется в следующие два совместных ограничения.

My,j + [x,-xt)>Pj и M{\-yil) + {xl-xi)>pi.

Указанное преобразование гарантирует, что лишь одно из двух ограничений может быть активным в любой момент времени. Если ytj = 0, первое ограничение является активным, а второе - избыточным (так как его левая часть будет содержать величину М, которая намного больше р). Если у, =1, первое ограничение является избыточным, а второе - активным.

Рассмотрим теперь ограничения по срокам сдачи заказов. При заданной дате сдачи заказа введем в рассмотрение неограниченную по знаку переменную Sj. Тогда соответствующее ограничение примет вид

*,+Р,+ ,-<*,

Если Sj > 0, то заказ сдается в срок, если же sy < 0, получаем убытки, связанные с задержкой сдачи заказа. Используя стандартную замену

приводим ограничение к виду

xj + s)-s-l=dj-pj. Штраф за задержку сдачи заказа пропорционален s].

Математическая модель рассматриваемой задачи принимает следующий вид. Минимизировать z = 19л," + 12л; +34

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

х,-х2 + М</12>20, -ж, + х2- Му12 > 5 - М, х,-х3 + Му,3>15, -ж, + ж3 - Му13 > 5 - М, х2 - х3 + Му23> 15, -х2 + х3-М</23>20-М, xt + sl - s~ =25-5,

x2 + sl -s2 =22-20,

x3 + sl - sl = 35-15,

x,, x2, x3, sl, sj", sl, sl, sl, sl >0,

Ух2> У XV </23 = 0иЛи1-



Целочисленные переменные yl2, у13 и у23 введены для преобразования ограничений типа или-или в совместные ограничения. Конечная задача является частично-целочисленной задачей линейного программирования.

Для решения задачи выберем М = 100 - число, которое больше суммы времени изготовления всех трех заказов.

Оптимальным решением (полученным с помощью программы TORA, файл Ch9ToraEitherOrEx9-l-4.txt) является хг = 20, х2 = 0 и х3 = 25. Следовательно, оптимальной последовательностью выполнения заказов будет 2 -> 1 -> 3. В соответствии с оптимальным решением заказ 2 выполняется за время 0 + 5 = 5, заказ 1 - за время 20 + 5 = 25 и заказ 3 - за 25 + 15 = 40 дней. В результате выполнение заказа 3 задержано на 40 - 35 = 5 дней, что приводит к штрафу в размере 5 х 34 = 170 долл.

УПРАЖНЕНИЯ 9.1.4

1. Игральная доска состоит из девяти равных квадратов, расположенных 3x3. Требуется заполнить каждый квадрат числом из интервала от 1 до 9 таким образом, чтобы сумма чисел каждой строки, каждого столбца и каждой диагонали была равна 15. Определите числа в каждом квадрате для следующих случаев.

a) Числа в каждой строке и каждом столбце различны.

b) Числа во всех квадратах различны.

Запишите сформулированную задачу в виде задачи ЦЛП с ограничениями и решите ее с помощью программы TORA.

2. Станок используется для производства двух взаимозаменяемых видов продукции. Производительность станка позволяет за день изготовить не более 20 единиц продукции первого вида и 10 единиц второго вида. Существует альтернативная наладка станка, позволяющая ежедневно изготовлять не более 12 единиц продукции вида 1 и 22 единицы вида 2. Анализ рынка показывает, что максимальный суммарный спрос на два вида продукции составляет 35 единиц ежедневно. Предположим, что прибыль от производства единицы продукции первого и второго вида составляет 10 и 12 долл. соответственно. Какая из двух возможных настроек станка должна быть выбрана? Сформулируйте задачу в виде задачи ЦЛП и решите ее с помощью программы TORA. (Примечание. Сформулированная двухмерная задача может быть решена путем перебора возможных решений после графического построения пространства допустимых решений. Этого нельзя сделать в л-мерной задаче.)

3. Некая компания производит три вида продукции. Ежедневные временные затраты и потребности сырья, необходимые на изготовление одной единицы продукции, приведены в следующей таблице.

Продукция Необходимое время (час./ед.) Необходимое сырье (фунты/ед.)

1 3 4

2 4 3

3 5 6

Доходы от производства единицы каждого вида продукции равны 25, 30 и 22 долл. соответственно. Компания имеет возможность организовать выпуск



этой продукции в двух цехах своего производства. Цехи отличаются главным образом ресурсом рабочего времени и сырья, как показывает следующая таблица.

Ресурс рабочего времени (часов в рабочий день)

Ресурс сырья (фунты в день)

Сформулируйте задачу в виде задачи частично-целочисленного линейного программирования и используйте программу TORA для оптимального размещения производства по цехам.

4. Рассмотрите задачу планирования производственной линии, связанной с изготовлением двух различных изделий на одном станке. Последовательность выполнения необходимых для этого восьми операций изображена на рис. 9.3. Пусть Pj- время выполнения j-й операции 0 = 1, 2, п). Сроки сдачи изделий типа 1 и 2, которые определяются на основе некоторого исходного момента, равны dl и d2 соответственно. Предполагается, что любая выполняемая на станке операция должна быть завершена до начала другой операции. Сформулируйте задачу в виде задачи частично-целочисленного линейного программирования.

Изделие 1 Изделие 2

Рис. 9.3. Отношения предшествования операций для упражнения 4

5. Компания владеет фабрикой, которая производит изделия трех типов. Необходимые трудовые затраты и потребности сырья для производства одной единицы каждого из трех типов изделий приведены в следующей таблице.

Тип изделия

Необходимое время (час./ед.)

Необходимое сырье (фунты/ед.)

Наличный дневной объем

Доходы от производства единицы каждого из трех типов изделий равны 25, 30 и 45 долл. соответственно. Если будет производиться изделие типа 3, то его ежедневный объем производства должен быть не менее 5 единиц. Сформулируйте задачу в виде задачи частично-целочисленного линейного программирования и используйте программу TORA, чтобы найти оптимальное решение.

6. Опишите невыпуклые заштрихованные области допустимых решений, которые изображены на рис. 9.4, в виде набора одновременно выполняющихся

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