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

 

Пример

Задача распределения денежных средств между предприятиями

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

8	41	28	35	27
16	57	68	67	73
24	120	122	126	125
32	150	146	144	175
40	180	175	180	178

 

Решение:

Запишем задачу в математической форме

 

При ограничениях

 

, где количество средств, выделяемых каждому предприятию.

ожидаемый прирост продукции от выделенных средств, млн. руб.

Разбиваем процесс решения на 4 этапа. Начальное состояние объекта 40 млн. руб., конечное 0 млн. руб. Состояние это имеющиеся на -ом этапе средства, возможные инвестиции в -ое предприятие. Очевидно

 .

1 этап

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

 

 

 

 

 

2 этап

Выделенную сумму 40 млн. руб. распределяем между первым и вторым предприятиями.

Рекуррентное уравнение имеет вид:

 

Поиск ведётся по переменной , которая в зависимости от числа может принимать значения 8; 16; 24; 32; 40, таким образом

 

 

 

 

 

3 этап 

Решается задача распределения средств между тремя предприятиями, рекуррентная формула имеет вид:  

Поиск ведётся по переменной , которая в зависимости от числа может принимать значения 8; 16; 24; 32; 40, таким образом

 

 

 

 

 

4 этап

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

 

Итак, полученный max ожидаемый прирост выпуска продукции равен 216 млн. руб. Необходимо определить, при каких вариантах вложений получен этот результат, для этого нужно пройти от 4 этапа к 1 и проследить, как получено max значение целевой функции. На 4 этапе получен max вариант при , фиксируем это значение переменной. Заметим, что , где - этот результат получен на 3 этапе, при , фиксируем это значение переменной. Заметим, что , где - этот результат получен при . Аналогично получаем , таким образом инвестиции целесообразно выделять первому и четвёртому предприятиям, в количестве 8 и 32 млн. руб. Оптимальный прирост составляет 216 млн. руб.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.1. Расчет целочисленной закупки станков методом ветвей и границ

Администрация фирмы желает увеличить производство своих изделий за счет привлечения дополнительной производственной площади в объеме S м2, а также покупки у машиностроительных фирм современных станков-автоматов по производству аналогичной продукции на сумму С млн.руб. После изучения соответствующих рекламных проспектов, подходящими для покупки признаны автомат фирмы А, занимающий площадь S1м2, имеющий цену С1 млн.руб. и обладающий производительностью Р1 изделий в час; автомат фирмы В, занимающий S2м2, имеющий цену С2 млн.руб. и дающий производительность Р2 изделий в час. В каких количествах нужно приобрести автоматы названных фирм, чтобы созданная дополнительная мощность имела наибольшую производительность?

S=15;

С=94;

S1=1;

С1=5;

Р1=14;

S2=1;

С2=8;

Р2=22.

 

 

Решение:

Пусть x1 – количество станков фирмы А;

           x2 – количество станков фирмы В.

Тогда под стратегией закупки будем понимать вектор удовлетворяющий следующим ограничениям:

• по площади:
• по финансам:

x1, x2  0 – целые числа.

 

Первый этап

 

 

 

x1	0	15
x2	15	0

 

 

x1	0	2
x2	11,75	10,5

 

 

x1	0	11
x2	0	-7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Найдем координаты Хmax –точки пересечения прямых заданных уравнениями:

 

 

 

 

 

 

 

 

 

Второй этап

Ветвление вспомогательной задачи на 4 вспомогательные подзадачи нижнего уровня. Так как полученное решение не целочисленной, то оно дает верхнюю границу F(x) = для максимума целевой функции искомого оптимального решения исходной задачи.

Задача 1.1

 

 

Хmax –точки пересечения прямых:

 

 

 

Задача 1.2

 

 

Хmax –точки пересечения прямых:

 

 

 

Задача 2.1

 

 

Хmax –точки пересечения прямых:

 

 

 

 

Задача 2.2

 

 

Хmax –точки пересечения прямых:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 1.1.1

 

 

Хmax –точки пересечения прямых:

 

 

 

 

 

 

 

 

 

Задача 1.1.2

 

 

Хmax–точки пересечения прямых:

 

 

 

 

 

 

 

Задача 2.2.1

 

 

Хmax –точки пересечения прямых:

 

 

 

 

 

Задача 2.2.2

 

 

 

Данная задача решений не имеет.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 1.1.2.1

 

 

 

 

 

Задача 1.1.2.2

 

 

Данная задача решений не имеет.

 

 

 

 

Задача 2.2.1.1

 

 

 

 

 

Задача 2.2.1.2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 1.1.2.1.1

 

 

 

 

 

Задача 1.1.2.1.2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Нарисуем дерево решений.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ответ:

 

 при . Максимальная производительность всех закупленных станков (260 изделий в час) будет достигнута, если у фирмы А приобрести 6 станков, а у фирмы В - 8 станков.

 

 

 

2.2. Анализ модели расчета производственной программы по разным экономическим критериям

 Администрации компании необходимо установить еженедельную программу производства фасонных отливов А и В, которая дает максимально чистого дохода на один рубль всех сделанных затрат. Отливка А гарантирована реализуется по цене С1 (руб) , отливка В по цене С2 (руб). Расход  электроэнергии на отливку А составляет А11  (кВт-час) , на отливку В составляет А12 (кВт-час), расход угля на А составит А21 кг, а на В - А22 кг. Минимальные затраты электроэнергии и угля, при которых не произойдут остановки литейного производства равны соответственно D1 кВт/час и  D2 кг/нед. Недельный запас компании В1 (кВт-час) и В2 (кг) угля. Себестоимость отливки А и В без учета заработной платы составляет соответственно S1 и S2 (руб).  Сумма оплаты рабочих и служащих компании вместе  с другими рабочими составляет S (тыс. руб.) в неделю. Администрация желает исследовать еженедельный выпуск изделий А и В по трем критериям:

1)максимальный  объем продаж;

2)минимальная  совокупность затрат;

3)максимальность  чистого дохода на рубль всех  сделанных затрат.

C1 = 358,24 

C2 = 154,36

A11 = 4

A12 = 2

A21 = 5

A22 = 5

D1 = 400

D2 = 500

B1 = 800

B2 = 1000

S1 = 285,2

S2 = 150

         S=16,18 

Решение:

Пусть х1 – программа выпуска изделий А; х2 – программа выпуска изделий В.

Под производственной программой понимаем вектор искомых неизвестных х = {х1,х2}.

Ограничения:

400 ≤ 4х1 + 2х2 ≤ 800

500 ≤ 5х1 + 5 х2 ≤1000

х1 ≥ 0, х2 ≥ 0

Приведем систему ограничений к стандартному виду.

 

Целевая функция первой модели выражает ожидаемый объем продаж компании и стремление к максимуму.

 

Решим систему графическим способом.

Х1	150	200
Х2	100	0

 

 

 

2

Х1	0	100
Х2	200	0

 

 

 
3)

Х1	100	0
Х2	100	200

 

 

 

4)

Х1	0	100
Х2	100	0

 

 

 

5)

Х1	0	154,36
Х2	0	-358,24

6)

Х1	0	-0,06
Х2	-0,11	0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

             

          

 

 

 

 

 

Х1* = 200;

Х2* = 0.

Z0 = 71,648 (тыс. руб.).

 

Целевая функция второй модели выражает все понесенные компанией затраты за неделю, которые минимизируются.

 

Х1* = 100;

Х2* = 0.

Z2 = 42 (тыс. руб.).

Чистые доходы компании за неделю это разность ожидаемой выручки и ожидаемых совокупных затрат, т.е.

 

(тыс. руб.).