3. Simplex method(단체법)
1. Simplex method이란?
Simplex method(단체법)은 LP의 실행 가능한 영역의 극단점(extreme point) 또는 꼭지점(vertex point)을 탐색하여 최적의 극단점을 찾는 방법입니다. 그러나 실제로 단체법은 대부분의 경우 최적의 극단점을 찾기 전에 모든 가능한 극단점을 탐색할 필요가 없습니다(즉, 단체법은 무차별 대입법이 아님에 주의).
2. Simplex method의 전략
초기 기본 실행 가능한 해가 주어지면 단체법은 기본 실행 가능한 해가 최적인지 여부를 판별합니다. 만약 최적이면 이 방법은 종료되고, 그렇지 않으면 목적함수 값이 이전 값보다 좋거나 나쁘지 않은 다른 기본 실행 가능 해가 생성되고, 최적성이 검사되는 식으로 최적의 기본 실행 가능 해가 얻어질 때까지 반복됨. 만약 LP가 무한하면 단체법은 이를 감지하고 목적함수가 무한한 퇴화(Degeneracy) 방향으로 돌아갈 수 있습니다. 단체법은 1장에서 살펴본 LP의 표준 형태가 요구됩니다.
2.1. Simplex method의 개략적인 순서
- Step 0: 초기 기본 실행 가능 해 \({x^{(0)}}\)를 생성함. \(k = 0\)으로 하고 1단계로 넘어감.
- Step 1: \({x^{(k)}}\)의 최적성 검사 단계. \({x^{(k)}}\)가 최적이면 중지하고 최적 해로 \({x^{(k)}}\)를 반환하고, 그렇지 않으면 2단계로 넘어감.
- Step 2: LP가 무계(unbounded)인지 확인함. 그렇다면 중지하고, 그렇지 않다면 3단계로 이동함.
- Step 3: 다른 기본 실행 가능 해 \({x^{(k + 1)}}\)을 생성하여 \({c^T}{x^{(k + 1)}} \le {c^T}{x^{(k)}}\)가 되도록 함. 그런 뒤 \(k=k + 1\)로 하고 1단계로 이동함.
2.2. Simplex method의 핵심 아이디어
- ① LP 문제를 표준 형태로 변환 후, 기본 변수(Basic variables)와 초기 극단점 설정.
- ② 목적 함수 값이 더 개선되는 방향으로 이동: 현재 위치한 극단점에서 인접한 다른 극단점으로 이동할 방향을 결정하기 위해 기둥 선택(Pivot selection)을 수행함.
- ③ 최적해 도달 여부를 확인: 더 이상 목적함수 값을 개선할 수 없는 경우, 현재 위치한 극단점이 최적해임. 만약 이동할 수 있는 방향이 없다면 문제는 퇴화(Degeneracy) 또는 무한해(Unbounded solution)일 수 있음.
3. Simplex method의 예시
3.1. 표준형태로 변환
maximize \(z = 3{x_1} + 5{x_2}\)
subject to \({x_1} + 2{x_2} \le 4\)
\(3{x_1} + 2{x_2} \le 6\)
\({x_1},{x_2} \ge 0\)
위 문제를 등식 제약 조건으로 변환하기 위해 여유 변수(Slack varialbes) \({s_1}\), \({s_2}\) 를 추가하면:
\[\begin{gathered}
{x_1} + 2{x_2} + {s_1} = 4 \hfill \\
3{x_1} + 2{x_2} + {s_2} = 6 \hfill \\
\end{gathered} \]
이제, 변환된 문제는 다음과 같음:
maximize \(z = 3{x_1} + 5{x_2}\)
subject to \({x_1} + 2{x_2} + {s_1} = 4\)
\(3{x_1} + 2{x_2} + {s_2} = 6\)
\({x_1},{x_2},{s_1},{s_2} \ge 0\)
초기 기본 해 설정: \({x_1} = 0,{x_2} = 0,{s_1} = 4,{s_2} = 6\)
3.2. Simplex 표 구성
| 기본 변수 | \({x_1}\) | \({x_2}\) | \({s_1}\) | \({s_2}\) | 우변(\(b\)) |
| \({s_1}\) | 1 | 2 | 1 | 0 | 4 |
| \({s_2}\) | 3 | 2 | 0 | 1 | 6 |
| \({z}\) | -3 | -5 | 0 | 0 | 0 |
목적 함수를 최대화하기 위해 가장 작은 값을 가진 \({z}\) 계수를 찾은 뒤 이에 해당하는 변수를 진입 변수(Entering variable)로 선정합니다.
여기서는 \({x_2}\)의 계수가 -5로 가장 작으므로, \({x_2}\)가 진입 변수입니다.
3.3. Pivot 선택 및 행 연산
들어오는 변수 \({x_2}\)에 대해 제약 조건을 만족하면서 최소한으로 증가할 수 있는 변수를 찾습니다.
이때, 우변(\(b\)) 값을 해당 열의 값으로 나눈 비율이 최소인 행이 탈락 변수(Leaving variable)가 됩니다.
| 기본 변수 | \({x_1}\) | \({x_2}\) | \({s_1}\) | \({s_2}\) | 우변(\(b\)) | \(b/a\) |
| \({s_1}\) | 1 | 2 (pivot) | 1 | 0 | 4 | \(4/2 = 2\) |
| \({s_2}\) | 3 | 2 | 0 | 1 | 6 | \(6/2 = 3\) |
여기서는 \({s_1}\)의 비율(2)이 더 작으므로, \({s_1}\)이 탈락 변수입니다.
3.4. Pivoting 수행(행 연산)
앞에서 들어오는 변수는 \({x_2}\)이고 나가는 변수는 \({s_1}\)인 것을 알고 있습니다.
피봇 요소는 \({a_{12}} = 2\), 즉 1행의 \({x_2}\)에 해당하는 값입니다.
피봇 행을 피봇 요소로 나누어 1로 변환하면:
새로운 행 \({s_{1,new}} = \frac{1}{2} \times \left( {1,2,1,0,4} \right)\)
따라서 표는 다음과 업데이트 됩니다:
| 기본 변수 | \({x_1}\) | \({x_2}\) | \({s_1}\) | \({s_2}\) | 우변(\(b\)) |
| \({x_2}\) | 0.5 | 1 | 0.5 | 0 | 2 |
| \({s_2}\) | 3 | 2 | 0 | 1 | 6 |
| \({z}\) | -3 | -5 | 0 | 0 | 0 |
이제 첫 번째 행을 사용하여 다른 행을 수정하여 \({x_2}\) 열의 값을 모두 0으로 만듭니다.
새로운 \({s_2}\)행 계산: \({s_{2,new}} = \left( {3,2,0,1,6} \right) - 2 \times \left( {0.5,1,0.5,0,2} \right) = \left( {2,0, - 1,1,2} \right)\)
새로운 \({z}\)행 계산: \({z_{new}} = \left( {-3,-5,0,0,0} \right) + 5 \times \left( {0.5,1,0.5,0,2} \right) = \left( {-0.5,0, 2.5,0,10} \right)\)
따라서 표는 다음과 업데이트 됩니다:
| 기본 변수 | \({x_1}\) | \({x_2}\) | \({s_1}\) | \({s_2}\) | 우변(\(b\)) |
| \({x_2}\) | 0.5 | 1 | 0.5 | 0 | 2 |
| \({s_2}\) | 2 | 0 | -1 | 1 | 2 |
| \({z}\) | -0.5 | 0 | 2.5 | 0 | 10 |
3.5. 최적해 확인
목적함수 계수 행(\({z}\))에 모든 값이 0 이상이 아니므로 다시 3.3~3.4과정을 반복해야 합니다.
여기서는 \({x_1}\)의 계수가 -0.5로 가장 작으므로, 진입 변수는 \({x_1}\)입니다.
| 기본 변수 | \({x_1}\) | \({x_2}\) | \({s_1}\) | \({s_2}\) | 우변(\(b\)) | \(b/a\) |
| \({x_2}\) | 0.5 | 1 | 0.5 | 0 | 2 | \(2/0.5 = 4\) |
| \({s_2}\) | 2 (pivot) | 0 | -1 | 1 | 2 | \(2/2 = 1\) |
| \({z}\) | -0.5 | 0 | 2.5 | 0 | 10 |
탈락 변수는 \({s_2}\)인 것을 알 수 있습니다.
피봇 행을 피봇 요소로 나누어 1로 변환하면:
| 기본 변수 | \({x_1}\) | \({x_2}\) | \({s_1}\) | \({s_2}\) | 우변(\(b\)) |
| \({x_2}\) | 0.5 | 1 | 0.5 | 0 | 2 |
| \({x_1}\) | 1 | 0 | -0.5 | -0.5 | 1 |
| \({z}\) | -0.5 | 0 | 2.5 | 0 | 10 |
피봇 요소에 해당하는 열을 피봇을 제외하고 모두 0으로 만들면:
| 기본 변수 | \({x_1}\) | \({x_2}\) | \({s_1}\) | \({s_2}\) | 우변(\(b\)) |
| \({x_2}\) | 0 | 1 | 0.75 | 0.25 | 1.5 |
| \({x_1}\) | 1 | 0 | -0.5 | -0.5 | 1 |
| \({z}\) | 0 | 0 | 2.25 | -0.25 | 10.5 |
목적함수 계수 행(\({z}\))에 모든 값이 0 이상이므로 최적해에 도달하였음을 알 수 있음.
따라서 최적해는 \({x_1} = 1,\,{x_2} = 1.5,\,{z_{\max }} = 10.5\)
4. Simplex 방법의 중요한 포인트
- 진입 변수 선택 시 최소의 목적함수 계수를 선택한 이유? ⇒ 빠르게 해를 개선하기 위하여
- 탈락 변수 선택 시 최소의 비율을 선택한 이유? ⇒ 가능 해를 유지하기 위하여(우변 상수가 음이 되면 비가능해가 됨)
- Pivoting의 의미는? ⇒ 또다른 Extreme point(극단점)또는 Vertex point(꼭지점)을 탐색(즉, 기저해를 탐색)