경영과학(Ⅰ) 제4장 쌍대이론과 민감도 분석 서론 쌍대이론 쌍대심플렉스법 민감도분석 secom.hanbat.ac.kr.

Presentation on theme: "경영과학(Ⅰ) 제4장 쌍대이론과 민감도 분석 서론 쌍대이론 쌍대심플렉스법 민감도분석 secom.hanbat.ac.kr."— Presentation transcript:

1 경영과학(Ⅰ) 제4장 쌍대이론과 민감도 분석 서론 쌍대이론 쌍대심플렉스법 민감도분석 secom.hanbat.ac.kr

2 제4장 쌍대이론과 민감도 분석 ▶ 서론 선형계획법의 한계성 : 선형계획모형의 4가지 가정(비례성, 가합성, 가분성, 확실성) ☞ 실제 문제에서는 ? → 현실상황에 대한 반영이 미흡 민감도분석(敏感度分析 ; sensitibility analysis) : 선형계획모형의 정적인 단점 보완 : 최적이후분석(post-optimality analysis) 또는 사후적 분석 쌍대이론(雙對理論 ; duality theory) :  원문제와 쌍대문제의 관계를 규명 → 민감도분석의 기본이론 : 쌍대문제 → 특정 상황의 문제(원문제)를 상대적인 측면에서 본 문제

3 제4장 쌍대이론과 민감도 분석 ▶ 서론 ⊙ 장님의 산 오르기 ?

4 ▶ 쌍대이론 ◁ 쌍대문제의 정의 ▷ 전형적인 원문제와 쌍대문제 < 원 문 제 > < 쌍 대 문 제 >
제4장 쌍대이론과 민감도 분석 ▶ 쌍대이론 ◁ 쌍대문제의 정의 ▷ 전형적인 원문제와 쌍대문제 < 원 문 제 > < 쌍 대 문 제 > Min. W = bt X s. t At Y ≥ Ct Y ≥ 0 Max. Z = c X s. t AX ≤ b X ≥ 0 벡터와 행렬 구조로 표시  X1 … Xj … Xn C1 … Cj … Cn a1 … a1j … a1n ： ： ： am1 … amj … amn b1 ： bm 원문제의 우변상수 = 쌍대문제의 목적함수계수 원문제의 목적함수계수 = 쌍대문제의 우변상수 원문제의 결정변수 쌍대문제의 제약식 Y1 ： Ym 쌍대문제의 결정변수 원문제의 제약식

5 ▶ 쌍대이론 T화학 문제의 경우 < 원 문 제 > Max. Z = 40X1 + 30X2 (총이익)
제4장 쌍대이론과 민감도 분석 ▶ 쌍대이론 T화학 문제의 경우 < 원 문 제 > Max. Z = 40X1 + 30X2 (총이익)      s. t.            4X1 + 5X2  ≤ 200  (원료 A의 사용량 제약)                             2X2  ≤  50  (원료 B의 사용량 제약)                    X1 + 3X2  ≤ 210  (원료 C의 사용량 제약)                       X1, X2 ≥ 0 < 쌍 대 문 제 > Min. W = 200Y1 + 50Y Y3       s. t.          4Y1       Y3  ≥ 40                      5Y Y Y3  ≥ 30                      Y1, Y2, Y3 ≥ 0

6 ▶ 쌍대이론 제4장 쌍대이론과 민감도 분석 T 화학 제품 생산 등 S 화학 원료A, B, C 필요 Y1 Y3 Y2 구입가격
구입희망 C 원료 A 210 200 B 50 제품 가 나 40 30

7 ▶ 쌍대이론 ◁ 쌍대문제의 경제적인 의미 ▷ 최대화문제의 경우(T화학 문제) : 상대적인 입장의 S화학을 고려
제4장 쌍대이론과 민감도 분석 ▶ 쌍대이론 ◁ 쌍대문제의 경제적인 의미 ▷ 최대화문제의 경우(T화학 문제) : 상대적인 입장의 S화학을 고려 쌍대변수, Y1, Y2, Y3 S화학에서 T화학이 보유하고 있는 원료를 구입하는 경우, 각 원료의 단위당 구입가(원가에 추가로 지불하는 금액) 목적함수, Min. W = 200Y1 + 50Y Y3 S화학에서 원료구입을 위해 지불하는 총비용 T화학에서는 A원료 4단위와 C원료 6단위로 40만원의 이익이 보장되는 가 제품을 생산할 수 있으므로, S화학으로서는 A원료 4단위와 C원료 6단위를 구입하는데 40만원 이상을 금액을 T화학에 제시해야 거래조건이 성립된다고 할 수 있다.(나 제품에 대하여도 마찬가지) 제약조건 4Y1      + 6Y3 ≥ 40(T화학이 제품 가의 생산을 포기하는 조건)  5Y1+ 2Y2+ 3Y3 ≥ 30(T화학이 제품 나의 생산을 포기하는 조건)

8 ▶ 쌍대이론 ◁ 쌍대문제의 경제적인 의미 ▷ 쌍대문제의 최적해,
제4장 쌍대이론과 민감도 분석 ▶ 쌍대이론 ◁ 쌍대문제의 경제적인 의미 ▷ 쌍대문제의 최적해, : (Y1, Y2, Y3) = (10/3, 0, 40/9)    ☞ S화학에서는 T화학이 보유한 원료 A와 C에 대해 원래의 가격에 10/3만원과 40/9만원을 더 주고 구입하는 것이 총비용을 1,600으로 최소화할 수 있다는 의미. ☞ S 화학에서 T화학이 보유한 원료를 구입하려면, T화학의 예상최대이익과 같은 비용을 들여야 함

9 ▶ 쌍대이론 최소화문제의 경우 예제 모형 비타민과 음식물 문제 음식물(단위 : kg) 비타민 A 비타민 C 가격(원)
제4장 쌍대이론과 민감도 분석 ▶ 쌍대이론 최소화문제의 경우 예제 모형   비타민과 음식물 문제  음식물별 비타민 함유량 음식물(단위 : kg) 비타민 A 비타민 C 가격(원) 음식물 1  1   4  500 음식물 2 3 2 300 일일 필요량 10 20

10 ▶ 쌍대이론 원문제 Min. Z = 500X1 + 300X2 (총비용)
제4장 쌍대이론과 민감도 분석 ▶ 쌍대이론 원문제 Min. Z = 500X X2 (총비용)  s. t.            X1 + 3X2  ≥ 10 (비타민 A의 필요섭취량 제약)          X1 + 2X2  ≥ 20 (비타민 C의 필요섭취량 제약)                X1, X2 ≥ 0 원문제의 최적해, (X1, X2) = (4, 2), Z = 2,600 Max. W = 10Y1 + 20Y2 (총판매이익)   s. t     Y1  + 4Y2 ≤ 500 (음식물 1의 대체조건)                 3Y1  + 2Y2 ≤ 300 (음식물 2의 대체조건)                    Y1, Y2 ≥ 0 쌍대문제   음식물 1, 2를 각각 4kg, 2kg 구입하는 것이 총비용을 ,600으로 하는 최적구입계획이다. 쌍대문제의 최적해, (Y1, Y2) = (120, 20), W = 2,600

11 ▶ 쌍대이론 쌍대변수, Y1, Y2 : 비타민 A와 C를 판매하는 경우, 각 비타민의 단위당 이익
제4장 쌍대이론과 민감도 분석 ▶ 쌍대이론 쌍대변수, Y1, Y2  : 비타민 A와 C를 판매하는 경우, 각 비타민의 단위당 이익 목적함수, Max. W = 10Y1 + 20Y2 : 한 사람의 수요에 대해 기대되는 총이익 최대화 제약조건, Y1  + 4Y2 ≤ 500 ,  3Y1  + 2Y2 ≤ : 음식물 1은 가격이 500원인데, 비타민A를 1단위, C를 4단위 함유하고 있으므로, 구입에 소요되는 비용(Y1 + 4Y2)이 500원을 넘지 않아야 구입(음식물 2에 대해서도 마찬가지) 최적해, (Y1, Y2) = (120, 20), W = 2,600   : 비타민 A는 단위당 120원, 비타민 C는 20원으로 책정해야 판매이익 최대(원문제와 쌍대문제의 목적함수 값이 동일)

12 ▶ 쌍대이론 ◁ 원-쌍대 관계 ▷ 일반적인 원-쌍대 전환 방법 원문제(쌍대문제) 쌍대문제(원문제) ① 목적함수 : 최대화
제4장 쌍대이론과 민감도 분석 ▶ 쌍대이론 ◁ 원-쌍대 관계 ▷ 일반적인 원-쌍대 전환 방법 원문제와 쌍대문제의 변환 원문제(쌍대문제) 쌍대문제(원문제) ① 목적함수 : 최대화 ① 최소화 ② i 번째 제약식     ≤ 형태의 제약식      = 형태의 제약식 ② i 번째 변수, Yi     비음조건 있는 변수(Yi ≥ 0)      비음조건 없는 변수 ③ j 번째 변수, Xj     비음조건 있는 변수(Xj ≥ 0)     비음조건 없는 변수 ③ j 번째 제약식     ≥ 형태의 제약식 

13 ▶ 쌍대이론 ◁ 원-쌍대 관계 ▷ 예제 모형 Max. Z = 5X1 +7X2 + 2X3 원문제
제4장 쌍대이론과 민감도 분석 ▶ 쌍대이론 ◁ 원-쌍대 관계 ▷ 예제 모형         Max. Z = 5X1 +7X2 + 2X3         s. t.    X1 -  X2 + 2X3   ≤ 5                               X2 - 3X3   =                -3X1 + 4X2 +  X3   ≥ 3                          X1, X2, X3 ≥ 0 원문제       Min. W = 5Y1 + 2Y2 - 3Y3            s. t.     3Y1            + 3Y3  ≥                    -Y1 +  Y2   - 4Y3  ≥ 7                      2Y1 - 3Y2   -  Y3  ≥ 2                        Y1, Y3 ≥ 0, Y2 : 비음제약 없음 쌍대문제

14 ▶ 쌍대이론 최적심플렉스표에서의 최적쌍대해 (1) 쌍대정리(duality theorem)
제4장 쌍대이론과 민감도 분석 ▶ 쌍대이론 최적심플렉스표에서의 최적쌍대해 (1) 쌍대정리(duality theorem) ① 원문제가 무한대해를 가지면 쌍대문제는 실행불가능하며,      원문제가 실행불가능하면 쌍대문제는 무한대해를 갖는다.  ② 원문제가 유한한 최적해를 가지면 쌍대문제도 유한한 최적해를     가지며, 두 목적함수값은 서로 같다. (2) 상보(相補)여유정리(complementary slackness theorem) 원문제가 최적해를 가지면 쌍대문제도 최적해를 가지며, 다음과 같은 관계가 성립한다.  ① (원문제의 j번째 변수 값) × (쌍대문제의 j번째 여유(잉여)변수 값) = 0  ② (쌍대문제의 i번째 변수 값) × (원문제의 i번째 여유(잉여)변수 값) = 0

15 ▶ 쌍대이론 ◁ 원-쌍대 관계 ▷ T화학 문제의 경우 < 원 문 제 > < 쌍 대 문 제 >
제4장 쌍대이론과 민감도 분석 ▶ 쌍대이론 ◁ 원-쌍대 관계 ▷ T화학 문제의 경우 < 원 문 제 > Min. W = 200Y1 + 50Y Y3   s. t.         4Y1           + 6Y3 ≥ 40                  5Y1 + 2Y2 + 3Y3 ≥ 30                     Y1, Y2, Y3 ≥ 0  < 쌍 대 문 제 > Max. Z = 40X1 + 30X2     s. t.      4X1 + 5X2  ≤ 200                          2X2  ≤ 50                 6X1 + 3X2  ≤ 210                      X1, X2 ≥ 0 

16 ▶ 쌍대이론 ◁ 원-쌍대 관계 ▷ 제4장 쌍대이론과 민감도 분석 T화학 원문제의 최적심플렉스표 Cj 40 30 기저변수 Cb
◁ 원-쌍대 관계 ▷ T화학 원문제의 최적심플렉스표 Cj 40 30 기저변수 Cb X1 X2 S1 S2 S3 우변상수 2 1 1/3 -2/3 -1/6 -2/9 4/9 5/18 20 10 25 Zj  Cj – Zj 10/3 -10/3 40/9 -40/9 1,600 파란색으로 표시된 부분이 쌍대문제의 해 즉, 쌍대문제의 최적해는  (Y1, Y2, Y3) = (10/3, 0, 40/9) 이다.

17 ▶ 쌍대이론 제4장 쌍대이론과 민감도 분석 T화학 쌍대문제의 최적심플렉스표 Cj 200 50 210 M 기저 변수 Cb Y1
M 기저 변수 Cb Y1 Y2 S1 S2 A1 A2 우변상수 Y3 1 -4/9 2/3 -5/18 1/6 2/9 -1/3 5/18 -1/6 -2/9 40/9 10/3 Zj  Cj – Zj 40 10 -25 25 -20 20 M-25 M-20 1,600 쌍대의 쌍대는 원문제이므로 원문제의 최적해 (X1, X2) = (25, 20) 위의 두 심플렉스표에서 쌍대정리, 상보여유정리가 성립함을 알수 있음

18 제4장 쌍대이론과 민감도 분석 ▶ 쌍대심플렉스법 쌍대심플렉스법(dual simplex method) : 최적조건 만족으로 출발 → 실행가능조건이 만족되면 최적해 얻음 1단계 : 초기 심플렉스표의 작성 :  우변상수에 음수가 존재하는 선형계획모형에 대해 초기 심플렉스표 작성 쌍대심플렉스법의 절차 2단계 : 최적해 여부 검사 및 탈락변수 결정 : 실행가능조건 만족여부 검사→ 우변상수에 음수가 없으면 최적해, 음수가 있으면 가장 작은 음수(절대값이 가장 큰 음수)를 탈락변수로 결정 3단계 : 진입변수 결정 : 탈락변수 행의 음수인 계수로 Cj - Zj 값을 나누어 그 절대값이 가장  작은 열의 변수를 진입변수로 결정 4단계 : 새로운 심플렉스표의 작성 : 진입변수 열과 탈락변수 행이 만나는 점을 기준요소로 행 연산을 실시하여 해를 개선

19 ▶ 쌍대심플렉스법 예제 모형 Min. Z = 2X1 + X2
제4장 쌍대이론과 민감도 분석 ▶ 쌍대심플렉스법 예제 모형  Min. Z = 2X1 + X2     s. t.    3X1 +   X2  ≥ 3               4X1 + 3X2  ≥ 6                 X1 + 2X2  ≤ 3                   X1, X2 ≥ 0  Min. Z = 2X1 + X2     s. t.   - 3X1 -   X2 + S = -3              - 4X1 - 3X S2 = -6                 X1 + 2X2   S3 = 3                 X1, X2, S1, S2 S3 ≥ 0

20 ▶ 쌍대심플렉스법 초기 심플렉스표의 작성 Cj 2 1 기저변수 Cb X1 X2 S1 S2 S3 우변상수 -3 -4 -1 0 1
제4장 쌍대이론과 민감도 분석 ▶ 쌍대심플렉스법 초기 심플렉스표의 작성 최적조건 만족(최소화문제) Cj 2 1 기저변수 Cb X1 X2 S1 S2 S3 우변상수 -3 -4 -1 0 1 -3(실행불가능) -6(실행불가능) 3 Zj  Cj – Zj 최적여부 검사 및 탈락변수 결정 : 최적조건은 만족, 실행가능조건이 불만족   → 절대값이 큰 음수인 S2를 탈락변수로 선택

21 ▶ 쌍대심플렉스법 Cj 2 1 기저변수 Cb X1 X2 S1 S2 S3 우변상수 -3 -4 -1 0 1 -6(탈락) 3 Zj
제4장 쌍대이론과 민감도 분석 ▶ 쌍대심플렉스법 진입변수 결정  : 최소비율검사 - (Cj – Zj를) / (│탈락변수 행의 음수인 계수│) 계산 → X1열 : 1/2,  X2열 : 1/3 이므로 X2를 진입변수로 결정 탈락변수와 진입변수 결정 Cj 2 1 기저변수 Cb X1 X2 S1 S2 S3 우변상수 -3 -4 -1 0 1 -6(탈락) 3 Zj  Cj – Zj * 비율의 절대값 : 2/4   1/3(진입)

22 ▶ 쌍대심플렉스법 Cj 2 1 기저변수 Cb X1 X2 S1 S2 S3 우변상수 -5/3 4/3 -1/3 2/3 0 1 -1
제4장 쌍대이론과 민감도 분석 ▶ 쌍대심플렉스법 새로운 심플렉스표의 작성 :  탈락변수 행과 진입변수 열의 교차점인 -3을 기준요소로 행연산 수행 두 번째 심플렉스표 Cj 2 1 기저변수 Cb X1 X2 S1 S2 S3 우변상수 -5/3 4/3 -1/3 2/3 0 1 -1 Zj  Cj – Zj 1/3

23 ▶ 쌍대심플렉스법 Cj 2 1 기저변수 Cb X1 X2 S1 S2 S3 우변상수 -3/5 4/5 -1 -1/5 0 1 3/5
제4장 쌍대이론과 민감도 분석 ▶ 쌍대심플렉스법 같은 과정을 한번 더 반복한 후의 최종 심플렉스표 최종 심플렉스표 Cj 2 1 기저변수 Cb X1 X2 S1 S2 S3 우변상수 -3/5 4/5 -1 -1/5 0 1 3/5 6/5 Zj  Cj – Zj -2/5 2/5 1/5 12/5

24 ▶ 민감도 분석 민감도분석이란? 민감도분석은 선형계획모형의 한계점을 보완하기 위한 수단
제4장 쌍대이론과 민감도 분석 ▶ 민감도 분석 민감도분석이란? 민감도분석은 선형계획모형의 한계점을 보완하기 위한 수단 초기 상황에 변화가 생길 경우 해가 어떻게 달라지는지 파악 민감도분석 과정에서 나타나는 상황 1. 현재의 기저변수가 바뀌지 않는다. 2. 현재의 해가 실행불가능해진다. → 쌍대심플렉스법 적용 3. 현재의 해가 비최적이 된다. → 원 심플렉스법 적용

25 ▶ 민감도 분석 ◁ 민감도분석의 예(T화학문제) ▷
제4장 쌍대이론과 민감도 분석 ▶ 민감도 분석 Max. Z = 40X1 + 30X2 (총이익) s. t.            4X1 + 5X2  ≤ 200  (원료 A 제약)                   2X2  ≤  50  (원료 B 제약)    X1 + 3X2  ≤ 210  (원료 C 제약)                 X1, X2 ≥ 0 ◁ 민감도분석의 예(T화학문제) ▷ 목적함수 계수의 변화   : 제품 가의 단위당 이익이 얼마가 되면 현재의 최적생산계획이 수정되겠는가? 최적해 : (X1, X2) = (25, 20), Z = 1,600 우변상수의 변화 :  원료 A의 사용한도가 200에서 150으로 감소한다면 ? 새로운 변수의 추가 : 신제품 다 (단위당 이익: 20원, 원료 A와 B를 3톤, 1톤 사용)를 판매하기 위해 생산에 착수하는 것이 바람직한가 ? 새로운 제약조건의 추가 : 시장조사 결과 제품의 총수요가 40을 넘지 않을 것이라고 한다면?

26 ▶ 민감도 분석 ◁ 목적함수 계수의 변화 ▷ 최적성의 범위 : 최적해가 변하지 않는 목적함수 계수의 범위
제4장 쌍대이론과 민감도 분석 ▶ 민감도 분석 ◁ 목적함수 계수의 변화 ▷ 최적성의 범위 : 최적해가 변하지 않는 목적함수 계수의 범위 X2 등이익선 기울기 : 기울기 -2 B(25,20) C(35,0) 50 X1 25 40 A(20,25) 기울기 제품 가의 단위당 이익을 c1이라 하면 등이익선의 기울기는 -c1/30 이 값이 -2와 -4/5 사이에 있으면 최적해 불변 4/5 < c1/30 < 2 → 24 < c1 < 60 ☞ c1의 최적성의 범위

27 ▶ 민감도분석 심플렉스표에서 최적성의 범위 계산 Cj c1 30 기저변수 Cb X1 X2 S1 S2 S3 우변상수 1 20
제4장 쌍대이론과 민감도 분석 ▶ 민감도분석 심플렉스표에서 최적성의 범위 계산 Cj c1 30 기저변수 Cb X1 X2 S1 S2 S3 우변상수 1 20 10 25 Zj  Cj – Zj 1,600 → 최적이 되려면 Cj - Zj의 값이 음수, 즉, c1/ <0, 20/3 - 5c1/18 <0 → 이를 계산하면  24 < c1 < 60이 된다.

28 ▶ 민감도분석 최적성의 변화에 따른 새로운 해의 계산 : 제품 나의 단위당 이익(c2)가 55로 변하는 경우 Cj 40 55
제4장 쌍대이론과 민감도 분석 ▶ 민감도분석 최적성의 변화에 따른 새로운 해의 계산 :  제품 나의 단위당 이익(c2)가 55로 변하는 경우 Cj 40 55 기저변수 Cb X1 X2 S1 S2 S3 우변상수 1 20 (최소비) 25 Zj  Cj – Zj 1,600 (비최적) → S3를 진입, S2를 탈락시킴

29 ▶ 민감도분석 Cj 40 55 기저변수 Cb X1 X2 S1 S2 S3 우변상수 1 25 Zj Cj – Zj 50 10 -10
제4장 쌍대이론과 민감도 분석 ▶ 민감도분석 Cj 40 55 기저변수 Cb X1 X2 S1 S2 S3 우변상수 1 25 Zj  Cj – Zj 50 10 -10 2,125 (최적) : 새로운 최적해 (X1, X2) = (18.75, 25), 최대이익은 2,125

30 ▶ 민감도 분석 ◁ 우변상수의 변화 ▷ 실행가능성의 범위 제4장 쌍대이론과 민감도 분석 B C 50 40 70 30 F D A
◁ 우변상수의 변화 ▷ X2 B C 50 X1 40 70 30 F D A G E 실행가능성의 범위 원료 A : 200 → 150으로 줄어들면 실행가능영역이 그림과 같이 좁아짐 최적점은 B에서 E로 바뀌지만 생산량만 달라질 뿐 기저변수가 변하지는 않음 원료 A가 더 줄어C(35, 0)나 F(0, 25)가 최적해가 되면 해가 근본적으로 달라짐 원료 A의 사용한도를 b1이라 하면, -C점을 지날 때 b1=4×35+5×0 = G점을 지날 때 b1=4×22.5+5×25=215 즉, 140 ≤ b1 ≤ 215이면 기저변수가 바뀌지 않음(b1의 실행가능성의 범위)

31 제4장 쌍대이론과 민감도 분석 ▶ 민감도분석 심플렉스표에서의 실행가능성의 범위 계산 : 첫 번째 우변상수의 값이 200에서 d만큼 증가한 경우(200+d) → 새로운 우변상수 값은 다음 표와 같이 변함 Cj 40 30 기저변수 Cb X1 X2 S1 S2 S3 우변상수 1 1/3 -2/3 -1/6 -2/9 4/9 5/18 20 + d × 1/3 10 - d × 2/3 25 - d × 1/6 Zj  Cj – Zj 10/3 -10/3 40/9 -40/9 1,600 + d× 10/3 : 실행가능하려면, ①20 + d/3 ≥ 0, ②10 - 2d/3 ≥ 0, ③25 - d/6 ≥ 0 → -60 ≤ d ≤ 15이므로 b1의 실행가능성 범위는 140 ≤ b1 ≤ 215

32 ▶ 민감도분석 Cj 40 30 기저변수 Cb X1 X2 S1 S2 S3 우변상수 1 1/3 -2/3 -1/6 -10(탈락)
제4장 쌍대이론과 민감도 분석 ▶ 민감도분석 실행가능성의 변화에 따른 새로운 해의 계산 : 원료 A의 사용한도가 230, 즉, b1 = 으로 증가한 경우, Cj 40 30 기저변수 Cb X1 X2 S1 S2 S3 우변상수 1 1/3 -2/3 -1/6 -2/9 4/9 5/18 -10(탈락) Zj  Cj – Zj 10/3 -10/3 40/9 -40/9 (진입) : 실행불가능하므로 쌍대심플렉스법을 적용(S2 탈락, S1 진입)

33 ▶ 민감도분석 Cj 40 30 기저변수 Cb X1 X2 S1 S2 S3 우변상수 1 25 15 Zj Cj – Zj 5 -5
제4장 쌍대이론과 민감도 분석 ▶ 민감도분석 Cj 40 30 기저변수 Cb X1 X2 S1 S2 S3 우변상수 1 25 15 Zj  Cj – Zj 5 -5 1,650 : 새로운 최적해는 (X1, X2) = (22.5, 25), 최대이익 Z = 1,650 (앞 그림의 G점에 해당)

34 제4장 쌍대이론과 민감도 분석 ▶ 민감도 분석 ◁ 새로운 변수의 추가 ▷ 신제품 다를 개발한 경우 -제품 다의 단위당 이익 20원, -단위 생산당 원료A를 3톤, 원료B를 1톤 사용 X3 = 신제품 다의 생산량이라 정의 심플렉스표에 변수 X3의 열이 추가 그 계수는 첫 번째 제약조건(원료A)과 두 번째 제약조건식 (원료B)에 대응하는 S1, S2열에 각각 3, 1을 곱하여 더한 것임 즉, 3*[1/3, -2/3, -1/6]t + 1*[0, 1, 0]t = [1, -1, -1/2]t

35 ▶ 민감도 분석 Cj 40 30 20 Cb X1 X2 X3 S1 S2 S3 1 -1 -1/2 20<탈락> 10 25
제4장 쌍대이론과 민감도 분석 ▶ 민감도 분석 새로운 변수의 도입(X3) Cj 40 30 20 기저변수 Cb X1 X2 X3 S1 S2 S3 우변상수 1 -1 -1/2 20<탈락> 10 25 Zj  Cj – Zj 1,600 <비최적> : 비기저변수(X3)의 수정비용이 양수이므로 최적이 아니다. → X3 진입, X1 탈락

36 ▶ 민감도 분석 Cj 40 30 20 Cb X1 X2 X3 S1 S2 S3 1 ½ 35 Zj Cj – Zj -10 1,800
제4장 쌍대이론과 민감도 분석 ▶ 민감도 분석 새로운 변수의 도입에 따른 최적해 Cj 40 30 20 기저변수 Cb X1 X2 X3 S1 S2 S3 우변상수 1 35 Zj  Cj – Zj -10 1,800   : 새로운 최적해는 (X1, X2, X3) = (35, 0, 20), 최대이익, Z = 1,800 : 즉, 신제품 다를 20단위 생산, 가는 35로 생산량 증가(나는 생산하지 않음)

37 ▶ 민감도 분석 ◁ 새로운 제약조건의 추가 ▷ 제품의 수요조사 결과에 따른 변화 수요조사 결과 제품의 총수요가 40이하인 경우
제4장 쌍대이론과 민감도 분석 ▶ 민감도 분석 ◁ 새로운 제약조건의 추가 ▷ 제품의 수요조사 결과에 따른 변화 수요조사 결과 제품의 총수요가 40이하인 경우 D(새로운 최적해) X2 B C 50 X1 40 70 25 E A 새로운 제약식 X1 + X2 ≤ 40 이라는 새로운 제약조건의 추가 기존의 최적해(B점)는 실행불가능 점 D(30, 10)가 새로운 최적해

38 ▶ 민감도분석 제4장 쌍대이론과 민감도 분석 심플렉스표에서의 제약조건 추가 분석
새로운 제약식 X1 + X2 ≤ 40을 심플렉스표형으로 만들면 X1 + X2 + S4 = 40 심플렉스표상에 S4를 위한 행과 열 추가 최적 심플렉스표상에서 S4를 기저변수로 하기 위해서는 X1과 X2를 비기저변수로 표시 즉, X1 - S1/6 + 5S3/18 = 25 ,   X2 + S1/3 - 2S3/9  = 20  에서,    → X1 = 25 + S1/6 - 5S3/18 ,  X2 = 20 - S1/3 + 2S3/9 이를 새로운 제약식에 대입하면 -S1/6 - S3/18 + S4 = -5 이 됨

39 ▶ 민감도 분석 Cj 40 30 Cb X1 X2 S1 S2 S3 S4 1 20 10 25 -5 Zj Cj – Zj 1,600
제4장 쌍대이론과 민감도 분석 ▶ 민감도 분석 새로운 제약식의 도입(X1 + X2 ≤ 40) Cj 40 30 기저변수 Cb X1 X2 S1 S2 S3 S4 우변상수 1 1/3 -2/3 -1/6 -2/9 4/9 5/18 -1/18 20 10 25 -5 Zj  Cj – Zj 10/3 -10/3 40/9 -40/9 1,600 (진입) : 실행불가능 → S4 탈락, S1 진입

40 ▶ 민감도 분석 Cj 40 30 Cb X1 X2 S1 S2 S3 S4 1 2 -4 -1 -6 10 Zj Cj – Zj 20
제4장 쌍대이론과 민감도 분석 ▶ 민감도 분석 새로운 제약식의 도입후의 최적해 Cj 40 30 기저변수 Cb X1 X2 S1 S2 S3 S4 우변상수 1 -1/3 2/3 1/3 2 -4 -1 -6 10 Zj  Cj – Zj 10/3 -10/3 20 -20 1,500 : 새로운 최적해는 (X1, X2) = (30, 10), 최대이익 Z = 1,500

41 경영과학(Ⅰ) 제4장 쌍대이론과 민감도 분석 수고하셨습니다… secom.hanbat.ac.kr