Методы расчета параметров сетевых моделей. Табличный метод расчета параметров сетевой модели.

Основные параметры сетевых моделей — это критический путь, резервы времени событий, работ и путей.

Методы расчета параметров сетевой модели делятся на две группы.

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

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

Анализ сетевых моделей

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

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

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

L1 = [(0, 1) (1, 2) (2, 4) (4, 6) (6, 8) (8, 9)]

L2 - [(0, 1) (1, 3) (3, 5) (5, 6) (6, 8) (8, 9)]

L3 = [(0, 1) (1, 3) (3, 5) (5, 6) (8, 9)]

L4 - [(0, 1) (1, 3) (3, 5) (5, 7) (7, 8) (8, 9)]

Определим длительность этих путей:

Т1 = t(L1) = t0, 1 + t1, 2 + t2, 4 + f4, 6+ t6, 8 + t8, 9 = 16 + 16 + 6 + 8 + 2 + 3 = 50 дн.

Т2 = t(L2) = t0, 1 + t1, 3 + t3, 5 + f5, 6+ t6, 8 + t8, 9 =15 + 6 + 5 + 6 + 2 + 3=37дн.

Т3 = t(L3) = t0, 1 + t1, 3 + t3, 5 + f5, 6+ t8, 9 = 15 + 6 + 5 + 14 + 3 = 43 дн.

Т4 = t(L4) = t0, 1 + t1, 3 + t3, 5 + f5, 7+ t7, 8 + t8, 9 = 15+ 6 + 5 + 8 + 4 + 3 = 41 дн.

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

ТКР = max {t(Li)} = 50 дн.

 

Длительность пути L2 составляет t(L2) = 37 дней минимальна, однако не позволяет выполнить все работы комплекса.

Длительность пути L2 составляет t(L2) - 50 дней, однако за это время все работы комплекса могут быть выполнены. Следовательно, минимальное время, за которое может быть выполнен весь комплекс работ, составляет 50 дней, следовательно, путь L1 является критическим.

Теперь определим полные резервы времени по всем путям:

R(L1)=TKP-T1=0

R(L2)=TKP-T2= 13 дн.

R(L3)=TKP-T3 = 7дн.

R(L4)=TKP-T4=9дн.

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

 

Построение начинается с критического пути LKP в соответствии с правилами сетевого моделирования по графику событий с учетом изображения длительностей работ tij в масштабе времени по оси абсцисс. По оси ординат длины стрелок выбираются из соображений удобства восприятия топологии сети в целом. Этим объясняется большая длина стрелки работы (6, 8) в сравнении с работой (4, 6), хотя по масштабу времени длительность t4, 6 больше t6, 8.

Длительность всех остальных путей T2, Т3, Т4 меньше, поэтому вводим фиктивные события 5', 8', 7' и фиктивные работы (5', 6), (8', 8), (7', 8) с нулевой продолжительностью.

В результате мы получили полную картину расположения мест свободных резервов времени работ r5, 6C.B =13 дням, r5, 8C.B = 7 дням r7, 8C.B =9 дням. Наиболее напряженными являются работы критического пути L1, которые не имеют резервов и поэтому являются «узкими местами» комплекса работ.

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

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

Венгерский метод решения задачи о назначениях

Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время (см. исследование операций). Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и Эгервари).

Джеймс Манкрес в 1957 году заметил, что алгоритм является (строго) полиномиальным. С этого времени алгоритм известен также как алгоритм Куна — Манкреса или алгоритм Манкреса решения задачи о назначениях. Временная сложность оригинального алгоритма была, однако Эдмондс и Карп (а также Томидзава независимо от них) показали, что его можно модифицировать так, чтобы достичь времени выполнения. Форд и Фалкерсон распространили метод на общие транспортные задачи. В 2006 году было обнаружено, что Якоби нашёл решение задачи о назначениях в XIX веке и опубликовал его в 1890 году на латыни

Предположим, есть три работника: Иван, Пётр и Андрей. Нужно распределить между ними выполнение трёх видов работ (которые мы назовём A, B, C), каждый работник должен выполнять только одну разновидность работ. Как это сделать так, чтобы потратить наименьшую сумму денег на оплату труда рабочих? Сначала необходимо построить матрицу стоимостей работ.

 

 

Венгерский алгоритм, применённый к приведённой выше таблице даст нам требуемое распределение: Иван выполняет работу A, Пётр — работу B, Андрей — работу С

 

Постановка задачи

Дана неотрицательная матрица размера n× n, где элемент в i-й строке и j-ом столбце соответствует стоимости выполнения j-ого вида работ i-м работником. Нужно найти такое соответствие работ работникам, чтобы расходы на оплату труда были наименьшими. Если цель состоит в нахождении назначения с наибольшей стоимостью, то решение сводится к решению только что сформулированной задачи путём замены каждой стоимости C на разность между максимальной стоимостью и C.[2]

Основные идеи

 

Алгоритм основан на двух идеях:

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

если есть решение нулевой стоимости, оно оптимально.

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

Решение задачи коммивояжера методом ветвей и границ

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

Метод ветвей и границ был впервые предложен в 1960 году Ленд и Дойг[1] для решения задач целочисленного программирования.

Общее описание

 

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

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

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

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

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

 

Метод ветвей и границ

⇐ Предыдущая12345Следующая ⇒

Поделиться: