1. 최적화 문제의 상한과 하한

• 임의의 최적화 문제에서 상한은 Optimal Value보다 큰 objective value를 말하고, 하한은 Optimal Value보다 작은 objective value를 말한다.

2. Ideation

A. Constraint에 Objective Function이 정의된 경우

$$ min \quad x_1 + x_2 \\ s.t \quad x_1 + x_2 \geq 2 \\ x_1\geq 0, x_2 \geq 0 $$

• 이 경우, 최적값은 2보다 낮아질 수 없으므로 하한은 2인 것을 알 수 있다.

B. Constraint의 Linear Combination으로 Objective Function이 정의되는 경우

$$ max \quad 20x_1 + 10x_2 \\ s.t \quad x_1 + x_2 \leq 6 \\3x_1 + x_2 \leq 12 \\ x_1 + 2x_2 \leq 10 \\ x_1\geq 0, x_2 \geq 0 $$

• $(x_1, x_2) = (3, 3)$이면, $20x_1 + 10x_2 = 90$이다. 단. Optimal Value인지는 모르기 때문에 최적값은 이 값보다 클 수 있으므로 최적값의 하한은 90이 된다.
• 이 LP의 최적해는 위의 제약식을 만족하므로, 제약식에 일정한 상수를 곱해도 성립하게 된다. 그리고 $A \leq B, C \leq D \rightarrow A+C \leq B+D$ 이므로, 두 제약조건을 합쳐도 된다.
• 따라서, 1번과 2번의 제약조건을 각각 5배 해서 더하면, $20x_1 + 10x_2 \leq 90$이 된다. 그리고 2번을 6배하고 3번을 2배해서 더하면 , $20x_1 + 10x_2 \leq 92$가 된다. 즉, 상한은 90이다.
• 최적값의 하한이 90이고 상한이 90이므로 이 경우 최적값은 90이 된다.

C. 일반화

• 임의의 최대화 LP 문제에 위의 아이디어를 적용하면, 상한은 다음과 같아진다.

$$ 20x_1 ^{}+ 10x_2^{} \leq (y_1 + 3y_2+y_3)x_1^{} + (y_1 + y_2 +2y_3)x_2^{} \leq (6y_1 + 12y_2+10y_3) $$

• 그렇기 때문에, 다음과 같이 새로운 최적화 문제를 정의하면 임의의 최대화 LP 문제의 상한을 계산할 수 있다.

$$ min \quad 6y_1 + 12y_2 + 10y_3 \\ s.t \quad y_1 + 3y_2 + y_3 \geq 20 \\ y_1 + y_2 + 2y_3 \geq 10 \\ y_1 \geq 0, y_2 \geq 0, y_3 \geq 0 $$

3. Formulation

• 원 문제가 최소화 문제인 경우, 다음과 같다.