Оптимальное распределение ресурсов

Для решения применим принцип оптимальности Р. Беллмана:
fnc=max0≤x≤cgnx+fn-1c-x.
где c – средства, которые распределяются между n предприятиями;
gnx – возможный прирост выпуска продукции -го предприятия в зависимости от выделенной ему суммы x0≤x≤c;
fnc – общий прирост выпуска продукции на n предприятиях.
В данной задаче ДП распределяем средства c=30 тысяч рублей на три предприятия n=3.
Рассмотрим случай при n=1. Распределим средства c на одно первое предприятие.
Общий прирост выпуска продукции на одном предприятии (из таблицы берем значения g1x):
f1c=max0≤x≤cg1x,
где x – средства, которые достаются первому предприятиями.
c
f1c
x1*c
50 g150
50
100 g1100
100
150 g1150
150
200 g1200
200
250 g1250
250
Таблица 2.
c
f1c
x1*c
50 8 50
100 18 100
150 23 150
200 28 200
250 40 250
Рассмотрим случай при n=2. Распределим средства c на два предприятия: первое и второе.
Общий прирост выпуска продукции на первом и втором предприятиях:
f2c=max0≤x≤cg2x+f1c-x,
где x – средства, которые достаются второму предприятиями;
c-x – – средства, которые достаются первому предприятию.
Таблица 3.
x
c
0 50 100 150 200 250 f2c
x2*c
50 0 + 8 12 + 0
12 50
100 0 + 18 12 + 8 15 + 0
20 50
150 0 + 23 12 + 18 15 + 8 22 + 0
30 50
200 0 + 28 12 + 23 15 + 18 22 + 8 33 + 0
35 50
250 0 + 40 12 + 28 15 + 23 22 + 18 33 + 8 39 + 0 41 200
Рассмотрим случай при n=3. Распределим средства c на три предприятия: первое, второе и третье.
Общий прирост выпуска продукции на первом, втором и третьем предприятиях:
f3c=max0≤x≤cg3x+f2c-x,
где x – средства, которые достаются третьему предприятиями;
c-x – – средства, которые достаются первому и второму предприятиям.
Таблица 4.
x
c
0 50 100 150 200 250 f3c
x3*c
50 0 + 12 7 + 0
12 0
100 0 + 20 7 + 12 16 + 0
20 0
150 0 + 30 7 + 20 16 + 12 20 + 0
30 0
200 0 + 35 7 + 30 16 + 20 20 + 12 29 + 0
37 50
250 0 + 41 7 + 35 16 + 30 20 + 20 29 + 12 41 + 0 46 100
Рассмотрим случай при n=4. Распределим средства c на все предприятия: первое, второе, третье и четвертое.
Общий прирост выпуска продукции всех четырех предприятиях:
f4c=max0≤x≤cg4x+f3c-x,
где x – средства, которые достаются четвертому предприятиями;
c-x – средства, которые достаются первому, второму и третьему предприятиям.
Таблица 5.
x
c
0 50 100 150 200 250 f4c
x4*c
50 0 + 12 11 + 0
12 0
100 0 + 20 11 + 12 17 + 0
22 50
150 0 + 30 11 + 20 17 + 12 23 + 0
31 50
200 0 + 37 11 + 30 17 + 20 23 + 12 30 + 0
41 50
250 0 + 46 11 + 37 17 + 30 23 + 20 30 + 12 38 + 0 48 50
Максимальный прирост выпуска продукции на четырех предприятиях при распределении между ними c=250 млн . рублей составляет:
f4250=48 млн. рублей.
Теперь распределим средства c=250 млн. рублей на четыре предприятия:
x1*c+x2*c+x3*c+x4*c=250.
Так как при решении в таблице 5 в последней строке x4*250 принимает одно значения 50, то будет один вариант распределения.
1 вариант распределения
Четвертому предприятию из общей суммы c=250 млн. рублей дадим:
x4*250=50 млн. рублей
Следовательно, на первое, второе и третье предприятия остается из 250 млн. рублей:
250-50=200 млн. рублей
Третьему предприятию из общей суммы c=200 млн. рублей дадим:
x3*200=50 млн. рублей
Следовательно, на первое и второе предприятия остается:
200-50=150 млн. рублей
Второму предприятию из суммы c=150 млн. рублей дадим:
x2*150=50 млн. рублей
Первому предприятию достается остаток:
150-50=100 млн. рублей
x1*100=100 млн. рублей
Ответ: Сумму c=250 миллионов рублей можно распределить между четырьмя предприятиями одним способом 100;50;50;50 при этом прибыль для распределения будет равной fmax=48 млн. рублей.
Контрольные вопросы к зачёту по теме «Динамическое программирование»
1. Какие задачи решаются методом динамического программирования?
Метод динамического программирования – это инструмент, позволяющий быстро находить оптимальное решение в задачах математического программирования с дискретным множеством допустимых управлений, т. е. в ситуациях, когда имеется некоторое количество различных вариантов поведения, приносящих разные результаты, среди которых необходимо выбрать наилучший. Любая задача такого рода может быть решена путём перебора всех возможных вариантов и выбора среди них наилучшего