Книги по разным темам Pages:     | 1 |   ...   | 2 | 3 | 4 |

Действительно: мы знаем в каком состоянии была управляемая система Х. Следовательно, можно выбрать оптимальное управление на первом шаге U1. В результате этого управления состояние системы изменилось на некоторое новое X1. Здесь тоже известно условное оптимальное управление U2, которое к концу второго шага переводит систему в состояние X2 и т.д.

Метод динамического программирования используется при:

- разработке правил управления запасами, устанавливающих момент пополнения запасов и размер заказа;

- календарном планировании производства и выравнивании занятости при колеблющемся спросе на продукцию;

- распределении капиталовложений между возможными направлениями их использования;

- выборе метода проведения рекламной кампании;

- систематизации методов поиска ресурсов;

- составлении календарных планов текущего и капитального ремонта оборудования;

- разработке планов замены основных фондов.

Рассмотрим различные варианты использования метода динамического программирования для нахождения оптимального управления экономическими системами.

Пример 2.Изделие, выпускаемое предприятием, имеет параметры качества V0 и себестоимость S0. В результате маркетинговых исследований установили, что для успешной реализации на рынке данное изделие должно иметь соответствующие параметры V1 и S1. Задача предприятия достичь параметров V1 и S1 с минимальными затратами.

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

S 0 8 6 9 8 9 8 7 S5 7 8 5 6 7 6 2 3 2 5 2 4 5 4 3 5 7 9 3 4 5 2 4 4 6 7 4 3 2 1 V SVVРис. 2.Считаем, что в каждом узле сетки возможно применение только двух управлений:

Ui =0 - изменение только качества V, Ui =1 - изменение только себестоимости S, таким образом, множеством допустимых управлений будет множество U={0,1} U=(01011001) - одна из возможных траекторий.

Для того, чтобы оценить эту траекторию, нужно знать затраты на каждом шаге. Это и будет целевой функцией Q(x, u). Значения Q(x,u) зададим в виде условных чисел, которыми на рисунке отмечен каждый из возможных переходов.

Для траектории U=(01011001) общие затраты, представляющие собой значения критерия качества управления, равны:

4+4+7+5+7+8+9+8=Дискретные значения V и S отметим числами от 0 до 4, начиная с конечного значения. Тогда Xij будет обозначать состояние при V=i и S=j, из которого до конца процесса останется сделать i+j шагов.

Обозначим через X k множество состояний, из которых процесс заканчивается за k шагов. В это множество войдут все те Xi j, для которых i+j=k. Полагая k=0,1,2..., получим:

x0={x00} ; x1 ={x10,x01}; x2={x20,x11,x02} и т.д.

Решение: при k=1 имеем x1={x10,x01}; F1(x,u)=Q(x,u); f1(x)=min F1(x,u) n Таблица 2.Расчет оптимального уравнения на последнем шаге u x1 Q (x,u) f 1 (x) u X 10 0 X 00 9 9 X 01 0 8 X 00 При k=2 имеем x2 ={x20, x11, x02} F2 (x,u)=Q(x,u)+f 1(x), f 2= min F2 (x,u) n Таблица 2.Расчет оптимального управления на предпоследнем шаге X u x* Q (x,u) f 1 (x) F2 (x,u) f 2 (x) u* 0 X 10 9 9 X 20 0 X 01 9 8 X 11 16 1 X 10 7 9 X 02 14 X 01 6 8 Таблица 2.Расчет оптимального управления за три шага до конца X u x* Q (x,u) f 2 (x) F3 (x,u) f3 (x) u* X 30 0 X 20 6 18 24 24 X 21 0 X 11 8 16 24 24 1 X 20 8 18 X 12 0 X 02 9 14 23 22 1 X 11 6 16 X 03 17 1 X 02 3 14 В рассматриваемом примере данные, содержащиеся в таблицах, можно изображать непосредственно на плоскости (V,S), указывая значения fk (x) в виде числа в соответствующем узле сетки, а u - стрелкой в направлении следующего узла. После того, как значения fk (x) и u* определены для всех узлов сетки, находим оптимальную траекторию, двигаясь от начального узла в направлении стрелок. Оптимальным управлением будет u(11000110), которому соответствует Jn (u)= 0 32 24 18 9 1 36 31 24 16 2 32 29 27 22 3 34 33 32 25 4 37 37 33 26 4 3 2 1 Рис. 2.2.2 Использование сетевых моделей в динамическом программировании Динамические задачи часто решаются с помощью сетевых моделей..

Сеть (граф) G1=(X,U) состоит из множества вершин {X} и множества ребер (дуг) {U}.

Дуги могут иметь различную длину U = Cij, где i - начальная вершина дуги, j - конечная вершина дуги.

Путь в графе G - это последовательность дуг U, в которой конец каждой предыдущей дуги совпадает с началом следующей.

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

Для реализации принципа оптимальности удобно использовать следующие обозначения:

fn(Xs) - стоимость, отвечающая стратегии минимальных затрат для пути от состояния s, если до конечного состояния остается n шагов.

jn (Xs ) - решение (управление), позволяющее достичь fn (Xs) (символ j зависит от шага n, номера вершины s и соответствует некоторому фиксированному пути), показывает переход от вершины Xs к вершине Xj. Последовательность j соответствует оптимальному уравнению.

Рекуррентное соотношение имеет вид:

f n (Xs) = min [ Csj + f n -1 (X j) ] S, j (x s, x j) X Упорядоченная запись вычислений выполняется в таблицах.

Таблица 2. j Номера вершин, в которые J l (Xs) f l (Xs) S совершен переход.

номера...

Csj+f l-вершин, из которых совершен...

переход : : : : :

n = l Таблица 2.Xs X Csj f - (Xj) f l (Xs) l j l(Xs) j Пример 2.2 Задача о путешествиях Некий человек N решил отправиться искать счастья в город М. В бюро путешествий ему показали карту Страны Р с нанесенными на ней автобусными маршрутами. Каждый круг на карте изображает населенный пункт. Для удобства они пронумерованы. Стоимость различных автобусных маршрутов различна (например, тем выше, чем длиннее путь). Обозначим через Cij стоимость проезда из пункта i в пункт j. Условные численные обозначения представлены на рис. 2.10 2 5 2 12 5 5 3 С 1 5 3 10 6 10 М 7 1 15 4 13 7 1 Рис. 2.Исходное состояние: fо (10) = 0 для jо (10) = остановка.

Таблица 2.10 J1 (Xs) f1 (Xs) J S 8 1 + 0 10 9 4 + 0 10 n = 1, Csj + fо(j) Таблица 2. Xj Csj fо(Xj) f1(Xs) j1(Xs) Xs 8 10 1 0 1 9 10 4 0 4 n = Таблица 2.Xs Xj Csj f1(Xj) f2(Xs) j2(Xs) 5 8 7 1 8 9 5 6 8 3 1 4 9 4 7 8 7 1 5 9 1 Таблица 2. j f 2(S) 8 j2(S) S 5 7+1 5+4 8 6 3+1 4+4 4 7 7+1 1+4 5 n = Таблица 2. j f3(Xs) 5 6 7 j3(Xs) S 2 10+8 12+4 3 5+8 10+4 7+5 12 4 15+4 13+5 18 n = Таблица 2. j 2 3 4 f 4 j Xs 2+16 5+12 1+18 17 Оптимальный путь 1 - 3 - 7 - 9 - 10, затраты по которому составляют f 4 (1) = 5 + 7 + 1 + 4 = 17.

Дополнительные условия 1) Предположим, между городами 1 и 9 не существует сообщения. Каким теперь будет оптимальный маршрут из 1 в 10 2) Предположим, дополнительно введен маршрут, связывающий 3 и 8. Какой должна быть наименьшая стоимость проезда между 3 и 8, чтобы выбранный ранее маршрут остался оптимальным 3) Определить диапазон цен переезда из 1 в 3 ( 3 в 7, 2 в 6 ), в рамках которого ранее выбранный маршрут остается оптимальным.

4) Племянник N., мистер П., живет в п. 10 и хочет отправиться в п. 1. Для каждого участка сети стоимость переезда в обратном направлении та же. Каков оптимальный маршрут П. Почему он тот же, что и у N., но в обратном направлении 15+19=10+16=6+13=3+10=9+3=12 1 6 2 7 3 8 4 9 5 10 Рис. 2.Пример 2.3 Задача распределения капиталовложений Строительная компания разрабатывает план капиталовложений на текущий год. Общий капитал, которым она располагает и который нужно распределить по различным объектам, составляет С сотен тысяч долларов. Рассматривается n возможных объектов капиталовложений. Компания может вло- жить деньги в любые из этих объектов. Единственным ограничением является объем наличного капитала. Минимальный объем капиталовложений, необходимый для приобретения объёма j, составляет pj. Компания оценивает соответствующую прибыль от вложенного капитала величиной Ui0. Однако, если в этот объект вложить дополнительно k сотен тысяч долларов, то в результате прибыль будет оцениваться величиной Uik. Предполагается, что Ui,к+1>Uik.

Компания стремится так распределить капиталовложения по объектам, чтобы максимизировать общую прибыль.

Пусть С=10, n=4, минимальные объемы капиталовложений p1=6, p2= 4, p3=3, p4=1. Пусть дополнительные капиталовложения можно распределить в объемах, кратных 1 сотне тысяч долларов, так что к=1,2,....

Сеть строится следующим образом. Для каждого объекта капиталовложений вводится столбец узлов. В обозначении узла (i,j) символ i относится к номеру объекта. Величина j определяет объем капитала, который можно вложить в объект i, при условии принятия определенных решений относительно вложений в уже рассмотренные объекты. Каждая дуга, исходящая из узла (i,j) соответствует конкретному решению по объекту i. Таким образом, любой допустимый вариант распределения капиталовложений по объектам можно представить в виде проходящего через всю сеть пути, который начинается в узле (1,10) и заканчивается в узле (5,0). Это означает, что весь наличный капитал должен быть распределен между четырьмя объектами.

Проверка:

- составить несколько возможных планов распределения капитало- вложений и найти соответствующие им пути в сетевой модели;

- выбрать несколько путей и найти соответствующие им варианты распределения капиталовложений.

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

Преобразование задачи о максимальном пути в задачу о кратчайшем пути осуществляется путём изменения знака целевой функции.

1.10 2.10 3.10 1.4.3.6 4.3.5 4.2.4 3.4 4.2.3 3.3 4.2.2 3.2 4.2.1 3.1 4.2.0 3.0 4.0 5.Рис. 2.Таблица 2.12 1 шаг до конца Таблица 2. объек- ты j f (s) j (s) кап. 1 2 3 4 S 5.влож.

1 - - - 4 4.10 0+22 22 5.2 - - - 6 4.7 0+19 19 5.3 - - 9 8 4.6 0+16 16 5.4 - 11 12 12 4.5 0+14 14 5.5 - 16 15 14 4.4 0+12 12 5.6 18 18 18 16 4.3 0+8 8 5.7 22 20 20 19 4.2 0+6 6 5.8 24 22 22 20 4.1 0+4 4 5.9 26 24 23 21 4.0 0+0 0 5. 10 28 25 24 2 шаг до конца Таблица 2.j 4.1 4.7 4.6 4.5 4.4 4.3 4.2 4.1 4.0 f (s) j (s) S 22+ 18+ 16+12 14+15 12+18 8+2 6+2 4+2 20+ 3.1 30 4.0 7 0 2 3 - - 16+0 - - 8+9 6+1 4+1 0+ 3.6 19 4.2 5 - - - 14+0 - - 6+9 4+1 0+ 3.5 18 4.2 - - - - 12+0 - - 4+9 0+ 3.4 13 4. - - - - - 8+0 - 0+ 3.3 9 4. - - - - - - 6+0 - 3.2 6 4. - - - - - - 4+0 - 3.1 4 4. - - - - - - 0+ 3.0 0 4.3 шаг до конца Таблица 2.j 3.1 3.6 3.5 3.4 3.3 3.2 3.1 3.0 f (s) j (s) S 30+ 19+11 18+16 13+18 9+20 6+22 4+24 0+2.1 32 3. - - - 13+0 - - - 0+ 2.4 13 3. - - - - 9+0 - - - 2.3 9 3. - - - - - 6+0 - - 2.2 6 3. - - - - - - 4+0 - 2.1 4 3. - - - - - - - 0+ 2.0 6 3.4 шаг до конца Таблица 2.j 2.1 2.4 2.3 2.2 2.1 2.0 f (s) j (s) S 32+ 13+18 9+22 6+24 4+26 0+1.1 32 2.Оптимальный путь 1.10 - 2.10 - 3.5 - 4.1 - 5. Прибыль 32 Таблица 2.Организация 1 2 3 Кап. вложе0 5 4 ния Прибыль 0 16 12 = ЗАДАЧИ 1. Необходимо разработать план аренды оборудования на период 3 года (с начала 1-го до на чала 4-го). Разрешается брать в аренду единицу оборудования в начале года 1 и эксплуатировать ее до начала года j<4. Единицу оборудования можно заменить в начале года j и эксплуатировать до начала года k<4 и так далее. Величина затрат Cjk (1

Величины Cij приведены в таблице.

C12 = 6 C 23 = 7 C 34 = С 13= 9 С 24= C 14=2. Из пункта 1 в пункт 6 требуется перевезти груз.

Из 1 в 6 есть несколько маршрутов, проходящих через 4 промежуточных пункта. Требуется перевезти груз, потратив при этом минимальное количество топлива. Расход топлива при перевозке груза между двумя пунктами приведен в таблице.

Таблица Маршрут Расход топлива 1 - 2 1 - 3 2 - 4 2 - 5 3 - 4 3 - 5 4 - 6 5 - 6 3. Транспортное агентство разрабатывает план аренды транспортного оборудования на период 5 лет (с начала 1 года до начала 6-го). Агентство может выполнить свои обязательства по перевозке грузов, взяв в аренду новую транспортную единицу в начале года 1 и эксплуатируя её до начала (любого) года j n. Агентство может заменить эту единицу в начале года j (если j < n) и эксплуатировать новую до начала года k (k n) и так далее. Величина затрат Cij (1 i< j n) включает арендную плату плюс ожидаемые расходы на ремонт и эксплуатацию транспорта взятого в начале года i и замененного в начале года j. Построить сеть, описывающую эту задачу при n = 6.

Допустим, что затраты на эксплуатацию и ремонт оборудования (транспорта) в течение одного, двух, трех, четырех и пяти последовательных периодов, составляют соответственно 1, 3, 6, 10, 15. Если аренда оборудования (транспорта) продолжается в течение одного, двух, трех, четырех или пяти последовательных периодов, то арендная плата составляет соответственно 5, 9, 13, 16 или 19. Эти арендные платежи увеличиваются на единицу в каждый период.

Например, если оборудование взято в аренду в начале третьего периода и аренда продлена на один, два или три последовательных периода, то арендная плата составит соответственно 7, 11, 15.

Необходимо найти оптимальную стратегию аренды транспортного оборудования.

ИТЕРАТУРА 1 Кобринский Н.Е., Майминас Е.З., Смирнов А.Д. Экономическая кибернетика - М.: Экономика, 1982.

2 Эртли-Каясоб П. Экономическая кибернетика на практике. - М.: Экономика, 1983.

3 Вагнер Г. Основы исследования операций. В 3 т. - М.: Мир, 1972.

4 Бункин В.А., Курицкий Б.Я., Сокуренко Ю.А. Решение задач оптимизации в управлении машиностроительным производством. - Л.: Машиностроение, 1976.

5 Эддоус М., Стэнефилд Р. Методы принятия решений. - М.: Аудит., 1997.

УДК 65.012.Михайлова Э.А., Смирнов А.О. Методы нахождения оптимального управления экономическими системами: пособие для практических занятий / РГАТА. Кафедра экономики. - Рыбинск, 1998. - 42 с.

Pages:     | 1 |   ...   | 2 | 3 | 4 |    Книги по разным темам