4.3. задача о назначениях

4.3. задача о назначениях

Рассмотрим ситуацию, когда требуется распределить m работ (или исполнителей) по n станкам. Работа і (i=1,...,m), выполняемая на станке j (j=1,...,n), связана с затратами су . Задача состоит в таком распределении

работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат.

Эту задачу можно рассматривать как частный случай транспортной задачи. Здесь работы представляют «исходные пункты», а станки -«пункты назначения». Предложение в каждом исходном пункте равно 1, т.е. ai = 1 для всех і. Аналогично спрос в каждом пункте назначения равен 1, т.е. bj = 1 для всех j. Стоимость «перевозки» (прикрепления) работы і к станку j равна Cj. Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость Cj берется равной

очень большому числу. Матрица стоимостей C определяется следующим образом:

станки 1 2 ... n ai

виды работ

2

C21 C22 " C2n

m V Cm1 Cm2 " Cmn J

bj 1 1 ... 1

Прежде чем решать такую задачу необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m = n.

Пусть Xj = 0, если j-я работа не выполняется на і-м станке,

x j = 1, если j-я работа выполняется на і-м станке. Таким образом, решение задачи может быть записано в виде двумерного массива X = {x j J. Допустимое решение называется

назначением. Допустимое решение строится путем выбора ровно одного элемента в каждой строке матрицы X = (x j j и ровно одного элемента в

каждом столбце этой матрицы. Для заданного значения n существует n! допустимых решений.

Теперь задача будет формулироваться следующим образом:

F (X) = Yj X Cj • x j —» min

i = 1j = 1

n

Xj = 1 i = 1,-,n

j=1

n

Xj = 1 J = 1,-,n

=1

Xj є{0,1}.

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

Для иллюстрации задачи о назначениях рассмотрим таблицу с тремя работами и тремя станками.

Виды работ

1

2 3

Специфическая структура задачи о назначениях позволяет использовать эффективный метод для ее решения.

Замечание. Оптимальное решение задачи не изменится, если из любой строки или столбца матрицы стоимостей вычесть произвольную постоянную величину.

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

С

Оптимальное назначение:

х* = 1, x*3 = 1, x3*2 = 1, остальные x * = 0,

F (X *) = 5 + 12 + 13 = 30.

К сожалению, не всегда удается определить решение так просто.

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

Шаг 1. (Редукция строк и столбцов).

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

Шаг 2. (Определение назначений).

а) Найти строки, содержащие ровно один невычеркнутый нулевой элемент. В каждой такой строке произвести назначение, соответствующее невычеркнутому нулевому элементу. В каждом столбце, в котором было произведено назначение, вычеркнуть все невычеркнутые ранее нулевые элементы. Строки рассматриваются в порядке возрастания их номеров.

б) Найти столбцы, содержащие ровно один невычеркнутый нулевой

элемент. В каждом таком столбце произвести назначение,

соответствующее невычеркнутому нулевому элементу. В каждой строке,

в которой было произведено назначение, вычеркнуть все невычеркнутые

ранее нулевые элементы. Столбцы рассматриваются в порядке

возрастания их номеров.

в) Выполнять пункты а) и б) до тех пор, пока не будет вычеркнуто

максимально возможное число нулевых элементов. Если построенное

назначение полное, то оно является оптимальным.

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

Если нельзя найти полного назначения, то необходима дальнейшая модификация матрицы стоимостей, т. е. перейти к шагу 3.

Шаг 3. (Модификация редуцированной матрицы).

Для редуцированной матрицы стоимостей:

а) Вычислить число нулей в каждой невычеркнутой строке и

каждом невычеркнутом столбце.

б) Вычеркнуть строку или столбец с максимальным числом нулей.

в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты

все нули.

г) Из всех невычеркнутых элементов вычесть минимальный

невычеркнутый элемент и прибавить его к каждому элементу,

расположенному на пересечении двух линий.

Перейти к шагу 2.

Замечания.

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

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

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

c

4-)

Итерация 1

Шаг 1. Редукция строк и столбцов.

Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим следующую матрицу:

' 0 8 7 5 Л

11 0 10 4

2 3 5 0'

. 0 11 9 15,

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5 и 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим следующую матрицу.

(0 8 2 5 ^

C

11 2

0 3 5 0 4 0

v 0 11 4 15 у

Шаг 2. Поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

а) Строки 1, 2 и 4 содержат по одному невычеркнутому нулю.

Рассматривая эти строки в порядке возрастания их номеров, произведем

вначале назначение, соответствующее элементу (1,1), и вычеркнем

нулевой элемент (4,1). Затем произведем назначение, соответствующее

элементу (2,2). Строка 4 не может быть использована, поскольку

нулевой элемент (4,1) был вычеркнут.

б) Столбцы 3 и 4 содержат по одному невычеркнутому нулю.

Рассматривая эти столбцы в порядке возрастания их номеров, мы можем

произвести третье назначение, соответствующее элементу (3,3). В

столбце 4 назначение невозможно, так как мы произвели назначение,

соответствующее элементу (3,3). После выполнения данного шага

матрица стоимостей имеет следующий вид:

((0) 8 2 5 ^

11 (0) 5 4

2 3 (0) 0

0 11 4 15у

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

Шаг 3. Модификация редуцированной матрицы.

С

(0 її

2

о

8

о

3

її

5 1 4

о

15 J

а) Число нулей в строках 1, 2, 3 и 4 равно 1, 1, 2 и 1 соответственно.

Для столбцов соответствующие величины равны 2, 1, 1 и 1.

б) Максимальное число нулей, по два, содержат строка 3 и столбец

1. Выбираем строку 3 и вычеркиваем все ее элементы горизонтальной

линией.

в) Число невычеркнутых нулей в строках 1, 2 и 4 равно 1, 1 и 1

соответственно. Для столбцов соответствующие значения равны 2, 1, о,

и 0. Поэтому мы должны выбрать столбец 1 и вычеркнуть его

вертикальной линией. После этого останется только один

невычеркнутый нуль элемент (2,2). Поэтому можно вычеркнуть либо

строку 2, либо столбец 2. Вычеркивая строку 2 горизонтальной линией,

получаем следующую матрицу:

(

0 8 2 5 1

1о54

23оо о 11 4 15

J

г) Значение минимального невычеркнутого элемента равно 2. Вычитая его из всех невычеркнутых элементов и складывая его со всеми элементами, расположенными на пересечении двух линий, получаем новую матрицу стоимостей:

Итерация 2.

Шаг 2.

Выполняя вновь процедуру построения допустимого решения нулевой стоимости, получаем следующее оптимальное решение:

Оптимальное назначение:

x*3 = 1, x*2 = 1, x3*4 = 1, x41 = 1, остальные x * = 0,

F(X *) = 9 + 4 + 11 + 4 = 28.

Пример 4.8: (Задача размещения производства)

Компания разрабатывает план выпуска трех новых видов продукции. Предположим, что компания владеет пятью предприятиями и что на трех из них должны производиться новые виды продукции по одному виду на одно предприятие. Ниже указаны издержки производства и сбыта единицы продукции.

Издержки производства единицы продукции (руб.):

Предприятие

1 2 3 4 5

1 I 20 I 23 I 38 I 15 I 35

Вид 2 8 29 6 35 35

продукции 3 5 8 3 4 7

Издержки сбыта единицы продукции (руб.):

Предприятие

1 2 3 4 5

Вид 1 120 150 120 110 113

продукции 2 7 90 8 35 60

3 |5 І5 И 115 |б

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

Решение: Общие издержки на единицу продукции складываются из издержек производства и издержек сбыта. Поскольку продажная цена единицы каждого вида продукции известна, то можно вычислить прибыль на единицу продукции:

1

Предприятие 2 3

4

5

Вид 1 продукции 2

3

15

20

35

-18

-69

17

_-3_

36

23

30

11

-20

7

-45

17

Умножая прибыль, приходящуюся на единицу продукции, на годовой объем сбыта, можно получить общую годовую прибыль, соответствующую каждой паре вид продукции предприятие. Данные величины (в тыс. руб.) приведены в следующей таблице:

Если прибыль рассматривать как отрицательные затраты, то исходная задача максимизации может быть сведена к минимизационной задаче о назначениях. Для того чтобы матрица стоимостей не содержала отрицательных элементов, сложим каждый элемент матрицы с числом 5760 и введем два вида фиктивной продукции (4 и 5), которой соответствует нулевая прибыль. В результате будет получена следующая матрица:

Вид

продукции

Предприятие

1 2 3

1 I -525 I 630 I 105

4 5

-1050 I -245~

3200 7200

-594 | -918~

Вид

продукции

Итерация 1

Шаг 1.

Г 525

C

160 I 162

0 0

0

'525 1680 160 16800 162 324

0

1155 0 805 ^

0 8960 12960

0 64 8 324

0 0 0

Оптимальное решение данной задачи следующее: производство первого вида продукции назначается предприятию 4, второго вида -предприятию 1, третьего вида предприятию 3, четвертого вида -предприятию 2, пятого вида предприятию 5. Очевидно, что 2 последних назначения являются фиктивными. Суммарная годовая прибыль, соответствующая данному решению, равна1050 + 5600 + 1242 = 7892 тыс. руб.

Оптимальное исследование рынка.

Группе, исследующий рынок, требуется получить данные из n различных мест. В ее распоряжении имеется n дней, и она предполагает провести по одному дню в каждом месте, проведя по аj опросов, j=1,...,n. Вероятность успешного опроса в каждом месте задается матрицей Р. Элемент матрицы рцхарактеризует вероятность успешного опроса в течении і-го дня в j-м месте, і=1,.. .,n.

Определить время проведения опросов, при котором общее число опросов максимально.

Решение. Сведем данную задачу к задаче о назначениях.

Введем величину гц=рц^, показывающую число успешных опросов в в j-м месте в течение і-го дня.

1, если в і-й день опрос проводится в j-м месте;

«0, в противном случае. Математическая модель задачи имеет следующий вид:

nn

F = YYrjxj— max.

i=1j=1

n i=1

[xij є {0;1}, , і=1,...лі; , j=1,...,n.

Функция F характеризует суммарное число успешных опросов. Ее нужно максимизировать. Первое и второе ограничения соответствуют тому, что в течении одного дня можно находиться только в одном месте. Для расчета модели венгерским методом надо перейти к противоположной функции

nn

F ' = -YYrvxy •

=1j=1

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

Оптимальное использование рабочих агентов.

Торговая фирма продает товары в n различных городах, покупательная способность жителей которых оценивается bj усл. ед., j = 1,...,n. Для реализации товаров фирма располагает n торговыми агентами, каждого из которых она направляет в один из городов. Профессиональный уровень агентов различен; доля реализуемых і-м торговым агентом покупательных способностей составляет аі, і = 1,...,n. Как следует распределить торговых агентов по городам, чтобы фирма получила максимальную выручку от продажи товаров?

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

Введем параметр сч= ai bj , характеризующий величину покупательных способностей, реализуемых і-м торговым агентом в j-м городе.

Управляющие переменные xij , і = 1,...,n; j = 1,...,n определяются по формуле

"~ 1, если і-й агент направлен в j-й город;

xij=

0, в противном случае. Математическая модель запишется в следующей форме:

F = SSScjxj -max.

і =1 j=1

j

j=1

Sxij =1 j = 1,-n;

i=1

[ Xij є {0;1}, і =1,...,n; , j =1,...,n.

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

Домашнее задание 4.3.

1. Рассмотреть следующую задачу распределения четырех рабочих по четырем станкам. Соответствующие коэффициенты стоимости в долларах приведены в таблице. Рабочий 1 не может работать на станке 3, а рабочий 3 — на станке 4. Найти решение.

Станок 12 3 4

Рабочий

— 2

2 3

5 —

6 7

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

3. Решить задачу о назначениях.

4. Решить задачу о назначениях.

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

Матрица времен  

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

6. Решить задачу оптимального исследования рынка в четырех городах, если задана матрица успешных опросов

7. Решить задачу оптимального исследования рынка в трех городах, если в каждом из городов предполагается проводить по 10 опросов. Матрица вероятностей успешных опросов

Р

0,3 0,2 0,2 0,1 0,4 0,1

0,2 0,5 0,1

8. Решить предыдущую задачу при условии, что в первом и втором

городах предполагается провести по 5 опросов, а в третьем 10.

9. Решить задачу оптимального использования трех торговых

агентов в трех городах, если задана матрица покупательных способностей сі], реализуемых і-м агентом в j-м городе.

С

200 270 360 180 240 330 210 300 300

10. Решить задачу оптимального использования трех торговых агентов в трех городах, если покупательная способность жителей j-го города, j = 1,2,3, равна 300, 450 и 360 усл. ед., а доли реализуемых і-м торговым агентом і = 1,2,3, покупательных способностей равны 0.5; 0,4 и 0,3 соответственно.