Samenvatting
Samenvatting Linear Programming
- Instelling
- Maastricht University (UM)
Samenvatting van het vak Linear Programming, gegeven aan de Universiteit Maastricht.
[Meer zien]Voorbeeld 2 van de 8 pagina's
Voorbeeld 2 van de 8 pagina's
In winkelwagengesponsord bericht van onze partner
Voorbeeld van de inhoud
Linear Programming F a mke N o u we n sLecture 1
A linear program consists of:
- Objective function Z: function of decision variables (x1, .., xn) that we try to maximize or
minimize.
- Constraints:
• Functional: define the range of values for the decision variables
• Nonnegativity: the variable(s) are nonnegative. These need to be in the LP!
The constraints create a feasible region: a collection of solutions where all constraints are satisfied.
With an LP we assume:
- We only work with sums
- The decision variables are allowed to have any value that satisfies the constraints
- We assume that the value assigned to each parameter is a known constant.
- The optimal solution for an LP is always a corner-point of the feasible region.
There are two techniques for solving an LP:
- Simplex method (exterior-point method): goes along the border of the feasible region, one
corner-point at a time
- Interior-point method: goes through the middle of the feasible region (no corner-points).
This one is much slower than SM, but the number of iterations required increases much
more slowly than with the Simplex-method (so it’s better for large instances).
If we only have two decision variables, we can also use a graphical method, where we draw the
constraints in a graph and calculate the corner-points for optimality.
Lecture 2
An LP has a standard form:
- We maximize Z
- All decision variables are nonnegative (≥ 0)
- All functional constraints are of the form ≤
Real-world applications of LP’s:
- Maximum flow problem: constraints consist of the arc capacity constraints, the inflow =
outflow constraints, and the nonnegativity constraints. Side constraints can be:
• Minimum flow constraint (x1 should carry at least 3 units of flow: x1 3)
• Flow consumption constraint (node b keeps 2 units for itself: x2 = x3 + x4 + 2)
• Flow entering constraint (b is at most 5: x2 5).
- Linear regression problem: Minimize line y = ax + b by minimizing ∑ni=1 |(asi + b) − t i |. a
and b will be decision variables modeling the line and also use decision variables e1, …, en
measuring the vertical distance of point (s i,ti) from the line. So n+2 decision variables.
Minimize e1 + e2 + … + en
s.t. ei = |asi + b + ti| for each ei ≈ e1 as1 + b + t1 and e1 -(as1 + b + t1).
Once the core model has been stabilized for an LP, it is easy to add extra side constraints.
Lecture 3
When we have an LP, we have feasible and infeasible solutions. For the system to have a unique
solution we need one of these to be true:
, - Row-rank(C) = column-rank(C) = m
- All rows of C are linearly independent
- All columns of C are linearly independent
- C is invertible, so C-1 exists
If these conditions do not hold, then the system is either infeasible or
infinitely many solutions exists.
The simplex method only considers corner-point feasible solutions (CPF): a
solution where two or more constraints are equal. A solution is feasible if
and only if all the basic variables are ≥ 0.
The trick to solving an LP is to transfer the system into a higher dimension (= more decision
variables).
Dealing with constraints:
- ≤ : introduce a slack variable, that turns the constraint into =. It deals with the lack of the =
−constraint. If the slack variable is 0, it means the constraint is tight → the original variable
is sitting on the constraint boundary.
- = : introduce an artificial variable, that makes sure the Simplex method can start at the
origin.
- ≥ : introduce a surplus and an artificial variable. The surplus variable is the same as a slack
variable, but then deals with the excess.
If the LP is in standard form (Ax b), where A has m rows (constraints) and n columns (variables),
then the augmented form will consist of m equalities in m + n variables.
Lecture 4
Simplex method – method to solve an LP in standard form. Algorithm:
- We start with creating a basis: the
variables that are non-zero. In the
beginning these are the slack variables.
The size of the basis is the number of
functional constraints. Basic variables
never appear in the objective function!
- Determine the entering variable: the
variable that has the most potential to
improve Z and the leaving variable: the
row in the basis that has the highest
ratio: Z/coefficient of entering variable in
that row. Important, we only need to look at rows with strictly positive coefficients in the
pivot column!
- Use elementary row operations to create 0-1 pattern in column of entering variable and
repeat the process until there are no negative numbers in the top row anymore.
- The values for Z and the basic variables can be read off on the right-hand side.
Adjacent solutions – two solutions that have n – 1 constraint boundaries in common, ie. The two
sets of non-basic variables differ in exactly one variable.
There can be multiple optimal solutions, that can be explored by continuing to pivot after obtaining
an optimal CPF by choosing a non-basic variable with coefficient 0 in the top row as pivot column.
Some problems that can occur:
- No leaving basic variable → unbounded objective function
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.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 67866 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen