Теория графов на английском.

[choucroute]

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

@темы: Теория графов

Comments

[Гость]

Попробуйте воспользоваться сервисами translate.google.com или translate.eu.

Текст для переводчиков

A steamship company has contracted to deliver perishable goods between several
different origin-destination pairs. Since the cargo is perishable, the customers have
specified precise dates (i.e., delivery dates) when the shipments must reach their
destinations. (The cargoes may not arrive early or late.) The steamship company
wants to determine the minimum number of ships needed to meet the delivery dates
of the shiploads.
To illustrate a modeling approach for this problem, we consider an example
with four shipments; each shipment is a full shipload with the characteristics shown
in Figure 6.8(a). For example, as specified by the first row in this figure, the company
must deliver one shipload available at port A and destined for port C on day 3. Figure
6.8(b) and (c) show the transit times for the shipments (including allowances for
loading and unloading the ships) and the return times (without a cargo) between the
ports.

...

We solve this problem by constructing a network shown in Figure 6.9(a). This
network contains a node for each shipment and an arc from node i to nodcj if it is
possible to deliver shipment j after completing shipment i; that is. the start time of
shipment j is no earlier than the delivery time of shipment i plus the travel time from
the destination of shipment i to the origin of shipment j. A directed path in this
network corresponds to a feasible sequence of shipment pickups and deliveries. The
tanker scheduling problem requires that we identify the minimum number of directed
paths that will contain each node in the network on exactly one path.
We can transform this problem to the framework of the maximum flow problem
as follows. We split each node i into two nodes i' and i" and add the arc (/', i"). Wc
set the lower bound on each arc (/", f), called the shipment arc, equal to 1 so that
at least one unit of flow passes through this arc. We also add a source node .v and
connect it to the origin of each shipment (to represent putting a ship into service),

...

and we add a sink node t and connect each destination node to it (to represent taking
a ship out of service). We set the capacity of each arc in the network to value 1.
Figure 6.9(b) shows the resulting network for our example. In this network, each
directed path from the source s to the sink t corresponds to a feasible schedule for
a single ship. As a result, a feasible flow of value v in this network decomposes into
schedules of v ships and our problem reduces to identifying a feasible flow of min-
imum value. We note that the zero flow is not feasible because shipment arcs have
unit lower bounds. We can solve this problem, which is known as the minimum
value problem, using any maximum flow algorithm (see Exercise 6.18).

[choucroute]

Текст я перевела, только мне это не помогло.

[Гость]

только мне это не помогло

Нельзя найти черную кошку в черной комнате, если ее там нет.

[All_ex]

Видимо стоимость считается одинаковой... хотя, может надо смотреть больший кусок текста...

[choucroute]

В задаче требуется минимизировать количество лодок использую алгоритм задачи о максимальном потоке. Единственное , что там сказано про числа которые даны : " 1) We set the lower bound on each arc (i', i"), called the shipment arc, equal to 1 so that at least one unit of flow passes through this arc. - Мы задаем нижнюю границу на каждой дуге (i', i"), названной дугой отправки, равную 1 так, что по крайней мере одна единица потока проходит через эту дугу. 2) We set the capacity of each arc in the network to value 1. - Пропускная способность равна 1".
Мне не понятно, будет ли нижняя граница на дуге (i', i"), равная 1, ценой дугового потока ? И переводчик мне тут никак не поможет.

[Гость]

Вероятно это - "транспортная логистика" и деньги не играют никакой роли при определении срока поставки.

[choucroute]

Очень часто в задачах о максимальном потоке при решении в exel указывается нулевая стоимость потока, но что тогда значит "нижняя граница на дуге (i', i"), равная 1", мне не совсем понятно.

[Гость]

Приведите перевод полностью, тогда будет проще обсуждать, что они делают с общим объемом груза, откуда появляется 1 и т.д.

[All_ex]

Обычно, в задаче о максимальном потоке ищут величину потока, а не его стоимость...

[Дилетант]

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

[choucroute]

Пароходство заключило контракт, чтобы доставить скоропортящиеся товары между несколькими
различными парами портов. Так как груз скоропортящийся, клиенты указали точные даты (т.е , даты поставки), когда грузы должны быть доставлены. (Раньше или позже груз быть доставлен не может) .Пароходство хочет решить эту проблему используя как можно меньше танкеров .
Чтобы проиллюстрировать подход к моделированию этой проблемы, мы рассматриваем пример
с четырьмя поставками; рисунок 6.8 (a). Например, в первой строке таблицы компания должен осуществить одну погрузку судов, доступную в порту A и предназначенную для порта C на день 3. Иллюстрация 6.8 (b) и (c) показывают время транзита для поставок (время на загрузку и разгрузку судна) и время возвращения (без груза) из порта в порт.

Мы решаем эту проблему, строя сеть, показанную в рисунке 6.9 (a). Это сеть содержит узел для каждой отгрузки и дуги от узла i к узлу j, если это возможный доставить партию j после завершения отгрузки i; то есть, время начала отгрузка j не ранее, чем время доставки отгрузки i плюс время в пути от места назначения отгрузки i к месту назначения отгрузки j. Искомый путь в этой сеть соответствует последовательности пикапов отгрузки и поставок. Проблема планирования танкера требует, чтобы мы идентифицировали минимальное число искомых
путей, которые будут содержать каждый узел в сети точно на одном пути.

Мы можем преобразовать эту проблему к структуре максимальной проблемы потока
следующим образом. Мы раскалываем каждый узел i на два узла i’ и i’’ добавляю дугу (i , i’’). Мы задаем нижнюю границу на каждой дуге (i', i"), названной дугой отправки, равную 1 так, что по крайней мере одна единица потока проходит через эту дугу. Мы также добавляем источник s и
соединяем его с узлами сети , и мы добавляем сток t и соединяем каждый узел назначения с ним. Пропускная способность равна 1. Рисунок 6.9 (b) показывает получающуюся сеть для нашего примера. В этой сети, каждом направленный путь из источника s к стоку t соответствует выполнимому графику для единственного судна. В результате допустимый поток величиной v в этой сети разлагается в графики для v танкеров и наша проблема идентифицируется как проблема о допустимой минимальной величине потока. Мы отмечаем, что нулевой поток не выполним, потому что дуги отгрузки имеют единичные более низкие границы. Мы можем решить эту проблему, которая известна как проблема о допустимой минимальной величине потока , используя алгоритм о максимальном потоке .

Перевод , конечно, корявый.
Такая модель дается в ключах к книге :

[choucroute]

Я поняла, что хотя бы одна единица потока должна пройти только по четырем дугам...

[Дилетант]

А, ну кажется, многое стало на свои места.
У вас есть многополюсная модель, вы ее приводите к модели Форда-Фалкерсона.
Задаете фиктивные источник и сток и каждую вершину преобразовываете в пару вершин, соединенную дугой. И вот на эти фиктивные дуги как раз накладываются указанные ограничения: по ним должен пройти поток, иначе эта преобразованная сеть не будет соответствовать исходной задаче.