Summary of the Operations Research course, given at Maastricht University.
Includes the following topics:
operations research - transportation problem - simplex method - optimal solution - transportation simplex method - degeneracy - assignment problem - minimum-cost flow - integer programming -...
OPERATIONS RESEARCH
operations research
Lecture 1 – Transportation Problem
Famke Nouwens
Operations research is prescriptive: it tells you what you should do in order to optimize performance, subject to
constraints.
Transportation problem (TP): a special type of linear programming problem where the objective consists in
minimizing transportation cost of a given commodity from a number of sources (e.g. factory, manufacturing
facility) to a number of destinations (e.g. warehouse, store).
Each source has a limited supply (i.e. maximum number of products that can be sent from it) while each
destination has a demand to be satisfied (i.e. minimum number of products that need to be shipped to it). The
cost of shipping from a source to a destination is directly proportional to the number of units shipped.
In tableau format it looks like the Simplex Tableau, except it has a
bottom row indicating total demand per destination and a last
column indicating total supply per source.
There is always the restriction of: sum of supplies = sum of demand.
However, this restriction can be softened with dummy destinations
and/or supplies: a ‘variable’ that absorbs the fictional overproduce or overdemand. To compute the
supply/demand for a dummy point: look at total demand or total supply and subtract what is needed for the
other points.
We use the notation of Big M to denote that a destination shouldn’t receive any supply.
A property of the TP: if the sources and demand are all integers, there will exist an integral optimal solution. We
use TP instead of regular LP’s since it can be solved much faster and we have more insight (i.e. we know there
exists an integral optimal solution).
Lecture 2 – Transportation Simplex Method
Simplex method:
1) Construct initial Basic Feasible Solution (BFS)
2) Check whether BFS is optimal
3) If not, identify non-basic (= 0) variable with most potential to improve objective function and have it
enter the basis (new BFS). Leaving variable is determined with minimum-ratio test. Go back to 2).
Transportation Simplex Method (TSM):
We always have m+n-1 basic variables (dummy counts as extra
source/demand!) and we use a special tableau where:
xij: value of the basic variable
cij – ui – vj: top-row entry of non-basic variable (it’s not the
value of the non-basic variable! It is the potential to improve
the objective function!).
Steps:
1) Construct initial BFS:
Use Northwest-corner rule: start in the north-west corner and supply as much as demanded
(or as supply allows). If there is additional supply, strike column and move left. If there is more
demand, strike row and move down. Keep doing this until you come in the bottom-right
corner. This is the basic BFS (circled values xij).
2) Check whether BFS is optimal:
Fill in the additional information for all non-basic variables according to the formula. For this,
we need the ui and vj values:
· For basic variables: cij – ui – vj = 0. Arbitrarily, set one of the ui and vj values to 0
(row with most basic variables).
If none of the values are negative, we have reached optimality.
3) Identify non-basic variable with most negative top-row entry as entering variable and determine
leaving variable with closed-loop.
, Choose most-negative value from non-basic variables.
Create a closed-loop satisfying the following:
· Any two consecutive cells lie in either the same row or same column.
· No three or more consecutive cells lie in the same row or column.
· The last cell is in the same row or column as the first cell.
The steps:
1) Find the only loop involving the entering variable and some of the basic feasible
variables.
2) Count the cells in the loop (starting from 0), label them as negative (-) cells or
positive (+) cells.
3) Find the negative cell with the smallest value. Call this value X. This cell
corresponds to the leaving variable.
4) Decrease each negative cell in the loop by X and increase each positive cell in the
loop by X.
5) New BFS! Update all additional information.
Go to 2).
The Northwest corner rule is easy but can start off quite far from optimality.
Degeneracy: at least one of the basic variables is zero. This causes iterations where Z does not increase.
TSM is faster than Simplex method in the pivoting: updating the tableau after having identified the entering and
leaving variable.
Lecture 3 – Assignment problem and minimum-cost flow
Assignment problem: special case of transportation problem where the people become the suppliers and their
tasks/assignments the destinations (n people and n tasks). Each task has demand 1 and each person has supply
1.
Maximum flow: in a find-shortest-path problem/graph we view each arc as a one-way pipeline with a maximum
flow capacity. The goal is to send as much from the source to the destination (sink). All nodes in between are
transshipment nodes and must obey flow in = flow out.
Min-cut max-flow theorem: the size of the maximum flow is equal to the minimum total capacity of any set of
arcs whose removal destroys all directed paths from O (source) to T (sink).
Minimum-cost flow: arcs have an associated cost and goal is to route a given amount of flow with minimum
cost. If there is a mismatch between supply and demand we can use dummy supply/demand points.
Linear Program formulation for flow:
xij – flow through arc i-j
cij – cost per unit flow through arc i-j
uij – arc capacity for arc i-j
bi – net flow generated at node i where:
· b > 0 if node is a supply node
· b < 0 if node is a demand node
· b = 0 if node is a transshipment node
Objective function: minimize sum of flow in arc × cost per unit flow through that arc, ranging over all arcs such
that for each node: flow leaving node – flow entering node = b.
To go from a maximum-flow problem to minimum-cost flow you add a dummy edge with unlimited capacity
from source to sink, with high cost (M). Any flow not routed through the real network will be punished heavily
so min-cost flow will attempt to minimize this (thus maximizing the real flow).
Lecture 4 – Network Simplex Method
If there are n nodes, there will always be n-1 basic variables (arcs) and BFS will be in 1-1 correspondence with
feasible spanning trees.
NSM incorporates upper bound technique: implicitly encode arc constraints. Central idea: we don’t need a
dedicated slack variable for the upper-bound constraint xij ≤ uij because the slack is always xij - uij. With this
technique we have to watch out for which basic variable will hit zero first, but also for the possibility that
, increasing the entering variable will cause some basic variable to reach its arc capacity xij = uij. At this point we
switch from xij (amount of flow > 0) to uij – yij, where yij is amount of flow below capacity. Substitute uij – yij for xij
everywhere (update the constraints, which causes arc direction to be flipped).
Steps:
1) Somebody gives you a basis (i.e. a feasible spanning tree). You need to computer the initial values of
the basic arcs.
2) Could adding in some non-basic arc (i.e. making it the entering basic variable) improve our Z-score? If
no, we are done. Else we identify the most-negative non-basic arc (calculate reduced cost).
3) Identify leaving basic variable and adjust the flow in the arcs. The leaving variable will exit either
because it hits zero or its upper bound. Be sure to adjust the arc direction (and the net consumption of
flow at the endpoints of arcs)!
4) Repeat until no negative reduced cost
5) Flip back any arcs pointing the wrong way
Lecture 5 – Integer Programming
Integer Programming can, unlike LP, often be used to solve NP-hard problems in practice, and it asks the user to
specify what they want, rather than how they want to achieve it.
Integer Linear Programming (ILP) is linear programming with the added possibility of restricting some variables
to be integers (optional!). Mixed Integer Linear Programming (MILP) explicitly has a mixture of normal and
integer variables, in contrast to pure IP.
Binary Integer Programming (BIP) – subcategory of IP where all integer variables in the program are binary
(forced to take either the value 0 or 1). This is often used to model ‘yes or no’ decisions.
Modelling tricks:
1. Either-or constraints
Example:
3x1 + 2x2 ≤ 18 + M y where at least one of these must hold
x1 + 4x2 ≤ 16 + M (1-y)
where y ∈ {0, 1}
Trick: add auxiliary binary variable. If y = 0, first constraint will hold, and second constraint is essentially
switched off (so second can be hold or not). If y = 1, the opposite.
2. At least K out of N constraints must hold
Example:
… ≤ d1 + My1
…. ≤ d2 + My2
…. ≤ dn + Myn
∑𝑖 𝑦𝑖 = N - K
Trick: introduce auxiliary binary variable for all constraints, with yi ∈ {0, 1}.
3. Functions with N possible values
Example:
xi ∈ {-4, 32, 73.95} N=3
xi = -4y1 + 32y2 + 72.95y3 where all yi ∈ {0, 1}
y1 + y2 + y3 = 1
Trick: write as two constraints with auxiliary binary variables.
4. The fixed-charge problem
Example: let xi be the amount of stuff we produce, let ci be the cost of producing one unit of ‘stuff’.
Total cost: c1x1 + F if xi > 0
0 if xi = 0
Minimize ….. + cixi + … + Fy1
xi ≤ Myi where yi ∈ {0, 1} Note! xi > 0 → yi = 1
(also because we’re minimizing: if xi = 0 → yi = 0)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller FamkeNouwens. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.04. You're not tied to anything after your purchase.
