NET Problem Specification

Problem Type Г Network Flow

is Transportation Pr oblem Г Assignment Problem Г Shortest Path Problem Г Maximal Flow Problem Г Minimal Spanning Tree Г Traveling Salesman Problem

Objective Criterion

'■ Minimization Г Maximization

Data Entry Format

'■ Spreadsheet Matrix Form Г Graphic Model Form

Г

(i.e.. both ways same cost)

[Транспортная за

Number of Destinations И

Cancel

Help

Problem Title

Number of Sources 3

Рис. 3.1. Ввод параметров решения транспортной задачи

1.104. Форма задачи — матричная (Spreadsheet Matrix Form) или графиче­ская (Graphic Model Form). Графическая форма— в виде сетевой диаграм­мы — нагляднее, но более трудоемка для ввода данных, так как требует рисо­вания на экране узлов сети (пунктов отправления и назначения) и соединяющих их дуг (маршрутов перевозок). Поэтому в дальнейшем мы будем использовать матричную форму. Однако после ввода данных можно легко изменить форму задачи, воспользовавшись соответствующей командой меню Format.

1.105. Название задачи — Problem Title.

1.106. Количество пунктов отправления — Number of Sources.

1.107. Количество пунктов назначения — Number of Destinations.

Ввод числовых данных

Если выбрана матричная форма задачи, откроется окно с таблицей для ввода данных: затрат на перевозку единицы груза в каждом направлении (тари­фов), запасов груза в пунктах отправления и потребностей в пунктах назначе­ния. Вид этого окна после ввода данных показан на рис. 3.2. Строки таблицы соответствуют пунктам отправления (Source), а столбцы— пунктам назначе­ния (Destination). На их пересечении — тарифы соответствующих перевозок. В столбце Supply — запасы грузов в пунктах отправления, а в строке Demand — потребности в пунктах назначения.

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

1.108. Перемещаться по таблице — с помощью клавиши Tab или клавиш со стрелками.

| m Транспортная задача: Minimization (Transportation Problem) ^	Jg|x|
[Source 1 Destination 1 |5		П
	From \ To	Destination 11 Destination 21 Destination 3| Destination 4 Supply
	Source 1	5 4 5 6
	Source 2	3 3 6 6
	Source 3	2 5 7 8
	Demand	200 100 150 250

Рис. 3.2. Ввод данных для решения транспортной задачи

1.109. Выбрать ячейку таблицы — щелчком этой ячейки. Если щелкнуть го­лубое поле над таблицей, то выбранная ячейка выделится цветом и можно ре­дактировать ее содержимое.

С помощью указанных далее команд меню Edit можно изменить следую­щие параметры задачи:

1.110. Название задачи —Problem Name.

1.111. Название пунктов отправления и назначения — Node Names.

1.112. Вариант оптимизации целевой функции — Objective Function Criterion (при этом максимизация меняется на минимизацию и наоборот).

1.113. Количество пунктов отправления и назначения — Add a Note или Delete a Note (пункты добавляются или удаляются, соответственно). По умол­чанию добавляются новые пункты отправления. Для добавления пункта назна­чения выберите команду Add a Note, а затем снимите флажок Added as а source. Здесь же можно задать название добавляемого пункта.

Изменим, например, названия пунктов отправления и назначения (рис. 3.3).

С помощью указанных далее команд меню Format могут быть изменены:

® Форма задачи — Switch to Graphic Model или Switch to Matrix Form (можно перейти в графическую или матричную форму, соответственно).

1.114. Формат чисел — Number.

1.115. Шрифт и цвет — Font.

1.116. Выравнивание — Alignment.

1.117. Высота строк — Row Height.

1.118. Ширина столбцов — Column Width.

* Транспортная задача: Minimization (Transportation Pro	1 J	1н1	а
|П.отпр.1: П.мазн.1 |5
From \ То	П.назн.1	П.назн.2	П.назн.З	П.наэн.4	Supply
П.отпр.1
П.отпр.2
П.отпр.З
Demand

Рис. 3.3. Изменение названии пунктов отправления и назначения

Например, та же задача в графической форме будет выглядеть следующим образом (рис. 3.4).

Внимание! После ввода данных задачи не забудьте ее сохранить с помо­щью команды File ► Save Problem As.

Нахождение решения

Чтобы решить задачу, выберите в меню Solve and Analyze один нз сле­дующих вариантов действий:

1.119. Решить задачу — Solve the Problem. Решение находится методом по­тенциалов. По окончании решения появляется отчет в виде таблицы, в которой указаны только ненулевые перевозки. В дальнейшем можно открыть этот отчет либо посредством меню Window, либо с помощью команды Results ► Solution Table - Nonzero Only.

1.120. Решить с показом шагов — Solve and Display Steps — Tableau или Solve and Display Steps — Network. При этом все итерации метода потенциа­лов показываются в виде, соответственно, транспортных таблиц или сетевых диаграмм. На каждом шаге указываются перевозки, вводимые в базис и исклю­чаемые из него. С помощью меню Iteration вы можете перейти к следующей

я Транспортная задача: Minimization (Тга... ГМ!

итерации (Next Iteration), к концу решения с выводом отчета (Nonstop to Fin­ish) или посмотреть информацию о вводимой и исключаемой перевозке (Show Entering and Leaving Arcs).

1.121. Выбрать метод нахождения начального плана — Select Initial Solution Method. Перед началом решения можно выбрать один из восьми предложен­ных методов, в частности методы северо-западного угла, минимального эле­мента, Фогеля и др. Имейте в виду, удачный выбор может ускорить поиск оп­тимального решения.

Анализ оптимального решения и его чувствительности

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

В отчете содержится следующая информация:

«В первом столбце — номера ненулевых перевозок.

1.122. В столбцах From и То — названия соответствующих пунктов отправле­ния и назначения.

® В столбце Shipment— количество груза, которое следует перевозить в каждом направлении.

1.123. В столбце Unit Cost— затраты на перевозку единицы груза в каждом направлении (тарифы).

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

я Solution for Транспортная задача: Minimization (Transportation |	_!□!	X
	08-23-2004	From | То	Shipment|Unit CostjTotal Cost jReduced Cost
		П.отпр.1 П.назн.З
		П.отпр.2 П.назн.2
		П.отпр.2 П.назн.4
		П.отпр.З П.назн.1
		П.отпр.З П.назн.З
		П.отпр.З П.назн.4
		Total Objective	Function	Value =

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

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

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

Кроме того, с помощью команд меню Results можно вывести и другие формы отчета:

® Отчет с перечнем всех перевозках — Solution Table — All. Форма таб­лицы — та же, что на рис. 3.5, но показаны все перевозки, в том числе и нуле­вые, для которых нормированные стоимости могут быть положительны.

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

Интервалы оптимальности — Range of Optimality. В таблице этого отчета (рис. 3.6), помимо сведений, присутствующих в обычном отчете, приво­дится состояние перевозок в столбце Basis Status. Перевозки могут быть либо базисными, то есть положительными (basic), либо небазисными, равными ну­лю— своей нижней границе (at bound). В столбцах Allowable Min. Cost и Al­lowable Max. Cost приведены пределы изменения тарифов — границы интер­валов оптимальности, внутри которых сохраняется прежнее оптимальное реше­ние (при этом буква М используется вместо символа да). В нашей задаче видно, что у двух небазисных, нулевых, перевозок (из пункта 1 в пункт 4 и из пункта 3 в пункт 2) нормированная стоимость равна нулю. Значит, у задачи есть альтер­нативные оптимальные решения, в которых эти перевозки — ненулевые.

» Интервалы устойчивости — Range of Feasibility. В этом отчете (рис. 3.7) перечислены узлы, то есть пункты отправления и назначения (Node), запасы грузов (Supply), потребности в них (Demand) и теневые цены (Shadow Price). Теневая цена показывает, насколько сократятся общие затраты при сни­жении на единицу потребностей в одном пункте назначения или увеличении на

л Range of Optimality for Транспортная задача: Minimization (Tra		X
	08-24-2004 15:21:01	From	То	Unit Cost	Reduced Cost	Basis Status	Allowable Min. Cost	Allowable Max. Cost
		П.отпр.1	П.назн.1			at bound		M
		П.отпр.1	П.назн.2			at bound		M
		П.отпр.1 П.назн.З			basic	-M
		П.отпр.1	П.назн.4			at bound		M
		П.отпр.2 П.назн.1			at bound		M
		П.отпр.2 П.назн.2			basic	-2
		П.отпр.2 П.назн.З			at bound		M
		П.отпр.2 П.назн.4			basic
		П.отпр.З П.назн.1			basic
		^П.отпр.З	П.назн.2			at bound		M
		П.отпр.З П.назн.З			basic
		П.отпр.З П.назн.4			basic

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

» Range of Feasibility for Транспортная задача: Minimization	I JeI	X
	08-24-2004 20:05:36	Node	Supply	Demand	Shadow Price	Allowable Min. Value	Allowable Max. Value
		П.отпр.1			-2
		П.отпр.2			-2
		П.отпр.З					M
		П.назн.1
		П.назн.2
		П.назн.З
		П.назн.4

единицу запасов в одном пункте отправления (при неизменности запасов и по­требностей в остальных пунктах). Знак минус перед теневыми ценами, соответ­ствующими пунктам отправления, показывает, что при увеличении запасов об­щие затраты уменьшаются — изменения происходят в противоположных направлениях. (Увеличение запасов в пунктах отправления с более выгодными тарифами позволяет сократить перевозки из тех пунктов, где тарифы менее вы­годны, за счет чего общие затраты и сокращаются.) С другой стороны, умень­шение потребностей всегда сопровождается уменьшением общих затрат (изме­нения в одном направлении), поэтому теневые цены, соответствующие пунктам назначения, положительны. Пределы изменения запасов и потребностей, при которых сохраняются прежние теневые цены, — в столбцах Allowable Min. Value и Allowable Max. Value. Это и есть границы интервалов устойчиво­сти.

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

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

Варианты транспортной задачи

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

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

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

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