Математическая постановка задачи о назначениях

1

МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ О НАЗНАЧЕНИЯХ.

ВЕНГЕРСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ

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

Пусть  x=(xij)nxn – матрица назначений, где

xij – переменная величина, отражающая факт назначения

xij=

                                                                      (1)

                                                                      (2)

                                                                                    (3)

                                                        (4)

Основные утверждения, лежащие в основе  венгерского метода:

1.       Решение задачи не изменится, если к любому столбцу или строке прибавить (или вычесть) некоторую компоненту, т.е. если план x* -- оптимальный план задачи (1)-(4), то он также оптимален для функции цели Z’ c матрицей , где

                 ,       i=1,…,n,         j=1,…,n,      

2. Если все     и найден план x*, такой, что

                ,

     то x* - оптимальный план.

Суть метода: Путем прибавления определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так называемых независимых нулей. Набор нулей называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то, приняв соответствующие им переменные xij равными 1, а все остальные – равными 0, согласно утверждению 2, получим оптимальный план назначения.

Описание   АЛГОРИТМА  ВЕНГЕРСКОГО МЕТОДА

Алгоритм состоит из предварительного шага и не более, чем (n-2) последовательно повторяющихся итераций. На предварительном этапе в случае решения задачи на максимум, ее преобразуют в эквивалентную задачу на минимум. На этом же этапе выделяется система независимых нулей. Каждая последующая итерация направлена на увеличение хотя бы на 1 числа независимых нулей. Как только число независимых нулей k станет равным размерности матрицы (k=n) , задача решена.

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

Подготовительный этап.

Пусть исходная задача имеет вид

Z(x)  =cijxij max

Находим li=max{cij}.    Заменим задачу на максимум задачей на минимум:

Z’(x)  =cij’xij min,

где cij’=lj-cij.  Далее в каждой строчке матрицы C’ находим минимальный элемент и вычитаем его из элементов соответствующей строки:  с’’=║cij’- minj  cij’║ = ║cij’’║. В результате преобразования в каждой строчке (и столбце)  матрицы C’’ появится хотя бы один 0.

Подготовительный этап заканчивается выделением системы независимых нулей. Для этого в первом столбце матрицы выделяется произвольный 0 и отмечается *. Затем рассматриваются нули второго столбца. Если среди них есть такие, которые находятся не в одной строке с нулем первого столбца, уже отмеченного *, то один из них отмечается *. Аналогично рассматриваются нули для других столбцов. Отмеченные * нули независимы (по определению). Если число независимых нулей равно n, то согласно утверждению 2, задача решена.

Последующие итерации

Цель каждого последующего шага (итерации) – увеличение числа независимых нулей. Перед началом итерации выделяются знаком «+» столбцы матрицы, содержащие 0*. Т.к. k<n, то не все столбцы окажутся выделенными. Устанавливаем, имеется ли среди невыделенных элементов матрицы хотя бы один 0.

Возможны следующие случаи:

1.       Среди невыделенных элементов имеется хотя бы один 0. Проверяем, содержит ли строка с невыделенным нулем также 0*.

а) если да, то невыделенный ноль отмечается 0’, содержащая этот ноль строка отмечается справа знаком «+» и снимается знак выделения «+» над столбцом, в котором расположен 0*, лежащий в только что выделенной строке. Снятие «+» производится знаком 

  .

б) если в строке с невыделенным нулем нулей со * нет, то невыделенный ноль также отмечается 0’.

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

Итерация оканчивается, если в строке с невыделенным нулем нет 0*. Невыделенный ноль, как говорилось, отмечается 0’, и строится цепочка элементов по правилу:  движение начинается от 0’ по столбцу к 0*, от 0* по строке переходим к 0’, вновь от 0’ к 0* по столбцу и т.д. начало и конец цепочки – нули с ‘ ”. если случится, что в одном столбце с исходным 0’ нет 0*, то цепочка вырождена.

После построения цепочки * над нулями уничтожаются, а ‘ заменяются на *. Все остальные * над нулями, не находящимися на цепочке, сохраняются. Т.к. в цепочке 0’ на один больше, чем 0* , то в результате общее число 0* увеличится на единицу. На этом одна итерация заканчивается.

Подсчитываем количество 0* (независимых нулей). Если k=n, то найден оптимальный план назначения. Иначе переходим к следующей итерации.

ПРИМЕР

Пусть надо решить задачу о назначениях на максимум

max: Z=cijxi   j,

где

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

          1).     2). 

3).

Образуем первоначальную систему независимых нулей, отмечая их звездочкой. Имеем матрицу С0. Число независимых нулей к=3. Так как к<n=4, то переходим к основному повторяющемуся шагу.

Первая итерация. В матрице 4 над столбцами, содержащими 0*, ставим знак «+». Находим невыделенный столбец j=4.Ищем в невыделенном столбце нулевой элемент. Это с14=0. Помечаем его штрихом с14=0’. Просматриваем строку i=1. В ней есть выделенный ноль с11=0*. Снимаем выделение первого столбца знаком  . выделяем первую строку знаком «+». Получаем матрицу5.

4).        +      +       +                5)           +      +

Если в матрице 5 вычеркнуть выделенные столбцы j=2,3 и выделенную строку, то получим матрицу, в которой нет нулей. Обозначим множество невыделенных строк через I1. Очевидно, что I1={2,3,4}, а множество невыделенных столбцов через J1, здесь J1={1,4}. Находим min{cij}=4, i I1, jJ1.

Прибавим число 4 к выделенным столбцам и вычтем его из невыделенных строк, получим матрицу 6:

6)          +      +

В результате такого преобразования получим новые невыделенные нули С21=0,  С41=0, С44=0. Берем любой из них и отмечаем его штрихом. Например, С21=0’. Так как в строке i=2 имеется  0*, то снимаем выделение столбца j=3. Перейдем к матрице 7:

7)        +   

Среди невыделенных рядов матрицы есть невыделенный ноль. Это С41=0. Штрихуем этот ноль С41=0’. В строке i=4 имеется 0*, снимаем выделение столбца j=2. Выделяем строку i=4. Получаем матрицу 8:

8).          

Среди невыделенных рядов находим невыделенный ноль С33=0. Штрихуем этот ноль С33=0’. В строке i=3 нет 0*, поэтому нужно строить цепочку. От последнего нуля со штрихом С33=0’ по столбцу переходим к нулю со звездочкой С23=0*. От С23=0* по строке i=2 переходим к нулю со штрихом С21=0’. От С21=0’ по столбцу j=1 переходим к нулю со звездочкой С11=0*. От С11=0* переходим по строке i=1 к С14=0’. В столбце j=4 нет 0*. Следовательно, построение цепочки закончено. Построенная цепочка показана в матрице 9:

9).          

На цепочке С33С23С21Сс11С14 нули со штрихом заменяем на нули со звездочкой. Звездочки над нулями, не находящимися на цепочке, сохраняем. Все остальные выделения уничтожаем. Переходим к матрице 10, в которой число независимых нулей увеличивается на единицу. На этом первая итерация заканчивается:

10)

Вторая итерация. Подсчитываем число независимых нулей к=4. Так как n=4, то k=n. Задача решена. Оптимальный план представлен в матрице 11:

11).

РЕШЕНИЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ С ПОМОЩЬЮ ПРОЦЕДУРЫ «ПОИСК РЕШЕНИЯ» MICROSOFT EXCEL FOR WINDOWS

Рис. 1. Представление исходных данных данных на листе EXEL

Рис. 2. Программирование ячеек, соответствующих целевой функции и левым частям системы ограничений

Рис. 3. Экранная форма «Поиск решения» та «Параметры поиска решений»

Рис. 4. Результаты работы процедуры «Поиска решения»

ВАРИАНТЫ ЗАДАНИЙ

8

1.

2.