선형계획모형의 구성과 전제조건

핵심 정리

선형계획법(linear programming)은 제한된 자원 아래에서 목적함수의 값을 최대화하거나 최소화하는 활동 수준을 찾는 의사결정 기법이다. 선형계획모형은 결정변수, 목적함수, 제약식의 세 요소로 구성되며, 이 구성이 성립하려면 모형이 몇 가지 전제를 만족해야 한다. 그 전제가 이 개념의 뼈대이고, 전제를 정확히 알아야 선형계획법이 적용되는 범위와 정수계획법·목표계획법과의 차이를 설명할 수 있다.

첫째 요건은 분할성이다. 분할성은 결정변수가 소수 값을 가질 수 있다는 선형계획법의 기본 가정이다. 결정변수가 정수로 한정되지 않으므로 해를 구한 뒤 활동 수준이 소수로 나와도 모형의 구조는 그대로 유지된다. 이 가정이 없다면 정수 해를 얻기 위한 별도의 절차가 필요해지므로 계산 구조 자체가 달라진다.

둘째 요건은 활동 수준과 자원 이용량 사이의 관계다. 선형계획법에서 작용성과 이용량은 활동 수준에 비례하도록 요구된다. 활동 수준이 커지면 그에 비례하여 자원 이용량이 커져야 하고, 이 관계가 깨지면 모형은 선형식으로 표현되지 않는다.

셋째 요건은 모형의 구조에 관한 것이다. 선형계획모형을 구성하는 활동의 수와 생산 방법은 제한이 있어야 한다. 또 의사결정변수는 어떠한 경우에도 음의 값을 가져서는 안 된다. 그리고 개개 활동 사이에 변환 작용이 없어야 한다.

넷째 요건은 목적함수와 제약식의 형태다. 이 두 식은 모두 1차식으로 표시되어야 한다. 반면 확률성은 선형계획모형의 전제에 들지 않는다.

정수계획법은 전제 가운데 하나를 바꾼 기법이다. 정수계획법은 모형변수가 0 또는 양의 정수여야 하는 기법이다. 가분성을 전제로 하는 기법은 정수계획법의 특성이 아니라 선형계획법의 특성이다. 목표계획법 모형에는 세 가지 목표가 포함된다.

자세히

정수계획법과의 구분

두 기법을 가르는 기준은 결정변수가 취할 수 있는 값의 범위다. 선형계획법은 분할성을 가정하므로 소수 값을 허용하고, 정수계획법은 그 가정을 두지 않는다. 아래 표는 두 기법의 차이를 한눈에 정리한 것이다.

정수계획법의 목적함수는 선형이다. 따라서 목적함수의 형태만으로는 두 기법을 구별할 수 없고, 결정변수의 값 범위에서 차이가 생긴다. 정수계획법은 변수가 정수값만 가지므로 분할성이 성립하지 않는다. 그러나 정수계획법에서도 나머지 조건은 그대로 요구된다. 비부성(비음조건)은 변수가 0 이상이어야 한다는 조건으로 정수계획법에도 적용된다. 선형성은 목적함수와 제약식이 선형식이라는 조건으로 정수계획법에도 해당한다. 따라서 정수계획법을 선형계획법의 조건을 모두 버린 기법으로 이해하면 틀린다. 두 기법의 선지를 판별할 때는 결정변수 값의 범위부터 확인하는 것이 순서다.

활동 수와 비음 조건의 취지

활동의 수와 생산 방법을 제한해 두는 까닭은 모형이 검토할 대안의 범위를 유한하게 묶기 위해서다. 대안의 범위가 열려 있으면 목적함수를 최대화하는 해를 정해진 절차로 찾기 어렵다. 결정변수의 음수 금지도 같은 맥락에서 이해한다. 활동 수준은 생산량이나 투입량처럼 음의 값을 가질 수 없는 양을 나타내므로, 모형은 그 범위 안에서만 해를 찾는다.