1. 선형 계획법(LP)이란?
LP는 선형적인 수학적 모델(함수)을 사용하여 최적화(최대화 or 최소화) 문제를 해결하는 기법입니다.
LP는 주어진 제약 조건(Constraints) 하에서 목적 함수(Objective function)를 최적화하는 것을 목표로 합니다.
응용분야로는 경제학, 경영학, 공학, 물류 등 다양한 분야에 활용되고 있습니다.
2. 선형 계획법의 기본 요소
- 의사결정 변수(Decision Variables): 최적화할 대상이 되는 변수들.
- 목적 함수(Objective Function): 최대화 또는 최소화하려는 함수.
- 제약 조건(Constraints): 문제 해결 시 만족해야 하는 조건이며, 등식 또는 부등식으로 표현됨.
- 비음수 변수 조건(Non-Negative Variable): 의사결정 변수는 일반적으로 0이상이어야 함.(만약 음수인 경우에는 적절한 변형을 통해 양수화를 시킴)
3. 선형 계획법의 일반적인 수식 표현
3.1 기본형 또는 표준형(Standard form)
maximize or minimize \({c_1}{x_1} + {c_2}{x_2} + \cdots + {c_n}{x_n}\)
subject to \({{a_{11}}{x_1} + {a_{12}}{x_2} + \cdots + {a_{1n}}{x_n} = {b_1}}\)
\({{a_{21}}{x_1} + {a_{21}}{x_2} + \cdots + {a_{2n}}{x_n} = {b_2}}\)
\(\vdots\)
\({a_{m1}}{x_1} + {a_{m1}}{x_2} + \cdots + {a_{mn}}{x_n} = {b_m}\)
\({x_i} \ge 0,\,i = 1,2, \cdots ,n\)
여기서, \({x_i}\)는 의사결정 변수, \({c_i}\)는 목적 함수의 계수, \({a_{ij}}\)는 제약조건 계수, \({b_i}\)는 제한 값입니다.
3.2 정규형(Normal form): 최대화
maximize \({c_1}{x_1} + {c_2}{x_2} + \cdots + {c_n}{x_n}\)
subject to \({{a_{11}}{x_1} + {a_{12}}{x_2} + \cdots + {a_{1n}}{x_n} \le {b_1}}\)
\({{a_{21}}{x_1} + {a_{21}}{x_2} + \cdots + {a_{2n}}{x_n} \le {b_2}}\)
\(\vdots\)
\({a_{m1}}{x_1} + {a_{m1}}{x_2} + \cdots + {a_{mn}}{x_n} \le {b_m}\)
\({x_i} \ge 0,\,i = 1,2, \cdots ,n\)
여기서, \({x_i}\)는 의사결정 변수, \({c_i}\)는 목적 함수의 계수, \({a_{ij}}\)는 제약조건 계수, \({b_i}\)는 제한 값입니다.
3.3 정규형(Normal form): 최소화
minimize \({c_1}{x_1} + {c_2}{x_2} + \cdots + {c_n}{x_n}\)
subject to \({{a_{11}}{x_1} + {a_{12}}{x_2} + \cdots + {a_{1n}}{x_n} \ge {b_1}}\)
\({{a_{21}}{x_1} + {a_{21}}{x_2} + \cdots + {a_{2n}}{x_n} \ge {b_2}}\)
\(\vdots\)
\({a_{m1}}{x_1} + {a_{m1}}{x_2} + \cdots + {a_{mn}}{x_n} \ge {b_m}\)
\({x_i} \ge 0,\,i = 1,2, \cdots ,n\)
*참고로 최대화 또는 최소화 문제의 제약식의 부등호는 위 처럼 정규화되어 있지 않음(즉, \(\ge\), \(\le\) 둘다 가능).
3.4 행렬식 표현
maximize \({c^T}x\) \(\left( {x \in {\mathbb{R}^n}} \right)\)
subject to \(Ax \le b\)
\(x \ge 0.\)
여기서, 제약 행렬 \(A\)는 \(m \times n\)차원 유리수 벡터, 결정 벡터 \(x\)는 \(n \times 1\)차원 열 벡터, 우변 벡터 \(b\)는 \(m \times 1\)차원 열 벡터, 비용 벡터 \(c\)는 \(n \times 1\)차원 열 벡터입니다.
4. LP의 가능성과 최적해 의미
가능한 해 집합(Feasible Set)은 주어진 제약 조건을 만족하는 모든 해의 집합을 의미하며 표기는 다음과 같이 한다:
\(F = \left\{ {x \in {\mathbb{R}^n}|Ax = b,\,x \geqslant 0} \right\}\)
만약 어떤 벡터가 이 집합에 포함되면 가능한 해(feasible solution)라고 하고, 그렇지 않으면 불가능한 해(infeasible solution) 라고 한다.
가능한 해 집합이 비어있지 않다면(즉, \(F \ne \emptyset \)), 즉 하나 이상의 가능한 해가 존재한다면 일관성이 있다(Consistent)고 하며, 가능한 해가 전혀 존재하지 않으면 일관성이 없다(Inconsistent)고 한다.
또한 LP 문제는 실행 가능 집합은 모든 \(x \in F\)에 대해 \(\left\| x \right\| \leqslant M\)이면 유계(Bounded) 라고 하며(여기서 \(M\)은 어떤 양의 상수), 그렇지 않다면 LP는 무계(Unbounded)라고 함. 명백히 \(F\)가 유계이면 LP도 유계이다.
직관적으로 실행 가능 집합은 실행 가능 집합을 완전히 포함할 수 있는 구 또는 직사각형이 있는 경우 유계이다.
최적해(optimal solution)은 가능한 해 중에서 목적 함수를 최소화 또는 최대화하는 해를 최적해라고 한다.
만약 최적해가 아닌 경우. 이를 준최적해 또는 부분 최적해(sub-optimal)라고 한다.
5. LP 문제를 기본형으로 변환하여 푸는 방법: 아래와 같은 변환 규칙 이용하여 풀이.
1) 변환 규칙-1: 제한 없는 변수 변환
의사결정 변수 \(x\)가 처음에 제한이 없는 것으로 정의되어 있다면(즉, 변수가 부호에 관계없이 모든 실수를 취할 수 있다면), \(x\)는 두 개의 음이 아닌 수 \({x^ + } \ge 0\), \({x^ - } \ge 0\)의 차로 표현될 수 있음: \(x = {x^ + } - {x^ - }\).
2) 변환 규칙-2: 부등식 제약 조건 변환
제약 조건 \(i\)가 처음에 \({a_{i1}}{x_1} + {a_{i1}}{x_2} + \cdots + {a_{in}}{x_n} \le {b_i}\) 형태인 경우, 음이 아닌 여유 변수(Slack variable) \({s_i}\)를 제약 조건의 왼쪽에 더하여 \({a_{i1}}{x_1} + {a_{i1}}{x_2} + \cdots + {a_{in}}{x_n} + {s_i} = {b_i}\)를 얻을 수 있으며, 여기서 \({s_i} \ge 0\) 입니다.
제약 조건 \(i\)가 처음에 \({a_{i1}}{x_1} + {a_{i1}}{x_2} + \cdots + {a_{in}}{x_n} \ge {b_i}\) 형태인 경우, 음이 아닌 여유 변수 \({s_i}\)를 제약 조건의 왼쪽에 빼서 \({a_{i1}}{x_1} + {a_{i1}}{x_2} + \cdots + {a_{in}}{x_n} - {s_i} = {b_i}\)를 얻을 수 있으며, 여기서 \({s_i} \ge 0\)입니다.
3) 변환 규칙-3: 최대화 문제를 최소화 문제로 변환
maximize \({c^T}x\) = minimize \({-c^T}x\).
모든 최대화 문제는 원래 목적 함수의 부정된 항을 최소화함으로써 동등한 최소화 문제로 변환될 수 있습니다. 이는 최적화에 영향을 미치지 않으므로 공식화에서 부정 '\(-\)' 항을 생략하는 것이 일반적임.
6. 목적함수를 등식화 표현
최대화: \(z = {c_1}{x_1} + {c_2}{x_2} + \cdots + {c_n}{x_n} \to z - {c_1}{x_1} - {c_2}{x_2} - \cdots - {c_n}{x_n} = 0\)
최소화: \( - z = {c_1}{x_1} + {c_2}{x_2} + \cdots + {c_n}{x_n} \to z + {c_1}{x_1} + {c_2}{x_2} + \cdots + {c_n}{x_n} = 0\)
7. 선형 계획법 문제 해법 종류
- Graphical method: 2개의 변수로 구성된 간단한 문제를 해석적으로 해결됨. 만약 \(F\)가 유계이면 최적해는 꼭지점(Vertex) 중에 하나에 존재하고, 만약 \(F\)가 무계이면 최적해는 어떤 선분(Edge) 위에서 존재하거나 존재하지 않을 수 있음.
- Simplex method(단체법): 다차원 문제를 효율적으로 해결하는 반복적 알고리즘.
- Interior-point method: Simplex 방법보다 큰 문제를 더 빠르게 해결하는 방법.
- Combinatorial method: 정수 제약이 추가된 정수 선형 계획법(Integer linear programming, ILP) 또는 혼합 정수 선형 계획법(Mixed-integer linear programming, MILP).