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


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


6

Расход сырья (в тоннах) на тонну краски

для наружных работ

для внутренних работ

Максимально возможный ежедневный расход сырья

Сырье М1 Сырье М2

Доход (в тыс. долл.) на тонну краски

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

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

1. Переменные, которые следует определить.

2. Целевая функция, подлежащая оптимизации.

3. Ограничения, которым должны удовлетворять переменные.

Определение переменных - первый шаг в создании модели. После определения переменных построение ограничений и целевой функции обычно не вызывает трудностей.

В нашем примере необходимо определить ежедневные объемы производства краски для внутренних и наружных работ. Обозначим эти объемы как переменные модели:

х1 - ежедневный объем производства краски для наружных работ;

х2 - ежедневный объем производства краски для внутренних работ.

Используя эти переменные, далее строим целевую функцию. Логично предположить, что целевая функция, как суммарный ежедневный доход, должна возрастать при увеличении ежедневных объемов производства красок. Обозначим эту функцию через z (она измеряется в тысячах долларов) и положим, что г = 5.v, + 4.v2. В соответствии с целями компании получаем задачу:

Итак, остался не определенным последний элемент модели - условия (ограничения), которые должны учитывать возможности ежедневного потребления сырья и ограниченность спроса на готовую продукцию. Другими словами, ограничения на сырье можно записать следующим образом.

максимизировать z = 5хх + 4х2.

Используемый объем сырья для производства < обоих видов краски ,

ежедневный расход сырья

Максимально возможный

Из таблицы с данными имеем следующее.

Используемый объем сырья Ml = 6jc, + 4х2 (т) Используемый объем сырья М2 = 1дг, + 2х2 (т)



2.1. Модели ЛП с двумя переменными

Поскольку ежедневный расход сырья Ml и М2 ограничен соответственно 24 и 6 тоннами, получаем следующие ограничения.

6х, + 4х2 < 24 (сырье Ml)

1х, + 2х2 < 6 (сырье М2)

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

Еще одно неявное ограничение состоит в том, что переменные х, и х2 должны быть неотрицательными. Таким образом, к сформулированным выше ограничениям необходимо добавить условие неотрицательности переменных: х, > 0, х2 > 0.

Окончательно задача будет записана следующим образом:

максимизировать z = 5х, + 4дг2 при выполнении ограничений

6х, + 4х2 < 24, xt + 2x2<6,

- Xj +х2 < 1,

х2<2,

х,>0,х2>0.

Любое решение, удовлетворяющее ограничениям модели, является допустимым. Например, решение х, = 3 и х2 = 1 будет допустимым, так как не нарушает ни одного ограничения, включая условие неотрицательности. Чтобы удостовериться в этом, подставьте значения х, = 3 и х2 = 1 в левые части неравенств системы ограничений и убедитесь, что ни одно неравенство не нарушается. Значение целевой функции при этом решении будет равно z = 5x3 4- 4x1 = 19 (тыс. долл.).

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

В предыдущем примере целевая функция и все ограничения были линейными. Свойство линейности функций предполагает следующее.

1. Значения левых частей неравенств ограничений и значение целевой функции прямо пропорциональны значениям переменных.

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



УПРАЖНЕНИЯ 2.1

1. В модели для компании Reddy Mikks сформулируйте новые ограничения, исходя из следующих условий.

a) Ежедневный объем производства краски для внутренних работ должен не менее чем на одну тонну превышать ежедневный объем производства краски для наружных работ.

b) Ежедневное потребление сырья М2 должно быть не менее 3 т и не более 6 т.

c) Ежедневный объем производства краски для внутренних работ не может быть меньше ежедневного объема производства краски для наружных работ.

d) Минимальный ежедневный общий объем производства краски обоих типов составляет 3 т.

e) Отношение ежедневного объема производства краски для внутренних работ к общему объему производства краски обоих типов не должно превышать 0,5.

2. Для компании Reddy Mikks найдите оптимальное допустимое решение модели среди следующих решений.

= 1,л;2 = 4;

= 2, х2 = 2;

= 3, х2 = 1,1

= 2, х8- 1;

= 2,х2 = -1

3. Для допустимого решения л:, = 2, х2 = 2 в модели компании Reddy Mikks определите:

a) объем используемого сырья Ml;

b) объем используемого сырья М2.

4. Предположим, что компания Reddy Mikks продает свою краску для наружных работ оптовому покупателю со скидкой, зависящей от объема поставок. В результате доход на тонну продукции составляет 5000 долл., если оптовик покупает не более 2 т краски в день, и 4500 долл. - в противном случае. Можно ли для этой ситуации построить модель линейного программирования?

2.2. ГРАФИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Графический способ решения задачи ЛП состоит из двух этапов.

1. Построение пространства допустимых решений, удовлетворяющих всем ограничениям модели.

2. Поиск оптимального решения среди всех точек пространства допустимых решений.

Далее графический способ решения описан в двух вариантах: для максимизации и минимизации целевой функции.

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