Особые случаи задачи о назначениях

Содержание

1.Теоретический вопрос: Особые случаи задачи о назначениях………………3

2. Задача №1……………………………………………………………………….8

3. Задача №2……………………………………………………………………...12

4. Библиографический список…………………………………………………..14

 

 

 

 

 

 

 

 

1.Теоретический вопрос: Особые  случаи задачи о назначениях

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

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

Алгоритм решения задачи о назначениях состоит из трех этапов:

1 этап

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

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

2 этап

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

1. Найти строку, содержащую  только одно нулевое значение  стоимости, и в клетку, соответствующую  данному значению, поместить один  элемент. Если такие строки  отсутствуют, допустимо начать  с любого нулевого значения  стоимости.

2. Зачеркнуть оставшиеся  нулевые значения данного столбца.

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

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

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

5. Зачеркнуть оставшиеся  нули в данной строке.

6. Повторять пункты 4 и  5 до тех пор, пока дальнейшая  их реализация окажется невозможной.

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

 

 

3 этап

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

2. Найти наименьший среди  элементов, через которые не  проходит ни одна из проведенных  прямых.

3. Вычесть его из всех  элементов, через которые не  проходят прямые.

4. Прибавить найденный  элемент ко всем элементам  таблицы, которые лежат на пересечении  проведенных ранее прямых

5. Все элементы матрицы,  через которые проходит только  одна прямая, оставить без изменения.

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

Особые  случаи задачи о назначениях

1.Максимизация  целевой функции

Алгоритм решения задачи о назначениях предполагает минимизацию  ее целевой функции. Если имеется  задача о назначениях, целевую функцию  которой нужно максимизировать, то поступают таким же образом, как  и в алгоритме решения транспортной задачи: после окончания формирования первой таблицы все ее элементы умножаются на (— 1).

Пример

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

 

 

 

Продавец	Объемы продаж, ф. ст./тыс. шт. Торговые точки
	I	II	III	IV	V	VI
A	68	72	75	83	75	69
B	56	60	58	63	61	59
C	35	38	40	45	25	27
D	40	42	47	45	53	36
E	62	70	68	67	69	70
F	65	63	69	70	72	68

 

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

Решение

Все элементы исходной таблицы  умножаются на (-1) и выявляются минимальные  элементы.

 

Продавец	Объемы продаж, ф. ст./тыс. шт. Торговые точки						Минимальный элемент
	I	II	III	IV	V	VI
A	-68	-72	-75	-83	-75	-69	-83
B	-56	-60	-58	-63	-61	-59	-63
C	-35	-38	-40	-45	-25	-27	-45
D	-40	-42	-47	-45	-53	-36	-53
E	-62	-70	-68	-67	-69	-70	-70
F	-65	-63	-69	-70	-72	-68	-72

 

Минимальный (наибольший по абсолютной величине) элемент вычитается из всех элементов соответствующей  строки.

 

 

Вычитание минимального элемента по строкам и выявление  минимальных элементов по столбцам

15	11	8	0	8	14
7	3	5	0	2	4
10	7	5	0	20	18
13	11	6	8	0	17
8	0	2	3	1	0
7	9	3	2	0	4
7	0	2	0	0	0	Минимальный элемент

 

Минимальный элемент вычитается из всех элементов соответствующего столбца.

8	11	6	0	8	14
0	3	3	0	2	4
3	7	3	0	20	18
6	11	4	8	0	17
1	0	0	3	1	0
0	9	1	2	0	4

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

2. Недопустимые  значения

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

3. Несоответствие  числа пунктов производства и  назначения 

Если исходная таблица  не является квадратной, в нее следует  включить дополнительные фиктивные  строки и столбцы, необходимые для  приведения ее к квадратной форме. Значения стоимости, соответствующие фиктивным  клеткам, как правило, равны нулю.

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

Пример:

На предприятии имеется 6 автомобилей разных моделей. Необходимо в разные районы области перевести 5 грузов. Затраты по перевозке каждого груза каждым автомобилем различны и приведены в таблице:

Авто/Груз	Г1	Г2	Г3	Г4	Г5
А1	37	17	52	73	72
А2	11	39	70	20	27
А3	12	21	25	11	30
А4	49	35	36	35	74
А5	40	31	78	66	79
А6	77	14	59	67	78

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