Main Content

Typical Linear Programming Problem

This example solves the typical linear programming problem

minxfTxsuchthat{Axb,Aeqx=beq,x0.

Load the sc50b.mat file, which is available when you run this example and contains the matrices and vectors A, Aeq, b, beq, f, and the lower bounds lb.

load sc50b

The problem has 48 variables, 30 inequalities, and 20 equalities.

disp(size(A))
    30    48
disp(size(Aeq))
    20    48

Set options to use the dual-simplex algorithm and the iterative display.

options = optimoptions(@linprog,'Algorithm','dual-simplex','Display','iter');

The problem has no upper bound, so set ub to [].

ub = [];

Solve the problem by calling linprog.

[x,fval,exitflag,output] = ...
    linprog(f,A,b,Aeq,beq,lb,ub,options);
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
37 rows, 37 cols, 93 nonzeros
20 rows, 20 cols, 61 nonzeros
15 rows, 15 cols, 59 nonzeros
12 rows, 12 cols, 58 nonzeros
12 rows, 12 cols, 58 nonzeros
Presolve : Reductions: rows 12(-38); columns 12(-36); elements 58(-60)
Solving the presolved LP
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0    -8.6188182138e-01 Ph1: 9(12.9103); Du: 1(0.861882) 0s
         14    -7.0000000000e+01 Pr: 0(0) 0s
Solving the original LP from the solution after postsolve
Model   status      : Optimal
Simplex   iterations: 14
Objective value     : -7.0000000000e+01
HiGHS run time      :          0.00

Optimal solution found.

Examine the exit flag, objective function value at the solution, and number of iterations used by linprog to solve the problem.

exitflag,fval,output.iterations
exitflag = 1
fval = -70.0000
ans = 14

You can also find the objective function value and number of iterations in the iterative display.