Помеченный ноль вычеркнутый ноль

3. а) Помечаем все строки, в которых нет помеченных нулей;

б)помечаем все столбцы, в которых есть помеченные нули и есть вычеркнутые нули в помеченных строках;

 

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

 

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

 

.

Назначение получено, следовательно, план оптимален.

- минимальный срок, за который институт может выполнить свой проект.

Пример

В конкурсе на занятие пяти вакансий (V1, V2, V3, V4, V5) участвуют семь претендентов (P1, P2, P3, P4, P5, P6, P7). Результаты тестирования каждого претендента, на соответствующие вакансии, даны в виде матрицы - С (тестирование производилось по десятибалльной системе).

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

 

С =

	V1	V2	V3	V4	V5
P1
P2
P3
P4
P5
P6
P7

Рис.22

Математическая модель задачи.

1) Переменные задачи.

Ведем переменные x_ij принимающие два значения:

x_ij=0, если i -й претендент (P_i) не принимается на j -ю вакансию (V_j).

x_ij=1, если i -й претендент (P_i) принимается на вакансию (V_j).

i=1,2,...7; j=1,2,...5.

2) Ограничения на переменные задачи.

Очевидно, что все переменные задачи неотрицательные и целые числа: x_ij 0 и x_ij - целые.

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

, j=1,2,...7,

, i=1,2,...5,

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

3) Целевая функция в задаче о назначениях.

Необходимо выбрать претендентов так, чтобы суммарное число очков, набранное ими было бы максимальным. Суммарное число набранных очков вычисляется по формуле:

;

Z=c₁₁x₁₁+c₁₂x₁₂+...+c₇₅x₇₅=7x₁₁+5x₁₂+...+4x₇₅;

Окончательная математическая модель задачи записывается так:

найти max ;

при ограничениях:

x_ij 0 и x_ij - целые числа, i=1,2,...7; j=1,2,...5;

, j=1,2,...7;

, i=1,2,...5.

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