Documentation

This is machine translation

Translated by Microsoft
Mouse over text to see original. Click the button below to return to the English verison of the page.

Typical Linear Programming Problem

This example shows the solution of a typical linear programming problem. The problem is

minxfTx such that {Axb,Aeqx=beq,x0.

You can load the matrices and vectors A, Aeq, b, beq, f, and the lower bounds lb into the MATLAB® workspace with

load sc50b

This problem in sc50b.mat has 48 variables, 30 inequalities, and 20 equalities.

Use linprog to solve the problem:

options = optimoptions(@linprog,'Algorithm','dual-simplex','Display','iter');
[x,fval,exitflag,output] = ...
    linprog(f,A,b,Aeq,beq,lb,[],options);

Because the iterative display was set using optimoptions, the results displayed are

LP preprocessing removed 2 inequalities, 16 equalities,
16 variables, and 26 non-zero elements.

 Iter      Time            Fval  Primal Infeas    Dual Infeas  
    0     0.002    0.000000e+00   0.000000e+00   1.305012e+00  
    7     0.002   -1.587054e+02   3.760622e+02   0.000000e+00  
   34     0.002   -7.000000e+01   0.000000e+00   0.000000e+00  

Optimal solution found.

For this problem, the interior-point linear programming algorithm quickly reduces the scaled residuals below the default tolerance of 1e-08.

The exitflag value is positive, telling you linprog converged. You can also get the final function value in fval and the number of iterations in output.iterations:

exitflag,fval,output

exitflag =
     1

fval =
  -70.0000

output = 
  struct with fields:
         iterations: 34
    constrviolation: 2.2737e-13
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 1.6787e-14
Was this topic helpful?