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

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

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

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

Каждый прибор может обслуживать одновременно одну или несколько заявок. Например, лифт высотного здания обслуживает сразу несколько человек, а кассир – только одного. Во-вторых, системы массового обслуживания могут быть однофазными и многофазными. В первом случае заявка обслуживается только одним прибором, после чего покидает систему. Например, покупатель билета в театре. Во втором случае заявка должна пройти некоторую последовательность «приборов».  Например, в сберкассе, прежде чем получить деньги, человек сначала должен быть обслужен контроллером и только потом кассиром. В-третьих, каждый «прибор» обслуживает заявку в течение некоторого промежутка времени. Иногда продолжительность того промежутка является заданной, иногда ее считают случайной величиной с заданным распределением.

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

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

1.3             Теория игр

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

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

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

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

2.                      Другим источником неопределенности является влияние случайных факторов. Игры, в которых исход оказывается неопределенным исключительно в результате случайных причин, называются азартными (игры в кости, рулетка).

3.                      Третий источник неопределенности состоит в отсутствии информации о действиях противника, о его стратегии. Игры такого рода называются стратегическими.

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

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

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

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

v1+v2+…+vi+…vn=0.

     Число vi может быть положительным, отрицательным или равным нулю. При vi > 0 – выигрыш, vi < 0 – проигрыш и vi= 0 – ничейный исход.

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

      Развитие игры во времени сводится к ряду последовательных действий или вариантов решений. Выбор одного из предусмотренных правилами игры вариантов называется ходом. Ходы делятся на личные и случайные. Личным ходом называется сознательный выбор одним игроком одного из возможных в данной ситуации ходов и его осуществление. Случайным ходом называется выбор из ряда возможностей, который осуществляется не игроком, а каким-либо механизмом случайного выбора. Игры могут состоять из личных, случайных и смешанных ходов.

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

     В общем виде постановка задачи парной игры с нулевой суммой сводится к следующему виду : если два игрока Р1 и Р2 играют в какую-либо игру, то как должен вести партию каждый из этих игроков, чтобы достигнуть наиболее благоприятного для себя исхода. При случайных ходах этих двух игроков естественной оценкой благоприятного исхода является среднее значение, которое обозначается символом аij. Если известны значения aij выигрыша, то парную игру можно записать в виде прямоугольной таблицы, которая называется матрицей выигрышей или платежной матрицей. Она имеет такой вид:

    В матрице xi обозначают ходы игрока Р1, а yi – ходы игрока Р2.

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

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

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

Сетевое планирование и управление возникло в 1957-1958 гг. под  названием «метод критического  пути» и метод PERT (метод оценки и пересмотра планов), то есть оно имеет наибольшую историю

Методы сетевого планирования и управления предусматривают:

1.               представление планов в виде сети;

2.               определение календарных графиков;

3.               определение вероятных величин;

4.               возможность применения в различных условиях.

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

Методы сетевого планирования и управления дают возможность:

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

2.                  предсказать вероятное время выполнения;

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

4.                  проверить ход выполнения работ по плану после того, как план приведен в действие;

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

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