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

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

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

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

Выделенные средства xi, млн. ден. ед.	Предприятие
Получаемый доход, млн. ден. ед.

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

(2.1)

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

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

Пусть теперь 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+9	11+0
	0+18	11+9	19+0
	0+24	11+18	19+9	30+0

Для каждого значения (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+11	16+0
	0+20	16+11	32+0
	0+30	16+20	32+11	40+0

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

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

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

с\x
	0+16	13+0
	0+32	13+16	27+0
	0+43	13+32	27+16	44+0

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

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

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

Ответ: максимальный дополнительный доход на четырех предприятиях при распределении между ними 60 млн. ден. ед. составляет 45 млн. ден. ед. и будет получен, если первому и второму предприятию средств не выделять, третьему 40 млн. ден. ед., а четвертому 20 млн. ден. ед.