Я пытаюсь решить задачу с помощью линейного программирования.
Я использую симплексный алгоритм, упомянутый в CLRS.
Рассмотрим приведенный ниже пример:
<code>
--(1/1)--->|a|---(10/1)------>|d|----------->
| | ^ |
| |_(7/1)__ | |
|s| ________|_(12/1)__| |t|
| | |_______ |
| | | |
| | v |
--(1/1)--->|b|---(10/1)---->|c|--(1/1)----->
Вершины a и b - это лица.
Вершины c и d - задания.
Я смоделировал это как проблему минимального расхода с максимальным расходом.
Добавлены Source S и Sink t.
Все веса ребер установлены на 1.
Стоимость ребра от источника до вершины a и b установлена на 1.
Стоимость фронта от d, c до раковины установлена на 1.
Значения (a / b) на ребре представляют (стоимость / пропускная способность) для этого ребра.
Я использую W для представления стоимости фронта и C для емкости.
The linear program is:
Minimize,
Summation(W(uv).f(uv)) over all uv.</p>
<pre><code> Such that,
f(uv) >= 0 , for all (u,v) in E
f(uv) <= C(u,v) , C(u,v)=1 in this case, for all (u,v) in E
Flow conservation for each vertex except the source and the sink.
So Sum(f(uv)) = Sum(f(vu)), for all u,v
Flow demand of atleast 2, since we need to match 2 persons.
f(sa) + f(sb) = 2
The Standard Form is:
Maximize,
-(Summation(W(uv).f(uv)) over all uv)</p>
<pre><code> Such that,
f(uv) >= 0 , for all (u,v) in E
f(uv) <= C(u,v) , C(u,v)=1 in this case, for all (u,v) in E
Flow conservation for each vertex except the source and the sink.
So Sum(f(uv)) = Sum(f(vu)), for all u,v
Demand:
f(sa) + f(sb) = 2
<code>
Which reduces to
maximize (- { W(sa).f(sa) + W(sb).f(sb) + W(ad).f(ad) + W(ac).f(ac) + W(bd).f(bd) + W(bc).f(bc) + W(dt).f(dt) + W(ct).f(ct) } )
Подставляя x1 для sa, x2 для sb, x3 для рекламы, x4 для ac, x5 для bd, x6 для bc, x7 для dt, x8 для ct.
Наконец, мы получаем что-то вроде этого:
<code>
Maximize
-x1-x2-10(x3)-7(x4)-12(x5)-7(x6)-x7-x8 (objective function)
Given that (constraints)
Capacity constraints:
x{1-8} <= 1
Flow conversations:
x1 = x3+x4 --> ( x1-x3-x4 <=0 & -x1+x3+x4 <= 0)
x2 = x6+x5 --> ( x2-x6-x5 <=0 & -x2+x6+x5 <= 0)
x7 = x3+x5 --> ( x7-x3-x5 <=0 & -x7+x3+x5 <= 0)
x8 = x4+x6 --> ( x8-x4-x6 <=0 & -x8+x4+x6 <= 0)
Demand:
x1 + x2 =2 --> ( x1+x2 <=2 && -x1-x2 <=2)
Согласно CLRS,
Первая часть симплекса состоит в том, чтобы получить начальную слабую форму с выполнимым решением, используя метод INITIALISE-SIMPLEX .
Этот метод проверяет, есть ли отрицательные значения в правой части неравенств в ограничениях.
Если нет, он возвращает текущую настройку в качестве начальной формы для основного алгоритма.
В основном алгоритме первым шагом является выбор неосновной переменной, коэффициент которой неотрицателен в целевой функции.
Но в этом случае все переменные в целевой функции имеют отрицательный коэффициент (поскольку мы умножили исходную функцию obj для преобразования минимизации в форму максимизации).
То есть симплекс будет оканчиваться на 0 как значения потока для всех ребер?
Я поставил вышеупомянутую проблему "linear_solver в библиотеке Google OR-Tools".
И он возвращает правильный результат как 21 и x3 = 1 & x4 = 0 & x5 = 0 & x6 = 1
Так что я думаю, что мои уравнения верны.
CLRS не обрабатывает этот случай, или я что-то упустил?