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


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


159

Решение задачи динамического программирования с общей функцией стоимости в Excel. Шаблон Excel chllDynamicInventory.xls создан для решения общих задач управления запасами с произвольной функцией стоимости. Этот шаблон похож на шаблон chlOKanpsack.xls, описанный в разделе 10.3.1. В частности, шаблон chllDynamicInventory.xls выполняет вычисления только для одного периода и для вычислений следующего периода пользователь должен произвести некоторые подготовительные операции.

На рис. 11.10 показано применение описываемого шаблона для решения задачи примера 11.3.2. Исходные данные надо вводить для каждого периода в отдельности (после вычислений очередного периода). Эти данные следует вводить в выделенные цветом ячейки. Коэффициенты функции затрат с,(г,) вводятся в строке 3: G3 = 10, НЗ = 20, 13 = 3. Это означает, что удельные затраты для первых трех единиц продукции составляют 10 долл., а для последующих - 20 долл. Отметим, что из значения D, необходимо вычесть значение начального запаса (= 3 - хх = 3 - 1 =2), эта разность вводится в ячейку С5. Также необходимо вручную ввести возможные значения переменной 2,. Шаблон автоматически проверит правильность этих значений и выведет соответствующие сообщения в строке 6.

После ввода всех данных, необходимых для вычислений первого периода, рабочий лист пересчитывается автоматически, показывая оптимальные значения f , и 2, в столбцах S и Т. Далее следует полученное решение (xv ft, z) переписать в область итоговых оптимальных решений в столбцах U:Z. Для этого, скопировав нужные данные и выделив диапазон ячеек, куда будут перенесены эти данные, надо выполнить команду ПравкаСпециальная вставкаЗначения - по этой команде будут скопированы только значения (без формул), по которым они вычислены. (Более подробно эта операция представлена в разделе 10.3.1 при описании работы с шаблоном chlOKanpsack.xls.)

Далее для выполнения вычислений следующего периода надо скопировать значения ft в столбец А, как показано на рис. 11.10, и ввести в ячейку Н2 номер очередного периода.

УПРАЖНЕНИЯ 11.3.3

1. Вернитесь к задаче из примера 11.3.2.

a) Имеет ли смысл рассматривать значение xt > 0?

b) Для каждого из следующих случаев определите допустимые интервалы значений для 2,, гг, гъ, х,, хг и х3. (Полезно представить каждый случай графически, как на рис. 11.9.)

i) xl = 4, остальные исходные данные не меняются,

ii) xl = 0, D1 = 5, D2 = 4 и D3 = 5.

2. Найдите оптимальное решение следующей четырехэтапной задачи управления запасами.

Период /

Спрос, Di (единицы)

Затраты на оформление заказа, К/ (долл.)

Затраты на хранение, hi (долл.)



Период 1

С D

I S 1 T

U V W X

beiieral (Forward) D. iismic P

ogramming Inventory Model

Number of periods, N

Current period-

Optimum solution

3 h1-

dill)-

Summary

Period

1 2

X f z

f z

£

D(1 to 3)=

2 I 2

Период 1

Are zl values correct?

Optimum

□ 23 2

Period 0

Periodl

1 34 3

C1(z1)=

f1 z1

2 55 4

x2= 0

1111111

1111111

1111111

1111111

1111111

1111111

23 2

3 76 5

x2= 1

1111111

1111111

1111111

1111111

1111111

1111111

34 3

4 97 Б

x2= 2

1111111

1111111

1111111

1111111

1111111

1111111

55 4

5 !118 7

x2= 3

1111111

1111111

1111111

1111111

1111111

76 5

6 139 8

x2= 4

1111111

1111111

1111111

1111111

1111111

1111111

97 Б

x2= 5

1111111

1111111

1111111

1111111

1111111

1111111

118 7

x2= E

1111111

1111111

1111111

1111111

1111111

1111111

139 8

Период 2

1 % T

IJ I V W

General (Forward) Dynamic Programming Inventory Model

Number of periods, N=

Current period

Optimum solution

cl(zl)-

Summarv

Period 1

X f z

f z

D(1 to 3)=

Пеои) ц 1

Период 2

, Are zl vafuet romcff

Optimum

0 23 2

50 2

Period 1

Period2

1 34 3

63 3

C2(z2)=

f2 z2

2 55 4

77 3

1111111

1111111

1111111

1111111

50 2

3 7Б 5

100 4

1111111

1111111

1111111

63 3

4 97 Б

123 5

1111111

1111111

77 3

5 118 7

1111111

100 4

Б 139 8

123 5

Период 3

С D

! is т

U W

General (Forward) Dynamic Programming Inventory Model

llumber of periods, N

Current period

Optimum solution

Б Ы

c1(z1)- 10

Summary

Period

1 2

X f z

f z

D(1 to 3)-

2 I ?

Период 1

Период 2

An zl value* correct?

>•(

>es

Optimum

0 23 2

50 2

Period 2

Penod3

1 34 3

63 3

C3(z3)=

G z3

2 55 4

77 3

x4= 0

99 3

3 76 5

100 4

4 97 Б

123 5

5 118 7

Период 3

6 139 8

99 3

1 i

Ufc.

Puc. 11.10. Решение e Excel задачи примера 11.3.2

Затраты на приобретение первых шести единиц продукции составляют 1 долл. за каждую единицу и 2 долл. за каждую дополнительную единицу.

Проверьте вычисления, выполненные вручную, с помощью шаблона ch 11 Dy namicln ven tory. xls.



3. Пусть стоимость хранения запаса определяется средним его объемом на протяжении периода. Получите соответствующее рекуррентное уравнение для алгоритма прямой прогонки.

4. Получите рекуррентное уравнение для алгоритма обратной прогонки и с его помощью решите задачу из примера 11.3.2.

5. Получите рекуррентное уравнение для алгоритма обратной прогонки, предполагая, что стоимость хранения запаса определяется средним его объемом на протяжении периода.

Алгоритм динамического программирования для задачи с постоянными или невозрастающими предельными затратами. Рассмотренную выше модель динамического программирования можно использовать при любых функциях затрат. Важным частным случаем этой модели является такая модель, в которой на этапе i как стоимость закупки единицы продукции, так и затраты на ее хранение - невозрастающие (вогнутые) функции объема закупаемой и хранимой продукции соответственно. Такая же ситуация возникает, когда функция стоимости, отнесенная к единице продукции, является постоянной или когда предоставляется оптовая скидка.

При указанных выше условиях можно доказать следующее.5

1. При заданном начальном нулевом уровне запаса (д:, = 0) для любого этапа I оптимальной стратегией является удовлетворение спроса за счет либо новой закупленной продукции, либо запаса, но не обоих источников, т.е. г1х1 = 0. (При положительном начальном уровне запаса (хх > 0) этот объем может быть списан из спроса последующих этапов, пока он не исчерпается.)

2. Оптимальный объем заказа zt на любом этапе i должен либо равняться нулю, либо в точности соответствовать спросу одного или более последующих этапов.

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

Пример 11.3.3

Рассмотрим четырехэтапную модель управления запасами при следующих исходных данных.

Период / Спрос, D, (единицы) Затраты на оформление заказа, К, (долл.)

1 76 98

2 26 114

3 90 185

4 67 70

5 Подробное доказательство изложено в работе Wagner Н. and Whitin Т. "Dynamic Version of the Economic Lot Size Model", Management Science, Vol. 5, 1958, pp. 89-96. Доказательство получено при ограничивающем предположении, что затраты на единицу продукции постоянны и идентичны на всех этапах. Этот результат в дальнейшем был обобщен А. Вейноттом (A. Veinott) из Стэнфордского университета для вогнутых функций затрат, имеющих место на каждом этапе.

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