Динамическое программирование. Запись соответствующих функциональных уравнений Бэллмана

Министерство образования и науки Российской Федерации

Новосибирский государственный технический университет

Кафедра экономической информатики

Расчетно-графическая работа №4

на тему:

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

по дисциплине: «Методы оптимизации»

Вариант №7

Факультет: Бизнеса

Группа:

Студенты:

Преподаватель:

Новосибирск

2004

Условие задачи:

Коммерческая фирма закупила товары четырех наименований А₁, А₂, А₃, А₄ по 10 упаковок каждого за пределами своего города. Доставку товаров предполагается осуществить собственным автофургоном за несколько рейсов. Грузоподъемность фургона составляет W кг. Вес одной упаковки товара каждого наименования равен соответственно w₁, w₂, w₃, w₄ кг, а стоимость – с₁, с₂, с₃, с₄ тыс. руб.

Определить, какие виды товаров и в каком количестве необходимо перевезти первым рейсом, с тем, чтобы их стоимость была максимальной.

Задание:

Рассматривая задачу как модель динамического программирования, записать соответствующие функциональные уравнения Бэллмана.

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

V	V1	V2	V3	V4	C1	C2	C3	C4
20	11	9	7	15	520	470	350	640

Математическая модель задачи:

Строим целевую функцию:  Z=520x₁ + 470x₂ + 350x₃ +640x₄ ® max

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

          11x₁ + 9x₂ + 7x₃ + 15x₄ <= 20,

           x₂ <=10

           x₃ <=10

           x₁, x₂, x₃, x₄ >= 0 и целые

Определяем границы переменных:

0 <= x1 <= 20/11 = 1;

0 <= x2 <= 20/9 = 2;

0 <= x3 <= 20/7 = 2;

0 <= x4 <= 20/15 = 1;

Wi	f1	x1	f2	x2	f3	x3	f4	x4
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0
5	0	0	0	0	0	0	0	0
6	0	0	0	0	0	0	0	0
7	0	0	0	0	350	1	0	0
8	0	0	0	0	350	1	0	0
9	0	0	470	1	350	1	0	0
10	0	0	470	1	350	1	0	0
11	520	1	470	1	350	1	0	0
12	520	1	470	1	350	1	0	0
13	520	1	470	1	350	1	0	0
14	520	1	470	1	700	2	0	0
15	520	1	470	1	700	2	640	1
16	520	1	470	1	700	2	640	1
17	520	1	470	1	700	2	640	1
18	520	1	940	2	700	2	640	1
19	520	1	940	2	700	2	640	1
20	520	1	940	2	700	2	640	1

1) На первом этапе мы заполняем фургон только товарами первого типа:

F1(w) = max z1(w1) = c1*x1= 520;

2) На втором шаге заполняем грузовик товарами 1-го и 2-го типа:

F2(w) = max [f2(x2) + F1(x –x2);

F2(0) = f2(0) + F1(0) = 0;

F2(1) =    f2(0) + F1(1) = 0;

                f2(1) + F1(0) = 0;               

F2(2) =    f2(0) + F1(2) = 0;

                f2(1) + F1(1) = 0;

                f2(2) + F1(0) = 0;

F2(3) =    f2(1) + F1(2) = 0;

                f2(0) + F1(3) = 0;

                f2(3) + F1(0) = 0;

                f2(2) + F1(1) = 0;

F2(4) =    f2(2) + F1(2) = 0;

                f2(0) + F1(4) = 0;

                f2(4) + F1(0) = 0;

                f2(2) + F1(2) = 0;

                f2(1) + F1(3) = 0;

                f2(3) + F1(1) = 0;

Только условно-оптимальные уравнения

F2(5) = 0

F2(6) = 0

F2(7) = 0

F2(8) = 0  

F2(9) =  f2(9) + F1(0) = 470;

F2(10) = 470;

F2(11) =     f2(0) + F1(11) = 520;

F2(12)       f2(0) + F1(11) = 520;

F2(13) =    520;

F2(14) =    520;

F2(15) =    520;

F2(16) =    520;

F2(17) =    520;

F2(18) = f2(18) + F1(0) =940

F2(19) =    940;

F2(20) = f2(9) + F1(11)=990;

3) На третьем  шаге заполняем грузовик товарами 1-го,  2-го и 3-го типа:

F3(w) = max [f3(w3) + F2(w –w3)];

F3(0)=0

F3(1)=0

F3(2)=0

F3(3)=0

F3(4)=0

F3(5)=0

F3(6)=0

F3(7)=f3(7)+F2(0)=350

F3(8)=350

F3(9)=f3(0)+F2(9)=470

F3(10)= 470

F3(11)=f3(0)+F2(11)=520

F3(12)= 470

F3(13)= 470

F3(14)=f3(14)+F2(0)=700

F3(15)= 700

F3(16)= 700

F3(17)= 700

F3(18)=f3(0)+F2(18)=940

F3(19)= 940

F3(20)=f3(0)+F2(18)=990

4) На третьем  шаге заполняем грузовик товарами 1-го,  2-го, 3-го и 4-го типа:

F4(20) =    F3(0) + f4(20) = 640;

                  F3(1) + f4(19) = 640;

                  F3(2) + f4(18) = 640;

                  F3(3) + f4(17) = 640;

                  F3(4) + f4(16) = 640;

                  F3(5) + f4(15) = 640;

                  F3(6) + f4(14) = 0;

                  F3(7) + f4(13) = 350;

                  F3(8) + f4(12) = 350;

                  F3(9) + f4(11) = 470;

                  F3(10) +f4(10) = 470;

                  F3(11) + f4(9) = 520;

                  F3(12) + f4(8) = 470;

                  F3(13) + f4(7) = 470;

                  F3(14) + f4(6) = 700;

                  F3(15) + f4(5) = 700;

                  F3(16) + f4(4) = 700;

                  F3(17) + f4(3) = 700;

                  F3(18) + f4(2) = 940;

                  F3(19) + f4(1) = 940;

                  F3(20) + f4(0) = 990;

Выберем вариант х* = (11, 9, 0, 0), хотя возможны и другие, следовательно, наиболее выгодно перевозить товары только первого и второго типов, и максимальная величина целевой функции равна 990.

Решим задачу как задачу целочисленного линейного программирования с помощью ПЭР, методом ветвей и границ:

┌─────────────────────────────────────────────────────────────────┐

 │                  ИТОГОВЫЙ РЕЗУЛЬТАТ для 123     Стр. : 1        │

 ╞═════════╤══════════╤═══════════╦═════════╤══════════╤═══════════╡

 │Переменн.│          │Целев.ф-ия.║Переменн.│          │Целев.ф-ия.│

 │No. Имена│ Решение  │Коэффициент║No. Имена│ Решение  │Коэффициент│

 ╞═════════╪══════════╪═══════════╬═════════╪══════════╪═══════════╡

 │1   X1   │     1.000│   520.000 ║3   X3   │     0.000│   350.000 │

 │2   X2   │     1.000│   470.000 ║4   X4   │     0.000│   640.000 │

 ╞═════════╧══════════╧═══════════╩═════════╧══════════╧═══════════╡

 │       MAX   величина цел.ф-и =  990  Всего итераций   = 5       │

 └─────────────────────────────────────────────────────────────────┘

 Полученное с помощью ПЭР решение полностью совпадает с найденным вручную, что говорит о правильности произведенных выше расчетов.