Промежуточные вычислении 14 страница

На рис. 10.5 показаны этапы вычислений для задачи примера 10.3.1. Вычисле­ния выполняются последовательно по этапам и пользователю необходимо предос­

¹ Эта рабочая книга закрыта паролем от изменений, поэтому она не русифицирована. Кроме того, перед ее использованием следует установить в Windows (Панель управления^Язык и стандарты) региональные установки Английский (США), иначе не все вы­числения в этой книге выполняются корректно. Это замечание относится ко всем рабочим книгам и шаблонам Excel, которые упоминаются в оставшейся части книги. — Прим. ред.

10.3. Приложения динамического программирования

тавить основные данных для каждого этапа. Вычисления начинаются с этапа 3, для которого надо ввести следующие данные.

Что вводится Ячейки Количество этапов, N = 3 D3 Ограничение загрузки, W = 4 G3 Текущий этап = 3 С4 w3 = 1 Е4 гЗ = 14 G4

ш3 = (0,1, 2, 3, 4) D6:H6

Отметим, что допустимыми значения для т₃ являются числа 0, 1, [W/w₃] = = [4/1] =4 так же, как в примере 10.3.1. Рабочий лист автоматически проверяет правильность значений т, и выводит соответствующие сообщения в строке 5 (сообщения вида "yes" ("да"), "по" ("нет") и "delete" ("исключить")).

После ввода данных для этапа 3 рабочий лист "оживает" и выполняет все необ­ходимые вычисления автоматически (в столбцах В:Р). Значения -111111 указы­вают, что соответствующий вариант загрузки недопустим. Оптимальное решение (/з, т_г) этого этапа приведено в столбцах О и Р. В столбце А выводятся значения /₄. Поскольку вычисления начинаются с этапа 3, f_t = 0 для всех значений х₃. Поэтому ячейки А9:А13 оставлены пустыми (или могут быть заполнены нулями).

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

Шаг 1. Скопируйте значения х₃ (диапазон С9:С13) и вставьте их в ячейки диапазона Q5:Q9, где будет храниться оптимальное решение 3-го этапа. Далее скопируйте значения (f₃, m₃) (диапазон 09:Р13) и вставьте их в диапазон R5:S9. Напомним, что необходимо скопи­ровать и вставить только значения (а не формулы, по которым вы­числялись эти значения). Для этого после копирования данных и выделения диапазона, где будут вставлены эти данные, выпол­ните команду ПравкаОСпециальная вставка и после появления од­ноименного диалогового окна установите в нем переключатель Значения; затем щелкните на кнопке ОК.

Шаг 2. Скопируйте значения f_} из диапазона R5:R9 в диапазон А9:А13 (без использования диалогового окна Специальная вставка).

Шаг 3. Введите число 2 в ячейку С4, а также новые значения w₂, г₂ и т₂. На этом заканчивается подготовка к выполнению этапа 2.

После выполнения этапа 2 рабочий лист следует подготовить к этапу 1 так же, как описано выше. После завершения этапа 1 полученное оптимальное решение интерпретируется точно так же, как показано в примере 10.3.1.

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

Глава 10. Детерминированные модели динамического программирования

Этап 3

Этап 2

'S ^т i ":.У,

IX

Input Data tnr Mar

m ratcnfcrtiofrs

Ouput Solution Summary

Number of atanaa.N

Pea. Nit*, W-

wi^ carrot шх rsd

Stage Optvnum Solution

x

f m

x

1 m

-utient агаре11]?

I

1?»

ЭтапЗ

Этап 2

4r9m2v

0 1 2 3

0 0 14 1 28 2 42 3

0 0

SteoeJ

ml

•

2 3

14 0 28 D 47 1

г2"т2-

f]

»2"m2-

D

Г2 m2

x2-

D

i11111

0 0

56 4

81 1

x2-

14 0

x2-

28 0

x2-

47 1

x2-

61 1

Этап I

. J *

В с

D

E

F

H

i

J

к

. L

M

N

P

Q

Г R ~S

I

U V

Dynamic Piooiamrnmg (Bachwardl Knapsack Model

■■put Data and sta.

ft Cetculetiona

Ouput sotait

on Summary

3 Numbei of stay»,M- 4 uiiemcta^c 1 5 hrt mlYMln»scomet

J

RM.kmrl.W-

Z2

f m

X

f m

_ t

il-

Hi

■

ЭтапЗ

Этап 2

•«

Г]

_

Stage

0 0

0 0

1_ml ■

•

г

Opttnum

14 1

14 0

7 Stage!

rlNnl-

D

Solution

28 2

28 0

8 f?

w1*ml«

t1

rtvt

42 3

47 1

S 3

xi- 0

D

56 4

61 1

10 14

xi- 1

ЭтапЗ

11 28

xi- 2

0 0

12 47

xi. 3

14 0

13 81

Xi- 4

31 1

I"

47 0

IS

62 2

^_

Рис. 10.5. Этапы решения задачи примера 10.3.1

УПРАЖНЕНИЯ 10.3.1³

1. В задаче примера 10.3.1 определите оптимальное решение, предполагая, что максимальная грузоподъемность самолета составляет 3 тонны.

2. Решите задачу о загрузке из примера 10.3.1 для каждого из следующих случаев.

a) w, = 4, г,= 70, w_s= 1, г₂= 20, w₃= 2, г₃= 40, W= 6.

b) и>,= 1, г, = 30, и>₂= 2, г₂= 60, w₃= 3, г₃= 80, W = 4.

3. Турист собирается в путешествие по дикой местности и должен упаковать в рюкзак предметы трех видов: пищу, средства первой помощи и одежду. Объем рюкзака составляет 3 кубических фута. Каждая единица пищи занимает

В этих упражнениях там, где возможно, выполните вычисления вручную, а затем про­верьте полученные результаты с помощью шаблона Excel chlOKnapsack.xls.

10.3. Приложения динамического программирования

1 кубический фут, упаковка средств первой помощи — четверть кубического фута, а отдельный предмет одежды — примерно половину кубического фута. Турист определил свои предпочтения весовыми коэффициентами 3, 4 и 5 — для пищи, средств первой помощи и одежды соответственно. Это означает, что одежда является самым ценным предметом среди остальных. Опыт под­сказывает туристу, что он должен взять не менее одного предмета каждого вида и не более двух комплектов средств первой помощи. Сколько единиц каждого наименования возьмет турист в поход? 4. Студент должен выбрать 10 факультативных курсов на четырех различных фа­культетах, причем на каждом факультете должен быть выбран по меньшей мере один курс. Эти курсы распределяются между факультетами таким образом, чтобы максимизировать объем "знаний". Студент оценивает знания по шкале в сто баллов и приходит к выводам, представленным в следующей таблице.

Номер курса

Факультет							>7
II
III
IV

Какие курсы следует выбрать студенту?

5. У меня во дворе имеется небольшой огород 10 х 20 футов. Этой весной я соби­раюсь посадить овощи трех видов: помидоры, зеленые бобы и кукурузу. Огород разбит на ряды, длина которых равна 20 футам. Кукуруза и помидоры зани­мают ряды шириной 2 фута, а зеленые бобы — 3 фута. Помидоры мне нравятся больше, а бобы меньше. По 10-балльной шкале предпочтений я бы присвоил помидорам 10 баллов, кукурузе — 7 баллов и зеленым бобам — 3 балла. Неза­висимо от моих предпочтений, жена настаивает, чтобы я посадил не менее одного ряда зеленых бобов и не более двух рядов помидоров. Сколько рядов каждого вида овощей следует мне посадить?

6. "Жилище для человечества" — прекрасная благотворительная организа­ция, которая строит дома для бедствующих семей силами добровольцев. Та­кая семья может выбрать себе дом из трех типоразмеров: 1000, 1100 и 1200 квадратных футов. Дом каждого типоразмера требует выполнения опреде­ленного объема работ силами добровольцев. Филиал организации в городе Файтвилл получил пять заявок на предстоящие шесть месяцев. Комитет по надзору дает оценку каждой заявке в численном виде, принимая во внима­ние различные факторы. Более высокая оценка означает более острую по­требность в жилье. В течение предстоящих шести месяцев филиал организа­ции в этом городе может привлечь к работе максимум 23 добровольца. Следующая таблица содержит оценку каждой заявки и необходимое число добровольцев для ее выполнения. Какие заявки следует утвердить комитету?

Заявка	Размер дома (фут2)	Оценка	Необходимое число добровольцев

Глава 10. Детерминированные модели динамического программирования

7. Шериф округа Вашингтон баллотируется на следующий срок. Денежные средства на предвыборную кампанию составляют примерно 10 ООО долларов. Хотя комитет по переизбранию хотел бы провести кампанию во всех пяти из­бирательных участках округа, ограниченность денежных средств предписы­вает действовать по-другому. Приведенная ниже таблица содержит данные о числе избирателей и денежных средствах, необходимых для проведения успешной кампании по каждому избирательному участку. Каждый участок может либо использовать все предназначенные деньги, либо вовсе их не ис­пользовать. Как следует распределить денежные средства?

Участок	Число избирателей	Необходимые средства (долл.)

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

Число параллельных блоков	Компонент 1	Компонент 2		Компонент 3
г1	с1 (долл.)	г2	с2 (долл.)	гЗ	сЗ (долл.)
	10.6		0.7		0.5
	20.8		0.8		0.7
	30.9		0.9		0.9

Общая сумма, выделенная на конструирование прибора, равна 10 000 долл. Как следует сконструировать прибор? (Совет. Наша задача состоит в макси­мизации надежности г,/у, прибора. Это значит, что целевая функция является мультипликативной, а не аддитивной.)

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

Максимизировать z = у\У2—у_п

при условиях

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

(Подсказка. Это упражнение аналогично предыдущему упражнению, но с той лишь разницей, что переменные y_t являются непрерывными.)

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

10.3. Приложения динамического программирования

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

при условиях

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

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

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

при условиях

У1 + У2 + Уз + У₄< 5, у,-> 0 и целые, / = 1, 2, 3, 4.

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

Минимизировать z = max {Ду₁),Ду₂), —,fly„)}

при условиях

У1 + У2+- +Уп=С,

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

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

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

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

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

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

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

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

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

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

/ (дг,_,) = min {С, (х, - Ь,) + С₂ (х, -) + (х,)}, i = 1,2.....л,

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

Глава 10. Детерминированные модели динамического программирования

Пример 10.3.2

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

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

bx = 5,b2=l, b3=&,b4=4,b5 = С,(дг, - Ы) = 3(дг, - Ы), х, > bh i C2(xi - xLl) = 4 + 2(Xj - x,_,), x, Этап 5. (bs = 6)	6, = 1,2.....5, ,>*,_,, ('= 1, 2,5.
Ci(x, - 6) + C^x, - xt)	Оптимальное решение
Xi xf - 6
4 3x0 + 4 + 2x2 = 8 5 3x0 + 4 + 2x1 = 6 6 3x0 + 0 = 0	8 6 0	6 6 6
Этап 4. (b4 = 4)
Ci(x4 - 4) + Q>(x4 - x3) + f,(xi)		Оптимальное решение
Хз x4 = 4 Xi = 5	Xt = 6
8 3x0 + 0 + 8 = 8 3x1 + 0 + 6 = 9 3x2 + 0 + 0	= 6 6 6
Этап 3. (b} = 8)
C,(x3 - 8) + Сг(хз - x2) + Mx3)		Оптимальное решение
x2 x3 = 8
7 3x0 + 4 + 2x1+6 = 12 8 3x0 + 0 + 6 = 6		12 8 6 8
Этап 2. (b2 = 7)
C,(x2 - 7) + Сг(хъ - x2) + h(x2)		Оптимальное решение
X\ x2 = 7 Хг = 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

10.3. Приложения динамического программирования 457

Этап 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

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

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

Номер недели (/)	Минимум рабочей силы (Ь,)	Количество фактически работающих (х,)	Решение
			Нанять 5 рабочих
			Нанять 3 рабочих
			Ничего не менять
			Уволить 2 рабочих
			Ничего не менять

УПРАЖНЕНИЯ 10.3.2

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

a) 6, = 6, Ъ_г = 5, b₃ = 3,Ь_А = 6, Ъ_ь = 8.

b) Ь_х = 8, Ь₂ = 4, b₃ =7,b_t = 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 долл. В течение года компания может произвести больше

Глава 10. Детерминированные модели динамического программирования

двигателей, чем необходимо, но в этом случае двигатели должны надле­жащим образом храниться до их отгрузки потребителю. Стоимость хране­ния одного двигателя также меняется от года к году и оценивается в 20 ООО долл. для первого года, 30 ООО долл. — для второго, 40 ООО долл. — для третьего и 50 000 — для четвертого. В начале первого года компания имеет один двигатель, готовый к отгрузке. Разработайте оптимальный план про­изводства двигателей.

10.3.3. Задача замены оборудования

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

Предположим, что мы занимаемся заменой механизмов на протяжении п лет. В начале каждого года принимается решение либо об эксплуатации механизма еще один год, либо о замене его новым. Обозначим через r(t) и c(t) прибыль от эксплуа­тации г-летнего механизма на протяжении года и затраты на его обслуживание за этот же период. Далее пусть s(t) — стоимость продажи механизма, который экс­плуатировался t лет. Стоимость приобретения нового механизма остается неизмен­ной на протяжении всех лет и равна /.