Задача о распределении средств между предприятиями

Рассмотрим схему решения задач динамического программирования с использованием уравнений Беллмана на примере задачи о распределении средств между предприятиями.

Постановка задачи.

Планируется деятельность трех предприятий на очередной год. Начальные средства s₀, которые следует распределить, составляют 5 усл. ед. Размеры вложения в каждое предприятие кратны 1 усл. ед. Средства x, выделенные предприятию k, приносят в конце года прибыль Функции заданы таблично (табл. 1). При решении подобных задач принято считать, что выполняются следующие предположения:

– прибыль предприятия k не зависит от вложения средств в другие предприятия;

– прибыль выражается в одних условных единицах;

– общая прибыль равна сумме прибылей, полученных от каждого предприятия.

Требуется определить, какое количество средств нужно выделить каждому предприятию, чтобы общая прибыль была наибольшей.

Таблица 1

Эффективность использования средств

x	f1(x)	f2(x)	f3(x)

Построим математическую модель задачи. Обозначим через x_k количество средств, выделенных предприятию k. Общая прибыль равна сумме прибылей предприятий:

(14)

Переменные x_k удовлетворяют следующим ограничениям:

(15)

Требуется найти переменные x₁, x₂, x₃, удовлетворяющие системе ограничений (15), при которых функция (14) достигает максимума.

Особенность модели состоит в том, что хотя ограничения линейные и переменные целочисленные, методы целочисленного линейного программирования применять нельзя, так как функции f_k(x) заданы таблично.

Процесс распределения средств можно рассматривать как трехшаговый, номер шага совпадает с номером предприятия. Выбор переменных x₁, x₂, x₃ – это выбор управления соответственно на 1, 2 и 3 шаге. Конечное состояние процесса распределения , когда все средства вложены в производство.

Графически схема распределения показана на рис. 9.

Рис.9. Схема распределения средств

Z1*(s0)

Z3*(s2)

Z2*(s1)

s0=5

Уравнения состояний имеют вид:

(16)

где s_k – параметр состояния, количество средств, оставшихся после k -го шага, т. е. эти средства остается распределить между (3 – k) оставшимися предприятиями.

Рассмотрим функцию – условную оптимальную прибыль, полученную от предприятий k, (k + 1), …, 3, если между ними оптимальным образом распределялись средства . Допустимые управления на шаге k удовлетворяют условию: .

Уравнения, связывающие оптимальную прибыль на каждом шаге, имеют вид:

(17)

Последовательно решаем уравнения, проводя условную оптимизацию каждого шага.

Решение задачи.

Шаг k=3. В табл. 1 прибыль монотонно возрастает, поэтому все средства, оставшиеся к третьему шагу, следует вложить в предприятие 3 (рис.10).

Z3*(s2)=f3(s2)

Рис.10. Распределение средств на шаге 3

При этом для возможных значений получим:

(18)

Шаг k=2. Делаем все предположения относительно остатка средств ко второму шагу, т. е. после выбора значения величина может принимать значения 0, 1, 2, 3, 4, 5. В зависимости от этого выбираем , находим и сравниваем для разных при фиксированном значения суммы .

Z3*(s2)

Рис.11. Распределение средств на шаге 2

Для каждого наибольшее из этих значений – это условная оптимальная прибыль, получаемая при оптимальном распределении средств между 2-м и 3-м предприятиями (рис.11).

Вычисления записаны в таблице 2. Для каждого значения оптимальные значения и записаны в графах 5 и 6.

Таблица 2

Оптимизация распределения средств при k=2

s1	x2	s2
			0+4=4
		6+0=6
			0+8=8
		6+4=10
		9+0=9
			0+12=12
		6+8=14
		9+4=13
		12+0=12
			0+16=16
		6+12=18
		9+8=17
		12+4=16
		15+0=15
			0+20=20
		6+16=22
		9+12=21
		12+8=20
		15+4=19
		18+0=18

Шаг k=1. Графическое представление шага представлено на рисунке 12. Условная оптимизация проведена в таблице 3.

Z3*(s2)

Z2*(s1)

s0=5

Рис.12. Распределение средств на шаге 1

Например, если , то . Прибыль, полученная от трех предприятий при условии, что 5 единиц средств будут распределены оптимально между оставшимися двумя предприятиями, равна . Значение взято из столбца 5 табл. 2 при . Если , то . Суммарная прибыль при условии оптимального распределения средств равна . Значение взято из исходных данных (табл. 1), значение – из столбца 5 табл. 2 при . Аналогично вычислены остальные значения столбца 4 табл. 3.

Таблица 3

Оптимизация распределения средств при k=1

s0	x1	s1
			0+22=22
		8+18=26
		10+14=24
		12+10=22
		14+6=20
		16+0=16

Оптимальное решение рассматриваемой задачи при выделено в таблице 3 жирным шрифтом. Максимум суммарной прибыли получаем при условии, что первому предприятию выделяется усл. ед. и между 2 и 3 предприятиями распределяются 4 усл. ед. средств. Далее оптимальный вариант распределения находим из табл. 2 при : усл. ед., усл. ед.

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