Linear Programming, Part I

Standard Form, Simplex Method, and Postoptimality Analysis

Reference: Jasbir Singh Arora, Introduction to Optimum Design, 4th ed., Academic Press, 2017, Ch. 8.

이 장에서는 cost function과 constraints가 design variables에 대해 linear인 optimum design problem을 다룬다. 일반 LP를 standard form으로 변환하고, basic feasible solution과 feasible set의 vertex 사이의 관계를 이용해 simplex method를 구성한다. 이어서 artificial variable을 이용한 two-phase method와 final tableau에 기초한 postoptimality analysis를 정리한다.


Linear Functions and Standard LP

Linear cost function과 $i$번째 linear constraint는 각각

\[f(x)=c^Tx=sum_{j=1}^{n}c_jx_j,\] \[\sum_{j=1}^{n}a_{ij}x_j \leq b_i, \qquad \sum_{j=1}^{n}a_{ij}x_j=b_i, \qquad \sum_{j=1}^{n}a_{ij}x_j\geq b_i\]

의 형태를 갖는다. Right-side parameter $b_i$는 resource limit이라고도 한다.

Chapter 8의 standard LP problem은

\[\begin{aligned} \underset{x}{\operatorname{minimize}}\quad & f=c^Tx \\ \text{subject to}\quad & Ax=b, \\ & b\geq0, \\ & x\geq0 \end{aligned}\]

이다. 여기서 $A\in\mathbb{R}^{m\times n}$이고 $\operatorname{rank}(A)=m$을 가정한다. Linear constraints가 만드는 feasible set은 convex이고 cost function도 convex이므로, optimum이 존재하면 global optimum이다.


Transcription to Standard Form

일반 LP는 다음 규칙으로 standard form에 옮긴다.

  • $b_i<0$이면 constraint 전체에 $-1$을 곱하고 inequality의 방향을 바꾼다.
  • $\leq$ constraint에는 slack variable $s_i\geq0$을 더한다.
  • $\geq$ constraint에는 surplus variable $s_i\geq0$을 뺀다.
  • Sign restriction이 없는 variable은 $x_j=x_j^+-x_j^-$, $x_j^+,x_j^-\geq0$로 분해한다.
  • Maximization은 objective의 부호를 바꾸어 minimization으로 변환한다.

Slack과 surplus variable은

\[\sum_j a_{ij}x_j+s_i=b_i \quad(\leq), \qquad \sum_j a_{ij}x_j-s_i=b_i \quad(\geq)\]

로 도입한다. Optimum에서 $s_i>0$이면 original inequality는 inactive이고, $s_i=0$이면 active이다.


Basic Solutions and LP Geometry

$m<n$이고 $A$가 full row rank이면 $Ax=b$는 일반적으로 infinitely many solutions를 갖는다. 이 중 $n-m$개의 variables를 zero로 두고 나머지 $m$개를 equations에서 풀어 얻는 solution을 basic solution이라 한다.

  • Zero로 둔 variables는 nonbasic variables이다.
  • Equations에서 결정되는 variables는 basic variables이다.
  • 모든 variables가 nonnegative이면 basic feasible solution이다.
  • Basic variable 중 하나 이상이 zero이면 degenerate basic solution이다.
  • Basic variables에 대응하는 $A$의 linearly independent columns를 basis라 한다.
  • Feasible set의 서로 다른 두 점 사이의 interior point로 표현되지 않는 점을 vertex 또는 extreme point라 한다.

Canonical form에서는 basic-variable columns가 identity matrix를 이룬다. 예를 들어

\[x_i = b_i- \sum_{j=m+1}^{n}a_{ij}x_j, \qquad i=1,\ldots,m\]

에서 $x_1,\ldots,x_m$은 basic이고 나머지는 nonbasic이다.


Fundamental Theorems of LP

Theorem 8.1 — Extreme Points and Basic Feasible Solutions. LP feasible set의 extreme points는 basic feasible solutions에 대응한다.

Theorem 8.2 — Basic Theorem of LP. Feasible solution이 존재하면 basic feasible solution이 존재한다. Optimum feasible solution이 존재하면 optimum basic feasible solution이 존재한다.

따라서 simplex method는 continuous feasible set 전체가 아니라 vertices만 조사하면 된다. Basic solutions의 최대 개수는

\[\binom{n}{m} = \frac{n!}{m!(n-m)!}\]

이지만, 이를 모두 열거하는 대신 cost를 감소시키는 adjacent basic feasible solutions만 선택한다.


Tableau and Pivot Step

Tableau는 constraint coefficients, right sides, cost coefficients를 하나의 표에 나타낸 것이다. Identity columns가 basic variables를 정하고, 각 unit element가 위치한 row의 right side가 해당 basic-variable value이다.

Pivot step은 basic variable 하나와 nonbasic variable 하나를 교환하는 Gauss–Jordan elimination이다.

  • Pivot column: 새로 basic이 될 nonbasic variable의 column이다.
  • Pivot row: leaving basic variable이 위치한 row이다.
  • Pivot element: pivot row와 pivot column의 intersection이다.

Pivot row를 pivot element로 나누고 다른 rows의 pivot-column coefficients를 zero로 만들면 new canonical tableau를 얻는다. Cost row에도 같은 elimination을 적용해야 objective가 계속 nonbasic variables만으로 표현된다.


Reduced Costs and the Ratio Test

Current basic feasible solution의 cost를 $f_0$라 하면 cost function은

\[f = f_0+ \sum_{\text{nonbasic }j}c_j^{\prime}x_j\]

로 쓸 수 있다. $c_j^{\prime}$는 nonbasic variable $x_j$의 reduced cost coefficient이다.

  • $c_j^{\prime}<0$이면 $x_j$를 증가시켜 cost를 감소시킬 수 있다.
  • 모든 $c_j^{\prime}\geq0$이면 current basic feasible solution은 optimum이다.

$c_q^{\prime}<0$인 variable $x_q$를 entering variable로 선택하면 feasibility는

\[b_i-a_{iq}x_q\geq0\]

을 요구한다. 따라서 $a_{iq}>0$인 rows에 대해

\[x_q = \min_{i:a_{iq}>0} \frac{b_i}{a_{iq}}\]

로 정하고, minimum을 주는 row의 basic variable을 leaving variable로 선택한다. 이것이 minimum-ratio rule이다.


Simplex Method and Optimality

Simplex method는 다음 절차를 반복한다.

  1. Problem을 standard form으로 변환하고 initial basic feasible solution을 정한다.
  2. Cost function을 nonbasic variables만으로 표현한다.
  3. 모든 $c_j^{\prime}\geq0$이면 종료한다.
  4. Negative reduced cost를 갖는 column을 pivot column으로 선택한다.
  5. Minimum-ratio rule로 pivot row를 정한다.
  6. Pivot operation을 수행해 new basic feasible solution을 만든다.

Theorem 8.3 — Improvement of the Basic Feasible Solution. Nondegenerate basic feasible solution에서 $c_j^{\prime}<0$인 nonbasic column이 basis에 들어갈 수 있으면 더 작은 cost를 갖는 basic feasible solution이 존재한다. 해당 column에 positive element가 없으면 cost는 unbounded이다.

Theorem 8.4 — Optimum Solutions. Basic feasible solution의 모든 reduced cost coefficients가 nonnegative이면 그 solution은 optimum이다.


Types of LP Solutions

LP problem의 solution은 다음과 같이 분류된다.

  • Unique optimum: Finite optimum이 존재하고 모든 nonbasic $c_j^{\prime}>0$이면 optimum basic solution은 unique하다.
  • Multiple optima: 어떤 nonbasic $c_j^{\prime}=0$이고 feasible pivot이 가능하면 동일한 cost를 갖는 alternate optimum이 존재한다.
  • Unbounded solution: $c_j^{\prime}<0$인 pivot column에 positive element가 없으면 feasible direction을 따라 cost가 $-\infty$로 감소한다.
  • Infeasible problem: Constraints를 동시에 만족하는 point가 없으며, two-phase method에서 Phase-I optimum이 $w>0$으로 남는다.

Multiple optimum vertices를 잇는 line segment의 모든 점도 optimum이다. 이 분류와 별개로 minimum ratio가 zero이면 degenerate pivot이 발생한다. Degenerate solutions에서는 서로 다른 bases가 동일한 vertex를 나타낼 수 있고, pivot 후에도 design point와 cost가 변하지 않을 수 있다.


Two-Phase Simplex Method

모든 constraints가 $\leq$ type이면 slack-variable columns가 initial basis를 제공한다. Equality와 $\geq$ constraints에서는 initial basic feasible solution을 만들기 위해 nonnegative artificial variables를 추가한다.

Artificial cost function은

\[w = \sum \left( \text{artificial variables} \right)\]

이다.

  • Phase I: Original constraints 아래에서 $w$를 최소화한다. $w=0$이면 original problem의 basic feasible solution을 얻고, $w>0$에서 더 이상 개선할 수 없으면 original problem은 infeasible이다.
  • Phase II: Artificial cost row를 제거하고 original cost function으로 simplex iteration을 계속한다. Artificial columns는 pivot-column selection에서 제외한다.

Phase I 동안 original cost row에도 elimination을 적용하면 Phase II를 current tableau에서 바로 시작할 수 있다.


Postoptimality and Lagrange Multipliers

Final tableau는 optimum뿐 아니라 $c$, $b$, $A$의 parameter 변화에 대한 정보도 포함한다. Final-tableau quantities는

\[a_{ij}^{\prime}, \qquad b_i^{\prime}, \qquad c_j^{\prime}\]

로 표시한다.

Theorem 8.5 — Lagrange Multiplier Values. $\leq$ constraint의 multiplier는 corresponding slack-variable column의 reduced cost coefficient이다. Equality와 $\geq$ constraint의 multiplier는 corresponding artificial-variable column의 reduced cost coefficient이다.

Minimization problem에서 right-side parameter $e_i$가 변할 때

\[\frac{\partial f}{\partial e_i}=-y_i, \qquad \Delta f=-y_i\Delta e_i\]

이다. 이 sensitivity relation은 optimum basis가 유지되는 parameter range 안에서 유효하다.


Ranges of LP Parameters

$k$번째 right side가 $\Delta_k$만큼 변하고 corresponding slack 또는 artificial column이 $j$라고 하자. Final tableau에서

\[r_i = -\frac{b_i^{\prime}}{a_{ij}^{\prime}}\]

를 계산하면 Theorem 8.6의 admissible range는

\[\max_{i:a_{ij}^{\prime}>0}r_i \leq \Delta_k \leq \min_{i:a_{ij}^{\prime}<0}r_i\]

이다. 이 범위에서는

\[b_i^{\prime\prime} = b_i^{\prime}+\Delta_k a_{ij}^{\prime}\]

로 new basic-variable values를 계산한다.

Cost coefficient 변화는 variable이 basic인지 nonbasic인지에 따라 구분한다.

Theorem 8.7. $x_k$가 nonbasic이면 current solution이 유지되는 range는 $-c_k^{\prime}\leq\Delta c_k\leq\infty$이다.

Theorem 8.8. $x_k$가 basic이면 final tableau의 row $r$과 nonbasic reduced costs의 ratios $c_j^{\prime}/a_{rj}^{\prime}$가 admissible range를 결정한다. 이 범위에서는 design variables는 변하지 않고 optimum cost만 $f_{\mathrm{new}}^{\star}=f^{\star}+\Delta c_kx_k^{\star}$로 변한다.

Theorems 8.9–8.10은 $a_{ij}$ 변화가 nonbasic 또는 basic variable과 연결된 경우를 나누어 다룬다. 핵심은 final tableau로 feasibility와 reduced-cost signs가 유지되는 범위를 검사하고, 범위를 벗어나면 changed problem을 다시 푸는 것이다.


Summary

  • Standard LP는 $\min c^Tx$ subject to $Ax=b$, $b\geq0$, $x\geq0$로 정의한다.
  • Basic feasible solutions는 feasible set의 extreme points에 대응하며, optimum이 존재하면 optimum basic feasible solution이 존재한다.
  • Reduced costs는 entering variable을, minimum-ratio rule은 leaving variable을 결정한다.
  • 모든 reduced costs가 nonnegative이면 optimum이고, improving column에 positive element가 없으면 unbounded이다.
  • Two-phase method의 Phase I은 feasibility를 판정하고 Phase II는 original cost를 최소화한다.
  • Final tableau는 Lagrange multipliers와 parameter ranges를 제공하여 postoptimality analysis를 가능하게 한다.