7. Linear programming and reductions

선형 계획법과 그 환원에 대해 알아보자.

7.1. An introduction to linear programming

선형 계획법의 용례를 알아보자.

7.1.1. Example: profit maximization

이득 최대화는 어떻게 풀까?

Solving linear programs

선형 계획법으로 풀 수 있다.

More products

제한 조건이 많은 경우로도 확장할 수 있다.

7.1.2. Example: production planning

생산 계획도 선형 계획법으로 풀 수 있다.

7.1.3. Example: optimum bandwidth allocation

최적의 대역폭 할당도 선형 계획법으로 풀 수 있다.

7.1.4. Variants of linear programming

여러 변형이 존재한다.

7.2. Flows in networks

7.2.1. Shipping oil

기름 운송 문제는 어떻게 풀까?

7.2.2. Maximizing flow

최대 유량 문제로 풀 수 있다.

7.2.3. A closer look at the algorithm

빈 유량에서 증강 경로를 차츰 추가해나가면서 최대 유량 경로를 만들면 된다.

7.2.4. A certificate of optimality

해당 경로가 최대 유량인 것을 증명 가능하다.

Max-flow min-cut theorem

최대 유량은 최소 절단을 만든다.

7.2.5. Efficiency

복잡도는 O(VE^{2})이다.

7.3. Bipartite matching

이분 완전 매칭도 최대 유량 문제와 비슷하게 풀 수 있다.

7.4. Duality

선형 계획법에는 쌍대성 문제가 존재한다.

7.5. Zero-sum games

제로섬 게임도 선형 계획법으로 풀 수 있다.

7.6. The simplex algorithm

선형 계획법은 심플렉스 알고리즘으로 푼다.

7.6.1. Vertices and neighbors in n-dimensional space

n차원으로도 확장할 수 있다.

7.6.2. The algorithm

현재 정점이 최적인지를 판단하고, 어느 방향으로 이동할지 판단하고, 이를 수렴할 때까지 반복한다.

7.6.3. Loose ends

심플렉스 알고리즘에는 여러 경계 케이스가 존재한다. 시작 정점의 문제, 비결정 케이스, 비한계 케이스.

7.6.4. The running time of simplex

한 반복마다 O(mn)의 시간이 든다.

7.7. Postscript: circuit evaluation

논리 회로 평가도 심플렉스 문제로 풀 수 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중