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

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

 

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

                                                                                              Факультет: 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 (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.