네트워크 심플렉스 알고리즘

수학적 최적화에서 네트워크 심플렉스 알고리즘은 심플렉스 알고리즘의 그래프 이론적 전문화다.알고리즘은 일반적으로 최소비용 흐름 문제의 관점에서 공식화된다.네트워크 심플렉스 방법은 실제로 매우 잘 작동하며, 일반적으로 같은 차원의 일반 선형 프로그램에 적용되는 심플렉스 방법보다 200~300배 빠르다.^{[citation needed]}

역사

오랫동안 효율적 네트워크 심플렉스 알고리즘의 존재는 효율적인 연습 버전을 이용할 수 있었음에도 불구하고 복잡성 이론의 주요한 개방적 문제들 중 하나였다.1995년에 Orlin은 $O{\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ E ${\displaystyle \log (}$ (${\displaystyle V}$ C${\displaystyle }$) ${\displaystyle$ O$(V^{2$}E$\log(VC))}$의 런타임으로 첫 번째 다항식 알고리즘을 제공했다. $여기$서 C ${\displaystyle C}$은 모든 에지의 최대 비용이다.^[1]이후 Tarjan은 1997년에 동적 트리를 사용하여$$ 이를 $O{\displaystyle (V}$ E ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$ V ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$(${\displaystyle V}$ C${\displaystyle ))}$ ${\displaystyle O(VE\log$V\$log(VC))}($으)^[2]로 개선했다.동일한 문제에 대한 강력한 다항식 이중 네트워크 심플렉스 알고리즘이 있지만, 그래프의 에지와 정점 수에 대한 의존도가 더 높은 것은 오래 전부터 알려져 왔다.^[3]

개요

network simplex 방법은 경계변수 primal simplex 알고리즘의 적응이다.기본은 변수가 호로 표현되는 기반 네트워크의 뿌리 스패닝 트리와 노드 전위별로 심플렉스 승수(simplix multiers)로 표현된다.각 반복에서 입력 변수는 듀얼 멀티플라이어(노드 잠재력)에 기초하여 일부 가격 전략에 의해 선택되며, 트리의 호와 함께 사이클을 형성한다.왼쪽 변수는 최소 증가 흐름을 갖는 주기의 호입니다.호를 떠나기 위해 들어가는 대체와 트리의 재구성을 피벗이라고 한다.비기초 호가 진입할 수 있는 상태로 남아 있지 않은 경우 최적의 해법에 도달한 것이다.

적용들

네트워크 심플렉스 알고리즘은 다음을 포함한 많은 실제적인 문제를 해결하기 위해 사용될 수 있다.^[4]

• 환적 문제
• 히치콕 교통 문제
• 할당 문제
• 부분적으로 정렬된 세트의 체인 및 부동액
• 고유대리인제도
• 초당적 그래프의 커버 및 일치
• 케이터러 문제

참조

외부 링크

• 네트워크 문제 해결 섹션 14, p B-113은 실행 예시를 보여준다.