linear program

        linear program (線型計劃法) 은 주어진 조건들을 만족하는
        
        범위에서 목적 함수를 최적화하는 기법으로 OR 분야에서 쓰이는
        
        가장 일반적인 기법 입니다.
        
        이 기법은 역시 미시 경제학, 네트워크 경로 최적화와 같은 많은
        
        분야에서 이용하고 있으며, 네트워크 흐름과 같은 문제들에 대해서
        
        여러 특화된 알고리즘들이 있습니다.
    
        가변 요소들의 1차 equation 이 성립할 경우, 변화의 한계를 
        
        정할 때에 쓰는 기법으로, 생산계획. 수송계획 따위의 문제를 
        
        풀때에 쓰이고 있습니다.
        
        
        그러면 linear program 의 풀이 예를 들어 보겠습니다.
        
        X1 과 X2 두 종류의 제품이 있어서 이것들을 만들어서 
        
        판매한다 합시다.
        
        
        X1 을 만들기 위해서는 재료1 100 과 재료2 10 이 필요하며 
        
        x2 를 만들기 위해서는 재료1 50 이 필요하다 합니다.
        
        그러면 재료비를 빼고 X1 을 판매했을 때 100 원 
        
        X2 를 판매했을 때 40 원이 남는다 합니다.
        
        
        그러면, 재료1 3000 과 재료2 100을 재료로 갖고 있을 때, 
        
        재료1 과 재료2 만으로 제품을 만들어 판매한다고 했을 때
        
        어떤 제품들을 어떻게 만들어야 할까요?
        
        이러한 문제를 푸는 예는 이렇습니다.

    
            최대화(x) 100 x1 + 40 x2
            
            조건 :  100 x1 + 50 x2 ≤ 3000,
            
                        10 x1 ≤ 100,
                        
                        x1, x2 ≥ 0.
                        
                        x1 는 제품1, x2 는 제품2 의 개수
                        
                        
            풀이) 제품1 = 10 개, 제품2 = 40개를 만든다.
            
                  이때 이익은 2,600 원.