Исследование операций. Линейное, динамическое программирование



         

Исследование операций - часть 83


/p>

условного оптимального управления, во втором — условного оптимального выигрыша. Таблица заполняется слева направо, сверху вниз. Решение на пятом — последнем — шаге вынужденное: выделяются все средства;

па всех остальных шагах решение приходится оптимизировать. В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W* за всю операцию — в данном случае он равен 5,6. В последних двух столбцах таблицы 13.2 заполнена только одна строка, так, как состояние системы перед началом первого шага нам в точности известно:

 S0 = К = 10. Оптимальные управления на всех шагах выделены рамкой. Таким образом, мы получили окончательный вывод: надо выделить первому предприятию две единицы из десяти, второму — пять единиц, третьему — две, четвертому — ни одной, пятому — одну единицу. При этом распределении доход будет максимален и равен 5,6.

Чтобы читателю было понятно, как заполняется таблица 13.2, продемонстрируем это на одном образце расчета. Пусть, например, нам нужно оптимизировать решение х3(7)—как поступать на третьем шаге, если мы подошли к нему с запасом средств S = 7, и сколько максимум мы можем выиграть на всех оставшихся

Таблица 13.3

x

7 - x

W4(7 - x)

+W4(7 - x)

7

6

5

4

3

1

0

0

1

2

3

4

5

6

7

1,8

1,7

1,6

1,4

1,2

1,1

0,6

0

0

1,0

1,3

1,6

2,3

2,5

2,6

2,7

1,8

2,7

2,9

3,0

3,5

3,2

2,7

шагах, включая третий? Предположим, что все шаги после третьего (4-й и 5-й) уже оптимизированы, т. е. заполнены две первые пары столбцов таблицы 13.2. Найдем x3(7) и W3(7). Для этого составим вспомогательную табличку (см. таблицу 13.3). В первом ее столбце перечислены все возможные вложения х на третьем шаге, не превосходящие S = 7.

Во втором столбце — то, что останется после такого вложения от запаса средств S = 7. В третьем столбце — выигрыш на третьем шаге от вложения средств х




Содержание  Назад  Вперед