Динамическое программирование

Автор: Пользователь скрыл имя, 25 Января 2012 в 15:10, курсовая работа

Описание работы

Целью исследования является выявление наилучшего способа действия при решение той или иной задачи. Для построения математической модели необходимо иметь строгое представление о цели функционирования исследуемой системы и располагать информацией об ограничениях, которые определяют область допустимых значений.

Содержание

Введение 3
1. Динамическое программирование 5
1.1 Задача динамического программирования 5
1.2 Общая структура динамического программирования 8
2. Задача о загрузке. Общие сведения 10
3. Практическая часть. Задача 12
Заключение 19
Список литературы 21

Работа содержит 1 файл

Мат.методы.doc

— 159.50 Кб (Скачать)
 

      i = 4. 
 
 
 

      Таблица 3.7

Вспомогательная таблица на шаге 4

x3 0 25000 35000 40000 60000 65000 75000 100000
B3(x3) 5200 5200 5200 5200 2800 2800 2400 0
 
 
 

      Таблица 3.8

Основная  таблица на шаге 4

x3 r4 x4 z4 B4(x4) z4+B4 B3(x3)
0 0

1

0

30000

0

2800

2400

2400

2400

5200

5200
25000 0

1

25000

55000

0

2800

2400

2400

2400

5200

5200
35000 0

1

35000

65000

0

2800

2400

2400

2400

5200

5200
40000 0

1

40000

70000

0

2800

2400

2400

2400

5200

5200
60000 0

1

60000

90000

0

2800

2400

0

2400

2800

2800
65000 0

1

65000

95000

0

2800

2400

0

2400

2800

2800
75000 0 75000 0 2400 2400 2400
100000 0 100000 0 0 0 0
 

      i = 5. 
 

      Таблица 3.9

Вспомогательная таблица на шаге 5

x3 0 25000 30000 35000 40000 55000 60000 65000
B3(x3) 2400 2400 2400 2400 2400 2400 2400 2400
x3 70000 75000 90000 95000 100000
B3(x3) 2400 2400 0 0 0
 
 
 
 
 

      Таблица 3.10

Основная  таблица на шаге 5

x4 r5 x5 z5 B5(x5) z5+B5 B4(x4)
0 0

1

0

20000

0

2400

0

0

0

2400

2400
25000 0

1

25000

45000

0

2400

0

0

0

2400

2400
30000 0

1

30000

50000

0

2400

0

0

0

2400

2400
35000 0

1

35000

55000

0

2400

0

0

0

2400

2400
40000 0

1

40000

60000

0

2400

0

0

0

2400

2400
55000 0

1

55000

75000

0

2400

0

0

0

2400

2400
60000 0

1

60000

80000

0

2400

0

0

0

2400

2400
65000 0

1

65000

85000

0

2400

0

0

0

2400

2400
70000 0

1

70000

90000

0

2400

0

0

0

2400

2400
75000 0

1

75000

95000

0

2400

0

0

0

2400

2400
90000 0 90000 0 0 0 0
95000 0 95000 0 0 0 0
100000 0 100000 0 0 0 0
 
 

      На  этом предварительный этап завершен. Далее проводится этап условной оптимизации.

      Этап  условной оптимизации. Данный этап непосредственно  связан с вычислением функций Bi(xi) и проводится в обратном порядке для i=5,4,3,2,1. Поскольку в соответствии с общим принципом оптимальности Беллмана имеет место равенство В55)=0, т.к. на последнем шаге управления дальнейших изменений системы не происходит и соответствующий экономический эффект равен 0, то в пятый столбец основной таблицы, полученной при i=5, записываем нулевые значения. При этом в шестой столбец записываются суммы соответствующих чисел из двух предшествующих столбцов, а в последний столбец заносится максимум из всех чисел шестого столбца для каждого строчного фрагмента отдельно. Полученные значения функции В44) заносятся во вторую строку вспомогательной таблицы. Заполненные таблицы уже приведены выше. Аналогично завершается заполнение основных и вспомогательных таблиц для i=4,3,2,1.

      Этап  безусловной оптимизации. На данном этапе определяются оптимальное значение задачи Z* и оптимальное управление (r1*,r2*,r3*). Поскольку начальное состояние x0 =0 задано однозначно, то Z*=B0(x0)= 9200 избирателей, x0*=x0=0. Для построения оптимального управления просмотрим все заполненные основные таблицы в естественном порядке при i=1,2,3,4.5 используя отмеченные знаками « » строки, содержащие условно-оптимальные значения управления. Получаем такую последовательность шагов:

      i = 1:   x0* = 0,   r1* = 1,  x1* = 35000.

      i = 2:   x1* = 35000,  r2* = 1,  x2* = 60000.

      i = 3:   x2* = 60000,  r3* = 1,  x3* = 100000.

      i = 4:   x3* = 100000,  r4* = 0,  x4* = 100000.

      i = 5:   x4* = 100000,  r5* = 0,  x5* = 100000.

      Следовательно, оптимальное решение данной задачи имеет вид (1,1,1,0,0).

      По  итогам решения данной задачи можно сделать следующие выводы:

  • максимальное число избирателей при оптимальном распределении ресурсов составит 9200 человек;
  • в задаче существует только одно оптимальное решение (1,1,1,0,0), которое означает, что комитет по переизбранию должен провести предвыборную кампанию только в первых трех избирательных участках;
  • сумма используемых денежных средств в случае оптимального их распределения составит ровно 100000 руб.

 

Заключение 

    Можно выделить,  по крайней мере, четыре аспекта применения динамических методов в решении практических проблем.

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

    2. Интенсификация и повышение точности  экономических расчетов. Формализация экономических задач и применение ЭВМ  многократно ускоряют типовые, массовые расчеты, повышают точность и сокращают трудоемкость,  позволяют проводить многовариантные экономические обоснования сложных мероприятий, недоступные при господстве "ручной" технологии.

    3. Углубление количественного анализа  экономических проблем. Благодаря   применению  метода  динамического программирования  значительно усиливаются возможности  конкретного  количественного анализа, изучение многих факторов, оказывающих влияние на экономические процессы, количественная  оценка последствий изменения условий развития экономических объектов и т.п.

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

В соответствии  с  современными  научными представлениями  системы разработки и принятия хозяйственных  решений должны сочетать формальные  и неформальные методы,  взаимоусиливающие и взаимодополняющие друг друга. Формальные методы являются, прежде всего,  средством  научно  обоснованной подготовки материала для действий человека в процессах  управления.  Это  позволяет продуктивно использовать опыт и интуицию человека, его способности решать плохо формализуемые задачи.

      По  итогам решения практической (задачи) можно сделать следующие выводы:

  • максимальное число избирателей при оптимальном распределении ресурсов составит 9200 человек;
  • в задаче существует только одно оптимальное решение (1,1,1,0,0), которое означает, что комитет по переизбранию должен провести предвыборную кампанию только в первых трех избирательных участках;

сумма используемых денежных средств в  случае оптимального их распределения  составит ровно 100000 рублей.

 

Список  использованной литературы. 

  1. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. – М.:Наука,1965.-458 с.
  2. Вентцель Е. С. Элементы динамического программирования. –М.: Наука,1987. – 218 c.
  3. Вилкас Э.И. Оптимальность в играх и решениях. - М.: Наука,1990.-256с
  4. Давыдов, Э.Г. Исследование операций : учеб. пособие для студ. вузов / Э.Г. Давыдов. - М. : Высш. школа, 1990. – 383 с.
  5. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Численные методы. – М.: Просвещение, 1991 г.-176 с.
  6. Информатика. Учебник. /Под ред. И.В.Макаровой. – 3-е изд.перераб. М.:Финансы и статистика, 2005-768 с.
  7. Карманов В. Т. Математическое программирование. –М.:Наука,1986. – 312 с.
  8. Конюховский П.В. Математические методы исследования операций: пособие для подготовки к экзамену. – Спб.:Питер, 2001-192 с.
  9. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2000.-960 с.
  10. Курицкий Б.К. Поиск оптимальных решений средствами Excel 7.0. - Спб.: BHV, 1997.-384 с.
  11. Мищенко А.В., Попов А.А. Некоторые подходы к оптимизации инвестиционного портфеля , "Менеджмент в России и за рубежом", №2 / 2002.-144 с.
  12. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр: Учебное пособие для университетов. - М.: Высшая школа, Книжный дом “Университет”, 1998.-300 с.
  13. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. — 2-е изд. — М.: «Вильямс», 2006.-1296 с.
  14. Шикин Е.В. Чхартишвили А.Г. Математические методы и модели в управлении: Учебник для ВУЗов. - М.: Дело, 2000.-440 с.
  15. Щербина О.А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы, 2005, вып. 19-179 с.

Информация о работе Динамическое программирование