Оптимальное распределение средств на расширение производства (стр. 2 из 3)

1) Записать функциональное уравнение для последнего состояния процесса (ему соответствует

):

;(1.4)

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.

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

с\x	0	20	40	60
20	0+11	16+0	16	20
40	0+20	16+11	32+0	32	40
60	0+30	16+20	32+11	40+0	43	40

Расчёт значений

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

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

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

с\x	0	20	40	60
20	0+16	13+0	16	0
40	0+32	13+16	27+0	32	0
60	0+43	13+32	27+16	44+0	45	20

Составим сводную таблицу, на основе расчетов таблиц, начиная с 2.2.

Таблица 2.6 – Сводная таблица

20	9	11	20	16	20	16	0
40	18	20	20	32	40	32	0
60	24	30	60	43	40	45	20

Из табл. 2.6 видно, что наибольший дополнительный доход, который могут дать четыре предприятия при распределении 60 млн. ден. ед. (с=60), составляет 45 млн. ден. ед. (

). При этом четвертому предприятию должно быть выделено 20 млн. ден. ед. ( ), а остальным трем – 60-20=40 млн. ден. ед. Из этой же таблицы видно, что оптимальное распределение оставшихся 40 млн. ден. ед. (с=40) между тремя предприятиями обеспечит общий дополнительный доход на них на сумму 32 млн. ден. ед. ( ) при условии, что третьему предприятию будет выделено 40 млн. ден. ед. ( ), а на долю второго и третьего средств не останется (40-40=0).