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

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

В каждом столбце найти минимальный элемент и вычесть его из всех элементов этого столбца. Результаты записать в новую таблицу.

Образовать таблицу затрат С.

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

Задача о назначениях (assignment problem).

Выполним вычисления в EXCEL.

Отметим, что фиктивные клетки следует рассматривать в последнюю очередь.

Потребитель Поставщик					ЗАПАСЫ
4^*
СПРОС

Проверяем условие m + n - 1.

2. Проверка опорного плана на оптимальность.

Проверка на оптимальность осуществляется с помощью потенциалов во вновь составленной таблице.

Потребитель Поставщик					U
	45 -		15 +
	4 +	4	25 _
4^*					-2
V				-1

Условие оптимальности не выполнено! Условие оптимальности нарушено в клетке (3, 1)!

Итак, полученный опорный план не оптимален!

Потребитель Поставщик					U
4^*					-2
V

Получен оптимальный план перевозок!

F_max = 35*1 + 5*2 + 20*3 + 40*3 + 25*4 + 65*2 + 0 =455

х₁₂ = 35

х₁₃ = 5

х₂₁ = 20

х₂₃ = 40

х₃₄ = 65

х₄₃ = 10

Заметим, что третий потребитель ничего не получит!

Пусть имеются n кандидатов и n работ.

Известны затраты с _{i j}, связанные с выполнением

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

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

Построение математической модели:

х_{i j} =1, если i -й кандидат назначен на j- ю работу

х_{i j} =0, в противном случае.

По условию:

Легко видеть, что модель соответствует модели транспортной задачи из § 5, однако специальная форма записи модели позволила разработать более эффективный алгоритм (венгерский метод). Его суть:

4. Проставить у нулей новой матрицы звездочки (*) так, чтобы в каждой строке и каждом столбце было по одному 0^*. Если это возможно, то каждому 0^* сопоставляем x_ij =1, остальным элементам 0 – оптимальное решение получено.

5. Если указанным способом нельзя проставить 0^*, то провести в таблице минимальное число прямых через некоторые 0, так, чтобы все нули оказались вычеркнутыми.

Пример 1

Дата добавления: 2015-06-04