Graph::minCost
Вычисляет минимальный поток стоимости
Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.
Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразуют Notebook MuPAD в Live скрипты MATLAB.
Синтаксис
Graph::minCost(G)
Описание
Graph::minCost(G) вычисляет минимальный поток стоимости в G относительно мощностей ребра, веса ребра и весов вершины G.
Веса вершины интерпретированы как спрос и предложение. Вес ребра дает ограничения для потока на каждом ребре. Затраты ребра являются стоимостью для одного модульного потока по ребру.
Алгоритм вычисляет поток, если существует кто-либо, который является возможным и удовлетворительным, т.е. именно в области значений спроса и предложения, уважает мощности и который имеет минимальную стоимость. Для получения дополнительной информации см. Алгоритмы.
Примеры
Пример 1
Мы создаем График с пятью вершинами и семью ребрами. Одна из вершин является чистым источником (1), другой - чистый приемник (5). Никакие другие вершины не предоставляют или требуют любые товары, они только служат соединениями транспортировки:
V := [1, 2, 3, 4, 5]:
Vw := [25, 0, 0, 0, -25]:
edges := [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 5]]:
Ec := [7, 6, 5, 4, 2, 2, 1]:
Ew := [30, 20, 25, 10, 20, 25, 20]:
G1 := Graph(V, edges, EdgeCosts = Ec, EdgeWeights = Ew,
VertexWeights = Vw, Directed):
Graph::minCost(G1)
Все 25 модулей могли быть транспортированы от вершины 1 к вершине 5 для общей стоимости 220. Стоимость для каждого ребра может быть найдена в первой таблице, накопленные затраты во втором и последней таблице содержит двойные цены. Например, 6 модулей текут по ребру [1, 3] с тех пор 6 20 = 120 и 7 модульных потоков по ребру [1, 2] с тех пор 7 5 = 35.
Параметры
|
График |
Возвращаемые значения
Последовательность, состоя из трех таблиц и номера. Первая таблица держит сумму, текущую над ребрами, второе, накопленные затраты для каждого используемого ребра и номера являются суммой всех затрат ребра для потока. Последняя таблица содержит двойные цены на каждую вершину.
Алгоритмы
Реализованный алгоритм является релаксационным алгоритмом из-за Bertsekas (взятый из Bertsekas, “Линейная Сетевая Оптимизация”, Нажатие MIT, Кембридж (Масса.)-Лондон, 1991), который, как известно, является одним из самых быстрых алгоритмов на практике.
Минимальный поток стоимости пытается минимизировать стоимость определенного количества потока через график. А именно, минимальный поток стоимости минимизирует
удовлетворяющий
Если веса вершины s i действительно составляю в целом 0 затем Graph::minCost ошибки.
Если ограничения (1.1) и (1.2) не могут быть удовлетворены s i и c i, j, то Graph::minCost выдает ошибку.