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




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


Поэтому условное оптимальное управление на m-м шаге: отдать последнему предприятию все имеющиеся средства S, т. е.

xm(S)=S,

а условный оптимальный выигрыш

Wm

(S)=

(S).

Задаваясь целой гаммой значений S

(располагая их достаточно тесно), мы для каждого значения S будем знать xm(S) и Wm(S). Последний шаг оптимизирован.

Перейдем к предпоследнему, (т— 1)-му шагу. Пусть мы подошли к нему с запасом средств S. Обозначим Wm-1(S) условный оптимальный выигрыш на двух последних шагах: (m - 1)-м и m-м (который уже оптимизирован). Если мы выделим на (m - 1)-м шаге (m - 1)-му предприятию средства х, то на последний шаг останется S — х. Наш выигрыш на двух последних шагах будет равен

,

и нужно найти такое х, при котором этот выигрыш максимален:

               (13.2)

 

Знак

 означает, что берется максимальное значение по всем х, какие только возможны (вложить больше, чем S, мы не можем), от выражения, стоящего в фигурных скобках. Этот максимум и есть условный оптимальный выигрыш за два последних шага, а то значение х, при котором этот максимум достигается,— условное оптимальное управление на (т—1)-м шаге.

Далее оптимизируем (т—2)-й, (т—3)-й и т. д. шаги. Вообще, для любого i-го шага будем находить условный оптимальный выигрыш за все шаги с этого и до конца по формуле

     (13.3)

 

и соответствующее ему условное оптимальное управление xi(S) — то значение х, при котором этот максимум достигается.

Продолжая таким образом, дойдем, наконец, до 1-го предприятия П1. Здесь нам не нужно будет варьировать значения S;

мы точно знаем, что запас средств перед первым шагом равен К:

.       (13.4)

 

Итак, максимальный выигрыш (доход) от всех предприятий найден. Теперь остается только «прочесть рекомендации». То значение х,

при котором достигается максимум (13.4), и есть оптимальное управление

 на 1-м шаге. После того как мы вложим эти средства в 1-е предприятие, у пас их останется К—
. «Читая» рекомендацию для этого значения S, выделяем второму предприятию оптимальное количество средств:




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