퍼지 선형 계획법 , 선형계획법 , 단체법

선형 계획법

• 최적화 문제
  • 제한된 조건하에서 가장 효과적인 해를 구하는 것
  • 주로 제약된 조건식을 만족하는 범위에서, 목적함수가 max or min이 되게 해를 구한다.
• 최적화 문제에서 제약 조건식과 목적함수가 일차식이여야 함. 
  일차식이 아니면 비선형 계획법이다.

 

• ex)
  • A,B공장 존재
  • 각각 공장은 물건을 만드는데 1kg,2kg의 원료가 필요하며, 시간은 3hours , 2 hours이다.
    각각 이익은 4만원 , 6만원이다...
    단, 하루에 사용가능한 원료는 30kg이다.
    단, 생산라인 가동 시간은 58시간을 못 넘음.
  • let, A,B의 생산량을 x,y 
    f=이익=4x+6y
    x+2y ≤ 30
    3x+2y ≤ 58
    0 ≤ x , 0 ≤ y 
  • 아래에서 최대 이익인 (14,8)지점을 정점(extreme point)이라고 한다.

다음과 같을때 A(14,8)이다. f=4x+2y이니 104이다. 즉, a제품을 14개 b제품을 8개 팔아야 최대 이익이다.

 

• ex)
  • 건강을 위해서 최소 하루에 칼슘,탄수화물,단백질을 각각 15,42,45g씩 먹어야한다. 다음에 대해서 선형계획법을 작성하여라

	칼슘 (g)	탄수화물 (g)	단백질(g)	가격(원)
식품A	2	12	5	500
식품B	3	6	10	600

==> (150 , 400)이 정점이다. 즉, 최소비용은 3150원

 

 

 

단체법 simplex method

• 핵심은 선형계획법 문제에 적절한 새로운 변수를 추가해서, 부등식을 등식으로 고쳐서, 기저가능해에서 최적해를 찾는것이다.
•  

왼쪽의 부등식을 다음과 같이 등식으로 표현한다.

그리고 위에 식을 행렬로 표현한다.

정리한다.

식으로 나타내면 다음과 같다

x와 y에 관해서 다음과 같이 나타내고, 이를 목적함수에 넣으면 최적함수를 다르게 고칠수있다.

==> 위에서 z=0 , w=0일때 최대값 104를 가진다. 그렇다면 x=14,y=8,z=0,w=0이 최적해이다.