Динамическое программирование

СОДЕРЖАНИЕ

Введение 3

1 планирование производственной программы 4

2. распределение на расширение программы 7

заключение 9

список литературы 10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

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

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

В данной работе будут рассмотрены  следующие задачи: планирование производственной программы и распределение средств на расширение программы.

 

 

1 ПЛАНИРОВАНИЕ ПРОИЗВОДСТВЕННОЙ ПРОГРАММЫ

 

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

,        (2.1)

здесь − затраты на хранение единицы продукции. Затраты складываются из условно-постоянных К и пропорциональных LX (L денежных единиц на  каждую единицу продукции) т. е.

.         (2.2)

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

Требуется определить производственную программу изготовления машин  удовлетворяющую спрос в каждом из месяцев планируемого периода и обеспечивающую минимальные затраты на производство продукции и содержание запасов. Запас продукции на складе в конце планируемого периода должен быть равен 0.

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

Составим основное рекуррентное уравнение для данной задачи.

1. Планируемый период  Т разбиваем на шаги по месяцам.  Обозначим 
через n номер планового отрезка времени (соответствует обратной нумерации месяцев, так как планирование выполняется с конца периода Т).

2. Состояние системы перед  каждым шагом будет характеризоваться 
параметром − уровень запасов на начало отрезка n (шага).

3. Параметром шагового  управления задачи будет переменная  - количество производимой продукции на отрезке n.

4. Выигрыш (эффект) на каждом  шаге n определяется общими затратами связанными с выпуском − единиц продлении на n отрезке и с содержанием запасов на конец n - го отрезка .

5. Состояние, в которое  переходит система под влиянием  управления  на шаге n.

,

где - спрос на продукцию на n-ом отрезке

.

Обозначим через  − условно-оптимальный накопленный эффект за n шагов, то есть минимальные затраты на производство и хранение продукции за n последних месяцев при условии, что уровень запасов на начало n - го месяца равен i − единиц; − производство продукции на n-м отрезке, если уровень запасов на начало отрезка равен (объем выпуска).

6. Основное рекуррентное  уравнение имеет вид

 (2.3)

Параметры и удовлетворяет следующим ограничениям:

,           (2.4)

так как спрос на данном отрезке должен быть удовлетворен.

,        (2.5)

так как запас на конец  планового периода равен 0 и производство продукции на любом отрезке не превышает B.

,         (2.6)

Так как уровень запасов  не должен превышать ограничений  на складские площади предприятия.

Пример:

Исходные данные

D1	D2	D3	D4	L	h	B	M	K	T
1	2	3	4	2	1	6	4	8	4

 

Решение:

n=4 (март) D4=4

	0	1	2	3	4	5	6	X4	F4
0	-	-	-	-	16+0+0	-	-	4	16
1	-	-	-	14+0+0	-	-	-	3	14
2	-	-	12+0+0	-	-	-	-	2	12
3	-	10+0+0	-	-	-	-	-	1	10
4	8+0+0	-	-	-	-	-	-	0	8

n=3 D3=3

	0	1	2	3	4	5	6	X3	F3
0	-	-	-	14+0+16	16+1+14	18+2+12	20+3+10	3	30
1	-	-	12+0+16	14+1+14	16+2+12	18+3+10	20+4+8	2	28
2	-	10+0+16	12+1+14	14+2+12	16+3+10	18+4+8	-	1	26
3	8+0+16	10+1+14	12+2+12	14+3+10	16+4+8	-	-	0	24
4	8+1+14	10+2+12	12+3+10	14+4+8	-	-	-	0	23

n=2 D2=2

	0	1	2	3	4	5	6	X2	F2
0	-	-	12+0+30	14+1+28	16+2+26	18+3+24	20+4+23	2	42
1	-	10+0+30	12+1+28	14+2+26	16+3+24	18+4+23	-	1	40
2	8+0+30	10+1+28	12+2+26	14+3+24	16+4+23	-	-	0	38
3	8+1+28	10+2+26	12+3+24	14+4+23	-	-	-	0	36
4	8+2+26	10+3+24	12+4+23	-	-	-	-	0	36

n=1 D1=1

	0	1	2	3	4	5	6	X1	F1
1	8+0+42	10+1+40	12+2+38	14+3+36	16+4+36	-.	-	0	50

 

Ответ: X1=0, X2=2, X3=3, X4=4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 РАСПРЕДЕЛЕНИЕ СРЕДСТВ НА РАСШИРЕНИЕ ПРОГРАММЫ

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

Составление основного рекуррентного  уравнения задачи.

1. Задача разбивается  на шаги искусственным образом.

В качестве n-го шага принимается вложение средств в n предприятий.

2. Параметр, характеризующий  состояние системы перед каждым  шагом − запас не вложенных  средств С.

3. Параметры «шагового  управления» данной задачи –  средства  выделяемые предприятиям.

4. Выигрыш на шаге n определяется приростом выпуска продукции , n-го предприятия в зависимости от вложенных в него средств х (шагового управления).

5. Под действием «шагового  управления» х система переходит в новое состояние . Здесь С_n –  запас не вложенных средств на шаге n, которые можно вложить в n предприятий, х_n – те средства из С_n, которые вложили на данном шаге в n-ое предприятие и С_n-1 – соответственно оставшиеся не вложенные средства на предыдущем шаге (n-1) для распределения по оставшимся (n-1) предприятиям.

Обозначим через  максимальное значение прироста продукции при распределении суммы С между n предприятиями.

6. Рекуррентное соотношение  для этой задачи имеет вид

       (3.1)

где максимальное значение прироста продукции на предыдущем шаге (n-1), при распределении суммы между (n-1) предприятиями, .

 

 

Пример:

Исходные данные

	1	2	3	4
20	14	37	48	45
40	64	33	52	51
60	47	77	73	64
80	104	61	102	103
100	94	98	103	108

 

Решение:

При n=1

	0	20	40	60	80	100	Fn	Xn
20	-	14+0	-	-	-	-	14	20
40	-	-	64+0	-	-	-	64	40
60	-	-	-	47+0	-	-	47	60
80	-	-	-	-	104+0	-	104	80
100	-	-	-	-	-	94+0	94	100

При n=2

	0	20	40	60	80	100	Fn	Xn
20	0+14	37+0	-	-	-	-	37	20
40	0+64	37+14	33+0	-	-	-	64	0
60	0+47	37+64	33+14	77+0	-	-	101	20
80	0+104	37+47	33+64	77+14	61+0	-	104	0
100	0+94	37+104	33+47	77+64	61+14	98+0	141	60,20

При n=3

	0	20	40	60	80	100	Fn	Xn
20	0+37	48+0	-	-	-	-	48	20
40	0+64	48+37	52+0	-	-	-	85	20
60	0+101	48+64	52+37	73+0	-	-	112	20
80	0+104	48+101	52+64	73+37	102+0	-	149	20
100	0+141	48+104	52+101	73+64	102+37	103+0	153	40

При n=4

	0	20	40	60	80	100	Fn	Xn
20	0+48	45+0	-	-	-	-	48	0
40	0+85	45+48	51+0	-	-	-	93	20
60	0+112	45+85	51+48	64+0	-	-	130	20
80	0+149	45+112	51+85	64+48	103+0	-	157	20
100	0+153	45+149	51+112	64+112	103+48	108+0	194	20