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

Рассмотрим предложенную выше схему на конкретной задаче

0 распределении средств между предприятиями.

^ 12.1.Планируется деятельность четырех промышленных пред­приятий (системы) на очередной год. Начальные средства: s₀ = = 5 усл. ед. Размеры вложения в каждое предприятие кратны

1 усл. ед. Средства х, выделенные к-му предприятию (к=\, 2, 3, 4),
приносят в конце года прибыль /_к(х). Функции f_k(x) заданы таб­
лично (табл. 12.1). Принято считать, что:

а) прибыль f_k (x) не зависит от вложения средств в другие
предприятия;

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

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

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

' Здесь описан способ решения задачи ДП, начинающийся с послед­него шага ("обратная схема"). Можно л-й и 1-й шаги поменять местами ("прямая схема").

¹ Через s_k здесь обозначено состояние системы после к-то шага при условии, что на к-м шаге выбрано оптимальное управление.

Модели динамического программирования

где ^ — параметр состояния — количество средств, оставшихся после к-го шага, т.е. средства, которые остается распределить ме­жду оставшимися А—к предприятиями.

* - - - п и _с. ^оозначим через х, количеств -—

ных *-му предприятию. (Нуме_РациГпред_Пп„ ^СРедс*в, вь,_п храняем в процессе решения" неизменной? ^РИЯТИЙ 1, 2, *^

' ^н Со-

^Z=IA(**).

*=1 ₍₁₂

Переменные х удовлетворяют ограничениям: "^

2>* =5,

4=1

*** О,* = 1,2Д4.

⁽¹²И)

Требуется найти переменные х, _х? х, г системе ограничении _(Ш1) „ _o6pa'--. «М*^

Особяшсш модели. Ограничения линейные *^Ю

„.„„,, ' ч^пмшил W заданы таблична ^ueP^eMe_Hu

применить методы целочисленного линейн^-^У £*

Схема решения задачи методом ДП имеет слеях ^ММИр°*а-

цесс решения распределения средств Д"uLZ^"* mur 4-шаговый, номер _шага совпадет с шмерГ^_пГ^Сс^„ват,^Пр°-переменньгх *,, х₂, _% ^ - ynpa^H^^S^?^ IV шагах. .-конечное состояние процесса иГ/п*^{0 На} I IT ??^р но нулю, так как все средства должны _бь ?£££*«**** "' ?• во, , =0. Схема распределения показана на рис * 4 ^{В П}^^

Уравнения состояний (12.2) в лани™ **?' Г⁴" ^ДСт"

(12.

Рис. 12.4

Введем в рассмотрение функцию Z*_k{s_k-{) — условную опти­мальную прибыль, полученную от А>го, (&+1)-го, ..., 4-го пред­приятий, если между ними распределялись оптимальным образом средства ^_i(0<^_[<5). Допустимые управления на к-и шаге удов­летворяют условию: 0 < Хк < s_k-\ (либо к-щ предприятию ничего не выделяем, х_к=0, либо не больше того, что имеем к к-му шагу, х_к< s_k-_x).

Уравнения (12.5) и (12.8) имеют вид:

к=А, s₄ = 0 => Z\(s₃) = max 74(^4), 00

0SX4 £*з

Z₃*(s₂)= max {f₃(x₃)+Z*₄(s₃)}, (б)

0<x₃<J₂

Z*₂(s_])= max {f₂(x₂)+Z'₃(s₂)}, (в)

z;(5)= max {/!(*,)+Z₂*(*,)}. (r)

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

IV ш а г. В табл. 12.1 fa{x) прибыли монотонно возрастают, поэтому все средства, оставшиеся к IV шагу, следует вложить в 4-е предприятие. При этом для возможных значений sy=Q, 1, ..., 5 получим:

Z*₄(s₃) =f₄(s₃) и xl(s₃) = s₃.

Глава 12^

III шаг. Делаем все предположения относительно остатка,-средств 5₂ к III шагу (т.е. после выбора xj и х₂). s₂ может прини­мать значения 0, 1,2, 3, 4, 5 (например, s₂ = 0, если все средства , отданы 1-му и 2-му предприятиям, 5₂=5, если 1-е и 2-е предпри­ятия ничего не получили, и т.д.). В зависимости от этого выбира- • ем 0<х₃^2, находим 5з=5₂-х₃ и сравниваем для разных х₃ при фиксированном s₂ значения суммы /з(*з)+ ^zl to)- Д^ля каждого s₂ наибольшее из этих значений есть Z₃* (s₂) — условная оптималь­ная прибыль, полученная при оптимальном распределении средств s₂ между 3-ми 4-м предприятиями. Оптимизация дана в табл. 12.2 при к=3. Для каждого значения s₂ Z₃ (5₂) и J₃ (s₂) по­мещены в графах 5 и 6 соответственно.

II шаг. Условная оптимизация, согласно уравнению (в), про­ведена в табл. 12.2 при к=2. Для всех возможных значений 5] зна­чения Z₂(s\) и X\{s\) находятся в столбцах 8 и 9 соответственно; первые слагаемые в столбце 7 - значения f₂(x₂), взяты из табл. 12.1, а вторые слагаемые взяты из столбца 5 табл. 12.2 при s₂ = s\ - х₂.

I шаг. Условная оптимизация (уравнение (г)) проведена в табл. 12.2 при к=\ для 5₀=5¹. Поясним решение подробно: если xi=0, то 5i=5, прибыль, полученная от четырех предприятий при условии, что ii=5 ед. средств между оставшимися тремя пред­приятиями будут распределены оптимально, paBHa/j(0)+Z₂(5) = =0+19=19 (Z₂(5) взято из столбца 9 табл. 12.2 при si=5). Если х, = 1, то 52=4. Суммарная прибыль при условии, что 5₂=4 ед. средств между оставшимися тремя предприятиями будут распре­делены оптимально, равна/,(1)+Z₂*(4)=8+16=24 (/,(1) взято из табл. 12.1, a Z₂*(4) - из столбца 9 табл. 12.2.) Аналогично при х,=2, 5₂=3 h/₁(2)+Z₂*(3)=10+13=23;

при х,=3, 5₂=2 и /,(3)+Z₂*(3)=l 1 + 10=21;

при х,=4, 5₂=1 _M/i(4)+Z₂*(l)=12+l6=28;

при х,=5, 5₂=0 _M/j(5)+Z₂*(0)=18+0=18.

¹ На I шаге условной оптимизации достаточно заполнить раздел таб­лицы, соответствующий 5₀=5.

Модели динамического программирования 257

Сравнивая подчеркнутые числа, получим Z*_x (5)=24 усл. ед. = = Z™_ax при х\ = х,*(5) = 1.

Используя уравнения (12.12), получим 5j* =5—1=4, а по табл. 12.2 в столбце 9 находим х₂ = х₂(4) = 2. Далее находим 5₂ =4-2=2, а по табл. 12.2 в столбце 6 — х₃ = х₃(2) = 1. Наконец, 5₃* =2-1=1 и х₄* =Х4(1) = 1, т.е. Х'{\\2; 1; 1).

Максимум суммарной прибыли равен 24 усл. ед. средств при условии, что 1-му предприятию выделено 1 усл. ед.; 2-му пред­приятию — 2 усл. ед.; 3-му предприятию — 1 усл. ед.; 4-му пред­приятию — 1 усл.ед>

Замечание 1. Решение четырехмерной задачи 12.1 на оп­ределение условного экстремума сведено фактически к реше­нию четырех одномерных задач: на каждом шаге определялась одна переменная х.

Замечание 2. На разобранной задаче 12.1 видно, что метод ДП безразличен к виду и способу задания функции: ^(х) были

заданы таблично, поэтому и Z*_k(s) и X*_k(s) принимали дис­кретные значения, представленные в табл. 12.2.

Таблица 12.2

9 Исследование операции в экономике

Глава 12 |;

Модели динамического программирования

Продолжение

Замечание З.Альтернативой между ДП для подобной дис­кретной задачи является метод перебора. Метод ДП предпоч­тительнее, так как на этапе условной оптимизации отбрасыва­ются заведомо негодные варианты.

Замечание 4.Достоинством метода является возможность анализа решения на чувствительность к изменению s_Q и п. Проведенные расчеты можно использовать для изменившихся начального состояния s₀ и числа шагов п. Например, пусть в задаче 12.1произошло уменьшение начальных средств на 1 усл. ед. Для s₀=4 достаточно в таблицу добавить расчеты при к=\ (это сделано в той же табл. 12.2). Получаем в этом случае Z_max=21 усл. ед. при распределении:

Xj* = 1 -> S*i =4-1 =3=> х\ = 1, ИЛИ Х*₂ =2 -»

-> 52=3-1=2, или s*₂ =3-2=1 =>*з=1, или а:₃*=0-> 5₃* =2-1=1, или ^з — 1~0=1=>JC4 =1.

В результате найдены два оптимальных рещ_ения. и\)*_п. 1; 1) и А<²>* (1; 2; 0; 1). Если начальные средства увеличили например, на 1 усл. ед., s₀=6, а функции прибыли f(\ °^Ь' лись прежними, то в табл. 12.2 достаточно добавить т ^оста" ^о=6 при к=Ъ, 2, 1; этот фрагмент расчетов помещенТтаб!?

Получаем Z_max=27, х'_{=1 -> 5* =6—1=5 => х*₂=\ _^ • =4 => х] =0 -» s] =4-0=4 => х*_А =4. Оптимальное решение Х*(1; 1; 0; 4).

Если принято решение распределить средства $„==<; iu^™ i

о j между z-, , 3- и 4-м предприятиями, то задача уже решена в табл 12 2 В

разделе к=2 таблицы находим Z_max= Z₂*(5)=19 _При условии, что х₂=1, х₃ =0, х₄=4.

Наконец, если увеличилось количество предприятий (число шагов), то схему можно дополнить, присоединяя шаги с номерами к=0, -1, ... и т. д. Например, _{Пусть средства} ^о = 6 распределяются между пятью предприятиями. Функция прибыли для пятого предприятия задана формулой /Ы=Зх+1 если х*0 и Д0)=0. Присвоим 5-му предприятию номер /fc=o' тогда х₀ — средства, выделенные этому пред_{Приятию} обо­значим через Z₀*(6) оптимальную прибыль, полученную от пяти предприятий:

Z₀*(6) = max {/₀(х₀) + Z\(s_x)\,

0<jcn<6 (. I

a Ji=6-Xo. Условная оптимизация 0-го шага дана в табл 12 4

Глава 12

Таблица 12.4

Следовательно, Z_max=28, а оптимальных решений четыре^-*,*(!; 1; 2; 1;1), JT₂*(2; 1; 1; 1; 1), *₃*(2; 1; 2; 0; 1), ^(3; 1; 1;0;1).

Замечание 5.К недостаткам метода по-прежнему следует отнести возникновение технических трудностей при вычисле­ниях в случае увеличения размерности. Если каждое управле­ние Х\ будет зависеть от г переменных, а состояние s\ — от р параметров, то на каждом шаге возникает /р-мерная задача оп­тимизации. (В задаче 12.1/•= 1, р=\, т.е. решалась одномерная задача). Даже при реализации метода ДП на ЭВМ практически можно решать задачи для небольших г, р, п.