Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Тема 7. Задачи динамического программирования
|
|
1.Модель динамического программирования.
2.Принцип оптимальности.
3.Уравнения Беллмана.
Решение задач линейного программирования мы находили как бы за один шаг. Такие задачи называют одношаговыми.В отличие от них задачи динамического программирования являются многошаговыми. Нахождение решения этих задач включает несколько этапов, на каждом из которых определяется решение некоторой частной задачи, обусловленной исходной.
Динамическое программирование - метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разбит на отдельные этапы или шаги.
Динамическое программирование начало развиваться в пятидесятых годах 20 века благодаря работам Р. Беллмана и его сотрудников. Практически метод динамического программирования стал применим в связи с развитием вычислительной техники и эффективно решает задачи оптимального управления запасами, оптимального распределения ресурсов, замены оборудования, маршрутизации.
Задача. Все предприятия периодически заменяют оборудование. При замене учитываются производительность используемого оборудования, затраты на содержание и ремонт оборудования, стоимость покупаемого и заменяемого оборудования. С учетом указанных факторов определяется оптимальный план замены оборудования, т.е. план, обеспечивающий максимум прибыли от замены оборудования в течение нескольких лет.
Задача. Некоторая сумма денежных средств распределяется в течение нескольких лет между рядом предприятий. Средства, выделяемые предприятиям, к концу года приносят доход, который может участвовать в последующем распределении. Требуется определить такой способ распределения средств, чтоб суммарный доход за ряд лет был максимальным.
Задача: Для увеличения объёмов выпуска продукции нескольким предприятиям выделены средства в объёме Z1 тыс.руб. Использование каждым К предприятием Xk рублей позволяет получить прибыль, определяемую нелинейной функцией fx(xk). Найти распределение средств, обеспечивающее максимум прибыли.
Запишем математическую модель:
n n _-----
F= å fx(xk)®max; å xk=Z1; xk³ 0, k=1, n
k=1 k=1
Z1 Z2 Zп
f1(x1) x1 f2(x2) x2 fп(xп) xп
1 2 п
xk – объём средств, выделенных предприятию К,
является переменной управления;
Zk – остаток средств до выделения средств предприятию К и оставшимся предприятиям, называется параметром состояния.
___
Zk=Zk-1 – xk-1, k=2, n – уравнение состояния
Изменяя управление и объем средств, получим различную суммарную прибыль: F=f(Z1, x).
Вектор Х*(x1*, …, xn*) – оптимальное управление, обеспечивающее получение максимальной прибыли.
Метод динамического программирования состоит в том, что оптимальное управление строится по шагам. На каждом шаге оптимизируется управление только этого шага. Но управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом. Суммарный экономический эффект складывается из эффекта на данном шаге и эффекта на оставшихся шагах.
Беллман сформулировал принцип оптимальности:
Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на этом шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.
Fк*(Zk)=махí fx(xk)+F*k+1(Zk+1)ý - уравнение Беллмана
0 £ xk £ Zk
Вычислительная схема динамического программирования строится в зависимости от размерности задачи, характера модели (непрерывный или дискретный), вида функций, описывающих уравнение состояния и целевую функцию и других характеристик.
При решении задач методом динамического программирования рассматривают прямой ход вычисления или обратный.
Задача. Найти оптимальный план вложения средств в размере 100 тыс. руб. в три предприятия, обеспечивающий максимум суммарной прибыли.
Исходные данные
| Объем средств Хк | Прибыль, тыс.руб. | ||
| Предприятие1 | Предприятие2 | Предприятие3 | |
Пусть х1 - объем средств, вложенных в 1 предприятие, тыс. руб.
х2 -объем средств, вложенных во 2 предприятие, тыс. руб.
х3 - объем средств, вложенных в 3 предприятие, тыс. руб.
Тогда F = S fк (хк) - мах
к=1
3
при условии S хк = 100
к=1
Пусть Z1 - остаток средств перед вложением в 1, 2 и 3 предприятия, тыс. руб.
Z2 - остаток средств перед вложением во 2 и 3 предприятия, тыс. руб.
Z3 - остаток средств перед вложением в 3 предприятие, тыс. руб.
Z1 = 100 20 £ х1 £ 80
Z2 = 100 - х1 = Z1 - х1 20 £ х2 £ 80
Z3 = 100 - х1- х 2 = Z2 - х 2 20 £ х3£ 80
Составим уравнения Беллмана для обратного хода вычислений:
F1*(Z1 = 100) = мах (f1(х1) + F*2(Z2 )) - первое уравнение
20 £ х1 £ Z1
F2*(Z2) = мах (f2(х2) + F*3(Z3 )) – второе уравнение
20 £ х2 £ Z2
F3*(Z3) = мах (f3(х3)) – третье уравнение
20 £ х3 £ Z3
Решим эти три уравнения табличным методом.
Решение уравнения 3
| Z3 | |||
| Х3 | |||
| f3(X3) | |||
| F3*(Z3) |
В таблице рассчитаны условно оптимальные вложения средств в третье предприятие и соответствующая прибыль.
Решение уравнения 2
| Z2 | X2 | f2(X2) | Z3=Z2-X2 | F3*(Z3) | f2+F3* | F2*(Z2) |
В таблице 2 для всех возможных значений Z2 определены максимальные значения суммарной прибыли на втором и третьем предприятии.
Решение уравнения 1
| Z1 | X1 | f1(X1) | Z2=Z1-X1 | F2*(Z2) | f1+F2* | F1*(Z1) |
В таблице получено оптимальное решение.
Максимум прибыли составляет 85 тыс. руб. Первому предприятию необходимо выделить 40 тыс. руб. Из таблицы 8 видно, что второму следует выделить 20 тыс. руб. Учитывая, что всего имеется 100 тыс. руб., находим, что третьему предприятию предназначено 40 тыс. руб.
Замечания
1. Основная сложность решения - 1 этап условной оптимизации.
2. Прямой и обратный ход вычислений есть реализация пошаговой оптимизации. Выбор хода вычислений зависит от условия задачи.
3. Основное достоинство метода динамического программирования заключается в применимости его при любом способе задания целевой функции и любом допустимом множестве значений параметра состояний и управлении.
4. При дискретном задании целевой функции происходит табулирование функций F*к(Zк) для всех возможных значений параметра, но объем расчетов значительно меньше, чем при прямом переборе вариантов. Это связано с тем, что на этапе условной оптимизации неудачные варианты сразу отбрасываются.
5. Большое достоинство моделей динамического программирования заключается в возможности анализа чувствительности к изменению исходных данных.
6. Модель динамического программирования позволяет без пересчета всей задачи учесть изменение количества шагов.
Модель динамического программирования легко реализовать в электронных таблицах Еxcel 7.0.
|
|