Студопедия

КАТЕГОРИИ:


Архитектура-(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)

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




Пусть рассматривается задача, распадающаяся на m шагов или этапов, например планирование деятельности предприятия на несколько лет, поэтапное планирование инвестиций, управ­ление производственными мощностями в течение длительного срока. Показатель эффективности задачи в целом обозначим че­рез W, а показатели эффективности на отдельных шагах — через qi, i =1,m. Если W обладает свойством аддитивности, т.е.

(1)

то можно найти оптимальное решение задачи методом динами­ческого программирования.

Таким образом, динамическое программирование — это ме­тод оптимизации многошаговых или многоэтапных процессов, критерий эффективности которых обладает свойством (1). В задачах динамического программирования критерий эффектив­ности называется выигрышем. Данные процессы управляемые, и от правильного выбора управления зависит величина выигрыша.

Определение 1. Переменная xi, от которой зависят выиг­рыш на i-м шаге и, следовательно, выигрыш в целом, называется шаговым управлением, i =1,m.

Определение 2. Управлением процесса в целом х называется последовательность шаговых управлений х = (х{, х2,.. •, х{,..., хт).

Определение 3. Оптимальное управление х* — это значение управления х, при котором значение W(x*) является максималь­ным (или минимальным, если требуется уменьшить проигрыш)

W(x*)=max {W(x)} (2)

где Х- область допустимых управлений. Оптимальное управление х* определяется последователь­ностью оптимальных шаговых управлений

x*=(x1*,x2*,…, xi*, …, xm*)

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

{Поясним это правило. При решении задачи динамического программирования на каждом шаге выбирается управление, ко­торое должно привести к оптимальному выигрышу. Если счи­тать все шаги независимыми друг от друга, то оптимальным шаговым управлением будет то управление, которое приносит максимальный выигрыш именно на данном шаге. Но J 'Напри­мер, при покупке новой техники взамен устаревшей на ее при­обретение затрачиваются определенные средства. Поэтому при­быль от ее эксплуатации вначале может быть небольшой. Однако в следующие годы новая техника будет приносить большую при­быль. И наоборот, если руководитель примет решение оставить старую технику для получения прибыли в текущем году, то в дальнейшем это приведет к значительным убыткам. Данный при­мер демонстрирует следующий факт: в многошаговых процессах все шаги зависят друг от друга, и, следовательно, управление на каждом конкретном шаге надо выбирать с учетом его буду­щих воздействий на весь процесс.}

При выборе шагового управления необ­ходимо учитывать:

1. возможные исходы предыдущего шага и 2) вли­яние управления на все оставшиеся до конца процесса шаги.

В задачах динамического программирования первый пункт учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и проводя для каждого из вариантов условную оптимизацию. Выполнение второго пункта обеспечивается тем, что в задачах динамическо­го программирования условная оптимизация проводится от конца процесса к началу. Сначала оптимизируется последний m-й шаг, на котором не надо учитывать возможные воздействия выбран­ного управления хт на все последующие шаги, так как эти шаги просто отсутствуют. Делая предположения об условиях окончания (m-l)-гo шага, для каждого из них проводят условную оптимиза­цию m-го шага и определяют условное оптимальное управление хт. Аналогично поступают для (m-1)-гo шага, делая предположе­ния об исходах окончания (m-2)-го шага и определяя условное оп­тимальное управление на (m-1)-м шаге, приносящее оптимальный выигрыш на двух последних шагах — (m-1)-м и m-м. Так же дей­ствуют на всех остальных шагах до первого. На первом шаге не надо делать условных предположений, так как состо­яние системы перед первым шагом обычно известно.

Для этого состояния выбирают оптимальное шаговое управ­ление, обеспечивающее оптимальный выигрыш на первом и всех последующих шагах. Это управление является безусловным опти­мальным управлением на первом шаге и, зная его, определяются оптимальное значение выигрыша и безусловные оптимальные управления на всех шагах.




Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 497; Нарушение авторских прав?; Мы поможем в написании вашей работы!


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



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.