Linprog solution differs from hand solution for minimum cost flow problem

Daniel Longest

2015 7 15

0 个回答

10 次查看（30 天）

0 个投票

I'm trying to solve a minimum cost flow problem in Matlab using linprog, but the solution computed by linprog doesn't match the solution calculated by hand and I'm not sure why. I presume I'm setting up the problem wrong, but I've been at this for hours and can't figure out the issue. The problem is shown in the image at bottom. The goal is to compute all x_ij by minimizing the function SUM(c_ij*x_ij) subject to:

SUM_j(x_ji)-SUM_j(x_ij) = b_i
x_ij>=0 for all (i,j)

I set up the vectors f, Aeq, beq, and lb vectors as shown below and use linprog to solve it. I don't specify a value for A and b (since I have no inequality constraints) nor a value for ub. The answer I expect to get is x_13 = 4, x_23 = 2, and x_34 = 5. The answer I actually get is x_41 = 5, x_32 = 2, and x_13 = 1. I'm using the default linprog options, although I did try varying the algorithm to no effect. Am I setting up the problem incorrectly?

f= zeros(4,4)
f(1,2) = 2
f(1,3) = -5
f(2,3) = -1
f(2,4) = 4
f(3,2) = 6
f(3,4) = 3
f(4,1) = 7
Aeq = zeros(4, 16)
Aeq(1,4)=1
Aeq(1,5)=-1
Aeq(1,9)=-1
Aeq(2,5)=1
Aeq(2,7)=1
Aeq(2,10)=-1
Aeq(2,14)=-1
Aeq(3,7)=-1
Aeq(3,9)=1
Aeq(3,10)=1
Aeq(3,15)=-1
Aeq(4,4)=-1
Aeq(4,14)=1
Aeq(4,15)=1
f = Aeq
beq = [4;2;-1;-5]
lb = zeros(16,1)
linprog(f, [], [], Aeq, beq, lb, [])