Multiple Objective Linear Programming(MOLP) 의 정의와 활용

정의

 

다중 목표 선형 계획법

(Multiple Objective Linear Programming, MOLP)은

두 개 이상의 목표 함수를 가지는

선형 계획법 (LP) 문제의 한 형태입니다.

 

MOLP의 주요 목적은

완벽하게 모든 목표를 동시에 최적화하는

단일 해를 찾는 것이 아니라,

서로 상충하는 여러 목표들 사이에서

의사 결정자에게 가장 적절한

절충점(trade-off)을 제공하는

일련의 효율적인 해(efficient solutions)를

찾는 것입니다.

 

 

1) 다수 목표: 하나의 목적 함수만을 최적화하는

일반적인 LP 문제와 달리,

여러 개의 상충되는

목표(objective)를 동시에 최적화하려고 합니다.

 

2) 제약 조건: 목표 함수는 모두 선형이며,

제약 조건 역시 선형입니다.

 

3) GP와의 관계: MOLP 문제는

각 목표 또는 목적에 대한

목표값(target values)을 설정해야 하는

목표 계획법(Goal Programming, GP)의

특별한 유형으로 간주될 수 있습니다.

GP가 마지막에 목적식이 나오듯이

MOLP도 마지막에 목적식이 나옵니다.

(이전 목적식이 결합되어)

 

4)해결 방법: MiniMax 목표와 같은 기법을 사용하여,

여러 목표 간의 균형을 맞추는 해를 찾게 됩니다.

 

 

사용 방법 (계산법)

 

예제를 통해 살펴보겠습니다.

(가) 광산 회사는 (A)와 (B)라는

2개의 광산을 갖고 있습니다.

 

(가) 광산 회사는 아래의 조건을 비교하여

(A) 광산과 (B) 광산 각각에서 어느 정도

씩 근무하는 게 효율적일지 판단하려 합니다.

	A 광산	B 광산
고품질 광석 월간 채굴량 (월간)	12	4
중품질 광석 월간 채굴량 (월간)	4	4
저품질 광석 월간 채굴량 (월간)	10	20
유지비(월간)	40,000	32,000
유해물질 배출(월간)	800	1,250
만인사고율	0.20	0.4

 

(가) 광산회사는 최소 48톤 이상의 고품질 광석

28톤 이상의 중품질 광석

100톤 이상의 저품질 광석을 필요로 합니다.

 

이를 목적식과 제약식으로 나누면 아래와 같습니다.

(A광산을 X1, B광산을 X2로 표시)

 

기존 목적식(1) 생신비용 최소(min) : 40 X1 + 32X2

기존 목적식(2) 유해물질 최소(min) : 800x1+1250x2

기존 목적식(3) 사고확률 최소(min) : 0.2x1+0.45x2

 

제약식(1) 12x1 + 4x2 >=48

제약식(2) 4x + 4x2 >= 28

제약식(3) 10x1 + 20x2 >= 100

제약식(4) x1, x2 >= 0

 

이제 앞 시간 GP에서 배웠던 개념을 활용하여

단위가 다 다른 목적식을 비율 단위로 맞춘 후

중요성에 따라 차등을 줄 가중치 W를 곱해주면 됩니다.

 

새로운 목적식은 아래와 같습니다.

MIN: w₁ ( ((40X₁ + 32X₂) - 244)  /  244 ) 
   + w₂ ( ((800X₁ + 1250X₂) - 6950)  /  6950 ) 
   + w₃ ( ((0.20X₁ + 0.45X₂) - 2)  /  2 )

 

 

-덧-

 

목적식이 3개 이기 때문에

3세개의 선(목적)에 다 포함되는 (이하) 범위에서만

선택이 가능합니다. 

 

 

실무 적용

 

엑셀로 한번 정리해 보겠습니다.

 

결론부터 말하면

가중치를 다 1로 놓았을 때

(비용, 유해물질, 사고율)

위의 값이 최적해가 됩니다.

 

앞선 포스팅에서

설명한 부분은 빼고 설명하겠습니다.

 

고,중,저 품질은 처음에 알려준 조건식에서

추가 제약식은 비율로 만들면서 생긴 식 즉,

MIN: w₁ ( ((40X₁ + 32X₂) - 244)  /  244 ) 
   + w₂ ( ((800X₁ + 1250X₂) - 6950)  /  6950 ) 
   + w₃ ( ((0.20X₁ + 0.45X₂) - 2)  /  2 )

에서 추론 됩니다.

 

 

 

더 자세히는 위 스샷을 참고하시기 바랍니다.

 

이상으로

Multiple Objective Linear Programming(MOLP) 의  정의와 활용

포스팅을 마칩니다.