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

МАКСИМИЗАЦИЯ ЦЕЛЕВОЙ ФУНКЦИИ

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

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

Таблица 13.38. Объемы продаж в различных торговых точках для различных продавцов

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

Как коммерческий директор должен осуществить назначение продавцов по торговым точкам, чтобы достичь максимального объема продаж? Решение. Все элементы исходной таблицы умножаются на (-1);

Таблица 13.39. Модификация исходных данных и выявление минимальных элементов

Продавец			Торговые	точки
						Мини-
	/	II	III	IV	V	VI	мальный элемент
А	-68	-72	-75	-83	-75	-69	-83
В	-56	-60	-58	-63	-61	-59	-63
С	-35	-38	-40	-45	-25	-27	-45
D	-40	-42	-47	-45	-53	-36	-53
Е	-62	-70	-68	-67	-69	-70	-70
F	-65	-63	-69	-70	-72	-68	-72

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

Гл. 13. Транспортная задача и задача о назначениях

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

					0 —

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

Таблица 13.41. Вычитание минимального элемента по столбцам

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

НЕДОПУСТИМЫЕ НАЗНАЧЕНИЯ

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

НЕСООТВЕТСТВИЕ ЧИСЛА ПУНКТОВ ПРОИЗВОДСТВА И НАЗНАЧЕНИЯ Если исходная таблица не является квадратной, в нее следует включить дополни­тельные фиктивные строки и столбцы, необходимые для приведения ее к квадратной форме. Значения стоимости, соответствующие фиктивным клеткам, как правило, равны нулю.

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

РЕЗЮМЕ

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

492 Ч. 4. Моделирование в бизнесе

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

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

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

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

В методе ступенек в пустую клетку помещается одна единица продукции. Затем определяются натуральные и стоимостные изменения, происшедшие под воздействием такого размещения. Метод МОДИ в большей степени основан на математической теории. Используя значения стоимости перевозки в каждой запол­ненной клетке, мы получаем стоимость, соответствующую строке или столбцу:

Используя значения компонент и и v, полученных для строк и столбцов соответ­ственно, рассчитывают значения теневых цен, соответствующие всем пустым клеткам. Их расчет производится по формуле:

Sjj = C,j - (U, + Vj).

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

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

Гл. 13. Транспортная задача и задана о назначениях 493

этом случае следует использовать пустые клетки, размещая в них псевдоперевозки объем которых равен нулю.

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

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