Оптимальное распределение рабочих по захваткам

Пусть имеется n видов работ и несколько специализированных бригад рабочих. Необходимо распределить рабочих между отдельными видами работ таким путем, чтобы в строительный поток включить максимальное количество рабочих. Такая задача близка к транспортной. В научной литературе она известна как задача о максимальном потоке в матричной постановке или задача назначения (выбора). Рассмотрим постановку задачи в общем виде. Пусть заданы количества единиц ресурса а: ,,, направляемые в пункты назначения, в которых потребности b: , , в этом ресурсе. Отличительной особенностью этой задачи является закрепление каждого пункта отправления за некоторыми пунктами назначения. Итак, имеется матрица , в которой

, если нельзя перевозить ресурс из i-го пункт отправления в j-пункт назначения, 0, если перевозка возможна.

Задача составляется в составлении плана перевозок максимального количества ресурса.

Такой план определяется числами (i=1, m, j=1, n);.

Если =0, то =0, т.е. нельзя перевозить ресурс из i-го пункта отправления в j-ый пункт назначения.

При этом должны соблюдаться условия:

1 , i=1, m, то есть из i-го пункта отправления вывозится ресурс не более чем .

2 , j=1, n, то есть в j-ый пункт назначения можно ввести не больше потребности -го ресурса.

При этом количество перевозимого ресурса

Ф=max.

Исходные данные:

На строительном объекте имеется 4 вида работ и 4 групп рабочих. Рабочие каждой группы выполняют одни и те же работы. Необходимо, чтобы работы выполняло максимальное количество рабочих. Условия задачи приведены в таблице 1.2.1, в столбцах которой указано требуемое количество рабочих для выполнения соответствующей работы, а строки отдельные виды рабочих. В клетках таблицы приведены нули, если рабочий i-ой группы может выполнять j-ю работу, и единицы, если рабочие i-ой группы не могут выполнять j-ю работу.

Таблица 1.2.1