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


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


48

a) Сформулируйте задачу линейного программирования и с помощью программы TORA найдите ее оптимальное решение.

b) Основываясь на двойственных ценах, приведенных программой TORA, определите возможное увеличение ежедневного фонда времени по каждой технологической операции.

c) Выгодно ли компании выполнение требования заданного минимального уровня производства? Обоснуйте ответ, основываясь на величинах двойственных цен.

d) Возможно ли увеличение на 10% временного фонда операции пайки с сохранением величины ее вклада в суммарный доход, определяемый текущей двойственной ценой?

3. Компания производит кожаные чехлы и сумки. На производство одного чехла требуется 8 м2 кожи и 12 часов рабочего времени, на производство сумки - 2 м2 кожи и 5 часов рабочего времени. Текущие еженедельные ресурсы производства ограничены 1200 м2 кожи и 1850 часами рабочего времени. Компания продает чехлы и сумки по цене 350 и 120 долл. соответственно. Определите для этой компании схему производства, максимизирующую чистую прибыль. Допустим, компания желает расширить свое производство. Какова максимальная цена, по которой компании имеет смысл закупать дополнительную кожу? А какова допустимая максимальная цена дополнительных трудовых ресурсов?

4.3.2. Экономическая интерпретация ограничений двойственной задачи

Для интерпретации ограничений двойственной задачи используем формулу 2 из раздела 4.2.4. В соответствии с этим соотношением на любой итерации решения прямой задачи справедливо равенство

коэффициент при xt в z-строке = а,ЛУ, - с, •

Условие оптимальности симплекс-метода в задаче максимизации говорит о том, что у-й вид деятельности (переменная дг), не представленный в текущем базисном решении, можно ввести в базис для увеличения дохода только тогда, когда коэффициент при Xj в z-строке (равный ".аУ; -су) будет неотрицательным. В рамках предлагаемой экономической интерпретации это означает, что у-й вид деятельности должен быть представлен в базисном решении, если выполняется следующее неравенство.

Стоимость всех ресурсов, используемых для производства единицы продукции j-то вида деятельности

Доход от реализации единицы продукции 7-го вида деятельности

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

Приведем стандартные определения, используемые в литературе по линейному

программированию. Введем обозначение z, = Х™1я,уУ,- Величина z представляет суммарную стоимость ресурсов, используемых на производство единицы продукции j-ro вида деятельности. Величина zf - с. равна коэффициенту при xj в z-строке симплекс-таблицы и часто называется приведенной стоимостью (приведенными издержками)



у-го вида деятельности. В некоторых случаях разности z - с\ = Га<,Х - cf используют-

ся непосредственно для вычисления коэффициентов в z-строке симплекс-таблицы (вместо метода Гаусса-Жордана). Такие вычисления используются в модифицированном симплекс-методе (этот метод описан в главе 7).

Пример 4.3.2

Фабрика игрушек TOYCO собирает три вида игрушек: модели поездов, грузовиков и легковых автомобилей; при сборке каждого вида используется три типа операций. Ежедневный фонд рабочего времени на каждую операцию ограничен предельными величинами 430, 460 и 420 минут. Доход на одну игрушку каждого вида составляет соответственно 3, 2 и 5 долл. На каждой из трех операций для сборки модели поезда требуется 1, 2 и 1 минуты рабочего времени. Соответствующее время для сборки моделей грузовиков и легковых автомобилей составляет (2,0, 4) и (1, 2, 0) минут (нуль указывает на то, что соответствующая операция не выполняется).

Обозначив через х{, х2 и х3 количество собираемых ежедневно моделей трех видов, получаем прямую и двойственную задачи ЛП.

Прямая задача

Двойственная задача

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

Минимизировать w= 430yi + 460уг + 420уз

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

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

xi + 2x2 + хз < 430 (операция 1),

yi + Зу2 + Уз 3,

3xi + 2х3 < 460 (операция 2),

2yi + 4у3 > 2,

xi + 4X2 420 (операция 3),

yi + 2у2 > 5,

xi, х2, хз >0.

yi, Уг, Уз>0.

Оптимальное решение

xi = 0, х2 = 100, х3 = 230, z= 1350 долл.

Оптимальное решение

У1 = 1, Уг = 2, уз = 0, w = 1350 долл.

Оптимальное решение предусматривает производство моделей грузовых (хг = 100) и легковых (лг, = 230) автомобилей и требует отказа от производства моделей поездов (д:, = 0). Это означает, что в текущей экономической ситуации производство моделей поездов нерентабельно. Вместе с тем, рынок игрушек требует выпуска этого вида моделей. Как сделать их производство доходным? В соответствии с экономической интерпретацией задач ЛП, приведенной в этом разделе, производство моделей поездов будет выгодным только тогда, когда будет выполняться неравенство z, < с,. Для выполнения этого неравенства нужно либо повысить коэффициент с, (доход от продажи одной модели поезда), например путем увеличения цены модели, либо снизить стоимость ресурсов z, (= у, + Зу2 + у3), необходимых для производства этих игрушек. Увеличение цены игрушек не желательно, так как это снизит их конкурентоспособность на рынке игрушек. Уменьшение величины коэффициента z, более привлекательно, поскольку для этого надо просто сократить время выполнения операций, необходимых для производства моделей поездов. Обозначим через г,, гг и г3 величины, пропорциональные долям сокращения времени соответствующих операций. Эти величины находим из условия, чтобы новая стоимость производственных операций не превышала доход от одной модели поезда. Это условие записывается следующим образом.

1(1 - г,)у, + 3(1 - г2)у2 + 1(1 - г3)у3 < 3



После подстановки значений у, = 1, уг = 2 и у3 = 0 получим следующее неравенство (проверьте!): г, + 6г2 > 4.

Таким образом, любые значения величин г1 и г2, от 0 до 1, удовлетворяющие неравенству г, + 6г2 > 4, приведут к доходности производства моделей поездов. Например, для значений гх = 0,6 и гг = 0,6 получаем z, - с, = 4 - 0,6 - 6x0,6 = -0,2. Вместе с тем отметим, что сокращение времени выполнения второй операции в 6 раз эффективнее сокращения времени выполнения первой операции.

УПРАЖНЕНИЯ 4.3.2

1. В задаче из примера 4.3.2 предположим, что время выполнения второй операции при сборке модели поезда сокращено с 3 до 1,25 минуты. На сколько должно быть сокращено время выполнения первой операции, чтобы производство этой игрушки стало доходным?

2. В задаче из примера 4.3.2 предположим, что фабрика игрушек рассматривает возможность производства еще одного вида игрушки - модели пожарной машины. При сборке этой модели первая операция не используется, а вторая и третья требуют соответственно 1 и 3 минуты для сборки одной модели. Доход от одной модели пожарной машины составляет 4 долл. Посоветуете ли вы фабрике производить эти игрушки?

3. Компания использует токарные и сверлильные станки для производства четырех типов деталей: РР1, РР2, РРЗ и РР4. В следующей таблице представлены технологические данные, характеризующие производство этих деталей.

Станок

Время обработки одного изделия (минуты)

Фонд машинного

времени (минуты)

Токарный

5300

Сверлильный

5300

Доход от одного изделия (долл.)

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

4. Рассмотрите оптимальное решение задачи из предыдущего упражнения. Компания подсчитала, что с помощью специальных мероприятий можно уменьшить общее время производства изделий, не вошедших в оптимальное базисное решение, на 20%. Будет ли после этого производство таких изделий рентабельно? Если нет, то на сколько следует сократить время производства данных изделий?

4.4. РАЗНОВИДНОСТИ СИМПЛЕКС-МЕТОДА

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

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