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


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


40

Пример 3.5.4. Отсутствие допустимых решений

Рассмотрим следующую задачу.

Максимизировать z = За-, + 2а2

при выполнении условий

2а, + а2<2, За, + 4х3> 12, а„ а2>0.

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

Итерация

Базис

Решение

Начальная

-3-ЗМ

-2-AM

-12М

Вводится хг

Исключается хз

Первая

1 +5М

2 + 4М

4-4М

(псевдооптимум)

Данные из этой таблицы показывают, что в точке оптимума искусственная переменная R имеет положительное значение (= 4), что свидетельствует об отсутствии допустимого решения. На рис. 3.13 графически представлена ситуация данной задачи. Алгоритм симплекс-метода, допуская положительные значения искусственной переменной, по существу, превращает неравенство За, + 4х3>12 в За, + 4а3 < 12. (Объясните, почему так происходит.) В результате получаем то, что можно назвать псевдооптимальным решением.

Рис. 3.13. Отсутствие допустимых решений в примере 3.5.4



Литература

УПРАЖНЕНИЯ 3.5.4

1. Компания производит изделия трех типов Tl, Т2 и ТЗ. На их изготовление расходуется материал Ml и М2 согласно данным следующей таблицы.

Расход материалов на единицу изделия

Материал

Т1 Т2

3 5

5 3

Ежедневно можно использовать не более 1000 единиц материала Ml и 1200 единиц материала М2. Отдел маркетинга настаивает, чтобы суммарное ежедневное производство изделий составляло не менее 500 единиц. Может ли производство удовлетворить это требование? Если ответ отрицательный, помогите компании составить наиболее выгодную структуру производства изделий. 2. Дана следующая задача ЛП.

Максимизировать z = Зхг + 2х2 + Зх3

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

2хх + х2 + х3<2, Зх, + 4х2 + 2х3 > 8, xv х2, х3>0.

Используя М-метод в программе TORA, покажите, что оптимальное решение этой задачи содержит искусственную базисную переменную, значение этой переменной равно нулю. Имеет ли задача допустимое оптимальное решение?

ЛИТЕРАТУРА

1. Bazaraa М., Jarvis J., Sherali М. Linear Programming and Network Flows, 2nd ed., Wiley, New York, 1990.

2. Dantzig G. Linear Programming and Extensions, Princeton University Press, Princeton, N.J., 1963. (Русский перевод: Данциг Дж. Линейное программирование, его применение и обобщение. - М.: Прогресс, 1966.)

3. Dantzig G., Thapa М. Linear Programming 1: Introdution, Springer, New York, 1997.

4. Nering E., Tucker A. Linear Programming and Related Problems, Academic Press, Boston, 1992.

5. Schrage L. Optimization Modeling with LINGO, LINGO Systems, Inc., Chicago, 1999.

6. Taha H. Linear Programming, Chapter II-1 in Handbook of Operations Research, J. Moder and S. Elmaghraby (eds.), Van Nostrand Reinhold, New York, 1978. (Русский перевод: Исследование операций: в 2-х томах. Под ред. Дж. Моудера, С. Элмаграби. - М.: Мир, 1981.)



Литература, добавленная при переводе

1. Ашманов С. А. Линейное программирование. - М.: Наука, 1981.

2. Гольштейн Е. Г., Юдин Д. Б. Линейное программирование: Теория, методы и приложения. - М.: Наука, 1969.

3. Мур Дж., Уэдерфорд Л. Экономическое моделирование в Microsoft Excel. - М.: Издательский дом "Вильяме", 2004.

КОМПЛЕКСНЫЕ ЗАДАЧИ

3.1. Небольшой консервный завод производит пять типов консервов на основе трех видов свежих фруктов. Завод имеет два производственных цеха, которые при необходимости могут наращивать выпуск продукции. В настоящее время производственные цеха работают в одну смену, но без труда могут перейти на двух- или трехсменную работу. Реальным ограничением наращивания выпуска продукции является только объем поставляемых на переработку свежих фруктов. Поскольку объемы холодильных камер ограничены, желательно, чтобы все фрукты перерабатывались в течение рабочего дня.

Молодой аналитик, специалист по исследованию операций, горит желанием увеличить уровень производства этого завода. После анализа производственной ситуации он сформулировал задачу линейного программирования. Задача включает пять переменных (для пяти видов продукции) и три ограничения (для трех видов сырья). Теория ЛП говорит о том, что в задаче с пятью переменными и тремя ограничениями оптимальное решение не может содержать более трех базисных переменных. Следовательно, оптимальное решение предполагает производство не более трех видов продукции. "Ага, - подумал

аналитик, - производство этой компании явно не оптимально."

Он добился встречи с менеджером по производству для обсуждения построенной модели ЛП. Менеджер, подробно ознакомившись с задачей, нашел, что модель адекватно отображает сложившуюся производственную ситуацию.

Аналитик объяснил, что согласно теории ЛП, поскольку задача имеет только три ограничения, оптимальный план производства не должен содержать более трех видов продукции, и поэтому завод должен прекратить выпуск двух бесприбыльных видов продукции. Менеджер, внимательно выслушав аналитика, сказал, что его компания не может прекратить выпуск двух видов продукции, так как это не выгодно предприятию. Но, чтобы согласовать теорию и практику, он предложил добавить в модель еще два ограничения, тогда будет пять ограничений, и в этом случае оптимальное решение должно разрешить производство всех пяти видов продукции.

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

Как разрешить этот "парадокс"?

3.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]