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

 

      i = 4. 
 
 
 

      Таблица 3.7

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

 
 
 

      Таблица 3.8

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

 

      i = 5. 
 

      Таблица 3.9

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

 
 
 
 
 

      Таблица 3.10

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

 
 

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

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

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

      i = 1:   x₀* = 0,   r₁* = 1,  x₁* = 35000.

      i = 2:   x₁* = 35000,  r₂* = 1,  x₂* = 60000.

      i = 3:   x₂* = 60000,  r₃* = 1,  x₃* = 100000.

      i = 4:   x₃* = 100000,  r₄* = 0,  x₄* = 100000.

      i = 5:   x₄* = 100000,  r₅* = 0,  x₅* = 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 с.