Simplex Method (part 5)
OR
학부 정리
Overview
- 심플렉스 방법의 기하학적·대수적 원리, 행렬형 알고리즘, 그리고 그 실용적 응용(민감도 분석 등)을 체계적으로 설명
- 심플렉스 방법은 선형계획 문제에서 최적해를 꼭짓점 가능해(CPF)에서 찾으며, 행렬 연산을 통해 컴퓨터로 효율적으로 구현할 수 있다.
Simplex 방법의 기초
꼭짓점 가능해와 제약식 경계
- 선형계획 문제의 해는 가능해 영역(feasible region)의 경계에 존재한다.
- 이 제약식들을 등호(=)로 바꾼 제약식 경계식을 만들 수 있다.
- 함수 제약식
- ≤: slack variable
- =: artificial variable
- ≥: surplus variable, artificial variable
- 비음 제약식
- non-restricted: \(x_i = x_i^{+} - x_i^{-}\)
- ≤ 0: \(x_i = -x_i^{+}\)
- 함수 제약식
- 이 경계식들은 2차원에서는 선, 3차원에서는 평면, n차원에서는 초평면(hyperplane)을 형성한다.
꼭짓점 가능해의 세 가지 주요 속성
- 최적해의 위치
- 최적해가 유일하면, 그것은 꼭짓점 가능해이다.
- 최적해가 여러 개라면, 그 중 적어도 두 개는 인접 꼭짓점 가능해이다.
- 즉, 최적해는 항상 꼭짓점 가능해(혹은 그 선분)에 존재한다.
- 유한성
- 꼭짓점 가능해의 개수는 유한합니다.
- m+n개의 제약식 중 n개를 선택하는 조합의 수는 유한하므로, 이론적으로 모든 꼭짓점 가능해를 열거해 비교할 수도 있습니다. 하지만 실제로는 심플렉스 방법이 훨씬 적은 수만 탐색한다.
- 최적성의 충분조건
- 인접 꼭짓점 중 더 좋은 해가 없으면, 현재 해가 최적해임이 보장된다.
심플렉스 방법의 핵심 알고리즘 구조
심플렉스 방법은 다음과 같은 반복 구조를 가진다
- 초기 꼭짓점 가능해(기저해) 선택
- 인접 꼭짓점으로 이동(목적함수 값이 개선되는 방향)
- 더 이상 개선이 불가능하면 종료, 그 해가 최적해임을 보장
행렬형의 Simplex
행렬형 심플렉스 방법의 기본 구조
표준형 선형계획 문제를 다음과 같이 쓸 수 있다.
\[ \begin{aligned} \text{Maximize} \quad &Z=c^Tx \\ \text{Subject to} \quad &Ax=b, x≥0 \\ \end{aligned} \]
- 여기서 A는 m×n 행렬, x는 n차원 변수 벡터, b는 m차원 상수 벡터, c는 n차원 계수 벡터이다.
- 여유변수(slack variable)등을 도입해 모든 제약식을 등식으로 바꾼다.
행렬 연산을 활용한 반복 과정
- (제일 처음 단계의 경우 3, 4단계 먼저 진행)
- 진입기저변수(Entering Variable) 선택
- 탈락기저변수(Leaving Variable) 선택
- 최소비율법(minimum ratio test) 사용
- 새로운 기저 가능해 결정
- 기저변수 식별
- 기저행렬(Basic Matrix, B): m개의 기저변수에 대해 m×m 행렬 \(B\)와 \(B^{-1}\)를 만든다. 1
- 기저해(Basic Solution) 계산: \(x_B=B^{-1}b\)
- 목적함수 값 계산: \(Z=c_B^TB^{−1}b\)
- 최적화 검사
- 비기저변수의 계수(감소계수, reduced cost)를 계산
- 계산식: \(c_B^TB^{−1}a_n - c_n\)
- slack 변수: \(c_B^TB^{-1}\)
- 최적일 경우 종료
- 비기저변수의 계수(감소계수, reduced cost)를 계산