matlablinear-programming

linprog doesn't match expected output

I have a problem were I need to find an LP function to solve it.In this problem we have 10 tons of wheat that needs to be transported to different cities 2,3,4,5 from source city 1. In the graph the cost per ton of every edge is written and near every vertice there is a triangle that includes the amount(in tons) that is destined for every city.The problem asks to find an optimal LP based strategy to optimize the wheat transportation at the lowest possible cost.

enter image description here

In order to solve this problem with LP I set the amount of tons transported through an edge as x{i,j} where i is a city and j is its neighbor city that it is connected to.

My objective is to find the minimum of the sum of tons-transported through the edges of the graph multiplied by the cost per ton for every edge.

f = 50x{1,2}+20x{1,4}+40x{2,3}+30x{2,5}+40x{4,3}+10x{4,5}+50*x{5,3}

After finding the amount of tons transported through every edge I will have the optimal way that wheat is distributed at the lowest possible cost.

The constraints are: For every vertice the sum of tons transported through every neighboring edge is equal to the value inside the triangle.

For example: x{1,2}-x{2,5}-x{2,3} = 1 (For vertice 2)

Note:For edges pointing outwards from a vertice we subtract them from the edges pointing inwards

And also all x{i,j} are greater equal than 0

To solve the LP problem I used MATLAB with the code below:

Aeq = [1 1 0 0 0 0 0; 
       1 0 -1 -1 0 0 0; 
       1 0 0 0 -1 -1 0; 
       0 0 1 0 1 0 1;
       0 0 0 1 0 1 -1;];

beq = [10; 1; 0; 6; 3;];

f = [50; 20; 40; 30; 40; 10; 50;];

[x,fval] = linprog(f,[],[],Aeq,beq,zeros(7,1));

disp(x);

However the solution that I get isn't the optimal solution as minimum cost is 500 and not 620 that the program returns.

My question is whether my approach to the problem is wrong or my MATLAB code is missing something because I'm not very familiar with linprog() function.

Solution

  • Your Aeq is incorrect.

    Aeq(3,:) should be

    >> Aeq(3,:)
ans =
     0     1     0     0    -1    -1     0

    where you are writing the constraint for vertex 4 and need x{1,4}, not vertex 2 and x{1,2}.

    You do get 500 as the output from linprog with the correct Aeq.

    >> Aeq = [1 1 0 0 0 0 0; 
       1 0 -1 -1 0 0 0; 
       0 1 0 0 -1 -1 0; 
       0 0 1 0 1 0 1;
       0 0 0 1 0 1 -1;];
>> [x,fval] = linprog(f,[],[],Aeq,beq,zeros(7,1));

Optimal solution found.

>> dot(x,f)
ans =
   500