Изменения

[[файл:ТЗ01ЗН01.JPG|thumb|300|[[Математическая модель]] ТЗЗН]]

Пусть имеется '''mn''' поставщиков работ '''(A1,A2,…,AmAn)''' и '''n''' потребителей исполнителей '''(B1,B2,…,Bn)''' однородного продукта. Пусть заданы объёмы поставок '''a_i''' продукта поставщиком '''Ai''' и объёмы потребностей '''b_j''' в продукте у потребителя '''Bj'''. Пусть известны транспортные расходы доходы '''c_ij''' на перевозку единицы продукта от поставщика назначения '''Aii''' -ой работы к потребителю '''Bjj''' -ому исполнителю и необходимо определить план перевозок назначения с минимальной наибольшей суммой транспортных расходовдоходов, тогда классическая [[Транспортная задача с промежуточными пунктами|транспортная при этом каждая работа назначается только одному исполнителю и каждый исполнитель назначается только на одну работу.Тогда задача]] о назначениях (ТЗЗН) формулируется следующим образом:

[[файл:ТЗ01ЗН01.JPG]],

где '''x_ij''' - объём перевозок продукта от поставщика – '''Ai1''' к потребителю если есть назначение '''Bji'''. [[Трёхиндексная транспортная задача|Транспортную задачу]] можно представить в виде таблицы  [[файл:ТЗ03.JPG]]. == Условия разрешимости ==Для разрешимости задачи необходимо выполнение условий баланса: [[файл:ТЗ02.JPG]]-ой работы '''j'''-ому исполнителю, т.е. необходимо, чтобы объём поставок продукта равнялся объёму потребностей в нём'''0''' - если нет назначения.

Необходимо найти начальное опорное решение, например, методом северо-западного угла. Затем транспортная задача Задача о назначениях решается венгерским методом потенциалов. === Метод северо-западного угла ===Метод северо-западного угла для нахождения допустимого решения транспортной задачи состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах.  1.Удовлетворяем потребности потребителей '''(b_j>0)''' за счёт поставщиков '''(a_i>0)''', т.е. назначаем соответствующие перевозки по формулам: '''x_ij=min(ai,bj), ai=ai-x_ij, b_j=b_j-x_ij'''. 2.Процесс заполнения клеток (распределения перевозок) для ТЗ продолжается до тех пор пока у поставщиков имеются нераспределённые остатки и у потребителей имеются неудовлетворённые потребности. === Метод потенциалов === 1.Берём решение '''Xmxn''' и базис '''Zmxn''', найденные, например, с помощью '''алгоритма северо-западного угла'''.  2.Определяем значение целевой функции '''L=ΣΣc_ijx_ij''' и базис опорного решения '''Bo={(i,j)|z_ij=1}'''.

3.Определяем оценку '''Δo''' и элемент '''(i_o,j_o)''' с помощью '''== Пример ЗН ==[[Алгоритм расчёта потенциалов|алгоритма расчёта потенциаловфайл:ЗН10.JPG]]''' и оценок оптимальности.

4.Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxn''' - оптимальное и конец работы[[файл:ЗН11.JPG]]

5.Определяем оценку '''Δx''', элемент '''(i_x,j_x)''' и новое опорное решение '''Xmxn''' с помощью '''=== Подготовительный этап ===[[Алгоритм перераспределения перевозок|алгоритма перераспределения перевозокфайл:ЗН12.JPG]]'''.

6.Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i_x,j_x)U(i_o,j_o)'''.Переходим к пункту 3[[файл:ЗН13.JPG]]

== Пример ТЗ ==[[файл:ТЗ10ЗН14.JPG]]

=== Нахождение допустимого решения Решение венгерским методом ===[[файл:ТЗ11ЗН21.JPG]][[файл:ТЗ12ЗН22.JPG]][[файл:ТЗ13.JPG]][[файл:ТЗ14ЗН23.JPG]]

=== Решение методом потенциалов ===Оптимальное решение равно[[файл:ТЗ21.JPG]][[файл:ТЗ22.JPG]][[файл:ТЗ23ЗН30.JPG]]