Математические методы, их виды

 

Содержание

1. введение…….....................................................................................(2-5) с
0. 1.1динамическоепрограммирование…………………………...….(5-6)с.
0. 1.2 Дополнительная информация ……………..…………………(6-8) с.
0. 1.3 Модели динамического программирования ………..…….…(8-11) с.
0. 1.4    Постановка задач динамического программирования выбор стратегии обновления оборудования ...............................................(11-14)с.00
2. Решение задачи …………………………………………………(14-15) с..

2.1.   Экономическая постановка задачи ……………………(14-15) с

2.2.   Численное решение задачи ……………………………..(15-20) с.

2.3    Получение результатов…………………………………(20-21) с.

3.  Описание автоматизированных расчетов  …………………..…(20-21) с.

3.1    Выбор языка программирования ……………………..…….(20-21) с.

3.2    Описание программы………………………….. ……..…….…(21-30) с.

3.3 Заключение ………….………………………………………..………(31) с.

4.Список литературы ……………………………..…………...………(31-32) с.

4.1Приложение …………………………………………………………………

4.2инструкция  для пользователя  по форме №1и№2(включая описание формы)…………………………………………………………………(32-34) с. 

     1.Введение

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

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

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

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

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

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

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

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

     Прежде  всего задачи математического программирования делятся на задачи линейного и  нелинейного программирования. При  этом если все функции f и gi линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функций нелинейная, то соответствующая задача является задачей нелинейного программирования. Наиболее изученным разделом математического программирования является линейное программирование. Для решения задач линейного программирования разработан целый ряд эффективных методов, алгоритмов и программ. Среди задач нелинейного программирования наиболее глубоко изучены задачи выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве.

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

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

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

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

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

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

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

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

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

1.2 Дополнительная информация(по динамическому програмированию).

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

     В процессе развития, а также по мере изменения экономических условий  все предприятия сталкиваются с  необходимостью совершенствования своих экономических структур. Предприятия пересматривают существующие системы управления, внедряют новые информационные системы управления, проводят реорганизацию бизнеса на основе современных методов реинжиниринга. К разряду "вечных" проблем предприятий относится проблема распределения ресурсов: ресурсы, в отличие от потребностей, всегда ограничены. Их, так или иначе, приходится распределять на различные нужды постоянно и на всех уровнях. Примерами таких задач распределения ресурсов являются динамическая задача оптимизации портфеля проектов, задача оптимизации финансирования ряда многоэтапных инвестиционных проектов в рамках некоторой целевой программы с достаточно длительным сроком реализации. Динамическое программирование является одним из наиболее эффективных методов решения подобных задач, чем и объясняется актуальность данной работы.

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

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

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

1.3 МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

Динамическое  программирование  связано  с  возможностью  пред-

ставления процесса управления в виде цепочки  последовательных дейст-

вий, или  шагов, развернутых во времени и  ведущих к цели. Таким обра-

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

виде  динамической последовательности и  интерпретировать в виде поша-

говой программы, развернутой во времени. Это позволяет  спланировать

программу будущих действий. Поскольку вариантов  возможных планов–

программ  множество, то необходимо из них выбрать лучший, оптималь-

ный по какому-либо критерию в соответствии с поставленной целью.

Динамическое  программирование  представляет  собой  математиче-

ский  аппарат, который подходит к решению  некоторого класса задач пу-

тем их разложения на части, небольшие и менее сложные задачи. При

этом  отличительной особенностью является решение задач по этапам,

через фиксированные  интервалы, промежутки времени, что  и определило

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

что методы динамического программирования успешно применяются и

при решении  задач, в которых фактор времени  не учитывается. В целом

математический  аппарат можно представить как  пошаговое или поэтап-

ное  программирование.  Решение  задач  методами  динамического  про-

граммирования проводится на основе сформулированного Р. Э. Беллма-

ном  принципа  оптимальности:  оптимальное  поведение  обладает  тем

свойством, что каким бы ни было первоначальное состояние системы и

первоначальное  решение, последующее решение должно определять оп-

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

первоначального решения.

Из этого  следует, что планирование каждого  шага должно проводиться

с учетом общей выгоды, получаемой по завершении всего процесса, что и

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

Таким образом, динамическое программирование в широком  смысле

представляет  собой  оптимальное  управление  процессом,  посредством

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

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

В  целом  динамическое  программирование  представляет  собой

стройную  теорию для восприятия и достаточно простую для применения

в коммерческой деятельности при решении как  линейных, так и нелиней-

ных задач.

Динамическое  программирование (ДП) является одним  из разделов

оптимального  программирования. Для него характерны специфические

методы  и приемы, применительные к операциям, в которых процесс при-

нятия решения  разбит на этапы (шаги). Методами ДП решаются вариант-

ные оптимизационные  задачи с заданными критериями оптимальности, с

определенными связями между переменными и  целевой функцией, вы-

раженными системой уравнений или неравенств. При этом, как и в зада-

чах, решаемых методами линейного программирования, ограничения мо-

гут быть даны в виде равенств или неравенств. Однако если в задачах ли-

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

и переменными  обязательно линейны, то в задачах  ДП эти зависимости

могут иметь  еще и нелинейный характер. ДП можно использовать как

для решения  задач, связанных с динамикой  процесса или системы, так и

для статических  задач, связанных, например, с распределением ресурсов.

Это значительно  расширяет область применения ДП для решения задач

управления. А возможность упрощения процесса решения, которая дос-

тигается  за счет ограничения области и  количества, исследуемых при пе-

реходе  к  очередному  этапу  вариантов, увеличивает  достоинства  этого

комплекса методов.

Вместе  с тем ДП свойственны и недостатки. Прежде всего, в нем нет

единого  универсального  метода  решения.  Практически  каждая  задача,

решаемая  этим методом, характеризуется своими особенностями и тре-

бует  проведения поиска наиболее приемлемой совокупности методов для

ее решения. Кроме того, большие объемы и трудоемкость решения много-

шаговых задач, имеющих множество состояний, приводят к необходи-

мости отбора задач малой размерности либо использования сжатой ин-

формации. Последнее достигается с помощью  методов анализа вариантов

и переработки  списка состояний.

Для процессов  с непрерывным временем ДП рассматривается  как

предельный  вариант дискретной схемы решения. Получаемые при этом

результаты  практически совпадают с теми, которые получаются метода-

ми максимума  Л. С. Понтрягина или Гамильтона-Якоби-Беллмана.

ДП применяется  для решения задач, в которых  поиск оптимума воз-

можен  при  поэтапном  подходе,  например,  распределение  дефицитных

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

разработка  правил управления спросом или запасами, устанавливающи-

ми момент пополнения запаса и размер пополняющего заказа; разработка

принципов календарного планирования производства и выравнивания за-

нятости в условиях колеблющегося спроса на продукцию; составление

календарных планов текущего и капитального ремонтов оборудования и

его замены; поиск кратчайших расстояний на транспортной сети; форми-

рование последовательности развития коммерческой операции и т. Д.

     . 

1.4.Постановка задач стратегии обновления оборудвания.

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

  Эксплуатация  оборудования планируется в течение  п лет, но оборудование имеет тенденцию с течением времени стареть и приносить все меньшую годовую прибыль r(t), где t — возраст оборудования. При этом есть выбор: либо в начале любого года продать устаревшее оборудование за цену s(t), которая также зависит от возраста, и купить новое оборудование за цену P, либо оставить оборудование в эксплуатации. Требуется найти оптимальный план замены оборудования с тем, чтобы суммарная прибыль за все n лет была максимальной, учитывая, что к началу эксплуатационного периода возраст оборудования составляет  t0  лет.

  Входными  данными в этой задаче являются:

r(t) — доход от эксплуатации в течение одного года оборудования возраста t лет;

S (t) — остаточная стоимость оборудовании

Р — цена нового оборудования;

t0 — начальный возраст оборудования.

  Остановимся на k-м шаге решения задачи.

  Переменной  управления на k-м шаге является логическая переменная, которая может принимать два значения:

  С — сохранить

  3 — заменить

  оборудование  в начале k-го года.

  Переменной  состояния системы на k-м шаге является переменная  t.

  Функцию Беллмана Fk(t) определим как максимально возможную прибыль от эксплуатации оборудования за годы с k-го по n-й, если к началу k-ro года возраст оборудования ссклавля t лет. Применяя то или иное управление, мы переводим систему в некоторое новое состояние, а именно, если в начале k-гo года мы оборудование сохраняем, то к началу следующего (k +1)-го года его возраст увеличится на 1 (состояние системы станет равно t+1), за этот год оно принесет прибыль r(t), и максимально возможная прибыль за оставшиеся годы (с (к+ 1)-го по n-й) составит Fk+1(t+1).

  Если  же в начале k-го года принимаем решение на замену оборудования, то мы продаем старое оборудование возраста t лет за цену S(t), покупаем новое оборудование за цену Р и эксплуатируем его в течение к-го года, что приносит за этот год прибыль r (0). К началу следующего года возраст оборудования составит 1 год, и за все годы с (k+1)-го по n-й максимально возможная прибыль будет Fk+1(1).

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

(1)

Функцию Беллмана для первого шага (к=п) легко вычислить — это максимально возможная прибыль только за последний n-й год:

(2)

  Вычислив  значение функции Fn(t) по формуле (2), далее можно

  замену  посчитать Fn-1(t), затем Fn-2(t) и так далее до F1(t0).

Функция F1 (t0) представляет собой максимально возможную прибыль за все годы (с 1-го по n-й). Этот максимум достигается при некотором управлении, применяя которое в течение первого года, мы определяем возраст оборудования к началу второго года (в зависимости от того, какое управление является для первого года оптимальным, это будет 1 или t0+1). Для данного возраста оборудования по результатам, полученным на этапе условной оптимизации, мы смотрим, при каком управлении достигается максимум прибыли за годы со 2-го по n-й и так далее. На этапе безусловной оптимизации отыскиваются годы, в начале которых следует произвести оборудования.

2.решение  задачи

2.1.   Экономическая постановка  задачи . 

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

 

     2.2.   Численное решение  задачи

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

     Решение.