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

Страницы работы

5 страниц (Word-файл)

Содержание работы

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

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

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

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

на тему:

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

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

Вариант №7

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

Группа:

Студенты:

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

Новосибирск

2004

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

Коммерческая фирма закупила товары четырех наименований А1, А2, А3, А4 по 10 упаковок каждого за пределами своего города. Доставку товаров предполагается осуществить собственным автофургоном за несколько рейсов. Грузоподъемность фургона составляет W кг. Вес одной упаковки товара каждого наименования равен соответственно w1, w2, w3, w4 кг, а стоимость – с1, с2, с3, с4 тыс. руб.

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

Задание:

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

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

V

V1

V2

V3

V4

C1

C2

C3

C4

20

11

9

7

15

520

470

350

640

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

Строим целевую функцию:  Z=520x1 + 470x2 + 350x3 +640x4 ® max

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

          11x1 + 9x2 + 7x3 + 15x4 <= 20,

           x2 <=10

           x3 <=10

           x1, x2, x3, x4 >= 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       │

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

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

Похожие материалы

Информация о работе

Тип:
Расчетно-графические работы
Размер файла:
66 Kb
Скачали:
0