선형 프로그래밍 운송 최적화

Question

내가

간단한 경우 GLPK 또는 R.

에, (운송 비용을 최소화) 최적화를 사용하는 일반적인 교통 문제를 해결하기 위해 노력하고 있어요 : 2 개 지역에 위치한 4 개 생산자 (A 및 B)는 다른 곳의 두 수출상에게 제품을 전달하고 있습니다. 각 경로 생산자 - 수출자에 대한 비용 매트릭스가 있습니다 (아래 참조). 해결책은 간단 할 것입니다. 교통 문제의 전형적인 예입니다.

예 :

production (id, province, tons) 
      1 A  300 
      2 A  800 
      3 B  800 
      4 B  1200 

    export (id, sourcing_province, tons) 
      5 A  400 
      5 B  600 
      6  2000 

    routes (id_orig, id_dest, cost) 
       1 5 5.1 
       1 6 3.2 
       2 5 6.7 
       2 6 7.2 
       3 5 2.8 
       3 6 4.1 
       4 5 6.9 
       4 6 5.3 

그러나 문제가 더 복잡하고 별도의 제한이 : 나는 수출 (5) 실제로 각 지방에서 특정 고정 금액을 소싱 것을 알고있다. 특히 위의 예에서 수출업자 (5)는 A 주에서 400 Tn, B 주에서 600 Tn을 공급해야합니다. 수출업자 (6)는 제한이 없으며, 어느 주에서든 물품을 공급할 수 있습니다. 이러한 제한을 표현할 방법을 찾지 못했습니다.

도와 주실 수 있습니까?

Answer 1

가장자리의 문제를 고려해 볼 수 있습니다. 1, 2, 3, 4가 생산자이고 5,6이 수출이라면, e15는 생산자 1에서 수출 5까지의 흐름, e25는 생산자 2에서 수출 5까지의 흐름이라고 가정 해 봅시다. 이 표기법

가 문제가된다 :

/* Objective function */ 
min: 5.1 e15 + 3.2 e16 + 6.7 e25 + 7.2 e26 + 2.8 e35 + 4.1 e36 + 6.9 e45 + 5.3 e46; 

/* production limits */ 
e15 + e16 <= 300; 
e25 + e26 <= 800; 
e35 + e36 <= 800; 
e45 + e46 <= 1200; 

/* demand */ 
e15 + e25 + e35 + e45 >= 1000; 
e16 + e26 + e36 + e46 >= 2000; 

/* exporter 5 restrictions */ 
e15 + e25 >= 400; 
e35 + e45 >= 600; 

마지막 두 부등식은 일정량의 제약이다.

이 문제는 LpSolve을 사용할 수 있습니다. 이 경우 R 패키지 lpsolveAPI도 있습니다. 위의 문제 공식은 이미 LP 형식으로되어 있습니다.