График::

Вычисляет минимальный поток стоимости

Блокноты 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.

Параметры

G

График

Возвращаемые значения

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

Алгоритмы

Реализованный алгоритм является релаксационным алгоритмом из-за Bertsekas (взятый из Bertsekas, “Линейная Сетевая Оптимизация”, Нажатие MIT, Кембридж (Масса.)-Лондон, 1991), который, как известно, является одним из самых быстрых алгоритмов на практике.

Минимальный поток стоимости пытается минимизировать стоимость определенного количества потока через график. А именно, минимальный поток стоимости минимизирует

(i,j)Αaijxij

подвергающийся

{j|(i,j)Α}xij{j|(j,i)Α}xji=si,iΝ(1.1)bijxijcij,(i,j)Α,(1.2)где,Ν = вершины  графикаΑ = ребра  графикаaij= стоимость ребра  ребра (i, j)xij= минимальный поток через ребро (i, j)si =  вес вершины  вершины icij=  вес ребра  ребра (i, j).

Если веса вершины s i действительно составляю в целом 0 затем ошибки Graph::minCost.

Если ограничения (1.1) и (1.2) не могут быть удовлетворены s i и c i, j, то Graph::minCost выдает ошибку.