선형 프로그래밍 - 이중 단순 변수 의미?

Question

선형 프로그램을 해결하기위한 단방향 방법을 배웠고 이중 문제가 무엇인지를 이해하려고합니다.

두 가지 문제를 해결하는 방법을 잘 알고 있습니다. 도움이 필요하지 않습니다. 내가 (Wikipedia에 대해 읽은 후에도) 의 y 변수의 실제 의미는입니다.

나는 원초적 문제에 변수 의미와 모두 함께 예를 들어 줄, 그리고 제가 이중에서 생각하고, 이중의 의미를 설명하기 위해 친절하게도 사람을 물어 보곤합니다 :

의 근원을 : 원초적 문제에

max z = 3*x1 + 5*x2 

subject to: 
      x1   <= 4 
       2*x2 <= 12 
     3*x1 + 2*x2 <= 18 

     x1, x2 >= 0 

, X1 및 X2 제품 가 생성 될 수있는 및 B의 양이다. 및 은 각각 판매 단가입니다. 제품은 3 가지 기계, M1-M3에서 생산됩니다. 첫 번째 제품을 생산하려면 M1에서 근무하고 M3에서 3 시간의 작업 시간이 필요합니다. 두 번째 제품을 생산하려면 M2 및 M3 모두에서 2 시간의 작업이 필요합니다. 기계 M1, M2, M3은 각각 4, 12 및 시간 동안 작동 할 수 있습니다. 마지막으로, 나는 어떤 제품의 음수를 생산할 수 없다.

지금, 듀얼 문제 설정 : 이제

min z = 4*y1 + 12*y2 + 18*y3 

subject to: 
      y1   + 3*y3 >= 3 
        y2 + 2*y3 >= 5 

      y1, y2, y3 >= 0 

를, 내가 알아낼 수 있다고 생각 유일한 것은 제약이 의미하는 것입니다 : - M1 3 시간의 작업 시간 동안 M3에, 나는 적어도 3 개 돈 단위 을 지불하고 살만한을하셔야합니다 - M2 및 에 2시간에 작업을 2 시간 동안 M3을, 나는 적어도 5 개 돈 단위

을 지불하고 살만한을하셔야합니다

그러나 나는 단지 y1과 y2 변수의 의미를 감안할 수 없습니다. 마지막으로 최소화를 수행하면 결과는 z의 결과가 기본 값과 동일하지만 (결과의 하한을 높이는 데있어서 기본이긴하지만 이중 값이 상한을 줄이는 것이지만) 이중 함수의 목적 함수는 무엇입니까? 문제는?

Answer 1

듀얼의 목표 기능은 3 대의 기계 (자원)의 비용/시간을 최소화하는 것입니다.생산의 이익을 극대화 다룬 태초의 이후

Minimize 4*(cost/hour of Machine1) + 12*(cost/hour of M2) + 18*(cost/hr of M3) 

에서, 듀얼가 생산을 최소화으로 간주 할 수 있습니다 :로

그래서 이중의 목적 함수 (4*y1 + 12*y2+ 18*y3)를 읽을 수 있습니다 회사 비용.

은 대부분 그들이 지불해야 [$/시간]가 무엇인지, 그들이 그것을 임대하려는 경우 (때때로 회사 기계 M1, M2와 M3을. "임대"를 생각하는 데 도움이됩니다) 각 기계마다 여전히 x1 및 x2을 수익성있게 생산할 수 있습니까?

이중 변수 y1, y2, and y3의 의미는 시간당 소유/임대 비용입니다.

이중 문제의 y 변수는 흔히 "그림자 가격" 리소스라고합니다.

당신은 이해 DUALS에 통찰력을 찾고 있기 때문에 :

1. 한 트릭은 이중의 크기를 줄이는 것입니다. (단 하나의 기계가 있다고 상상해보십시오 M1) 이제 이중화를 공식화하고 목적 함수와 제약 조건을 이해하려고 노력하십시오.
2. 의 관점에서 생각하면 도움이됩니다. 제조 회사가 기계 (자원)를 임대해야한다면 어떤 가격/시간을 지불해야합니까? 또는 다른 많은 (수익성있는) 제품이있는 경우, 어떤 비용/시간으로 기계를 X1 및 X2으로 할당하는 대신 다른 제품을 생산할 수 있습니다.
3. 모든 이중성을 쉽게 "이해"할 수있는 것은 아닙니다. 그러나 primal에서 해당 변수를 보면 많은 이중 제약 조건을 이해할 수 있습니다. 마찬가지로, 해당 primal 제약 조건을 연구함으로써 이중 변수에 대한 통찰력을 얻을 수 있습니다.