Samenvatting van het vak Operations Research, gegeven aan de Universiteit Maastricht.
Bevat onder andere de volgende onderwerpen:
operations research - transportation problem - simplex method - optimal solution - transportation simplex method - degeneracy - assignment problem - minimum-cost flow...
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)
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper FamkeNouwens. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €6,49. Je zit daarna nergens aan vast.
