Note: This page has been translated by MathWorks. Click here to see

To view all translated materials including this page, select Country from the country navigator on the bottom of this page.

To view all translated materials including this page, select Country from the country navigator on the bottom of this page.

This example shows how to solve a mixed-integer linear program.
The example is not complex, but it shows typical steps in formulating a problem in
the syntax for `intlinprog`

.

For the problem-based approach to this problem, see Mixed-Integer Linear Programming Basics: Problem-Based.

You want to blend steels with various chemical compositions to obtain 25 tons of steel with a specific chemical composition. The result should have 5% carbon and 5% molybdenum by weight, meaning 25 tons*5% = 1.25 tons of carbon and 1.25 tons of molybdenum. The objective is to minimize the cost for blending the steel.

This problem is taken from Carl-Henrik Westerberg, Bengt Bjorklund, and Eskil
Hultman, “*An Application of Mixed Integer Programming in a Swedish
Steel Mill*.” Interfaces February 1977 Vol. 7, No. 2 pp. 39–43,
whose abstract is at `http://interfaces.journal.informs.org/content/7/2/39.abstract`

.

Four ingots of steel are available for purchase. Only one of each ingot is available.

Ingot | Weight in Tons | %Carbon | %Molybdenum | Cost/Ton |
---|---|---|---|---|

1 | `5` | `5` | `3` | $350 |

2 | `3` | `4` | `3` | $330 |

3 | `4` | `5` | `4` | $310 |

4 | `6` | `3` | `4` | $280 |

Three grades of alloy steel are available for purchase, and one grade of scrap steel. Alloy and scrap steels can be purchased in fractional amounts.

Alloy | %Carbon | %Molybdenum | Cost/Ton |
---|---|---|---|

1 | `8` | `6` | $500 |

2 | `7` | `7` | $450 |

3 | `6` | `8` | $400 |

Scrap | `3` | `9` | $100 |

To formulate the problem, first decide on the control variables. Take variable
`x(1) = 1`

to mean you purchase ingot **1**, and `x(1) = 0`

to mean
you do not purchase the ingot. Similarly, variables `x(2)`

through `x(4)`

are binary variables indicating that you
purchase ingots **2** through **4**.

Variables `x(5)`

through `x(7)`

are the
quantities in tons of alloys **1**, **2**, and **3** you
purchase, and `x(8)`

is the quantity of scrap steel you
purchase.

Formulate the problem by specifying the inputs for
`intlinprog`

. The relevant
`intlinprog`

syntax is as follows.

[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)

Create the inputs for `intlinprog`

from first
(`f`

) through last (`ub`

).

`f`

is the vector of cost coefficients. The coefficients
representing the costs of ingots are the ingot weights times their cost per
ton.

f = [350*5,330*3,310*4,280*6,500,450,400,100];

The integer variables are the first four.

intcon = 1:4;

To specify binary variables, set the variables to be integers in
`intcon`

, and give them a lower bound of
`0`

and an upper bound of `1`

.

There are no linear inequality constraints, so `A`

and
`b`

are empty matrices (`[]`

).

There are three equality constraints. The first is that the total weight is 25 tons.

```
5*x(1) + 3*x(2) + 4*x(3) + 6*x(4) + x(5) + x(6) + x(7) +
x(8) = 25
```

.

The second constraint is that the weight of carbon is 5% of 25 tons, or 1.25 tons.

```
5*0.05*x(1) + 3*0.04*x(2) + 4*0.05*x(3) +
6*0.03*x(4)
```

.

+ 0.08*x(5) + 0.07*x(6) + 0.06*x(7) +
0.03*x(8) = 1.25

The third constraint is that the weight of molybdenum is 1.25 tons.

```
5*0.03*x(1) + 3*0.03*x(2) + 4*0.04*x(3) +
6*0.04*x(4)
```

.

+ 0.06*x(5) + 0.07*x(6) + 0.08*x(7) +
0.09*x(8) = 1.25

In matrix form, `Aeq*x = beq`

, where

Aeq = [5,3,4,6,1,1,1,1; 5*0.05,3*0.04,4*0.05,6*0.03,0.08,0.07,0.06,0.03; 5*0.03,3*0.03,4*0.04,6*0.04,0.06,0.07,0.08,0.09]; beq = [25;1.25;1.25];

Each variable is bounded below by zero. The integer variables are bounded above by one.

lb = zeros(8,1); ub = ones(8,1); ub(5:end) = Inf; % No upper bound on noninteger variables

Now that you have all the inputs, call the solver.

[x,fval] = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);

View the solution.

x,fval

x = 1.0000 1.0000 0 1.0000 7.2500 0 0.2500 3.5000 fval = 8.4950e+03

The optimal purchase costs $8,495. Buy ingots **1**, **2**, and **4**, but not **3**, and buy 7.25 tons
of alloy **1**, 0.25 ton of alloy **3**, and 3.5 tons of scrap steel.

Set `intcon = []`

to see the effect of solving the problem
without integer constraints. The solution is different, and is not sensible,
because you cannot purchase a fraction of an ingot.