Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Задачи динамического программирования

Рис. 6.6. Дерево задач

Рис. 6.5. Решение задачи (1.2.2)

Рис. 6.4. Решение задачи (1.2.1)

 

Оптимальное решение удовлетворяет условию целочисленности исходной задачи. Для рассматриваемой задачи (27 > 26), то .

Решим задачу (1.2.2):

 

Задача (1.2.2) не имеет решения, вычеркиваем ее из общего списка.

Список задач исчерпан, о чем свидетельствует дерево задач (рис. 6.6).

 

 

 
 

 

 


 

Оптимальное целочисленное решение задачи (1.2.1) обеспечивает большее значение целевой функции, чем оптимальное целочисленное решение задачи (1.1), следовательно, его принимаем в качестве оптимального для исходной целочисленной задачи.

Ответ: оптимальное целочисленное решение: , .


 

Динамическое программирование – метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называются многошаговыми.

Начало развития динамического программирования относится к 50-м годам ХХ в. и связано с именем Ричарда Эрнеста Беллмана.

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

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

Рассматривается управляемый процесс, например, процесс распределения средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования и т.п. В результате управления система (объект управления) S переводится из начального состояния s0 в состояние sn. Пусть, управление можно разбить на n шагов, т.е. решение принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой совокупность n пошаговых управленческих решений.

Обозначим через Xk управленческое решение на k-м шаге (k=1, 2, …, n). Переменные Xk удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (Xk может быть числом, точкой в n-мерном пространстве или качественным признаком).

Пусть X=(X1, X2, …, Xn) – управление, переводящее систему S из состояния s0 в состояние sn. Обозначим через sk состояние системы (характеризуемое определенным набором параметров и конкретных их значений) после k-го шага управления. Причем состояние системы sk в конце k-го шага зависит только от предшествующего состояния sk-1 и управленческого решения на k-ом шаге Xk (т.е. не зависит напрямую от предшествующих состояний и управленческих решений). Данное требование называется «отсутствием последствия» и может быть выражено следующими уравнениями состояний:



. (11.1)

Таким образом, получаем последовательность состояний s0, s1, …, sk-1, sk, …, sn-1, sn. Тогда n-шаговый управленческий процесс схематично можно изобразить следующим образом:

 
 


Пусть показатель эффективности k-го шага выражается некоторой функцией:

, (11.2)

а эффективность всего рассматриваемого многошагового процесса следующей аддитивной функцией:

, (11.3)

или

. (11.4)

Тогда задача пошаговой оптимизации (задача динамического программирования) формулируется следующим образом: определить такое допустимое управление Х, переводящее систему S из состояния s0 в состояние sn, при котором целевая функция Z принимает наибольшее (наименьшее) значение.

Задача динамического программирования обладает следующими особенностями:

1. Задача оптимизации интерпретируется как n-шаговый процесс управления.

2. Целевая функция равна сумме целевых функций каждого шага.

3. Выбор управления на k-ом шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (отсутствие обратной связи).

4. Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1 и управления Xk («отсутствие последствия»).

5. На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние sk – от конечного числа параметров.

 

<== предыдущая лекция | следующая лекция ==>
| Общая постановка задачи динамического программирования

Дата добавления: 2013-12-12; Просмотров: 373; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:

  1. I Цели, задачи и сущность ценовой политики в маркетинге
  2. I. Общая характеристика.
  3. I. Основные задачи, принципы и уровни политики занятости и регулирования рынка труда
  4. I. Формулировка задачи и характеристики СМО
  5. II. НЕОФРЕЙДИЗМ: ОБЩАЯ ХАРАКТЕРИСТИКА, ОСНОВНЫЕ ПРЕДСТАВИТЕЛИ
  6. XVII. Многостадийные задачи в органической химии
  7. АРХИТЕКТУРА И ЕЕ ЗАДАЧИ. ОБЩИЕ ПОНЯТИЯ О ЗДАНИЯХ И СООРУЖЕНИЯХ
  8. В XXI веке архитекторам и строителям нашей страны предстоит решать не менее важные задачи в новых исторических условиях.
  9. В стратегию управления входит постановка долгосрочных целей и выработка порядка действий.
  10. Виды финансовых планов. Задачи и этапы разработки финансового плана
  11. Витамины. Роль витаминов в питании. Общая характеристика витаминов
  12. Влияние отраслей народного хозяйства на состояние окружающей среды. Общая характеристика структуры промышленного техногенеза




studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.166.231.176
Генерация страницы за: 0.085 сек.