2) Найти из дискретного набора его значений при некоторых фиксированных и из соответствующих допустимых областей ( так как , то ). В результате после первого шага известно решение и соответствующее значение функции ;

3) Уменьшить значение на единицу и записать соответствующее функциональное уравнение. При оно имеет вид:

;(1.5)

4) Найти условно-оптимальное решение на основе выражения (1.5);

5) Проверить, чему равно значение . Если расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если перейти к выполнению п. 3;

6) Вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу.[1, с 244]

2. Решение задачи оптимального распределения средств на расширение производства

2.1 Решение задачи оптимального распределения средств на расширение производства ручным способом

Широкий класс составляют задачи, в которых речь идет о наиболее целесообразном распределении во времени тех или иных ресурсов (денежных средств, рабочей силы, сырья и т.п.). Рассмотрим пример задачи такого рода.

Производственному объединению из четырех предприятий выделяется банковский кредит в сумме 60 млн. ден. ед. для реконструкции и модернизации производства с целью увеличения выпуска продукции. Значения дополнительного дохода, получаемого на предприятиях объединения в зависимости от выделенной суммы xi, приведены в табл. 2.1. Распределить выделенный кредит между предприятиями так, чтобы дополнительный доход объединения был максимальным.[1, с 261]

Таблица 2.1 – Значения дополнительного дохода

Выделенные средства xi, млн. ден. ед.	Предприятие
	Получаемый доход, млн. ден. ед.
0 20 40 60	0 9 18 24	0 11 19 30	0 16 32 40	0 13 27 44

Решение. Пусть n=1. В соответствии с вычислительной схемой динамического программирования рассмотрим сначала случай n=1, т.е. предположим, что все имеющиеся средства выделяются на реконструкцию и модернизацию одного предприятия. Обозначим через ¦1(x) максимально возможный дополнительный доход на этом предприятии, соответствующий выделенной сумме x. Каждому значению x отвечает вполне определенное (единственное) значение дополнительного дохода, поэтому можно записать, что:

(2.1)

В соответствии с формулой (2.1) в зависимости от начальной суммы с поучаем с учетом табл. 2.1 значения ¦1(с), помещенные в табл. 2.2.

Таблица 2.2 – Значения максимально возможного дополнительного дохода в зависимости от выделенных средств

0	0
20	9
40	18
60	24

Пусть теперь n=2, т.е. средства распределяются между двумя предприятиями. Если второму предприятию выделена сумма x, то дополнительный доход на нем составит g2(x). Оставшиеся другому предприятию средства (c-x) в зависимости от величины x (а значит, и c-x) позволят увеличить дополнительный доход до максимально возможного значения ¦1(c-x). При этом условии общий дополнительный доход на двух предприятиях:

(2.2)

Оптимальному значению ¦2(с) дополнительного дохода при распределении суммы с между двумя предприятиями соответствует такое x, при котором сумма (2.2) максимальна.

Это можно выразить записью:

(2.3)

Значение можно вычислить, если известны значения , и т.д.

Функциональное уравнение Беллмана для рассматриваемой задачи запишется в следующем виде:

(2.4)

Очередная задача – найти значения функции (2.3) для всех допустимых комбинаций с и x. Для упрощения расчетов значения x будем принимать кратными 20 тыс. ден. ед. и для большей наглядности записи оформлять в виде таблиц. Каждому шагу будет соответствовать своя таблица. Рассматриваемому шагу соответствует табл. 2.3.

Таблица 2.3 – Значения функции на втором шаге

с\x	0	20	40	60
20	0+9	11+0	11	20
40	0+18	11+9	19+0	20	20
60	0+24	11+18	19+9	30+0	30	60

Для каждого значения (20,40,60) начальной суммы с распределяемых средств в табл. 2.2 предусмотрена отдельная строка, а для каждого возможного значения x (0,20,40,60) распределяемой суммы – столбец. Некоторые клетки таблицы останутся незаполненными, так как соответствуют недопустимым сочетаниям с и x.

В каждую клетку таблицы будем вписывать значение суммы (2.2). Первое слагаемое берем из условий задачи (см.табл.2.1), второе – из табл.2.2.

В двух последних столбцах таблицы проставлены максимальный по строке дополнительный доход (в столбце ) и соответствующая ему оптимальная сумма средств, выделенная второму предприятию (в столбце ).

Расчет значений приведен в табл. 2.4. Здесь использована формула, получающаяся из (2.4) при n=3:

Первое слагаемое в табл. 2.4 взято из табл. 2.1, второе из табл. 2.3.