김민경 (mkyung.kim@gmail.com) 제 7장. 정수계획모형 경영과학1 2008. 가을 김민경 (mkyung.kim@gmail.com)

Presentation on theme: "김민경 (mkyung.kim@gmail.com) 제 7장. 정수계획모형 경영과학1 2008. 가을 김민경 (mkyung.kim@gmail.com)"— Presentation transcript:

1 김민경 (mkyung.kim@gmail.com)
제 7장. 정수계획모형 경영과학1 2008. 가을 김민경

2 학습목표 정수계획법의 모형화 정수계획법의 해법 분단탐색법 K-opt를 이용한 정수계획모형의 풀이 정수계획법의 적용사례

3 정수계획법의 모형화 정수계획법(IP ; Integer Programming) : 의사결정변수가 정수의 값만을 갖는 수리계획법
정수선형계획법(ILP) : IP중에서도 목적함수와 제약조건이 모두 1차식인 경우 정수계획모형의 종류 - 순수정수계획모형 : 모든 변수가 정수인 모형 - 혼합정수계획모형 : 일부가 정수인 모형 정수계획모형 : 모든 변수가 0 또는 1인 모형 정수계획법이 중요하게 다루어지는 이유 - 실제 의사결정 상황이 정수인 해를 요구 - 정수계획모형으로 모형화하면 보다 쉽게 해결되는 경우 모형화 : 정수계획 모형은 선형계획모형에 변수가 정수이어야 한다는 조건을 추가

4 정수계획법의 모형화와 해법 예제 7-1 한국슈퍼연쇄점은 최근 사세확장을 위하여 신규점포와 중간저장설비를 신설할 계획으로 155억원의 자금을 확보하였다. 신규점포는 신설비용이 개당 10억원이 소요되며 이를 통해 한 달에 3000만원의 수익을 올릴 수 있고, 저장설비는 개당 30억원의 자금이 소요되며 이를 통해 한 달에 7200만원의 수익을 올릴 수 있다. 경영층에서는 최소한 한 개의 신규저장설비를 설치할 예정이며 신규점포는 5개를 넘지 않는 범위에서 설치하려고 한다. 한국슈퍼는 확보된 자금으로 최대의 수익을 얻을 수 있는 신설계획을 수립하고자 한다. 의사결정변수 : 신설점포수와 신설저장시설의 수 → 정수계획모형   X1 : 신설점포의 수,   X2 : 신설저장시설의 수 ( X1과 X2는 음이 아닌 정수이어야 함)

5 정수계획법의 모형화와 해법 예제 7-1 의사결정변수 : 신설점포수와 신설저장시설의 수 → 정수계획모형   X1 : 신설점포의 수,   X2 : 신설저장시설의 수 ( X1과 X2는 음이 아닌 정수이어야 함) 목적함수는 월간 예상총이익을 최대화 (단위 : 만원)   Max. Z = 3000X X2 제약조건   s. t.      10X1 + 30X2  ≤ 155 (자금제약식, 단위: 억원)                   X1   ≤   5  (신규점포제약)                            X2    ≥ 1  (신규창고제약)                   X1, X2 는 음이 아닌 정수

6 정수계획법의 해법 해법의 종류 ① 열거법  ② 선형계획법의 해를 이용한 근사법  ③ 절단평면법(cutting plane method)  ④ 분단탐색법(branch and bound method)

7 정수계획법의 해법 열거법 : 실행가능해를 모두 열거하여 최적해를 찾는 방법 x2 x1 등이익선 LP의 최적해 (5 , 3.5)
열거법 : 실행가능해를 모두 열거하여 최적해를 찾는 방법 x2 등이익선 LP의 최적해 (5 , 3.5) Z = 4억 200만원 정수 최적해 (3 , 4) Z = 3억 7800만원 LP의 실행가능영역 5 4 실행가능정수해 3 2 1 x1 1 2 3 4 5

8 정수계획법의 해법 열거법의 문제점 그래프를 이용한 분석의 경우 변수가 두 개인 모형만 가능
꼭지점에서 최적해가 발생한다는 성질이 없으므로 최적해를 구하기 위해서는 제약조건을 만족하는 거의 모든 정수해 들을 조사해야 함 But, 선형계획법의 해법과 같은 효율적인 해법은 아직 없는 상태 절단평면법 새로운 제약식(절단평면)을 추가하여 기존의 실행가능영역 중 정수해를 포함하지 않는 부분을 제외 위 과정을 반복하여 최적 정수해를 구하는 방법 ☞ 선형계획법의 민감도분석의 기법을 적용하는 것으로 개념적으로는 우수하지만 계산상의 효율성이 떨어짐

9 정수계획법의 해법 분단탐색법 해의 집합을 열거해 가면서 최적해의 가능성을 검토
가능성이 없는 집합은 고려대상에서 제외시켜 검토 영역을 좁혀나감으로써 최적정수해를 찾는 방법 해의 집합을 열거하기 때문에 부분적인 열거법이라고 함 ☞ 다른 해법에 비해 개념상으로나 계산상으로 가장 우수한 방법 선형계획법에 의한 근사법 변수의 정수제약조건을 완화한 선형계획모형(LP relaxation)의 해를 구하여, 그 값을 반올림, 반내림하거나 절삭하여 정수해를 구하는 방법 ☞ 매우 쉬운 방법이기는 하지만 최적해를 얻지 못하거나 실행불가능한 해를 얻을 수도 있다.

10 분단탐색법 분단탐색법의 절차 (1) 문제 나누기(branching)
- 완화된 LP 문제의 실행가능영역을 비정수인 변수의 측면에서 두 개의 상호 배타적인 영역으로 나누어, 두 개의 부분문제를 만든다. (2) 한계 정하기(bounding) - 두개로 나누어진 문제에 대하여 각각의 해를 구하고, 이를 토대로 원래의 문제가 가질 수 있는 한계 값을 정한다. (3) 검토하기(fathoming) - 목적함수의 한계 값이 결정된 각 문제에 대하여 최적해로서의 가능성을 검토하고, 최적해의 가능성이 없는 문제는 고려 대상에서 제외시킨다.

11 분단탐색법 예제 7-1 : 분단탐색법 적용 선형계획법의 최적해 : (X1, X2) = (5, 3.5), Z = 4억 200만원
목적함수값 4억 200만원은 최적정수해가 가질 수 있는 목적함수값의 상한 X2는 3에서 4사이의 값을 가질 수 없음 -> X2≤3 혹은 X2≥4 Z*=40200 X1*=5, X2*=3.5 Z*=36600 X1*=5, X2*=3 Z*=39300 X1*=3.5, X2*=4 Z*=39000 X1*=3, X2*=4.2 실행불가능 Z*=37800 X1*=3, X2*=4 Z*=37500 X1*=0.5, X2*=5 X2 ≤ 3 X2 ≥ 4 X1 ≤ 3 X1 ≥ 4 X2 ≤ 4 X2 ≥ 5

12 분단탐색법 분단탐색법 적용 예제 Max. Z = 4X1 + 6X2 s. t. 5X1 + 10X2 ≤ 38 X1 + X2 ≤ 5
등이익선 5 실행가능영역 LP의 최적해(2.4,2.6) Z = 25.2 1 x1 5

13 분단탐색법 (1) 문제 나누기 X1, X2 둘다 정수가 아님 (2) 한계 정하기 → 문제 나누기 필요
( 일반적으로 소수점이하 부분이 정수에 더 가까운 것부터 분기) X1을 분기 → ②,③번 문제 생성 ②번 : 원래 문제에 X1 ≤ 2 추가 ③번 : X1 ≥ 3 제약을 추가 (2) 한계 정하기 ②번 문제의 최적해 (X1, X2) = (2, 2.8), Z = 24.8 ③번 문제의 최적해 (X1, X2) = (3, 2), Z = → 정수해이므로 최적해의 후보 (목적함수의 하한 : 24) x2 x1 5 1 (2,2.8) ②번 문제의 실행가능영역 ③번 문제의 (3,2) X1=2 X1=3

14 분단탐색법 (3) 검토하기 ②번 문제의 X2를 분기 → ④,⑤번 문제 생성 x2 5 1 x1 5
④번 문제의 최적해 (X1, X2) = (2, 2), Z = → 정수조건을 만족 (but, 24보다 작으므로 탈락) ⑤번 문제의 최적해 (X1, X2) = (1.6, 3), Z = → 정수조건을 만족 하지 못하므로 다시 분기 (⑥, ⑦ 문제 생성) x2 ⑤번 문제의 실행가능영역 5 ④번 문제의 실행가능영역 (1.6,3) X2=3 X2=2 (2,2) 1 x1 5

15 분단탐색법 분단탐색법 적용 예제 ① X1 = 2.4, X2 = 2.6 Z= 25.2 ② X1 ≤ 2 X1 ≥ 3 ③
<정수해> : 최적해 X2 ≤ 2, X2 ≥ 3 ④ ⑤ X1 = 2, X2 = 2 Z= 20 X1 = 1.6, X2 = 3 Z= 24.4 <정수해> ⑥ X1 ≤ X1 ≥ 2 ⑦ X1 = 1, X2 = 3.3 Z= 23.8 실행불가능 23.8 ≤ 현재의 하한값(24)

16 K-opt를 이용한 정수계획법의 풀이 K-opt
분단탐색법을 이용하여 연속적인 변수와 0 또는 1 만이 될 수 있는 이진변수가 혼합되어 있는 혼합정수계획모형을 풀 수 있다. K-opt가 풀수 있는 최대 크기는 제약식의 개수 : 100개 이하 변수들 (연속변수 및 이진변수)의 총 개수 : 100개 이하 이진변수들의 개수 : 20개 이하 K-opt의 한계 이진변수만을 취급할 수 있으므로 예제 7-1과 같이 모든 정수값을 가질 수 있는 정수변수를 갖는 개수결정문제는 직접 해결할 수 없음 일반적인 정수변수를 이진변수와 변환하여 K-opt 활용가능

17 정수계획법의 적용사례 예제 7-2 : 자금운용계획 (Capital Budgeting)
H 그룹은 다음 3년간의; 투자계획으로서 3가지의 사업을 고려하고 있다. 각 사업에 소요되는 자금의 연도별 예상액과 이 사업이 가져올 사업이익금의 현재가치가 표와 같이 주어져 있다. H 그룹은 가용자금 한도 안에서 총 사업이익의 현재가치가 최대가 되도록 사업을 선택하고자 한다. H 그룹 투자계획 관련 자료 (단위: 억원) 사업 사업이익의 현재가치 자금소요계획 첫해 둘째 해 셋째 해 공장확장 450 100 창고신설 200 150 50 첨단기계설치 350 가용자금 250 400

18 정수계획법의 적용사례 예제 7-2 : 자금운용계획 (Capital Budgeting) 의사결정변수
X1 = 1, 공장확장을 추진하는 경우 0, 공장확장을 취소하는 경우 X2 = 1, 창고신설을 추진하는 경우 0, 창고신설을 취소하는 경우 X3 = 1, 첨단기계설치를 추진하는 경우 0, 첨단기계설치를 취소하는 경우 목적함수 (총이익의 최대화, 단위: 억원) Max Z = 450 X X X3

19 정수계획법의 적용사례 예제 7-2 : 자금운용계획 (Capital Budgeting) 제약식
100X1 +150X2+ 50X3 ≤ 250 100X1 + 50X2+200X3 ≤ 400 50X X2+100X3 ≤ 200 X1, X2, X3은 0또는 1 선형계획모형 Max 450 X X X3 s.t 100X1 +150X2+ 50X3 ≤ 250 100X1 + 50X2+100X3 ≤ 200

20 정수계획법의 적용사례 예제 7-2 : 자금운용계획 (Capital Budgeting) – K-opt 풀이 입력 분석결과

21 정수계획법의 적용사례 고정비문제 선형계획모형의 비례의 조건을 완화
생산활동의 수준에 관계없이 발생하는 고정비 (fixed cost) 고려 가능 변동비를 a, 고정비를 f, 생산수준이 X 일 때의 총 비용 C(X) C(X) = f + aX, X >0 일 때 , X=0 일 때 총 비 용 총비용=고정비용+변동비용 변동비용=(변동비×생산수준) 고정 비용 생산수준

22 정수계획법의 적용사례 고정비문제 정수변수 Y의 도입 Y = 1 , X > 0 일 때 (즉, 생산할 때)
 C(X) = fY + aX X ≤ MY ( M : X가 가질 수 있는 값의 범위 이상되는 양수)

23 정수계획법의 적용사례 예제 7-3 : 고정비문제 K 공업은 20000단위의 제품을 3개의 기계를 통하여 생산하고 있는데 각 기계를 가동시키기 위해서는 일정한 고정비가 소요된다. 각 기계의 고정비, 변동비 및 생산능력 등이 다음 표에 정리되어 있다. K 공업은 20000단위의 제품을 어느 기계로 생산하는 것이 총생산비를 최소화하는지 알아보고 싶다. 기계 고정비(만원) 변동비(만원/단위) 생산능력 1 300 2 8000 100 10 13000 3 200 5 14000

24 정수계획법의 적용사례 예제 7-3 : 고정비문제 의사결정변수 Yj = 1, 기계 j를 가동시키는 경우,
Xj = 기계 j의 생산수준, j = 1, 2, 3 목적함수 (총생산비의 최소화, 단위: 만원) Min Z = 300Y Y Y3 + 2X1 + 10X2 + 5X3 제약식 X1 + X2 + X3 ≥20000 X1 ≤ 8000Y1 X2 ≤ 13000Y2 X3 ≤ 14000Y3 X1, X2, X3 ≥0, Y1, Y2, Y3 = 0 또는 1

25 정수계획법의 적용사례 예제 7-3 : 고정비문제 – K-opt 풀이 입력 분석결과

26 정수계획법의 적용사례 예제 7-4 : 공장신설문제
현재 A지역에 공장을 갖고서 L, M, N 세 지역의 수요를 공급하고 있는 제일산업은 내년에 수요의 급증이 예상됨에 따라 B, C, D, E 등 4군데에 공장의 신설을 고려 중에 있다. 공장신설 고려대상이 되는 지역에는 수요지까지의 단위당 수송비(단위:만원)는 다음에 주어진 표와 같다. 한편 B, C, D 지역에 신설되는 공장의 총 건설비는 각각 17억 5천만원, 30억원, 37억 5천만원, 50억원으로 공장건설비의 연간금융비용은 10%의 이율을 적용할 떄 각각 1억 7500만원, 3억원, 3억 7500만원, 5억원 씩이다. 이 회사에서는 연간 총 수송비와 금융비용의 합을 최소화하는 건설 및 수송계획을 수립하고자 한다. 수요지 공장 L M N 연간생산능력 금융비용(만원) B 0.5 0.2 0.3 10000 17500 C 0.4 20000 30000 D 0.9 0.7 37500 E 1 40000 50000 A 0.8 - 연간수요

27 정수계획법의 적용사례 예제 7-4 : 공장신설문제 의사결정변수
YB, YC, YD, YE = 각각 지역 B, C, D, E에 공장을 신설할지를 결정하는 이진 변수 (즉, 0 또는 1) Xij = i공장에서 수요지 j로의 공급량 목적함수 (총비용의 최소화, 단위: 만원) Min 17500YB YC YD YE + 0.5XBL +0.2XBM +0.3XBN +0.4XCL +0.3XCM+0.4XCN+0.9XDL +0.7XDM +0.5XDN +XEL +0.4XEM +0.2XEN +0.8XAL +0.4XAM +0.3XAN

28 정수계획법의 적용사례 예제 7-4 : 공장신설문제 제약식 XBL + XBM + XBN -10000YB ≤ 0
XCL + XCM + XCN Yc ≤ 0 XDL + XDM + XDN YD ≤ 0 XEL + XEM + XEN YE ≤ 0 XAL + XAM + XAN ≤ 30000 XBL +XCL +XDL +XEL +XAL ≥ 30000 XBM +XCM +XDM +XEM +XAM ≥ 20000 XBN +XCN +XDN +XEN +XAN ≥ 20000 Xij ≥ 0, for all i and j YB, YC, YD, YE = 0 또는 1

29 정수계획법의 적용사례 예제 7-4 : 공장신설문제 K-opt 결과
지역 E에 공장을 신성하고 공장 E에서는 M과 N 지역에 공급하고 기존의 공장 A에서는 L지역에 공급하는 것이 최적

30 정수계획법의 적용사례 예제 7-5 : 공공시설배치문제
새로이 건설되고 있는 H 시에는 7개의 행정구역이 있는데 이 구역을 담당하기 위한 파출소의 위치를 고려하고 있다. 고려대상이 되는 위치는 A, B, C, D, E, F, G 등 7곳인데 각 위치에서 담당할 수 있는 행정구역은 다음과 같다. H시에서는 개설해야 하는 파출소의 개수가 최소가 되는 설치계획을 구하고자 한다. A B C D E F G 담당구역 1,5,7 1,2,5,7 1,3,5 2,4,5 3,4,6 4,5,6 1,5,6

31 정수계획법의 적용사례 예제 7-5 : 공공시설배치문제 의사결정변수
XA ,XB, XC, XD, XE, XF, XG = 각각 지역 A, B, C, D, E, F, G에 파출소 설치 여부를 결정하는 이진변수 (즉, 0 또는 1) 목적함수 (설치 파출소 개수의 최소화) Min XA+ XB + XC + XD + XE + XF + XG

32 정수계획법의 적용사례 예제 7-5 : 공공시설배치문제 제약식 XA+ XB + XC + XG ≥1 XB + XD ≥1
XC + XE ≥1 XD + XE + XF ≥1 XA+ XB + XC + XD + XF + XG ≥1 XE + XF + XG ≥1 XA+ XB ≥1 XA, XB, XC, XD, XE, XF, XG = 0 또는 1 최적해 XB =1, XE =1, 즉 B와 E에 파출소를 하나씩 설치하는 것이 최적

33 개수결정문제와 K-opt 예제 7-1을 K-opt로 풀기 Max. 3000X1 + 7200X2
s. t.      10X1 + 30X2  ≤ 155                X1   ≤   5                       X2    ≥           X1, X2 는 음이 아닌 정수 X1 = 20Y1 + 21Y Y3 = Y1 + 2Y Y3 X2 = 20Y Y5 + 22Y6 = Y4 + 2Y5 + 4Y6 Max. 3000Y Y Y Y Y Y6 s. t.   10Y1 + 20Y Y3 + 30Y4 + 60Y Y6  ≤ 155         Y1 + 2Y Y3 ≤   5         Y4 + 2Y5 + 4Y6 ≥    Y1, Y2, Y3, Y4 , Y5, Y6 = 0 또는 1

34 개수결정문제와 K-opt 예제 7-1을 K-opt로 풀기
X1 = 20Y1 + 21Y Y3 = Y1 + 2Y Y3 = 1x1 + 2x1 + 4x0 = 3 X2 = 20Y Y5 + 22Y6 = Y4 + 2Y5 + 4Y6 = 1x0 + 2x0 + 4x1 = 4