Методы оптимизации в экономике, страница 7

Задача распределения ресурса Применим метод динамического программирования к задаче распределения ресурса. Постановка задачи. Дан ресурс объемом Х,. Вклад и единиц ресурса в г -е предприятие дает прибыль Р; ( и ) . Как распределить ресурс среди Ф предприятий, чтобы суммарная прибыль была максимальной7 Найти максимум Составим математическую модель задачи распределения ресурса как задачи оптимального дискретного управления. Для этого требуется представить процесс распределения ресурса как многошаговый динамический процесс.

Пусть шаг процесса соответствует выделению 1- му предприятию средств, состояние процесса — тому, сколько средств осталось для выделения предприятиям ото-го до Ф -го, а управление равно объему средств, выделенных 1 -му предприятию. Множество возможных состояний Х = ~ О, .....,Х, ~~; множество возможныхуправлений (Х = ~ О,.....,Х ~. Уравнение состояний имеет вид х~+~ = х~ что следует из введенных определений для состояния и управления (объем средств, имеющийся в распоряжении для распределения среди предприятий, начиная с (к + 1 ) - го, равен объему средств, имеющихся в распоряжении для распределения среди предприятий, начиная с Й -го,минус объем, выделенный й-му предприятию).

Начальное состояние х1 = Х. Еачество процесса оценивается Г= ХР;(и,). 1-1 Уравнение Беллмана в задаче распределения ресурса (5.14) примет вид: $К, (х, ) = шах ~ Г, (и ) + й~ +1 (х — и,) ~ О ~ир хр (5.15) с учетом (5.16) с граничным условием Сколько средств и в какое предприятие следует вложить директорату концерна, чтобы прибыль была максимальной? Математическая постановка задачи: 3 з Найти максимум Г = Х Г,(и;) при Х и, = 5 .

1-1 1-1 И'~„~(х1,,) = О. (5.17) Условие О ~ и ~ х связано со смысловым содержанием задачи: выделить предприятию больше средств, чем есть для распределения, нельзя. Нулевое граничное условие для функции 'Беллмана соответствует тому, что прибыль от нераспределенных средств равна О. Решим следующую задачу распределения ресурса.

Концерн располагает 5 миллионами долларов (млн.долл.) для вклада средств в расширение производства на трех предприятиях. Известно, что вложение средств должно быть кратно 1 млн.долл. и прибыль от вложения 1 млн.долл. в 1-е предприятие равно Г;(1) (табл.5. 3).

Таблица 53 Множество возможных состояний Х = ~ О, ....,,5 ~; множество возможныхуправлений У = ~ 0,....,,5 ~. Применим алгОритм динамического программирования, Этап 1. По (5.17) И'4(0) = И~4(1) = И'4(2) = И'4(3) = И'"4(4) = = И'4(5) = О . Найдем значения функции Беллмана и оптимального управления для р = 3. По (5.16) И~~(х) = шах ~ Г (и) ~ . О~и~х Так как РЗ (и ) неубывакпцая функ~и~ то шах -"З (и ) достигается при наибольшем и, т.е.

при и = х. Следовательно, И'з(х) = Гз(и) и из(х) = х. Запишем найденные значения в табл. 5.4 для х = О, 1 „2, 3, 4, 5. Найдем значения функции Беллмана и оптимального управления для р = 2 . По (5.16) И2(х2) шах ~ ~2(и) + И з(х О~и ~х Для х = О, учитывая О ~ и ~ х, получаем, что иг(О) =О И И~г(0) = Гг(0) + И~з(О) = О . Для х = 1: и'2(1) - шах ~1 Рг(0) + и'з(1 — О ) ), 1Р (1) + и'. (1 — 1) )1 = - ша ( (О+ 21 (О+ 0)) = 2 при иг(1) = О Аналогично вычислим И~г(х) и иг(х) для х = 2„3,4,5. Проверьте: И'2(5) = шах (1Рг(0) + И'з(5 — О)) 1Р2(1) + И з(5 1)) (Рг(2)+ )~з(5 2)) (Гг(3)+ И'з(5 3)) (Гг(4)+И'з(5 4)1* 1рг(2) + И',(5-2)1) = шах ( [О+ 3 ), (О+ 3 1, ( 1+ 3 ), 12+ 2 1, (4+ 2 ), (7+ О ) ) = 7 при иг ( 5 ) = 5 . Найдем значения функции Беллмана и оптимального управления для р = 1.

По (5.16) И~ ~ ( х ) = шах ~ Г1 ( и ) + И'2 ( х — и ) ~ . О~и ~х Д~ (3) = шах ( (Р (О) + и'2(3 0)1 (Р1(1) + ""2(3 (р (2) + ц," (3 2)1,(г„(3) + й'2(3 — 3)) 1= х ((О+ 3),( 1 + 23,(2+ 21,( 3+ 01 )= 4 прн и2(3) = 2 Таблица 54 Этап 2. Построим оптимальный процесс. х~ — — 5; выбираем и1 ( 5 ) = 0; тогда на следующем шаге х2 = 5 — О = 5; по табл.

5.3 определяем„что и~ (5) = 5, тогда хз — — 2. Оптимальным распределением ресурса в данной задаче будет выделение 5 млн.долл. второму предприятию, первому и третьему предприятиям выделять средства неэффективно. Суммарная прибыль от распределения 5 млн. долл. равна 7 млн. долл. (в табл. 5.4 это значение В'; ( 5 ) ). 5.4. Вычислительный алгоритм решения задачи оптимального управления дискретным динамическим процессом Рассмотренные простые примеры мы смогли решить вручную, не используя ЭВМ.

Более сложные задачи, где число элементов алфавитов состояний и управлений велико, можно решить, составив программу по вычислительному алгоритму метода динамического программирования. Рассмотрим вычислительный алгоритм решения задачи оптимального управления дискретным ' динамическим многошаговым процессом методом динамического программирования. Описание алгоритма приведем для случая, когда множество возможных состояний Х и множество возможных управлений У не зависят от номера шага процесса.

50 Входными данными йлгОритмй являются: 1, Дискретный отрезок времени 1 = О, 1, ....., Ф . 2. Множество возможных состояний Х= ~ х|,х2, .....,х~ 1 . 3. Множество возможных управлений У= ~ ц, и, ....., и 4, Уравнение состоянийх~+1 =~~(х~,и~). 5.

Начальное состояние х о. 6. Показатель качества Ф-1 г = ~ ~ ~(ха "~)'+ гл(хл) 1=0 Описание алгоритма: Шаг 1. Положить И~~( х ) = Р~( х ) для 1 = 1, ..., Х,. Шаг 2. Положить р = Ф вЂ” 1 . Шаг 3. Положить 1 = 1 . Шаг 4. Положить т = 1. Шйг 5. Определить по . уравнению состояний (5.1) х „+1 = „1 (х, и ), по значению функции Беллмана на последующем р+1 (~р+1) и вы слить А ~ р(х «~ )+ ~ р+1(хр+1) . + 1 не принйдлежит множеству возможнык сос~ояний, ТО 1ж Шаг 6. Если т с М, то положить т = т + 1 и перейти на шаг 5, иначе перейти на шаг 7.

Шаг7. Вычислить А '= так ~ А 1, А 2, ..., А 1, Пусть А = А '. По~о~~т~ И~р ( х ) = А, и р ( х ) = и ' . Шаг 8. Если 1 < Ь, то положить 1 = ! + 1 и перейти на шаг 4, иначе перейти нй шйг 9. Шаг 9. Если р > О, то положить р = р — 1 и перейти на шаг 3, иначе перейти нй шаг 10.

Шаг 10. Задать хо. Шаг 11. Положить Ж = О. Шаг 12. Вычислитьх~+1 = 1'~(х~,и~(х~) ), где и~(х~) ) определяется по оптимальному управлению, найденному на шаге 7. Шаг .13. Если й < М, то положить В = ф + 1 и перейти на шаг 12, иначе вывести результаты расчета (оптимальный процесс и оптимальное упрйвление нй кйждОм шаге) и зйкОнчить рйботу йлгоритмй. 5.5. Варианты заданий Нечетные вапианты К ОиттЕРаи паСПОЛИГаЕТ Я МИЛЛИОНаМИ ЛОЛЛВРОВ (МЛН.ДОЛЛ.) ДЛЯ вклада средств в расширение производства на трех предприятиях.

Известно, что вложение средств должно быть кратно 1 млн.долл. и при. быль' от вложения у млн.долл. в 1-е предприятие равно Р; (~ ) . Примечание,Ф вЂ” номер варианта. Сколько средств и в какое предприятие следует вложить директорату концерна, чтобы прибыль была максимальной? Четные ва ианты Фирма использует оборудОвание, срок работы которого не может превышать пяти лет. Замена оборудования может производиться в конце календарного года, Прибыль от эксплуатации оборудования ~Р) и затраты на его ремонт ~Я) зависят только от срока его эксплуатации и даны в таблице в условных единицах Примечание.

т' — номер варианта. Стоимость покупки и установки оборудования составляет 40 условных единиц, Требуется составить план замены оборудования, при котором суммарны прибыль за три года будет максимальной, если а) оборудование новое; б) оборудование проработало ~ ~Ча )лет, ~ 1) — целая часть числа ~с .