Задача о назначениях

мне надо код с++ ( Мака метод)
Пусть необходимо выполнить некоторый проект, который состоит из комплекса работ. Связи между работами описываются с помощью ориентированного графа G:
e1

e2 e5
e11 e6


e3 e4 e10 e7


e12 e9 e8




Факт окончания или начала выполнения работ соответствуют вершинам графа, а сами работы – дугам, ориентация которых соответствует технологии этого процесса. Номера дуг указывают номера работ.
Пусть Tij – время, которое требуется j-му исполнителю для выполнения i-й работы. Совокупность Tij – образует матрицу Т:
1 2 3 4 5 6 7 8 9 10 11 12
29 16 19 28 13 39 11 13 11 15 999 999 | 1
21 19 38 18 18 26 37 30 32 17 999 999 | 2
34 24 23 28 34 26 37 25 25 37 999 999 | 3
26 17 16 31 11 17 34 33 24 11 999 999 | 4
21 35 37 17 38 25 13 31 37 25 999 999 | 5
38 16 39 14 32 29 18 37 28 15 999 999 | 6
36 17 23 19 25 30 20 37 29 39 999 999 | 7
27 15 13 20 27 22 30 20 36 31 999 999 | 8
29 17 18 23 17 21 14 31 34 25 999 999 | 9
28 23 22 25 24 40 32 16 27 24 999 999 | 10
999 999 999 999 999 999 999 999 999 999 0 0 | 11
999 999 999 999 999 999 999 999 999 999 0 0 | 12

Если известен исполнитель, назначенный на каждую работу, то будет известно и время выполнения каждой работы. Тогда срок выполнения всего проекта можно найти как длину критического пути в графе методом PERT.
В задаче требуется так распределить исполнителей, чтобы длина критического пути была не более директивного срока D.
Алгоритм решения задачи.
1. Решаем задачу о назначениях для матрицы Т: находим минимум функции
(1)
при ограничениях
(2)

где Zij {0; 1} – распределение операций по исполнителям: Zij = 1, если i-я операция поручена j-му исполнителю, Zij = 0 в противном случае.

2. Определяем полученную длительность выполнения каждой i-й работы:

3. При найденных i находим критический путь PERT на графе от начала работ до конца проекта. Тогда время выполнения проекта будет равно


4. Если F  D, то задача решена. Иначе попытаемся за счёт перераспределения работ уменьшить длину критического пути. Для этого умножим веса Tij всех дуг, участвующих в критическом пути, на некоторый коэффициент  > 1. В результате некоторые строки матрицы T умножатся на . Тем самым увеличатся значимости этих работ.
5. Возвращаемся к пункту 1 и решаем новую задачу о назначениях. Если длина критического пути (со старой матрицей) удовлетворяет условию F  D – задача решена. Иначе переходим к пункту 6.
6. Увеличим значение  и повторим решение задачи о назначениях (вернёмся к пункту 1).
7. Если после нескольких попыток критический путь не улучшится – значит, задача не имеет решения при данных исполнителях. В этом случае необходимо либо привлечь более квалифицированных исполнителей, либо поменять перечень работ, сделав их более выполнимыми.
Пример. Имеем модель процесса реализации проекта в виде графа G c матрицей длительностей выполнения работ T. Директивный срок окончания работ D = 88.


1. Решаем задачу о назначениях (1) – (2). Получаем следующее решение:
Операции 1 2 3 4 5 6 7 8 9 10 11 12
Исполнители 9 1 6 10 7 4 2 3 5 8 11 12
Длительности 11 21 26 11 13 14 17 13 17 16 0 0

2. Находим критический путь – дуги 11, 2, 3, 4, 7, 10. Его длительность составляет 91 единиц.

3. Умножаем строки 11, 2, 3, 4, 7, 10 матрицы на  = 2. Повторяем решение задачи о назначениях с новой матрицей.
Результат

Операции 1 2 3 4 5 6 7 8 9 10 11 12
Исполнители 9 10 6 5 1 4 2 3 7 8 11 12
Длительности 11 17 26 11 21 14 17 13 14 16 0 0

Длительность полученного критического пути (работы 11, 2, 3, 4, 10, 7) составляет 87 единиц, т.е. условие F  D выполнено, задача решена.

0