Main Content

# Typical Linear Programming Problem

This example solves the typical linear programming problem

`$\underset{x}{\mathrm{min}}{f}^{T}x\phantom{\rule{0.5em}{0ex}}such\phantom{\rule{0.5em}{0ex}}that\left\{\begin{array}{c}A\cdot x\le b,\\ Aeq\cdot x=beq,\\ x\ge 0.\end{array}$`

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.