35. Задача оптимального распределения ресурса по потребителям, для которых заданы производственные функции по используемому ресурсу. Задача динамического программирования.

Филиал выпускает 3 вида продукции. Основным ресурсом, определяющим выпуск этой продукции, является денежный ресурс, который расходуется на затратные статьи производства.

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

2.1. Обозначения задачи

Z [у.д.е] – прибыль, получаемая филиалом;

X_i[ед.] – объемы производства i-ой продукции;

C_i[у.д.е./ед.] – прибыль от реализации единицы i-ой продукции;

S_i[у.д.е./ед.] – затраты на производство единицы i-ой продукции;

m_i[ед.] – максимальный объем производства i-ой продукции;

Д_i[у.д.е.] – располагаемый денежный ресурс филиала.

2.2. Запись исходной формы задачи

Исходная форма задачи с данными по варианту:

Преобразовав, получим:

2.3. Запись задачи в канонической форме

Для перехода к канонической форме необходимо от ограничения неравенств перейти к ограничениям равенств. Для этого в каждое ограничение неравенства ввести дополнительную переменную [±d_i].

2.4. Симплексная таблица

1	Сj		0	7	6	5	0	0	0	0
Ci			x0	x1	x2	x3	d1	d2	d3	dД
			0	1	2	3	4	5	6	7
	dД	1	Д	5	6	7	0	0	0	1
	d1	2	21	1	0	0	1	0	0	0
	d2	3	31	0	1	0	0	1	0	0
	d3	4	41	0	0	1	0	0	1	0

Д = 0 у.д.е

Д=10⁶ у.д.е

Проверка работоспособности модели

Любая модель должна быть обязательно проверена серией расчетов. Исходные данные для расчетов должны взяты такими, чтобы результаты расчета были очевидны и понятны.

Число необходимых контрольных расчетов определяется сложностью модели.

Расчет № 1. В этом расчете располагаемый денежный ресурс примем равным 0 (Д=0 у.д.е).

В результате расчета получим: Х₁ = 0

Х₂ = 0

Х₃ = 0

Расчет № 2. Денежный ресурс берем равным Д = 10⁶ у.д.е. (заведомо завышенный объем денежного ресурса, который полностью не может быть использован).

Z= 538 у.д.е.

d_Д = 999422 у.д.е.

Указанных расчетов достаточно для проверки модели

Построение производственной функции (ПФ)

В данном случае под производственной функцией будем понимать функцию зависимости прибыли от располагаемого денежного ресурса.

Аргументом функции будет являться денежный ресурс. Производственную функцию необходимо построить для всех значений аргументов, определенных на отрезке [0;Д_max], где Д_max – объем денежного ресурса, позволяющего 100% загрузить производство.

Для определения Д_max необходимо воспользоваться результатами 2-го контрольного расчета).

В этом расчете Д_max = 10⁶ у.д.е. В результате расчета d_Д≠0.

Дополнительная переменная ресурсного ограничения, отличная от 0, - это неиспользованный объем ресурса.

Д_max = 1,1∙(10⁶ – d_Д)

Д_max = 1,1∙(10⁶ – 999422)=635,8

2.7. Расчеты для построения производственной функции (ПФ)

Для расчета ПФ выберем шаг изменения аргумента

=

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

Филиал №1

Д	0	64	128	192	256	320	384	448	512	576	640
Z	0	89,6	170	234	298	353,71	399,43	445,14	490,86	536,57	538

Филиал №2

Д	0	64	128	192	256	320	384	448	512	576	640
Z	0	98,56	187	257,4	327,8	389,081	439,373	489,654	539,946	590,227	591,8

Филиал №3

Д	0	64	128	192	256	320	384	448	512	576	640
Z	0	80,64	153	210,6	268,2	318,34	359,49	400,63	441,774	482,913	484,2

2.8. Построение линии тренда или нахождение аналитического вида производственной функции (ПФ)

2.9. Уточнение производственного плана для первого филиала, согласованное с распределением денег между филиалами

Используя в Excel команду «поиск решения» получив аналитическое выражение ПФ, будем считать, что в результате получилось следующее распределение денег между филиалами

1 филиал – 0,4*3*G_max=0,4*3*635,8=762,96 у.д.е.

2 филиал – 0,3*3*G_max=0,3*3*635,8=572,22 у.д.е

3 филиал – 0,3*3*G_max=0,3*3*635,8=572,22 у.д.е.

G_max=Д_max=635,8 у.д.е.

Возьмем ЭММ 1-го филиала и подставим денежный ресурс 0,4*3*G_max = 762,96 у.д.е. Заново решив оптимальную задачу, получим следующие результаты:

Прибыль – 538у.д.е.

Объем производства:

• X₁ – 21 ед.

• X₂ – 31 ед.

• X₃ – 41 ед.

Динамическое программирование в математике и теории вычислительных систем — метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами, который намного эффективнее, чем решение «в лоб»