Постановка задачи динамического программирования. Составление основного функционального управления динамического программирования, определяющего условный оптимальный выигрыш для данного состояния. Выбор оптимальной стратегии замены оборудования.
Аннотация к работе
Пусть рассматриваемая задача, распадающаяся на m шагов или этапов, например планирование деятельности предприятия на несколько лет, поэтапное планирование инвестиций, управление производственными мощностями в течение длительного срока. Переменная хі, от которой зависят выигрыш на i-м шаге и, следовательно, выигрыш в целом, называется шаговым управлением, i= . В основе метода динамического программирования лежит принцип оптимальности Беллмана, формулирующийся следующим образом; управление на каждом шаге надо выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до юнца процесса шагах, включая выигрыш на данном шаге. При решении задачи динамического программирования на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми друг от друга, то оптимальным шаговым управлением будет то управление, которое приносит максимальный выигрыш именно на этом шаге.Выбор переменных, характеризующих состояние s моделируемого процесса перед каждым шагом, и выявление налагаемых на них ограничений. Определение выигрыша ?i(s, xi), (1.1) который принесет на i-м шаге управление xi, если система перед этим находилась в состоянии s. 5.Определение состояния s’, в которое переходит система из состояния s под влиянием управления xi, s’=fi(s, xi), (1.2) где fi - функция перехода на i-м шаге из состояния s в состояние s’. Составление основного функционального управления динамического программирования, определяющего условный оптимальный выигрыш для данного состояния s с i-го шага и до конца процесса через уже известный условный оптимальный выигрыш с (i 1)-го шага и до конца: Wi(S) = max{ ?i(s,xi) Wi 1(fi(s,xi))}. В это уравнение в уже известную функцию Wi 1(s), характеризующую условный оптимальный выигрыш с (i 1)-го шага до конца процесса, вместо состояния s подставлено новое состояние s’=fi (s,xi), в которое система переходит на i-м шаге под влиянием управления xi.Одной из важных экономических проблем, с которыми приходиться встречаться на практике, является определение оптимальной стратегии в замене старых станков, производственных зданий, агрегатов, машин и т.д., другими словами, старого оборудования на новое. Старение оборудования включает его физический и моральный износ, в результате чего увеличиваются производственные затраты по выпуску продукции на старом оборудовании, увеличиваются затраты на его ремонт и обслуживание, а вместе с тем снижаются производительность и так называемая ликвидная стоимость. Наступает момент, когда старое оборудование более выгодно продать, заменить новым, чем эксплуатировать ценой больших затрат. При этом оборудование можно заменить либо новым оборудованием того же вида, либо новым, более совершенным в техническом отношении, с учетом технического прогресса. Оптимальная стратегия замены оборудования состоит в определении оптимальных сроков замены.В общем виде проблема ставится следующим образом: определить оптимальную стратегию использования оборудования в период времени длительностью m лет, причем прибыль за каждые I лет, i= от использования оборудования возраста t лет должна быть максимальной. Известны: r(t) - выручка от реализации продукции, произведенной за год на оборудовании возраста t лет, l(t) - годовые затраты, зависящие от возраста оборудования t, c(t) - остаточная стоимость оборудования возраста t лет, P - стоимость нового оборудования. Под возрастом оборудования понимается период эксплуатации оборудования после последней замены, выраженный в годах. В начале i-го шага, i= может быть выбрано одно из двух управлений: заменять или не заменять оборудование. Функция выигрыша на на i-м шаге - это прибыль от использования оборудования к концу на i-го года эксплуатации, t= , i= . ?i (t)= u1= uc - если оборудование в начале i-го года не заменяется;На основании входной информации получим следующую таблицу: Таблица №2 (7) найдем максимальную прибыль при замене оборудования через 2 года: По формуле Вывод: Максимальную прибыль в размере 215 единиц мы получим, если поменяем оборудование через 2 года на третий. При разработки программного обеспечения так же использовались следующие системные утилиты: Антивирусные программа (Dr.Web 4.44) В силу ряда причин, оборудование изнашивается физически, т.е. ломается и не подлежит ремонту или возникают такие неисправности, при которых проще купить новое оборудование, чем ремонтировать старое, либо изнашивается морально, т.е. темпы роста экономического развития отрасли производства этого оборудования очень велики.Для установки программы требуются следующие минимальные технические характеристики: Процессор 300 MHZ Если компьютер пользователя имеет данные технические характеристики, то программа будет работать без сбоев. Для начала процесса установки требуется распаковать архив с программой . Для запуска с компакт диска требуется: Вставить компакт диск в привод CD-ROM; Распаковать архив в свою папку и запустить Project.exe после этого можно начать работу с программой.2.Расчет •Визуализация 1.
План
Содержание
Введение
1. Постановка задачи
2. Составление математической модели динамического программирования
3. Оптимизация
4. Выбор оптимальной стратегии замены оборудования как задача динамического программирования
5. Алгоритм решения задачи
6. Порядок установки
Заключение
Приложение А, формы программы
Приложение В, листинг программы
Введение
В ряде реальных экономических и производственных задач необходимо учитывать изменение моделируемого процесса во времени и влиянии времени на критерий оптимальности. Для решения указанных задач используется метод динамического планирования (динамическое планирование). Этот метод более сложен по сравнению с методами расчета статических оптимизационных задач, изложенных выше. Также не простым делом является процесс построения для реальной задачи математической модели динамического программирования.
1. Постановка задачи динамического программирования. Основные условия и область применения
Пусть рассматриваемая задача, распадающаяся на m шагов или этапов, например планирование деятельности предприятия на несколько лет, поэтапное планирование инвестиций, управление производственными мощностями в течение длительного срока. Показатель эффективности задачи в целом обозначим через W, а показатели эффективности на отдельных шагах - через ?i, i=1,m. Если W обладает свойством аддитивности, т.е. m
W=? ?i , I=1
То можно найти оптимальное решение задачи методом динамического программирования.
Таким образом, динамическое программирование - это метод оптимизации многошаговых или многоэтапных процессов, критерий эффективности которых обладает свойством. В задачах динамического программирования критерий эффективности называется выигрышем. Данные процессы управляемые, и от правильного выбора управления зависит величина выигрыша.
Переменная хі, от которой зависят выигрыш на i-м шаге и, следовательно, выигрыш в целом, называется шаговым управлением, i= .
Управлением процесса в целом (х) называется последовательность шаговых управлений х=(х1, х2,…,хі,…,хм).
Оптимальное управление х* - это значение управления х, при котором значение W (х*) является максимальным (или минимальным, если требуется уменьшить проигрыш)
W*=W (х*)=max{W (х)}, x€X, где X - область допустимых управлений.
Оптимальное управление х* определяется последовательностью оптимальных шаговых управлений х*=(х*1,х*2,…,х*i, ,х*m).
В основе метода динамического программирования лежит принцип оптимальности Беллмана, формулирующийся следующим образом; управление на каждом шаге надо выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до юнца процесса шагах, включая выигрыш на данном шаге.
При решении задачи динамического программирования на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми друг от друга, то оптимальным шаговым управлением будет то управление, которое приносит максимальный выигрыш именно на этом шаге. Но, например, при покупке новой техники взамен устаревшей на ее приобретение затрачиваются определенные средства. Поэтому прибыль от ее эксплуатации, вначале может быть небольшой. Однако в следующие годы новая техника будет приносить большую прибыль. И, наоборот, если руководитель примет решение оставить старую технику для получения прибыли в текущем году, то в дальнейшем это приведет к значительным убыткам. Данный пример демонстрирует следующий факт: в многошаговых процессах все шаги зависят друг от друга, и, следовательно, управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на весь процесс.
Другой момент, который следует учитывать при выборе управления на данном шаге, - это возможные варианты окончания предыдущего шага. Эти варианты определяют состояние процесса. Например, при определении количества средств, вкладываемых в предприятие в i-м году, необходимо знать, сколько средств осталось в наличии к этому году, какая прибыль получена в предыдущем (i-м) году. Таким образом, при выборе шагового управления необходимо учитывать: 1) возможные исходы предыдущего шага
2) влияние управления на все оставшиеся до конца процесса шаги.
В задачах динамического программирования первый пункт учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и проводя для каждого из вариантов условную оптимизацию. Выполнение второго пункта обеспечивается тем, что в задачах динамического программирования условная оптимизация проводится от конца процесса к началу. Сперва оптимизируется последний m-й шаг, на котором не надо учитывать возможные воздействия выбранного управления xm на все последующие шаги, так как эти шаги просто отсутствуют. Делая предположения об условиях окончания (m-1)-го шага, для каждого из них проводят условную оптимизацию m-го шага и определяют условное оптимальное управление xm. Аналогично поступают для (m-1)-го шага, делая предположения о исходах окончания (m-2)-го шага и определяя условное оптимальное управление на (m-1)-м шаге, приносящее оптимальный выигрыш на двух последних шагах - (m-1)-м и m-м. Так же действуют на всех остальных шагах до первого. На первом шаге, как правило, не надо делать условных предположений, так, как состояние системы перед первым шагом обычно известно.
Для этого состояния выбирают оптимальное шаговое управление, обеспечивающее оптимальный выигрыш на первом и всех последующих шагах. Это управление является безусловным оптимальным управлением на первом шаге и, зная его, определяются оптимальное значение выигрыша и безусловные оптимальные управления на всех шагах.