조용히 살자~

이름하야 O.R이라고 불리는 과학적 방법에 의한 시스템의 운영문제 해결방안

1909년 F.W.Taylor가 발표한 '과학적 관리의 원칙'(the principles of scientific management)으로 시작된 과학적 관리기법은 공정도로 유명한 Frank Gilbreth 의 동작분석에 의한 작업방법의 개선연구인 '동작연구'(motion study)를 거쳐 드디어 O.R이 개발되었다.

O.R은 2차 세계대전 중 본격적인 연구 이전에  영국의 F.W.Lanchester라는 사람이 군사작전 문제를 수량적으로 연구하고 전투의 결과(평균병력손실)는 병력 수와 교전 1회당 화력의 유효율의 積에 비례한다고하는 Lanchester 방정식을 고안하여 O.R과 유사한 연구를 시도하였고 본격적인 연구는 2차 세계대전 중 영국 국방부에서 시작되었다.

영국은 전쟁 중 전쟁물자를 비롯한 물품을 미국 등 외부로부터 선박편으로 들여왔는데 독일군의 U-Boat의 무차별 공격에 의해 피해가 막심하였다. 이에 잠수함 공격에 대한 최선의 방어전략을 찾기 위해 영국 국방장관은 물리학자, 심리학자, 공학자, 수학자 들로 구성된 O.R 팀을 구성하였는데 그 중 가장 유명한 팀이 노벨 물리학상을 수상한  P.M.SSS.Blackett 교수가 이끄는 해군 O.R 팀이었다. 그리고 전쟁이 끝난 수 이들은 각자의 기업체와 학교로 복귀하여 기업의 경영관리상 문제에 O.R을 적용하기 시작하면서 이 괴로운 O.R이 시작되었다.

선형계획법(Linear Programming)

여러 개의 제한 조건하에서 목적함수(objective function)의 값을 극대화, 극소화하는 자원의 배분문제(allocation problem)를 물기위한 O.R 기법을 수리계획법(mathematical programming)이라하고 이 중 가장 유명한 것이 선형계획법이다.

선형계획법은 선형대수학의 이론을 활용한 것으로 목적함수, 제한식(constraints)이 모두 1차식이 된다하여 이름 붙여졌다.

예제를 보면서 천천히 함 풀어보자.

문제>

아래 표에서 보듯 제품 A를 만드는 데 재료 abc가 각각 3,1,1 쓰이고 제품 B를 만드는 데는 재료 abc가 각각 4.3.6 이 쓰인다. 판매이익을 극대화하는 각 제품의 생산량을 구하라.

풀이>

이런 문제가 바로 제품혼합문제라구 그나마 간단한 문제 되겠다. 이걸 도해법과 Simplex Method로 풀어보자.

먼저 수학모델로 만들기 위해 결심변수(decision variable)결정. 생산량 구하는 문제이므로

제품 A의 생산량을  , 제품 B의 생산량을

■ 도해법 (Graphical Method)

제한식 ①②③을 에 대해 그림으로 나타내면 위 그림과 같다. 목적식 는 Z값이 변함에 따라 움직이며 가해지역내에서 Z값이 최대가 되는 점을 찾기 위해 움직여보면 가해지역의 다섯 꼭지점 중 하나에서 Z값은 최대가 된다.

이 문제에서는 C점이 가해지역과 만나는 최대 지점인데 C점은 목적식 ①과 ②가 만나는 접점으로 이 두방정식으로부터 ()=(12, 3)가 구해진다. 그리고 드디어 최적해 정답 Z=18,000

■ Simplex Method

위 도해법에서 최적해는 제한식들이 만나는 점 중에서 생긴다는 사실에서 각 접점만을 최적해 값에 대입해 보는 것이 Simplex Method란 것이다.

근데 과연 Simplex 라는 말처럼 간단할까? 아니 열라 복잡하다. 거의 죽음이다. 그래도 우짜겠나 위 그림처럼 2차원내에 그림이 그려지면 모르지만 목적식이나 제한식이 4,5차원으로 넘어가 버리면 못 그리지 않나 근데 현실의 문제라는 게 대부분 그렇게 복잡한 것들 투성이니까 어찌보면 Simplex 이기도 하다. 아주 복잡한 Simplex. 젠장...

다시 똑같은 문제를 Simplex Method로 풀기 위해서는 먼저 제한식의 부등식을 등식으로 바꾸어야 한다. 그래서 말고 또 다른 변수를 널어서 등식을 만들어보자.

위의 부등식에서 좌변이 모자라는 것을 메우기 위해서는 양의 변수를 더해 주어야 하는데 이렇게

          더해주는 변수를 여유변수(slack variable)이라 하고

          빼주는 변수를 잉여변수(surplus variable)이라 한다.

이제 접점들 중 인 A 점부터 해를 구하고 A 점에서 가까운 접점의 해를 차례대로 구해나간다.

또한 여기서 기저변수(Basic Variable)는 한 곳에만 존재하고 계수가 1인 이고 비기저변수(Nonbasic Variable)는 0의 값을 가지는 이다.

1. 진입변수는 Maximize 문제에서는 Z 값의 음수를 없애야 하니까 음수 중 가장 작은 값으로, Minimize 문제에서는 Z 값의 양수 중 가장 큰 값이 된다. (쉽게 절대값이 젤 큰 거 넣으면 된다) 이 문제에서는 표에 □ 안의 열이고 진출변수는 해를 진입변수로 나눈값 중 가장 작은 값으로 □ 안의 행이다. 그리고 진입과 진출의 접점에 있는 값을 Pivot Element라 한다.

2. 진입열이 이고 진출행이 이므로 기저변수는 , 에서 , 으로 바뀐다. =0, =0이므로

가 속한 ③번 식이  =0과 만나는 접점인 E점으로 이동한다.

3. 진출행은 Pivot Element로 나누어 주고

   나머지 행은 기존의 값-(해당행의 진입변수 × 바뀐 진출행의 값)

4. 이것을 반복하는데 비기저변수의 Z값이 양의 수가 나올 경우 해가 최적해가 된다. 위의 경우 18000

근데 완전 노가다 짓이다. 이짓을 어케하냐. 그래서 맨처음 표만 짜고 나머지는 컴에게 맡긴다고 한다. 컴만 불쌍하다.

여기까지가 아주 평범한 Simplex Method 이고 Big M, Two Phase 는 시간 나는 대로 정리 할 거다.