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


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


146

Минимизировать z = y] + у; + ...+ у*

при условиях

У\Уг-Уп = с, у,>0, / = 1, 2,п.

11. Решите следующую задачу, используя метод динамического программирования.

Максимизироватьz = (у, +2)" + угуъ +(у4 -5)"

при условиях

У1+У2 + Уз + У4< 5,

у-> 0 и целые, / = 1, 2, 3, 4.

12. Решите следующую задачу с помощью метода динамического программирования.

Минимизировать z = max {Ду!),Ду2), ...,Ду„)}

при условиях

У1 + У2+- +у„=с, у,->0, /= 1,2,..., п.

Найдите решение задачи при условии, что п = 3, с =10, ДуО = Vi + 5, Лу2) = 5у2+Зи/(у3)=уз-2.

10.3.2. Задача планирования рабочей силы

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

Предположим, что проект будет выполняться в течение п недель и минимальная потребность в рабочей силе на протяжении /-Й недели составит Ь, рабочих. При идеальных условиях хотелось бы на протяжении i-й недели иметь ровно £>, рабочих. Однако в зависимости от стоимостных показателей может быть более выгодным отклонение численности рабочей силы как в одну, так и в другую сторону от минимальных потребностей. Если х, - количество работающих на протяжении i-й недели, то возможны затраты двух видов: l)Ci(x,-b,)- затраты, связанные с необходимостью содержать избыток х,-Ь, рабочей силы и 2) С2(х, - Х; ,)- затраты, связанные с необходимостью дополнительного найма х, - Х/ , рабочих.

Элементы модели динамического программирования определяются следующим образом.

1. Этап i представляется порядковым номером недели i, i = 1, 2, п.

2. Вариантами решения на t-м этапе являются значения х, - количество работающих на протяжении ;-й недели.

3. Состоянием на ;-м этапе является - количество работающих на протяжении (/ - 1)-й недели (этапа).

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

/ (х, ,) = min {С, (х, - Ь,) + С2 (х,. - х,.,) + /Itl (х,)}, i = 1,2.....л,

где/„+1(х„) = 0. Вычисления начинаются с этапа п при х„ = Ь„и заканчиваются на этапе 1.



Пример 10.3.2

Строительный подрядчик оценивает минимальные потребности в рабочей силе на каждую из последующих пяти недель следующим образом: 5, 7, 8, 4 и 6 рабочих соответственно. Содержание избытка рабочей силы обходится подрядчику в 300 долл. за одного рабочего в неделю, а наем рабочей силы на протяжении одной недели обходится в 400 долл. плюс 200 долл. за одного рабочего в неделю.

Выражая С\ и С2 в сотнях долларов, имеем следующее.

bx = 5,b2=l, b3=S,b4=4,b5 = Ci(xf - Ы) = 3(дг, - Ы), х, > b,, i C2(Xi - *, ,) = 4 + 2(Xj - х, ,), x,

Этап 5. (bs = 6)

= 1,2.....5,

,>*, ,, (= 1, 2,5.

Ci(X; - 6) + Cl(Xl - Xi)

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

Xi Xf - 6

U*i)

4 3x0 + 4 + 2x2 = 8

5 3x0 + 4 + 2x1 = 6

6 3x0 + 0 = 0

8 6 0

6 6 6

Этап 4. (b4 = 4)

C,(xt - 4) + Ci(Xi - х3) + b(Xi)

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

х} xt = 4 Xi = 5

Xt = 6

8 3x0 + 0 + 8 = 8 3x1 + 0 + 6 = 9 3x2 + 0 + 0

= 6 6 6

Этап 3. (b} = 8)

C,(Xi - 8) + C2(Xi - x2) + fi(Xi)

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

x2 Xi = 8

Кхг) x;

7 3x0 + 4 + 2x1+6 = 12

8 3x0 + 0 + 6 = 6

12 8 6 8

Этап 2. (b2 = 7)

C,(x2 - 7) + C2(Xi - хг) + h(x2)

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

X\ x2 = 7 x2 = 8

5 3x0 + 4 + 2x2 + 12 = 20 3x1 +4 + 2x3 + 6 = 19

6 3x0 + 4 + 2x1 + 12 = 18 3x1 +4 + 2x2 + 6= 17

7 3x0 + 0+ 12 = 12 3x1 +4 + 2x1 +6= 15

8 3x0 + 0 + 12 = 12 3x1 +0 + 6 = 9

19 8 17 8 12 7 9 8



Этап 1. (6, = 5)

Ci(x, - 5) + С2(х, - хь) + f2(xi)

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

Хо Xi = 5

Xi = 6 Xi = 7

X, = 8

fl(Xo) x

0 3x0 + 4 + 2x5

3x1 + 4 + 2x6 3x2 + 4 + 2x7

3x2 + 4 + 2x8

33 5

+ 19 = 33

+ 17 = 36 +12 = 36

+ 9 = 35

Оптимальное решение определяется последовательно таким образом.

х0 = 0 -> х\ - 5 -> х\ = 8 -> xj = 8 -> х\ = 6 -> дг* =6. Полученному решению соответствует следующий план.

Номер недели (/)

Минимум рабочей сипы (о,)

Количество фактически работающих (х,)

Решение

Нанять 5 рабочих

Нанять 3 рабочих

Ничего не менять

Уволить 2 рабочих

Ничего не менять

УПРАЖНЕНИЯ 10.3.2

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

a) 6, = 6, Ъг = 5, b3 = 3,ЬА = 6, Ъь = 8.

b) Ьх = 8, Ь2 = 4, b3 =7,bt = 8, Ьь = 2.

2. Пусть в примере 10.3.2 каждому уволенному рабочему выплачивается выходное пособие в размере 100 долл. Найдите оптимальное решение задачи.

3. Туристическое агентство организовывает недельные поездки в Египет. В соответствии с договором на ближайшие четыре недели агентство должно обеспечить туристические группы арендными автомобилями в количестве семь, четыре, семь и восемь штук соответственно. Агентство заключает договор с местным дилером по прокату автомобилей. Дилер назначает арендную плату за один автомобиль 220 долл. в неделю плюс 500 долл. за любую арендную сделку. Агентство, однако, может не возвращать арендованные автомобили в конце недели, и в этом случае оно должно будет платить только арендную плату в 220 долл. Каково оптимальное решение проблемы, связанной с арендой автомобилей?

4. Компания на следующие четыре года заключила контракт на поставку авиационных двигателей, по 4 двигателя в год. Доступные производственные мощности и стоимость производства меняются от года к году. Компания может изготовить пять двигателей за 1-й год, шесть - за 2-й, три - за 3-й и пять - за 4-й. Стоимость производства одного двигателя на протяжении следующих четырех лет равна соответственно 300 000, 330 000, 350 000 и 420 000 долл. В течение года компания может произвести больше

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