Минимизировать 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 долл. В течение года компания может произвести больше