Linear Programming 정리

최적화 : 문제가 주어졌을 때, 문제에 대한 가장 최적의 해를 찾는 것이다.

결정변수와 목적함수 (최대화 or 최소화), 제약조건들에 대한 식을 만들 수 있다.

선형계획법(LP: linear programming) : 최적화 기법 중 하나이자, 제약조건들과 목적함수가 선형적인 관계를 유지해야한다.
ex) f(x1, x2) = 3x1x2 + 2x2 의 형태면 비선형적이기 때문에 선형계획법을 적용시키지 못한다.

예제) 수공예 하회탈 제조업체인 안동하회탈은 양반탈과 각시탈, 두 가지 탈을 만들어 팔고 있다.
양반탈의 개당 판매가는 2만 7천 원이고, 재료비는 1만 원이며, 가변비용(노동비, 간접비 등 탈 하나 만들 때마다 발생하는 비용)은 1만 4천 원이다. 각시탈의 경우, 개당 판매가는 2만 1천 원이고, 재료비는 9천 원, 그리고 가변비용은 1만 원이라고 한다.
하회탈을 만드는데는 목공기술과 마무리기술, 두 종류의 기술이 필요하다.
목공기술이란 나무를 양반이나 각시 모양으로 깎는 기술을 말하고, 마무리기술은 도색작업, 마무리 등의 상품화 기술을 말한다.
양반탈 한 개를 만드는 데는 1시간의 목공기술과 2시간의 마무리기술이 필요하고, 각시탈 한 개를 만드는 데는 1시간의 목공기술과 1시간의 마무리기술이 필요하다. 매주 안동하회탈에서는 필요한 재료는 모두 구입할 수 있으나 노동력에는 한계가 있어 매주 80시간의 목공기술과 100시간의 마무리 기술을 이용할 수 있다. 과거의 경험으로 볼 때 각시탈의 수요는 무제한이고, 양반탈은 많아야 40개가 팔렸다.
안동하회탈은 주당 이윤을 최대화하기 위한 제품 생산 계획안을 마련하고자 한다. 즉, 주당 양반탈과 각시탈을 각각 몇 개씩 생산하는 것이 안동하회탈의 주당 이윤을 최대화시킬 수 있겠는가?

Decision Variables (결정 변수) : X1 : 주당 양반탈 생산 개수, X2 : 주당 각시탈 생산 개수

Objective function (목적 함수) : 주당 이윤 = (양반탈 1개 이윤) x X1 + (각시탈 1개 이윤) x X2

양반탈 이윤 = 27000 (판매가) - 10000 (재료비) -14000 (가변비용) = 3000

각시탈 이윤 = 21000 - 9000 - 10000 = 2000

o.f Z = 3000X1 + 2000X2 -> Z = 3X1 + 2X2 (천원 단위)

주당 이윤을 최대화해야 하므로 MAX Z = 3X1 + 2X2

Constraints (제약 조건) : 목공기술은 80시간, 마무리기술은 100시간 양반탈은 많아야 40개가 팔림

How to find optimal solution ?

Graphical method

문제의 제약조건들을 순서대로 (1), (2), (3), (4) 라고 하고 그래프를 그려보면 위와 같은 형태가 나온다. 각각의 범위를 고려해 봤을 때 노란색으로 칠해진 부분이 feasible region (실현 가능한 대안들의 집합) 이 되고 여기에서 optimal solution 을 찾기 위해 목적함수 Z = 3X1 + 2X2 역시 그래프 상에서 표현해준다.

목적함수 Z = 3X1 + 2X2 는 기울기가 1.5인 직선으로 표현할 수 있고 feasible region에서 영역이 최대가 되게끔 이동시켜주면 X1 = 20, X2 = 60 이 된다. 이에 따라 최대 이윤은 Z = 3 x 20 + 2 x 60 = 180, 천 원단위로 바꿔주면 180000원으로 구할 수 있다.

Finding vertices

꼭짓점으로 찾는 방법은 feasible region의 모든 꼭짓점을 표시하고 각 꼭짓점에서 목적 함수의 최댓값을 찾는 방법이다. 위 그림에서 꼭짓점은 (0, 0), (0, 80), (20, 60), (40, 20), (40, 0) 이고, 각 꼭짓점에서의 Z 값은 0, 160, 180, 160, 120 이며, 최댓값은 180이고 이때의 X1 X2 값은 20, 60으로 최적해를 찾을 수 있게 된다.

Graphical method의 단점은 변수의 개수가 2개 초과일 경우 적용하기 어렵다는 단점이 있는데, 3개 이상의 변수가 존재할 경우 Simplex method 으로 해결할 수 있다.

Simplex method

Convert to Standard Form
slack ( s1 s2 s3 ) 를 활용하여 주어진 제약 조건을 등식으로 만들어준다.

​X1 + X2 + S1 = 80

2X1 + X2 + S2 = 100

X1 + S3

Initial Simplex Tableau

각 변수의 계수들로 안의 내용을 채워준다. Z = 3X1 + 2X1 목적함수의 식의 경우 Z - 3X1 - 2X2 = 0으로 변형하여 넣어준다. (최대화하는 문제의 경우 목적함수의 계수가 음수이다.)

다음으로는 Pivot Column과 Pivot Row를 찾는다. 목적함수를 기준으로 가장 최소가 되는 값을 찾고, 그 값을 포함하는 열이 Pivot Column이 된다. 예시에서는 -3 의 값이 가장 작고, 피벗 열은 X1 이 된다.

Pivot Row는 Pivot Column에 대해 RHS / Pivot Column 의 값이 최소가 되는 행이 된다. 예시에서는 40/1 이 40으로 가장 작으므로 S3가 Pivot Row가 된다.

그 다음으로는 Pivot Row를 제외하고 나머지 행들을 모두 0으로 만들어야하는데, Pivot Row를 활용하여 행 연산을 진행한다. (가우스 소거법에 적용시키는 행 연산 그대로 적용하면 된다.)
(X1 열의 S3 행을 제외한 나머지 행들이 모두 0이 된 형태)

다음으로 X2열에서 -2가 포함 되어 있으므로 X1 열에 한 계산과 똑같이 RHS / Pivot Column 값의 계산을 한 후 최소가 되는 값을 찾아 이후 과정을 똑같이 수행한다.

계산을 마치면 최종 형태는 아래 그림과 같이 나온다.

목적함수의 행에 모두 양수가 나왔으므로 이 형태가 최종 형태가 되고, 표에서 X1 = 20, X2 = 60, Z = 180 임을 알 수 있다.

참고영상 : https://www.youtube.com/watch?v=9YKLXFqCy6E

Google OR-Tools - Solver

Solver를 활용하여 해결할 수도 있다.

결국 선형계획법 문제가 주어졌을 때는, 결정 변수와 목적 함수를 설정하고, 올바른 식들을 도출해내기만 하면 위 방법론들로 문제를 해결할 수 있다.