Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Глава 22. Потоки в сетях. о 22.137.Докажите, что все ребра остовного дерева, описанного в доказательстве свой­ства 22.29, включены в пути






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

о 22.138.Докажите, что остовное дерево, описанное в доказательстве свойства 22.29, соответствуют дереву кратчайших путей в исходной сети.

22.139.Предположим, что вы используете сетевой симплексный алгоритм для реше­
ния задачи, полученной в результате сведения задачи о кратчайших путях из единствен­
ного источника, как описано в доказательстве свойства 22.29. (i). Докажите, что этот
алгоритм никогда не использует аугментальный путь нулевой стоимости. (ii) Покажите,
что ребро, которое выходит из цикла, всегда есть родитель вершины назначения реб­
ра, добавляемого в цикл. (iii) Как следствие упражнения 22.138, сетевой симплексный
алгоритм не обязан поддерживать потоки в ребрах. Представьте полную реализацию,
использующую все преимущества, вытекающего из этого факта. Выбор нового древес­
ного ребра производится случайным образом.

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

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

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

о 22.143.Предположим, что стоимости ребер 0-2и 1-3на рис. 22.40 суть -1, а не 1. По­кажите, как найти максимальный поток минимальной стоимости путем преобразова­ния заданной сети в сеть с положительными стоимостями, а затем вычислить макси­мальный поток с минимальной стоимостью на новой сети.

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

о 22.145.Зависят ли реализации из разделов 22.5 и 22.6 существенным образом от того факта, что цены принимают неотрицательные значения? Если зависят, укажите, в ка­кой степени; если не зависят, покажите, какие настройки (если таковые имеются) требуется выполнить, чтобы заставить работать сеть с отрицательными стоимостями, либо объясните, почему такие настройки невозможны.



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

22.147.Покажите, к каким результатам приводит использование метода сведения за­
дач, описанного в тексте, на примере сведения транспортной сети, описанной в уп­
ражнении 22.112, к транспортной задаче.



Часть 5. Алгоритмы на графах


о 22.148.Покажите, что задача о максимальном потоке минимальной стоимости сво­дится к транспортной задаче со всего лишь V дополнительными вершинами и ребра­ми, если прибегнуть к построению, аналогичному тому, что применялось при доказа­тельстве свойства 22.16.

> 22.149.Реализуйте класс для решения транспортной задачи, основанный на простом сведении задачи о максимальном потоке минимальной стоимости, описанном в дока­зательстве свойства 22.30.

о 22.150.Разработайте реализацию класса для решения задачи вычисления потока ми­нимальной стоимости, в основу которого положено сведение к транспортной задаче, описанное в доказательстве свойства 22.31.

о 22.151.Разработайте реализацию класса для решения задачи вычисления потока ми­нимальной стоимости, в основу которого положено сведение к транспортной задаче, описанное в упражнении 22.148.

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



22.153.Дайте пример крупной динамической транспортной задачи.

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

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

22.156.Дайте пример крупной динамической задачи о назначениях.

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

22.158.Проведите эмпирические исследования по сравнению производительности двух
реализаций сетевого симплексного алгоритма, описанных в разделе 22.6, применитель­
но к решению вариантов задачи о назначениях (см. упражнение 22.155), с V верши­
нами и Е ребрами и разумно выбранным множеством значений V и Е.

22.159.Очевидно, что задача о почтальоне не имеет решения для сетей, которые не
принадлежат к числу сильно связных (почтальон может нанести визит только в вер­
шины, содержащиеся в сильной компоненте, в которой он начинает свой обход), од­
нако этот факт не оговаривается свойством 22.33. Что произойдет, если мы попыта­
емся применить сведение к сети, которая не является сильно связной?

22.160.Проведите эмпирические исследования для различных взвешенных графов (см.
упражнения 21.4—21.8) с тем, чтобы определить среднюю протяженность пути почта­
льона.

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

22.162.Дайте формулировку произвольной задачи о назначениях как LP-задачи.


Глава 22, Потоки в сетях



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

о 22.164. Найдите такую модель стоимостей для упражнения 22.18, чтобы ее решением был максимальный поток, требующий минимальное число дней.


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.014 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал