МП – Общие принципы построения математической модели, страница 3

Ui – потенциал строки, Vj – потенциал столбца. Ui = Cij – Vj,  Vj = Cij – Ui.  Примечание – Число загруженных клеток = m + n – 1,  где

m – число строк, n – число столбцов. 2 – Определяем характеристику незагруженных клеток: Eij = Cij – (Ui + Vj),  Eij – для заполненного = 0. Если имеются отрицательные характеристики, то план не оптимален, и его необходимо улучшить. 3 – К-тая итерация. Выбираем среди характеристик min и по этой клетке строим цепь распределений поставок по следующим правилам: 3.1 – Вершина цепи, кроме исходных, находится в загруженных клетках. Любой отрезок, принадлежащий либо строке, либо столбцу, все углы прямые, количество вершин – четное, отрезки цепи могут пересекаться – тогда эта вершина не считается, цепь является замкнутым многоугольником, отрезки цепи могут пересекать любые клетки. 3.2 – Не загруженную вершину помечаем знаком. Чередуя по часовой стрелке пишем плюсы и минусы. 3.3 – Выбираем среди помеченных минусом min поставку и на эту величину уменьшаем все помеченные минусом и увеличиваем все помеченные плюсом.

Вопрос 13

МП – Матричный расчет параметров СПУ

1 – С сетевого графика заносим в соответствующую ячейку Tij. 2 – Для того чтобы вычислить необходимые параметры вычисляем вспомогательный столбец ‘l’. Для исходного события ‘l’ = 0. Для определения ‘l’ в строке i = j отыскиваем Tij и по этой строке складываем соотв. ‘l’. Если таких Tij несколько, то берем max. 3 – Заполняем строки ‘мю’ начиная с последнего столбца, причем с числителя. Для завершающего события ‘мю’ = 0. Для всех остальных ‘мю’ = как сумма Tij в строке i = j и соотв. ‘мю’ по этому столбцу где Tij. Если таких Tij несколько выбираем максимальную сумму. 4 – Берем max ‘мю’ и (‘l’) и вычитаем из этого значения числитель, и получаем знаменатель. Берем по строке и столбцу i = j и получаем резервное время как разность ‘l’ и ‘мю’. резерв равный 0 лежит на критическом пути

Вопрос 15

МП – Задача о назначении (Венгерский метод)

Алгоритм: состоит  из предварительного этапа и не более чем n-2 итераций, каждая итерация связана с эквивалентным преобразованием матрицы и выбора максимального числе независимых нулей. Каждая итерация увеличивает число независимых нулей на единицу. Если кол-во независимых нулей n то задача решена. Fmax определяется по позиции независимых нулей не в последней таблице, а в исходной. 1 ЭТАП: 1 – в каждом столбце выбираем максимальный элемент и из него вычитаем все элементы данного столбца, после чего получаем матрицу, в каждом столбце которой есть хотя бы 1 ноль. 2 – в каждой строке выбираем минимальный элемент и его вычитаем из каждого элемента строки. В результате получаем матрицу, в каждой строке и столбце которой есть хотя бы 1 ноль. 3 – берем первый столбец и отыскиваем нуль, и ставим около него знак *, после переходим во второй столбец. Если во втором столбце есть ноль, то если этот ноль лежит в строке, где нет 0*, то отмечаем этот ноль *. В противном случае переходим к следующему столбцу. По построению, все 0* являются независимыми. 2 ЭТАП (K+1 итерация): Допустим, что 5 итерация закончилась, в результате которой мы получили матрицу. Если в ней n=0* то задача решена, else переходим к К+1 итерации. Каждая итерация начинается первым этапом и заканчивается вторым этапом. Между ними может быть много третьих этапов. Перед началом итерации плюсом помечаем столбцы, имеющие 0*. 1 Этап: Рассматриваем невыделенные столбцы матрицы, если среди них нет нулевых элементов, переходим к третьему этапу. Если нули есть, то возможно 2 случая: 1 – строка содержащая 0 содержит 0*. 0 отмечаем ‘, выделяем строку, затем возвращаемся по строке уничтожая знак + над столбцом, обведя его кружком, на пересечение которого находиться 0*, затем, просматриваем этот столбец отыскивая 0 и помечаем его штрихом, выделяем строку и т.д. 2 – Строка содержащая 0 не содержит 0*., то переходим к этапу 3. Процесс может закончиться одним из нескольких исходов.: 1 – все нули матрицы выделены, т.е. находятся в выделенных строках и столбцах, то переходим к третьему этапу. 2 – иметься 0 в строке где нет 0*, то переходим к этапу 2, но после отмечаем ‘. 2 Этап: Строим цепочку из элементов матрицы. Начиная и заканчивая 0’. Штрихи заменяем *, а * уничтожаем. В результате итерация на 0* становиться больше, и конец итерации. 3 Этап: Переходим после первого этапа, если все 0 выделены. Тогда, среди невыделенных элементов матрицы выбираем минимальный > 0. H > 0. H – вычитаем из всех элементов в невыделенных строках, и прибавляем к элементам в выделенных столбцах.   Постановка – что дано, и что найти.