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

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

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

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

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

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

정수계획법의 해법 열거법 : 실행가능해를 모두 열거하여 최적해를 찾는 방법 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

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

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

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

분단탐색법 예제 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

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

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

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

분단탐색법 분단탐색법 적용 예제 ① 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 ≤ 1 X1 ≥ 2 ⑦ X1 = 1, X2 = 3.3 Z= 23.8 실행불가능 23.8 ≤ 현재의 하한값(24)

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

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

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

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

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

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

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

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

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

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

정수계획법의 적용사례 예제 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 - 연간수요

정수계획법의 적용사례 예제 7-4 : 공장신설문제 의사결정변수 YB, YC, YD, YE = 각각 지역 B, C, D, E에 공장을 신설할지를 결정하는 이진 변수 (즉, 0 또는 1) Xij = i공장에서 수요지 j로의 공급량 목적함수 (총비용의 최소화, 단위: 만원) Min 17500YB +30000YC +37500YD +50000YE + 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

정수계획법의 적용사례 예제 7-4 : 공장신설문제 제약식 XBL + XBM + XBN -10000YB ≤ 0 XCL + XCM + XCN -20000Yc ≤ 0 XDL + XDM + XDN -30000YD ≤ 0 XEL + XEM + XEN - 40000YE ≤ 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

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

정수계획법의 적용사례 예제 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

정수계획법의 적용사례 예제 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

정수계획법의 적용사례 예제 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에 파출소를 하나씩 설치하는 것이 최적

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

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