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

 

Содержание

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 МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

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

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

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

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

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

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

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

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

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

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