보강 4-2. 미지수와 기준을 만들기

먼저 확인할 것이 있다. 회수액 표를 놓고

(1)에서 각 행의 최소는 $(1, 2)$ 라 그 최대가 2 이고, 각 열의 최대는 $(4, 3)$ 이라 그 최소가 3 이다. 둘이 다르므로 안장점이 없다. 곧 어느 한 항구에 몰빵하는 답은 없고 섞어야 한다.

세관이 비율 $\vv{x}$ 로 섞으면, 밀수업자가 어느 쪽으로 오든 세관의 기대 회수액이 같아야 한다. 그렇지 않으면 밀수업자가 작은 쪽으로만 갈 것이기 때문이다.

(2)의 세 줄에는 미지수가 셋($x_1, x_2, v$) 있다. $v$ 를 왼쪽으로 넘기면 그냥 정방계다.

(3)의 행렬식은 4 라 가역이다. 풀면

이다. 인천에 약 91일, 부산에 약 274일이고 연평균 2.5억원을 회수한다.

검산. 밀수업자가 인천을 고르면 $\frac14(4) + \frac34(2) = 1 + \frac32 = \frac52$, 부산을 고르면 $\frac14(1) + \frac34(3) = \frac14 + \frac94 = \frac52$ 로 같다. 어느 쪽으로 와도 같으니 밀수업자에게 유리한 선택이 없다.

밀수업자 쪽도 같은 방법으로 풀린다. 계수행렬만 전치하면

이고 (5)의 값도 $v = \frac52$ 로 같다. 두 사람이 서로 다른 계를 푸는데 답의 셋째 성분이 같다. 그것이 게임의 값이다.

빠지기 쉬운 곳 — 이 수법은 두 순수전략이 모두 양의 확률로 쓰인다는 가정 아래에서만 성립한다. 지지집합이 더 작으면 해에 음수가 나오고, 그때는 선형계가 아니라 선형계획을 풀어야 한다. 그래서 안장점이 없다는 것을 먼저 확인한 것이다.

회수 : L03 역행렬 · L05 전치 · L20 크래머

노는 시간에 이름을 붙인다. 공장 $i$ 가 쉬는 시간을 $s_i$ 라 하면 부등식이 등식이 된다.

(6)의 세 줄을 쌓으면 이렇게 된다.

(7)의 계는 줄 3개에 미지수 5개다. L07의 계산 그대로 자유변수가 $5 - 3 = 2$ 개다. 답이 무수히 많다.

그런데 여기서 L07이 준 것이 하나 더 있다. 다섯 열 중 셋을 골라 피벗 열로 삼고 나머지 둘을 0으로 두면 $3\times3$ 계가 남는다. 고르는 방법이

가지다. (8) 중 두 가지는 고른 세 열이 종속이라 못 푼다. 남은 8가지가 기저해다.

세 열을 골랐다면 남은 두 미지수는 0이고, 고른 세 열이 만드는 $3\times3$ 계를 푼다.

(9)에서 $\det B \neq 0$ 이면 답이 하나 나온다. 열 $\vv{a}_1$ 과 $\vv{a}_2$ 를 함께 고르면서 여유변수를 하나만 남기는 두 경우가 종속이라 못 푼다.

여덟 기저해 중 성분이 전부 0 이상인 것이 다섯이다. 그 다섯이 꼭짓점이다.

나머지 셋은 각각 $s_3 = -6$, $s_1 = -2$, $s_2 = -6$ 로 노는 시간이 음수다. 그런 공장은 없다.

한걸음 더 — 이익이 최대인 곳이 왜 하필 꼭짓점인가. 목적함수가 선형이므로 같은 이익을 주는 점들이 직선을 이루고, 그 직선을 평행이동하면 영역을 벗어나기 직전에 반드시 꼭짓점에 닿는다. 그래서 꼭짓점만 세면 된다. 여기서는 다섯 개뿐이다.

빠지기 쉬운 곳 — $\vv{x} \ge \vv{0}$ 은 선형계가 아니다. 이 책은 여덟 개의 기저해를 전부 구한 뒤 부호를 눈으로 확인했다. 실제 선형계획법은 그렇게 하지 않고 꼭짓점을 하나씩 옮겨 다닌다. 그 옮겨 다니는 일이 무엇인지가 다음 문제다.

회수 : L06 열공간 · L07 피벗과 자유변수 · L08 완전해 · L09 독립

기저 $B$ 에서 열 하나만 바꿔 $B'$ 이 될 때

이고, (10)의 $E$ 는 단위행렬에서 한 열만 바뀐 것이다. 축 원소를 $a_{rs}$ 라 하면 $E$ 의 $r$ 번째 열이

이다. (11)의 꼴이 L02의 소거행렬 그대로다. 한 열을 $\vv{e}_r$ 로 만드는 일이니 당연하다.

실제로 해 보자. 출발 기저는 여유변수 셋이라 $B = I$ 다.

첫 걸음 — 제품 2를 넣는다. 그 열이 $\vv{a}_2 = (0, 2, 2)$ 이고 $\vv{b} = (4, 12, 18)$ 이므로, 어느 줄이 먼저 바닥나는지 비율로 본다.

(12)에서 2행을 골랐으니 (11)에 넣으면

이다. (13)의 확인처럼 열이 정확히 $\vv{e}_2$ 가 됐다.

둘째 걸음 — 제품 1을 넣는다. 같은 식으로

가 나온다. (14)까지 곱하면 최종 역행렬이다.

(15)에서 기저가 $(s_1, x_2, x_1)$ 이므로 $s_1 = 2$, $x_2 = 6$, $x_1 = 2$ 다. 최적 꼭짓점 $(2, 6)$, 이익 36만원으로 상황의 답과 같다.

개발자가 설명하기 어려웠던 것이 이것이다. 저장하는 것은 $B^{-1}$ 전체가 아니라 $E$ 들의 목록이고, $E$ 하나는 숫자 세 개면 적힌다. 아홉 칸이 아니라 세 칸이다.

한걸음 더 — 걸음을 많이 걸으면 $E$ 가 쌓여 곱셈이 늘고 반올림 오차도 쌓인다. 그래서 실무에서는 주기적으로 $B$ 를 다시 분해한다. 보강 2가 말한 대로 빠른 갱신과 안정성이 맞바꿈 관계다.

회수 : L02 소거행렬 · L03 역행렬 · L04 분해를 다시 하는 값 · L07 기저 교환

최적 기저에서 $\vv{y}$ 가 만족해야 할 것은 이것이다.

(16)에 전치가 나오는 것이 이 문제의 전부다. 원문제는 열을 활동으로 읽었는데, 값을 물으면 행을 자원으로 읽게 된다. L05가 말한 그 전치다.

최적 기저는 열 $(\vv{a}_{s_1}, \vv{a}_2, \vv{a}_1)$ 이므로

이다. (17)의 $\vv{c}_B$ 에서 첫 성분이 0인 것은 여유변수 $s_1$ 이 이익을 안 내기 때문이다. 전치해서 풀면

(18)의 답이 답이다. 1공장은 0원, 2공장은 1.5만원, 3공장은 1만원이다.

1공장이 0인 것에 뜻이 있다. (15)에서 $s_1 = 2$ 였다. 1공장은 이미 2시간이 남아돌므로 한 시간 더 준다고 이익이 늘지 않는다.

검산. 2공장 가용시간을 12에서 13으로 올려 실제로 다시 풀어 보자.

(19)의 이익은 $3(\frac53) + 5(\frac{13}{2}) = 5 + 32.5 = 37.5$ 다. $36 + 1.5$ 로 정확히 $y_2$ 만큼 늘었다.

그러니 잔업 시급이 1.5만원 미만이면 남는 장사다. 다시 풀 필요가 없었다.

왜 $\vv{y}$ 가 곧 값인지 한 줄로 보인다. 최적 이익은 $z = \vv{c}_B^{\mathsf T}\vv{x}_B$ 이고 $\vv{x}_B = B^{-1}\vv{b}$ 이므로

이다. (20)의 마지막 꼴에서 $\vv{b}$ 의 성분 하나를 1만큼 올리면 이익이 정확히 그 자리의 $y_i$ 만큼 는다. 기저가 안 바뀌는 동안은 그렇다.

한걸음 더 — 이 값이 영원히 유효한 것은 아니다. 시간을 계속 늘리면 어느 순간 다른 제약이 먼저 바닥나 기저가 바뀌고 그때 $\vv{y}$ 도 달라진다. "한 시간에 1.5만원"은 지금 기저가 유지되는 범위 안에서만 맞는 말이다.

회수 : L03 역행렬 · L05 전치 · L08 유일해 · L10 네 부분공간

L12의 결합행렬을 그대로 쓴다. 간선을 행, 노드를 열로 놓고 꼬리에 -1, 머리에 +1 이다.

(21)에서 $\rank A = 4 - 1 = 3$ 이다. 연결된 그래프의 결합행렬은 늘 노드 수보다 하나 작다(L12).

그러면 루프 공간의 차원이

이다. (22)의 오일러 공식대로 독립인 루프가 둘이다.

담당자의 답은 $\vv{y} = (6, 6, 0, 6, 0)$ 이고 비용이 36만원이다. 검산하면 $A^{\mathsf T}\vv{y} = (-6, 0, 0, 6)$ 로 흐름이 보존된다.

이제 최선임을 확인한다. 노드마다 숫자 $x_i$ 를 붙이고, 간선의 축소비용을 다음처럼 잰다.

(23)의 값이 0 이상이면 그 간선을 쓰는 것이 이득이 아니다. 쓰고 있는 간선 셋에서 $\bar{c}_e = 0$ 이 되도록 $\vv{x}$ 를 정하면

이고, (24)의 전위로 나머지 둘을 재면 안 쓰는 간선 $e_3$ 와 $e_5$ 에서 축소비용이 각각 $4 - 3 = 1$ 과 $5 - 4 = 1$ 이다. 둘 다 0 이상이므로 최선이다.

빠지기 쉬운 곳 — $\vv{x}$ 는 유일하지 않다. 전체에 상수를 더해도 차이가 안 바뀌기 때문이다. 곧 $N(A) = \operatorname{span}(\vv{1})$ 이고, 상황의 기준 통화 이야기와 같은 구조다. 하나를 0으로 고정하면 나머지가 정해진다.

회수 : L07 자유변수 · L08 해집합 · L10 네 부분공간 · L12 결합행렬

(25)의 각 열에 1이 정확히 둘 있다. 칸 하나는 공장 하나와 대리점 하나에 걸쳐 있기 때문이다. 이것이 완전이분그래프의 결합행렬이다.

이제 종속을 찾는다. 공급 줄을 다 더하면 전부 1이 되고, 수요 줄을 다 더해도 전부 1이 된다.

(26)의 등식이 그 종속이다. "공급 총합 = 수요 총합"이라는 사실이 행 사이의 관계로 나타난 것이다.

그래프가 연결이므로 종속은 이 하나뿐이고

이다. (27)에서 자유변수가 $6 - 4 = 2$ 개다. 담당자가 둘을 정해야 했던 이유가 이것이다.

북서코너부터 채우면 $x_{11} = 20$, $x_{12} = 10$, $x_{22} = 5$, $x_{23} = 15$ 이고 나머지 둘은 0이다. 0이 아닌 성분이 정확히 4개 = $m+n-1$ 이고, 그 넷이 노드 다섯을 잇는 신장나무를 이룬다.

빠지기 쉬운 곳 — 만약 공급 총합과 수요 총합이 다르면 (26)의 종속이 깨지고 $\rank T = 5$ 가 되지만, 그때는 해가 아예 없다. 랭크가 오르는 것이 좋은 소식이 아닌 드문 경우다.

회수 : L05 전치 · L07 자유변수 · L09 독립 · L12 결합행렬

배정된 쌍에서는 값어치가 잉여와 월세로 정확히 갈리고, 나머지 쌍에서는 옮길 마음이 없어야 하므로 부등식이 된다.

먼저 배정부터 확인하자. 값어치 표에서 대각선이 $12 + 8 + 7 = 27$ 이고, 나머지 다섯 배정은 22, 22, 20, 19, 18 로 전부 작다. 대각선이 최적이다.

이제 (28)에서 등식이 걸리는 쌍을 찾으면 $(1,1)$, $(2,1)$, $(2,2)$, $(3,1)$, $(3,3)$ 의 다섯이다. 이 다섯 줄을 미지수 여섯에 대해 쌓으면 $A$ 가 $5\times6$ 이고 각 행에 1이 정확히 둘 있다. 또 결합행렬이다.

(29)의 영공간 기저가 무엇인지 보자.

확인은 한 줄이면 된다. 어느 등식이든 $u_i + p_j$ 꼴이므로

이고, (31)의 좌변이 우변과 같으니 다섯 줄 전부가 그대로 유지된다.

곧 (30)의 뜻은 이렇다. 모든 잉여를 1씩 올리고 모든 월세를 1씩 내려도 아무 등식도 깨지지 않는다.

곧 남은 자유도 하나는 회사와 직원 사이의 이득 배분 그 자체다. 선형대수는 그것을 정해 주지 않는다.

총무팀이 "월세가 되도록 낮게"라고 했으니 그 방향으로 끝까지 밀면

이고, (32)에서 더 내리면 월세가 음수가 된다. 해 전체는

이다. (33)의 꼴이 L08의 “특수해 + 영공간” 그대로다.

검산. $u_1 + p_1 = 10 + 2 = 12 = v_{11}$ ✓. 그리고 직원 1이 둘째 집을 보면 $u_1 + p_2 = 10 + 0 = 10 \ge 5 = v_{12}$ 이므로 옮길 마음이 없다. 아홉 쌍 전부 확인하면 여유가 최소 0이다.

빠지기 쉬운 곳 — 부등식 조건 $\vv{p} \ge \vv{0}$ 이 자유도를 잘라 주는 것이지 선형계가 잘라 주는 것이 아니다. "되도록 낮게"라는 총무팀의 말이 $t$ 를 고르는 기준이었다. 4막에서 이 이야기를 본격적으로 한다.

회수 : L06 영공간 · L07 특수해 · L09 독립 · L12 결합행렬

두 가지 경제 법칙이 각각 하나씩 준다.

하나, 왈라스 법칙. 모든 값에서 $\vv{p}^{\mathsf T}\vv{z}(\vv{p}) = 0$ 이다. "사람들이 가진 돈만큼만 산다"는 뜻이다. 이것을 $\vv{p}$ 로 미분하고 균형에서 $\vv{z} = \vv{0}$ 을 넣으면

이다. (35)의 식은 $\vv{p}^{*}$ 가 좌영공간에 있다는 말이다.

둘, 0차 동차성. 모든 값에 같은 배율을 곱해도 수요가 안 바뀐다. 곧 $\vv{z}(\lambda\vv{p}) = \vv{z}(\vv{p})$ 다. 오일러 정리를 쓰면

이다. (36)의 식은 $\vv{p}^{*}$ 가 영공간에 있다는 말이다.

$\vv{p}^{*} = (1, 2, 3)$ 을 넣어 검산하면 둘 다 $\vv{0}$ 이 나온다. 그러므로 $\det J = 0$ 이고 $\rank J = 2$ 다. 연구원 말이 맞다.

이제 팀장의 둘째 물음이다. 아무거나 버려도 되는가. 셋째 값을 $p_3 = 3$ 으로 고정하고 남은 둘로 $2\times2$ 계를 만들면

가 나온다. 다른 줄을 버려도 마찬가지다. 세 경우의 행렬식이 각각 3, -6, 9 로 전부 0이 아니다. 이 표에서는 아무거나 버려도 된다.

한걸음 더 — 그런데 늘 그렇지는 않다. 어떤 재화의 균형가격이 0이면 (자유재라면) 이야기가 달라진다. $\vv{p}^{*} = (1, 2, 0)$ 인 표를 만들어 보면

이고 (38)도 $J'\vv{p}^{*} = J'^{\mathsf T}\vv{p}^{*} = \vv{0}$ 을 만족한다. 그런데 $p_3 = 0$ 을 고정하고 $2\times2$ 를 만들면 어느 줄을 버려도 행렬식이 0이다. 1행과 2행이 서로 비례하기 때문이다.

값이 0인 재화를 기준으로 잡으면 안 된다. 기준은 반드시 양의 값을 갖는 재화로 골라야 한다. 이것이 (37)의 답이 우연히 잘 된 이유이기도 하다.

회수 : L06 영공간 · L09 독립 · L10 좌영공간 · L14 직교

새 표를 이렇게 둔다.

(39)에서 왼쪽 대각행렬이 행을 늘리고 오른쪽이 열을 늘린다. 옛 표의 0인 칸은 0으로 남는다. 구조가 보존된다는 뜻이고, 이것이 이 방법의 값이다.

미지수는 $m + n = 4$ 개인데 자유도가 하나 모자란다. $(k\vv{r},\ \vv{s}/k)$ 가 같은 $Z$ 를 주기 때문이다.

조건도 넷인데 "행 합계의 총합 = 열 합계의 총합"이 이미 걸려 있어 독립인 것이 셋이다. (40)의 자유도와 딱 맞는다. 상황의 $m+n-1$ 이 여기서 또 나온다.

풀면 다음이 나온다.

(41)의 행 합이 $(40, 50)$, 열 합이 $(50, 40)$ 으로 발표값과 정확히 맞는다.

배율 자체는 유일하지 않다. $(\vv{r}, \vv{s})$ 를 $(4, 2)$ 와 $(\frac12, \frac14)$ 로 바꿔도 같은 $Z$ 가 나온다. 정해지는 것은 곱 $r_i s_j$ 뿐이다.

실무에서 푸는 법. 비선형계를 직접 풀지 않고 행과 열을 번갈아 맞춘다.

회당 오차가 약 $1/100$ 로 줄어 세 번이면 소수 넷째 자리까지 맞는다. 이것을 RAS 법이라 부른다.

빠지기 쉬운 곳 — 옛 표에 0인 칸이 있으면 새 표에서도 0이다. 만약 옛 표가 $\begin{bmatrix}10&0\\0&40\end{bmatrix}$ 이었다면 행 합이 $(10r_1, 40r_2)$ 이고 열 합이 $(10r_1, 40r_2)$ 라 행 합과 열 합이 같을 수밖에 없다. 목표가 $(40,50)$ 과 $(50,40)$ 이면 $40 = 50$ 이라는 모순이 되어 답이 없다.

회수 : L03 대각행렬 곱 · L05 전치 · L09 자유도 세기

미지수 9개, 방정식 6줄인데 총합이 양쪽에서 같아야 하므로 독립인 것이 5줄이다.

(42)의 $(m-1)(n-1)$ 이 일반 공식이다. 일반적으로 세어 보면

이고, (43)의 $m+n-1$ 이 (27)에서 본 그 수다. 합계를 만드는 사상의 랭크가 늘 $m+n-1$ 이다.

$3\times3$ 이면 $2\times2 = 4$ 차원어치를 정할 수 없다.

영공간의 기저가 보기 좋다. $i, j$ 가 1 또는 2일 때

인 네 개다. 예로 $i=j=1$ 이면

이고 (45)의 행 합도 열 합도 전부 0이다. 이만큼을 더해도 합계가 안 바뀐다.

연구자의 둘째 물음에 답한다. 반례를 만들 수 있다.

(46)의 두 표는 여섯 합계가 모두 60으로 같은데 아홉 칸 중 넷이 다르다. $Z' = Z + 5E_{11}$ 이기 때문이다.

한걸음 더 — 그러면 아예 손을 놓아야 하는가. 아니다. 두 가지가 남는다. 하나는 칸이 음수가 아니라는 조건이 범위를 좁혀 준다는 것이고, 다른 하나는 옛 표라는 추가 정보를 넣는 것이다. 그게 상황의 RAS 법이었다.

정보가 모자랄 때 답은 "못 푼다"가 아니라 "무엇을 더 가져올 것인가"다.

회수 : L06 영공간 · L07 자유변수 · L09 차원 · L10 네 부분공간

먼저 상황을 정직하게 적자. 미지수 셋에 줄 하나다. 해집합이 평면이다. 선형대수는 여기서 할 말이 없다.

우리가 기준을 만든다. "흔들림이 가장 작게"를 고르면 최소화 대상이 정해진다.

(48)의 목적함수가 이차형식이다. L27에서 배운 그 이차형식이고, $S$ 가 양의 정부호이므로 최솟값이 존재한다(고윳값이 $0.586, 2, 3.414$ 로 전부 양수다).

제약 아래 최소를 찾는 조건을 쓴다. 라그랑주 승수 $\lambda$ 를 붙이면

이고, (49)의 두 조건을 한 행렬에 쌓으면 $4\times4$ 테두리 계가 된다.

(50)의 왼쪽 위가 $2S$ 이고 테두리가 제약이다. 미지수가 넷으로 늘었지만 줄도 넷이라 상자 1이 됐다.

닫힌 꼴로도 쓸 수 있다. (49)의 첫 줄을 $\vv{w}$ 에 대해 풀면

이고, (51)의 식을 둘째 줄 $\vv{1}^{\mathsf T}\vv{w} = 1$ 에 넣으면

이다. (52)의 값을 다시 (51)에 넣으면 $\lambda$ 가 사라지고

이다. $\det S = 4$ 이고

이므로 (54)에서 $\vv{1}^{\mathsf T}S^{-1}\vv{1} = 1$ 이고 답이 그대로 나온다.

가운데 자산에 0을 준다. 1번과 3번이 서로 무관해서 둘을 반씩 섞으면 흔들림이 가장 잘 상쇄되기 때문이다.

검산. 균등배분 $(\frac13,\frac13,\frac13)$ 은 $\frac{10}{9} = 1.111$, 가운데를 공매도한 $(1,-1,1)$ 은 2 로 둘 다 1보다 크다.

후보를 고를 때 성분합이 1인지 먼저 확인해야 한다. $(1,-1,0)$ 처럼 합이 0인 것은 애초에 비교 대상이 아니다. 돈을 다 넣지 않은 배분이기 때문이다.

빠지기 쉬운 곳 — $\vv{w}$ 에 음수가 나올 수 있다. 여기서는 안 나왔지만 공분산이 조금만 달라도 나온다. 공매도가 안 되는 계좌라면 $\vv{w} \ge \vv{0}$ 을 넣어야 하고, 그러면 이차계획이 되어 이 책 밖이다.

회수 : L03 역행렬 · L08 유일해 · L25 대칭 · L27 양의 정부호

요금이 $x_1^2 + 2x_2^2 + 2x_3^2$ 이므로 이차형식으로 쓰면 계수행렬이 $Q = \operatorname{diag}(2, 4, 4)$ 다(2계 도함수라 두 배가 붙는다).

정류 조건과 제약을 블록으로 쌓으면 KKT 계가 된다.

(57)의 계를 풀면

이다. 요금은 $36 + 18 + 18 = 72$ 만원으로 반장의 144보다 훨씬 싸고 균등배분의 80보다도 싸다.

왜 $(6,3,3)$ 인가. 정류 조건 $Q\vv{x} = -\lambda\vv{1}$ 을 성분으로 보면 $2x_1 = 4x_2 = 4x_3 = 12$ 다. 곧 한계비용이 세 라인에서 같아야 한다. 싼 라인에 더 보내되, 제곱이라 무한정 보낼 수는 없다.

이 점이 정말 최소인가. $N(\vv{1}^{\mathsf T})$ 의 기저를 열로 세워 $Z = \begin{bmatrix}-1&-1\\1&0\\0&1\end{bmatrix}$ 로 두면

이고 (60)의 둘 다 양수다. 제약 위에서 곡률이 양수이므로 최소점이다. $Q$ 자체가 양의 정부호이니 이 확인은 사실 필요 없지만, 다음 문제에서는 필요하다.

회수 : L07 영공간의 기저 · L18 행렬식 · L25 대칭 · L27 정부호

가격이 같으므로 $\vv{p} = (1,1,1)$ 이고, 예산을 유지하며 갈 수 있는 방향은 $\vv{p}^{\mathsf T}\vv{v} = 0$ 인 것들, 곧 $N(\vv{p}^{\mathsf T})$ 로 2차원이다.

기저를 $\vv{z}_1 = (1,-1,0)$, $\vv{z}_2 = (1,0,-1)$ 로 잡아 $Z = \begin{bmatrix}1&1\\-1&0\\0&-1\end{bmatrix}$ 로 세운다. 그러면

성분을 하나만 손으로 확인해 보자. $(1,1)$ 자리는

이고, $(1,2)$ 자리는 $\vv{z}_1^{\mathsf T}H\vv{z}_2 = (1,-1,0)\cdot(1,0,3) = 1$ 이다. (63)의 계산이 (62)의 행렬 첫 칸과 맞는다.

그 행렬이 축소 헤시안이다. 예산평면 위에서의 곡률이다.

고윳값을 구하면 -1 과 -3 으로 둘 다 음수다. 곧 어느 방향으로 가도 만족이 줄어든다. 이 점은 최대점이 맞다.

검산 두 가지. 커피를 $t$ 늘리고 빵을 $t$ 줄이면 $\vv{v} = (1,-1,0)$ 이고

커피를 $t$ 늘리고 빵과 우유를 $\frac t2$ 씩 줄이면 $\vv{v} = (1,-\frac12,-\frac12)$ 이고

(65)의 손해가 (64)보다 작다. 손해를 나눠 지면 덜 아프다. 그래도 여전히 음수다.

같은 판정을 행렬식으로도 할 수 있다. 유테두리 행렬을 만들면

이고 (66)의 부호가 $+, -$ 로 번갈아 간다. 이것이 제약 아래 최대의 부호 규칙이다. 다만 규칙을 외우기보다 $Z^{\mathsf T}HZ$ 로 환원하는 편이 안전하다.

회수 : L06 영공간 · L18 행렬식 · L19 여인수 · L27 정부호

배출은 총산출에서 나오고 총산출은 최종수요에서 나온다. 두 단계를 이으면

이고, (67)의 $\vv{a}$ 가 유발 배출계수다. 계산하면

이다. (68)의 계수가 뜻하는 바가 재미있다. 제조와 서비스는 직접 오염을 전혀 안 내는데도 유발계수가 12와 16이다. 그들이 농림 제품을 쓰기 때문이다.

조건은 한 줄뿐이다.

(69)의 줄은 $1\times3$ 행렬이라 랭크 1, 영공간 2차원이다. 기저는 $(-3, 7, 0)$ 과 $(-4, 0, 7)$ 이고, 해집합이 평면 전체다.

기준을 정한다. "어느 부문에도 치우치지 않게"를 노름 최소로 옮기면 답이 유일해진다. L33의 최소노름 해다.

왜 답이 $\vv{a}$ 방향인지는 한 줄로 나온다. 해를 $\vv{d} = t\,\vv{a} + \vv{n}$ ($\vv{n} \in N(\vv{a}^{\mathsf T})$) 으로 쪼개면 두 조각이 직교하므로

이고, (70)에서 $\vv{n}$ 은 목표에 아무 기여도 안 하면서 노름만 키운다. 그러니 $\vv{n} = \vv{0}$ 으로 두는 것이 최소다.

(71)의 검산은 $28(7) + 12(3) + 16(4) = 196 + 36 + 64 = 296$ 이다. 노름 제곱이 $49+9+16 = 74$ 다.

다른 후보와 견줘 본다.

검산 한 번 더. $\vv{d}^{*}$ 를 넣으면 총산출이 $(29.6,\ 21.6,\ 18.8)$ 이고 배출이 $10 \times 29.6 = 296$ 으로 정확히 맞는다.

빠지기 쉬운 곳 — 최소노름이 “옳은” 답이 아니다. 단지 우리가 고른 기준일 뿐이다. "기존 수요에서 가장 적게 바뀌게"를 기준으로 삼으면 다른 답이 나오고, 그것도 똑같이 정당하다. 다섯째 칸에 그것을 적어야 한다.

회수 : L07 영공간 · L08 해집합 · L09 차원 · L33 최소노름 해

낮음을 -1, 높음을 +1 로 코드화하고 열을 (상수항, A, B, C)로 세운다. 세 가지 선택을 견줘 보자.

선택 1 — $(+,-,-)$, $(-,+,-)$, $(-,-,+)$, $(+,+,+)$

(72)에서 네 열이 서로 직교다. 상황의 $8I$ 와 같은 구조다.

선택 2 — 전부 낮음에서 시작해 하나씩만 올린다

(73)의 값을 보려면 1행을 나머지에서 빼면 된다. $(0,2,0,0)$, $(0,0,2,0)$, $(0,0,0,2)$ 가 되어 행렬식이 $1 \times 2^3 = 8$ 이다.

선택 3 — 냉각을 네 번 다 "높음"으로 둔다

(74)의 값이 0인 이유가 명확하다. 냉각 열이 상수항 열과 똑같다. 열이 종속이므로 냉각 효과와 전체 평균을 갈라낼 수 없다.