생산계획을 다음에 어떻게 개선할 것인가?

심플렉스법(simplex method)은 기저의 변수를 교환하며 선형계획 문제를 푼다. 기저는 후보 해를 결정하는 소수의 독립인 열로 이루어진다. 원문제 심플렉스법은 계획의 실행가능성을 유지하면서 목적값을 개선한다. 보통 피벗은 모서리를 따라 다른 꼭짓점으로 이동하지만, 퇴화 피벗은 점을 이동시키지 않고 기저만 바꿀 수도 있다. 일반 알고리즘을 제시하기 전에 이 연산들을 직접 유도한다. Goemans, §§2–3을 참고하자.

선형계획법의 배경인 생산 문제에서 출발하자. 부품의 총개수만 최대화하면 짝이 맞지 않는 부품이 남을 수 있다. Kantorovich의 1939년 저서에는 다음 출판된 설명용 자료가 나온다. 공장에서 관측한 자료는 아니다. 완제품 하나에는 각 부품이 하나씩 필요하다. 예제 1과 표 1, 인쇄 쪽수 369–370쪽을 보자.

기계군 가용 기계·일 기계·일당 부품 I 기계·일당 부품 II
밀링 3 10 20
터릿 선반 3 20 30
자동 터릿 선반 1 30 80

$m,t,a$를 부품 I에 배분한 기계·일이라 하자. 나머지 시간에는 부품 II를 만든다. 시간은 분할 가능하고 생산율은 일정하며 생산량은 더할 수 있다고 가정한다. 가용시간을 모두 사용하고 준비비용은 없으며 두 부품의 총생산량을 정확히 맞춘다. 이는 문제 A, 371–372쪽의 완전 가동·부품 일치 가정이다.

아래 계산은 출판 생산율을 현대적 심플렉스 관점으로 재유도한 것이며, Kantorovich가 이 알고리즘을 사용했다는 주장이 아니다. 별도 출처를 밝히지 않은 이후의 수치 예제, 연습문제, 대수 계산은 직접 작성했다. 분수 생산량은 일일 생산율이지 완제품을 정수로 만드는 일정이 아니다. 원문의 표 2는 전문화 계획의 정수 합계로 86을 제시한다. 표 1의 정확한 연속 생산율을 유지하면 아래의 $260/3$을 얻는다.

두 부품의 총생산량과 공통 일일 생산량은

\[P=10m+20t+30a,\qquad Q=230-20m-30t-80a,\qquad P=Q=z.\]

따라서 모형은 다음과 같다.

\[\begin{aligned} \text{최대화}\quad &z=10m+20t+30a\\ \text{제약조건}\quad &30m+50t+110a=230,\\ &0\le m,t\le3,\qquad0\le a\le1. \end{aligned}\]

균형식은 $P=Q$에서 얻는다. 어떤 개선도 다른 배분을 함께 바꾸어 이 식을 유지해야 한다. 따라서 부품 I의 단순 생산율이 가장 큰 변수를 늘리는 것만으로는 올바른 최적화 규칙이 되지 않는다.

꼭짓점을 사전식으로 나타내기

상한 제약을 등식으로 완성하는 양인 여유변수(slack variable)를 도입하자.

\[m+s_m=3,\qquad t+s_t=3,\qquad a+s_a=1,\qquad m,t,a,s_m,s_t,s_a\ge0.\]

여기서 여유변수는 유휴시간이 아니라 부품 II를 만드는 시간이다. 균형식을 포함하면 변수 여섯 개에 독립인 방정식 네 개가 있다. 기저(basis)는 독립인 열 네 개를 선택한다. 나머지 두 변수인 비기저변수를 0으로 놓고 네 기저변수를 구한다. 기저변숫값이 음이 아니면 기저 실행가능해(basic feasible solution, BFS)이다. 기저변수도 0일 수 있다. Goemans, §2.4를 참고하자.

비기저변수를 $m=s_a=0$으로 고르자. 그러면 $a=1$이고 균형식에서 $t=12/5$이다. 모든 식을 두 비기저변수로 정리하면 사전식(dictionary)을 얻는다.

\[\begin{aligned} t&=\frac{12}{5}-\frac35m+\frac{11}{5}s_a,\\ s_m&=3-m,\\ s_t&=\frac35+\frac35m-\frac{11}{5}s_a,\\ a&=1-s_a,\\ z&=78-2m+14s_a. \end{aligned}\]

각 행은 비기저변수를 바꾸는 동안에도 유지해야 하는 등식이다. $m=s_a=0$에서 기저변숫값은 $(t,s_m,s_t,a)=(12/5,3,3/5,1)$이고 $z=78$이다. 모든 값이 음이 아니므로 실행가능한 꼭짓점이다.

마지막 행에는 $t,a$의 보상 변화가 이미 반영되어 있다. 계수 $-2,14$는 감소비용(reduced cost), 즉 비기저변수를 한 단위 늘릴 때의 순수 목적값 변화율이다. 최대화에서는 감소비용이 양수이면 양의 보폭이 실행가능할 때 개선하는 방향을 나타낸다. 보폭을 마음대로 크게 잡아도 된다는 뜻은 아니다.

첫 피벗: 어떤 기저변수가 먼저 소진되는가?

$m=0$을 유지하며 $s_a$를 0에서 늘리자. 자동 선반 시간을 부품 II로 옮기고 터릿의 부품 I 시간을 늘리는 변화다. $s_t,a$ 행은 다음 상한을 준다.

\[s_a\le\frac{3/5}{11/5}=\frac3{11},\qquad s_a\le1.\]

최솟값은 $3/11$이다. 이것이 비율 검사(ratio test)이다. 현재 기저변숫값을 그 변수의 감소율로 나누고 해당 비율 중 가장 작은 값을 택한다. 기저변수가 증가하는 행은 보폭을 제한하지 않는다. $s_a=3/11$에서 $s_t$가 먼저 0이 되므로 $s_a$가 기저에 진입하고 $s_t$가 이탈한다.

이탈변수의 행을 진입변수에 대해 풀고, 목적식을 포함한 다른 모든 행에 대입하자.

\[\begin{aligned} s_a&=\frac3{11}+\frac3{11}m-\frac5{11}s_t,\\ t&=3-s_t,\\ s_m&=3-m,\\ a&=\frac8{11}-\frac3{11}m+\frac5{11}s_t,\\ z&=\frac{900}{11}+\frac{20}{11}m-\frac{70}{11}s_t. \end{aligned}\]

새 비기저변수는 $m,s_t$이다. 둘을 0으로 놓으면 $(m,t,a)=(0,3,8/11)$이고 $z=900/11$이다. 증가량은 하루 완제품 $14(3/11)=42/11$세트이다. 이 대입 연산은 사전식으로 수행한 피벗이다. 심플렉스 표(tableau)는 같은 방정식을 계수 격자에 저장한다.

두 번째 피벗: 목적식이 증명이 된다

이제 $m$의 감소비용은 양수 $20/11$이다. $s_t=0$을 유지하며 $m$을 늘리자. 감소하는 기저변수들이 주는 상한은

\[m\le3\quad\text{여유변수 }s_m,\qquad m\le\frac{8/11}{3/11}=\frac83\quad\text{변수 }a.\]

따라서 $m=8/3$에서 $m$이 진입하고 $a$가 이탈한다. $m$에 대해 풀면 최종 사전식을 얻는다.

\[\begin{aligned} m&=\frac83-\frac{11}{3}a+\frac53s_t,\\ t&=3-s_t,\\ s_m&=\frac13+\frac{11}{3}a-\frac53s_t,\\ s_a&=1-a,\\ z&=\frac{260}{3}-\frac{20}{3}a-\frac{10}{3}s_t. \end{aligned}\]

모든 실행가능한 점은 $a,s_t\ge0$이므로 이 항등식은 $z\le260/3$을 증명한다. 비기저변수를 $a=s_t=0$으로 놓으면 기저변숫값이 음이 아니면서 상한을 달성한다. 따라서

\[(m,t,a)=\left(\frac83,3,0\right),\qquad z^{\star}=\frac{260}{3}.\]

실제 부품 생산량도 확인하자. $P=10(8/3)+60=260/3$이고 $Q=20(1/3)+80=260/3$이다. 목적식은 이웃 꼭짓점뿐 아니라 모든 실행가능 계획에 대해 최적성을 인증한다.

두 교환을 그림으로 보고 재생하기

$m$을 소거하고 가로축에 터릿 시간 $t$, 세로축에 자동 시간 $a$를 그리자. 밀링의 상·하한은 $140\le50t+110a\le230$이 된다. 음영은 부품 균형을 맞추는 모든 실행가능 계획이고 강조한 경로는 두 피벗이다. 각 점에서 $m=(230-50t-110a)/30$을 복원할 수 있다.

좌표 t,a로 나타낸 균형 기계 배분 다각형. 강조 경로는 (12/5,1)에서 시작하여 (3,8/11)로 피벗하고 최적점 (3,0)에서 끝난다.
두 축은 부품 I을 만드는 기계·일이다. 첫 피벗은 터릿의 부품 II 시간을 소진하고 두 번째는 자동 선반의 부품 I 시간을 소진한다. 경로는 실행가능 다각형의 경계에 놓인다.

출판 기준값에서 다음 교환을 두 번 누르면 $78$, $900/11$, $260/3$을 재현한다. 실험 도구는 소수를 반올림해 표시한다. 발표된 기준값 복원 및 재현은 용량과 경로를 함께 초기화한다. 용량 변경은 가상 실험이다. 표시 최적값은 다시 계산하지만 두 피벗의 단계별 재생은 원래 자료에서만 제공한다. 용량이 0이거나 입력이 잘못된 경우 상태 메시지가 나온다. 버튼과 입력란은 키보드로 조작할 수 있다. JavaScript가 없어도 위의 사전식과 그림으로 과정을 따라갈 수 있다.

출판 기계 자료로 심플렉스 교환 재생하기

발표된 예시 자료의 기준값이다. 밀링 3, 터릿선반 3, 자동선반 1 기계·일과 Kantorovich, 예제 1과 표 1, 369쪽의 고정 부품 I/II 생산율을 사용한다. 배분과 교환은 시간 분할, 완전 가동, 부품 수의 정확한 일치, 준비 시간 없음을 가정하여 현대적으로 다시 유도했다. 분수 출력은 일일 생산율이다. 용량 변경은 가상 실험이다.

자동 선반의 단순 생산율은 두 부품 모두에서 가장 크지만 최적계획에서는 부품 II만 만든다. 감소비용은 균형을 유지한 뒤 대안적 용도를 비교한다. 단순 생산율만으로는 이 비교를 할 수 없다.

사전식에서 일반 표준형 LP로

독립인 행을 가진 $A\in\mathbb R^{r\times n}$에 대해 최대화 문제를 등식 표준형으로 쓰자.

\[\text{최대화 }c^Tx\quad\text{제약조건 }Ax=b,\quad x\ge0.\]

$r$은 방정식 수, $n$은 변수 수, $A_j$는 $j$번째 열, $c_j$는 그 변수의 목적식 계수이다. 변수를 기저 인덱스 $B$와 비기저 인덱스 $N$으로 나눈다. 가역인 기저행렬을 $M=A_B$라 하면

\[x_B=\bar b-M^{-1}A_Nx_N,\qquad \bar b=M^{-1}b,\] \[c^Tx=z_0+\sum_{j\in N}\bar c_jx_j,\qquad z_0=c_B^T\bar b,\qquad \bar c_j=c_j-c_B^TM^{-1}A_j.\]

이 식들은 기계 문제의 사전식과 마찬가지로 제약방정식을 풀어 목적식에 대입하면 나온다. Goemans, §3을 보자. 최소화 관례를 쓰면 개선을 나타내는 감소비용의 부호가 반대이다.

$\bar b\ge0$, 즉 현재 기저가 실행가능하다고 가정하자. $\bar c_j>0$인 $j\in N$을 고른다. $x_j=\theta$로 놓고 나머지 비기저변수를 0으로 유지한다. $d=M^{-1}A_j$라 하면

\[x_B(\theta)=\bar b-\theta d,\qquad z(\theta)=z_0+\theta\bar c_j.\]

$d_i>0$인 행만 기저변수를 감소시키므로

\[\theta^{\star}=\min_{i:d_i>0}\frac{\bar b_i}{d_i}.\]

최솟값을 주는 행의 기저변수가 이탈변수이다. 진입변수의 열로 그 열을 대체한다. 피벗 계수가 0이 아니므로 대체한 기저도 가역이다. 사전식을 갱신하고 반복한다. 모든 비기저 감소비용이 0 이하이면 목적식 항등식이 최적성을 증명한다. 모든 행에서 $d_i\le0$이면 실행가능한 반직선 $\theta\ge0$을 따라 목적값이 한없이 개선되므로 비유계성(unboundedness)을 증명한다. 이 결론에는 실행가능한 초기 기저가 필요하다. 실행불가능한 표만으로는 충분하지 않다.

보충용 창작 비유계 예제로 $x_1-x_2=1$, $x_1,x_2\ge0$에서 $x_1$을 최대화하자. 사전식 $x_1=1+x_2$, $z=1+x_2$에는 감소하는 기저변수가 없다. $(1+\theta,\theta)$는 모두 실행가능하고 목적값은 무한대로 간다.

같은 기저에서 쌍대 인증서 얻기

$M^Ty=c_B$로 $y$를 정의하자. 모든 $\bar c_j\le0$인 기저에서 감소비용 식은 $A^Ty\ge c$를 주고 기저 열에서는 등호가 성립한다. 제약이 등식이므로 $y$의 부호에는 제한이 없다. 모든 실행가능 $x$에 대해

\[c^Tx\le y^TAx=y^Tb=c_B^TM^{-1}b=z_0.\]

현재 해는 이 상한을 달성한다. 이것이 기저와 쌍대성의 연결이다. MIT의 “Simplex and Duality” 설명을 보자.

역사적 모형에서 네 행의 순서를 부품 균형, 밀링 용량, 터릿 용량, 자동 용량으로 두면 최종 기저는

\[y=\left(\frac13,0,\frac{10}{3},0\right),\qquad b=(230,3,3,1)^T,\qquad b^Ty=\frac{260}{3}.\]

비기저 열 $a,s_t$에 대해 $A_j^Ty-c_j$는 각각 $20/3,10/3$이다. 최종 감소비용에 음수를 붙인 값이다. 자동 용량 승수가 0이라고 해서 자동 선반을 추가해도 가치가 없다는 뜻은 아니다. 자동 시간이 늘면 부품 균형 상수 $230$도 변한다. 마지막 연습문제처럼 실제 용량 변화에서는 두 우변을 모두 갱신해야 한다.

1단계: 생산량을 최적화하기 전에 실행가능한 기저 찾기

역사적 문제에서는 초기 꼭짓점을 쉽게 찾았다. 일반 LP에는 실행가능한 기저가 바로 보이지 않을 수 있다. 먼저 $b_i<0$인 행에 $-1$을 곱해 모든 우변을 음이 아니게 만든다. 방정식마다 하나씩 비음수 인공변수(artificial variable) $u_i$를 추가하자.

\[Ax+u=b,\qquad x,u\ge0,\qquad \text{최소화 }w=\sum_{i=1}^{r}u_i.\]

인공변수의 열은 단위행렬이므로 $x=0,u=b$는 보조문제의 실행가능한 기저이다. 이 구성에서 인공변수는 방정식의 불일치를 나타내며 물리적 생산 활동은 아니다. 1단계는 이 문제를 푼다. 동등하게 $-w$를 최대화해도 된다. 최적값은 음이 아니다. 양수이면 원래 방정식에는 비음수 해가 없고, 0이면 $u=0$이 원래 문제의 실행가능한 점을 준다. 값이 0인 인공 기저변수를 피벗으로 내보내고 필요하면 중복된 영행을 제거한다. 이후 원래 목적식을 복원하고 현재 기저로 다시 표현하여 2단계를 시작한다. Goemans, §2.5를 보자.

보충용 창작 실행불가능 예제로 $x\ge2$와 $x\le1$을 동시에 요구하자. 초과변수 $s_1\ge0$과 여유변수 $s_2\ge0$를 쓰면

\[x-s_1+u_1=2,\qquad x+s_2+u_2=1,\qquad w=u_1+u_2.\]

두 번째 식은 $x\le1$을 강제한다. 첫 번째 식에서 $u_1=2-x+s_1\ge1$이므로 $w\ge1$이다. $(x,s_1,s_2,u_1,u_2)=(1,0,0,1,0)$에서 이 하한을 달성한다. 양의 1단계 최적값이 실행불가능성을 증명한다. Farkas 보조정리는 같은 결론을 모순 인증서로 표현하는 방법을 설명한다.

퇴화가 피벗의 의미를 바꾼다

기저변수 중 하나 이상이 0인 BFS를 퇴화(degenerate)했다고 한다. 이 경우 비율 검사에서 $\theta^{\star}=0$이 나올 수 있다. 감소비용이 양수라도 엄격한 개선이 보장되지 않는다. 서로 다른 기저가 같은 점을 나타낼 수 있다.

보충용 창작 예제로 $x_1\le1$, $x_2\le1$, $x_1+x_2\le1$과 비음수 조건 아래 $x_1+x_2$를 최대화하자. $(1,0)$에서 기저변수를 $(x_1,s_2,s_3)$, 비기저변수를 $(x_2,s_1)$로 고르면 사전식은

\[x_1=1-s_1,\qquad s_2=1-x_2,\qquad s_3=s_1-x_2,\qquad z=1-s_1+x_2.\]

$x_2$의 감소비용은 $1$이지만 $s_1=0$일 때 $s_3=-x_2$ 행은 보폭 0만 허용한다. $x_2$를 진입시키고 $s_3$를 이탈시키면 기저는 변해도 $(x_1,x_2)=(1,0)$은 그대로이다. $x_1+x_2\le1$이므로 이 점은 이미 최적이었다. 따라서 비양수 감소비용은 최적성의 충분조건이지만, 최적점의 퇴화 기저가 처음부터 그 부호 조건을 가질 필요는 없다.

적절하지 않은 규칙에서 보폭 0인 피벗이 반복되면 순환할 수 있다. Bland 규칙은 모든 변수의 순서를 고정하고, 진입 가능한 변수 중 인덱스가 가장 작은 변수를 고른다. 최소 비율이 같은 행들에서는 인덱스가 가장 작은 기저변수를 이탈시킨다. 정확한 산술에서 이 규칙은 순환을 막아 유한 종료를 보장한다. Goemans, §2.4.2, 정리 2.2를 보자. 유한하다고 해서 적다는 뜻은 아니다. 특정 심플렉스 규칙에는 지수적인 최악의 경우가 있다. MIT의 Klee–Minty 예제 설명을 참고하자.

기하학적 단체(simplex), 즉 음이 아닌 좌표의 합이 1인 집합은 특정 실행가능집합이다. 심플렉스 알고리즘은 그 집합 밖에도 적용된다. 기계 배분 다각형도 삼각형일 필요가 없다. 또한 심플렉스법은 연속 LP를 푼다. 기계·일이 분수인 최적해가 정수 일정 문제까지 자동으로 해결하지는 않는다.

선형계 풀이로 대수 구현하기

역행렬 표기는 유도에 유용하지만 수정 심플렉스법(revised simplex) 구현은 기저행렬로 기저변숫값, 가격, 방향을 구하는 선형계를 푼다. Goemans, §3을 보자. 구체적으로 LU 분해와 같은 분해로 $M\bar b=b$, $M^Ty=c_B$, $Md=A_j$를 푼다. 분해 인자를 재사용하면 역행렬을 직접 만들 필요가 없다.

실무 검사는 방정식에서 바로 나온다. $Ax-b$, 비음수성, 감소비용의 부호, 원문제와 쌍대 목적값의 차이를 확인한다. 부동소수점 허용오차는 행과 열의 스케일을 반영해야 한다. 0에 가까운 피벗과 거의 같은 비율에는 주의가 필요하다. 작은 잔차만으로 작은 해 오차가 보장되지는 않는다. 이 문서의 유도는 정확한 분수를 사용하고 대화형 도구는 부동소수점 계산과 반올림 표시를 사용한다.

연습문제

직접 작성한 문제들은 손계산, 해석, 논리적 추론, 실제 용량 계산을 포함한다. 1번, 2번, 4번은 출판 기계 생산율을 연속 모형에 적용한다.

1. 손계산: 첫 피벗 복원하기

초기 사전식에서 $s_a$를 진입변수로 고르자. 감소하는 기저변수를 모두 찾고 비율, 새 점, 목적값 증가량을 계산하라.

힌트

$m=0$을 고정하자. 기저변수 행의 양의 계수는 그 변수가 증가한다는 뜻이므로 보폭을 제한하지 않는다.

풀이

$s_t$는 $11/5$, $a$는 $1$의 비율로 감소한다. 비율은 $(3/5)/(11/5)=3/11$과 $1$이다. $t,s_m$은 증가하거나 일정하다. 따라서 $s_a=3/11$에서 $s_t$가 이탈한다. 새 점은 $(m,t,a)=(0,3,8/11)$이고 $z=78+14(3/11)=900/11$이다. 증가량은 하루 완제품 $42/11$세트이다.

2. 해석: 큰 감소비용과 긴 이동거리

초기 사전식에서 계획 담당자가 감소비용이 양수라는 이유로 $s_a$를 $1$까지 늘리자고 한다. 어느 제약이 깨지는가? 감소비용만으로 이 선택을 정당화할 수 없는 이유는 무엇인가?

힌트

$s_a=1,m=0$을 터릿 행과 그 여유변수 행에 대입하라.

풀이

제안한 값에서는 $t=23/5>3$, $s_t=-8/5<0$이다. 감소비용 $14$는 등식을 유지하는 방향의 목적값 기울기이지 비음수 제약을 없애는 값이 아니다. $m=0$에서 실행가능한 범위는 $0\le s_a\le3/11$뿐이다. 보폭과 목적값 기울기를 함께 고려해야 한다.

3. 논리: 감소비용 0이면 여러 최적해가 존재하는가?

최적 사전식에서 어느 비기저변수의 감소비용이 0이라고 하자. 그것만으로 서로 다른 최적점이 존재함을 증명할 수 있는가? 추가하면 충분한 조건을 제시하고, 그 조건이 없을 때의 반례를 들어라.

힌트

그 방향에서는 목적값이 일정하다. 양의 보폭이 가능한지 확인하라.

풀이

아니다. 그 방향으로 양의 실행가능 보폭이 있으면 충분하다. 최적값을 유지하면서 진입변수의 좌표가 달라지기 때문이다. 보충 반례로 $x+s=0$, $x,s\ge0$에서 $\max 0$을 생각하자. $s$가 기저이면 사전식은 $s=-x$, $z=0$이다. 비기저 감소비용은 0이지만 유일한 실행가능점은 $(0,0)$이고 최대 보폭은 0이다. 보폭 0인 피벗만으로 서로 다른 최적해를 증명할 수 없다.

4. 응용: 기존 용량 가격은 언제까지 유효한가?

출판 생산율과 나머지 용량을 유지하고 자동 기계·일을 $\delta\ge0$만큼 추가하자. 전문화 $t=3,a=0$을 유지할 때 $m$, 생산량, 기존 승수의 상한을 여전히 달성하는 $\delta$의 범위를 구하라.

힌트

균형 상수는 $230+80\delta$, 자동 용량은 $1+\delta$가 된다. $b$의 두 성분이 함께 바뀐다.

풀이

균형식 $30m+150=230+80\delta$에서 $m=8/3+(8/3)\delta$이다. 생산량은 $z=10m+60=260/3+(80/3)\delta$이다. 실행가능성에는 $m\le3$이 필요하므로 $0\le\delta\le1/8$이다. $A,c$가 그대로이므로 기존 쌍대벡터는 여전히 실행가능하고 상한 변화는 $(1/3)(80\delta)+0\delta=(80/3)\delta$이다. 이 범위에서 계획은 상한을 달성한다. 범위를 넘으면 식이 밀링 용량을 위반하므로 최적값을 예측할 수 없다. 끝점에서는 $s_m=0$이 되어 퇴화 기저가 생기고 전문화 방식이 바뀔 수 있다.

참고 문헌과 추가 학습