Модели сетевого планирования: технология построения, основные определения, правила построения моделей

↑

⇐ ПредыдущаяСтр 13 из 28Следующая ⇒

15.Метод Брауна-Робинсон

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

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

После определенного количества итераций записывается ответ приближенно равный решению игры.

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

Одновременно на каждом шаге вычисляется приближенно .

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

процесс, требующий затрат труда, ресурсов и времени. Ожидание требует только затрат времени и может быть обусловлено технологией выполнения работ друг за другом. Например, затвердевание бетона, сушка древесины, обжиг деталей и т.д. Фиктивная работа представляет собой только логиче- скую зависимость между функциональными операциями, представленными действительными работами или ожиданиями. Она не требует ни времени, ни ресурсов, но показывает, что начало одной работы обусловлено либо окон- чанием другой работы, либо внешними обстоятельствами. Поэтому фиктив- ную работу вводят для отражения правильной взаимосвязи между работами при построении сетевого графика и изображают пунктирной стрелкой. Событие – это результат выполнения одной или нескольких работ. Оно не имеет продолжительности. Свершение события означает, что можно при- ступить к последующим работам. Поэтому факт свершения события являет- ся обязательным условием для начала выполнения выходящих из него работ. На сетевом графике выделяют два особых события: исходное и завершающее. Исходному событию не предшествуют работы, а завершающее событие не имеет последующих работ. Каждая работа СГР объединяет два события (начальное и конечное), поэтому обозначается двумя индексами этих событий. Всем событиям на СГР присваиваются порядковые номера i. Путь в СГР представляет собой любую последовательность работ, в ко- торой конечное событие каждой работы совпадает с начальным событием последующей работы. Путь, начало которого совпадает с исходным событием, а конец которого совпадает с завершающим событием, называется полным. Продолжительность пути L равна сумме продолжительностей составляющих работ. Полный путь, имеющий максимальную длину L, называют критическим, а работы, составляющие этот путь, называются критическими работами. Задержка выполнения любой из критических работ ведёт к более позднему сроку наступления завершающего события. У некритических пу- тей имеются резервы времени, в пределах которых продолжительность от- дельных работ может быть увеличена. За счёт этого возможно, например, перераспределение ресурсов от этих работ на критические работы. При по- строении сетевого графика необходимо соблюдать следующие правила: – в СГР не должно быть работ, имеющих одинаковые номера; – все события, кроме завершающего, должны иметь последующую рабо- ту. «Тупики» на СГР свидетельствуют либо об ошибке, либо указывают на то, что эта работа является лишней; – не должно быть событий, в которые не входит ни одна из работ, по- скольку условия их свершения не будут обеспечены; – в СГР не должно быть замкнутых контуров. Поэтому СГР представляет собой специальный вид графа; – если некоторые работы могут быть начаты после частичного выполнения работ, то предшествующую работу надо разбить на части и ввести до- полнительные события; – если для свершения события кроме работ, указанных на СГР, нужны результаты от посторонних условий, то это изображается с помощью дополнительных надписей. Процесс разработки СГР разбивается на две стадии: подготовка исход- ных данных, построение СГР. На первой стадии необходимо выявить все взаимозависимости и установить продолжительности работ. Работы ij и jk называются взаимозависимыми, если одна из них может быть начата только после завершения другой. В противном случае они могут выполняться па- раллельно. Взаимосвязь между работами обычно представляют в виде мат- рицы связей (матрицы следования), обозначаемой || αij ||. В этой матрице, состоящей из нулей или единиц, на пересечении строки j и столбца i ставит- ся αij = 1, если работа j может начаться только после завершения работы i. В противном случае эти работы независимы, и αij = 0. Как видим, эта матрица || || αij является треугольной снизу. Вторым шагом первой стадии построения СГР является оценка продол- жительности работ. Существуют два подхода к нахождению продолжитель- ности ij-й работы (tij): детерминистический и вероятностный. При первом подходе tij представляют собой некоторую нормативную (постоянную) ве- личину. При втором подходе tij есть случайная величина, но при этом извес- тен закон и параметры её распределения F(tij). После нахождения всех времён tij и составления матрицы следования || αij || переходят ко второй стадии: построению СГР. Сам процесс построения может быть либо машинным, либо с помощью графика. Остановимся на графическом представлении СГР. Используются две формы СГР: полиго- нальная и ортогональная. В первом случае работы ij изображаются в виде безмасштабных стрелок, длины которых не зависят от значения tij, и эти стрелки могут представляться под любым углом к оси абсцисс. Во втором случае работы изображаются в виде горизонтальных стрелок, длина которых пропорциональна времени tij. В нижней части графика вводится шкала вре- мени t0. Для связи параллельных веток СГР между собой используют фик- тивные работы, изображаемые пунктирными линиями. Полигональная форма обычно используется при поиске оптимального варианта СГР, нахождении узких мест и резервов для их перераспределения. Ортогональная форма более удобна в качестве средства контроля за реали- зацией её выполнения. Например, на строительстве или предприятии все работы всех служб контролируются по СГР, когда в нижней части СГР ука- заны календарные даты. Невыполнение работ к указанным срокам является сигналом для дополнительных организационно-технических мероприятий Третья стадия календарного планирования включает в себя расчёт и ана- лиз параметров СГР. В ходе этого анализа вычисляется критический путь и резерв времени выполнения работ, расположенных на других путях. При этом выполняются операции над событиями и работами.

Познавательные статьи:



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте