Решение задач оптимизации на основе метода динамического программирования

переходит операция распределения средств в результате принятия каждого решения (после выделения средств первому, второму и третьему предприятию), S₃=S₂-U₃. Для каждого состояния S₃ по таблице решения шага 4 находим условно-оптимальное значение критерия эффективности для четвертого шага, т.е. прибыль четвертого предприятия E₄^* от выделенных ему средств в размере S₃. Находим критерий эффективности операции на третьем и четвертом шаге (суммарная прибыль третьего и четвертого предприятий) E₃=Z₃+ E₄^*. По максимальному значению E₃ находим условно-оптимальное значение критерия эффективности для третьего и четвертого шагов – U₃^*. Здесь U₃^* - денежные средства, которые следует выделить предприятию П3 при наличии суммы S₂. E₃^* - условно оптимальный критерий эффективности для предприятий П3 и П4, т.е. прибыль, получаемая этими предприятиями в результате решения U₃^*.

Таблица 3

Шаг 2

Находим всевозможные состояния в начале второго шага (S₁) – остаток средств после их выделения первому предприятию. Для каждого из них находим все допустимые решения U₂. Для каждого решения находится критерий эффективности для данного шага Z₂ – прибыль второго предприятия от выделения ему средств в размере U₂. Находим состояния, в которые  переходит операция распределения средств в результате принятия каждого решения (остатки средств после их выделения первому и второму предприятиям): S₂=S₁-U₂. Для каждого состояния S₂ по таблице из шага 3 находим условно-оптимальное значение критерия эффективности для третьего шага E₃^* - прибыль четвертого и третьего предприятий при условии, что им будет выделена сумма S₂. Находим критерий эффективности на втором и третьем шаге (суммарная прибыль второго, третьего и четвертого предприятий), соответствующий каждому состоянию S₁ и решению U₂: E₂=Z₂+E₃^*. ПО максимальному значению E₂ для каждого состояния S₁ находится условно-оптимальное значение критерия эффективности для второго, третьего и четвертого шагов E₂^*. Здесь U₂^* - средства, которые следует выделить второму предприятию, если имеется сумма в размере S₁; E₂^* - суммарная прибыль второго, третьего и четвертого предприятий, при условии, что сумма S₁ будет разделена между ними оптимальным образом.

Таблица 4

Шаг 1

Состояние в начале первого шага известно: S₀=60 млн. д.е. Для состояния S₀ находятся  все допустимые решения U₁, т.е. возможные варианты выделения средств первому предприятию. Для каждого решения находим критерий эффективности данного шага Z₁ – прибыль первого предприятия при выделении ему средств в размере U₁. Для каждого решения находится соответствующее ему состояние в конце первого шага, т.е. остаток средств после выделения их ему первому предприятию: S₁=S₀-U₁. Для каждого состояния S₁ по таблице из шага 2 находится условно-оптимальное значение критерия эффективности для второго, третьего и четвертого шагов E₂^*, т.е. суммарная прибыль второго, третьего и четвертого предприятий при выделении им средств в размере S₁. Находим критерий эффективности операции на всех четырех шагах (суммарная прибыль всех четырех предприятий), соответствующий состоянию S₀ и каждому из решений U₁: E₁=Z₁+E₂^*. По максимальному значению E₁ находится оптимальное решение U₁^* - денежные средства, которые следует выделить первому предприятию; E₁^* - суммарная прибыль всех четырех предприятий, при условии, что имеющаяся сумма в размере