Linear Programming Output summary 13 страница

Таблица 5.24

Vj = 1 v₂ = 2 v₃ = 4 v₄=15 Предложение

и, = 0

щ = 5

		-е		— в
	-9	_ А		-16	+: 4
	: 7 0 + 6-	.. 9 —•15'--	Т 20 -10-е
	-6	+				-
		-9		-9

^СпР^0С 5 15 15 15

5.3. Решение транспортной задачи 217 Таблица 5.25

vi = -3 V2 - 2 1/з ⁼ 4 i/4 = 11 Предложение

	-13				-16
	-10						-4
			-5		-5

Спрос 5 15 15 15

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

От элеватора До мельницы Количество зерновозов

Суммарная стоимость перевозок =	435 долл.

5.3.3. Решение транспортной задачи с помощью TORA

Ранее было показано, как решить транспортную задачу в программе TORA в авто­матическом режиме. В этом разделе будет описано, как решать эту задачу в обучающем режиме (режиме пошагового выполнения). Также будет показано, как можно решить эту задачу, используя средство Excel Поиск решения и программу LINGO.

Обучающий режим программы TORA. Из меню Solve/Modify выберите команду Solved Iterations. Чтобы приступить к решению транспортной задачи, из появивше­гося подменю выберите один из трех методов решения (северо-западного угла, наи­меньшей стоимости или Фогеля). В этом режиме можно использовать два полезных интерактивных средства.

1. Любые значения потенциалов и и v можно приравнять к нулю перед вычис­лением второй итерации (по умолчанию и, = 0). Если вы приравняли к нулю какой-либо потенциал, отличный от u_v то заметите, что, несмотря на то, что значения u_t и v_] изменились, значения в небазисных ячейках (= u_t + v_j - c_tj) ос­тались неизменными. Это означает, что изначально любые и или v могут при­равниваться к нулю (в действительности могут принимать любое значение), что не влияет на применение условия оптимальности.

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

Глава 5. Транспортные модели

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

На рис. 5.4 представлено решение задачи из примера 5.3.1, полученное в систе­ме TORA с применением метода северо-западного угла.

Рис. 5.4. Решение в системе TORA транспортной задачи из примера 5.3.1

Средство Excel Поиск решения. Ввод данных транспортной модели в рабочую книгу Excel не вызывает затруднений. На рис. 5.5 показан пример решения задачи из примера 5.3.1 (файл ch5SolverTransportation.xls). Этот шаблон может быть ис­пользован для решения моделей, которые состоят из не более 10 пунктов отправле­ния и не более 10 пунктов назначения. Рабочий лист состоит из разделов входных и выходных данных. В разделе входных данных обязательно должны содержаться следующие данные: количество пунктов отправлений (ячейка ВЗ), количество пунктов назначений (ячейка В4), транспортная таблица, т.е. матрица стоимостей (диапазон В6:К15)⁶, названия пунктов отправления (диапазон А6:А15), названия пунктов назначения (диапазон В5:К5), объемы предложения (диапазон L6:L15) и спрос (диапазон В16:К16). В разделе выходных данных (диапазон В20:К29) со­держится оптимальное решение в матричном виде, которое вычисляется автомати­чески. Соответствующее значение общей стоимости вычислено в ячейке А19. Размер модели был ограничен до 10 х 10 для того, чтобы все данные поместились на экране. Ниже приведем подробные объяс-нения того, как можно создать в Excel табличную модель, размер которой регулируется пользователем.

На рис. 5.5 часть строк этого диапазона и диапазона В20:К29 скрыты. — Прим. ред.

5.3. Решение транспортной задачи

А

В

: С,

D

Е _

L.H.

_L.

L i_

_ К

L

Входные данные

К-во п. отправления

з

«максимум 10

А

К-во п. назначения

«MafO"-vM 10

Матрица стоимостей

D1

D2

D3

Предложение

S1

S2

S3

4

16 -

Спрос

Оптимальное решение

Общая стоимость

D1

D2

D3

D4

S1

S2

S3

Пг)игк рршениа

№1

Установить целевую ячейку: |$А$19~4j Равной: с иэсииальному значению *~ значению: (о"

миидаильному знамению, Изменяя ячейки:

■ Ограничения:

Выполнить I Закрыть |

Предпопоасить I

$8$30:$К$30 - t6$16:$K$16 tLt20:$L$29 = $L$6:$L$15 ~3

Рис. 5.5. Решение задачи из примера 5.3.1, полученное с помощью средства Поиск решения

После ввода исходных данных откройте средство Поиск решения и щелкните на кнопке ОК. Решение появится в диапазоне В20:К29.

Для создания транспортной модели в рабочий лист необходимо ввести следую­щие формулы.

Формула вычисления значения целевой функции в ячейке А19: =СУММПРОИЗВ(В6:К15;В20:К29).

Объемы перевозки от пунктов отправления: в ячейку L20 сначала введится формула =СУММ(В20:К20), после чего она копируется в диапазон L21:L29.

Объемы перевозки до пунктов назначения: в ячейку В30 вводится формула =СУММ(В20:В29), затем она копируется в диапазон С30:К30.

Ограничения модели связаны с отношениями объемов перевозок и объемов предложения в пунктах отправления и спросом в пунктах назначения. Ограниче­ния формируются в виде следующих равенств

$L$20:$L$29=$L$6:$L$15 $В$30:$К$30=$В$16:$К$16

Глава 5. Транспортные модели

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

На рис. 5.6 показано решение примера 5.2.5 с использованием новой формули­ровки задачи (файл ch5SolverNetworkBasedTransportation.xls). Решение задачи находится в столбце В (начиная с ячейки В22) под заголовком "Поток". Названия маршрутов были сгенерированы автоматически на основе названий пунктов от­правления и назначения в разделе входных данных и находятся в столбце А (начиная с ячейки А22 и ниже).

Основные формулы, с помощью которых вычисляется оптимальное решение, содержатся в разделе промежуточных вычислений. В столбце Е (начиная с ячей­ки Е21) находятся порядковые номера пунктов отправлений и назначений, при­чем сначала идут пункты отправлений. Эта информация, а также номера пунктов отправлений и назначений используются для числового представления путей модели. Например, пункт отправления 1 (ячейка Н21) в пункт назначения 4 (ячейка 121) обозначают путь от пункта отправления S1 в пункт назначения D1.

На основе информации из столбцов Н и I в столбце F (начиная с ячейки F21) строятся формулы для вычисления потока через узел. В частности, в ячейке F21 содержится следующая формула⁵.

=СУММЕСЛИ($Н$21:$Н$121;$Е21;$В$22:$В$122)--СУММЕСЛИ($1$21:$1$121;$Е21;$В$22:$В$122)

Затем эта формула была скопирована в диапазон F22:F121.

В сущности, в формуле СУММЕСЛИ вычисляется чистый поток (вход-выход) че­рез каждый узел, перечисленный в столбце Е (начиная с ячейки Е21). Важно отме­тить, что в данной стандартной транспортной модели с помощью формулы можно эффективно вычислить сумму выходных потоков из каждого пункта отправления или сумму входных потоков в каждый узел пункта назначения. Несмотря на то что необходимо использовать две отдельные формулы для представления выходных потоков в пунктах отправлений и входных потоков в пунктах назначений, при ис­пользовании основных сетевых моделей (которые обсуждаются в главе 6) все вы­числения можно объединить в одной формуле.

Для каждого узла величина потока вычисляется по формуле:

входной поток - выходной поток = чистый поток.

Нам необходимо определить объем чистого потока для каждого узла. В столбце G (начиная с ячейки G21) содержатся данные, которые автоматически копируются из раздела входных данных с помощью функции ИНДЕКС. Заметьте, что чистый поток для узла пункта отправления имеет положительный знак, в то время как для узлов пунктов назначения чистый поток имеет отрицательное значение. Необходимость использования отрицательных значений чистого потока для узлов пунктов назна­чений обусловлена тем, как определен поток через узлы сети в столбце F.

Идея использования функции СУММЕСЛИ для представления баланса потоков в сети по­заимствована из статьи С. Т. Ragsdale, "Solving Network Flow Problems in a Spreadsheet", COMPASS News, No. 2, Spring 1996, pp. 4, 5. Остальная часть таблицы, частичная автоматиза­ция вычислений и раздел промежуточных вычислений разработаны автором.

5.3. Решение транспортной задачи

	А	В	с	D		■F	G	н 1		J | К	L
			Общая сетевая модель
2 'Входные данные:
3 К-ьо п. отправления		«маюимум 10
	К-во п. назначения		«максимум 10
	Пр.способностьи пи"	п	«■«иэиениетенз	V, е<-ли v4>"weeTCH пр способность
			Матрица «дельных стоимостей
■1!.		D1	D2	D3	D4					Предложение
ь	S1 _
	S2
to	S3
'18	Спрос			1S
	Оптимальное решение:	Промежуточные вычисления:
	Общая стоимость ■		Имя	Узел	поток	Спрос	От	В	Уд. стоимость
	От-в	Поток	Пр спос.	S1		, 1S
	S1-D1		99959»	S2		1 25
	SI - D2	В		S3
	S1 - D3					-S	-5		7 11
	S1 -D4			D2		-15	-15		4,2 5 7
	S2-D1			D3		-15	-IS
	S2-D2			D4		-15	-is
ы	S2-D3	IS								20'
	S2-D4
	S3-D1	S
Ж	S3-D2
S3-D3									16.
S3-D4	S
34 •

Поиск решения

Установить целевую «чайку: Равной:-;.<"" досииальному значению С

Р ницинальному значению Иэиенаяячейф!'.-

|$В$22:$В$ЗЭ

JB$22:$B$33 <=$C$22:$C$33 |F$21:$F$27 = $G$21:$G$27

Рис. 5.6. Решение примера 5.3.1, полученное с использованием сетей

Можно также наложить ограничения на пропускные способности на различных маршрутах транспортной модели. Сначала введите латинскую букву "у" (без ка­вычек) в ячейку В5. В результате будут созданы и соответствующим образом оза­главлены ячейки в диапазоне N8:W17, в которые можно ввести ограничения про­пускной способности маршрута. Если пропускная способность маршрута не ограничена, то соответствующая ячейка должна остаться пустой. После этого огра­ничения пропускной способности с помощью функции ИНДЕКС будут автоматиче­ски скопированы в столбец С (начиная с ячейки С22). Число 999 999 представляет неограниченную пропускную способность.

Глава 5. Транспортные модели

Теперь для решения задачи осталось только задать параметры средства Поиск решения. Целевая ячейка уже содержит следующую общую формулу, которую не нужно изменять для моделей, размер которых не превышает 10 х 10.

=СУММПРОИЗВ(В22:В122;и21:Л21)

Осталось заполнить поля Изменяя ячейки и Ограничения в диалоговом окне сред­ства Поиск решения. На рис. 5.6 показано, что в поле Изменяя ячейки содержится ссылка $В$22:$В$33.

В строках 22:33 содержатся все возможные маршруты модели, которые изме­няются в соответствии с размерами транспортной задачи.

Ограничения можно сформулировать следующим образом.

Поток на маршруте (/,;) < пропускной способности на маршруте (/, j), (входной поток - выходной поток) через узел = спрос в узле

Для первого множества ограничений левая часть выражения соответствует зна­чениям в столбце В (начиная с ячейки В22), а правая часть — значениям в столбце С (начиная с ячейки С22). Например, на рис. 5.6 первой группе ограничений соот­ветствует такое выражение.

$В$22:$В$33 <= $С$22:$С$33

Значения для второго множества ограничений содержатся в столбцах F и G, а выражение выглядит следующим образом.

$F$21:$F27 = $G$21:$G$27

Условия неотрицательными можно задать в диалоговом окне Параметры поиска решения, которое появляется после щелчка на кнопке Параметры в окне средства Поиск решения⁶.

Решение транспортной задачи в программе LINGO. На рис. 5.7 представлена модель LINGO для транспортной задачи примера 5.3.1 (файл ch5LingoTrans.lg4). Используемые в модели имена не нуждаются в пояснениях. Обратите внимание на то, что имена пунктов отправлений (SI, S2, S3) и пунктов назначений (Dl, D2, D3, D4) можно ввести так, как показано на рисунке, вместо того, чтобы включать их в раздел DATA (Данные) модели.

УПРАЖНЕНИЯ 5.3.2

1. В табл. 5.26 приведены исходные данные (в долл.) для трех транспортных задач.

a) Используя начальное решение, полученное методом северо-западного уг­ла, найдите их оптимальное решение.

b) В программе TORA сравните начальные решения, полученные методами северо-западного угла, наименьшей стоимости и Фогеля.

c) Решите задачи с помощью средства Excel Поиск решения.

d) Решите задачи с помощью программы LINGO.

Следует быть внимательным, поскольку стандартная версия средства Поиск решения, вхо­дящая в поставку Excel, обладает некоторыми "особенностями". Если в диалоговом окне Параметры поиска решения установить слишком маленькое значение в поле Относительная погрешность (например, 0,000000001), будет выдано непонятное сообщение о том, что модель не удовлетворяет условиям линейности. Кроме того, выходные результаты будет легче читать, если их округлить (например, число 1Е-14 должно отображаться как 0, а 9,999999999 — как 10).

5.3. Решение транспортной задачи

MODEL:

TITLE: Transportation model, Example 5.3-1; SETS:

from/SI S2 S3/:supply; to/Dl D2 D3 D4/:demand; route (from, to):cost, ship; ENDSETS

MIN=0SUM(route (I, J).-cost (I, J) *ship(l,J));!subject to; 0FOR (

to(J):0SUM(from(I):ship(I,J))=demand(J));

@FOR (

from (I):@SUM(to (J): ship (I, J))=supply(I));

DATA:

supply=15 25 10; demand=5 15 15 15; cost=10 2 20 11 12 7 9 20 4 14 16 18; ENDDATA END

Рис. 5.7. Решение транспортной задачи в программе LINGO

Таблица 5.26

	а)				Ь)				с)
								—

2. В транспортной модели (табл. 5.27) суммарный спрос превышает общий объем предложений. Пусть штрафы за необеспеченный единичный спрос составляют 5 долл. для первого пункта назначения, 3 — для второго и 2 — для третьего.

a) Используя начальное решение, полученное методом наименьшей стоимо­сти, найдите оптимальное решение.

b) Решите задачу с помощью средства Excel Поиск решения.

c) Решите задачу с помощью программы LINGO.

Таблица 5.27

5 1 7

6 4 6 3 2 5 75 20 50

3. Пусть в транспортной модели из предыдущего упражнения штрафы не назнача­ются, но спрос третьего пункта назначения должен быть выполнен полностью. Найдите оптимальное решение в программах a) TORA, b) Excel, с) LINGO.

10 80 15

Глава 5. Транспортные модели

4. В несбалансированной транспортной модели (табл. 5.28) стоимость хранения единицы груза, не отправленного из первого, второго и третьего пунктов от­правления, составляет соответственно 5, 4 и 3 долл. Найдите оптимальное ре­шение, если из второго пункта отправления груз должен быть вывезен полно­стью. Для получения начального решения используйте метод Фогеля.

Таблица 5.28

1 2 1 3 4 5

2 3 3 30 20 20

5. Пусть в транспортной модели размерностью 3x3 через х_ц обозначено количе­ство грузов, перевозимых из пункта отправления i в пункт назначения

а через c_tj — стоимость перевозки. Объемы грузов в первом, втором и третьем пунктах отправления равны соответственно 15, 30 и 85 единиц. Спрос в пер­вом, втором и третьем пунктах назначения составляет 20, 30 и 80 единиц со­ответственно. Предположим, что начальное решение, полученное методом северо-западного угла, оптимально со следующими значениями потенциа­лов: и₁ = -2, и₂ = 3, и₃ = 5, и, = 2, v₂ = 5 и v₃ = 10.

a) Найдите оптимальную стоимость транспортных расходов.

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

6. В табл. 5.29 показано вырожденное базисное решение некой транспортной задачи. Пусть этому решению соответствуют следующие значения потенциа­лов: и, = 1, и₂ = -1, v_l = 2, Dj = 2hd_s= 5. Стоимости перевозок для всех нуле­вых (базисных и небазисных) переменных х_ц представим в виде

с,. = / +;9, -со < 0 < со.

Таблица 5.29

10 20 20

20 40 30

a) Найдите значение целевой функции, если данное решение оптимально.

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

7. Дана следующая задача.

Т п

Минимизировать z = ^^с,у*,_у при выполнении ограничений

"£jr,_y>a„ / = 1,2,...,т,

5.3. Решение транспортной задачи

|>„>г>,, у = 1,2,..., и,

х_ц > 0, для всех i и у.

Логично предположить, что оптимальное решение обращает первое или вто­рое множество неравенств в равенства (в зависимости от того, будет ли вы­полняться неравенство ^я,>^6_уили 2^e, <^fy). Контрпример, опровер­гающий это предположение, представлен в табл. 5.30.

Таблица 5.30

1 1 2 6 5 1

2 7 1

Покажите, что данное предположение приводит к "оптимальному" решению х_п = 2, х₁₂ = 3, х₂₂ = 4, х₂₃ = 2, дающему 2 = 27 долл., которое хуже решения х_и = 2, х₁₂ = 7, х₂₃ = 6 с г = 15 долл.

5.3.4. Интерпретация метода потенциалов как симплекс-метода

Связь метода потенциалов с симплекс-методом основывается на соотношениях двойственности задач ЛП (раздел 4.2). Исходя из специальной структуры транс­портной задачи (обратитесь к примеру 5.5.1, где показано, как транспортную задачу представить в виде стандартной задачи ЛП), двойственная ей задача будет записана в следующем виде.

т п

Максимизировать z = '^a_lu_j + '^b_jv_i

при ограничениях

и. + Vj < c_ti для всех i и u_i и v. — свободные переменные,

где

"а — предложение (объем грузов) пункта отправления i, Ь — спрос (заявка на грузы) пункта назначения

с — стоимость перевозки единицы груза из пункта отправления i в пункт назначения

u_t — двойственная переменная, соответствующая ограничению на предло­жение пункта отправления i,

v_j — двойственная переменная, соответствующая ограничению на спрос пункта назначения /.