Динамическое программирование лабораторная работа

1.6. Лабораторная работа №6: Динамическое программирование: замена оборудования, подверженного старению

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

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

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

Введем следующие обозначения:

r(t) — прибыль от эксплуатации t-летнего оборудования на протяжении года;

c(t) — затраты на обслуживание t-летнего оборудования на протяжении года;

s(t) – стоимость замены оборудования, которое эксплуатировалось t лет (продажа t-летнего оборудования и покупка нового).

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

Пусть предполагается к осуществлению некоторое мероприятие или серия мероприятий («операция»), преследующая определенную цель. Спрашивается: как нужно организовать (спланировать) операцию для того, чтобы она была наиболее эффективной? Для того чтобы поставленная задача приобрела количественный, математический характер, необходимо ввести в рассмотрение некоторый численный критерий W, которым мы будем характеризовать качество, успешность, эффективность операции. Критерий эффективности в каждом конкретном случаи выбирается исходя из целевой направленности операции и задачи исследования (какой элемент управления оптимизируется и для чего).

Сформулируем общий принцип, лежащий в основе решения всех задач динамического программирования («принцип оптимальности»):

«Каково бы ни было состояние системы S перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным».

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

Пример.В определенный момент времени на предприятии установлено новое оборудование, т.е. в начале 1-го года возраст оборудования t = 0. Если в начале 2-го года не заменить оборудование, то его возраст t будет равен 1. Максимальный срок службы оборудования 5 лет, к/й достигается в начале 6-го года (если все это время оборудование не заменяется). В табл. 1 приведены зависимость дохода (в тыс. руб.), приносимого этим оборудованием, затрат на содержание и ремонт оборудования, а также зависимость стоимости замены оборудования от времени его использования предприятием.

Время использования оборудования (t)

Источник

Лабораторная работа № 5 Решение задач динамического программирования

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

Краткие теоретические сведения

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

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

Контрольный пример

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

Источник

Лабораторные работы №2

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

1. Этап i представляется порядковым номером недели.i=1,2,3,4,5
2. Вариантом решения на i-том этапе являются значения — количество работающих на протяжении i –той недели.
3. Состояние на i – том этапе является — количество работающих на протяжении (i-1)- й неделе.

Рекуррентное уравнение динамического программирования представляется в виде: — затраты, связанные с содержанием избытка — затраты, связанные с наймом — затраты, связанные с увольнением Метод обратной прогонки: Этап 5.

Оптимальное решение
6	300*0+400+200*2+100*(-2)= 600	600	8
7	300*0+400+200*1+100*(-1)= 500	500	8
8	300*0+400+200*0+100*0= 400	400	8

Этап 4.

+ Оптимальное решение
	= 6	= 7	= 8
3	1300	1600	1900	1300	6
4	1200	1500	1800	1200	6
5	1100	1400	1700	1100	6
6	1000	1300	1600	1000	6

Этап 3.

+ Оптимальное решение
5	1500	1800	2100	2400	1500	3

Этап 2. + Оптимальное решение

	= 5
6	300*0+400+200*(-1)+100+1500=1800	1800	5
7	300*0+400+200*(-2)+200+1500=1700	1700	5
8	300*0+400+200*(-3)+300+1500=1600	1600	5

Этап 1. + Оптимальное решение

	= 6	= 7	= 8
0	2800	3100	3400	3800	6

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

Номер недели	Минимум раб.силы	Кол-во реально работающих	Решение
1	6	6	Нанять 6 рабочих
2	5	5	Уволить 1 рабочего
3	3	3	Уволить 2 рабочих
4	6	6	Нанять 3 рабочих
5	8	8	Нанять 2 рабочих

Вывод: в результате решения задачи получилось, что на первой неделе надо нанять 6 человек, на второй уволить 1 рабочего, на третьей уволить 2 рабочих, на четвертой нанять троих рабочих и на пятой нанять двоих рабочих.

Источник