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

На рис. 6.9 показана построенная сеть. С помощью программы TORA находим кратчайший путь 1->3->5 (показан на рис. 6.9 жирными линиями). Это решение означает, что автомобили, приобретенные в 2001 году (узел 1), будут эксплуатиро­ваться 2 года, до 2003 года (узел 3), затем они будут заменены новыми, которые бу­дут эксплуатироваться до конца 2005 года. Общая стоимость замены составит 5400 + 7100= 12 500 долл.

Рис. 6.9. Задача замены оборудования как задача поиска кратчайшего пути

Глава 6. Сетевые модели

Пример 6.3.2. Самый надежный маршрут

М-р Разумник ежедневно ездит на работу на автомобиле. Закончив в свое время полный курс по теории исследования операций, он легко определил самый короткий путь от дома до работы. К сожалению, данный маршрут усиленно патрулируется нарядами по­лиции, и автомобиль Разумника часто останавливают за превышение скорости (как ему кажется, не обоснованно). Таким образом, самый короткий путь оказался не са­мым быстрым. Поэтому м-р Разумник планирует разработать новый маршрут, на ко­тором он имел бы самую высокую вероятность не быть остановленным полицией. Схема сети дорог, по которой м-р Разумник может добраться от дома до работы, показана на рис. 6.10. На этой же схеме приведены вероятности не быть останов­ленным для каждого сегмента сети дорог. Вероятность не быть остановленным на всем пути следования автомобиля Разумника равна произведению вероятностей не быть остановленным на каждом сегменте выбранного пути. Например, вероятность не быть остановленным на маршруте 1—»3—»5—»7 равна 0,9 х 0,3 х 0,25 = 0,0675. Таким образом, м-ру Разумнику необходимо решить задачу выбора маршрута, ко­торый максимизировал бы вероятность не быть остановленным.

Рис. 6.10. Сетевая модель

Эту задачу можно сформулировать как задачу нахождения кратчайшего пути, если вместо вероятностей использовать логарифмы вероятностей. Тогда произведение вероятностей преобразуется в сумму логарифмов вероятностей: если р_п=р₁х-р₂х... хр_к — вероятность не быть остановленным на маршруте 1—>2—>к, тогда

log p_lk = log р, + log р₂ +... + log р_к.

С точки зрения математики задача максимизации вероятности р_1к эквивалентна за­даче максимизации величины \ogp_lk. Поскольку \ogp_n<0, задача максимизации величины logp_u эквивалентна задаче минимизации -logp_u. Заменив на рис. 6.10 вероятности р_к на величины -\ogp_k, получаем сеть (рис. 6.11), к которой можно применить алгоритм определения кратчайшего пути.

Рис. 6.11. Сетевая модель для задачи поиска кратчайшего пути

6.3. Задача поиска кратчайшего пути

С помощью программы TORA находим кратчайший путь для полученной сети: 1-»3-»5-»7 с соответствующей "длиной" пути 1,1707 (=-logp₁₇). Таким образом, максимальная вероятность не быть остановленным равнар₁₇ = 0,0675.

Пример 6.3.3. Головоломка о трех бидонах

Восьмилитровый бидон заполнен некой жидкостью, а два бидона емкостью 5 и 3 литра пусты. Необходимо разделить 8 литров жидкости на две равные части, ис­пользуя только три имеющихся бидона. Какое минимальное количество перелива­ний из бидона в бидон надо сделать, чтобы достичь желаемого результата?

Вы, вероятно, уже нашли решение этой головоломки. Вместе с тем ее можно ре­шить как задачу о нахождении кратчайшего пути.

В этой сетевой модели каждый узел будет соответствовать объемам жидкости в 8-, 5- и 3-литровом бидонах. Начальным узлом будет (8, 0, 0), а конечным — (4, 4, 0). Новый узел получается из текущего при однократном переливании жидкости из одного бидона в другой.

На рис. 6.12 показаны различные маршруты, ведущие от начального узла (8, 0, 0) к конечному (4, 4, 0). Таким образом, наша головоломка сведена к задаче опреде­ления кратчайшего пути между узлами (8, 0, 0) и (4, 4, 0).

Рис. 6.12. Головоломка о трех бидонах как задача вычисления кратчайшего пути

Оптимальное решение, показанное в нижней части рис. 6.12, требует семи перели­ваний из бидона в бидон.

УПРАЖНЕНИЯ 6.3.1

1. Создайте заново модель замены оборудования из примера 6.3.1, предполагая, что автомобиль до замены должен эксплуатироваться не менее 2-х и не более 4-х лет. Стоимость замены автомобилей в 2001-2005 годах приведена в сле­дующей таблице.

Глава 6. Сетевые модели

	Стоимость замены (долл.) в зависимости от срока эксплуатации
Год покупки
			—
		—	—

2. На рис. 6.13 показана коммуникационная сеть между двумя приемно-передающими станциями 1 и 7. Возле каждой дуги этой сети указаны веро­ятности передачи сообщений без потерь по этим дугам. Необходимо найти маршрут от станции 1 к станции 7 с максимальной вероятностью успешной передачи сообщений. Сформулируйте эту задачу как поиск кратчайшего пу­ти и решите ее с помощью программы TORA.

Рис. 6.13. Сеть для задачи из упражнения 2

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

полнения различных операций.

Операция Время (секунды) Помещение ломтика хлеба в тостер 3 Поджаривание одной стороны ломтика 30 Переворачивание ломтика в тостере 1 Извлечение ломтика из тостера 3

6.3. Задача поиска кратчайшего пути

4. Планирование производства. Компания продает некую продукцию, спрос на которую в следующие 4 месяца составит 100, 140, 210 и 180 единиц соответ­ственно. Компания может удовлетворить любой помесячный спрос на про­дукцию и даже спрос на два и более месяцев вперед. В последнем случае не­обходимо платить 1,20 долл. за хранение единицы избыточно произведенной продукции в течение месяца. Покупная цена единицы продукции в следую­щие 4 месяца будет равна 15, 12, 10 и 14 долл. соответственно. Стоимость пе­реналадки оборудования для выполнения заказа составляет 200 долл. Ком­пания хочет разработать такой производственный план, чтобы минимизировать расходы на выполнение заказов, покупку продукции и ее хранение. Сформулируйте задачу как поиск кратчайшего пути и найдите ее оптимальное решение с помощью программы TORA.

5. Задача о рюкзаке. Путешественник, собираясь в путь, пытается поместить в свой рюкзак (объемом 5 кубических футов) наиболее необходимые в путе­шествии вещи. Есть три вещи, объемом соответственно 2, 3 и 4 кубических фута, необходимость в которых оценивается (по 100-балльной шкале) в 30, 50 и 70 баллов. Сформулируйте эту задачу как сетевую, где необходимо оп­ределить самый длинный путь, и найдите ее оптимальное решение. {Совет. Узел в этой сети можно определить как пару [i, и], где i — номер выбираемой вещи, a v — свободный объем рюкзака, оставшийся после выбора t-й вещи.)

6.3.2. Алгоритм определения кратчайшего пути

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

1. Алгоритм Дейкстры.

2. Алгоритм Флойда.

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

Алгоритм Дейкстры. В процессе выполнения этого алгоритма при переходе от £зла i к следующему узлу / используется специальная процедура пометки ребер. Обозначим через и, кратчайшее расстояние от исходного узла 1 до узла i, через d_tj — длину ребра (г, j). Тогда для узла / определим метку [u_jt i] следующим образом.

[_Uj, i] = [u_t + d_h, i],d_(/>0

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

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

Этап 0. Исходному узлу (узел 1) присваивается постоянная метка [0, —]. Полагаем i = 1.

Этап 1.

а) Вычисляются временные метки [и₁ + d_tj, i] для всех узлов у, которые можно достичь непосредственно из узла I и которые не имеют постоянных ме­

Глава 6. Сетевые модели

ток. Если узел уже имеет метку [и, k], полученную от другого узла k, и, если u_t + d_tj < u_jt тогда метка [u_y, k] заменяется на \u_l + d_tj, i],

b) Если все узлы имеют постоянные метки, процесс вычислений заканчива­ется. В противном случае выбирается метка [u_r, s] с наименьшим значени­ем расстояния и_г среди всех временных меток (если таких меток несколь­ко, то выбор произволен). Полагаем i = г и повторяем этап i.

Пример 6.3.4

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

	(2\_
	100/ \20, / \ 10/	jT) \50
	СЛ 30»Vi
	V У V У	У
	Рис. 6.14. Пример сети для алгоритма Дейкстры
Этап 0.	Назначаем узлу 1 постоянную метку [0, —].
Этап 1.	Из узла 1 можно достичь узлов 2 и 3. Вычисляем метки для этих узлов, в результате получаем следующую таблицу меток.
Узел	Метка	Статус метки
	[0,-]	Постоянная
	[0 + 100, 1] = [100, 1]	Временная
	[0 + 30, 1] = [30, 1]	Временная
	>• Среди узлов 2 и 3 узел 3 имеет	наименьшее значение расстояния
	(и3 = 30). Поэтому статус метки этого узла изменяется на " постоянная".
Этап 2.	Из узла 3 (последнего узла с постоянной меткой) можно попасть в узлы 4 и 5. Получаем следующий список узлов.
Узел	Метка	Статус метки
	[0,-]	Постоянная
	[100, 1]	Временная
	[30, 1]	Постоянная
	[30 + 10, 3] = [40, 3]	Временная
	[30 + 60, 3] = [90, 3]	Временная

6.3. Задача поиска кратчайшего пути

Временный статус метки [40, 3] узла 4 заменяется постоянным (u_t = 40).

Этап 3. Из узла 4 можно достичь узлов 2 и 5. После вычисления меток по­лучим следующий их список.

Узел Метка Статус метки

1 [0, —] Постоянная

2 [40 + 15, 4] = [55, 4] Временная

3 [30,1] Постоянная

4 [40,3] Постоянная

5 [90, 3] или [40 + 50, 4] = [90, 4] Временная

Временная метка [100, 1], полученная узлом 2 на втором этапе, из­менена на [55, 4]. Это указывает на то, что найден более короткий путь к этому узлу (проходящий через узел 4). На третьем этапе узел 5 получает две метки с одинаковым значением расстояния и_ь = 90.

Этап 4. Из узла 2 можно перейти только в узел 3, но он уже имеет постоянную метку, которую нельзя изменить. Поэтому на данном этапе получа­ем такой же список меток, как и на предыдущем, но с единственным изменением: метка узла 2 получает статус постоянной. С временной меткой остается только узел 5, но, так как из этого узла нельзя по­пасть ни в какой другой, процесс вычислений заканчивается.

Алгоритм позволяет проводить вычисления непосредственно на схеме сети, как показано на рис. 6.15.

ШЮтт^) [55,4]₍₃₎

() = шаг

Рис. 6.15. Применение алгоритма Дейкстры

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

(2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30, 1] -> (1). Таким образом, получаем путь 1 —> 3 —> 4 —> 2 общей длиной 55 миль.

Глава 6. Сетевые модели

Программа TORA также может применять алгоритм Дейкстры для решения се­тевых задач. Для этого в меню SOLVE/MODIFY выберите команду Solve problem^ Iterations¹^ Dijkstra's algoritm (Алгоритм Дейкстры). На рис. 6.16 показано выходное окно TORA с решением задачи из примера 6.3.4 (файл ch6ToraDijkstraEx6-3-4.txt).

netwofk MGDF1S

Рис. 6.16. Решение задачи из примера 6.3.4

УПРАЖНЕНИЯ 6.3.2

1. На рис. 6.17 показана транспортная сеть, соединяющая восемь городов, и расстояния между ними. Найдите кратчайшие маршруты между следую­щими городами.

a) Города 1 и 8.

b) Города 1 и 6.

c) Города 4 и 8.

d) Города 2 и 6.

2. Найдите кратчайшие пути между узлом 1 и всеми остальными узлами сети, представленной на рис. 6.18.

3. Найдите оптимальное решение задачи из упражнения 6.3.1.1.

4. Найдите оптимальное решение задачи из упражнения 6.3.1.2.

5. Найдите оптимальное решение задачи из упражнения 6.3.1.4.

6.3. Задача поиска кратчайшего пути

Рис. 6.17. Сеть для задачи из упражнения 1 6

Рис. 6.18. Сеть для задачи из упражнения 2

Алгоритм Флойда. Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с п стро­ками и п столбцами. Элемент (£, /) равен расстоянию d_tj от узла i к узлу /, кото­рое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.

Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис. 6.19). Если выполняется неравенство d_tj + d_jk < d_llt, то целесообразно заменить путь i -> k путем i->;->ft. Такая замена (далее ее будем условно называть треугольным оператором) выполняется система­тически в процессе выполнения алгоритма Флойда.

Рис. 6.19. Треугольный оператор Флойда Алгоритм Флойда требует выполнения следующих действий.

Этап 0. Определяем начальную матрицу расстояний D₀ и матрицу после­довательности узлов S₀. Диагональные элементы обеих матриц помечаются знаком "—", показывающим, что эти элементы в вы­числениях не участвуют. Полагаем k = l.

Глава 6. Сетевые модели

1 2... j... п

—	di2				dyn
	—		d2j
dn			da		dm
	dn2		dnj		—

1 2... j... л

So =

	—			j		n
				j		n
/'				j		n
л				j		—

Основной этап к. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам d_tj матрицы D_k__r Если выполняется неравенство

^dik + ^dkj < ^d,j> (i*k,j*kni*j), то делаем следующее:

a) создаем матрицу D_k путем замены в матрице элемента d_tj суммой d_lk + d_kj,

b) создаем матрицу S_k, меняя в матрице S₄_j элемент s, на h. Пола­гаем k — k + 1 и повторяем этап k.

Поясним действия, выполняемые на k-м этапе алгоритма, представив матрицу _D_k_j так, как она показана на рис. 6.20. На этом рисунке строка k и столбец k явля­ются ведущими. Стро-ка i— любая строка с номером от 1 до А - 1, а строка р — произвольная строка с номером от k + 1 до п. Аналогично столбец / представляет любой столбец с номером от 1 до k - 1, а столбец q — произвольный столбец с номе­ром от k + 1 до п. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратиках) меньше элементов, находящихся на пересечении столбца и строки (показаны в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется суммой расстояний, представленных ведущими элементами.

После реализации п этапов алгоритма определение по матрицам D_n и S_n крат­чайшего пути между узлами i и j выполняется по следующим правилам.

1. Расстояние между узлами i и j равно элементу d_tJ в матрице D_n.

2. Промежуточные узлы пути от узла i к узлу j определяем по матрице S_n. Пусть s₀ = k, тогда имеем путь i —> k —> /. Если далее s_lk = k и s_kj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные уз­лы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу

6.3. Задача поиска кратчайшего пути

Столбец j

Строка i

Ведущая строка

Строка р

Ведущий столбец

к

Столбец Q

Рис. 6.20. Реализация треугольного оператора

Пример 6.3.5

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

Рис. 6.21. Сеть для примера 6.3.5

ЭтапО. Начальные матрицы D₀ и S₀ строятся непосредственно по заданной схеме сети. Матрица D₀ симметрична, за исключением пары элементов и d₅₃, где d₆₃ = се (поскольку невозможен переход от узла 5 к узлу 3).

			Do 3						So 3
	—			СО	со
		—			со
		со	—						—
	СО									—
	со										—

Глава 6. Сетевые модели

Этап 1. В матрице D₀ выделены ведущие строка и столбец с номером k = 1.

Затемненными представлены элементы d₂₃ и d₃₂, единственные среди элементов матрицы D₀, значения которых можно улучшить с помощью треугольного оператора. Таким образом, чтобы на ос­нове матриц D₀ и S₀ получить матрицы D, и S_v выполняем сле­дующие действия.

1. Заменяем d₂₃ на d_2X + d_l3 = 3 + 10 = 13 и устанавливаем s₂₃ = 1.

2. Заменяем d₃₂ на d_3l + d_l2 = 10 + 3 = 13 и устанавливаем s₃₂ = 1. Матрицы D, и S, имеют следующий вид.

			D, 3						Si 3
				ОС			—
		—						—
			—						—
	.00			—						—
					—						—

Этап 2. Полагаем k = 2; в матрице D_; выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матриц D, и выделенным затенением. В результате получаем матрицы D₂ и S₂.

			D2 3						s2
	—				X		—
		—			X			—
		i:13v:	—						—
				—						—
					—						—

Этап 3. Полагаем k = 3; в матрице D₂ выделены ведущие строка и столбец.

Треугольный оператор применяется к затемненным элементам матриц D₂ и S₂. В результате получаем матрицы D₃ и S₃.

			D3 3						S3 3
	—						—
		—						—
			—						—
				—						—
			ой		—		. 1				—

6.3. Задача поиска кратчайшего пути

Этап 4. Полагаем k = 4, ведущие строка и столбец в матрице D₃ выделены. Получаем новые матрицы D_t и S₄.

			Da 3						s4
	—						—
		—						—
			—						—
				—						—
					—						—

Этап 5. Полагаем k — 5, ведущие строка и столбец в матрице Б₄ выделены.

Никаких действий на этом этапе не выполняем; вычисления за­кончены.

Конечные матрицы £>₄ и S_t содержат всю информацию, необходимую для определе­ния кратчайших путей между любыми двумя узлами сети. Например, кратчайшее расстояние между узлами 1 и 5 равно d_iS = 12.

Для определения соответствующих маршрутов напомним, что сегмент маршрута (i,j) состоит из ребра (/,_/) только тогда, когда s_tj = j. В противном случае узлы i и j связаны, по крайней мере, через один промежуточный узел. Например, поскольку s,₅ = 4 и s_iS = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1 -» 4 -» 5. Но так как д-,₄ ф 4, узлы 1 и 4 в определяемом пути не связаны одним реб­ром (но в исходной сети они могут быть связаны непосредственно). Далее следует определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем s_u — 2 и s_2i = 4, поэтому маршрут 1 -» 4 заменяем 1 -» 2 —> 4. Поскольку д-,₂ = 2 hj₂₄ = 4, других промежуточных узлов нет. Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 до узла 5:1-»2-»4-»5. Длина этого пути равна 12 милям.