А. Кофман и Р. Фор. Займемся исследованием операций (стр. 13 )

	1	2	3	4	5
1	11	5	0	0	4,5
2	10	7	2	0	3,5
3	7,5	7,5	7,5	7,5	0
4	0	0	7	14	7,5
5	7	0	0	7	10,5

Таблица 6.12

	1	2	3	4	5
a	0	0	1	0	0
b	0	0	0	1	0
c	0	0	0	0	1
d	1	0	0	0	0
e	0	1	0	0	0

Решение может быть, наконец, представлено, как и в таблице 6.2, в виде единиц и нулей, причем единицы будут занимать использованные клетки (табл. 6.12).

Таким образом, решение, которое приводит к минимальному суммарному времени ожидания в 33,5 часа, оказывается следующим:

1-я бригада живет в Мехико. Рейсы d и 1. Перерыв 4,5 часа.

2-я бригада живет в Акапулько. Рейсы 2 и е. Перерыв 9,5 часа.

3-я бригада живет в Акапулько. Рейсы 3 и а. Перерыв 9 часов.

4-я бригада живет в Мехико. Рейсы b и 4. Перерыв 5 часов.

5-я бригада живет в Акапулько. Рейсы 5 и с. Перерыв 5,5 часа.

Аналогичный расчет позволяет определить максимальное время простоя, которое составляет 83,5 часа. Между наилучшим и наихудшим решениями имеется разница в 50 часов и существует еще 118 промежуточных решений (не обязательно отличающихся друг от друга по существу; так, например, решения 2а, b1, 5с, d4, е3 и 2а, b1, 5с, d3, e4 эквивалентны друг другу). Кто теперь осмелится утверждать, что для нахождения оптимального решения достаточно интуиции и общих рассуждений, особенно если в таблице было бы еще несколько строк и столбцов?

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

Теорема Кёнинга.

В 1916 г. венгерский математик Д. Кёнинг среди других утверждений доказал следующую фундаментальную теорему, благодаря которой оказалось возможным построить алгорифм, позволяющий решать задачи о назначениях[31].

Различные доказательства этой теоремы, как правило, являются громоздкими и довольно тонкими. Хотя алгорифм Форда – Фалкерсона исторически появился значительно позже теоремы Кёнига, использовать[32]теорему Форда – Фалкерсона для доказательства теоремы Кёнига очень удобно[33].

Пусть нам дана m×n – матрица M, некоторые элементы которой являются нулями, а другие произвольны. Обозначим через (L) совокупность всех m строк L1, L2…, Lm матрицы, а через (С) – совокупность всех её n столбцов C1, C2,…, Cn.

Множество рядов матрицы (т. е. её строк и столбцов) называется опорным, если удаление этих рядов из матрицы приведет к исчезновению из неё всех нулей. Множество всех строк матрицы, равно как множество всех её столбцов, являются, очевидно, опорными, но не минимальными опорными. Если минимальное опорное множество состоит из p строк Li1,…, Lip и q столбцов Cj1,…, Cjq, то мы, естественно, имеем p +q ≤ min(m, n), поскольку минимальное опорное множество должно содержать не более чем (m, n) рядов. Рассмотрим в качестве примера матрицу 1.

Матрица 1

Как L1,…, L4 так и C1,…, C5 являются опорными множествами, причем меньшее из них состоит из четырех рядов. Можно, однако, найти опорное множество, состоящее из еще меньшего числа рядов, именно C1, L3, L4.

Минимальное число рядов в опорном множестве матрицы M назовем индексом рассредоточения этой матрицы и обозначим через D(M).

Довольно легко показать, что для матрицы 1 оказывается D(M) = 3. Таким образом, мы имеем

D(M) ≤ min(m, n).

Будем говорить, что совокупность k нулей матрицы образует связку k строк и k столбцов, если эти k нулей стоят на пересечении k различных строк и k различных столбцов. Так, обведенные рамкой нули в матрице 1 образуют связку

L2C1- L3C2- L4C5.

Каждая строка и каждый столбец встречаются в этом выражении ровно по одному разу.

Максимальной связкой называется связка, содержащая наибольшее число нулей. Это число называется индексом квадратности матрицы М и обозначается через Q(M).

Теорема Кёнига может быть сформулирована так:

D (M) = Q (M).

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

Для матрицы 1 мы имеем D (M) = Q (M)=3 .

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

а) Источник O связан при помощи дуг ОСj с каждой из n точек С1, …,Сn (если n≥m) или при помощи дуг OLj c каждой из точек L1, …Lm (если m>n); пропускная способность каждой из этих дуг равна еденице.

б) Сток Z связан дугами LiZ с m точками L1,…,Lm (если m≤n) или с n точками C1,…,Cn (если n<m), и пропускная способность каждой из этих дуг также равна 1.

в) Каждому нулю LiCj матрицы ставится в соответствие дуга CjLi (если m≤n) или соответственно дуга LiCj (если n<m); пропускную способность каждой из этих дуг будем считать бесконечной.

Пример. На рис. 6.1. изображена транспортная сеть, соответствующая матрице 1.

Нахождение максимальной связки в матрице равносильно определению максимального потока в соответствующей ей сети:

Q(M) = значению максимального потока.

В самом деле, нуль LiCj матрицы представлен дугой CjLi. Если единичный поток пройдет по этой дуге, то мы получим также единичный поток на дугах ОСj и LiZ, которые таким образом обе окажутся насыщенными. Иными словами, каждая строка и каждый столбец могут быть затронуты не более одного раза. Отсюда становится сразу же ясным, что если m≤n, то полное значение потока, могущего войти в Z, не превосходит m, причем точка Z является разрезом сети. [34]

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

Таким образом:

D(M) =минимальной пропускной способности разреза.

По теореме Форда-Фалкерсона,

минимальный разрез = максимальному потоку,

т. е.

Q(M) =D(M).

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

Пусть дано опорное множество, составленное из множества (L+) строк и множества (С+) столбцов Например, для матрицы им будет L1, L2, L3 и C5

(L+)=(L1, L2, L3); (C+) = (C5).

Обозначим теперь соответственно через (L-) и (C-) множества строк и столбцов, не принадлежащих рассматриваемому опорному множеству.

После удаления рядов из (L+) и (C+) полученная матрица, составленная из строк (L-) и столбцов (C -), не будет содержать ни одного нуля.

В соответствующей сети ни одна из дуг не соединяет какой-либо точки из (C-) с какой-либо точкой из (L-).

В нашем примере

(L-) = (L4),

(C-) = (C1, C2, C3, C4).

Здесь L4 действительно не связано ни с одной из точек C1, C2, C3, C4.

Пусть ε есть множество точек сети, состоящее из:

1.  точки Z,

2.  всех точек из (L-),

3.  всех точек из (С+).

В нашем примере

ε = (Z, L4, C5).

Это множество точек определяет разрез С (ε), все входящие дуги которого входят в ε и выходят из точки, внешней по отношению к ε. Итак:

а) Только дуги, выходящие из точки, внешней по отношению к ε, и входящие в Z, являются дугами, началом которых является какая-либо точка из (L+). Для любой точки Li из (L+) существует – и притом только одна - дуга LiZ с пропускной способностью 1.

Если (L+) насчитывает p точек (причем p является числом строк опорного множества; в рассматриваемом примере p=3), то суммарная пропускная способность этих дуг равна р.

б) Точки из (L-) не связаны ни с какой точкой из (C-). Таким образом, нет дуг, входящих в ε и заканчивающихся в (L-).

В нашем примере никакая входящая дуга не кончается в L4.

в) Каждая точка из (C+) связана с нулевой точкой некоторой дугой с пропускной способностью 1. Если в (C+) имеется q точек (q есть число столбцов опорного множества; здесь q=1), то общая пропускная способность дуг, входящих в ε в точках (C+), равна q.

Таким образом, пропускная способность разреза равна p+q (здесь 3+1=4).

2. Покажем теперь, что каждому разрезу конечной пропускной способности можно поставить в соответствие некоторое опорное множество.

Пусть нам дан некоторый разрез, который содержит Z и не содержит точки O. Он содержит некоторое число точек из L, множество которых мы обозначим через (L-), и некоторое число точек C, множество которых обозначим через (С+).

Если этот разрез обладает конечной пропускной способностью, то никакая дуга не соединяет точки из (L-) с точками из множества (C-), состоящего из точек, не вошедших в (C+). В самом деле, если бы это было не так, то нашлась хотя бы одна входящая дуга с бесконечной пропускной способностью; в этом случае и весь разрез имел бы бесконечную пропускную способность, что противоречит предположенному.

Итак, подматрица, состоящая из строк, соответствующих точкам из (L-), и столбцов, соответствующих точкам из (C-), полученная из M после удаления всех остальных строк и столбцов, не содержит ни одного нуля. Таким образом, все нули из M оказываются в строках и столбцах из (L+) и (C+), совокупность которых составляет опорное множество.

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

Пусть теперь C(ε’) есть минимальный разрез. Этому разрезу соответствует минимальное опорное множество, число рядов которого D(M) равно пропускной способности разреза. Согласно теореме Форда-Фалкерсона, некоторому минимальному разрезу соответствует максимальный поток. Вместе с тем максимальный поток равен D(M). Таким образом, значением максимального потока является максимальное число нулей разреза, т. е. Q(M). Следовательно,

D (M) =Q (M).

Теорема Кёнига доказана.

Применение теоремы Кёнига к решению задачи о назначениях.

В том случае, когда задача о назначениях не связана с издержками, она сводится к определению максимальной связки. Пусть, например, m шоферов должны вести n машин, причем каждый из них должен быть прикреплен к одной машине, которой он умеет управлять. Обозначим через X1, X2,…,Xn имена шоферов, а через Y1, Y2,…, Ym – марки машин и соединим на графе рис. 6.3 Xi c Yj, если шофер Xi может работать на машине Yj.

Поставим в соответствие данному графу матрицу M; в этой матрице 2 любой элемент Mij=1, если в графе существует дуга XiXj.

Максимальным назначением будет такая связь Xi с соответствующими Yj, при которой на каждую машину будет назначен ровно один шофер и число занятых машин будет максимально.

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

1.выбрать строку, состоящую из минимального числа единиц, или одну из таких строк и обвести одну из этих единиц квадратиком;

Матрица 2

2.  прочеркнуть строку и столбец, пересекающиеся по обведенной единице;

3.  повторять операции 1. и 2. для полученных матриц до тех пор, пока все строки и все столбцы, содержащие единицы, не будут прочеркнуты.

Мы получим здесь, например (ибо существуют и другие), связку X1Y1, X2Y3, X3Y2, X4Y4, X5Y5; эта максимальная связка позволяет назначить n шоферов. Так оказывается не всегда; в случае, когда это имеет место, говорят, что связка является насыщающей.

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

Возьмём в качестве отправной точки матрицу затрат C, каждый элемент cij которой представляет собой (см. матрицу 3) затраты от назначения Xi на Yj.

1.  Покажем, что задача не изменится, если вычесть произвольную постоянную ui из всех затрат, находящихся в i-строке, или постоянную υj из всех затрат j-го столбца.

Пример. Возьмем в качестве матрицы C матрицу 3.

Матрица 3

Положим, например,

и

Мы получим тогда матрицу 4 или , элементы которой равны

Матрица 4

Рассмотрим две произвольно выбранные связки

γ1=(X1Y1, X2Y2, X3Y3, X4Y4, X5Y5)

γ2=(X1Y5, X2Y4, X3Y3, X4Y2, X5Y1).

Соответствующие общие затраты равны

C (γ1) = 3+6+3+7+9=28,

C (γ2) = 1+3+3+3+5=15,

и мы имеем

∆ = C (γ1) - C (γ2) = 28 – 15 = 13 = ∆.

Убедимся в том, что при переходе к матрице 4 эта разность ∆ не изменится:

и

откуда

Вообще, поскольку речь идет о связках, мы имеем

и

откуда

2.  Заметим далее, что если

каковы бы ни были cij, то для любой связки γ мы будем иметь

независимо от конкретного способа вычисления значений ui и ,

Из сказанного следует:

а) если существуют такие ui и , что

для всех i и j и

б) если существует связка γ, для которой

,

то минимально, а

максимально.

Итак, мы видим, что если для некоторых значений ui и граф, образованный дугами, для которых

[или же ]

до того, как связка γ окажется насыщенной, т. е. если каждая строка и каждый столбец матрицы будут затронуты, то мы будем иметь

а так как каждая строка и каждый столбец затрагиваются один и только один раз, должно быть

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

3.  Рассмотрим пример, связанный с матрицей 3. Вспомогательный граф, составленный из дуг, для которых (матрица 4), изображен на рис. 6.4.

Этому графу соответствует матрица 5, в которой записаны только нули матрицы 4.

Матрица 5.

Найдем максимальную связку для этой матрицы 5. Мы можем, например, взять связку

которая не является насыщенной, поскольку затронутыми оказываются только четыре ряда матрицы. Чтобы сделать ее насыщенной, нужно затронуть строку 2 и столбец 1. При этом мы получим

C (γ1) = 1+4+1+2+1=9,

откуда

Наша задача состоит теперь в том, чтобы найти новые значения ui и , позволяющие увеличить S, и в результате найти такую связку γ2, что

Найдем опорное множество вспомогательного графа, изображенного на рис. 6.4. На основании теоремы Кёнига это опорное множество состоит из четырех рядов, потому что связка состоит из четырех пар XiYj. Тем же методом, которым мы пользовались при рассмотрении задачи без затрат, мы находим ряды

X3, X4, X5 и Y5.

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

Пусть k – наименьший элемент этой последней матрицы (здесь число k положительно, потому что матрица не содержит ни одного нуля. Положим

если строка i не входит в опорное множество, и

если столбец j в опорное множество входит.

Мы получаем следующие значения:

Они дают нам новую матрицу , в которой

Мы видим, что в матрице мы вычли k=1 из элементов и прибавили k=1 к элементам, расположенным на пересечении опорных строк и столбцов (матрица 6).

Матрица 6.