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


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


161

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

{К,, t = i.

rC(f) \к, + h,DM +(/*,. + hM)DM + ... + (/*,+ /,м1 + ... + V,)D„ t >,. Обозначим далее через TCU(i, t) соответствующие затраты за период, т.е.

тс (и)

TCU{i,t) =

/-/4-1

Таким образом, для заданного текущего этапа / эвристический метод определяет t", которое минимизирует функцию TCU(i, t).

Функция TC(i, t) определяется с помощью рекуррентных соотношений.

TC(i, i) = К,,

TC(i, t) = TC{i, * - 1) + (Л, + Vi + ••• + *,-i)A. t=i + l,i + 2, n. Алгоритм эвристического метода состоит из следующих шагов.

Шаг О. Пусть i = l.

Шаг 1. Определяем локальный минимум t функции TCU(i, t), который должен удовлетворять неравенствам

TCU(i, t-\)>TCU(i, t),

TCU(i,t +\)>TCU(i,t).

Тогда в соответствии с эвристическим подходом на этапе i размещается заказ объемом (Д 4- Дм + ... + Д.) для этапов ;, /4-1, t".

Шаг 2. Пусть i = t*+l. Если 1> п, вычисления заканчиваются; рассмотрен весь плановый период. Иначе следует перейти к шагу 1.

Пример 11.3.4

Найдем оптимальную стратегию управления запасами в следующей 6-этапной задаче. Стоимость единицы продукции равна 2 долл. для любого периода.

Этап i

D, (единицы)

К, (долл.)

л, (долл.)

Итерация 1 (i - 1, Кх = 20 долл.). Функция ТС(1, t) определяется рекуррентно по t. Например, при заданном значении 742(1, 1) = 20 долл., ТС(1, 2) = ТС(1, 1) 4- h,D2 = = 20 4- 1 х 15 = 35 долл.



Этап f

тс(1,о

7Щ1, г)

20/1 = 20,00

20 + 1 х 15 = 35

35/2 = 17,50

35+ (1 +1)х7 = 49

49/3 = 16,33

49+ (1 +1 +1)х20 = 109

109/4 = 27,25

Локальный минимум достигается при t* = 3, что означает необходимость размещения на первом этапе заказа объемом 10 + 15 + 7 = 32 единицы для этапов 1, 2, 3. Полагаем i = t +1 = 3 + 1=4.

Итерация 2 (<

= 4, Kt = 18 долл.)

Этап С

Щ4, 0

ТОД4, г)

18/1 = 18,00

18 + 3x13 = 57

52/2 = 28,50

Значение t - 4 означает, что на четвертом этапе необходимо разместить заказ объемом 20 единиц для этапа 4. Полагаем i = 4 + 1 = 5.

Итерация 3(i = 5, Кь = 5 долл.)

Этап f

ТЦ5, г)

TCU(5, г)

5/1 =5

5 + 1 х 25 = 30

30/2 = 15

Так как t = 5, на пятом этапе заказывается 13 единиц для этапа 5. Полагаем далее г = 5 + 1 = 6. Так как i = 6, то это последний этап планирования. Мы должны заказать на шестом этапе 25 единиц для этого же этапа.

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

Этап

Эвристический метод

Метод динамического программирования

Закуплено единиц

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

Закуплено единиц

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

Всего

Стоимость производственного плана, предложенного эвристическим методом, примерно на 32 % превышает стоимость аналогичного плана, полученного методами динамического программирования (122 долл. против 90). "Неадекватность" результата эвристического метода может быть обусловлена данными, которые ис-



пользовались в задаче. В частности, причиной этого может быть чрезвычайная неравномерность стоимостей размещения заказов для этапов 5 и 6. Тем не менее этот пример показывает, что эвристический метод не обладает способностью "смотреть вперед" в поисках лучшего производственного плана. Например, размещение на пятом этапе заказов для этапов 5 и 6 (вместо размещения их в отдельности) может сэкономить 25 долл., что уменьшит суммарные затраты производственного плана, предложенного эвристическим методом, до 97 долл.

Реализация в Excel эвристического подхода Сильвера-Мила. Шаблон Excel chllSilverMealHeuristic.xls разработан для получения решения на основе эвристического подхода Сильвера-Мила. Процесс решения задачи начинается со ввода всех необходимых данных, включая значения величин К, й и D для каждого периода и значение N - количество периодов. (Ячейки рабочего листа для входных данных выделены цветом.) Затем пользователь должен инициировать вычисления для каждой итерации вручную.

На рис. 11.12 показано применение этого шаблона для решения задачи из примера 11.3.4. Первая итерация инициируется путем введения значения 1 в ячейку F11, это означает что на первой итерации выполняются вычисления для первого периода. Excel выведет столько строк расчетных значений, сколько указано в ячейке G3 как общее число периодов (в данном примере это число равно 6). Номера периодов выводятся в диапазоне G11:G16. Далее проверяем вычисленные значения TCU в столбце L (этот столбец выделен зеленым цветом) и находим минимальное значение. В данном случае локальному минимуму соответствует t = 3 (третий период) со значением TCU = 16,33. Отсюда следует, что следующая итерация должна начаться

О Р О R

Silver-Meal Heuristic Inventory Model

Input data:

i Number of periods, N =

:Maximum 14 periods

Period t=

Setup cost, Kt =

Holding cost. ht =

Demand, Dt =

Solution complete

Model calculations:

Optimum solution (Total cost"

$122 00)-

1 Start Iteration at Period

Period

0 00

20 00

1.00

35 00

2 00

49.00

3 00

109.00

6 00

187.00

7 00

362.00

Order 32 in period 1 lor periods 1 to 3, cost - S49.00

20 0.00

18.00

3.00

57.00

4.00*

157.00

Older 20 in period 4 for period!. 4 to 4, cod - $18.00

13 0.00

~ 5.00

38 1.00

30.00

Ordtr 13 in period 5 for period! 5 to 5, cod - SS.00

1

L

0.00

50.00

Ordsr 25 in peiiod 61or penods 6to 6, cost - S50.00

Рис. 11.12. Решение в Excel задачи из примера 11.3.4

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