기초수학선형계획법#329

선형계획법

Linear Programming

선형계획법은 일차 제약을 만족하는 범위에서 일차 목적함수를 최적화한다. 비어 있지 않은 경계를 포함한 유계 다각형에서 꼭짓점 비교의 이유를 살피고, 비용 최소화·복수 최적해·최적값 부재·정수 조건을 구별한다.

주인공 기호
Z
읽는 시간
약 8분
선수 개념
부등식의 영역

직관 — 만들 수 있는 것 중 무엇을 고를까?

직관

자원 조건을 만족하는 생산 조합은 여러 개다. 같은 자원을 쓰더라도 두 제품의 판매 가격이 다르면 수입도 달라진다. 먼저 가능한 조합을 모은 뒤, 비교할 목표를 숫자로 정하자.

가능한 조합의 모임은 부등식의 영역에서 구한 가능 영역이고, 비교할 숫자는 목적함수다. 이번에는 그 영역 안에서 목표를 가장 크게 또는 작게 하는 점을 찾는다. 이름의 '계획법(programming)'은 컴퓨터 프로그래밍이 아니라 자원 배분의 계획을 세운다는 뜻이다.

선형계획법은 일차 목표를 일차 제약 아래에서 최적화한다

선형계획법은 일차식으로 표현한 목적함수를 일차 제약 아래에서 최대 또는 최소로 만드는 방법이다. 목적함수는 비교할 수입·비용 같은 양이고, 제약조건은 허용되는 선택을 정하는 조건이다. 이 글에서는 실수인 두 변수의 문제를 그림으로 다룬다.

Z=ax+by.(1)Z=ax+by. \tag{1}
정의
기호이름원어뜻
x,yx,y결정변수decision variables하루 생산할 A, B의 L 수
ZZ목적함수objective function비교할 하루 수입의 만원 수
a,ba,b단위 수입unit revenueA, B 1L를 팔 때의 만원 수
RR가능 영역feasible region제약을 모두 만족하는 생산 조합

가상 액체 공장은 A 1L와 B 1L를 각각 3만원, 2만원에 판매한다. 식 (1)에서 a=3,b=2a=3,b=2인 경우다. 허용 범위의 생산량은 모두 이 고정 가격으로 팔린다고 가정한다. 이 글의 목표는 수입이며, 비용을 빼지 않은 수입을 이윤이라고 부르지 않는다.

최대화할 수입Z=3x+2y,R: x≥0, y≥0, x+y≤6, 2x+y≤8.(2)\begin{gathered} \text{최대화할 수입}\quad Z=3x+2y,\\ R:\ x\ge0,\ y\ge0,\ x+y\le6,\ 2x+y\le8. \end{gathered} \tag{2}

자원 제약은 앞 글과 같아 꼭짓점은 (0,0),(4,0),(2,4),(0,6)(0,0),(4,0),(2,4),(0,6)이다. 목적함수만 보고 A를 계속 늘릴 수는 없다. A 1L가 기계 시간을 B의 두 배로 쓰기 때문이다.

같은 수입의 직선을 움직이면 무엇이 보이나요?

수입이 같은 점들을 이은 직선을 위로 밀어 올리다 가능 영역에 마지막으로 닿는 점이 최대 수입의 후보다. 수입이 kk인 모든 점은 3x+2y=k3x+2y=k 위에 있고, 이런 직선을 등위선이라고 한다. yy로 풀면 다음과 같다.

y=−32x+k2.(3)y=-\frac32x+\frac{k}{2}. \tag{3}

kk를 키우면 기울기 −32-\frac32는 그대로이고 yy절편 k2\frac k2만 커져 위로 평행이동한다. 그림 1에서 k=10,12k=10,12의 직선은 영역을 가로지르고, k=14k=14의 직선은 (2,4)(2,4) 한 점에서만 닿는다. 그보다 큰 kk의 직선은 가능 영역과 만나지 않는다.

가상 공장의 가능 영역에서 수입 등위선 3x+2y=k를 k=10,12,14로 옮겼다. 마지막 접촉점 (2,4)의 수입 14만원이 최대이고, 경계 위 여러 점이 가능한지와 목표값이 큰지는 별개의 문제다.
그림 1 가상 공장의 가능 영역에서 수입 등위선 3x+2y=k를 k=10,12,14로 옮겼다. 마지막 접촉점 (2,4)의 수입 14만원이 최대이고, 경계 위 여러 점이 가능한지와 목표값이 큰지는 별개의 문제다. figures/objective_lines.py

왜 하필 (2,4)(2,4)인지는 직선의 기울기로 설명된다. 등위선의 기울기 −32-\frac32는 기계 경계 2x+y=82x+y=8의 기울기 −2-2와 재료 경계 x+y=6x+y=6의 기울기 −1-1 사이에 있다. 그래서 등위선은 두 경계가 만나는 모서리 (2,4)(2,4)에 마지막으로 걸린다.

왜 꼭짓점의 값만 비교할 수 있나요?

가능 영역이 비어 있지 않고 경계를 포함한 유계 다각형이면, 일차 목적함수의 최댓값과 최솟값은 각각 어느 꼭짓점에서 나타난다. 선분 위에서 일차식의 값은 언제나 두 끝값 사이에 있어, 선분 중간이 두 끝보다 커질 수 없기 때문이다. 유계라는 말은 영역이 사방으로 끝없이 뻗지 않는다는 뜻이다.

선분 중간의 점은 두 끝점 좌표를 같은 비율로 섞은 값이고, 일차식에 넣은 값도 두 끝점의 목표값을 같은 비율로 섞은 값이다. 예를 들어 (4,0)(4,0)과 (2,4)(2,4)의 가운데 (3,2)(3,2)의 수입은 3×3+2×2=133\times3+2\times2=13으로, 두 끝값 12와 14의 평균이다.

그림 2는 영역의 둘레를 (0,0)(0,0)에서 출발해 한 바퀴 돌며 수입을 잰 것이다. 변 위에서는 값이 직선으로 변하고 꺾이는 곳은 꼭짓점뿐이라, 가장 높은 점 14는 꼭짓점 (2,4)(2,4)에 있다.

식 (2)의 가능 영역 둘레를 (0,0)→(4,0)→(2,4)→(0,6)→(0,0) 순서로 돌며 Z=3x+2y를 잰 값이다. 각 변에서 Z는 두 끝값 사이를 직선으로 잇고, 변 (4,0)–(2,4)의 가운데 (3,2)에서는 12와 14의 평균 13이다.
그림 2 식 (2)의 가능 영역 둘레를 (0,0)→(4,0)→(2,4)→(0,6)→(0,0) 순서로 돌며 Z=3x+2y를 잰 값이다. 각 변에서 Z는 두 끝값 사이를 직선으로 잇고, 변 (4,0)–(2,4)의 가운데 (3,2)에서는 12와 14의 평균 13이다. figures/boundary_values.py

영역 안쪽의 점도 마찬가지다. 안쪽 점을 지나는 선분을 그으면 양 끝이 경계에 닿고, 그 끝점 가운데 적어도 하나의 목표값은 안쪽 점보다 크거나 같다. 그 경계점이 변의 중간이라면 같은 이유로 변의 끝인 꼭짓점까지 갈 수 있다. 최솟값도 부등호를 바꾸어 같은 논리로 설명한다.

식 (2)의 꼭짓점을 계산하면 다음과 같다.

(x,y)(x,y)수입 3x+2y3x+2y (만원/일)
(0,0)(0,0)00
(4,0)(4,0)1212
(2,4)(2,4)6+8=146+8=14
(0,6)(0,6)1212

최댓값은 A 2L·B 4L에서 14만원/일이다. 두 자원 조건을 더하면 표를 거치지 않고도 상한을 검산할 수 있다.

Z=(x+y)+(2x+y)≤6+8=14.(4)Z=(x+y)+(2x+y)\le6+8=14. \tag{4}

등호가 성립하려면 두 자원식을 동시에 등호로 만족해야 한다. 그 교점이 (2,4)(2,4)이므로 이 예에서는 최적 생산 조합도 하나다. 꼭짓점 표는 네 점을 비교했고, 식 (4)는 영역 전체에서 14를 넘지 못하는 이유를 보인다.

최적해가 여러 개이거나 아예 없을 수도 있나요?

그렇다. 등위선이 영역의 변과 평행하면 그 변 전체가 최적해이고, 영역이 끝없이 뻗거나 경계가 빠지면 최댓값이 없을 수 있다.

같은 영역에서 목표가 Z1=x+yZ_1=x+y라면 최댓값은 6이다. 그림 3에서 x+y=6x+y=6의 등위선은 (0,6)(0,6)과 (2,4)(2,4)를 잇는 변과 겹친다. 그 선분의 모든 점이 최적해이므로, 두 꼭짓점만 답이라고 쓰면 나머지 최적해를 놓친다.

식 (2)와 같은 가능 영역에서 목표 x+y의 등위선 k=2, 4, 6을 그렸다. k=6의 직선이 변 (0,6)–(2,4)와 겹쳐 굵게 표시한 변 전체에서 최댓값 6이 나온다.
그림 3 식 (2)와 같은 가능 영역에서 목표 x+y의 등위선 k=2, 4, 6을 그렸다. k=6의 직선이 변 (0,6)–(2,4)와 겹쳐 굵게 표시한 변 전체에서 최댓값 6이 나온다. figures/multiple_optima.py

반면 x,y≥0x,y\ge0만으로 x+yx+y를 최대화하면 얼마든지 큰 값을 만들 수 있어 최댓값이 없다. 0≤x<10\le x<1, y=0y=0에서 xx를 최대화하면 1에 가까워져도 1은 허용되지 않아 역시 최댓값이 없다. 영역이 비어 있으면 비교할 점 자체가 없다. 그래서 꼭짓점 비교 전에 조건부터 읽는다.

비용을 최소로 하는 선형계획법은 어떻게 푸나요?

비용 최소화도 같은 방법으로, 등위선을 원점 쪽으로 내리다 영역에 마지막으로 닿는 꼭짓점을 찾는다. 이때 제약은 보통 '얼마 이상'이라 영역이 바깥으로 끝없이 열린다.

가상 농장에서 사료 A와 B를 섞는다고 하자. A 1kg에는 단백질 1단위·칼슘 1단위, B 1kg에는 단백질 1단위·칼슘 3단위가 들어 있다. 하루에 단백질 5단위, 칼슘 9단위 이상이 필요하고, 값은 A가 1kg에 2천원, B가 3천원이다.

최소화할 비용C=2x+3y,x≥0, y≥0, x+y≥5, x+3y≥9.(5)\begin{gathered} \text{최소화할 비용}\quad C=2x+3y,\\ x\ge0,\ y\ge0,\ x+y\ge5,\ x+3y\ge9. \end{gathered} \tag{5}

두 경계의 교점은 x+3y=9x+3y=9에서 x+y=5x+y=5를 빼 2y=42y=4, 곧 (3,2)(3,2)다. 꼭짓점 (0,5),(3,2),(9,0)(0,5),(3,2),(9,0)의 비용은 각각 15, 12, 18천원이다. 그림 4에서 C=12C=12의 등위선은 (3,2)(3,2)에서만 영역에 닿는다.

단백질 x+y≥5, 칼슘 x+3y≥9와 비음수 조건이 만드는 위로 열린 가능 영역이다. 비용 등위선 2x+3y=12는 꼭짓점 (3,2)에서만 닿고, C=18의 직선은 영역을 가로지른다.
그림 4 단백질 x+y≥5, 칼슘 x+3y≥9와 비음수 조건이 만드는 위로 열린 가능 영역이다. 비용 등위선 2x+3y=12는 꼭짓점 (3,2)에서만 닿고, C=18의 직선은 영역을 가로지른다. figures/cost_minimum.py

이 영역은 유계가 아니므로 꼭짓점 정리를 그대로 쓸 수 없다. 대신 두 조건에 알맞은 양수를 곱해 더하면 영역 전체의 하한을 보일 수 있다.

C=32(x+y)+12(x+3y)≥32×5+12×9=12.(6)C=\tfrac32(x+y)+\tfrac12(x+3y)\ge\tfrac32\times5+\tfrac12\times9=12. \tag{6}

따라서 최소 비용은 A 3kg·B 2kg을 섞을 때 12천원이다. 반대로 비용의 최댓값은 없다. 사료를 얼마든지 더 살 수 있기 때문이다.

정수 개수만 가능하면 연속 해를 반올림해도 되나요?

아니다. 반올림한 점이 제약을 어기거나, 정수 좌표 중 최선이 아닐 수 있다. 개수 문제라면 영역 안의 정수 좌표를 다시 비교해야 한다.

2x+2y≤52x+2y\le5, x,y≥0x,y\ge0에서 3x+2y3x+2y의 연속 최댓값은 꼭짓점 (2.5,0)(2.5,0)의 7.5다. 그림 5에서 xx를 반올림한 (3,0)(3,0)은 6>56>5라 영역 밖이다. 정수 좌표는 x+y≤2x+y\le2인 6개뿐이고, 그중 최댓값은 (2,0)(2,0)의 6이다.

2x+2y≤5인 삼각형 영역의 정수 좌표 6개를 채운 점으로 표시하고, 그중 정수 최댓값 6이 나오는 (2,0)에 고리를 둘렀다. 연속 최댓값 7.5는 꼭짓점 (2.5,0)에서 나오지만, 반올림한 (3,0)은 영역 밖이고 (2,0)은 꼭짓점이 아니다.
그림 5 2x+2y≤5인 삼각형 영역의 정수 좌표 6개를 채운 점으로 표시하고, 그중 정수 최댓값 6이 나오는 (2,0)에 고리를 둘렀다. 연속 최댓값 7.5는 꼭짓점 (2.5,0)에서 나오지만, 반올림한 (3,0)은 영역 밖이고 (2,0)은 꼭짓점이 아니다. figures/integer_rounding.py

(2,0)(2,0)은 원래 연속 삼각형의 꼭짓점도 아니다. 꼭짓점 비교는 실수 변수의 정리이고, 정수 조건이 붙으면 후보를 따로 세어야 한다.

핵심

선형계획법에서 실수 변수의 가능 영역이 비어 있지 않은 닫힌 유계 다각형이면 일차 목적함수의 최적값은 꼭짓점에서 찾을 수 있다. 변 전체가 최적일 수 있고, 열린 경계·무한 영역·정수 조건은 따로 확인한다.

선형계획법에서는 무조건 단가가 큰 상품만 만들면 되나요?

아니다. 단가뿐 아니라 제품마다 쓰는 자원이 다르다. A만 만들면 기계 시간 제약 때문에 4L가 한도여서 수입은 12만원이다. A 2L·B 4L를 섞으면 14만원이 된다.

선형계획법에서 판매 가격이 바뀌면 최적해도 바뀌나요?

가격의 비가 일정 범위를 벗어날 때만 바뀐다. B 단가가 2만원일 때 A 단가 aa가 2 이상 4 이하이면 등위선 기울기 −a2-\frac a2가 −2-2와 −1-1 사이여서 (2,4)(2,4)가 계속 최적이다. a=5a=5이면 (4,0)(4,0)의 20만원이 (2,4)(2,4)의 18만원보다 커서 최적해가 옮겨 가고, a=4a=4나 a=2a=2이면 한 변 전체가 최적이 된다.

선형계획법은 변수가 셋 이상이어도 쓸 수 있나요?

그렇다. 변수가 셋이면 가능 영역이 공간의 다면체가 되고, 유계이고 비어 있지 않으면 최적값은 역시 꼭짓점에서 찾는다. 다만 그림으로 풀 수 있는 것은 이 글처럼 변수가 둘일 때이고, 꼭짓점이 4개인 이 공장 문제와 달리 큰 문제는 심플렉스법 같은 계산 절차로 꼭짓점을 따라 이동하며 푼다.

선형계획법에서 생기기 쉬운 오해

  • 경계선 교점이면 모두 후보로 채택한다. — (6,0)(6,0)은 x+y=6x+y=6 위에 있어도 2x+y≤82x+y\le8을 어긴다. 가능 영역의 꼭짓점인지 먼저 검산한다.
  • 최댓값 14가 생산량이다. — 이 모형의 14는 만원/일 단위의 수입이고, 생산 결정은 A 2L·B 4L다.
  • 이차식 목표도 꼭짓점만 보면 된다. — 위 논리는 일차식이 선분 위에서 고르게 변한다는 데 근거한다. 목표가 −(x−1)2−(y−1)2-(x-1)^2-(y-1)^2이면 최댓값 0은 꼭짓점이 아닌 안쪽 점 (1,1)(1,1)에서 나온다.

직접 해보기

  1. 가상 공장에서 x,y≥0x,y\ge0, 3x+y≤93x+y\le9, x+2y≤8x+2y\le8일 때 일차 수입 Z=4x+3yZ=4x+3y의 최댓값과 생산 조합을 구하라. x,yx,y는 연속적인 kg 수, 수입은 만원/일이다.
  2. 1번의 답을 두 제약에 대입하고, 각 자원이 얼마나 남는지 구하라.
  3. 같은 영역에서 목표를 Z1=3x+yZ_1=3x+y로 바꾸면 최댓값과 최적해 전체는 무엇인가?
  4. 제품 개수인 비음수 정수 x,yx,y에 대해 2x+2y≤72x+2y\le7이고 수입이 5x+3y5x+3y다. 연속 해와 정수 해를 구별해 최대 수입을 구하라.
  5. x,y≥0x,y\ge0, x+y≥4x+y\ge4, x+2y≥6x+2y\ge6일 때 비용 C=3x+4yC=3x+4y의 최솟값과 그때의 (x,y)(x,y)를 구하고, 식 (6)처럼 두 조건을 더해 하한을 검산하라.
답과 풀이
  1. 두 자원 경계의 교점은 y=9−3xy=9-3x를 대입해 x+2(9−3x)=8x+2(9-3x)=8, x=2,y=3x=2,y=3이다. 가능 꼭짓점 (0,0),(3,0),(2,3),(0,4)(0,0),(3,0),(2,3),(0,4)에서 목표값은 각각 0,12,17,120,12,17,12다. A 2kg·B 3kg에서 17만원/일이 최대다.
  2. 3×2+3=93\times2+3=9, 2+2×3=82+2\times3=8이므로 두 자원 모두 남지 않는다.
  3. 첫 제약 때문에 최대 9이며 (3,0)(3,0)과 (2,3)(2,3)을 잇는 선분 전체에서 달성한다. 즉 2≤x≤32\le x\le3, y=9−3xy=9-3x인 모든 점이다. 이 범위에서 다른 제약도 만족한다.
  4. 연속량이면 x+y≤3.5x+y\le3.5이고 5x+3y≤5(x+y)≤17.55x+3y\le5(x+y)\le17.5이므로 (3.5,0)(3.5,0)에서 17.5다. 정수이면 x+y≤3x+y\le3이므로 5x+3y≤155x+3y\le15이며 (3,0)(3,0)에서 15를 얻는다. 정수 조건을 붙인 뒤의 최댓값은 15다.
  5. 두 경계의 교점은 x+2y=6x+2y=6에서 x+y=4x+y=4를 빼 y=2y=2, 곧 (2,2)(2,2)다. 꼭짓점 (0,4),(2,2),(6,0)(0,4),(2,2),(6,0)의 비용은 16,14,1816,14,18이므로 최솟값은 (2,2)(2,2)의 14다. C=2(x+y)+(x+2y)≥2×4+6=14C=2(x+y)+(x+2y)\ge2\times4+6=14로 영역 전체에서도 확인된다.

더 읽기

  • 교육부 2022 개정 수학과 교육과정 — [12경수02-06]에서 부등식 영역과 관련된 경제 최대·최소는 일차식으로 다룸을 확인했다.
  • Feras Awad, Linear Programming 강의노트 — 1.5절, 인쇄 26–29쪽의 꼭짓점 정리와 선분에서 일차 목표값이 끝점 값 사이에 있다는 논증을 읽었다. 고차원 정리와 심플렉스법은 질문 블록에서 이름과 역할만 소개했다.

영상 노트

영상 노트
  • 00:00 단가가 더 큰 상품만 만들면 가장 좋을까?
  • 00:40 식 (2)에서 제약과 목표를 분리하기
  • 01:30 식 (3)의 등위선을 그림 1에서 평행이동하고 경계의 기울기와 비교하기
  • 02:30 그림 2의 둘레 그래프와 꼭짓점 표, 식 (4)의 전체 상한으로 최대 검산하기
  • 03:40 그림 3에서 변 전체가 최적인 경우와 최댓값이 없는 경우
  • 04:30 식 (5)·(6)과 그림 4로 사료 비용 최소화
  • 05:30 그림 5에서 반올림이 실패하는 정수 생산

지도에서의 위치

완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 자원 제약·일반 이유·새 경제 연습 집필
  2. 2026-11-17 · 전수 검수 반영 — 최댓값·최솟값 표기 교정, 등위선과 경계의 기울기 비교, 둘레를 따른 목표값 그림, '이상' 조건의 비용 최소화 절과 그 하한 검산, 정수 조건 절과 그 그림의 정답·위반 색 구분, 단가 변화·변수 셋 이상 질문, 해보기 5문항 (에이전트 수정, 그림 1→5)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림