모형화와 한계 제2장 선형계획법 : 기본개념과 모형화 선형계획법의 유형 도해법과 해의 분석 특수한 해

Presentation on theme: "모형화와 한계 제2장 선형계획법 : 기본개념과 모형화 선형계획법의 유형 도해법과 해의 분석 특수한 해"— Presentation transcript:

1 모형화와 한계 제2장 선형계획법 : 기본개념과 모형화 선형계획법의 유형 도해법과 해의 분석 특수한 해
secom.hanbat.ac.kr 경영과학(Ⅰ) 제2장 선형계획법 : 기본개념과 모형화 모형화와 한계 선형계획법의 유형 도해법과 해의 분석 특수한 해

2 ▶ 모형화와 한계 수리계획법(mathematical programming) : 현실에서 부딪히는 의사결정 상황을 수학적 모형(수리계획모형)으로 작성하여 그 해를 구함으로써 최적 의사결정을 도모하는 방법 수리계획모형의 세가지 구성요소 의사결정변수(decision variable) : 의사결정의 대상 목적함수(objective function) : 의사결정의 목표 제약조건(constraints)  :　목표를 성취하는 과정에서 제한되는 한계

3 ▶ 모형화와 한계 수리계획법의 종류 선형계획법(Linear Programming ; LP) : 목적함수와 제약조건식이 모두 1차식으로 표현 비선형계획법(Non-Linear Programming ; NLP) : 1차식으로만 표현되지 않는 모형 정수계획법(Integer Programming ; IP) :의사결정변수가 정수값 만을 가지는 특수한 경우 목표계획법(Goal Programming ; GP) : 목적함수가 여러 개의 목표를 포함하고 있는 경우 동적계획법(Dynamic Programming ; DP) : 여러 단계에 걸쳐 변수의 값을 결정하는 모형

4 ▶ 모형화와 한계 ◁ 모형화 ▷ 예제모형 (T 화학의 경우) 공장장 : 수식을 모름 제품 나 원료 A B C 제품 가
공장장 : 수식을 모름 OR전공자 ◁ 모형화 ▷ 예제모형 (T 화학의 경우) 원료 A B C 제품 가 제품 나 200 t 210 t 50 t 40 30 각 제품을 얼마나 생산? 예상 이익은? 원료들은 남을까?

5 ▶ 모형화와 한계 ◁ 모형화 ▷ 예제모형 (T 화학 문제) 각 제품의 원료사용량과 단위당 이익
◁ 모형화 ▷ 예제모형 (T 화학 문제) 각 제품의 원료사용량과 단위당 이익  제품＼원료 A B C 단위당이익 가 4 6 40 나 5 2 3 30 사용가능량 200 50 210 총이익을 최대로 하는 생산계획수립이 목표

6 ▶ 모형화와 한계 ◁ 모형화 ▷ 의사결정변수 X1 : 제품 가 의 주간 생산량, X2 : 제품 나 의 주간 생산량
◁ 모형화 ▷ 의사결정변수 X1 : 제품 가 의 주간 생산량, X2 : 제품 나 의 주간 생산량 목적함수 Maximize(최대화) Z = 40X1 + 30X2　   각 원료의 제약조건 X1 + 5X2 ≤ 200　(원료 A의 제약)          X2 ≤ 50　(원료 B의 제약)  6X1 + 3X2 ≤ 210　(원료 C의 제약)   X1, X2 ≥ 0　　　(의사결정변수의 비음 조건)  

7 ▶ 모형화와 한계 ◁ 가정과 한계 ▷ 비례성(proportionality)
◁ 가정과 한계 ▷ 비례성(proportionality) T 화학의 경우, 생산량에 비례하여 이익은 증가하고, 원료의 사용량이 제품생산량에 정확히 비례한다는 가정 → 현실적인 예로서, 대량구매에 따른 할인정책이 적용되는 경우 생산량(판매량)에 이익이 정확히 비례하지 않음(비선형 모형)

8 ▶ 모형화와 한계 ◁ 가정과 한계 ▷ 가합성(additivity)
◁ 가정과 한계 ▷ 가합성(additivity) 회사의 총이익은 각 제품의 판매에 따른 이익을 단순히 더하여 얻어지며, 원료의 총 사용량도 각 제품생산에 소모되는 양을 단순히 더한다는 가정   → 예를 들어 제품들이 보완재 또는 대체재와 같이 서로 종속적인 관계에 있을 때는 단순히 더할 수 없고 곱의 형태나 특수한 함수 로 표시(비선형 모형)

9 ▶ 모형화와 한계 ◁ 가정과 한계 ▷ 가분성(divisibility)
◁ 가정과 한계 ▷ 가분성(divisibility) 선형계획모형의 해가 정수가 아닌 소수값도 가질 수 있다는 가정   → 예를 들어, 의사결정 변수가 고용인 수, 구입기계 대수와 같이 반드시 정수로 나와야만 실행가능한 경우는? (정수계획모형)

10 ▶ 모형화와 한계 ◁ 가정과 한계 ▷ 확실성(certainty)
◁ 가정과 한계 ▷ 확실성(certainty) 모형의 모든 계수가 확실한 숫자로 표시될 수 있다고 가정(제품의 단위당 이익, 원료 사용량, 원료 사용한도량 등을 모두 확실히 알고 있다고 가정)   → 실제는 불확실하거나 확률적인 경우가 많음(확률적 모형)   

11 ▶ 선형계획법의 유형 ◁ 생산량결정문제 ▷ 예제모형(전형적인 이익최대화 문제) B공장의 공정별 소요시간(단위 : 분) 제품
◁ 생산량결정문제 ▷ 예제모형(전형적인 이익최대화 문제) B공장의 공정별 소요시간(단위 : 분) 제품 공정 A B C 1 2 5 3 4 6 각 공정의 1일 가동시간은 480분, 450분, 420분 각 제품의 단위당 이익은 각각 3, 5, 4(만원)인 경우 1일 최적 생산량 결정

12 ▶ 선형계획법의 유형 ◁ 생산량결정문제 ▷ 의사결정변수
◁ 생산량결정문제 ▷ 의사결정변수 X1 : 제품 A의 1일 생산량  X2 : 제품 B의 1일 생산량  X3 : 제품 C의 1일 생산량 최종 정리된 모형 Max.　 Z = 3X1 + 5X2 + 4X3　　 　(총이익) s. t.　 2X1 +　X2 + 5X3 ≤ (공정 1의 가동시간)    　 　　  3X1 + 2X2 +   X3 ≤ 450　　 (공정 2의 가동시간)    　 　　　 　   4X2 + 6X3 ≤ 420　　 (공정 3의 가동시간)   　 　 　 X1, X2, X3 ≥ 0

13 ▶ 선형계획법의 유형 ◁ 제품배합문제 ▷ 예제 모형
◁ 제품배합문제 ▷ 예제 모형 A, B 두가지 원료를 혼합하여 일반비료와 고급비료 등 두 종류의 비료를 생산, 판매 제품의 수요 : 일반비료는 20kg짜리 푸대로 5,000푸대, 고급비료는 7,000푸대로 예측 고급비료는 질소함유량이 40∼ 50%, 일반비료는 인산함유량이 20%를 넘지 않아야 한다.

14 ▶ 선형계획법의 유형 ◁ 제품배합문제 ▷ 각 원료의 성분과 가격
◁ 제품배합문제 ▷ 각 원료의 성분과 가격 원료 질소함유랑(%) 인산함유량(%) 구입가격(원/kg) A 60 10 200 B 40 300 최소의 비용으로 예상되는 수요를 충족시킬 수 있는 원료 구입계획 결정 문제

15 ▶ 선형계획법의 유형 ◁ 제품배합문제 ▷ 의사결정변수 : 각 원료의 구입량(단위 : kg)
◁ 제품배합문제 ▷ 의사결정변수 : 각 원료의 구입량(단위 : kg) 　 X1 : 일반비료에 투입되는 원료A의 양 　  X2 : 일반비료에 투입되는 원료B의 양 　　 X3 : 고급비료에 투입되는 원료A의 양 　　 X4 : 고급비료에 투입되는 원료B의 양 목적함수 : 각 원료의 구입비용을 최소화 　　  Min. Z = 200(X1 + X3) + 300(X2 + X4) 수요를 충족시키기 위한 제약 　　  X1 + X2 ≥ 20 × 5,000 (일반비료 수요 제약) 　　  X3 + X4 ≥ 20 × 7,000 (고급비료 수요 제약)

16 ▶ 선형계획법의 유형 ◁ 제품배합문제 ▷ 최종 정리된 선형계획모형
◁ 제품배합문제 ▷ 최종 정리된 선형계획모형 Min. Z = 200X X X X4　　　 (총비용) s. t.　　 X X2　　　　　     ≥ 100,000 (일반비료 수요) 　 　　　　 　 X3　+　X4  　 ≥ 140,000 (고급비료 수요) 　　　　　　 0.2X3　- 0.3X4 ≥ 0 (고급비료 최소질소함유량) 　　　 　　 　 0.1X3　- 0.4X4 ≤ 0 (고급비료 최대질소함유량) 　 　 -0.1X X2　　　 　   ≤ 0 (일반비료 최대질산함유량) 　　　 X1, X2, X3, X ≥ 0

17 ▶ 선형계획법의 유형 ◁ 수송문제 ▷ 예제 모형 : C시멘트회사 각 공장별 하루 생산능력(톤) : 600, 500, 900
◁ 수송문제 ▷ 예제 모형 : C시멘트회사 각 공장별 하루 생산능력(톤) : 600, 500, 900 각 대리점의 일일 수요(톤) : 500, 400, 700, 200 수송경로별 1톤당 수송비용 (단위 : 만원) 대리점 공장 A B C D 1 4 5 9 3 2 6 7 최소의 비용으로 각 공장에서 대리점까지의 수송계획을 수립

18 ▶ 선형계획법의 유형 ◁ 수송문제 ▷ 의사결정변수 : 각 수송경로에 배정하게 될 수송량
◁ 수송문제 ▷ 의사결정변수 : 각 수송경로에 배정하게 될 수송량 Xij : i 공장에서 j 대리점으로의 수송량 목적함수: 총 수송비용(단위당 수송비와 수송량과의 곱) 최소화 Min. Z = 4X11 + 5X12 + … + 9X34 공급능력의 제약 각 공장에서 수송되는 양은 그 공장의 생산능력을 벗어날 수 없으므로, 1번 공장의 경우 X11 + X12 + X13 + X14 ≤ 600 으로 표현, 나머지 공장에서도 마찬가지임 수요량 충족 제약 각 대리점의 수요량을 만족시키기 위한 제약조건은 A대리점의 경우, X11 + X21 + X31 = 500으로 표현 나머지 세 대리점에서도 마찬가지임

19 ▶ 선형계획법의 유형 ◁ 수송문제 ▷ 최종 정리된 수송계획문제의 모형
◁ 수송문제 ▷ 최종 정리된 수송계획문제의 모형 Min. Z = 4X11 + 5X12 + … + 9X34　  (총 수송비용) s. t.　 X11 + X12 + X13 + X14　 ≤ 600(1번 공장의 공급량 제약) 　　  X21 + X22 + X23 + X24　 ≤ 500(2번 공장의 공급량 제약) 　　  X31 + X32 + X33 + X34　 ≤ 900(3번 공장의 공급량 제약) 　　  X11 + X21 + X31　　　　 = 500(A대리점의 수요량 제약) 　　  X12 + X22 + X32　　　　 = 400(B대리점의 수요량 제약) 　　  X13 + X23 + X33　　　　 = 700(C대리점의 수요량 제약) 　　  X14 + X24 + X34　　　　 = 200(D대리점의 수요량 제약) 　　　 모든 Xij ≥ 0

20 ▶ 선형계획법의 유형 ◁ 식단문제 ▷ 예제 모형(전형적인 최소화문제)
◁ 식단문제 ▷ 예제 모형(전형적인 최소화문제) 사람들에게 필요한 영양분을 충족시키면서 최소의 비용으로 음식물을 구입하는 문제 하루에 필요한 단백질, 탄수화물, 지방의 요구량과 이를 공급하는 5가지 음식물에 대한 자료가 다음 표와 같을 경우,

21 ▶ 선형계획법의 유형 ◁ 식단문제 ▷ 음식물의 영양분 함유량과 비용 음식물종류 단위당 영양분 함유량(g) 단위당 비용 단백질
◁ 식단문제 ▷ 음식물의 영양분 함유량과 비용 음식물종류 단위당 영양분 함유량(g) 단위당 비용 단백질 탄수화물 지방 1 9 20 3 200 2 8 4 250 120 16 300 5 26 500 1일최소요구량 400 최적 음식물 구입 계획을 수립하는 문제 

22 ▶ 선형계획법의 유형 ◁ 식단문제 ▷ 의사결정변수 : Xi를 각 음식물의 구입량으로 정의
◁ 식단문제 ▷ 의사결정변수 : Xi를 각 음식물의 구입량으로 정의 목적함수 : 음식물 구입에 따른 총 비용의 최소화 제약조건 : 각 영양분의 최소요구량 만족 최종 정리된 모형 Min. Z = 200X X X X X5 (총구입비용) s. t. 9X1 + 8X2 + 4X3 + 16X4 + 26X5 ≥ 300(단백질 요구량) 　20X1 + 3X2 +　X3 +  8X4 +　9X5 ≥ 400(탄수화물 요구량) 　 3X1 + 4X2　　　+　4X4 +  9X5　≥ 200(지방 요구량) 　　　　 　 X1, X2, X3, X4, X5 ≥ 0 　

23 ▶ 선형계획법의 유형 ◁ 조달계획문제 ▷ 예제 모형 5일 동안의 특별행사 기간에 필요한 냅킨의 조달계획을 수립
◁ 조달계획문제 ▷ 예제 모형 5일 동안의 특별행사 기간에 필요한 냅킨의 조달계획을 수립 조달방법 : 새 것을 구입 또는 사용한 것을 세탁하여 다시 사용 세탁의 경우, 하루만에 찾아올 수 있는 긴급세탁과 이틀 후에 찾는 보통세탁으로 구분 냅킨의 단위당 구입가격은 10원이며, 세탁가격은 긴급세탁 5원, 보통세탁 3원 행사기간 동안의 냅킨 수요량이 각각 200, 300, 280, 210, 190으로 예측 냅킨의 최적 조달계획을 수립하는 것이 문제

24 ▶ 선형계획법의 유형 ◁ 조달계획문제 ▷ 의사결정변수 Xi = i번째 날에 새로 구입하여 사용하는 냅킨 수
◁ 조달계획문제 ▷ 의사결정변수 Xi = i번째 날에 새로 구입하여 사용하는 냅킨 수 Yi = i번째 날에 사용하고 긴급세탁을 맡긴 냅킨 수   Zi = i번째 날에 사용하고 보통세탁을 맡긴 냅킨 수 Wi = i번째 날에 사용하였으나 세탁을 맡기지 않은 냅킨 수 <5일 동안 사용하게 될 냅킨 수> 날 냅킨종류 1 2 3 4 5 구 입 X1 X2 X3 X4 X5 긴급세탁 Y1 Y2 Y3 보통세탁 Z1 Z2 수 요 량 200 300 280 210 190

25 ▶ 선형계획법의 유형 ◁ 조달계획문제 ▷ 변수의 성격상 Y4 = Y5 = Z3 = Z4 = Z5 = 0
◁ 조달계획문제 ▷ 변수의 성격상 Y4 = Y5 = Z3 = Z4 = Z5 = 0 매일 냅킨의 수요를 충족시키기 위한 조건 X1 = 200, X2 = 300, X3 + Y1 = 280, X4 + Y2 + Z1 = 210, X5 + Y3 + Z2 = 190 매일 사용하고 남은 냅킨의 수 = (당일 사용한 냅킨) + (전날 남은 냅킨) – (당일 세탁을 맡긴 냅킨) W1 = (Y1+Z1), W2 = W1- (Y2+Z2), W3 = W2 - (Y3+Z3) = W2 - Y3 * 4일째와 5일째는 세탁을 맡기는 냅킨이 없음

26 ▶ 선형계획법의 유형 ◁ 조달계획문제 ▷ 최종 정리된 수식화 결과
◁ 조달계획문제 ▷ 최종 정리된 수식화 결과 Min. Z = 10(X3 + X4 + X5) + 5(Y1 + Y2 + Y3) + 3(Z1 + Z2) (총비용) s. t.　 X3 + Y1　　　　　  　 = 280 (3일째의 냅킨 수요) 　 X4 + Y2 + Z1　　　　   = 210 (4일째의 냅킨 수요) 　 　 　 X5 + Y3 + Z2　　　　 = 190 (5일째의 냅킨 수요) 　 　 　 Y1 + Z1 + W1　　 　    = 200 (1일째 사용한 냅킨수) 　  　　 Y2 + Z2 - W1 + W 　    = 300 (2일째 사용한 냅킨수) 　  　　 Y3 - W2 + W3　　　   = 280 (3일째 사용한 냅킨수) 　　　　　　　 모든 변수는 비음수  

27 ▶ 도해법과 해의 분석 도해법(graphical solution method) : 제약조건식을 만족시키는 영역을 그래프 상에 나타내어 해를 찾아내는 방법 : 변수가 3개 이상이면 표현하기가 곤란하며, 4개 이상이면 적용 불가능

28 ▶ 도해법과 해의 분석 예제 모형 : T화학 문제 * 만약 T화학이 거래처인 S화학으로부터 각 제품을 이미 10톤씩 주문받아 놓은 상태라고 할 때, T화학의 최적생산계획 결정 새로운 선형계획모형 목적함수 : Max. Z = 40X1 + 30X2 (예상 총이익) 제약조건(subject to) (1) 4X1 + 5X2　 ≤ 200　(원료 A의 사용한도) (2)　　 　 2X2　 ≤ 50　 (원료 B의 사용한도) (3) 6X1 + 3X2　 ≤ 210　(원료 C의 사용한도) (4)　X1  　　 　  ≥ 10　 (제품 가의 주문량) (5)　　　   X2 　 ≥ 10　 (제품 나의 주문량) 　　　　　 X1, X2 ≥ 0

29 ▶ 도해법과 해의 분석 위의 제약조건을 만족시키는 영역을 X1, X2의 좌표상에 그린다 X2 ③ 35 40 ① 50
Max. Z = 40X1 + 30X2 ① 4X1 + 5X2 ≤ 200 ②　 　 2X2 ≤ 50 ③ 6X1 + 3X2 ≤ 210 ④ X1  　 　 ≥ 10 ⑤　 　   X2 ≥ 10 　 X1, X2 ≥ 0 ③ 35 40 ① 50 기울기:-2 기울기: (등이익선) ④ 10 B A E D C(25, 20) 25 ② 실행가능영역 10 ⑤ X1

30 ▶ 도해법과 해의 분석 빗금친 부분은 모든 제약조건을 만족시키는 영역 : 실행가능영역(feasible region)
이 영역에 있는 모든 좌표들 : 실행가능해 (feasible solution) 실행가능해 중에서 목적함수값을 가장 크게 해주는 점을 최적해(optimal solution) 최적해는 실행가능영역의 꼭지점(extreme point), A, B, C, D, E 중에 존재

31 ▶ 도해법과 해의 분석 ◁ 최적해를 찾는 방법 ▷ 목적함수식을 종속변수인 X2에 관해 정리하면,
◁ 최적해를 찾는 방법 ▷ 목적함수식을 종속변수인 X2에 관해 정리하면, 이 직선상에 있는 모든 좌표는 똑같은 Z값(이익)을 갖게 되므로 이를 등이익선(等利益線 ; iso-profit line)이라고 함 총이익 Z를 최대로 하기 위해서는 등이익선이 실행가능영역과 만나면서 절편값을 가장 크게 해야 한다. 앞의 그림에서 이 문제의 경우는 점 C(25, 20)가 최적점임 따라서 최적해는 X1 = 25, X2 = 20이고, 이 때의 Z = 1,600 즉, T화학회사의 주간 최적생산계획은, 가 제품을 25톤, 나 제품을 20톤 생산하는 것이고 예상되는 총이익은 1,600만원이다.

32 ▶ 도해법과 해의 분석 ◁ 최적해에 대한 분석 ▷ 1, 2, 3번째 제약식의 좌변 : 원료 A, B, C의 사용량, 우변: 사용한도 따라서, (우변 – 좌변) = 사용하고 남는 여분의 양을 의미 이를 여유변수(slack variable)라 하고 각각 S1, S2, S3라 표시 최적인 상태에서 이들의 값은, 　　　S1 = (4×25 + 5×20) = 0 　　 S2 = ×20 = 10 　 　 S3 = (6×25 + 3×20) = 0 즉, 원료 B는 10만큼의 여유가 있고, A와 C는 부족한 상태 4X1 + 5X2　 ≤ 200 (원료 A) → 4X1 + 5X2　+ S1 = 200 4, 5번째 제약조건의 좌변: 각 제품의 실제 생산량, 우변: 최소생산량 따라서, (좌변-우변) = 초과분의 생산량을 의미 이를 잉여변수(surplus variable)라 하고 S4, S5라 표시 이 경우 S4 = 15, S5 = 10    X1 ≥ 10 (제품 가) → X1 - S4 = 10

33 ▶ 특수한 해 ◁ 다수최적해 ▷ 앞의 예에서 만약 제품 나의 단위당 판매이익이 50(만원)으로 높아진 경우 ③ X2 ① 40
◁ 다수최적해 ▷ 앞의 예에서 만약 제품 나의 단위당 판매이익이 50(만원)으로 높아진 경우 ③ X2 ① 40 ④ B(18.75, 25) A C(25, 20) ② 25 E D ⑤ 10 X1 10 35 50 기울기:-2 기울기:

34 ▶ 특수한 해 ◁ 다수최적해 ▷ 목적함수식이 Z= 40X1 + 50X2가 되어 등이익선의 기울기가 -4/5가 되므로 그림과 같이 등이익선이 1번 제약조건식의 경계선과 일치 따라서 점B와 C사이에 있는 모든 점이 최적해가 되는데, 이를 다수최적해(multiple optimal solutions)라 함 　 점 B(18.75, 25) 와 C(25,20) 사이의 점은 0≤α≤1인 α에 대하여, (X1, X2) = α(25, 20) + (1-α)(18.75, 25) = ( α, 25-5α)로 표시 이 경우, 제품 가를 18.75톤, 나를 25톤 생산해도 각각 25톤, 20톤씩 생산하는 것과 마찬가지로 총이익이 2,000이 된다. 　

35 ▶ 특수한 해 ◁ 무한대해 ▷ 무한대해(unbounded solution) : 목적함수의 값을 무한히 증가(최대화 문제) 또는 감소(최소화 문제)시키는 해   예제 모형 　 Max. Z = 2X1 + X2 s. t.  　　 X1 - 2X2 ≤ 10 　　　　 -2X1 + 5X2 ≥ 25 　　　　　 X1, X2 ≥ 0 5 X2 2X1-X2=10 -2X1+5X2=25 X2=-2X1+Z X1 실행가능영역이 제한되지 않고 한쪽 방항으로 열려 있음 제약조건식이 빠졌거나 제약조 건의 설정이 잘못된 경우

36 실행가능영역이 무제한이나 유한한 최적해를 갖는 경우
▶ 특수한 해 실행가능영역이 무제한이나 유한한 최적해를 갖는 경우 실행가능영역과 등이익선 X2 5 X2=3X1-Z X1=5 2X1-X2=4 -4 X1 2 A(5, 6) 예제 모형 　 Max. Z = 3X1 - X2 　 s. t.　  2X1 - X2 ≤    X1　 　 ≤ 5 　 X1, X2 ≥ 0 실행가능영역은 위쪽으로 열려 있으나, 점 A(5, 6)에서 유한한 목적함수 값의 최적해를 가짐

37 ▶ 특수한 해 ◁ 실행불가능한 경우 ▷ 앞의 T화학 문제에서 가 제품에 대해 주문받은 양이 40인 경우
◁ 실행불가능한 경우 ▷ 앞의 T화학 문제에서 가 제품에 대해 주문받은 양이 40인 경우 4번째 제약조건식 : X1 ≥ 40 → 이를 그래프에 표시하면, 10 25 40 X2 ⑤ 35 50 ② ① ③ ④ X1 모든 제약식을 공통 적으로 만족시키는 영역이 없음 제약조건의 타당성 또는 우선순위 검토 가 필요

38 secom.hanbat.ac.kr 경영과학(Ⅰ) 제2장 선형계획법 : 기본개념과 모형화 수고하셨습니다…