Метод динамического программирования

Для развития трех торговых предприятий выделено 4 млн. руб. Известна эффективность капитальных вложений в каждое предприятие, заданное значением нелинейной функции ?k(xk). Требуется составить оптимальный план распределения капитальных вложений между предприятиями. Предполагается, что распределение денежных средств проводится в целых числах xk, xk = 0, 1, 2, 3, 4.

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

f1

f2

f3

xi

0

0

0

0

3.1

2.4

1.7

1

3.2

2.8

1.9

2

4.5

3

2.2

3

6.4

4.4

3

4

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

I этап. Условная оптимизация.

1-ый шаг. k = 3.

e2

u3

e3 = e2 - u3

f3(u3)

F*3(e3)

u3(e3)

1

0

1

0

1

0

1.7

1.7

1

2

0

2

0

1

1

1.7

2

0

1.9

1.9

2

3

0

3

0

1

2

1.7

2

1

1.9

3

0

2.2

2.2

3

4

0

4

0

1

3

1.7

2

2

1.9

3

1

2.2

4

0

3

3

4

2-ый шаг. k = 2.

e1

u2

e2 = e1 - u2

f2(u2)

F*2(e1)

F1(u2,e1)

F*2(e2)

u2(e2)

1

0

1

0

1.7

1.7

1

0

2.4

0

2.4

2.4

1

2

0

2

0

1.9

1.9

1

1

2.4

1.7

4.1

4.1

1

2

0

2.8

0

2.8

3

0

3

0

2.2

2.2

1

2

2.4

1.9

4.3

2

1

2.8

1.7

4.5

4.5

2

3

0

3

0

3

4

0

4

0

3

3

1

3

2.4

2.2

4.6

2

2

2.8

1.9

4.7

3

1

3

1.7

4.7

4.7

3

4

0

4.4

0

4.4

3-ый шаг. k = 1.

e0

u1

e1 = e0 - u1

f1(u1)

F*1(e0)

F0(u1,e0)

F*1(e1)

u1(e1)

1

0

1

0

2.4

2.4

1

0

3.1

0

3.1

3.1

1

2

0

2

0

4.1

4.1

1

1

3.1

2.4

5.5

5.5

1

2

0

3.2

0

3.2

3

0

3

0

4.5

4.5

1

2

3.1

4.1

7.2

7.2

1

2

1

3.2

2.4

5.6

3

0

4.5

0

4.5

4

0

4

0

4.7

4.7

1

3

3.1

4.5

7.6

7.6

1

2

2

3.2

4.1

7.3

3

1

4.5

2.4

6.9

4

0

6.4

0

6.4

Поясним построение таблиц и последовательность проведения расчетов.

Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).

В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.

Этап II. Безусловная оптимизация.

Из таблицы 3-го шага имеем F*3(e0 = 4) = 7.6. То есть максимальный доход всей системы при количестве средств e0 = 4 равен 7.6 млн. руб.

Из этой же таблицы получаем, что первому торговому предприятию следует выделить u*1(e0 = 4) = 1

При этом остаток средств составит:

e1 = e0 - u1

e1 = 4 - 1 = 3

Из таблицы 2-го шага имеем F*2(e1 = 3) = 4.5. То есть максимальный доход всей системы при количестве средств e1 = 3 равен 4.5 млн. руб.

Из этой же таблицы получаем, что второму торговому предприятию следует выделить u*2(e1 = 3) = 2

При этом остаток средств составит:

e2 = e1 - u2

e2 = 3 - 2 = 1

Последнему торговому предприятию достается 1 млн. руб..

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

1-му торговому предприятию выделить 1;

2-му торговому предприятию выделить 2;

3-му торговому предприятию выделить 1;

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

Перейти к онлайн решению своей задачи

загрузка...