II этап. Выбор назначений.

По приведенной матрице строим таблицу , в которой допустимыми являются клетки, которые соответствуют нулевым значениям матрицы . На построенной таблице решаем задачу о нахождении ММНДК(мак. мн-во незав. допустим. клеток ). Если количество клеток в ММНДК совпадает с , то оптимальное значение построено, в противном случае, переходим к этапу III.

III этап. Дополнительное приведение матрицы.

Пусть - мн-во помеченных на последнем шаге этапа II строк таблицы допустимых клеток, а - мн-во не помеченных столбцов. Среди элементов матрицы , стоящих на пересечении помеченных строк и не помеченных столбцов находим элемент . Элемент вычитаем из помеченных строк и добавляем к помеченным столбцам. Получим новую приведенную матрицу . Возвращаемся в этап II.

Задача о назначении на узкие места.

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

Математическая модель задачи выглядит так: Рассмотрим функционал , заданный на мн-ве подстановок следующим образом

- подстановок.

Рассмотрим алгоритм решения поставленной задачи:

• Пусть - некоторое назначение на работу;

• По матрице эффективности строится таблица , в которой клетки с номерами считаются допустимыми, если .

На построенной таблице решается задача нахождения ММНДК(мак. мн-во нез. допуст. клеток); если количество независимых допустимых клеток (НДК) равно , то получено новое назначение , так что , в противном случае, оптимальное решение получено на предыдущем шаге. Процесс повторяется до тех пор, пока не будет установлено оптимальное решение.

15. Основные этапы и понятия сетевого планирования и управления(спу)

Этапы СПУ:1) структурное планирование;

2) календарное планирование;

3) операционное планирование.

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

№ операции	Предыд. операция	Послед. операция	Длит-ность операции
1	­---	4, 5, 6	3
2	---	5, 6	6
3	---	7, 9	4
4	1	8	5
5	1, 2	7, 9	1
6	1, 2	8	9
7	3, 5	8	6
8	4, 6, 7	---	8
9	3, 5	---	5

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

Существует 2 типа СГ:

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

Работы обозн. вершинами, а события –дугами.

Правила построения сетевых графиков. Параметры СГ. Календарный план

Правила построения СГ:

1. Каждой работе соотв. одна и только одна дуга.

2. Ни одна пара работ не должна опред-ся общенач. и конеч. событиями. Чтобы этого избежать необх. ввести в рассмотрение фиктивное событие и фиктивную дугу.

3. Мн-во работ, вход. в событие, должно непосредств. предшествовать работам, исход. из данного события.

4. У каждого СГ должно быть одно начало и один конец.

5. Вершины СГ должны быть правильно пронумерованы (используя алг. Форда-Фалькерсона).

Рез-том календарного планирования явл. календарный план, кот. определ. моменты наступления событий. Поскольку каждая работа хар-ся нач. событием i и кон. событием j, тогда обозн. работы (i, j). Длительность соотв. работ обозначим ч-з .

Опр. Ранним сроком свершения события j наз. самый ранний момент времени, в кот. завершаются все работы, предшествующие этому событию.

Ранний срок будем обозн. .

Опр. Ранний срок свершения конечного события наз. критическим сроком и обозн. . -минимальное время выполнения проекта.

Опр. Поздним сроком свершения события i наз. самый поздний момент времени, при кот. не нарушается критическое время. Поздний срок обозн. .

Опр. Резервом события i наз. величина .

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

Пусть максимальные длины, проход. ч-з критич. события, наз. критич. путем, а работы, лежащие на критич. пути, наз. критич. работами.

Расчет сроков свершения событий расчитыв. на СГ, при этом событие обозн. след. образом:

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

; ; ; ;

-полный резерв

-свободный резерв

Полный резерв времени указывает максимальное кол-во времени. Может быть отложена работа без нарушения критич. времени. А свободный резерв означ. насколько можно отложить или растянуть работу, не нарушая критич. времени и ранних сроков наступления последних работ.

Замечание. Критический путь может быть не единственным.

16. Алгоритм нахождения критическом пути. Линейные диаграммы проекта

Сетевой график (СГ) дает наглядное представление о порядке выполнения работ, однако по нему трудно судить какие работы выполняются одновременно в опред. промежуток времени. С этой целью строится лин. диаграмма проекта (график Ганта). Задается горизонтальная ось времени с заданным на ней масштабом. Каждой работе соотв. отрезок равный длит-сти работы и параллельный оси Ох. Отрезки располагаются один над другим в порядке возрастания индекса i. Если индекс i совпадает, то в порядке возрастания индекса j. Фиктивные работы обозн. точками.

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

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

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

Рассмотрим все работы, кот. начинаются с события n-1 (с учетом сдвига).Через крайний левый конец всех работ, начинающихся с события n-1, проводим вертикальную черту, кот. соотв. сроку . К этой линии сдвигаем все работы, кот. заканчив. событием n-1 и т.д.

Работы, кот. не подвергались сдвигу –критич. работы.