Динамическое программирование. Задача о замене оборудования

Государственное образовательное  учреждение высшего                             профессионального образования                                                                                                             Санкт-Петербургский государственный  технологический институт                          (Технический университет)

 

   Кафедра:                 Экономики и логистики                     

                                                                                              Факультет: 5

                                                                                              Курс:   2  

                                                                                              Группа:  588

    Учебная  дисциплина:                                                      Статистика

 

                                                 КУРСОВАЯ РАБОТА

Тема:         Динамическое программирование. Задача о замене оборудования.

 

 Студент:                       Подпись ________                 Романова А. В.

Руководитель:              Подпись_________                  Межевич К. Г.

 

 

 Оценка:  ________                                 Подпись руководителя   _________                                                          

                                                                   

 

Санкт-Петербург

2010

Содержание:

 

1. Введение………………………………………………………………......стр.3

2.Динамическое программирование……………………………………......стр.4

2.1.  Целочисленное  программирование…………………………………....стр.5

2.2.  Идеи и алгоритм решения задач динамического программирования.стр.6

2.3. Достоинства динамического программирования…………….............стр.11

3. Задача о замене  оборудования. Постановка задачи  в общем виде……стр.12

3.1.Задача 1…………………………………………………………………..стр.16

3.2.Задача 2…………………………………………………………………..стр.19

3.3. Задача 3……………………………………………………………….....стр.23

3.4. Задача 4………………………………………………………………….стр.26

4. Заключение………………………………………………………………..стр.29

5. Список литературы……………………………………………………….стр.31

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Введение.

Словосочетание динамическое программирование впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования.

Слово «программирование» в словосочетании «динамическое  программирование» в действительности к традиционному программированию (написанию кода) почти никакого отношения не имеет и происходит от словосочетания «математическое программирование», которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программирование в данном случае понимается как допустимая последовательность событий.

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

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

 

 

 

 

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

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

Процессы принятия решений, которые строятся по такому принципу, называются многошаговыми процессами. Математически оптимизационная  задача строится с помощью таких соотношений, которые последовательно связаны между собой: например, полученный результат для одного года вводится в уравнение для следующего (или, наоборот, для предыдущего) и т. д. Таким образом, можно получить на вычислительной машине результаты решения задачи для любого избранного момента времени и «следовать» дальше. Динамическое программирование применяется не обязательно для задач, связанных с течением времени. Многошаговым может быть и процесс решения вполне статической задачи. Таковы, например, некоторые задачи распределения ресурсов

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

Поэтому в данном случае применяют модель общей задачи математического  программирования с ограничением   (целочисленны).

Множество реальных задач  характеризуются как дискретные. Причиной этому служит физическая неделимость некоторых факторов и объектов расчета. Так, на практике невозможно построить примерно 2,3 завода или принять на работу 1/5 землекопа. Все отраслевые задачи составляются на основе точного количества предприятий или проектных вариантов. Что касается планирования, то здесь используются типовые размеры предприятий, типовые мощности агрегатов. Такие элементы, в свою очередь вносят дискретность в реализацию расчетов.

Существуют так называемые плановые показатели — это годовые, месячные или суточные периоды, которые являются дискретными, раздельными. Каждый из элементов предполагает свое начало и конец.

Дискретное программирование также называют целочисленным. По этому  поводу среди ученых возникают разногласия. С одной стороны, как видно, из примеров, в таком программировании действительно используются целые числа, с другой — в целом дискретное программирование не является исключительно целочисленным.¹

 

 

 Целочисленное программирование.  

 

 

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

Задачи и методы, относящиеся  к перечисленному кругу вопросов, в литературе именуются по-разному. Наибольшее распространение получил  термин «целочисленное программирование», однако встречаются и такие как «дискретное программирование», реже «комбинаторное (или диофантово) программирование».

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

 

2.    Идеи и алгоритм решения задач динамического программирования.

Идеи:

Планируя многошаговый процесс, необходимо выбирать управляющее воздействие на каждом шаге с учетом его будущих последствий на еще предстоящих шагах. Однако, из этого правила есть исключение. Среди всех шагов существует один, который может планироваться без "заглядывания в будущее". Какой это шаг? Очевидно, последний — после него других шагов нет. Этот шаг, единственный из всех, можно планировать так, чтобы он как таковой принес наибольшую выгоду. Спланировав оптимально этот последний шаг, можно к нему пристраивать предпоследний, к предпоследнему — предпредпоследний и т.д.

Поэтому процесс динамического программирования на 1-м этапе разворачивается от конца к началу, то есть раньше всех планируется последний,

N-й шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Очевидно, нужно сделать все возможные предположения о том, чем кончился предпоследний, (N — 1)-й шаг, и для каждого из них найти такое управление, при котором выигрыш (доход) на последнем шаге был бы максимален. Решив эту задачу, мы найдем условно оптимальное управление  на N-м шаге, т.е. управление, которое надо применить, если (N — 1)-й шаг закончился определенным образом.

Предположим, что эта  процедура выполнена, то есть для  каждого исхода

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

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

    Теперь предположим,  что условно оптимальное управление  на каждом шаге нам известно: мы знаем, что делать дальше, в каком бы состоянии ни  был процесс к началу каждого  шага. Тогда мы можем найти уже не "условное", а действительно оптимальное управление на каждом шаге.                       

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

Таким образом, в процессе оптимизации управления методом  динамического программирования многошаговый процесс "проходится" дважды:

—   первый раз —  от конца к началу, в результате чего находятся условно оптимальное управление  на каждом шаге и оптимальный выигрыш (тоже условный) на всех шагах,  начиная с данного и до конца процесса

• второй раз — от начала к концу, в результате чего находятся оптимальные управления на всех шагах процесса.       

Можно сказать, что процедура  построения оптимального управления

методом динамического  программирования распадается на две  стадии: предварительную и окончательную. На предварительной стадии для каждого  шага определяется условно оптимальное  управление, зависящее от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация — также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.²

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

 

Граф подзадач (ребро  означает, что одна задача зависит от решения другой) для чисел Фибоначчи (граф — ациклический).

Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.

1. Разбиение задачи на подзадачи меньшего размера.
2. Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
3. Использование полученного решения подзадач для конструирования решения исходной задачи.

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).³

 

 

Типовой алгоритм решения задач методом динамического программирования:

1. Описать строение оптимальных решений.
2. Выписать рекуррентное соотношение, связывающие оптимальные значения параметра для подзадач.
3. Двигаясь снизу вверх, вычислить оптимальное значение параметра для подзадач.
4. Пользуясь полученной информацией, построить оптимальное решение.

Для решения задач  оптимизации существует специальная  теория, большая заслуга в ее создании принадлежит Р. Беллману, в общем виде она достаточна сложна.⁴ 

Метод динамического программирования может применяться только для определенного класса задач. Эти задачи должны удовлетворять таким требованиям:

1. Задача оптимизации интерпретируется как n-шаговый процесс управления.
2. Целевая функция равна сумме целевых функций каждого шага.
3. Выбор управления на i-м шаге зависит только о состояния системы к этому шаге, не влияет на предшествующие шаги (нет обратной связи).
4. Состояние после i-го шага управления зависит только от предшествующего состояния   управления (отсутствие последействия).
5. На каждом шаге управление зависит от конечного числа управляющих переменных, а состояние от конечного числа параметров.

В основе решения всех задач динамического программирования лежит "принцип оптимальности" Беллмана, который выглядит следующим образом:  
Каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.  
Этот принцип впервые был сформулирован Р. Беллманом в 1953 г. Им же четко были сформулированы и условия, при которых принцип верен. Основное требование - процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.

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

 

       2.3. Достоинства  динамического   программирования:

 

1. Идея и метод динамического программирования наиболее приспособлены к дискретным задачам, каковыми являются задачи из экономики.

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

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

4. Метод динамического программирования дает возможность анализа чувствительности к изменению исходных данных S_i и n. Фактически здесь решается не одна задача, а множество однотипных задач для различных состояний S_i и различных на каждом шаге. Поэтому при изменении исходных данных можно не решать задачу заново, а сделать лишь несложные добавления к уже выполненным расчетам, т.е. продолжить уже решенную задачу за счет увеличения числа шагов n или числа значений S_i.⁶

 

4. Задача о замене оборудования. Постановка задачи в общем виде.

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

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

Обозначим через r(t) и c(t) прибыль от эксплуатации t–летнего механизма на протяжении года и затраты на его обслуживание за тот же период. Далее пусть  s(t) - стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна I.

Элементы модели динамического  программирования таковы :

1. Этап і представляется порядковым номером года і, і=1,2,...n
2. Вариантами решения на i–м этапе ( т. е. для i–го года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале i–го года.
3. Состоянием на i–ом этапе является срок эксплуатации (возраст) механизма к началу i–го года.

Пусть f_i(t)– максимальная прибыль, получаемая за годы от i до n  при условии, что в начале i–го года имеется механизм t– летнего возраста.

Рекуррентное уравнение  имеет следующий вид:

 

1. – если эксплуатировать механизм
2. – если заменить механизм.⁷

Постановка  задачи в общем виде.

Рассмотрим задачу  в общей  постановке.

Пусть в течение периода, состоящего из n этапов, предприятие использует оборудование, которое вместе с установкой имеет стоимость I. Со временем оборудование изнашивается. При этом:

1. суммарная производительность оборудования  r(t) снижается, так как увеличивается время, необходимое для его профилактики и ремонта;

     2) возрастают затраты на обслуживание и ремонт c(t) данного оборудования. Требуется определить моменты (их для длительного периода эксплуатации оборудования может быть несколько), когда следует заменять старое оборудование на новое, чтобы суммарная прибыль за весь период эксплуатации оборудования была максимальной. Под прибылью имеется в виду чистый доход от продажи выпущенной продукции за вычетом стоимости обслуживания и ремонта или замены оборудования. Предполагается, что заменяемое оборудование имеет нулевую стоимость, а доход от его реализации

по остаточной стоимости не учитывается. Это допущение не является принципиальным и введено для упрощения анализа.

Обозначим моменты начала каждого  этапа через  ; 

момент завершения всего периода  — через  . Тогда на каждом этапе мы можем выбрать одно из двух возможных управлений:

  — сохранить установленное  оборудование и продолжать его  эксплуатацию;

   — приобрести новое оборудование  и заменить старое.

Здесь следует подчеркнуть, что  управленческие решения могут применяться только в моменты

Оптимальной инвестиционной политикой (стратегией управления) U* называется совокупность таких решений    , в результате реализации которых рассматриваемое производство за n шагов переходит из начального     состояния в конечное        и при этом суммарная прибыль от эксплуатации оборудования достигает максимального значения. Состояние процесса на i-ом      этапе характеризуется возрастом оборудования. Максимально возможный возраст оборудования в момент     равен i, а минимальный равен 1, если на предыдущем этапе произошла замена оборудования.

Прибыль    ,получаемая на i-м этапе, зависит от состояния оборудования  и сделанного нами выбора (управления) :

    

где r(0) — стоимость продукции, выпускаемой на новом оборудовании;

s(t) – стоимость продажи оборудования, который эксплуатировался t лет;

I — полная стоимость нового оборудования.

Очевидно, что суммарная  прибыль F, которую требуется максимизировать  для разработки оптимальной инвестиционной политики, равна сумме прибылей на каждом из этапов производства. Таким образом, суммарная прибыль будет определяться по формуле:

В выражении (2) критерий является аддитивным. Для оптимизации  подобных критериев возможно использование методов динамического программирования.

Таким образом, суть разработки оптимальной инвестиционной политики — это получение максимального  значения суммарной прибыли F. Она  зависит от результатов управления процессом эксплуатации оборудования на каждом шаге. Особенностью динамического программирования является рассмотрение процесса от конца к началу, то есть сначала анализируется n-1 этап, ищется здесь оптимальное решение, затем то же делается на n-2 этапе и т.д.  Таким образом, основой математического аппарата для нахождения оптимального решения является принцип оптимальности Беллмана:

           (3)

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

Управление    выбирают следующим образом:

1) для всех возможных  управлений    определяются значения сумм

        (4),

которые сравниваются между  собой;

2) в качестве условно  оптимального управления выбирается  то управление, которое соответствует  наибольшему значению      (при решении задачи максимизации).

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

При выборе управления на предпоследнем этапе (при i = n-1) никаких дальнейших шагов по эксплуатации оборудования не планируется, так что естественно считать . Тогда в сумме (4) остается лишь первое слагаемое. Таким образом, процесс продвигается от конечного этапа к начальному и на всех промежуточных шагах находятся значения:

– условно оптимальных  управлений   для каждого из возможных состояний ;

– оптимальное значение    .

Вектор оптимального управления U* всего процесса будет  получен при объединении найденных  в ходе вычислений условно оптимальных управлений U*:

   

⁸

 

1. Задача 1.

Пусть требуется выработать оптимальную стратегию для эксплуатации оборудования на 6-ти летнем периоде (табл. 1).

Таблица 1.

Возраст оборудования – t(лет)	0	1	2	3	4	5
Производительность оборудования – r(t) (млн. руб.)	9	8	7	6	5	5
Затраты на ремонт – c(t) (млн. руб.)	1	1	2	2	3	4

 

Стоимость нового комплекта  оборудования I=6 млн. руб. Будем предполагать, что за пределами срока, представленного в таблице, эксплуатация оборудования нас не интересует.

Обозначения:

(t) – максимальный доход на временном отрезке i, . . . , n, при возрасте оборудования    лет в начале i−го года.

  – начальные затраты на приобретение и установку нового оборудования (цена нового оборудования).

Составляем уравнение  Беллмана.

Приведем расчеты. После  пятого этапа эксплуатация оборудования не предусматривается, поэтому будем  иметь:

 

Этап 5:

			Оптимальное решение
				решение
1	8-1=7	9-6-1=2	7	c
2	7-2=5	9-6-1=2	5	c
3	6-2=4	9-6-1=2	4	с
4	5-3=2	9-6-1=2	2	с,н
5	5-4=1	9-1-6=2	2	н