제 7 장 정수계획법 정수계획법의 모형화 정수계획법의 해법 분단탐색법 정수계획법 적용사례.

Presentation on theme: "제 7 장 정수계획법 정수계획법의 모형화 정수계획법의 해법 분단탐색법 정수계획법 적용사례."— Presentation transcript:

1 제 7 장 정수계획법 정수계획법의 모형화 정수계획법의 해법 분단탐색법 정수계획법 적용사례

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

3 ▶ 정수계획법의 모형화와 해법 ◁ 모형화 ▷ 정수계획 모형은 선형계획모형에 변수가 정수이어야 한다는 조건을 추가
◁ 모형화 ▷ 정수계획 모형은 선형계획모형에 변수가 정수이어야 한다는 조건을 추가    예제 모형  : 유통회사인 Y사 문제 - 38(억원)의 예산으로 유통판매점과 물류센터를 신설 계획 - 신설비용 : 판매점 5(억원), 물류센터는 10(억원) - 월간 예상수익은 : 판매점 4(천만원), 물류센터 6(천만원) - 물류센터는 한 개 이상을 반드시 신설해야 하고 두 시설을 합하여 5개가 넘지 않아야 함 의사결정변수 : 유통판매점과 물류센터의 수 → 정수계획모형   X1 : 신설할 판매점의 수,   X2 : 신설할 물류센터의 수 ( X1과 X2는 음이 아닌 정수이어야 함)

4 ▶ 정수계획법의 모형화와 해법 목적함수는 월간 예상총이익을 최대화하는 것이므로   Max. Z = 4X1 + 6X2 (월간 예상총이익) 제약조건   s. t.      5X1 + 10X2  ≤ 38 (예산 제약)                  X1 +     X2  ≤   5 (총 시설수 제약)                            X2    ≥ 1 (물류센터 수 제약)                  X1, X2 는 음이 아닌 정수 정리된 정수계획모형 Max. Z = 4X1 + 6X2 (월간 예상총이익) s. t.    5X1 + 10X2  ≤ 38 (예산 제약)              X1 +    X2  ≤  5  (총 시설수 제약)                          X2   ≥ 1 (물류센터 수 제약)               X1, X2 는 음이 아닌 정수

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

6 ▶ 정수계획법의 해법 열거법 : 실행가능해를 모두 열거하여 최적해를 찾는 방법 x2 x1 등이익선 5 완화된 LP의
열거법 : 실행가능해를 모두 열거하여 최적해를 찾는 방법 x2 등이익선 5 완화된 LP의 실행가능영역 완화된 LP의 최적해(2.4,2.6) 실행가능정수해 1 x1 5

7 ▶ 정수계획법의 해법 선형계획법에 의한 근사법
변수의 정수제약조건을 완화한 선형계획모형(LP relaxation)의 해를 구하여, 그 값을 반올림, 반내림하거나 절삭하여 정수해를 구하는 방법 ☞ 매우 쉬운 방법이기는 하지만 최적해를 얻지 못하거나 실행불가능한 해를 얻을 수도 있다. 절단평면법 새로운 제약식(절단평면)을 추가하여 기존의 실행가능영역중 정수해를 포함하지 않는 부분을 제외 위 과정을 반복하여 최적정수해를 구하는 방법 ☞ 선형계획법의 민감도분석의 기법을 적용하는 것으로 개념적으로는 우수하지만 계산상의 효율성이 떨어짐

8 ▶ 정수계획법의 해법 절단평면의 개념 x2 5 절단평면에 의해 제외되는 영역 절단평면 1 x1 5

9 ▶ 정수계획법의 해법 분단탐색법 해의 집합을 열거해 가면서 최적해의 가능성을 검토
가능성이 없는 집합은 고려대상에서 제외시켜 검토 영역을 좁혀나감으로써 최적정수해를 찾는 방법 해의 집합을 열거하기 때문에 부분적인 열거법이라고 함 ☞ 다른 해법에 비해 개념상으로나 계산상으로 가장 우수한 방법

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

11 ▶ 분 단 탐 색 법 Y사의 문제에 대한 분단탐색법 적용 완화된 선형계획법의 최적해 : (X1, X2) = (2.4, 2.6), Z = 25.2(①번 문제)  ☞ 목적함수값 25.2는 최적정수해가 가질수 있는 목적함수값의 상한  x2 5 완화된 LP의 최적해(2.4, 2.6) Z = 25.2 1 x1 5

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

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

14 ▶ 분 단 탐 색 법 ① ② ③ ④ ⑤ ⑥ ⑦ 분단탐색법 적용 결과 Y사 문제의 분단탐색법 적용 결과
▶ 분 단 탐 색 법 분단탐색법 적용 결과 ① Y사 문제의 분단탐색법 적용 결과 X1 = 2.4, X2 = 2.6 Z= 25.2 ② X1 ≤ X1 ≥ 3 ③ X1 = 2, X2 = 2.8 Z= 24.8 X1 = 3, X2 = 2 Z= 24 <정수해> : 최적해 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)

15 ▶ 정수계획법 적용사례 ◁ 배낭(Knapsack)문제 ▷ 전형적인 0-1 정수계획법 문제
용량이 한정된 배낭에 넣어야 할 물건을 결정하는 문제 정수 0과 1을 도입하여 1은 해당 물건을 선택, 0은 선택하지 않는 경우를 표시

16 ▶ 정수계획법 적용사례 예제 모형 : K군의 배낭문제 -배낭용량 : 12kg 물건 중량(kg) 효용(가치) 텐트 침낭 버너
음식 그릇 낚시도구 구급약 5.0 2.0 1.2 4.0 2.5 4.5 0.5 75 20 40 50 30 25 15 결정변수 Xi를 각 물건의 선택여부를 나타내도록 정의    Xi = 1,  i 번째 물건을 선택하는 경우             0,  i 번째 물건을 선택하지 않는 경우

17 ▶ 정수계획법 적용사례 목적함수 : K군의 총 효용을 최대화      Max. Z = 75X1 + 20X2 + 40X3 + 50X4 + 30X5 + 25X6 + 15X7 제약조건 : 선택한 물건들의 총 중량이 12kg를 넘지 않는 것     5X1 + 2X X3 + 4X X X X7 ≤ 12 0-1 정수계획모형으로 정리된 K군의 문제  Max. Z = 75X1 + 20X2 + 40X3 + 50X4 + 30X5 + 25X6 + 15X7     s.  t.         5X1 + 2X X3 + 4X X X X7 ≤ 12                       Xi = 0 또는 1

18 각 사업의 투자소요금액과 예상이익(단위 : 억원)
▶ 정수계획법 적용사례 ◁ 자원배정문제 ▷ 예제 모형  : S그룹의 투자계획 문제 -3년간 4가지의 사업을 고려 각 사업의 투자소요금액과 예상이익(단위 : 억원) 사업명 자금소요금액 예상이익 1차년도 2차년도 3차년도 신제품개발 자동설비도입 공장확장 해외지사설립 10 1 5 20 30 15 40 50 45 투자가능한도 60 결정변수   Xi = 1,  i 번째 사업을 추진하는 경우          0,  i 번째 사업을 추진하지 않는 경우

19 ▶ 정수계획법 적용사례 목적함수 : 각 사업의 투자에 따른 예상 총이익을 최대화     Max.  Z = 40X1 + 30X2 + 50X3 + 45X4 제약조건 : 각 연도의 투자가능한도     10X1 +     X2 +   5X3 + 10X4 ≤ 20 (1차년도 투자한도)     10X1 + 20X2 + 30X3 + 15X4 ≤ 60 (2차년도 투자한도)     10X1 +   5X2 + 20X3 + 15X4 ≤ 40 (3차년도 투자한도) 정수계획모형으로 최종 정리된 S그룹의 사업투자 결정 문제   Max.  Z = 40X1 + 30X2 + 50X3 + 45X4      s.  t.         10X1 +    X2  +  5X3 + 10X4 ≤ 20                      10X1 + 20X2 + 30X3 + 15X4 ≤ 60                      10X1 +   5X2 + 20X3 + 15X4 ≤ 40                              Xi = 0 또는 1

20 ▶ 정수계획법 적용사례 ◁ 고정비용 문제 ▷ 예제 모형 : L그룹의 공장을 신설 및 제품 공급 문제
◁ 고정비용 문제 ▷ 예제 모형  : L그룹의 공장을 신설 및 제품 공급 문제 공장신설비용과 단위당 수송비용 대리점 공장후보지 A B C 공장신설비용  (억원) 1 2 5 10 8 9 12 6 7 수요량 80,000 30,000 40,000 어느 공장후보지에 공장을 신설하는 것이 공장신설비용과 수송비용의 합을 최소로 하겠는가를 결정하는 문제

21 ▶ 정수계획법 적용사례 수송모형과 유사하나 공장신설에 따르는 초기의 고정비용을 고려해야 한다는 점이 다르다. 총
수송량 총비용=고정비용+변동비용 변동비용=(수송비×수송량) 고정 비용 고정비용이 고려되는 경우의 비용함수

22 ▶ 정수계획법 적용사례 결정변수    Xij = 각 공장에서 대리점으로 수송하게 될 수송량    Y1,Y2 = 각각 1번과 2번의 공장후보입지에 공장을 신설할 것인지의 여부를 나타내는 변수(1이면 해당 후보지에 공장을 신설, 이면 신설하지 않는 경우 표현) 목적함수 : 총비용(수송비용 +공장신설비용)을 최소화    Min. Z = 5X11 + 8X X X21 + 9X22 + 6X23 + 7Y1 + 5Y2 제약조건 :    - 각 대리점에서의 수요량이 충족 조건         X11 + X21 = 80,000         X12 + X22 = 30,000         X13 + X23 = 40,000

23 ▶ 정수계획법 적용사례 제약조건 : - 공급지의 제약 : 신설예정인 공장의 공급능력이 규정되지 않았으므로 Big-M을 도입         X11 + X12 + X13 ≤ MY1         X21 + X22 + X23 ≤ MY2 최종 정리된 L그룹의 문제   Min. Z = 5X11 + 8X X X21 + 9X22 + 6X23 + 7Y1 + 5Y2  s. t.        X11 + X21   = 80,000                X12 + X22   = 30,000                X13 + X23   = 40,000                X11 + X12 + X13 ≤ MY1                X21 + X22 + X23 ≤ MY2                 Xij ≥ 0, Yi = 0 또는 1

24 제 7 장 정수계획법 수고하셨습니다…