‘선형계획법’은 자원을 용도에 맞게 효율적으로 배분하는 문제를 해결하기 위해 사용되는 방법이다. 이윤 최대화나 비용 최소화라는 목적 달성을 위해 한정된 자원 같은 제약조건을 적용해 최적해를 구해내는 과정이다. 제2차 세계대전 당시 효율적으로 군수 물자를 생산하고 수송하기 위한 작전연구 분야였고, 대(對)U보트 작전의 성공적 수행을 위해 연구팀을 꾸려 준비하던 것에서 발전해 산업 전 분야에 확산됐다. 최근에는 광고믹스 문제, 생산계획 문제, 포트폴리오 구성 문제 등 다양한 분야에서 적용되고 있다. 선형계획법 정립에 큰 기여를 한 인물은 조지 버나드 댄치그(1914~2005)다. 그와 선형계획법에 얽힌 유명한 일화가 전해지는데, 맷 데이먼 주연의 영화 ‘굿 윌 헌팅’에서 청소부로 일하던 주인공이 수학 난제를 푼 것만큼 극적이다.

UC 버클리 학생 댄치그는 어느 날 수업에 지각을 했다. 강의실에 들어서자마자 수업은 끝나버리고, 그는 칠판에 적힌 두 문제를 노트에 옮겨 적었다. 그는 이 문제가 숙제라고 생각하고 열심히 고민했지만, 지금까지의 숙제 중 가장 어렵다고 생각했다. 그리고 1주일 정도 고민한 끝에 완성한 문제 풀이를 교수 책상에 두고 나왔다. 얼마 후 담당 교수가 이 과제물을 들고 기숙사 방문을 다급하게 두드렸다. 놀란 댄치그가 나오자 교수는 이렇게 외쳤다. “자네가 지금 무엇을 나에게 제출했는지 아나? 자네는 지금까지 누구도 푼 적이 없는 통계학의 난제를 풀었다네.”

‘선형계획의 아버지’로 불리는 댄치그는 1914년 미국 오리건주 포틀랜드에서 태어나 UC 버클리에서 박사학위를 받았다. 1947년 댄치그는 선형계획법 역사에 한 획을 긋는데, 바로 선형계획법 해법인 단체법(Simplex Method)을 고안한 것이다. 최근에는 컴퓨터의 발달로 린도(Lindo), 링고(Lingo) 등 전문 프로그램이나 마이크로소프트 엑셀의 해찾기 기능을 통해 선형계획법을 쉽게 풀이할 수 있지만 그 기초가 된 것이 댄치그가 개발한 단체법이다. 이렇게 개발된 선형계획법은 아직도 국내외 산업에 많은 영향을 미치고 있다.

병원에서도 선형계획법은 다양하게 활용되고 있다. 지난 칼럼에서 짧게 언급한 캐나다 마운트 시나이 병원 사례를 살펴보자. 캐나다 병원은 정부에서 자금을 지급하는 ‘단일지불제도’로 운영한다. 전문의가 부족해 진찰이 지연되기 일쑤며 단순 내시경 검사에도 2~3개월이 걸린다. 서비스를 제공한 만큼 의사가 월급을 받으므로, 의사의 과잉 서비스 가능성이 있다. 정부의 예산 지원 부족으로 병원 시설이 낙후돼 있고 수술실, 입원실 등이 매우 부족하다. 캐나다 병원은 우리가 생각하기에 최적으로 운영된다고 보기 어렵다.

그렇다면 어떻게 운영하는 것이 최적인가? 병원 수술실은 사용 가능 시간이 정해져 있고, 각각의 날에 이용 가능한 수술실의 총 개수의 데이터를 얻을 수 있다. 또 수술실에서 진행되는 수술 유형은 몇 가지이며, 수술 부서 역시 몇 개인지를 알 수 있다. 특정한 날에 하나의 수술실에는 한 부서만 배정된다는 식의 가정도 선형계획법에 반영될 수 있으며, 하나의 수술실을 두 부서가 각기 다른 주에 사용할 수 있다는 가정도 포함할 수 있다. 각 주 사이의 일관성도 반영할 수 있으며, 이를 통해 주별, 일별 각 부서에 할당될 수 있는 수술실 공간을 목적함수로 두고, 이 값의 최댓값, 최솟값도 계산할 수 있다. 이 같은 제약 조건 아래 마운트 시나이 병원은 수술 시간을 줄이려는 병원과 수술 시간을 늘리려는 의사의 상반된 의견을 모두 반영해 총체적인 해법을 찾기 위해 선형계획법을 사용했고, 이를 통해 상당한 성과를 거뒀다.

선형계획법은 일상에서도 흔히 접할 수 있다. 우리는 매일 TV, 휴대폰 등을 통해 각종 광고에 노출된다. 그럼 어떻게 해야 광고를 통해 자사 제품이나 서비스를 소비자에게 널리 알릴 수 있을까? 답은 의외로 간단하다. 시청률이 높은 프로그램 앞뒤에 광고를 많이 배치하면 된다. 하지만 그 시간대에는 광고료가 비싸게 책정돼 있을 것이고 그러면 총이익이 줄어들 수 있다. 이를 위해 사용되는 것이 선형계획법이다. 최적의 광고 전략을 세우기 위해 시청률 정보, 광고 비용 등의 데이터를 수집한 뒤 이를 1차 제약조건식과 광고비용 최소화, 시청률 최대화를 동시에 만족시키는 복수목적선형계획법을 구성하면 된다. 이때 제약조건으로는 자사의 예산, 방송통신위원회 정책 등이 포함될 수 있다.

이런 광고 외에도 제품 제조회사들도 선형계획법을 사용하고 있다. 반도체 관련 모듈, 웨이퍼, 유기발광체 등을 제조하거나 파운드리 위탁 생산을 하는 글로벌 기업 페어차일드 역시 제품 가격 책정을 위해 선형계획법을 사용했다. 이는 페어차일드의 비생산적인 가격 산정 프로세스를 해결하고 다수의 가격 산정 방식으로 인한 기존의 혼선을 해결하는 동시에 e비즈니스를 위한 최적 가격 도출을 가능하게 했다. 즉 가격 분할화를 통한 채널별 가격 적용 혼선을 방지했고, 가격 책정 시간이 70% 감소하는 효과를 거뒀다. 약 20여개의 분활화를 통한 최적 단가적용, 매출 15% 상승, 최적 가격을 통한 수익 향상, 가격 산출을 위한 인력 10% 절감 등 많은 성과를 거뒀다.

이처럼 우리 주변의 삶과 산업에는 선형계획법이 녹아들어 있다. 지금 주변에 어떤 경영 과학적인 요소가 있는지, 어느 부분에 선형계획법이 적용돼 있는지 살펴보라. 만약 적용돼 있지 않다면 적용할 수 있는 문제가 있는지 생각해 보자. 무엇을 기대했든 선형계획법은 언제나 현 상황에서의 최적해라는 선물을 제공할 것이다.