При рассмотрении транспортных задач можно было заметить, что ТЗ иногда оказывается вырожденной. Это происходит, если при некотором допустимом распределении поставка в любую клетку, кроме последней, удовлетворяет спрос всего столбца, используя при этом все ресурсы соответствующей строки.
В рассматриваемой задаче каждый ресурс назначается только на одну работу, а каждая работа требует только одного ресурса. Следовательно, задача о назначении есть полностью вырожденная форма транспортной задачи. В этом случае методы решения транспортных задач оказываются малоэффективными: при любом назначении всегда автоматически совпадают поставки по строке со спросом по столбцу и, поэтому, вместо 
получаем 
ненулевых значений 
и, в связи с этим, необходимо заполнить матрицу 
величинами 
и совершать «фиктивные перевозки».
Специальный метод решения задачи о назначении основан на следующих теоремах.
Теорема 1. Если 
минимизирует 
по всем таким, что 
минимизирует также функционал
Доказательство:
т. е. решение не изменится, если прибавить к любому столбцу или строке матрицы 
некоторую константу или вычесть ее из них.
Теорема 2. Если все 
и можно отыскать набор 
, такой, что 
, то это решение оптимально, т. е. 
.
Доказательство. (самостоятельно)
Рассматриваемый метод решения сводится к прибавлению констант к строкам и столбцам и вычитанию их из строк и столбцов до тех пор, пока достаточное число величин 
не обращается в нуль, что дает искомое решение.
В 1912 году венгерский математик Кёниг (König D.) среди других утверждений доказал теорему, благодаря которой оказалось возможным построить алгоритм решения задач о назначении.
Пусть дана 
матрица 
, некоторые элементы которой являются нулями, а другие произвольны. Обозначим через 
- совокупность всех 
строк, а через 
- совокупность всех столбцов. Множество рядов матрицы (т. е. множество ее строк и столбцов) называется опорным, если удаление этих рядов приводит к исчезновению из нее всех нулей. Если минимальное опорное множество состоит из 
строк и 
столбцов, то можно утверждать, что 
.
Минимальное число рядов в опорном множестве матрицы назовем индексом рассредоточения –
.
В качестве примера рассмотрим матрицу .
|
|
|
|
|
| |
| 0 | * | ||||
| * | |||||
| 0 | 0 | ||||
| ||||||
* |
М=
Как 
, так и 
являются опорными множествами, причем меньше из них состоит из четырех рядов 
. Можно найти опорное множество, состоящее из еще меньшего числа рядов
. Для матрицы оказывается 
и 
.
Совокупность 
нулей матрицы образует связку строк и столбцов, если эти нулей стоят на пересечении различных строк и различных столбцов. Так, обведенные рамкой нули образуют связку
.
Каждая строка и каждый столбец встречаются в этом выражении ровно по одному разу.
Максимальной связкой называют ту связку, которая содержит наибольшее число нулей. Это число называют индексом квадратности матрицы - 
.
Теорема Кёнига формулируется следующим образом:
,
т. е. минимальное число опорного множества равно максимальному числу нулей связки, или индекс рассредоточения матрицы равен индексу ее квадратности.
Для поиска максимальной связки можно предложить следующий алгоритм:
 |
1. В строке или столбце, который содержит наименьшее число нулей, обведем один из нулей, а затем вычеркнем все нули, которые находятся в той же строке или в том же столбце, что и обведенный квадратной рамкой нуль.
2. Повторить пункт 1, пока существуют непомеченные нули.
Алгоритм поиска минимального опорного множества:
 |
1. пометить звездочкой (*) все строки, которые не содержат ни одного обведенного квадратной рамкой нуля;
2. пометить звездочкой столбец, содержащий перечеркнутый нуль, хотя бы в одной из помеченных строк;
3. пометить звездочкой строку, содержащую обведенный нуль, хотя бы в одном из помеченных столбцов;
4. повторять пункты 2 и 3, пока не останется строк или столбцов, которые ещё можно пометить;
5. перечеркнуть каждую непомеченную строку и каждый помеченный столбец.
Алгоритм решения задачи о назначении.
1. В каждом столбце таблицы выберем наименьший элемент и вычтем его из всех элементов этого столбца.
.
Описанный прием позволяет получить хотя бы один нуль в каждом столбце.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Основные порталы (построено редакторами)