Постановка задачи. Некоторые свойства

Пусть имеются n претендентов (каждому из них отвечает индекс ) на n мест работы (каждому из них отвечает индекс ). При этом известна стоимость  затрат, связанных с назначением i -го претендента на j -е место. Требуется распределить претендентов по рабочим местам так, чтобы каждый претендент занял одно место, каждое место было занято одним претендентом и так, чтобы связанные с этим распределением суммарные затраты были минимальными.

Для получения математической записи задачи о назначениях можно ввести  

если i-й претендент назначен на j-e место,

переменных следующим образом:

иначе

в противном случае.

Теперь задача принимает следующий вид:

Замечание. Если последние ограничения  заменить условиями вида  то полученная задача является частным случаем транспортной задачи, у которой, как известно, оптимальное решение всегда существует. Таким образом, задачу о назначениях можно решать методом потенциалов, причем в соответствии со спецификой этого метода можно утверждать, что решением является - мерный вектор, или матрица порядка n × n, элементы которой равны 0 или 1. Это означает, что полученный ответ будет также являться ответом в исходной задаче о назначениях. Однако начальная базисная точка, полученная, например, по методу северо-западного угла, содержит не

m+n-1=2n-1, а всего лишь n ненулевых компонент равных 1, cледовательно, при  этот план становится вырожденным. Как известно, это обстоятельство существенно усложняет вычислительную процедуру решения транспортной задачи. По этой причине для решения задачи о назначениях существуют специальные методы. Рассмотрим один из них, который носит название венгерский метод.

В дальнейшем нам потребуется следующее определение.

Определение. Любые k элементов () матрицы C=  порядка n × n  называются независимыми, если всякие два из них располагаются в разных строках и в разных столбцах.

Теперь можно переформулировать задачу о назначениях следующим образом: среди   элементов данной матрицы C найти n независимых элементов , , таких, что сумма минимальна.

Для обоснования венгерского метода потребуются следующие понятия и утверждения.

Матрицей назначений порядка n × n  называется матрица, в которой имеются n независимых единиц и  нулей. Иными словами, это матрица, у которой в каждой строке и в каждом столбце имеется ровно одна единица, а остальные элементы являются нулями.

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

Замечание. Все задачи о назначениях размера n × n   имеют одно

и то же допустимое множество и отличаются друг от друга только коэффициентами целевой функции, т.е. матрицей   C= .

Теорема 1. Если элементы матриц C и D порядка n × n  связаны равенствами

, то задачи о назначениях с данными матрицами C и D эквивалентны, т.е. множества их решений (оптимальных точек) совпадают.

  Доказательство. Во-первых, как отмечалось выше, допустимые множества

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

из которой следует, что значения двух целевых функций с матрицами C и D

отличаются на постоянную F. Это означает, что минимумы этих функций достигаются в одних и тех же точках (на одних и тех же матрицах назначений).

Теорема доказана.

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

Следствие. Всегда можно считать, что все элементы матрицы C неотрицательны, т.е.

Действительно, этого можно добиться применением эквивалентных преобразований.

Теорема 2. Пусть все элементы матрицы C неотрицательны, т.е.  Если в ней имеются n независимых нулевых элементов то их сумма является минимальной.

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

 

Венгерский метод

 

Алгоритм венгерского метода включает в себя 4 этапа.

Приведение матрицы.

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

2. Получение новых нулей при .

3. Отыскание n независимых нулей  при .

Рассмотрим каждый этап подробнее.

Этап 1.

Матрица C называется приведенной, если все ее элементы неотрицательны и, кроме того, в каждой строке и в каждом столбце имеются нулевые элементы. Таким образом, приведенная матрица C удовлетворяет двум условиям:

1.

2.

Для приведения матрицы C с элементами   нужно воспользоваться эквивалентными преобразованиями. При этом вначале осуществляется приведение матрицы по строкам, т.е. ищется наименьший элемент  в каждой строке и осуществляется переход к матрице  с элементами . Если матрица  оказывается неприведенной по столбцам, то ищется наименьший элемент  в каждом столбце и осуществляется переход к матрице , элементы которой вычисляются следующим образом: . Матрица  по построению является приведенной.

Пример 1. Пусть

2	1	2	1	0
1	3	5	7	4
2	7	8	6	9
1	5	4	7	8
1	3	4	9	10

 

 

С=

Легко проверить, что

2	0	0	0	0
0	1	2	5	3
0	4	4	3	7
0	3	1	5	7
0	1	1	7	9

 

2	1	2	1	0
0	2	4	6	3
0	5	6	4	7
0	4	3	6	7
0	2	3	8	9

 

=                                 , A =,

причем матрица  является приведенной.

Этап 2.

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

Теорема 3. Максимальное число независимых нулей равно минимальному суммарному числу горизонтальных и вертикальных линий (строк и столбцов), которыми можно зачеркнуть все нулевые элементы приведенной матрицы.

Пример 2. Пусть имеется приведенная матрица из примера 1.

2	0	0	0	0
0	1	2	5	3
0	4	4	3	7
0	3	1	5	7
0	1	1	7	9

 

 

=

                                     

 

 

Все ее нули содержат 1-я горизонталь и 1-я вертикаль, следовательно, здесь k =2 < 5. При решении задачи о назначениях будем проводить указанные линии, в результате чего некоторые элементы окажутся зачеркнутыми, другие - зачеркнутыми дважды и остальные - незачеркнутыми.

Этап 3.

 Обозначим через  элемент приведенной матрицы , зачеркнутый r раз (r =0, 1, 2) на 2-м этапе, и положим , где минимум берется по всем i, j, т.е. ищется наименьший из незачеркнутых элементов матрицы . Построим матрицу , проведя пересчет элементов матрицы  следующим образом:

a) из элементов  вычитается значение ;

b) элементы  остаются без изменения;

c) к элементам  прибавляется значение .

Такие преобразования являются следствием применения Теоремы 1, согласно

которой задача с новой матрицей   оказывается эквивалентной исходной и,

кроме того, элементы этой новой матрицы неотрицательны.

Если  оказалась неприведенной матрицей, то следует перейти к этапу 1.

Если же - приведенная матрица, то переходят к этапу 2.

Пример 3. Взяв матрицу  из примера 2, пересчитаем ее элементы

при , в итоге получим приведенную матрицу

 

3	0	0	0	0
0	0	1	4	2
0	3	3	2	6
0	2	0	4	6
0	0	0	6	8

=

 

Все ее нули содержат, например, 1-я горизонталь и три вертикали: 1-я, 2-я, 3-я. Следовательно, здесь k =4 < 5 и .   

Еще один пересчет дает приведенную матрицу

5	2	2	0	0
0	0	1	2	0
0	3	3	0	4
0	2	0	2	4
0	0	0	4	6

 

=

 

Здесь уже k=n= 5.

Этап 4.

 Отыскание n независимых нулей осуществляется перебором всех возможных вариантов. Удобно перебор начинать с отыскания строк или столбцов, содержащих единственный нулевой элемент, поскольку такой элемент обязательно войдет в группу независимых. Выбрав элемент , исключают из рассмотрения l -ю строку и s -й столбец, после чего переходят к отысканию следующего единственного нулевого элемента строки или столбца оставшейся части матрицы. Действуя подобным образом, можно столкнуться со следующими двумя ситуациями.

1. В результате удается выбрать n независимых нулей. ОСТАНОВ. Выписать ответ.

2. На некотором шаге все оставшиеся строки и столбцы содержат более одного нулевого элемента. В этом случае выбирается любой нулевой элемент, "помечается" номер строки, из которой выбран 0, и осуществляется переход к выбору следующего нулевого элемента. Если таким образом удается выбрать все n независимых нулей, то ОСТАНОВ. Выписать ответ. В противном случае следует возвратиться к помеченной строке и выбрать из нее другой нулевой элемент. По этой схеме надодействовать до тех пор, пока не получим n независимых нулей.

Пример 4. Взяв матрицу  из примера 3, замечаем, что независимыми

здесь будут нули с индексами (1, 5), (2, 2), (3, 4), (4, 3), (5, 1). Это

означает, что ответом в задаче о назначениях с матрицей C из примера 1

является матрица назначений вида

0	0	0	0	1
0	1	0	0	0
0	0	0	1	0
0	0	1	0	0
1	0	0	0	0

,;;; для которой .

 

Важно отметить, что наряду с указанными, здесь будут также независимыми нули с индексами (1, 4), (2, 5), (3, 1), (4, 3), (5, 2). Следовательно, эта задача о назначениях имеет еще один ответ- матрицу назначений вида

0	0	0	1	0
0	0	0	0	1
1	0	0	0	0
0	0	1	0	0
0	1	0	0	0

 , причем .

 

 

УПРАЖНЕНИЯ

1. Является ли данная матрица приведенной? Укажите количество в ней независимых нулей.

а)                                               в)

2	0	0	0	0
0	1	2	5	3
0	4	4	3	7
0	3	1	5	7
0	1	1	7	9

0	1	3	2	4
1	-1	6	0	3
3	0	-4	3	8
2	5	0	-5	7
4	3	8	7	0

 

пп =                            бьбьбю =

 

2. Решите задачу о назначениях с матрицей С вида:

а)                                    в)                                          c)

2	3	4	2	4	0
3	5	6	7	4	3
6	7	2	6	2	6
3	5	7	4	3	1
8	3	5	2	1	2
1	5	6	4	9	1

2	2	1	2	1	0
1	3	5	6	9	4
2	7	8	5	3	6
1	5	4	7	8	3
1	3	4	9	5	6
2	4	6	5	3	1

3	4	2	1	3	0
4	3	6	7	3	4
7	6	2	6	3	5
1	4	7	8	3	2
3	2	4	8	4	6
1	6	5	4	9	2

 

=                           б ь =       mdhs =     

 

f

 

 

 

МЕТОДЫ ОТСЕЧЕНИЙ

  Первый алгоритм Гомори

Рассмотрим целочисленную задачу линейного программирования в следующей форме:

            (1)

               (2)                            

            (3)                                                               

               (4)

 Идея методов отсечений состоит в следующем. Процесс получения решения задачи начинается с решения соответствующей ей оценочной задачи линейного программирования (1)-(3) с отброшенным условием целочисленности. Если полученная при этом оптимальная точка  имеет только целые координаты, то она является решением  задачи (1)-(4). Если полученное решение нецелочисленное, то вводится добавочное ограничение, которое отсекает часть области допустимых решений задачи (1)-(3) вместе с найденным нецелочисленным решением, сохраняя при этом все целочисленные точки. Затем рассматривается решение исходной задачи (1)-(3) с учетом нового ограничения. Если оно нецелочисленное, то вводится новое ограничение и так до тех пор, пока не будет найдено целочисленное оптимальное решение. Правила формирования отсекающих ограничений были разработаны  американским ученым Р. Гомори.

Идея метода, названного первым алгоритмом Гомори, заключается в следующем. Пусть в результате решения задачи (1)-(3) симплекс-методом получена нецелочисленная оптимальная точка. Заключительная симплекс-таблица содержит уравнения вида:

                                         (5)

, где I - множество базисных переменных, J - множество небазисных переменных задачи,  и - пересчитанные к данному шагу значения  и .

Выберем индекс  , такой что базисная координата  - дробная. По определению целой части числа имеем:  . Так как , то . Следовательно, с учетом равенства (5) имеем: . Если переменные , то последнее неравенство можно переписать так:

                                             (6)

Вычитая из равенства (5) неравенство (6), получаем неравенство

                                               (7)

где символом { y } обозначена дробная часть числа y. Неравенство (7) верно для всех допустимых целых точек в задаче (1)-(3). Однако координаты полученного нецелочисленного решения не удовлетворяют этому ограничению, так как для него все небазисные переменные , и, следовательно, , что невозможно для нецелого числа по определению дробной части.

Неравенство (7) может быть использовано для дополнительного отсекающего ограничения. В приведенную к канонической форме задачу его вводят в виде

                                      (8)

где - дополнительная переменная (После приведения задачи (1)-(3) к каноническому виду переменных в ней будет ).

Замечание 1. До решения задачи симплекс-методом все исходные данные должны быть приведены к целым. Иначе, например, неравенство  после приведения к канонической форме примет вид , а это уравнение неразрешимо в целых числах.