최소비용 흐름 문제

최소비용 흐름 문제(MCFP)는 흐름 네트워크를 통해 일정량의 흐름을 보내는 가장 저렴한 방법을 찾기 위한 최적화 및 의사결정 문제다.이 문제의 일반적인 적용은 공장에서 도로망이 어느 정도 용량과 비용을 수반하는 창고로 가는 최적의 배송 경로를 찾는 것을 포함한다.최소비용 흐름 문제는 모든 흐름과 순환 문제 중에서 가장 근본적인 문제 중 하나인데, 그 밖의 대부분의 문제들은 최소비용 흐름 문제로 주조될 수 있고 또한 네트워크 심플렉스 알고리즘을 사용하여 효율적으로 해결할 수 있기 때문이다.

정의

GA흐름 네트워크는 통제된 그래프){G=(V,E)\displaystyle}V{\displaystylet\in V}∈ 각 가장자리(u, v)원천 꼭지점 s∈ V{\displaystyles\in V}, 싱크대 등 꼭지점 t, c(u, v)을 ∈ E{\displaystyle(u,v)\in E}용량을 가지고 있;0{\displaystyle c(u,v)>0}, 흐름 f(u, v)과(V, E). ≥ 0대부분의 최소 비용 흐름 알고리즘이 마이너스 비용으로 가장자리를 지원하는 $[\$$displaystyle f$$(u,v)\geq 0}$ 및 비용$$ $($에지$({\displaystyle u}$, v${\displaystyle }$) ${\displaystyle (u,v)}$을(를) 따라 이 흐름을 보내는 비용은 ${\displaystyle f}$ (${\displaystyle u}$ , ${\displaystyle v}$ ) ${\displaystyle \cdot }$ a (${\displaystyle u}$ ,${\displaystyle v}$ ${\displaystyle )}$ ${\displaystyle f(u,v)\cdot a(u,v)}$이다$.$ 문제는 $소스{\displaystyle }$ s ${\displaystystyle$ $s$$}$에서 전송되는$$$$ 양의 $}$을 필요로 한다$.$

문제의 정의는 모든 가장자리에 걸쳐 흐름의 총 비용을 최소화하는 것이다.

${\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}$

제약을 받고

용량 제약 조건:	${\displaystyle \,f(u,v)\leq c(u,v)}$
스큐 대칭:	${\displaystyle \,f(u,v)=-f(v,u)}$
흐름 보존:	${\displaystyle \,\sum _{w\in V}f(u,w)=0{\text{모든 }u\neq s,t}$
필요한 흐름:	${\displaystyle \,\sum _{w\in V}f(s,w)=d{\text{ 및 }}\sum _{w\in V}f(w,t)=d}$

기타 문제와의 관계

이 문제의 변동은 최대 유량이지만 최대 유량 솔루션 중 비용이 가장 낮은 유량을 찾는 것이다.이것은 최소 비용 최대 흐름 문제라고 불릴 수 있으며 최소 비용 최대 일치 항목을 찾는 데 유용하다.

일부 솔루션에서는 대신 최소 비용 최대 흐름을 찾는 것이 간단하다.그렇지 않으면 $d{\displaystyle }$ ${\displaystyle$ d$}$에서 바이너리 검색을 수행하여 최대 흐름을 찾을 수 있다$.$

관련 문제는 최소 비용 흐름 해결에 활용할 수 있는 최소 비용 순환 문제다.이는 모든 가장자리의 하한을 0으로 설정한 다음 용량 $c{\displaystyle (t}$, ${\displaystyle s}$)${\displaystyle }$= ${\displaystyle d}$ ${\displaystyle$ t$}$에서$$소스$$$$$s{\displaystyle }$ {\$displaystyle s}$까지 여분의 에지를 만들고, $용량{\displaystyle }$ c(${\displaystyle t}$ $,$${\displaystyle s)}$ = d , s = d ${\$$d$ $표시style$l$(t,$s) ${\displaystyle =}$ ${\displaystyle d}\},$ d$}$에서 총 흐름을 $강제{\displaystyle }$ 적용함으로써 달성된다$.$$isplaystyle s}$ ~ $t$ ${\displaystyle t}$도 $d{\displaystyle }$ ${\displaystyle d}$이$($가) 되도록 .

다음 문제는 최소 비용 흐름 문제의 특별한 경우(각 적용 가능한 절감액에 대한 간략한 스케치를 제공한다.^[1]

• 최단 경로 문제(단일 소스)최소 비용 흐름 문제에 대한 실현 가능한 솔루션이 지정된 소스 $s{\displaystyle }$ ${\displaystyle$ s$}$에서 지정된 싱크 $t{\displaystyle }$ ${\displaystyle t}($으)로$$ 흐름의 한 단위를 전송하도록 요구$.$ 모든 에지에는 무한 용량을 부여한다.
• 최대 흐름 문제.모든 노드는 제로 디맨드를 가지며, 에지 통과와 관련된 비용은 0이 되도록 한다.자, 현재 $싱크{\displaystyle }$ t$${\$displaystyle t$}에서$$$$ 현재 $소스{\displaystyle }$ t$${\$displaystyle s}$까지 새 에지${\displaystyle (}$${\displaystyle t}$ , ${\displaystyle s}$$)$를 도입하십시오$.$ 에지${\displaystyle (,}$ s${\displaystyle }$) ${\displaystyle(t,s})$를 통한 흐름 전송에 대한 단위 비용이${\displaystyle }$- 1 ${\displaystystyle -1}$및 허용${\displaystyle (,}$ ${\displaystyle t}$) ${\displaystysty$$)$과 동일하도록$$ 규정$(t,s)}$개의$$ 무한 확장 용량.(이 감소는 Circulation 문제에서도 언급된다.)
• 과제 문제.Suppose that each partite set in the bipartition has ${\displaystyle n}$ vertices, and denote the bipartition by ${\displaystyle (X,Y)}$. Give each ${\displaystyle x\in X}$ supply ${\displaystyle 1/n}$ and give each ${\displaystyle y\in Y}$ demand ${\displaystyle 1/n}$. Each edge는 단위 용량을 가져야 한다.

해결 방법

최소 비용 흐름 문제는 선형 함수를 최적화하고 모든 제약조건은 선형이기 때문에 선형 프로그래밍으로 해결할 수 있다.

그것과는 별도로, 많은 조합 알고리즘이 존재하며, 포괄적인 조사를 위해 참조한다. 그 중 일부는 최대 흐름 알고리즘의 일반화, 다른 일부는 완전히 다른 접근법을 사용한다.

잘 알려진 기본 알고리즘(이 알고리즘에는 다양한 변형이 있음):

• 사이클 취소: 일반적인 원시 방법.^[2]
• 커트 취소: 일반 이중 방식.^[3][4]
• 최소 평균 주기 취소: 강력한 다항식 알고리즘.^[5]
• 연속 최단 경로 및 용량 확장: Ford-Fulkerson 알고리즘의 일반화로 볼 수 있는 이중 방식.^[6]
• 비용 확장: 원시-이중 접근법으로서, 푸시-릴라벨 알고리즘의 일반화로 볼 수 있다.^[7]
• Network simplex 알고리즘: 선형 프로그래밍 simplex 메소드의 전문 버전.^[8]
• D에 의한 Out-of-kilter 알고리즘. 풀커슨 R.

적용

최소 중량 양당 일치

초당적 그래프 G = (A ∪ B, E)의 경우, 최소 비용이 드는 G에서 최대 카디널리티 일치를 찾는 것이 목표다.Let w: E → R은 E의 가장자리의 중량 함수가 된다.최소 중량 초당적 일치 문제 또는 할당 문제는 총 중량이 최소화된 M ⊆ E와 완벽하게 일치하는 것을 찾는 것이다.이 문제를 네트워크 흐름 문제로 축소하자는 취지다.

G′ = (V′ = A ∪ B, E′ = E)로 한다.E′에 있는 모든 가장자리의 용량을 1로 할당한다.소스 정점을 추가하여 A′의 모든 정점에 연결하고 싱크 정점 t를 추가하고 그룹 B′ 내부의 모든 정점을 이 정점에 연결한다.모든 새로운 가장자리의 용량은 1이고 그 비용은 0이다.G에 최소 비용 흐름이 있는 경우에만 G에 최소 중량 완벽한 초당적 매칭이 있음을 증명한다.^{[9][dead link]}

참고 항목

• 레몬(C++ 라이브러리)
• GNU 선형 프로그래밍 키트

참조

1. ^ Ravindra K. Ahuja; Thomas L. Magnanti & James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc. ISBN 978-0-13-617549-0.
2. ^ Morton Klein (1967). "A primal method for minimal cost flows with applications to the assignment and transportation problems". Management Science. 14 (3): 205–220. CiteSeerX 10.1.1.228.7696. doi:10.1287/mnsc.14.3.205.
3. ^ Refael Hassin (1983). "The minimum cost flow problem: A unifying approach to existing algorithms and a new tree search algorithm". Mathematical Programming. 25: 228–239. doi:10.1007/bf02591772.
4. ^ Thomas R. Ervolina & S. Thomas McCormick (1993). "Two strongly polynomial cut cancelling algorithms for minimum cost network flow". Discrete Applied Mathematics. 4: 133–165. doi:10.1016/0166-218x(93)90025-j.
5. ^ Andrew V. Goldberg & Robert E. Tarjan (1989). "Finding minimum-cost circulations by canceling negative cycles". Journal of the ACM. 36 (4): 873–886. doi:10.1145/76359.76368.
6. ^ Jack Edmonds & Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM. 19 (2): 248–264. doi:10.1145/321694.321699.
7. ^ Andrew V. Goldberg & Robert E. Tarjan (1990). "Finding minimum-cost circulations by successive approximation". Math. Oper. Res. 15 (3): 430–466. doi:10.1287/moor.15.3.430.
8. ^ James B. Orlin (1997). "A polynomial time primal network simplex algorithm for minimum cost flows". Mathematical Programming. 78 (2): 109–129. doi:10.1007/bf02614365. hdl:1721.1/2584.

외부 링크

• 여러 개의 최대 흐름과 최소 비용 순환 알고리즘이 있는 레몬 C++ 라이브러리
• 최소 비용 흐름과 최단 경로 알고리즘을 갖춘 MCFClass C++ 프로젝트 라이브러리