[2학년][1학기][경영과학입문][9w]

정수계획법

의미

- 선형계획법의 분할성(Divisibility)

 : 결정변수가 소수점 이하의 값을 가질 수 있음

 : 부피, 시간, 길이, 무게와 같이 측정 가능한 변수는 문제 없음

 

- 현실의 많은 문제들은 결정변수가 정수(Integer) 값을 가질 때만 의미 있음

 ex) 선박, 비행기, 대형컴퓨터, 자동차 등의 구입 문제 등

 : 구한 분수 값을 정수로 반올림하는 경우에는 최적 정수해가 될 수 없음

 

- 정수계획법에 대한 일반적인 접근 방법

 : 선형계획 모델에 새로운 제약조건식을 추가

 → 가해영역의 boundary를 잘라서 정수 값이 되도록 하는 아이디어

 : 분단탐색법(Branch and Bound method) 사용

 → 엑셀 해찾기에서 이용됨

 

 정수계획모델의 세가지 형태

순수정수계획모델	모든 결정변수의 값이 정수	x1, x2 ≥ 0 : 정수
혼합정수계획모델	일부의 변수만 정수	x1, x2 ≥ 0, x2 : 정수
0-1 정수계획모델	모든 결정변수의 값이 0 또는 1	x1, x2 = 0 or 1

 정수계획모델의 해법

1. 그래프 방법

 - 결정변수의 수가 2개인 문제에 적용 가능

 - 일반 선형계획문제의 그래프 방법과의 차이는 가해영역

 - 정수계획 문제의 가해영역보다 선형계획 문제의 가해영역이 큼

 - 최적정수해는 등가이익선을 평행이동하여 원점으로부터 마지막에 만나는 정수좌표에서 결정

 - 최대화 문제에서 최적정수해의 Z값은 일반최적해의 Z값보다 언제나 작거나 같음

 

2. 분단탐색법(참고만)

- 주어진 문제에 선형계획법을 적용

 : 이때 구한 해는 원래 문제의 상한을 제공

 : 현재까지의 최적해 목적식 값 = 0

- 정수가 아닌 해를 선택하여 문제를 작은 문제로 분지

 ex) x2 = 2.4 → x2 ≤ 2 와  x2 ≥ 3 으로 분지함

- 각각의 작은 문제에 선형계획법을 적용함

 : 정수 해가 발견되면 그 해를 현재까지의 최적해와 비교하여 갱신함

 : 만일 작은 문제의 해가 현재까지의 최적해 목적식보다 작으면 그 문제는 더 이상 분지하지 않고 cut함

 : 만일 작은 문제가 infeasible하면 cut함

 

3.  탐색트리

 

 

문제 풀이

0-1 정수계획 모델: 한 개의 작업형태 당 1개의 작업 존재할 때

xj = 1: 처리해야 할 작업형태 j를 선택함(j = 1,2,3,...,n)

xj = 0: 작업형태 j를 선택하지 않음(j = 1,2,3,...,n)

 

고정비용 문제: 생산을 하는 경우에만 고정 비용이 발생할 때

ex) 서로 다른 제품 생산을 위해 생산라인을 변경하는데 필요한 준비 비용 혹은 시설 건설 비용 등

- 0-1 보조변수 yj를 도입하여 값을 할당

 if xj > 0, yj = 1

 if xj = 0, yj = 0

 총비용 = cj * xj + fj * yj

 (단위당 비용 * 생산량) + (고정 비용 * 발생 여부)

- 생산량 변수와 도입한 0-1 변수 yj를 관련시키는 연결제약조건식의 도입

 xj ≤ Myj (M은 매우 큰 수 이며, 결정변수 xj의 최적값에 대한 상한)