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


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


26

2.3. Фирма АгкТес собирает персональные компьютеры для частных клиентов. На следующие четыре квартала имеются заказы на 400, 700, 500 и 200 компьютеров соответственно. Фирма может производить больше компьютеров, чем указано в заказах, но в таком случае приходится платить 100 долл. за хранение одного компьютера в течение квартала. Увеличение производства в следующем квартале, по сравнению с предыдущим, приводит к дополнительному набору работников, что повышает себестоимость одного компьютера на 60 долл. При уменьшении производства в следующем квартале, по сравнению с предыдущим, придется прибегнуть к сокращению персонала, что также увеличивает себестоимость одного компьютера на 50 долл. Как организовать сборку компьютеров, чтобы удовлетворить все заказы?

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

Ежемесячная производительность заготовительного цеха составляет 3000 стульев, 1000 столов и 580 книжных полок (несобранных). В сборочном цехе работают 150 рабочих в две 8-часовые смены 5 дней в неделю. Среднее время сборки одной единицы продукции равно 20, 40 и 15 минут соответственно для стульев, столов и книжных полок.

Количество рабочих в сборочном цехе колеблется в зависимости от того, сколько человек в настоящее время находится в ежегодном отпуске. В мае, июне и июле планируют уйти в отпуск соответственно 20, 25 и 45 человек.

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

Продукт

Май Июнь

Июль

Остаток на конец апреля

Стул

2800 2300

3350

Стол

500 800

1400

Книжная полка

320 300

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

Продукт

Себестоимость (долл.)

Отпускная цена (долл.)

Стул

Стол

Книжная полка

Если какая-либо продукция не продана в течение того месяца, в каком она произведена, то она может быть продана в следующем месяце. Хранение одной единицы стоит 2% от стоимости этой продукции.

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



ГЛАВА 3

СИМПЛЕКС-МЕТОД

Графический способ решения задачи ЛП из главы 2 показывает, что оптимальное решение этой задачи всегда ассоциируется с угловой точкой пространства решений (в математике она также называется крайней точкой множества). Это является ключевой идеей при разработке общего алгебраического симплекс-метода для решения любой задачи линейного программирования.

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

Основное свойство симплекс-метода заключается в том, что решение задачи ЛП осуществляется итерационно. На каждой итерации алгоритм переходит к новой угловой точке, которая потенциально может улучшить значение целевой функции. Этот процесс перехода от одной угловой точки к следующей заканчивается, когда дальнейшее улучшение значений целевой функции невозможно.

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

3.1. СТАНДАРТНАЯ ФОРМА ЗАДАЧИ ЛП

Стандартная форма записи задачи ЛП предполагает выполнение следующих требований.

1. Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью.

2. Все переменные неотрицательные.

3.1.1. Преобразование неравенств в равенства

Неравенства любого типа (со знаками неравенств < или >) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных переменных - остаточных или избыточных1, которые связаны с неравенствами типа "<" и ">" соответственно.

1 Отметим, что в русской язычной математической литературе для этих типов переменных не используются какие-либо специальные названия - они известны просто как дополнительные переменные (хотя иногда их также называют балансными). В неравенствах они различаются тем, что перед остаточной переменной всегда стоит знак " плюс", а перед избыточной - " минус". - Прим. ред.



Для неравенств типа "<" в левую часть неравенства вводится неотрицательная остаточная переменная. Например, в модели компании Reddy Mikks (пример 2.1.1) ограничение на количество сырья Ml задается в виде неравенства 6х, + 4х2 < 24. Вводя новую неотрицательную переменную s,, которая показывает остаток (неспользованное количество) сырья Ml, это ограничение преобразуется в равенство

6x,+4x2 + s1 = 24, s,>0.

Неравенства типа ">" в задачах ЛП обычно устанавливают нижнюю границу чего-либо. Избыточная переменная определяет превышение значения левой части неравенства над этой границей. Так, в модели "диеты" (пример 2.2.2) неравенство х, + х2 > 800 показывает, что суточное производство пищевой добавки не должно быть меньше 800 фунтов. Математически это неравенство эквивалентно равенству

х, + х2 - S, = 800, S, > 0.

Положительное значение избыточной переменной S, показывает превышение суточного производства добавки над минимальным значением в 800 фунтов.

Важно еще раз подчеркнуть, что дополнительные переменные - остаточная s, и избыточная S, - всегда неотрицательные.

Правую часть равенства всегда можно сделать неотрицательной, умножив все равенство на -1. Кроме того, заметим, что неравенство типа "<" также преобразуется в неравенство типа ">" посредством умножения обеих частей неравенства на -1. Например, неравенство -х, + х2 < -3 эквивалентно равенству

-х, + х2 + s, = -3, s, > 0.

Теперь, умножая обе части этого равенства на -1, получим равенство с неотрицательной правой частью: х, - х2 - s, = 3.

УПРАЖНЕНИЯ 3.1.1

1. В модели компании Reddy Mikks (пример 2.2.1) рассмотрите допустимое решение х, = 3 т и х2 = 1 т. Для этого решения найдите недоиспользование сырья Ml и М2.

2. В модели "диеты" (пример 2.2.2) определите превышение над минимальным допустимым объемом производства пищевой добавки, на которую расходуется 500 фунтов кукурузной муки и 600 фунтов - соевой.

3. Дано неравенство 10х,-Зх2>-5. Покажите, что в результате преобразования, когда сначала обе части неравенства умножаются на -1, а затем неравенство преобразуется в равенство, получется такое же равенство, что и в результате преобразования, когда сначала исходное неравенство преобразуется в равенство, а затем умножается на -1.

4. Два изделия, Р1 и Р2, можно произвести на двух различных станках Ml и М2. Время изготовления любого изделия на любом станке одинаково. Производительность станка Ml составляет 200 изделий за смену, а производительность станка М2 - 250 изделий. Мастер планирует сбалансировать рабочее время таким образом, чтобы общее количество изделий, произведенных на одном станке, не превышало более чем на 5 единиц общее количество изделий, изготовленных на другом станке. Доход от одного изделия Р1 составляет 10, а от второго - 15 долл. Запишите эту задачу в стандартной форме линейного программирования.

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