Summary Supply Chain Lab
By Pepijn Paans
Student 2016 – 2017
MSc Transport & Supply Chain Management
FACEBOOK: https://www.facebook.com/pepijn.paans
LINKEDIN: https://www.linkedin.com/in/pepijn-paans-6b828a80
EMAIL:
,Chapter 15 Management science
Integer linear programming models:
All integer linear programme: all variables are integers (round numbers), where X1, X2 …, Xn
are not only >0 ‘and integer’.
Mixed integer linear programme: some, but not all, variables have to be integers. Where
e.g. X1, X2 >0 and X2 integer
LP relaxation means: dropping the requirement for the solution to have integers: no
integers required.
0-1 linear integer programme: an application where the variables are not only integers but
are also bound to be either 0 or 1.
The example in the book describes a manager that has available €2 million to purchase
either townhouses or apartments, respectively yielding €10k and €15k a year. The problem
looks like:
T and A must be integers, because it is not possible to purchase fractional numbers of
townhouses or apartments.
Via the graphical solution method, a maximum of T=2,479 and A=3,252 is found and the
annual cash flow becomes €73.574. However, as we just said, this is not possible.
Rounding can form a solution but only when the rounding results in minimal impact of the
objective function, e.g. 15.132,4 à 15.132 (read, boxes of cereal).
However, for small values of decision variables rounding is not a good option in case these
numbers have massive impact on the objective function or on the feasibility of the solution,
such as in our property buying example.
Rounding in our example to e.g. T=2 and A=3 results in annual cashflow of €65k.
Substantially less then without rounded numbers under LP relaxation.
Using the graphical method again, where the feasible region contains dots for all the
possible integer solution and finally moving the objective line to the best extreme point
,shows that the optimal integer solution is T=4 and A=2 with an objection function value of
€70k, much better than if we would simply round the numbers.
Observation: for a maximization problem, the value of the optimal solution to the LP
relaxation provides the upper bound on the value of the optimal integer solution!
For minimization, this value is the lower bound!
A computer uses the so called Branch and Bound method to calculate an integer solution,
shown in the figure below (refer back to chapter 15 page 9 an onward for a thorough
explanation.
binary variables 0-1 integer linear programme
we now introduce variables that are binary, i.e. only take the value of a 0 or a 1.
, These binary variables are typically used when there is an either or choice.
We will look at a couple of common areas of business application that use binary variables
such as: capital budgeting; fixed cost problems; distribution system design; location
planning.
Capital budgeting
The example is about a company that has four investment possibilities, due to capital
restrictions not all possibilities can be executed and moreover, the company can either
execute the investment or not but it cannot execute one investment option multiple times.
It is thus integer and binary.
the objective in a capital budgeting problem is to maximize the present value of projects. In
this example, four constraints are present; one for the total capital funds available in each
of the next four years. The problem looks as follows:
E.g. setting P=0 means that it does not contribute to the objective function value but at the
same time it also does not make any costs in either of the four years. When P=1 it does
contribute to the final value of the objective function, but at the same time costs are
incurred in each of the four years: 15k, 20k, 20k, 15k euro.
So we are looking for the combination of 0s and 1s for the four decision variables that will
maximize the objective function and satisfy the defines constraints.
Fixed cost
Production costs usually split into fixed costs and variable costs. Fixed costs can be included
in a model by using 0-1 variables.
An example is where a car manufacturer produces a car model in a four-door configuration
and a two-door configuration. Switching from producing the four-door model to producing
the two-door model required reconfiguring the production line and thus set-up (fixed) costs
are incurred.
By Pepijn Paans
Student 2016 – 2017
MSc Transport & Supply Chain Management
FACEBOOK: https://www.facebook.com/pepijn.paans
LINKEDIN: https://www.linkedin.com/in/pepijn-paans-6b828a80
EMAIL:
,Chapter 15 Management science
Integer linear programming models:
All integer linear programme: all variables are integers (round numbers), where X1, X2 …, Xn
are not only >0 ‘and integer’.
Mixed integer linear programme: some, but not all, variables have to be integers. Where
e.g. X1, X2 >0 and X2 integer
LP relaxation means: dropping the requirement for the solution to have integers: no
integers required.
0-1 linear integer programme: an application where the variables are not only integers but
are also bound to be either 0 or 1.
The example in the book describes a manager that has available €2 million to purchase
either townhouses or apartments, respectively yielding €10k and €15k a year. The problem
looks like:
T and A must be integers, because it is not possible to purchase fractional numbers of
townhouses or apartments.
Via the graphical solution method, a maximum of T=2,479 and A=3,252 is found and the
annual cash flow becomes €73.574. However, as we just said, this is not possible.
Rounding can form a solution but only when the rounding results in minimal impact of the
objective function, e.g. 15.132,4 à 15.132 (read, boxes of cereal).
However, for small values of decision variables rounding is not a good option in case these
numbers have massive impact on the objective function or on the feasibility of the solution,
such as in our property buying example.
Rounding in our example to e.g. T=2 and A=3 results in annual cashflow of €65k.
Substantially less then without rounded numbers under LP relaxation.
Using the graphical method again, where the feasible region contains dots for all the
possible integer solution and finally moving the objective line to the best extreme point
,shows that the optimal integer solution is T=4 and A=2 with an objection function value of
€70k, much better than if we would simply round the numbers.
Observation: for a maximization problem, the value of the optimal solution to the LP
relaxation provides the upper bound on the value of the optimal integer solution!
For minimization, this value is the lower bound!
A computer uses the so called Branch and Bound method to calculate an integer solution,
shown in the figure below (refer back to chapter 15 page 9 an onward for a thorough
explanation.
binary variables 0-1 integer linear programme
we now introduce variables that are binary, i.e. only take the value of a 0 or a 1.
, These binary variables are typically used when there is an either or choice.
We will look at a couple of common areas of business application that use binary variables
such as: capital budgeting; fixed cost problems; distribution system design; location
planning.
Capital budgeting
The example is about a company that has four investment possibilities, due to capital
restrictions not all possibilities can be executed and moreover, the company can either
execute the investment or not but it cannot execute one investment option multiple times.
It is thus integer and binary.
the objective in a capital budgeting problem is to maximize the present value of projects. In
this example, four constraints are present; one for the total capital funds available in each
of the next four years. The problem looks as follows:
E.g. setting P=0 means that it does not contribute to the objective function value but at the
same time it also does not make any costs in either of the four years. When P=1 it does
contribute to the final value of the objective function, but at the same time costs are
incurred in each of the four years: 15k, 20k, 20k, 15k euro.
So we are looking for the combination of 0s and 1s for the four decision variables that will
maximize the objective function and satisfy the defines constraints.
Fixed cost
Production costs usually split into fixed costs and variable costs. Fixed costs can be included
in a model by using 0-1 variables.
An example is where a car manufacturer produces a car model in a four-door configuration
and a two-door configuration. Switching from producing the four-door model to producing
the two-door model required reconfiguring the production line and thus set-up (fixed) costs
are incurred.
