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

4 5 6 7 8 9 10

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 - Nonzero 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 Alternative 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).