제 8 장 목표계획법 서론 목표계획법의 모형화 도해법 및 해의 분석 심플렉스법의 응용 www.or-ms.com

▶ 서 론 목표계획법(GP ; goal programming) : 이익 최대화나 비용 최소화라는 단 하나의 목표 이외에 서로 상충되는 여러개의 목표가 있는 경우의 수리계획법 여러 개의 목표 중 우선순위가 높은 목표부터 만족시켜 나간다. (상위의 목표가 충족이 안된 상황에서는 하위의 목표도 충족될 수 없다고 가정) 편차변수 도입 : 목표에 미달/초과를 표시(직접적인 의사결정변수) 목적함수 : 편차합의 최소화 이익 최대화의 경우, 선형계획법과의 개념 비교 (a) 선형계획법 (b) 목표계획법

▶ 목표계획법의 모형화 목표계획모형의 구성요소 ① 편차변수 ② 시스템 제약조건 ③ 목표 제약조건 ④ 목적함수 편차변수 목표계획모형의 구성요소   ① 편차변수 ② 시스템 제약조건 ③ 목표 제약조건 ④ 목적함수 편차변수 편차 : 미리 정해진 목표와의 차이를 나타내는 값 목표 값보다 큰 편차는 d+, 목표 값보다 작은 편차는 d-로 표시 두 편차변수중 하나는 반드시 0이 된다. : 예로서 어떤 제품의 생산량 목표가 100단위인데, 실제 생산이 90단위라면 d- = 10, d+ = 0 시스템 제약조건 선형계획모형에서의 제약조건과 같은 의미의 환경적, 시간적, 물질적 제약 등 외부적으로 주어진 제약 이 제약조건은 반드시 만족되어야 하는 절대적인 제약이다.

▶ 목표계획법의 모형화 d1- d1+ 목표제약조건 목표들의 희망수준을 나타내기 위한 식 예로서, 어느 회사에서 제품 A의 생산량(X1)을 최소 100단위 이상 생산하는 경우 - 선형계획법의 관점 : X1 ≥ 100  (절대적인 제약) - 목표계획법의 관점 : X1 + d1- - d1+ = 100 (목표 달성여부를 표시) d1- d1+ 미달 X1 100 초과 (목표생산량)

▶ 목표계획법의 모형화 목적함수 목표들로부터의 편차를 최소화 ► 목표값보다 커야 좋은 경우 → 미달 편차변수(di-)를 최소화 목표들의 우선순위를 표시하는 편차변수의 계수 결정 ► 목표들의 우선순위가 고정된 경우 (높은 우선순위의 목표부터 차례로 만족 되어야 하는 경우)      → 편차변수의 계수를 p1, p2, p3 … 등으로 부호화     여기서 p1 ≫ p2 ≫ p3 … (단순히 숫자적으로는 비교불가능한 차이) ► 목표들의 우선순위가 순차적으로 정해져 있지 않은 경우    → 각 목표에 대한 가중치를 부여하여 편차들의 가중합을 최소화 : 선형계획법의 목적함수와 근본적으로 같기 때문에 일반 심플렉스 법으로 최적해를 구함

▶ 목표계획법의 모형화 예제 모형 : 음향기기제조 전문회사인 H 사의 문제 A형(220V전용), B형(110V/220V 겸용) 음향기기를 생산ㆍ판매 단위당 생산시간 : A형 60분, B형 72분, 주당 평균생산시간 : 60시간 단위당 판매이익 : A형 30(만원), B형 35(만원) 주간 목표를 다음과 같은 우선순위로 설정      1. 주당 이익을 1,500만원으로 함.       2. B형 음향기기를 최소한 35대 생산함.       3. 생산유휴시간을 최소화 함.       4. 주당 초과작업시간이 10시간을 넘지 않도록 함.       5. A형을 B형보다 적지 않게 생산함. 의사결정변수(궁극적으로 결정하고자 하는 내용)    X1 = A형 음향기기의 주당 생산대수     X2 = B형 음향기기의 주당 생산대수 편차변수(각 목표에 대한 편차)  : di-, di+(i = 1, 2, 3, 4, 5)

▶ 목표계획법의 모형화 목표제약식 1. 주당이익 목표(p1) 30X1 + 35X2 + d1- - d1+ = 1,500 (d1- 최소화가 목표) 2. B형 기기 생산량 목표(p2) X2 + d2- - d2+ = 35  (d2-를 최소화) 3. 생산유휴시간 최소화 목표(p3) 60X1 + 72X2 + d3- - d3+ = 3,600 (d3-를 최소화) 4. 초과작업시간 목표(p4) 60X1 + 72X2 + d4- - d4+ = 4,200 (d4+를 최소화) 5. A형 기기 생산량 목표(p5) X1 - X2 + d5- - d5+ = 0  (d5-를 최소화)

▶ 목표계획법의 모형화 정리된 목표계획모형 목적함수(편차합의 최소화)   Min. Z = p1d1- + p2d2- + p3d3- + p4d4+ + p5d5-   제약조건(각 목표의 제약식)  subject to      30X1 + 35X2  + d1- - d1+ = 1,500 (주당이익 목표 제약식)                      X2  + d2- - d2+ = 35     (B형기기 생산량목표 제약식)      60X1 + 72X2  + d3- - d3+ = 3,600 (생산유휴시간 최소화목표 제약식)      60X1 + 72X2  + d4- - d4+ = 4,200 (초과작업시간 목표 제약식)           X1 -    X2   + d5- - d5+ = 0        (A형기기 생산량 목표 제약식)               X1, X2, di-, di+ ≥ 0, (i = 1, 2, 3, 4, 5)

▶ 도해법 및 해의 분석 1번 목표를 달성시키는 영역 도해법의 개념 1번 목표를 달성시키는 영역  도해법의 개념 40 50 X2 X1 30X1+35X2 =1,500 Min. Z = p1d1- d1- d1+ 첫 번째 목표를 달성시키는 영역 우선순위가 높은 목표부터 목표달성영역(편차가 최소화 되는 영역)을 차례로 표시 가장 낮은 우선순위 목표까지 반복 그중 가장 만족스러운 점을 최적해로 결정

▶ 도해법 및 해의 분석 1, 2, 3번 목표를 달성시키는 영역 1, 2번 목표를 달성시키는 영역 40 50 X2 X1 1, 2번 목표를 달성시키는 영역  1, 2, 3번 목표를 달성시키는 영역  40 50 X2 X1 Min. Z = p1d1-+p2d2- d2- 35 d2+ 1번, 2번 목표를 달성시키는 영역 x2= 35 40 35 50 X2 X1 Min. Z = p1d1-+p2d2-+p3d3- d3- d3+ 1번, 2번, 3번 목표를 달성시키는 영역 60 60X1+72X2 =3,600

▶ 도해법 및 해의 분석 다섯 번째 목표 달성영역 1, 2, 3, 4번 목표를 달성시키는 영역 50 X2 X1 1, 2, 3, 4번 목표를 달성시키는 영역  다섯 번째 목표 달성영역 50 X2 X1 Min. Z = p1d1-+p2d2-+p3d3-+p4d4+ d4- d4+ 1번, 2번, 3번, 4번 목표를 달성시키는 영역 60 60X1+72X2 =4,200 70 35 40 5번 목표를 달성시키는 영역 50 X2 X1 Min.Z= p1d1-+p2d2-+p3d3-+p4d4++p5d5- d5- 1번, 2번, 3번, 4번 목표를 달성시키는 영역 60 X1-X2 =0 70 35 40 d5+ A(28, 35)

▶ 도해법 및 해의 분석 다섯 번째 목표(A형 기기의 생산량 목표)를 달성시키는 영역 : 1,2,3,4번 우선순위 목표를 달성시키는 영역과 공통된 부분이 없음 → 기존의 영역중에서 5번 목표의 미달치를 최소화하는 A(28, 35)가 최적 즉, A형 기기 28대, B형 기기 35대를 생산하는 것이 H사의 최적 생산계획 각 목표의 달성여부 ① 이익이 30×28 + 35×35 = 2,065이므로, 주당 이익목표를 565만큼 초과달성 ② B형 기기 생산량은 35이므로 목표를 정확히 달성 ③ 생산시간 28×60 + 35×72 = 4,200이므로 생산유휴시간 600 초과 달성 ④ 초과 작업시간 목표 정확히 달성 ⑤ A형 기기 28대, B형 기기 35대 생산이므로 A형 기기 생산량 목표는 7대 미달성 각 편차변수의 값 : d1- = d2- = d3- = d4+ = 0 , d5- = 7, d1+ = 565, d3- = 600  

▶ 심플렉스법의 응용 심플렉스법을 적용하는 두가지 경우 우선순위 기호에 임의의 숫자를 배정하는 방법     - 위의 예에서 목적함수 계수 p1, p2, p3, p4, p5 대신 10,000, 1,000, 100, 10, 1 등의 숫자를 대입      - 숫자의 크기에 따라 원하는 해를 얻을 수 없거나, 풀이가 불가능한 경우가 생길 수 있음 우선순위 기호를 벌점(penalty)으로 이용하는 방법       - 심플렉스법에서 Big-M법의 개념       - 구체적인 숫자 대신 p1, p2, p3 … 를 p1 ≫ p2 ≫ p3 …의 관계가 성립하는 벌점으로  취급하여 목적함수 계수로 이용

▶ 심플렉스법의 응용 매 체 광고비(백만원) 광고효과(십만명) 신 문 4 5 T V 10 예제 모형  : G 맥주회사의 광고계획 수립 문제 월간 광고예산 8천만원으로 신문, TV광고 계획 <매체별 1회당 광고비 및 광고효과 > 매 체 광고비(백만원) 광고효과(십만명) 신 문 4 5 T V 10 광고계획에 대해 제시된 목표들과 그 우선순위     ① 월간 1,000만명에 대한 광고효과를 가져오도록 할 것     ② 신문광고는 10회 이내로 하도록 할 것     ③ 총광고비는 광고예산을 초과하지 않도록 할 것 - 광고 횟수가 정수가 아니더라도, 다음달 광고계획과 연계시켜 실행

▶ 심플렉스법의 응용 목적함수(편차합의 최소화) Min. Z = p1d1- + p2d2+ + p3d3+ 의사결정변수 : X1 = 신문광고 횟수, X2 = TV광고 횟수라 하면, 목적함수(편차합의 최소화)   Min. Z = p1d1- + p2d2+ + p3d3+ 제약조건(각 목표의 제약식)  subject to           5X1 + 10X2  + d1- - d1+ = 100 (광고효과 목표)             X1            + d2- - d2+ = 10  (신문광고 횟수 목표)           4X1 + 10X2  + d3- - d3+ = 80  (예산지출 목표)                X1, X2, di-, di+ ≥ 0, (i = 1, 2, 3)

▶ 심플렉스법의 응용 초기 심플렉스표의 작성 목표계획모형은 그 자체가 심플렉스표형(d1-, d2-, d3-를 초기 기저변수) Cj P1 P2 P3 기저 변수 Cb X1 X2 d1- d1+ d2- d2+ d3- d3+ 우변상수 비율 5 1 4 10 -1 100 80 ∞ 8(탈락) Zj  Cj – Zj 5P1 - 5P1 10P1 -10P1 -P1 100P1 (진입) 초기해 : (X1, X2 ) = (0, 0), d1- = 100, d2- = 10, d3- = 80, Z= 100p1 목적함수값 100p1의 의미 → 첫 번째 목표가 100만큼 미달성

▶ 심플렉스법의 응용 새로운 해의 계산 기준요소 10을 중심으로 하여 행연산을 수행한 결과 Cj P1 P2 P3 기저 변수 기준요소 10을 중심으로 하여 행연산을 수행한 결과   Cj P1 P2 P3 기저 변수 Cb X1 X2 d1- d1+ d2- d2+ d3- d3+ 우변상수 비율 1 0.4 -1 0.1 20 10 8 Zj  Cj – Zj - P1 -P1 -P1 +P3 20P1 탈락 (진입) 개선된 해 : (X1, X2) = (0, 8), d1- = 20, d2- = 10, Z = 20p1 →TV광고를 8회 하면, 1번 목표가 20만큼 미달

▶ 심플렉스법의 응용 새로운 심플렉스표 Cj P1 P2 P3 기저 변수 Cb X1 X2 d1- d1+ d2- d2+ d3- P1 P2 P3 기저 변수 Cb X1 X2 d1- d1+ d2- d2+ d3- d3+ 우변상수 비율 1 -1 -0.4 0.4 0.1 10 4 ∞ - Zj  Cj – Zj -P1 -P1 +P2 - P1 -P1 +P3 10P1 탈락 (진입) 새로운 해 : (X1, X2) = (10, 4), (d1-, d2+, d3+) = (10, 0, 0), Z = 10p1 → 아직도 첫 번째 목표가 10만큼 미달성

▶ 심플렉스법의 응용 최적 심플렉스표 Cj P1 P2 P3 기저 변수 Cb X1 X2 d1- d1+ d2- d2+ d3- P1 P2 P3 기저 변수 Cb X1 X2 d1- d1+ d2- d2+ d3- D3+ 우변 상수 d3+ 1 0.1 -1 -0.5 0.5 10 5 Zj  Cj – Zj P1-P3 -P3 P2-P3 - P3 10P3 비기저변수의 Cj - Zj 값이 모두 양수이므로 최적조건 만족 최적해 : (X1, X2) = (10, 5), d3+ = 10이고, 나머지는 모두 0, Z = 10p3 → 1, 2번 목표는 달성(d1- = d2+ = 0), 3번 목표는 10만큼 미달성 → 즉, 신문광고 10회, TV광고 5회가 최적(광고예산목표 천만원 초과)  

제 8 장 목표계획법 수고했어요!!!