Аннотация: Симплекс-алгоритм — классический алгоритм решения задач линейного программирования (ЛП).Самым трудоемким модулем в симплекс-алгоритме является алгоритм вычисления обратной матрицы. Сетевой симплекс-алгоритм — это специальная версия симплекс-алгоритма, которая использует базовые остовные деревья для более эффективного решения задач линейного программирования с чистой сетевой формой.
Эта статья опубликована в сообществе HUAWEI CLOUD.Введение в симплексные алгоритмы в сетях, оригинальный автор: Юн Сяофань.
[Предисловие] Симплекс-алгоритм — классический алгоритм решения задач линейного программирования (ЛП).Самым трудоемким модулем в симплекс-алгоритме является алгоритм вычисления обратной матрицы. Сетевой симплекс-алгоритм — это специальная версия симплекс-алгоритма, которая использует базовые остовные деревья для более эффективного решения задач линейного программирования с чистой сетевой формой. Такая задача ЛП может быть смоделирована формулировкой на ориентированном графе как задача потока с минимальной стоимостью.
Сетевой симплекс относится к проблеме LP в форме:
где каждый столбец содержит только 1 и -1, а все остальные коэффициенты равны 0.
Ниже приведен пример:
Эту задачу можно рассматривать как графическую форму задачи о потоке с минимальными затратами.
Граф G=(V, E), вершина V представляет строку (ограничение), ребро E представляет столбец (переменную), для столбца в матрице A i-я строка имеет 1, а k-я строка имеет - 1, что указывает на то, что граф G An ребро (i, k) в .
Для приведенного выше примера это может быть представлено следующим рисунком:
Задача сетевого потока удовлетворяет условиям Хоффмана и Гейла, поэтому гарантируется целочисленное решение.
[Матрица ассоциации]:
Для графа G=(V,E) корреляционная матрица A может быть выражена как:
Матрица корреляции в приведенном выше примере может быть выражена как:
【дорожка】:
Связный граф: Любые две вершины в графе имеют путь.
Связующее дерево: подграф T графа G, содержащий все вершины графа G.
Свойства: rank(A)=n-1, n — количество узлов.
Мы добавляем переменную w и столбец в A
Любое значение в r∈{1,2...n}, w=0, тогда модель LP:
Среди них r называется корневой вершиной, w называется корневым ребром (никуда не уходящим)
Для приведенного выше примера, если выбран корневой узел r=2
A — ассоциативная матрица графа G, а T — остов графа G, тогда базис (A│e_r ) B=e_r∪{a_e |e∈T}
[Простой алгоритм]:
Мы можем выполнить предварительный обход от корневого узла, чтобы получить y2=0, y1-y2=1, y1-y3=10, то есть пройти по основанию 5, основанию 1, основанию 4 по очереди. p,Tree S){//p — корневой узел дерева S Vertex v=root(S);if(v==r) y[r]=c[w];else if ((p,v)∈ E y[v]=y[p]-c[(p,v)];иначе y[v]=y[p]+c[(v,p)];решить(v,S.left()) ;решить(v ,S.right());}
использованная литература:Woohoo. В это время. UPC. Quota/~ And OD Day/Web…
Нажмите «Подписаться», чтобы впервые узнать о новых технологиях HUAWEI CLOUD~