Задача о распределении средств между предприятиями Рассмотрим предложенную выше схему на конкретной задаче
0 распределении средств между предприятиями.
^ 12.1.Планируется деятельность четырех промышленных предприятий (системы) на очередной год. Начальные средства: s0 = = 5 усл. ед. Размеры вложения в каждое предприятие кратны
1 усл. ед. Средства х, выделенные к-му предприятию (к=\, 2, 3, 4), приносят в конце года прибыль /к(х). Функции fk(x) заданы таб лично (табл. 12.1). Принято считать, что:
а) прибыль fk (x) не зависит от вложения средств в другие предприятия;
б) прибыль от каждого предприятия выражается в одних ус ловных единицах;
в) суммарная прибыль равна сумме прибылей, полученных от каждого предприятия.
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.
' Здесь описан способ решения задачи ДП, начинающийся с последнего шага ("обратная схема"). Можно л-й и 1-й шаги поменять местами ("прямая схема").
1 Через sk здесь обозначено состояние системы после к-то шага при условии, что на к-м шаге выбрано оптимальное управление.
Модели динамического программирования
где ^ — параметр состояния — количество средств, оставшихся после к-го шага, т.е. средства, которые остается распределить между оставшимися А—к предприятиями.
Решение. Обозначим через *, количество гх *-му предприятию. (HvMeoanL nil™. сРедс
| * - - - п и с. ^оозначим через х, количеств -—
хракяем в прочее решения „Гз"»^^ Суммарная прибыль равна
| ных *-му предприятию. (НумеРациГпредПп„ СРедс*в, вь,п храняем в процессе решения" неизменной? РИЯТИЙ 1, 2, *^
' н Со-
Z=IA(**).
*=1 (12
Переменные х удовлетворяют ограничениям: "^
2>* =5,
4=1
*** О,* = 1,2Д4.
(12И)
Требуется найти переменные х, х? х, г системе ограничении (Ш1) „ o6pa'--. «М*^
Особяшсш модели. Ограничения линейные *Ю
„.„„,, ' ч^пмшил W заданы таблична uePeMeHu
применить методы целочисленного линейн^-^У £*
Схема решения задачи методом ДП имеет слеях ММИр°*а-
цесс решения распределения средств Д"uLZ^"* mur 4-шаговый, номер шага совпадет с шмерГ^пГСс^„ват,Пр°-переменньгх *,, х2, % ^ - ynpa^H^^S^?^ IV шагах. .-конечное состояние процесса иГ/п*0 На I IT ??р но нулю, так как все средства должны бь ?£££*«**** "' ?• во, , =0. Схема распределения показана на рис * 4 В П^^
Уравнения состояний (12.2) в данной зад^е Ltl
«t-,-**, *=1,2,3,4, ТВИд:
| Уравнения состояний (12.2) в лани™ **?' Г4" ДСт"
(12.
Рис. 12.4
Введем в рассмотрение функцию Z*k{sk-{) — условную оптимальную прибыль, полученную от А>го, (&+1)-го, ..., 4-го предприятий, если между ними распределялись оптимальным образом средства ^_i(0<^_[<5). Допустимые управления на к-и шаге удовлетворяют условию: 0 < Хк < sk-\ (либо к-щ предприятию ничего не выделяем, хк=0, либо не больше того, что имеем к к-му шагу, хк< sk-x).
Уравнения (12.5) и (12.8) имеют вид:
к=А, s4 = 0 => Z\(s3) = max 74(^4), 00
0SX4 £*з
Z3*(s2)= max {f3(x3)+Z*4(s3)}, (б)
0<x3<J2
Z*2(s])= max {f2(x2)+Z'3(s2)}, (в)
z;(5)= max {/!(*,)+Z2*(*,)}. (r)
Последовательно решаем записанные уравнения, проводя, условную оптимизацию {см. рис. 12.4) каждого шага.
IV ш а г. В табл. 12.1 fa{x) прибыли монотонно возрастают, поэтому все средства, оставшиеся к IV шагу, следует вложить в 4-е предприятие. При этом для возможных значений sy=Q, 1, ..., 5 получим:
Z*4(s3) =f4(s3) и xl(s3) = s3.
Глава 12^
III шаг. Делаем все предположения относительно остатка,-средств 52 к III шагу (т.е. после выбора xj и х2). s2 может принимать значения 0, 1,2, 3, 4, 5 (например, s2 = 0, если все средства , отданы 1-му и 2-му предприятиям, 52=5, если 1-е и 2-е предприятия ничего не получили, и т.д.). В зависимости от этого выбира- • ем 0<х3^2, находим 5з=52-х3 и сравниваем для разных х3 при фиксированном s2 значения суммы /з(*з)+ zl to)- Для каждого s2 наибольшее из этих значений есть Z3* (s2) — условная оптимальная прибыль, полученная при оптимальном распределении средств s2 между 3-ми 4-м предприятиями. Оптимизация дана в табл. 12.2 при к=3. Для каждого значения s2 Z3 (52) и J3 (s2) помещены в графах 5 и 6 соответственно.
II шаг. Условная оптимизация, согласно уравнению (в), проведена в табл. 12.2 при к=2. Для всех возможных значений 5] значения Z2(s\) и X\{s\) находятся в столбцах 8 и 9 соответственно; первые слагаемые в столбце 7 - значения f2(x2), взяты из табл. 12.1, а вторые слагаемые взяты из столбца 5 табл. 12.2 при s2 = s\ - х2.
I шаг. Условная оптимизация (уравнение (г)) проведена в табл. 12.2 при к=\ для 50=51. Поясним решение подробно: если xi=0, то 5i=5, прибыль, полученная от четырех предприятий при условии, что ii=5 ед. средств между оставшимися тремя предприятиями будут распределены оптимально, paBHa/j(0)+Z2(5) = =0+19=19 (Z2(5) взято из столбца 9 табл. 12.2 при si=5). Если х, = 1, то 52=4. Суммарная прибыль при условии, что 52=4 ед. средств между оставшимися тремя предприятиями будут распределены оптимально, равна/,(1)+Z2*(4)=8+16=24 (/,(1) взято из табл. 12.1, a Z2*(4) - из столбца 9 табл. 12.2.) Аналогично при х,=2, 52=3 h/1(2)+Z2*(3)=10+13=23;
при х,=3, 52=2 и /,(3)+Z2*(3)=l 1 + 10=21;
при х,=4, 52=1 M/i(4)+Z2*(l)=12+l6=28;
при х,=5, 52=0 M/j(5)+Z2*(0)=18+0=18.
1 На I шаге условной оптимизации достаточно заполнить раздел таблицы, соответствующий 50=5.
Модели динамического программирования 257
Сравнивая подчеркнутые числа, получим Z*x (5)=24 усл. ед. = = Z™ax при х\ = х,*(5) = 1.
Используя уравнения (12.12), получим 5j* =5—1=4, а по табл. 12.2 в столбце 9 находим х2 = х2(4) = 2. Далее находим 52 =4-2=2, а по табл. 12.2 в столбце 6 — х3 = х3(2) = 1. Наконец, 53* =2-1=1 и х4* =Х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
sk-\
| хк
| h
| к=Ъ
| /fc=2
| k=\
|
/э(*з)+
+Z4*to)
| z3*
to)
| to)
| /2(*2) +
+z3*to)
| z>*
to)
| to)
| /i(*i)+
+Z2*to)
| (So)
| to)
|
|
|
|
| 5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| e
|
|
|
| 0+1 = 1
3+0=3
|
|
| 0+4=4 6+0=6
|
|
| 0+6=6 8+0=8
|
| l
|
|
| 2 1 0
| 0+6=6
3+4=7 4+0=4
|
| l
| 0+7=7 6+4=10 9+0=9
|
|
| 0+10=10 8+6=14 10+0=10
|
| l
|
|
|
2 1
| 0+8=8 3+6=9 4+4=8
|
| l
| 0+9=9 6+7=13 9+4=13
|
|
| 0+13=13 8+10=18 10+6=16
|
| l
| 9 Исследование операции в экономике
Глава 12 |;
Модели динамического программирования
Таблица
| 2.3
|
|
|
| 0+24=24
|
|
| 8+19=27
|
|
| Ю+16=26
|
|
| П + 13=24
|
|
| 12+10=22
|
|
| 18+6=24
|
|
| Продолжение
sk-l
| Ч
| ^
| к=Ъ
| к=2
| k=\
|
/з(*з)+
| (J2)
| *
*з (s2)
| Л(х2)+ +Z3\s2)
| Z,' (Ji)
| *
x2
| +Z2'(s1)
| z;
| (So)
|
|
|
|
|
|
| 1
|
| 9
|
| и
|
|
|
|
| 7+0=7
|
|
| 11+0=11
|
|
| 11+0=11
|
|
|
| 0 1 2 3 4
| 4 3 2 1 0
| 0+13=13 3+8=11 4+6=10 7+4=11 11+0=11
|
|
| 0+13=13 6+9=15 9+7=16 11+4=15 13+0=13
|
| 2
| 0+16=16
8+13=21
10+10=20
11+6=17
12+0=12
|
|
|
| 0 1
2 3 4 5
| 5 4 3 2 1 0
| 0+16=16 3+13=16 4+8=12 7+6=13 11+4=15 18+0=18
|
|
| 0+18=18 6+13=19 9+9=18 11+7=18 13+4=17 15+0=15
|
|
| 0+19=19 8+16=24 10+13=23 11+10=21 12+6=18 18+0=18
|
|
| Замечание З.Альтернативой между ДП для подобной дискретной задачи является метод перебора. Метод ДП предпочтительнее, так как на этапе условной оптимизации отбрасываются заведомо негодные варианты.
Замечание 4.Достоинством метода является возможность анализа решения на чувствительность к изменению sQ и п. Проведенные расчеты можно использовать для изменившихся начального состояния s0 и числа шагов п. Например, пусть в задаче 12.1произошло уменьшение начальных средств на 1 усл. ед. Для s0=4 достаточно в таблицу добавить расчеты при к=\ (это сделано в той же табл. 12.2). Получаем в этом случае Zmax=21 усл. ед. при распределении:
Xj* = 1 -> S*i =4-1 =3=> х\ = 1, ИЛИ Х*2 =2 -»
-> 52=3-1=2, или s*2 =3-2=1 =>*з=1, или а:3*=0-> 53* =2-1=1, или ^з — 1~0=1=>JC4 =1.
В результате найдены два оптимальных рещения. и\)*п. 1; 1) и А<2>* (1; 2; 0; 1). Если начальные средства увеличили например, на 1 усл. ед., s0=6, а функции прибыли f(\ °Ь' лись прежними, то в табл. 12.2 достаточно добавить т оста" ^о=6 при к=Ъ, 2, 1; этот фрагмент расчетов помещенТтаб!?
|
|
|
|
|
|
|
|
|
| 0 1
|
| 0+16=16 3+16=19
|
|
| 0+22=22 6+18=24
|
|
|
| 2 3 4 5
| 4 3 2 1
| 4+13=17 7+8=15 11+6=17 18+4=22
|
|
| 9+13=22 11+9=20 13+7=20 15+4=19
|
|
| Получаем Zmax=27, х'{=1 -> 5* =6—1=5 => х*2=\ _^ • =4 => х] =0 -» s] =4-0=4 => х*А =4. Оптимальное решение Х*(1; 1; 0; 4).
Если принято решение распределить средства $„==<; iu^™ i
о j между z-, , 3- и 4-м предприятиями, то задача уже решена в табл 12 2 В
разделе к=2 таблицы находим Zmax= Z2*(5)=19 При условии, что х2=1, х3 =0, х4=4.
Наконец, если увеличилось количество предприятий (число шагов), то схему можно дополнить, присоединяя шаги с номерами к=0, -1, ... и т. д. Например, Пусть средства ^о = 6 распределяются между пятью предприятиями. Функция прибыли для пятого предприятия задана формулой /Ы=Зх+1 если х*0 и Д0)=0. Присвоим 5-му предприятию номер /fc=o' тогда х0 — средства, выделенные этому предПриятию обозначим через Z0*(6) оптимальную прибыль, полученную от пяти предприятий:
Z0*(6) = max {/0(х0) + Z\(sx)\,
0<jcn<6 (. I
a Ji=6-Xo. Условная оптимизация 0-го шага дана в табл 12 4
Модели динамии^
—------------------------ ^-^Р^ОГгч
^^^программирования 261 5. Вводят п--------------------------------------------------------------------------------
^к\Ч-\) и ycjj0B сМотрение условные максимумы (минимумы) к = п, л-1, ... л оптимальное управление на к-и шаге: XUs^-Л
■ Записывав нения БеллмаНа Ровные для вычислительной схемы ДП урав-
7. Решают По^я K(s„-i) и Z^^-J, k=n-\, ..., 1, тимизация) и По*Аовательно уравнения Беллмана (условная оп-
^Ют две последовательности функций:
8. После ВьШол и^->>>и<^-1)Ь
мальное решецИе ^ения условной оптимизации получают опти-
а) Zmax = %*, "^я конкретного начального состояния s0: _. ' wo) и
б) по иепоЧк
=> ХК -> £ CW ^ Х\ "> Si => Х2 "> *2 => - => Хп.х -> Sn_^
| Глава 12
Таблица 12.4
*0
|
|
|
|
|
|
|
| 5,=6-Х0
|
|
|
|
|
|
|
| ЛО)=о
|
|
|
|
|
|
|
| Zx (sx) (взята из табл. 12.2 и 12.3 при *=1)
|
|
|
|
|
|
|
| Лхо)+ Zx{sx)
|
|
|
|
|
|
|
| Следовательно, Zmax=28, а оптимальных решений четыре-*,*(!; 1; 2; 1;1), JT2*(2; 1; 1; 1; 1), *3*(2; 1; 2; 0; 1), ^(3; 1; 1;0;1).
Замечание 5.К недостаткам метода по-прежнему следует отнести возникновение технических трудностей при вычислениях в случае увеличения размерности. Если каждое управление Х\ будет зависеть от г переменных, а состояние s\ — от р параметров, то на каждом шаге возникает /р-мерная задача оптимизации. (В задаче 12.1/•= 1, р=\, т.е. решалась одномерная задача). Даже при реализации метода ДП на ЭВМ практически можно решать задачи для небольших г, р, п.
|