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

↑

▷ Содержание

⇐ ПредыдущаяСтр 4 из 7Следующая ⇒

Пусть имеются 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. Пусть

С=

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

=                                 , A =,

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

Этап 2.

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

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

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

=

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

Этап 3.

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

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

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

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

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

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

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

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

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

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

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

=

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

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

=

Здесь уже 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

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

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

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

 , причем .

УПРАЖНЕНИЯ

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

а)                                               в)

пп =                            бьбьбю =

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

а)                                    в)                                          c)

=                           б ь =       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. До решения задачи симплекс-методом все исходные данные должны быть приведены к целым. Иначе, например, неравенство  после приведения к канонической форме примет вид , а это уравнение неразрешимо в целых числах.

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии