Автор работы: Пользователь скрыл имя, 12 Марта 2012 в 10:15, контрольная работа
Динамическое программирование в математике и теории вычислительных систем — метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами, который намного эффективнее, чем решение «в лоб».
1. Уравнение Беллмана.
2. Задача управления запасами.
Для этого целесообразно воспользоваться 2-мя таблицами. Заполнение таблицы 1 проводится так: столбцы – величина запаса с предыдущего шага, строки – объем производства на текущем этапе. Число столбцов ограничивается imax, а число строк xmax. Клетка таблицы делится на 2 части. В одной части записываются значения состояния в конце текущего этапа (in = in-1 + xn – dn ). Если in < 0 ,то это недопустимое состояние, клетка вычеркивается из рассмотрения. Во второй части клетки записывается значение функции
fn(in) = cn-1(xn-1) + cn(xn) + h*in-1 (2.4.1)
Среди допустимых клеток находятся клетки с одинаковыми значениями состояний, и выбирается клетка, для которой функция fn(in) минимальна, для нее фиксируется оптимальный объем производства. Эти результаты записываются в таблицу 2.
Такие шаги повторяются N раз.
Для нахождения оптимальных объемов производства xn и оптимальных уровней запасов in производится решение задачи в обратном порядке. На последнем этапе (n = N) из таблицы 2 выбирается xn и in , соответствующие оптимальной (минимальной) функции затрат fn(in). На этапах n < N из таблицы 2 выбираются строки для которых xn и in такие, что бы |dn – xn+1 | = in. Обратное решение задачи производится до n = 1 этапа.
Список литературы
1) Черноморов Г. А. Теория принятия решений – Южно-Российский Государственный Технический университет. Новочеркасск: редакция журнала "Изв. Вузов. Электромеханика", 2002.
2) Павлов В.Н. Математическая экономика – Новосибирск, ЭФ НГУ 2000.
3) Домбовский В.В., Чаусова Е.В. Математическая модель управления запасами при случайном сезонном спросе и ненадежных поставщиках.
4) Кузнецов Ю. Н. Математическое программирование. –М.: Наука,1976.
5) Вентцель Е. С. Элементы динамического программирования. –М.: Наука,1987.
6) Карманов В. Т. Математическое программирование. –М.:Наука,1986.
7) Динамическое программирование http://www.karelia.ru/psu/
8) ::Bolshe.ru:: Методология и методы принятия решения. http://www.bolshe.ru/unit/109/