Resume
Summary D0H45A_Linear Optimisation: Part 2: Models
- Établissement
- Katholieke Universiteit Leuven (KU Leuven)
- Book
- Operations Research
Uitbreiding van grafiek en simplex method om LP problemen op te lossen
[Montrer plus]
Livre connecté
Titre de l’ouvrage:
Auteur(s):
- Édition:
- ISBN:
- Édition:
Vendeur
S'abonner
Aperçu du contenu
Part 2: MethodsGraphical solution of LP problems with two variables
General form
Max cx
s.t. Ax ≤ b
x≥0
To graphically determine the
solution of an LP problem we will
represent the information we have
in a graph by drawing the lines of
all the constraints and determine
on basis if that the feasible region.
In order to find the optimal
solution of the feasible set we will
draw the objective function and
make it move in the direction c.
C is the improving direction and is the vector made with the coefficients of the objective
function.
Isoprofit line: line on which all points have the same z-value (𝑧 = 𝑎𝑥$ + 𝑏𝑥?) for
maximization problems
Isocost line: line on which all points have the same z-value (𝑧 = 𝑎𝑥$ + 𝑏𝑥? ) for minimization
problems
As we move the isoprofit lines in the direction of c, the total profit will increase. To solve an
LP problem in 2 variables, we should try tp push isoprofit (or isocost) lines in the improving
direction as much as possible while still staying in the feasible region.
!! for a maximization problem we use c as improving direction. For minimization problems
we will have to use ( -c) because otherwise we are improving.
The feasible region is defined by the constraints so if we modify the objective function while
keeping the constraints the same, this one won’t change.
What will change in this case is the improving direction => is defined by the objective
function.
Convex set
Set S is convex if the line joining any pair of points in S is completely contained in S.
, Convex if for two points 𝑥 ∈ 𝑆 and 𝑦 ∈ 𝑆, their convex combination 𝜆𝑥 + (1 − 𝜆)𝑦 ∈ 𝑆 for
all 𝜆 ∈ [0,1].
ð Feasible set of an LP must be a convex set
Strict convex combination
X is a strict convex combination of 𝑥$ and 𝑥? if 𝑥 = 𝜆𝑥$ + (1 − 𝜆)𝑥? for some 𝜆 ∈ ]0,1[.
Extreme point (corner point)
P is an extreme point of it cannot be represented as a strict convex combination of distinct
points of S. If to represent the point as a convex combination of 2 other points then if one
point is in the set then the other one will necessarily have to be outside of the set S.
In the case that the isoprofit or isocost line on a constraint line arrives when optimization its
direction, we will have as optimal solution every feasible solution on the segment of the
constraint line that belongs to the feasible region.
ð LP has multiple or alternate optimal solutions
Unbounded LP Problems:
Arises when we the objective function can be moved infinitely while keeping optimizing the
problem and staying in the feasible region.
For such a LP problem there is no optimal solution because we can always find beter and
the optimal value is defined to be +∞ (−∞)
Infeasible LP Problems:
Happens when we can’t find a feasible solution.
Fundamental Theorem of Linear Programming
“If the feasible set is not empty, if there is a feasible solution, then there is at least an
extreme point.”
“If an LP with feasible set has an optimal solution, then there is an extreme point of the
feasible region that is an optimal solution to the LP.”
ð ! not every optimal solution needs to be an extreme point!
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur chlodewandeleer. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €4,49. Vous n'êtes lié à rien après votre achat.
Peut-on faire confiance à Stuvia ?
4.6 étoiles sur Google & Trustpilot (+1000 avis)
78252 résumés ont été vendus ces 30 derniers jours
Fondée en 2010, la référence pour acheter des résumés depuis déjà 14 ans