🔍
Integer Linear Programming - Binary (0-1) Variables 1, Fixed Cost - YouTube
Channel: Joshua Emmanuel
[0]
Welcome!
[1]
In this tutorial I’ll formulate linear integer
programming models involving Binary or 0-1
[7]
variables.
[9]
Binary variables are employed when there is
a yes or no situation.
[13]
That is, to indicate whether a selection is
made or not.
[17]
For example, suppose we have 4 different projects
to consider.
[20]
We can either select a project, or not select
it.
[24]
So for the first project we can define the
decision variable as follows:
[28]
X1 = 1 if project 1 is selected, and 0 if
not selected.
[33]
We do the same for projects 2, 3, and 4 by
defining X2, X3, and X4.
[39]
Or we can simply write
Xi = 1 if project i is selected, and 0 if
[45]
not selected.
[46]
where i = 1, 2, 3, and 4.
[50]
Now, suppose each project has the same lifespan
of 3 months (January to March), with corresponding
[57]
outlays or costs (in thousands of dollars)
shown here.
[61]
Suppose these are the funds available for
selected projects each month, and these are
[66]
the net returns (in thousand dollars) from
each project.
[71]
In this case, our objective is to maximize
return which is
[74]
217X1 + 125X2 + 88X3 + 109X4.
[81]
Since project outlays are constrained by available
funds, we write (for January)
[88]
58X1+ 44X2+ 26X3+ 23X4 ≤ 120
We do the same for February, and for March.
[98]
And then complete the model by stating that
the decision variables must be binary.
[103]
Upon solving this model using software like
LINDO or Excel Solver, we find that the optimal
[109]
solution is
X1 = 1, X2 = 0, X3 =1, and X4 = 1 with a corresponding
[118]
net return on 414.
[121]
That is, to maximize net return, undertake
projects 1, 3 and 4 only.
[126]
Let’s now model a fixed cost problem.
[130]
Suppose a small company receives an order
to supply 1000 units of a product.
[135]
The company has 3 machines that can be used
to produce the product.
[138]
Here are the variable costs per unit produced
from each machine, here are the fixed costs,
[144]
and here are the machines’ capacities.
[146]
Our objective is to minimize total costs.
[150]
We’re going to need 2 types of decision
variables in this case.
[154]
One set for the number of units produced from
each machine, and because of the fixed costs,
[159]
another to indicate whether a machine is being
used or not.
[162]
So for units produced we write
Xi = number of units produced on machine i
[168]
(i = 1, 2, 3)
That is, X1 represents units produced on machine
[171]
1, X2 for machine 2 and X3 for machine 3.
[176]
Now because fixed costs indicate that the
entire cost will be incurred if the corresponding
[181]
machine is used to produce at all, we define
another set of variables.
[187]
For machine 1 we can write Y1 = 1 if machine
1 is used, 0 otherwise.
[194]
That is, if X1 > 0, Y1 = 1, otherwise Y1 = 0.
[201]
For all 3 machines we write
Yi = 1 if machine i is used, 0 otherwise …
[208]
So for the objective function, which is to
minimize total costs, we write
[213]
Minimize 2.39X1 + 1.99X2+ 2.99X3 + 300Y1+250Y2+
400Y3
[220]
That is, we multiply variable costs by units
produced
[229]
and multiply the fixed costs by the corresponding
0-1 variables.
[233]
When Y1 = 1 here, for example, it means that
machine 1 is used and the fixed cost of 300
[240]
will be incurred.
[241]
And when Y1 = 0, machine 1 is not used, so
the fixed cost of 300 will not be incurred.
[248]
For the constraints, we have an order here
to supply 1000 units.
[252]
So we write
X1+X2+X3 = 1000
[257]
Equality is used here because we have to meet
the order or demand placed by the customer.
[263]
Now, for the capacities.
[264]
Normally we just write
X1 ≤ 400, X2 ≤ 550, and X3 ≤ 600
[274]
Note that this X1 ≤ 400 constraint simply
states that we can produce up to 400 units
[281]
on machine 1.
[282]
But if the machine is not used at all, this
won’t be possible.
[286]
So whenever we have fixed costs associated
with minimum requirements or maximum capacities,
[292]
we usually multiply the capacity by the corresponding
binary variable.
[297]
So the correct format is X1 ≤ 400Y1.
[303]
That is, when Y1 = 1, we can produce up to
400 on machine 1, and when Y1 = 0, 0 units
[311]
should be produced.
[312]
We do the same for machine 2, and for machine
3.
[315]
We can then move the variables to the left
side of the constraints.
[320]
And state that Xis should be non-negative,
and the Yis binary.
[325]
On solving this model, we obtain
X1 = 0, X2 = 550, X3 = 450
[332]
and for the binary variables
Y1 = 0, Y2 = 1, and Y3 = 1.
[338]
Showing that only machines 2 and 3 should
be used.
[342]
And that completes the fixed cost problem.
[344]
In the next video, I’ll be showing how to
formulate some relational constraints using
[349]
binary variables, including multiple choice,
mutually exclusive, co-requisite, and conditional
[356]
constraints.
[357]
Thanks for watching.
Most Recent Videos:
You can go back to the homepage right here: Homepage