Сетевые методы планирования и управления

Содержание

Введение……………………………………………………..………………………3

1. Теоретические вопросы……………………………………………………….....5

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

1.2 Теория массового обслуживания ………………………………….……….9

1.3 Теория игр …………………………………………………………………..12

1.4 Сетевые методы планирования и управления…………………………….15

1.5 Линейное программирование……………………………………………...20

2. Практическое применение………………………………………………………21

2.1  Динамическое программирование…………………………………………21

2.2  Теория массового обслуживания…………………………………………..24

2.3  Теория игр …………………………………………………………………..25

2.4  Сетевые методы планирования и управления…………………………….28

2.5  Линейное программирование……………………………………………...29

Выводы………………………………………………………………..…………….35

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

Введение

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

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

                   Управление и планирование являются наиболее сложными функциями в работе предприятия, фирм, служб администраций на всех уровнях.

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

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

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

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

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

1.     Теоретические вопросы

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

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

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

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

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

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

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

Рассмотрим некоторый развивающийся во времени управляемый процесс, т.е. такой, на развитие которого можно влиять принимаемыми решениями. Предполагается, что процесс распадается (естественно или искусственно) на N шагов (этапов). Состояние процесса на начало каждого шага будем характеризовать векторами Si =(Si1;…;Sim). Этот вектор называют вектором состояния процесса. Множество всех состояний, в которых может находиться процесс на начало i-го шага, обозначим через Si. Начальное состояние процесса считается известным, т.е. вектор Sо задан.

Развитие процесса заключается в последовательном переходе из одного состояния в другое. Если процесс находится в состоянии Si, то состояние его Si+1 на следующем шаге определяется не только вектором Si, но и решением Иi, принятым на i-м шаге.

Запишем это следующим образом: Si+1 = φ (Si; Иi). Ясно, что решение на каждом шаге не может быть совершенно произвольным, его следует выбирать из некоторого множества Vi   возможных решений. Развитие процесса в течение всего рассматриваемого периода можно однозначно описать последовательностью состояний Sо;S1;….;SN-1;SN где SI Є СI . Любую последовательность И0,И1,…,ИN-1 допустимых решений, переводящую процесс из начального состояния Sо в конечное SN будем называть стратегией. Для более полного описания N – шагового процесса каждой стратегии надо сопоставить некоторую оценку – значение целевой функции  Fn(S).Зададим целевую функцию в виде суммы оценочных функций Ri(Si; Si+1), значения которых получаются на каждом шаге процесса при переходе из состояния SI в состояние SI+1, т.е. Fn(S) = Σ ri(SI; SI+1). Такая форма целевой функции соответствует аддитивной задаче динамического программирования. Теперь можно сказать, что многошаговый процесс полностью описан, если заданы: целевая функция, допустимое множество состояний СI, допустимое множество решений VI, правило перехода из одного состояния в другое под воздействием выбранного решения.

Общую задачу динамического программирования можно сформулировать следующим образом:

- найти стратегию И* = {И*0; И*1;…;И*N-1},

- доставляющую экстремум функции Fn(S) = Σ ri (SI; SI+1), при условии Sо – вектор начального состояния процесса, SI+1 = φ (SI;ИI), SЄ СI,  ИI Є VI (i=0,..,N-1).

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

Итак, при решении оптимизационной задачи методом динамического программирования необходимо учитывать на каждом шаге последствия, к которым приведет в будущем решение, принимаемое в данный момент. Исключением является последний шаг, которым процесс заканчивается. Здесь процесс сложно спланировать таким образом, чтобы последний шаг сам по себе приносил максимальный эффект. Спланировав оптимальным образом последний шаг, можно к нему «пристраивать» предпоследний так, чтобы результат этих двух шагов был оптимальным и т.д. Именно так – от конца к началу – и можно развернуть процедуру принятия решений. Но чтобы принять оптимальное решение на последнем шаге надо знать, чем мог закончиться предпоследний шаг. Значит, надо сделать разные предположения о том, чем мог закончиться предпоследний шаг и для каждого из предположений найти решение, при котором эффект на последнем шаге был бы наибольшим. Такое оптимальное решение, найденное при условии, что предыдущий шаг закончился определенным образом, называют условно оптимальным. Аналогично оптимизируется решение на предпоследнем шаге, т.е. делаются все возможные предположения о том, чем мог завершиться шаг, предшествующий предпоследнему, и для каждого из возможных исходов выбирается такое решение на предпоследнем шаге, чтобы эффект за последние два шага (из которых последний уже оптимизирован) был наибольшим и т.д. В принципе динамическое программирование может разворачиваться  и в прямом направлении, т.е. от первого шага процесса к последнему.

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

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

1.2 Теория массового обслуживания

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

Работа любой такой системы заключается в обслуживании поступающего на нее потока требований, или заявок (вызова абонентов, приход покупателей в магазин, требования на выполнение работы в мастерской и т.д.). Заявки поступают в систему одна за другой в некоторые, вообще говоря, случайные моменты времени. Обслуживание поступившей заявки продолжается какое-то время, после чего система освобождается для обслуживания очередной заявки.

Поскольку обслуживающая система обычно имеет ограниченную пропускную способность, а заявки поступают нерегулярно, то время от времени создается очередь заявок в ожидании обслуживающего устройства, иногда же оборудование простаивает в ожидании заявок. Наиболее часто предполагается, что известен вероятностный закон, управляющий поступлением заявок. Впервые такой подход был применен датским математиком А.К. Эрлангом в начале нашего века для анализа работы телефонной станции. С тех пор методы массового обслуживания начали применяться для анализа разнообразных проблем. Системы массового обслуживания встречаются практически везде, где есть или может возникнуть очередь. На Западе методы массового обслуживания даже получили название «теория очередей». Поскольку обычно очередь – явление нежелательное, то для ее ликвидации естественно  предложить увеличить мощность (пропускную способность) обслуживающих устройств.  Однако поскольку заявки поступают нерегулярно, то с увеличением своей мощности оборудование все большую долю времени будет простаивать, что также нежелательно. Таким образом, с экономической точки зрения задачи массового обслуживания сводятся к нахождению компромисса между двумя противоречивыми требованиями: требованием ликвидировать очередь и требованием полной загрузки оборудования. Убытки от возникновения очереди связаны с потерей времени покупателями в магазинах, простоев автолюбителей на автозаправочных станциях, у мостов и перекрестках и т.д. Простой оборудования означает непродуктивное использование вложенных в него средств, которые в другом месте могли бы приносить пользу.