Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





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

Пусть процесс имеет 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. В пунктах А1, А2, А3 производится однородная продукция в количествах а1, а2, а3 единиц. Готовая продукция поставляется в пункты В1, В2, В3, В4, потребности которых составляют b1, b2 , b3 , b4 единиц. Стоимости сij перевозок единицы продукции из пункта Аi в пункт Вj заданы матрицей . Требуется найти оптимальный план методом дифференциальных рент.



1. а1=500 а2=200 а3=600 b1=250 b2=150 b3=350 b4=250

2. а1=500 а2=900 а3=100 b1=200 b2=650 b3=150 b4=300

3. а1=200 а2=500 а3=300 b1=150 b2=450 b3=50 b4=50

4. а1=250 а2=650 а3=300 b1=350 b2=50 b3=150 b4=450

5. а1=350 а2=750 а3=300 b1=200 b2=50 b3=600 b4=400

6. а1=450 а2=200 а3=350 b1=150 b2=300 b3=50 b4=400

7. а1=300 а2=700 а3=400 b1=250 b2=450 b3=150 b4=350

8. а1=250 а2=550 а3=350 b1=300 b2=150 b3=400 b4=150

9. а1=750 а2=200 а3=550 b1=450 b2=300 b3=350 b4=250

10. а1=400 а2=300 а3=500 b1=350 b2=250 b3=150 b4=250

Задание № 2

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

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

 

Задание № 3

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

U (x1; x2)

,

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

Все необходимые числовые данные приведены в таблице 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.

 









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


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.