선형계획법 - 최소화문제

선형계획법(LP) - 최소화문제

아침 식사에는 영양소 A가 288mg, 영양소 B가 200mg 필요하고, 달걀 하나에는 영양소 A가 4mg, 영양소 B가 4mg, 베이컨 한 쪽에는 영양소 A가 5mg, 영양소 B가 3mg 포함되어 있다고 함.

그런데 달걀 1개의 가격은 40원, 베이컨 1개의 가격은 60원이라고 할 때 목적으로 하는 영양조건을 만족시키면서 비용을 최소화하는

① 이상을 요약한 영양분석표 작성

② 선형계획 모형구성

③ 도식해법으로 이 문제를 풀어라

(풀이)

① 영양분석표

(도표 5) 영양분석표

② 선형계획형 ; 제공될 달걀 수량은 X, 제공될 베이컨 수량을 Y로 할 때

최소화 Z = 40 * 60Y

제약조건 4X + 5Y = 28

4X + 3Y = 20

X,Y = 0

③ 도식해법조건식 ①, ②를 직선식으로 변형하면

식 ③, ④를 그래프로 그리면 (도표 6)과 같고, 식 ①, ②에서 부등호 방향이 ≥ 이므로 빗금부분이 가해영역임.

(도표 6) 최소화문제의 도식해법

그리고 목적함수를 Y에 관해 표시함으로써 등비용선을 구하면

로부터

식 ⑤에서 등비용선의 기울기는 -2/3이고, Y축에 대한 절편은 Z/60이다.

* 등비용선이란 X와 Y의 값이 어떻게 결합하든지 간에 동일비용을 나타내는 점 들로 이루어진 선으로서,

예컨데 등비용선은 (X=3, Y=0)일 때의 비용이 120원이고, (X=0, Y=2)일 때의 비용이 120원이므로 이 두점을 연결하는상의 점은 X와 Y의 값이 어떻게 결합하더라도(예컨데 A, B점) 모두 120원의 비용을 발생시킴.

* 최적해는 총비용이 최소화되는 점에서 실현되는데, 총비용은 -4/3의 기울기를 가지고 등비용선이 원점 0에서 가까워 올수록 작아지게 됨.

* 제약조건을 고려한 최적해는 가해영역중의 원점에서 가장 가까은 꼭지점과 등 비용선이 접하는 점(X=7, Y=0)에서 실현됨.

∴ 최적해는 X=7단위, Y=0단위

이 때의 총비용은 Z=40(7)+60(0)=280원

출처 : 최신공장관리기술사(하권) OR 출판사 : (주)ATPM컨설팅

저자 : 공학박사/기술사/지도사 권오운 지음

공장혁신/공장기술사 자료실 메인 페이지로 홈페이지 메인으로