Тема. Динамическое программирование. Принцип оптимальности. Уравнение Беллмана

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

Пусть процесс имеет n шагов. Состояние системы на каждом шаге i описывается s параметрами , которые называются фазовыми координатами. Введем обозначения:

- множество состояний системы S перед шагом i ();

- множество состояний системы S в конце шага i();

- множество управлений, которые возможно выбрать на шаге i и под воздействием каждого из которых система S переходит в одно из состояний множества ();

- условно-оптимальное значение целевой функции от шага i до шага n, при условии, что перед шагом i система S находилась в одном из состояний множества ; а на шаге i было выбрано управление , обеспечивающее целевой функции условно-оптимальное значение;

- значение целевой функции (показатель эффективности) на шаге i для всех управлений из множества при условии, что на шаге i система S находилась в одном из состояний множества ;

- условно-оптимальное значение целевой функции от шага i+ 1 до шага n, при условии, что в результате воздействия управления, выбранного из множества , система S на шаге i перейдет из состояния, принадлежащего множеству , в одно из состояний множества ().

Формально принцип оптимальности Беллмана имеет вид:

= ( + ) (*).

Уравнение (*) называется основным функциональным уравнением динамического программирования (или уравнением Беллмана, или рекуррентными соотношениями).

Рассмотрим последний шаг n процесса и уравнение (*):

= ( + ).

Функция не определена при , значит, =0. Получим

=

В процессе условной оптимизации по уравнениям Беллмана (рекуррентным соотношениям) определяются условно-оптимальные значения целевой функции и оптимальные управления для всех возможных состояний системы на каждом шаге, начиная с последнего.

После определения значений функции и соответствующих оптимальных управлений для всех шагов от шага n до шага 1 переходят к безусловной оптимизации. По известному начальному состоянию системы для 1-го шага определяют оптимальный результат за следующие n шагов () и управление на шаге 1, которое обеспечивает этот результат. Применяя управление система перейдет в определенное состояние из множества , зная которое возможно определить и так далее до последнего шага n.

Задачи для контрольных заданий

Задание № 1

1-10. В пунктах А₁, А₂, А₃ производится однородная продукция в количествах а₁, а₂, а₃ единиц. Готовая продукция поставляется в пункты В₁, В₂, В₃, В₄, потребности которых составляют b₁, b₂, b₃, b₄ единиц. Стоимости с_ij перевозок единицы продукции из пункта А_i в пункт В_j заданы матрицей . Требуется найти оптимальный план методом дифференциальных рент.

1. а₁= 500 а₂= 200 а₃= 600 b₁= 250 b₂= 150 b₃= 350 b₄= 250

2. а₁= 500 а₂= 900 а₃= 100 b₁= 200 b₂= 650 b₃= 150 b₄= 300

3. а₁= 200 а₂= 500 а₃= 300 b₁= 150 b₂= 450 b₃= 50 b₄= 50

4. а₁= 250 а₂= 650 а₃= 300 b₁= 350 b₂= 50 b₃= 150 b₄= 450

5. а₁= 350 а₂= 750 а₃= 300 b₁= 200 b₂= 50 b₃= 600 b₄= 400

6. а₁= 450 а₂= 200 а₃= 350 b₁= 150 b₂= 300 b₃= 50 b₄= 400

7. а₁= 300 а₂= 700 а₃= 400 b₁= 250 b₂= 450 b₃= 150 b₄= 350

8. а₁= 250 а₂= 550 а₃= 350 b₁= 300 b₂= 150 b₃= 400 b₄= 150

9. а₁= 750 а₂= 200 а₃= 550 b₁= 450 b₂= 300 b₃= 350 b₄= 250

10. а₁= 400 а₂= 300 а₃= 500 b₁= 350 b₂= 250 b₃= 150 b₄= 250

Задание № 2

11-20. Решить методом Гомори.

11.	12.	13.	14.	15.
16.	17.	18.	19.	20.

Задание № 3

2 1-30. Найти необходимый размер компенсации для задачи

U (x₁; x₂)

,

если произошло изменение цены на один из товаров.

Все необходимые числовые данные приведены в таблице 3.

Таблица 3.

Номер задачи	U (x1; x2)	=(Р1; Р2)	I	Изменение цены
		(4; 5)		цена на первый товар увеличиться до 8 денежных единиц
	3x13 · x22	(3; 10)		цена на второй товар увеличиться до 20 денежных единиц
		(3; 6)		цена на первый товар увеличиться до 7 денежных единиц
		(10; 5)		цена на второй товар увеличиться до 7 денежных единиц
		(2; 5)		цена на первый товар увеличиться до 5 денежных единиц
	4x12 · x23	(1; 2)		цена на второй товар увеличиться до 4 денежных единиц
		(5; 2)		цена на первый товар увеличиться до 7 денежных единиц
		(1; 4)		цена на второй товар увеличиться до 7 денежных единиц
		(5; 5)		цена на первый товар увеличиться до 9 денежных единиц
	3x1 · x23	(5; 1)		цена на второй товар увеличиться до 3 денежных единиц

Задание № 4

31-40. Решить игру сведением к задаче линейного программирования. Платежные матрицы имеют вид:

(Замечание. При решении задачи линейного программирования использовать графический метод решения, первую и вторую теоремы двойственности)

31.	32.	33.	34.	35.
36.	37.	38.	39.	40.

Задание № 5

41-50. Найти наибольшее и наименьше значения функции при заданных ограничениях.

41.	42.
43.	44.
45.	46.
47.	48.
49.	50.

Задание № 6

51-60. Для реконструкции и модернизации производства на n предприятиях выделены денежные средства с. По каждому из n предприятий известен возможный прирост () выпуска продукции в зависимости от выделенной ему суммы x (). Требуется с помощью метода динамического программирования распределить средства с между предприятиями так, чтобы суммарный прирост выпуска продукции на всех n предприятиях достиг максимальной величины (этот основной результат задачи получить для с =100 млн ден. ед. и n =4).

Все необходимые числовые данные приведены в таблице 4.

Таблица 4.

Номер задачи	Предприятие	Прирост выпуска продукции на i -м предприятии млн ден.ед.	Часть средств, выделяемых предприятием, млн ден.ед
	№1
	№2
	№3
	№4

Контрольные вопросы:

1. Общая задача математического программирования.

2. Основные разделы математического программирования

3. Формы задач линейного программирования, их эквивалентность и способы преобразования

4. Симплексный метод решения задачи линейного программирования

5. Построение начального опорного плана и переход к плану, более близкому к оптимальному, при решение задач линейного программирования симплексным методом

6. Решение канонической задачи линейного программирования с помощью симплекс – таблиц

7. Прямая и двойственная задачи (основные понятия)

8. Правила составления двойственных задач

9. Виды двойственных задач

10. Основные теоремы двойственности

11. Экономическая интерпретация двойственных оценок в производственных задачах.

12. Постановка задачи целочисленного программирования.

13. Графический метод решения задачи целочисленного программирования

14. Целочисленное программирование. Метод Гомори

15. Метод ветвей и границ

16. Этапы метода ветвей и границ

17. Математическая постановка задачи коммивояжера

18. Решение задачи коммивояжера методом ветвей и границ

19. Построение редуцированных матриц и ветвление в методе ветвей и границ решения задачи коммивояжера

20. Двойственный симплекс-метод решения задачи линейного программирования

21. Математическая постановка транспортной задачи

22. Определение опорного плана транспортной задачи методом минимального элемента.

23. Определение оптимального плана транспортной задачи методом потенциалов

24. Этапы перехода от открытой модели транспортной задачи к закрытой модели

25. Определение опорного плана транспортной задачи методом «северо-западного угла»

26. Закрытая модель транспортной задачи

27. Открытая модель транспортной задачи

28. Общая постановка задачи нелинейного программирования.

29. Решение задачи нелинейного программирования методом множителей Лагранжа

30. Общая постановка задачи нелинейного программирования. Теорема Куна-Таккера

31. Основные понятия теории игр.

32. Классификация игр

33. Решение матричных игр в чистых стратегиях

34. Решение матричных игр в смешанных стратегиях

35. Основные понятия теории игр. Доминирование стратегий

36. Методы решения матричных игр без седловой точки

37. Принцип оптимальности. Уравнение Беллмана

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

39. Определение функции полезности.

40. Свойства функции полезности

41. Кривые безразличия.

42. Свойства кривых безразличия

43. Постановка задачи потребительского выбора и ее геометрическая интерпретация

44. Решение задачи потребительского выбора методом множителей Лагранжа

45. Функции спроса. Свойства функции спроса

46. Геометрическое представление изменения спроса при изменении цен и дохода: кривые «доход-потребление», кривые «цена-потребление»

47. Коэффициенты эластичности спроса по ценам и доходу.

48. Свойства коэффициентов эластичности

49. Факторы, определяющие эластичность спроса

50. Коэффициенты эластичности. Эластичность спроса по цене (прямая).

51. Эластичность спроса по доходу.

52. Коэффициенты эластичности. Перекрестная эластичность спроса по цене

53. Общие свойства производственных функций

54. Доминирование и оптимальность по Парето

55. Эффективные решения и паретова граница

56. Основные методы решения многокритериальных задач

57. Метод обобщенного критерия

58. Методы параметрического программирования

59. Теорема Неймана

60. Матричная игра как задача линейного программирования

7 Учебно-методическое обеспечение дисциплины

7.1 Основная литература

1. Экономико-математическое моделирование: учебник/ Под ред.И.Н. Дрогобыцкого. - М.: ЭКЗАМЕН, 2006. - 798 с - ISBN 5-472-01573-1.

2. Экономико-математические методы и прикладные модели: учеб.пособие для вузов/ под ред.В.В. Федосеева. - М.: ЮНИТИ, 2002. - 391 с - ISBN 5-238-00068-5.

3. Красс, М.С. Математика для экономического бакалавриата: Учебник/ М.С. Красс, Б.П. Чупрынов. - М.: Дело, 2005. - 576 с - ISBN 5-7749-0404-0.

4. Красс, М. С. Математика для экономистов: учеб.пособие для вузов/ М. С. Красс, Б.П. Чупрынов. - CПб.: Питер, 2005. - 464 с. - (Учебное пособие). - Библиогр.: с. 461. - Предм.указ.: с. 462-464. - ISBN 5-94723-672-9.

5. Лабскер, Л. Г. Игровые методы в управлении экономикой и бизнесом: учеб. пособие для вузов / Л. Г. Лабскер, Л. О. Бабешко; Акад. нар. хоз-ва при Правительстве РФ. - М.: Дело, 2001. - 464 с - ISBN 5-7749-0233-1.

7.2 Дополнительная литература

1. Красс, М. С. Математика для экономических специальностей: учеб. для вузов/ М. С. Красс. - М.: Дело, 2003. - 704 с - ISBN 5-7749-0264-1.

2. Исследование операций в экономике: учеб. пособие для вузов/ под ред. Н.Ш. Кремера. - М.: ЮНИТИ, 2004. - 407 с. - Библиогр.: с. 393-402. - ISBN 5-238-00636-5

3. Шелобаев, С. И. Математические методы и модели в экономике, финансах, бизнесе: учеб. пособие для вузов/ С.И. Шелобаев. - М.: ЮНИТИ-ДАНА, 2001. - 367 с.

4. Бережная, Е. В. Математические методы моделирования экономических систем: учеб.пособие для вузов/ Е. В. Бережная, В. И. Бережной. - М.: Финансы и статистика, 2002. - 368 с.: ил. - ISBN 5-279-02291-8.

5. Коршунова Н.И., Плясунов В.С. Математика в экономике: - М.: Издательство «Вита - Пресс», 2001.- 368с.

6. Замков, О. О. Математические методы в экономике: учебник / О. О. Замков, А. В. Толстопятенко, Ю. Н. Черемных; общ. ред. А. В. Сидорович.- 4-е изд. стер. - М.: Дело и Сервис, 2004. - 368 с. - (Учебники МГУ им. М. В. Ломоносова) - ISBN 5-86509-054-2.

7. Акулич, И.Л. Математическое программирование в примерах и задачах: учеб.пособие/ И.Л. Акулич.- 2- е изд., испр. - CПб.: Лань, 2009. - 348 с.: ил... - Библиогр.: с. 346-347 - ISBN 978-5-8114-0916-7.

8. Вентцель, Е. С. Исследование операций: задачи, принципы, методология: учеб.пособие для вузов/ Е. С. Вентцель.- 3-е изд., стер. - М.: Дрофа, 2004. - 208 с.: ил. - (Высшее образование). - Библиогр.: с. 206. - ISBN 5-7107-7770-6.

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: