Note: This page has been translated by MathWorks. Please click here

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

To view all translated materals including this page, select Japan 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.

Was this topic helpful?