제 7 장 정수계획법 (IP : Integer Programming)

Presentation on theme: "제 7 장 정수계획법 (IP : Integer Programming)"— Presentation transcript:

1 제 7 장 정수계획법 (IP : Integer Programming)

2 선형계획법과 그 변형

3 정수계획법 기본 개념 이산형 결정변수 정수계획법(IP: Integer Programming)의 종류
일반정수변수(general integer variables): 0,1,2,3,4, ... 이진정수변수(binary variables): 0/1(yes/no, true/false) 정수계획법(IP: Integer Programming)의 종류 순수정수계획법(Pure Integer Programming) 혼합정수계획법(Mixed Integer Programming) 二進정수계획법(0-1 Integer Programming)

4 정수계획법 기본 개념 정수계획법 해법 엑셀을 이용한 정수계획법 해법 ① Rounding-Off
② Cutting-Plane Method ③ Branch&Bound (분단탐색법) : 가장 효율적인 방법 엑셀을 이용한 정수계획법 해법 제한조건 : 정수 변수에 대해 정수 조건을 추가

5 LP 문제와 IP 문제의 비교 선형계획법(LP) 문제 (P1) Max z = 5x1 + 4x2 s.t. x1 ≤ 4

6 정수계획법(IP) 문제 #1 LP 완화문제 (LP Relaxation Problem) (P1)을 (P2)의 LP 완화문제 라고 함. (P2) Max z = 5x1 + 4x2 s.t x ≤ 4 x2 ≤ 6 3x1 + 2x2 ≤ 18 x1 ≥ 0, x2 ≥ 0, x1, x2 : 정수

7 LP와 IP의 실행가능영역 비교 (P1) : LP 문제 (P2) : IP 문제 F(P1) ⊇ F(P2)
Z(P1) ≥ Z(P2)

8 정수계획법(IP) 문제 #2 (P2)의 두 번째 제약조건식 x2 ≤ 6 을 x2 ≤ 5 로 수정한 경우
(P3) Max z = 5x1 + 4x2 s.t x ≤ 4 x2 ≤ 5 3x1 + 2x2 ≤ 18 x1 ≥ 0, x2 ≥ 0, x1, x2 : 정수

9 LP와 IP의 실행가능영역 비교 (P3)의 LP 완화문제의 최적해 x1=2.67, x2=5 최적 목적함수값 = 33.33

10 LIP : IP 문제의 LP 완화문제 ZLIP : LIP 문제의 최적 목적함수값 ZIP : IP 문제의 최적 목적함수값
IP 문제 (P3)의 최적해 : x1=4, x2=3, ZIP = 32 ZIP (= 32) ≤ ZLIP (= 33.33) 최대화 문제의 경우 : ZIP ≤ ZLIP 최소화 문제의 경우 : ZIP ≥ ZLIP

11 IP 문제의 해법 LP 완화 문제가 정수 최적해를 갖지 않는 경우 IP 문제의 최적해를 구하는 방법
Rounding-Off 방법 Cutting Plane 방법 Branch&Bound 방법 : 엑셀에서 이용

12 Rounding-Off 방법 (P3)의 LP 완화문제 최적해 : x1=2.67, x2=5, z = 33.33
Lower Rounding LP 완화문제의 최적해에서 소수점 이하 잘라 버림. x1=2, x2=5, z = 30 : 최적해가 아님. (near optimal) Upper Rounding LP 완화문제의 최적해에서 소수점 이하 올림. x1=3, x2=5, z = 35 : 실행불가능해

13 엑셀을 이용한 IP 해법 (P4) Max z = 35x1 + 30x2 s.t. x1 + x2 ≤ 200
x1 , x2 ≥ 0, x1, x2 : 정수

14 (P4)의 LP완화문제를 위한 해찾기 모델

15 (P4) 문제를 위한 정수화 조건 추가

16 정수화 조건이 추가된 해찾기모델 설정

17 실행 결과 → x1=117, x2=77 : IP문제의 최적해 아님

18 IP 문제의 최적해를 구하기 위한 고려 사항 해 찾기 설정 모델의 옵션(O) 항목 선택
해찾기 옵션 창의 허용한도(E)를 5% → 0% 수정입력

19 해 찾기 옵션의 허용 한도(E) 변경후의 최적해
최적해 x1=118, x2=76 목적함수값 = 6,410

20 순수 0-1 정수계획법 문제 문제 정의 모든 의사결정변수가 0 또는 1의 값을 가져야 하는 문제
순수 이진 정수계획법 문제 (pure binary integer programming problem) 라고도 함. 특정 의사결정 대안을 선택하느냐 선택하지 않느냐를 다루는 문제에 주로 적용

21 (예제 7-1) 자본투자문제(capital budgeting problem)
사업 수익(NPV) 소요자금 첫째 해 둘째 해 셋째 해 넷째 해 1 190 90 50 25 15 2 270 110 70 35 3 200 100 30 4 170 80 40 20 10 5 180 60 가용자금 300 (단위: 억원)

22 수학적 모형 결정변수 i = 1,2,3,4,5 에 대해 목적함수 Max z = 190x x x x x5 xi = 1, 만약 사업 i 가 선택되면, 0, 만약 사업 i 가 선택되지 않으면

23 제약조건 연도별 가용자금에 대한 제약조건 결정변수에 대한 제약조건
(첫째 해) 90x x x3 + 80x4 + 80x5 ≤ 300 (둘째 해) 50x x x3 + 40x4 + 60x5 ≤ 200 (셋째 해) 25x x x3 + 20x4 + 15x5 ≤ 80 (넷째 해) 15x x x3 + 10x4 + 15x5 ≤ 50 결정변수에 대한 제약조건 xi = 0 또는 1, i=1,2,3,4,5 → 다른 표현 방법 xi ∈ {0, 1}, i=1,2,3,4,5 xi ≥ 0, xi ≤ 1, xi :정수, i=1,2,3,4,5

24 엑셀입력 모형 <엑셀을 이용한 해 찾기>
① 셀범위 C7:G11에 수익의 현재가치 및 연도별 각 사업의 소요자금을 입력한다. 셀범위 D13:G13에 연도별 가용자금에 대한 데이터를 입력한다. ② 변경할 셀 : 셀범위 B7:B11 초기값으로 0을 입력한다. ③ 연도별 사용자금 계산 : D12:G12 D12 : =SUMPRODUCT(D7:D11,$B$7:$B$11) 셀 D12를 셀범위 E12:G12에 복사한다. ④ 목표 셀 : C15 목표 셀 C15에 총수익의 현재가치를 다음과 같이 계산한다. C15 : =SUMPRODUCT(C7:C11,B7:B11) 이상과 같이 엑셀 입력 모형을 완성하였다면, 도구(T) 메뉴의 해 찾기(V)를 선택하여, 해찾기 모델과 옵션을 설정한다.

25 해 찾기 모델 설정

26 최적해 <엑셀을 이용한 해 찾기>
① 셀범위 C7:G11에 수익의 현재가치 및 연도별 각 사업의 소요자금을 입력한다. 셀범위 D13:G13에 연도별 가용자금에 대한 데이터를 입력한다. ② 변경할 셀 : 셀범위 B7:B11 초기값으로 0을 입력한다. ③ 연도별 사용자금 계산 : D12:G12 D12 : =SUMPRODUCT(D7:D11,$B$7:$B$11) 셀 D12를 셀범위 E12:G12에 복사한다. ④ 목표 셀 : C15 목표 셀 C15에 총수익의 현재가치를 다음과 같이 계산한다. C15 : =SUMPRODUCT(C7:C11,B7:B11) 이상과 같이 엑셀 입력 모형을 완성하였다면, 도구(T) 메뉴의 해 찾기(V)를 선택하여, 해찾기 모델과 옵션을 설정한다.

27 특별한 경우의 제약조건 사업 1, 2, 3 중에서 최소한 하나의 사업은 반드시 선택되어야 한다면, x1 + x2 + x3 ≥ 1 사업 1, 2, 3 중에서 기껏해야 하나의 사업만을 선택해야 한다면, x1 + x2 + x3 ≤ 1 사업 1, 2, 3 중에서 반드시 하나의 사업만을 선택해야 한다면, x1 + x2 + x3 = 1 사업 1과 사업 3의 연관성으로 인해 사업 3이 수행될려면, 반드시 사업 1이 선택되어야 한다면, x3 ≤ x1

28 (예제 7-2) 0-1 배낭문제 (0-1 knapsack problem)
물건 무게(kg) 판매이익 1 10 22 2 3 8 11 25 4 5 14 12 26 6 9 20 7 16 15

29 수학적 모형 결정변수 i = 1,2,3,4,5,6,7,8 에 대해, 수학적 모형 Max z = 22x1 + 8x2 + 25x3 + 14x4 + 26x5 + 20x6 + 16x7 + 15x8 s.t x1+ 3x2 + 11x3 + 5x4 + 12x5 + 9x6+ 8x7 + 6x8 ≤ 35 xi ≥ 0, xi ≤ 1, xi : 정수, i=1,2,…,8 xi = 1, 만약 물건 i가 선택되면, 0, 만약 물건 i가 선택되지 않으면

30 해 찾기 모델 설정 및 최적해 해를 구하는 과정은 (예제 7-1)에서와 동일하다. 변경할 셀 : 셀범위 B6:B13
목표 셀 : D18 - 셀 D18 : =SUMPRODUCT(D6:D13,B6:B13) 배낭에 넣을 물건의 총 무게 계산 - 셀 D15 : =SUMPRODUCT(C6:C13,B6:B13) 제한조건 B6:B13 ≥ 0 B6:B13 ≤ 1 B6:B13 = 정수 D15 ≤ D16

31 (예제7-3) Set Covering 문제 행정구역 20km 안에 있는 행정구역 1 1, 3, 5, 8 2 2, 8, 10 3
1, 3, 7, 8 4 4, 9 5 1, 5, 7 6 6, 9 7 3, 5, 7 8 1, 2, 3, 8 9 4, 6, 9, 10 10 2, 9, 10

32 수학적 모형 결정변수 목적함수식 i = 1, … ,10 에 대해, xi =
Min z = x1+x2 +x3 +x4 +x5 +x6 +x7 +x8 +x9 +x10 xi = 1, 만약 구역 i 에 소방서가 설치되면, 0, 만약 구역 i 에 소방서가 설치되지 않으면

33 수학적 모형 제약조건식 x1+x3 +x5 +x8 ≥ 1 (1) x2+x8 +x10 ≥ 1 (2)
xi ≥ 0, xi ≤ 1, xi : 정수, i=1,2,…,10

34 엑셀 입력 모형 ① 셀범위 B7:K16에 특정 구역과 20km 내에 있는 구역들에 대한 정보를 입력한다. “1”이 입력된 셀의 의미는 그 셀의 열에 대응되는 구역에 소방서가 설치될 경우, 행에 대응되는 구역은 이 소방서에 의해 처리될 수 있음을 의미한다. 반면, “0”이 입력된 셀의 의미는 열에 대응되는 구역에 소방서가 설치되더라도, 행에 대응되는 구역은 이 소방서에 의해 처리될 수 없음을 의미한다. ② 변경할 셀 : 셀범위 B18:K18에 초기값 0을 입력한다. ③ 각 구역별 20km 내에 설치된 소방서의 수 계산 : L7 : =SUMPRODUCT(B7:K7,$B$18:$K$18) 셀 L7을 L8:L16에 복사한다. ④ 목표 셀 : L18 A시에 설치될 전체 소방서의 수를 계산한 수식을 입력한다. L18 : =SUM(B18:K18) 이상과 같이 엑셀 입력 모형이 완성되면 엑셀의 도구(T) 메뉴에서 해 찾기(V)를 선택하여 다음과 같이 제한조건을 입력 B$18:$K$18 = 2진수 L7:L16 >= N7:N16 여기서 제한조건 ‘B$18:$K$18 = 2진수'는 해당 셀범위에 대응되는 변수들이 0 또는 1의 값을 가져야 함을 의미 이는 앞에서 소개한 예제에서와 같이 다음과 같은 세 가지 제약조건을 사용하는 것과 같다. $B$18:$K$18>=0 $B$18:$K$18<=1 $B$18:$K$18=정수

35 해 찾기 모델 설정 ‘$B$18:$K$18=2진수’는 다음의 세 가지 제약조건을 사용하는 것과 같다.

36 최적해 구역 7, 8, 9에 소방서를 설치하면, 최소의 수로써 전체 10개의 구역을 모두 처리

37 일반 배낭문제 (general knapsack problem)
순수일반 정수계획법 문제 일반 배낭문제 (general knapsack problem) (예제 7-4) 보물종류 개당 무게(kg) 개당 가치(만원) 1 3.5 50 2 5.7 70 3 6.3 115 4 7.5 120 5 8.1 130 6 9.4 145

38 수학적 모형 결정변수 xi : 배낭에 넣는 보물 i 의 개수 (i =1,2,…,6) 목적함수식 제약조건
Min z = 50x1+70x2 +115x3 +120x4 +130x5 +145x6 제약조건 3.5x1+5.7x2 +6.3x3 +7.5x4 +8.1x5 +9.4x6 ≤ 100 xi ≥ 0, xi : 정수, i=1,2,…,6

39 엑셀 입력 모형 <엑셀에 의한 해 찾기> ① 변경할 셀 : D7:D12 ② 목표 셀 : D17
D17 : =SUMPRODUCT(C7:C12,D7:D12) ③ 셀 D14에는 배낭에 넣을 보물들의 총무게를 계산한다. D14 : =SUMPRODUCT(B7:B12,D7:D12) 이상과 같이 엑셀 입력 모형이 완성되면 엑셀의 도구(T) 메뉴에서 해 찾기(V)를 선택하여 다음과 같이 제한조건을 입력 D14 <= D15 D7:D12 = 정수 D7:D12 >= 0

40 최적해 <엑셀에 의한 해 찾기> ① 변경할 셀 : D7:D12 ② 목표 셀 : D17
D17 : =SUMPRODUCT(C7:C12,D7:D12) ③ 셀 D14에는 배낭에 넣을 보물들의 총무게를 계산한다. D14 : =SUMPRODUCT(B7:B12,D7:D12) 이상과 같이 엑셀 입력 모형이 완성되면 엑셀의 도구(T) 메뉴에서 해 찾기(V)를 선택하여 다음과 같이 제한조건을 입력 D14 <= D15 D7:D12 = 정수 D7:D12 >= 0

41 (예제 7-5) 다이어트 문제 (diet problem)
음식 에너지(kcal) 단백질 (g) 칼슘 (mg) 단위당 가격 최대 섭취량 빵(1) 110 4 2 3 치킨(2) 205 32 12 24 계란(3) 160 13 54 우유(4) 8 285 9 파이(5) 420 22 20 콩(6) 260 14 80 19 최소섭취량 2,200 60 1,000

42 수학적 모형 결정변수 xi : 음식 i 의 섭취량 (i =1,2,…,6) 목적함수식
Min z = 3x1+24x2 +13x3 +9x4 +20x5 +19x6

43 수학적 모형 제약조건 (영양소별 1일 요구량) 110x1+205x2 +160x3 +160x4 +420x5 +260x6 ≥ 2,200 4x1+ 32x x x x x6 ≥ 60 2x1+ 12x x3 +285x x x6 ≥ 1,000 (음식별 하루 최대 섭취량) x1 ≤ 4, x2 ≤ 3, x3 ≤ 2, x4 ≤ 8, x5 ≤ 2, x6 ≤ 2 xi ≥ 0, xi : 정수, i=1,2,…,6

44 엑셀 입력 모형 ① 변경할 셀 : F6:F11 ② 목표 셀 : F13
F13 : =SUMPRODUCT(E6:E11,F6:F11) ③ 셀 범위 B12:D12에는 각 영양소의 실제 섭취량을 계산한다. B12 : =SUMPRODUCT(B6:B11,$F$6:$F$11) B12를 C12:D12에 복사한다. 이상과 같이 엑셀 입력 모형이 완성되면 엑셀의 도구(T) 메뉴에서 해 찾기(V)를 선택하여 다음과 같이 제한조건을 입력 $B$12:$D$12 >= B$13:$D$13 $F$6:$F$11 >= $G$6:$G$11 $F$6:$F$11 = 정수 $F$6:$F$11 >= 0

45 최적해

46 혼합 정수계획법 문제 (정의) 혼합 정수계획법 문제(mixed IP problem)
의사결정 변수들 중 일부는 정수화 조건이 주어지고, 나머지에는 정수화 조건이 주어지지 않는 문제

47 (예제 7-6) 고정비(fixed charge) 문제
기계 고정비 (단위: 만원) 변동비 최대 생산능력 1 4,000 7 700 2 3,000 7.5 600 3 2,000 8 800 4 8,000 6 1,500 5 9,000 1,200

48 수학적 모형 결정변수 xi : 기계 i 에서의 범퍼 생산량 (i =1,2,…,5) yi 변수를 추가하여 다음 관계식을 설정
C1(x1) = 7x1 + 4,000, x1 > 0 일 때 0, x1 = 0 일 때 yi = 1, 만약 xi > 0 0, 만약 xi = 0

49 수학적 모형 목적함수식 : 총비용(고정비+변동비) 최소화
Min z = 7x1+7.5x2 +8x3 +6x4 +5x5 +4,000y1 +3,000y2 +2,000y3 +8,000y4 +9,000y5

50 수학적 모형 제약조건 (총생산량이 주문량보다 커야 하는 조건) x1+ x2 + x3 + x4 + x5 ≥ 2,500
(각 기계에서 최대로 생산가능한 양에 대한 조건) x1 ≤ 700 y1 , x2 ≤ 600 y2 , x3 ≤ 800 y3 , x4 ≤ 1,500 y4 , x5 ≤ 1,200 y5 (결정변수에 대한 조건) xi ≥ 0, yi = 0 또는 1, i=1,2,…,5

51 (해설) 제약조건 x1 ≤ 700 y1 은 다음 관계를 만족시킨다.
Min z = 7x1+4,000y1+7.5x2 +3,000y2 +8x3 +2,000y3 +…. 에 의해 최적해 상태에서는 반드시 y1 = 0 이 된다. 역으로, y1 이 1인 경우, x1 ≤ 700 이 된다. 따라서, 제약조건 x1 ≤ 700 y1 은 (x1, y1) 이 (0, 0) 또는 (0 <x1≤ 700, 1) 임을 나타낸다. y1 = 1, 만약 x1 > 0 0, 만약 x1= 0

52 엑셀 입력 모형 ① 변경할 셀 : 셀 범위 E5:E9 (기계 사용 여부를 나타내는 yi 변수에 해당)
셀 범위 F5:F9 (각 기계별 생산량을 나타내는 xi 변수에 해당) ② 목표 셀 : F13 F13 : =SUMPRODUCT(B5:B9,E5:E9)+SUMPRODUCT(C5:C9,F5:F9) 이는 다음과 같이 하나로 나누어 나타내어도 된다. F13 : =SUMPRODUCT(B5:C9,E5:F9) ③ 셀 F11에는 기계별 생산량의 총합을 나타낸다. F11 : =SUM(F5:F9) ④ 셀 범위 G5:G9 (두 번째 제약조건식들의 부등호 우변항을 나타냄.) G5 : =D5*E5 G5를 G6:G9에 복사한다. 이상과 같이 엑셀 입력 모형이 완성되었으면, 엑셀 도구(T) 메뉴의 해 찾기(V)를 선택하여, 다음과 같이 변경할 셀, 목표 셀, 제한조건을 입력한다. 변경할 셀 : E5:F9 목표 셀 : F13 제한조건 : E5:E9 <= 1 E5:E9 = 정수 E5:E9 >= 0 F11 >=F12 F5:F9 <= G5:G9 F5:F9 >= 0

53 최적해