선형계획법 — 심플렉스법과 그래프 해법

선형계획법은 최대 이익이나 최소 비용처럼 선형인 목적함수의 최적값을, 선형 제약조건 아래에서 찾는 방법입니다. 변수가 두 개인 문제에서는 그래프 해법으로 가능영역을 찾고 그 꼭짓점을 확인합니다. 더 큰 문제에서는 심플렉스법이 같은 꼭짓점 아이디어를 대수적으로 사용합니다.

목적함수와 제약조건이 모두 선형일 때만 선형계획법을 사용해야 합니다. 관계가 휘어지거나 곡선이 되거나, $xy$ 같은 곱에 의존하면 그 모형은 선형계획 문제가 아닙니다.

선형계획법의 정의

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

제약조건은 예를 들어 다음과 같습니다.

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

이와 비슷한 선형부등식들이 더해지고, 음수 값이 의미가 없을 때는 $x_i \ge 0$ 같은 조건도 함께 붙습니다.

모든 제약조건을 만족하는 점들의 집합을 가능영역이라고 합니다. 선형계획법은 이렇게 묻습니다. 가능한 점들 가운데 어떤 점이 목적함수의 최적값을 주는가?

그래프 해법은 어떻게 작동할까

의사결정변수가 두 개뿐이라면 각 제약조건을 $xy$-평면에 그릴 수 있습니다. 허용되는 영역들이 겹치는 부분이 가능영역입니다.

그 영역 안의 모든 점은 유효한 해입니다. 목적함수는 각 점에 하나의 값을 대응시킵니다.

선형계획법에서 중요한 사실 하나는 다음과 같습니다. 최적해가 존재한다면, 적어도 하나의 최적해는 가능영역의 꼭짓점에서 나타납니다. 그래서 그래프 해법은 음영 처리된 영역의 모든 점을 확인하는 대신 꼭짓점에 집중합니다.

예제: 그래프로 선형계획 문제 풀기

어떤 공장에서 두 제품 $A$와 $B$를 만든다고 합시다.

• $A$ 1단위당 이익: $3$
• $B$ 1단위당 이익: $5$
• 기계 사용 시간 제한: $A$ 1단위는 $1$시간, $B$ 1단위는 $2$시간이 필요하고, 총 사용 가능 시간은 최대 $8$시간
• 조립 시간 제한: $A$ 1단위는 $1$시간, $B$ 1단위는 $1$시간이 필요하고, 총 사용 가능 시간은 최대 $5$시간

$A$의 생산량을 $x$, $B$의 생산량을 $y$라고 둡니다.

최대화할 식은

$$P = 3x + 5y$$

제약조건은

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

꼭짓점 찾기

좌표축과 제약조건의 경계선을 보면, 가능영역의 꼭짓점은 다음과 같습니다.

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

점 $(2,3)$은 다음 경계식들을 연립해서 얻습니다.

$$x + 2y = 8,\quad x + y = 5$$

두 식을 빼면 $y = 3$이고, 이를 대입하면 $x = 2$입니다.

각 꼭짓점에서 목적함수값 계산하기

각 꼭짓점에서 이익을 계산하면 다음과 같습니다.

• $(0,0)$에서 $P = 0$
• $(5,0)$에서 $P = 15$
• $(0,4)$에서 $P = 20$
• $(2,3)$에서 $P = 21$

따라서 최대 이익은

$$P = 21$$

이고, 그때의 해는

$$(x,y) = (2,3)$$

입니다.

그래프 해법을 한 문장으로 말하면 이렇습니다. 가능영역을 그리고, 꼭짓점을 찾고, 그 점들에서 목적함수값을 계산하는 것입니다.

심플렉스법의 직관

그래프 해법은 변수가 두 개일 때만 실용적이고, 3차원 영역을 그릴 수 있다면 경우에 따라 세 개까지도 가능합니다. 하지만 실제 최적화 문제는 변수가 많은 경우가 많아서 가능영역을 그리는 일 자체가 비현실적입니다.

심플렉스법은 같은 꼭짓점 논리를 유지하되, 그것을 대수적으로 수행합니다. 크게 보면, 목적함수값을 더 좋게 만드는 가능한 꼭짓점으로 하나씩 이동하다가, 더 이상 인접한 이동으로 개선할 수 없을 때 멈춥니다.

그래서 다음처럼 이해하면 좋습니다.

• 그래프 해법: 꼭짓점을 눈으로 본다
• 심플렉스법: 그림 없이 꼭짓점들을 따라 이동한다

이 설명은 직관일 뿐, 전체 알고리즘은 아닙니다. 실제 심플렉스 절차에서는 각 단계에서 어떤 변수가 들어오고 나가는지를 결정하기 위해 심플렉스 표나 그에 해당하는 대수적 형태를 사용합니다.

왜 꼭짓점이 중요한가

선형 목적함수는 다음과 같은 등가선들을 만듭니다.

$$3x + 5y = k$$

여기서 $k$ 값이 달라지면 서로 다른 직선이 생깁니다. 이 직선을 더 큰 이익이 되는 방향으로 평행이동하면, 가능영역과 마지막으로 접하는 점에서 최대값이 발생합니다.

많은 그림에서는 그 마지막 접점이 하나의 꼭짓점입니다. 만약 목적함수의 직선이 경계선의 한 변과 평행하다면, 그 변 위의 여러 점이 모두 최적해가 될 수 있습니다. 그래도 그 경우에도 적어도 하나의 최적 꼭짓점은 존재합니다.

자주 하는 실수

가능해와 최적해를 혼동하기

어떤 점이 모든 제약조건을 만족하더라도 목적함수를 최대화하거나 최소화하지 못할 수 있습니다. 가능하다는 것은 단지 허용된다는 뜻입니다.

음이 아닌 조건을 빼먹기

$x$와 $y$가 생산량이나 운송량을 나타낸다면 보통 음수는 의미가 없습니다. $x \ge 0$ 또는 $y \ge 0$를 빠뜨리면 문제가 달라질 수 있습니다.

답은 항상 정수라고 가정하기

기본적인 선형계획법에서는 분수값도 허용됩니다. 변수들이 트럭 수나 작업자 수처럼 반드시 정수여야 한다면, 정수계획 모형이나 추가적인 정수 조건이 필요합니다.

모든 문제에 최적해가 있다고 가정하기

어떤 선형계획 문제는 불가능해서 어떤 점도 모든 제약조건을 만족하지 못합니다. 또 어떤 문제는 비유계라서 목적함수값이 한없이 좋아질 수 있습니다. 제약조건이 문제를 충분히 제한할 때만 유한한 최적값을 얻을 수 있습니다.

변수가 너무 많은데 그래프 해법을 쓰기

변수가 많아지면 그래프로 푸는 것은 더 이상 적절한 도구가 아닙니다. 이때는 심플렉스법이나 다른 최적화 방법이 필요합니다.

선형계획법은 언제 쓰일까

선형계획법은 제한된 자원을 두고 여러 선택이 경쟁하며, 목표와 제약을 모두 선형으로 모델링할 수 있을 때 사용됩니다. 대표적인 예로는 생산계획, 운송, 인력 배치, 배합, 일정 계획, 예산 배분 등이 있습니다.

모형의 품질은 가정의 타당성에 달려 있습니다. 실제 관계가 선형에 가깝지 않거나 변수가 반드시 정수여야 한다면, 기본 선형계획 모형은 출발점에 불과할 수 있습니다.

비슷한 문제를 직접 풀어보기

두 제품, 두 개의 자원 제한, 그리고 이익함수가 있는 간단한 문장제를 하나 골라 보세요. 변수를 정하고, 제약조건을 그래프로 그리고, 꼭짓점에서 목적함수값을 직접 계산해 보세요. 이 아이디어가 이해되면, 심플렉스법은 같은 논리를 더 높은 차원으로 확장한 것이라는 점이 훨씬 쉽게 보입니다.