부등식의 영역과 경제
본문가구 공방은 하루에 목재 100단위와 작업 시간 80시간을 쓸 수 있다. 책상 하나에는 목재 2단위와 1시간, 의자 하나에는 목재 1단위와 2시간이 든다. 책상 하나는 40만 원, 의자 하나는 30만 원의 이익을 낸다. 목재와 시간이 모자라지 않는 범위에서 이익을 가장 크게 하려면 몇 개씩 만들어야 할까?
2.6.1제약 조건과 실행 가능 영역
책상을 \(x\)개, 의자를 \(y\)개 만든다고 하자. 목재 조건은 \(2x + y \le 100\), 시간 조건은 \(x + 2y \le 80\)이고, 개수는 음수가 될 수 없으므로 \(x \ge 0\), \(y \ge 0\)이다. 이 부등식들을 모두 만족하는 점 \((x, y)\)의 영역이 가능한 생산 계획 전체이다. 영역은 네 꼭짓점 \((0, 0)\), \((50, 0)\), \((40, 20)\), \((0, 40)\)을 가진 볼록한 사각형이다.
일차부등식들로 둘러싸인 볼록한 다각형 영역에서 일차식 \(ax + by\)의 최댓값과 최솟값은 다각형의 꼭짓점에서 나타난다.
이익 \(40x + 30y = k\)는 기울기가 \(-\dfrac{4}{3}\)인 직선이고, \(k\)가 커질수록 위로 평행이동한다. 이 직선이 영역과 만나는 동안 \(k\)를 최대한 키우면, 직선이 영역의 한 꼭짓점에 마지막으로 닿는다. 그래서 꼭짓점만 비교하면 된다. 이런 문제를 선형계획법이라 한다. 영역 안쪽의 점은 모든 방향으로 조금씩 움직일 수 있어 이익을 더 늘릴 여지가 있으므로 최적이 될 수 없다.1
2.6.2이익이 바뀌면 답도 바뀐다
그림 1에서 책상의 이익을 바꾸어 보자. 책상 이익이 15만 원보다 작으면 이익 직선이 완만해져 의자만 만드는 \((0, 40)\)이, 60만 원보다 크면 가팔라져 책상만 만드는 \((50, 0)\)이 최적이 된다. 그 사이에서는 두 조건이 모두 빠듯해지는 \((40, 20)\)이 최적이다. 이익 직선의 기울기가 영역의 변의 기울기를 넘어설 때마다 최적의 꼭짓점이 옮겨 간다.
2.6.3예제 풀이
위 공방에서 책상 이익이 40만 원, 의자 이익이 30만 원일 때 이익을 최대로 하는 생산량과 그때의 이익을 구하여라. 이때 목재와 시간이 남는가?
꼭짓점 \((40, 20)\)은 \(2x + y = 100\)과 \(x + 2y = 80\)을 연립하여 얻는다. 첫 식에 2를 곱해 둘째 식을 빼면 \(3x = 120\), 곧 \(x = 40\), \(y = 20\)이다.
네 꼭짓점의 이익은 \(0\), \(2000\), \(2200\), \(1200\)만 원이므로 책상 40개, 의자 20개를 만들 때 최대 2200만 원이다. 이때 목재는 \(80 + 20 = 100\), 시간은 \(40 + 40 = 80\)으로 둘 다 남김없이 쓴다. 두 자원이 모두 빠듯하게 쓰이는 점이 최적이 된 것이다. 남는 자원이 있다면 그것으로 무언가를 더 만들어 이익을 늘릴 수 있었을 것이다.
아래 탐구 카드에서 가구 생산 계획과 가장 싼 아침 식단을 부등식의 영역으로 직접 찾아보자.
- 선형계획법은 제2차 세계 대전 무렵 군수 물자의 수송 계획을 세우며 발전했다. 오늘날에는 항공사의 운항 계획, 공장의 생산 계획, 영양 식단 설계 등에 쓰인다.
자원의 제약은 연립 일차 부등식이 되고, 이를 만족하는 영역이 가능한 계획 전체이다. 이 영역에서 이익 같은 일차식의 최댓값과 최솟값은 꼭짓점에서 나타나므로, 꼭짓점의 값만 비교하면 된다. 그래서 처음 질문의 공방은 목재와 시간을 모두 빠듯하게 쓰는 책상 40개, 의자 20개에서 이익이 가장 크다.