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


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


47

d) Максимизировать г = 3jc, + 2х2 при ограничениях

2jc, + х2<3, Зл:, + 4х2 > 12, хг,х2>0.

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

a) дс1 = 3,лс2=1;у, = 4,у2=1.

b) х1 = 4, *г=1;у, = 1, у, = 0.

c) jc1 = 3,jc2 = 0;j/1 = 5,j/2 = 0.

4.3. ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ДВОЙСТВЕННОСТИ

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

Чтобы формализовать рассматриваемый вопрос, приведем еще раз общее представление прямой и двойственной задач, причем прямая задача будет играть роль модели распределения ресурсов.

Исходя из модели распределения ресурсов, прямая задача отображает п видов экономической (производственной) деятельности и возможности получения т ресурсов. В прямой задаче коэффициент с\ представляет собой прибыль на единицу продукции у-го вида экономической деятельности, причем на единицу продукции этого вида деятельности расходуется ац единиц ресурса I, максимальные запасы которого ограничены величиной bt.

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

Максимизировать z =

Минимизировать w =

т ; = 1

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

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

!>,*,<*>., « = 1, 2,.. м

., т.

2>„у,.£с,, У = 1,2,..

i = l

Ху>0,у= 1, 2.....п.

у,-> 0, /=1,2.....т.

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

Соотношение из раздела 4.2.5 устанавливает, что для любой пары допустимых решений прямой и двойственной задач значения (конечные) их целевых функций удовлетворяют неравенству



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

Рассмотрим сначала вариант оптимума, т.е. когда z = w. Исходя из представления прямой задачи как модели распределения ресурсов, можно считать, что величина z соответствует величине дохода (в долларах3). Поскольку bt - общее доступное количество ресурса i, равенство z = w можно переписать следующим образом.

Доход (долл.) = ]Г (количество ресурса i) х (доход (долл.) на единицу ресурса i).

Это означает, что переменная yt двойственной задачи должна представлять стоимость единицы ресурса i. (Данное понятие уже вводилось в разделе 2.3.3, исходя из графического представления задачи ЛП.) В литературе по исследованию операций переменные yt двойственной задачи часто называют двойственными ценами. Кроме того, иногда их именуют теневыми ценами и симплексными мультипликаторами.

Аналогично для любой пары допустимых решений прямой и двойственной задач неравенство z <w можно интерпретировать следующим образом:

доход < общая стоимость ресурсов.

Это соотношение показывает, что до тех пор, пока суммарный доход от всех видов деятельности строго меньше суммарной стоимости всех используемых ресурсов, решение как прямой, так и двойственной задачи не может быть оптимальным. Оптимум (максимальный доход) может быть достигнут только тогда, когда все потребляемые ресурсы использованы полностью. Если модель ЛП рассматривать более обще как модель некой системы, имеющую "вход" и "выход", то потребляемые ресурсы характеризуют "вход" этой системы, а получаемый доход- ее "выход". Система будет находиться в нестабильном (неоптимальном) состоянии, пока вход превышает выход. Устойчивое состояние системы характеризуется равенством входа и выхода.

Пример 4.3.1

Приведем формулировки прямой и двойственной задач, описывающие модель производства компании Reddy Mikks из примера 2.1.1.

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

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

Максимизировать z= 5xi + 4хг при ограничениях

6xi + 4хг i 24 (ресурс 1, сырье М1), Xi + 2X2 < 6 (ресурс 2, сырье М2), -Xi + хз < 1 (ресурс 3), хг < 2 (ресурс 3), Хь х2 > 0.

Минимизировать w= 24yi + буг + уз + 2у4

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

6yi + уг - уз s 5,

4yi + 2уг + уз + уд > 4,

У1.У2, Уз, У4>0.

Оптимальное решение: X! =3, хг = 1,5, z= 21

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

yi = 0,75, уг = 0,5, уз = у4 = 0, w= 21

Читатель вместо долларов может, конечно, подставить любую другую денежную единицу - это не принципиально для понимания изложенного материала. - Прим. ред.



Напомним вкратце, что в этой модели описывается производство двух видов краски (для внутренних и наружных работ) на основе двух видов сырья Ml и М2 (ресурсы 1 и 2) с учетом рыночных условий, выражаемых третьим и четвертым ограничениями. Задача состоит в определении объемов производства красок каждого вида (в тоннах), при которых будет получен максимальный доход (в тыс. долл.).

Оптимальное решение двойственной задачи показывает, что стоимость единицы первого ресурса (сырье Ml) составляет у, = 0,75 (или 750 долл. за тонну), а второго (сырье М2) - у2 = 0,5 (или 500 долл. за тонну). В разделе 2.3.3 мы графически показали, что приведенные значения стоимостей справедливы, если значение первого ресурса не выходит из интервала (20, 36), а второго - из интервала (4, 6,67) (эти же результаты алгебраически будут получены в разделе 4.5.1). Таким образом, расход сырья Ml может возрасти с 24 до 36 тонн, что приведет к соответствующему увеличению дохода на величину 12 х 750 = 9000 долл. Аналогично количество второго ресурса (сырье М2) можно увеличить с 6 до 6,67 тонн с увеличением дохода на величину 0,67 х 500 = 335 долл. Но еще раз напомним, что подобные расчеты применимы только тогда, когда увеличение числа используемых ресурсов не выходит за приведенные выше интервалы значений. Конечно, это не означает, что количество используемых ресурсов в принципе не может выходить за указанные пределы. Однако приведенные выше стоимости ресурсов определены только для ситуации, когда количество этих ресурсов не выходит за указанные пределы.

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

УПРАЖНЕНИЯ 4.3.1

1. В задаче из примера 4.3.1 подсчитайте оптимальный доход при выполнении следующих условий.

a) Ограничение для первого ресурса: &хг + 4х2 < 22.

b) Ограничение для второго ресурса: х, + 2х2 < 4,5.

c) Четвертое ограничение: х2 < 10.

2. Электротехническая компания NWAC производит четыре типа кабеля для оборонного ведомства. Каждый тип кабеля подвергается четырем последовательным операциям: разделка, пайка, оплетка и проверка. В следующей таблице приведены данные, характеризующие производство кабелей.

тип Затраты времени на изделие (в минутах) Доход

кабеля

Разделка

Пайка

Оплетка

Проверка

(долл.)

SC320

10,5

20,4

9,40

SC325

24,6

10,80

SC340

11,6

17,7

8,75

SC370

26,5

7,80

Ежедневный фонд рабочего

4800,0

9600,0

4700,0

4500,0

времени (в минутах)

Оборонное ведомство гарантирует для компании минимальный уровень производства в 100 единиц каждого типа кабеля.

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