Пиши Дома Нужные Работы

Обратная связь

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

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

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з=523 и сравниваем для разных х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
=5-1=

Получаем 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 {/00) + 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, р=\, т.е. решалась одномерная задача). Даже при реализации метода ДП на ЭВМ практически можно решать задачи для небольших г, р, п.






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2021 pdnr.ru Все права принадлежат авторам размещенных материалов.