Л Solution for Задача о назначениях: Minimization (Assignment Pr

From | To | Assignment I Unit Cost | Total Cost | Reduced Cost

08-27-2004

Function

Value ■

Исп.1 Раб.2 Исп.2 Раб.З Исп.З Раб.1 Исп.4 Раб.4

Total Objective

Рис. 4.4. Отчет с перечнем предлагаемых назначений

1.150. В столбце Total Cost— общие затраты времени, вызываемые каждым назначением (они всегда совпадают со стоимостью назначений, указанной в предыдущем столбце).

1.151. В столбце Reduced Cost — приведенные (нормированные) стоимости, двойственные оценки, которые могут быть отличны от нуля только для нуле­вых (не вошедших в оптимальный план) назначений. Чтобы увидеть такие назначения и их нормированные стоимости, воспользуйтесь либо отчетом с пе­речнем всех назначений (Solution Table — All), либо отчетом об интервалах оп­тимальности (Range of Optimality). Как получить такие отчеты — говорится далее в этом разделе. Нормированная стоимость показывает: а) на какую вели­чину, как минимум, нужно снизить стоимость назначения, чтобы оно стало вы­годным (ненулевым); б) насколько увеличатся общие затраты времени, если выполнить это невыгодное назначение, не меняя его стоимости. Если у нулево­го назначения — нулевая нормированная стоимость, то это говорит о наличии альтернативных оптимальных решений.

1.152. В последней строке таблицы — оптимальное значение целевой функ­ции, общие затраты времени на выполнение работ при выполнении предлагае­мых назначений (Total Objective Function Value = 20).

После нахождения решения становится доступным меню Results. С по­мощью его команд, как и при решении транспортной задачи (см. раздел 3.2), можно узнать, сколько итераций и времени работы процессора потрачено на поиск решения (Show Run Time and Iteration), снова вызвать рассмотренный отчет, содержащий перечень предлагаемых назначений (Solution Table - Non­zero Only), а также получить другие формы отчета:

1.153. Отчет с перечнем всех назначений — Solution Table - All. В этом от­чете показаны все возможные назначения, в том числе и не вошедшие в опти­мальный план (для них нормированные стоимости могут быть положительны).

1.154. Графическое решение — Graphic Solution. Решение выводится в виде сетевой диаграммы.

1.155. Интервалы оптимальности — Range of Optimality. В таблице этого отчета (рис. 4.5), помимо сведений, присутствующих в обычном отчете, приво­дится состояние назначений в столбце Basis Status. Назначения могут быть либо базисными, то есть положительными (basic), либо небазиснымн, то есть равными нулю, своей нижней границе (at bound). В столбцах Allowable Min.

1.156. | я Range of Optimality for Задача о назначениях: Minimization	zM	X
	08-28-2004 12:38:59	From	То	Unit Cost	Reduced Cost	Basis Status	Allowable Min. Cost	Allowable Max. Cost
		Исп.1	Раб 1			at bound		M
		Исп.1	Раб.2			basic
		Исп. 1	Раб.З			at bound		M
		Исп.1	Раб.4			at bound		M
		Исп.2 Раб.1			at bound		M
		Исп.2 Раб.2			at bound		M
		Исп.2 Раб.З			basic
		Исп.2	Раб.4			basic
		Исп.З	Раб.1			basic
		Исп.З Раб.2			at bound		M
		Исп.З Раб.З			basic
		Исп.З Раб.4			at bound		M
		Исп.4	Раб.1			at bound		M
		Исп.4	Раб.2			basic
		|Исп.4 Раб.З			at bound		M
		| Исп.4	Раб.4			basic
								II

Рис. 4.5. Интервалы оптимальности задачи о назначениях

Cost и Allowable Max. Cost приведены пределы изменения стоимости назна­чений — границы интервалов оптимальности, внутри которых сохраняется прежнее оптимальное решение (при этом буква М используется вместо символа оо).

Внимание! Новый отчет в виде таблицы всегда заменяет предыдущий (старый не сохраняется). Графическое же решение сохраняется и может быть изменено лишь при повторном выборе команды Graphic Solution.

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

Варианты задачи о назначениях

При решении задачи о назначениях могут встретиться случаи, отличные от только что рассмотренного:

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

1.158. Если количество работ и исполнителей не совпадает, то для их вырав­нивания программа автоматически вводит фиктивных исполнителей под име­нем Unfilled_Demand или фиктивные работы, обозначаемые Unused_Supply. При этом стоимости назначений, в которых участвуют фиктивные исполнители или работы, полагаются равными нулю. Полученное в отчете назначение фик­тивного исполнителя (Unfilled_Demand) на реальную работу говорит о том, что эта работа не будет выполнена. А любое назначение реального исполнителя на фиктивную работу (Unused_Supply) указывает на то, что этот исполнитель не будет задействован.

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

Другие виды анализа

Как и в случае транспортной задачи, после нахождения оптимального ре­шения можно с помощью команд меню Solve and Analyze и меню Results вы­полнить следующие виды анализа (подробности см. в разделе 3.2):

1.160. Получить альтернативные оптимальные решения — Obtain Alterna­tive Solution. Эта команда появляется лишь при наличии таких решений.

1.161. Выполнить анализ «Что-если» — Perform What If Analysis. Позволяет получать различные решения, изменяя значения коэффициентов целевой функ­ции (в нашем примере — времени выполнения работ). Можно задать новое значение только одного или сразу нескольких коэффициентов. Преимущество анализа «Что-если», по сравнению с многократным решением задачи при раз­ных наборах данных, в том, что сохраняются первоначальные данные задачи.

1.162. Выполнить параметрический анализ — Perform Parametric Analysis. Исследуется, как зависит оптимальное значение целевой функции (в нашем примере — общие затраты времени) от изменяющихся стоимостей назначений (времени выполнения работ разными исполнителями). При этом, предполагая.

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

1.163. Вывести график решающей функции — Show Parametric Analysis — Graphic. Результаты предварительно выполненного параметрического анализа выдаются в виде графика, на котором показана зависимость оптимального зна­чения целевой функции от параметра (график решающей функции).

В качестве примера на рис. 4.6 и 4.7 представлены табличный и графиче­ский результаты параметрического анализа при изменении стоимости одного назначения — времени выполнения 2-м исполнителем 3-й работы. Исходное значение этой стоимости в нашем примере равно 3. Пусть нас интересует ее изменение в пределах от 1 до 9 с шагом 2 и влияние этого изменения на общие затраты времени. Если изменяется стоимость только одного назначения, ее за­висимость от параметра задается простым выражением 3 + и, где коэффициент параметра и равен 1. (Если бы изменялись сразу несколько стоимостей, то ко­эффициенты параметра и для каждой из них могли бы быть заданы разными, не обязательно равными 1.) Перед началом параметрического анализа для пара­метра и задаются: начальное значение (-2), конечное значение (6) и шаг изме­нения (2) (см. раздел 3.2).

ik Parametric Analysis for Задача о назначениях	1 J		X
	08-29-2004	Hcn.2to Раб.З Connection Cost/Distance	OBJ Value

Рис. 4.6. Результаты параметрического анализа при изменении стоимости одного

Назначения

Рис. 4.7. График решающей функции при изменении стоимости одного

назначения

1.164. Решение с помощью программы Excel