Solving transportation problems (LPP) using linprog in MATLAB

[Wrichik Basu]

I want to solve transportation problems (TP) in MATLAB. For solving LPPs, MATLAB provides the linprog function in the Optimization Toolbox.

According to my book, the following is a TP:

​

​	$\mathbf{D_1}$​	$\mathbf{D_2}$​	$\mathbf{D_3}$​	$\mathbf{D_4}$​	​
$\mathbf{O_1}$​	$c_{11}$​	$c_{12}$​	$c_{13}$​	$c_{14}$​	$\mathbf{a_1}$​
$\mathbf{O_2}$​	$c_{21}$​	$c_{22}$​	$c_{23}$​	$c_{24}$​	$\mathbf{a_2}$​
$\mathbf{O_3}$​	$c_{31}$​	$c_{32}$​	$c_{33}$​	$c_{34}$​	$\mathbf{a_3}$​
​	$\mathbf{b_1}$​	$\mathbf{b_2}$​	$\mathbf{b_3}$​	$\mathbf{b_4}$​

Here, $D_j$ are the destinations, $O_i$ are the origins, $a_i$ are the availabilities at the origins $O_i$, $b_j$ the requirements at destinations $D_j$, and $c_{ij}$ is the cost of transport of unit commodity from $O_i$ to $D_j$. We assume that the problem is balanced, i.e. $\sum\limits_i a_i = \sum\limits_j b_j$.

There are several methods for solving TPs, like North-West corner rule, row-minima method, etc. Here, however, I am interested in converting the above TP to an LPP. The LPP will be:

Minimize the objective function, $$Z = \sum_{i, j} c_{ij} ~ x_{ij}$$ subject to the constraints

• $\sum_j x_{ij} = a_i$,
• $\sum_i x_{ij} = b_j$,
• $x_{ij} \ge 0$.

I have written the following MATLAB function file:

function tp(cost, avb, req)

    if sum(avb) ~= sum(req)
      
        exc = MException('tp:unbalancedProblem', ...
                            'Cannot solve unbalanced problem.');
  
        throw(exc);
    end
  
    x = optimvar('x', size(cost, 1), size(cost, 2), 'LowerBound', 0);
  
    z = sum(x .* cost, 'all');
  
    numCons = size(cost, 1) + size(cost, 2);
  
    cons = optimconstr(numCons, 1);
  
    count = 1;
    for i = 1:1:size(x, 1)
        cons(count) = sum(x(i, :)) == avb(i);
        count = count + 1;
    end
  
    for i = 1:1:size(x, 2)
        cons(count) = sum(x(:, i)) == req(i);
        count = count + 1;
    end
  
    problem = optimproblem('Objective', z, 'ObjectiveSense', 'min');
    problem.Constraints = cons;
  
    show(problem)
  
    problem = prob2struct(problem);
  
    [sol, zval, exitflag, output] = linprog(problem)

end

Let's consider the following worked out problem from my book:

​

​	$\mathbf{D_1}$​	$\mathbf{D_2}$​	$\mathbf{D_3}$​	$\mathbf{D_4}$​	$\mathbf{a_i}~\downarrow$​
$\mathbf{O_1}$​	4​	6​	9​	5​	16​
$\mathbf{O_2}$​	2​	6​	4​	1​	12​
$\mathbf{O_3}$​	5​	7​	2​	9​	15​
$\mathbf{b_j}~\rightarrow$​	12​	14​	9​	8​	​

​

In MATLAB, I execute as follows:

>> cost = [4 6 9 5; 2 6 4 1; 5 7 2 9];
>> avb = [16 12 15];
>> req = [12 14 9 8];
>>
>> tp(cost, avb, req)

  OptimizationProblem :

    Solve for:
       x

    minimize :
       4*x(1, 1) + 2*x(2, 1) + 5*x(3, 1) + 6*x(1, 2) + 6*x(2, 2) + 7*x(3, 2) + 9*x(1, 3) + 4*x(2, 3)
     + 2*x(3, 3) + 5*x(1, 4) + x(2, 4) + 9*x(3, 4)    subject to :
       x(1, 1) + x(1, 2) + x(1, 3) + x(1, 4) == 16
       x(2, 1) + x(2, 2) + x(2, 3) + x(2, 4) == 12
       x(3, 1) + x(3, 2) + x(3, 3) + x(3, 4) == 15
       x(1, 1) + x(2, 1) + x(3, 1) == 12
       x(1, 2) + x(2, 2) + x(3, 2) == 14
       x(1, 3) + x(2, 3) + x(3, 3) == 9
       x(1, 4) + x(2, 4) + x(3, 4) == 8

    variable bounds:
       0 <= x(1, 1)
       0 <= x(2, 1)
       0 <= x(3, 1)
       0 <= x(1, 2)
       0 <= x(2, 2)
       0 <= x(3, 2)
       0 <= x(1, 3)
       0 <= x(2, 3)
       0 <= x(3, 3)
       0 <= x(1, 4)
       0 <= x(2, 4)
       0 <= x(3, 4)Optimal solution found.sol =

     8
     4
     0
     8
     0
     6
     0
     0
     9
     0
     8
     0zval =

   156exitflag =

     1output =

  struct with fields:

         iterations: 6
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 0

In the book, they have solved using north-west corner rule. The answer given is $z = 226$.

Is my MATLAB program wrong, or am I just getting a more optimized answer than the book?

N.B.: This is a programming question and not a homework question.

 

[Wrichik Basu]

I believe my program is correct. The different methods that I mentioned above, like row minima method, NW corner rule, Vogel's Approximation, etc., when applied to the same problem, can give in different solutions. So, the solutions are not unique in most cases. MATLAB's algorithm for solving the LPP is certainly far better than any of those methods.

I have also modified the function to make it work for unbalanced problems too. Maybe I will upload the file to MATLAB File Exchange to make it available for others.

 

[judend88]

Hello Wrichik Basu!
I tried this linear transportation problem in Matlab and it did not work. Please, kindly explain to me the way forward.
Regards
Jude +2348064095411

 

[judend88]

Your program is correct based on the answer it produced. The NW method answer you were referring to is the initial basic feasible solution while yours produced the optimal solution with its corresponding optimal value. I have tried the problem using Mathematica and it gave me the results with yours (optimal solution and value). Please, kindly clarify me on how you ran the MATLAB program to get the result. I am interested to learn it. Thanks