29. Linear Programming

선형 계획법에 대해 알아보자.

A political problem

선형 계획법의 예로 정책에 대한 비용 배분 문제를 들 수 있다.

General linear program

실수 벡터 \mathbf{a}와 변수 벡터 \mathbf{x}에 대해 선형 함수 f(\mathbf{x}) = \mathbf{a} \cdot \mathbf{x}가 있을 때 f(\mathbf{x}) = b선형 방정식, f(\mathbf{x}) \geq b, f(\mathbf{x}) \leq b선형 부등식이라 한다. 통틀어 선형 조건식이라 한다. 선형 계획 문제는 유한 개의 선형 조건식에 대해 선형 함수를 최대화 (최대화 선형 계획법) 또는 최소화 (최소화 선형 계획법)하는 것이다.

An overview of linear programming

선형 계획법은 대개 표준형느슨형의 2가지 방법으로 표현한다. 선형 계획법 내의 선형 조건식들을 만족하는 해를 가용해라 한다. 이들이 만드는 영역을 가용 영역이라 하고 최대화하고자 하는 함수를 목적 함수라 한다. 목적 함수의 특정 지점에서의 값을 목적값이라 한다. n차원의 경우 가용 볼록 영역을 심플렉스라 한다. 심플렉스 알고리즘은 선형 계획 문제를 입력받아 최적해를 낸다.

Applications of linear programming

선형 계획법은 여러 적용례가 있다.

Algorithms for linear programming

선형 계획법을 푸는 알고리즘에는 타원체 알고리즘, 내부점 방법 등이 있다. 정수 조건을 추가한 정수 선형 계획법의 경우 일반적으론 다항 시간에 푸는 것이 불가능하다.

29.1. Standard and slack forms

표준형과 느슨형을 알아보자.

Standard form

표준형은 다음과 같다: \mathbf{a}_{i}^{T} \mathbf{x} \leq b_{i}, x_{j} \geq 0에 대해 \mathbf{c}^{T}\mathbf{x}를 최대화하라.

이는 목적 함수조건식에 맞춰 최적화하는 것이다. 아래쪽의 조건식은 비음수성 조건식이다. 모든 조건식을 만족시키는 해를 가용해라 한다. 가용해가 아니면 불가용해이다. 해는 목적값 \mathbf{c}^{T} \mathbf{x}을 갖는다. 이 목적값을 최적 목적값으로 만드는 해가 최적해이다. 가용 해가 없으면 선형 계획 문제는 불가용이라 하고 아니면 가용이라 한다. 가용해가 있으나 최적해의 값에 제한이 없을 때 이 선형 계획 문제를 무제한이라 한다.

Converting linear programs into standard form

등식 조건식이나 방향이 다른 부등식 조건식의 존재로 인해 표준형이 아닌 선형 계획법이 존재하더라도 동치인 표준형으로 다 바꿀 수 있다.

Converting linear programs into slack form

느슨 변수 s = b_{i} - \mathbf{a}_{j}^{T} \mathbf{x} \geq 0 의 형태로 느슨함을 측정하는 조건식을 표현할 수 있다. 이 느슨 변수를 선형 계획법에 도입하면 기초 변수가 되고 나머지는 비기초 변수가 된다. 이를 통해 느슨형을 얻을 수 있다.

29.2. Formulating problems as linear programs

여러 문제들을 선형 계획법으로 바꿀 수 있다.

Shortest paths

최단 경로 문제를 선형 계획법으로 바꿀 수 있다.

Maximum flow

최대 유량 문제를 선형 계획법으로 바꿀 수 있다.

Minimum-cost flow

최소 비용 유량 문제를 선형 계획법으로 바꿀 수 있다.

Multicommodity flow

여러 상품을 고려하는 다중 상품 유량 문제집계 흐름을 도입해 선형 계획법으로 바꿀 수 있다.

29.3. The simplex algorithm

심플렉스 알고리즘을 알아보자.

An example of the simplex algorithm

등식 조건식이 조건식의 기초 변수를 0으로 만들 경우 타이트하다고 한다. 비기초 변수가 기초 변수를 음수로 만들 경우 조건을 위반한다고 한다. 알고리즘을 고려할 때는 먼저 비기초 변수를 전부 0으로 하는 해인 기초해를 구성한다. 기초해가 가용해이면 기초가용해라 한다. 이후 가장 타이트한 조건식에 대해 비기초 변수 하나를 중심으로 잡아 최대한 늘린다. 이는 비기초 변수 (진입 변수)와 기초 변수 (탈출 변수)의 역할을 바꾼다.

Pivoting

비기초 변수를 중심으로 잡는 피보팅은 다음과 같다.

PIVOT(N, B, A, b, c, v, l, e)
// Compute the coefficients of the equation for new basic variable x_e
let A' be a new m x n matrix
b_e' = b_l / a_le
for each j ∈ N - {e}
    a_ej' = a_lj / a_le
a_el' = 1 / a_le
// Compute the coefficients of the remaining constraints
for each i ∈ B - {l}
    b_i' = b_i - a_ie b_e'
    for each j ∈ N - {e}
        a_ij' = a_ij - a_ie a_ej'
    a_il' = -a_ie a_el'
// Compute the objective function
v' = v + c_e b_e'
for each j ∈ N - {e}
    c_j' = c_j  - c_e a_ej'
c_l' = -c_e a_el'
// Compute new sets of basic and nonbasic variables
N' = N - {e} ∪ {l}
B' = B - {l} ∪ {e}
return (N', B', A', b', c', v')

이에 대해 다음이 성립한다.

Lemma. a_{le} \neq 0일 때 PIVOT(N, B, A, b, c, v, l, e)를 호출한다고 하자. 이것이 리턴한 값을 (N’, B’, A’, b’, c’, v’)라 하고 \bar{x}를 기초해라 하자. 그러면 다음이 성립한다.

  1. j \in N^{\prime}에 대해 \bar{x}_{j} = 0.
  2. \bar{x}_{e} = \frac{b_{l}}{a_{le}}.
  3. i \in B^{\prime} - \{e\}에 대해 \bar{x}_{i} = b_{i} - a_{ie}b_{e}^{\prime}.

The formal simplex algorithm

피보팅을 이용한 심플렉스 알고리즘은 다음과 같다.

SIMPLEX(A, b, c)
(N, B, A, b, c, v) = INITIALIZE-SIMPLEX(A, b, c)
let Δ be a new vector of length n
while some index j ∈ N has c_j > 0
    choose an index e ∈ N for which c_e > 0
    for each index i ∈ B
        if a_ie > 0
            Δ_i = b_i / a_ie
        else
            Δ_i = ∞
    choose an index l ∈ B that minimizes Δ_i
    if Δ_i == ∞
        return "unbounded"
    else
        (N, B, A, b, c, v) = PIVOT(N, B, A, b, c, v, l, e)
for i = 1 to n
    if i ∈ B
        x_i' = b_i
    else
        x_i' = 0
return (x_1', ..., x_n')

이 때 다음이 성립한다.

Lemma. 선형 계획법 (A, b, c)에 대해 INITIALIZE-SIMPLEX가 느슨형을 반환하고 이 때 기초해가 가용이라고 하자. 이 때 SIMPLEX가 해를 반환한다면 이 해는 가용해이다. SIMPLEX가 “unbounded”를 반환한다면 이 선형 계획법은 무한이다.

Termination

순환으로 인해 심플렉스 알고리즘이 무한히 돌 수 있다. 순환은 심플렉스 알고리즘이 무한히 도는 유일한 이유이다.

Lemma. I가 인덱스의 집합이고 j \in I에 대해 \alpha_{j}, \beta_{j}가 실수라 하자. x_{j}가 실변수, \gamma가 실수라 할 때 모든 x_{j}에 대해 \sum_{j \in I} \alpha_{j} x_{j} = \gamma + \sum_{j \in I} \beta_{j} x_{j}라면 모든 j \in I에 대해 \alpha_{j} = \beta_{j}이고 \gamma = 0이다.

Lemma. 표준형 선형계획법 (A, b, c)가 있을 때 기초 변수 집합 B에 대해 연관된 느슨형은 유일하게 결정된다.

Lemma. SIMPLEX가 \binom{n+m}{m} 번에 끝나지 않으면 순환한다.

순환은 변수를 택할 때 조건이 같으면 항상 최소 인덱스 변수를 택하는 블랜드의 규칙을 써서 막을 수 있다.

Lemma. SIMPLEX가 변수를 택할 때 조건이 같으면 항상 최소 인덱스 변수를 택한다면 알고리즘은 종료된다.

Lemma. INITIALIZE-SIMPLEX가 기초해가 가용한 느슨형을 반환한다면 SIMPLEX가 선형 계획법이 무한임을 알리거나 \binom{n+m}{m}번 안에 가용해를 반환하고 종료한다.

29.4. Duality

여기서는 선형 계획법 쌍대성에 대해 소개한다. 선형 계획법 문제에 대한 쌍대 문제는, 목적 함수를 최소화하되 최적값은 원본 선형 계획법 문제의 그것과 같은 문제이다. 이 때 원본 선형 계획법을 원시 계획이라 한다. 먼저 약한 쌍대성에 대해 소개한다.

Lemma. (Weak linear-programming duality) \bar{x}가 원시 선형 계획에 대한 임의의 가용해라 하고 \bar{y}가 쌍대 선형 계획에 대한 임의의 가용해라 하자. 그러면 다음이 성립한다: \mathbf{c}^{T}\bar{\mathbf{x}} \leq \mathbf{b}^{T} \bar{\mathbf{y}}.

Corollary. \bar{x}가 원시 선형 계획에 대한 임의의 가용해라 하고 \bar{y}가 쌍대 선형 계획에 대한 임의의 가용해라 하자. \mathbf{c}^{T}\bar{\mathbf{x}} = \mathbf{b}^{T} \bar{\mathbf{y}}라고 하면 \bar{\mathbf{x}}\bar{\mathbf{y}}은 원시 선형 계획과 쌍대 선형 계획 각각에 대한 최적해이다.

Theorem. (Linear-programming duality) SIMPLEX가 원시 선형 계획에 대해 해 \bar{\mathbf{x}}를 반환한다 하자. N, B가 최종 느슨형의 비기초/기초 변수들의 집합이라 할 때 \bar{\mathbf{y}} = -c_{n+i}^{\prime} if n + i \in N, 이외 0으로 잡으면 \bar{\mathbf{x}}는 원시 선형 계획의 최적해이고 \bar{\mathbf{y}}은 쌍대 선형 계획의 최적해이다. 또한 \mathbf{c}^{T}\bar{\mathbf{x}} = \mathbf{b}^{T} \bar{\mathbf{y}}이 성립한다.

29.5. The initial basic feasible solution

초기해는 어떻게 구할까?

Finding an initial solution

선형 계획법에 가용해가 존재하는지를 알아보려면 보조 선형 계획법을 도입한다.

Lemma. L이 표준형 선형 계획법이라 하자. x_{0}이 새 변수고 L_{aux}를 다음의 새 선형 계획법이라 하자: -x_{0}을 조건 \mathbf{a}_{i}^{T} \mathbf{x} - x_{0} \leq b_{i}, x_{j} \geq 0에 대해 최대화시킨다. 그러면 L이 가용하다는 것은 L_{aux}의 최적 목적값이 0일 것과 동치이다.

이제 INITIALIZE-SIMPLEX를 다음과 같이 쓸 수 있다.

INITIALIZE-SIMPLEX(A, b, c)
let k be the index of the minimum b_i
if b_k ≥ 0 // is the initial basic solution feasible?
    return ({1, 2, ..., n}, {n + 1, ..., n + m}, A, b, c, 0)
form L_aux by adding -x_0 to the left-hand-side of each constraint and setting the objective function to -x_0
let (N, B, A, b, c, v) be the resulting slack form for L_aux
l = n + k
// L_aux has n + 1 nonbasic variables and m basic variables
(N, B, A, b, c, v) = PIVOT(N, B, A, b, c, v, l, 0)
// The basic solution is now feasible for L_aux
iterate the while loop of lines 3-12 of SIMPLEX until an optimal solution to L_aux is found
if the optimal solution to L_aux sets x_0' to 0
    if x_0' is basic
        perform one (degenerate) pivot to make it nonbasic
    from the final slack form of L_aux, remove x_0 from the constraints and restore the original objective function of L, but replace each basic variable in this objective function by the right-hand side of its associated constraint
    return the modified final slack form
else
    return "infeasible"

이 때 다음이 성립한다.

Lemma. 선형 계획법 L에 가용해가 없다면 INITIAL-SIMPLEX는 “infeasible”을 반환한다. 이외엔 기초해가 가용한 느슨형을 반환한다.

Fundamental theorem of linear programming

Theorem. (Fundamental theorem of linear programming) 표준형의 선형 계획법 L은 유한 목적값을 최적해로 갖거나, 불가용하거나, 무한이다. 불가용하면 SIMPLEX는 “infeasible”을 반환한다. 무한이면 SIMPLEX는 “unbounded”을 반환한다. 이외에는 SIMPLEX는 유한한 최적 목적해를 반환한다.

답글 남기기

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

WordPress.com 로고

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

Google photo

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

Twitter 사진

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

Facebook 사진

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

%s에 연결하는 중