Programmation Lin ́eaire
Cours 1 : programmes lin ́eaires, mod ́elisation et r ́esolution graphique
F. Clautiaux
[Link]@[Link]
Universit ́e Bordeaux 1 Baˆt A33
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Motivation et objectif du cours
Introduction a` la programmation lin ́eaire Un outil qui permet de :
• mod ́eliser
• r ́esoudre
toute une classe de probl`emes d’optimisation. Existence de solveurs efficace pour la PL
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Ouvrages de r ́ef ́erence
V. Chv ́atal - Linear Programming, [Link], New York, 1983.
R. J. Vanderbei - Linear Programming, Foundations and Extensions,
Springer-Verlag, 2008.
C. Gu ́eret, C. Prins et M. Sevaux - Programmation lin ́eaire : 65 probl`emes d’optimisation mod ́elis ́es
et r ́esolus avec Visual Xpress, Eyrolles, 2000.
C. Prins et M. Sevaux - Programmation lin ́eaire avec Excel : 55 probl`emes d’optimisation mod ́elis ́es
pas `a pas et r ́esolus avec Excel, Eyrolles, 2011.
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Introduction par l’exemple
Exemple 1 : Production Exemple 2 : Transport Exemple 3 : Planification
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Sommaire
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Probl`eme de production
Un fabricant produit 2 types de yaourts a` la fraise A et B a` partir de Fraise, de Lait et de Sucre.
Chaque yaourt doit respecter les proportions suivantes de mati`eres premi`eres.
AB
Fraise 2 1
Lait 1 2
Sucre 0 1
On dispose de 800 Kg de Fraises, 700 Kg de Lait et 300 Kg de sucre.
La vente de 1 Kg de yaourts A et B rapporte respectivement 4e et 5e.
Le fabricant cherche a` maximiser son profit.
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
• Sur quelles quantit ́es peut-on travailler ? • Que cherche-t-on a` optimiser ?
• Quelles sont les contraintes du probl`eme ?
Mod ́elisation
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Mod ́elisation
• Sur quelles quantit ́es peut-on travailler ?
• Seules valeurs non constantes : les quantit ́es de yaourts A et B produites
• On parle de variables • On les notera xA et xB
• Que cherche-t-on a` optimiser ?
• Quelles sont les contraintes du probl`eme ?
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
• Sur quelles quantit ́es peut-on travailler ? • Variables : xA et xB
• Que cherche-t-on a` optimiser ? • Le profit z
• Calcul ́e `a partir de xA et xB • On parle de fonction objectif • z=4xA+5xB
• Quelles sont les contraintes du probl`eme ?
Mod ́elisation
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Mod ́elisation
• Sur quelles quantit ́es peut-on travailler ? • Variables : xA et xB
• Que cherche-t-on a` optimiser ? • maxz=4xA+5xB
• Quelles sont les contraintes du probl`eme ?
• Premi`ere contrainte : 800 Kg de fraises disponibles
• la quantit ́e utilis ́ee d ́epend de la production : 2xA + xB • 2xA + xB ≤ 800
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Mod ́elisation
• Sur quelles quantit ́es peut-on travailler ? • Variables : xA et xB
• Que cherche-t-on a` optimiser ? • maxz=4xA+5xB
• Quelles sont les contraintes du probl`eme ?
2xA+ xB xA+ 2xB
≤ 800
(fraises) (lait) (sucre)
≤ 700 xB ≤ 300
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Mod ́elisation
• Sur quelles quantit ́es peut-on travailler ? • Variables : xA et xB
• Que cherche-t-on a` optimiser ? • maxz=4xA+5xB
• Quelles sont les contraintes du probl`eme ?
2xA+ xB xA+ 2xB xB xA, xB
≤ 800 ≤ 700 ≤ 300 ≥ 0
(fraises) (lait) (sucre)
p o s i t i v i t ́e !
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Mon premier programme lin ́eaire
max4xA+ 5xB
2xA+ xB ≤ 800
xA+ 2xB ≤700 xB ≤ 300
xA, xB ≥0
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Probl`eme de transport
Approvisionner au moindre couˆt les clients a` partir des usines.
Usines (i ∈ I) Bordeaux Biarritz Toulouse
Productions (pi ) 25 15 20
Clients (j ∈ J) Pau Bayonne Bordeaux Libourne
Demandes (dj) 20 12 9 14
Prix/unit ́e (ci,j) Pau Bayonne Bordeaux Libourne
Bordeaux 26 19 0 4
Biarritz 12 2 20 24
Toulouse 19 30 24 28
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
• Variables :
xi,j : quantit ́e transport ́ee de i a` j
Mod ́elisation
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
• Variables :
xi,j : quantit ́e transport ́ee de i a` j
• Objectif :
Minimiser i∈I j∈J ci,jxi,j
Mod ́elisation
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
• Variables :
xi,j : quantit ́e transport ́ee de i a` j
• Objectif :
Minimiser i∈I j∈J ci,jxi,j
• Contraintes :
x ≤
j∈J i,j
pi,
x =
i∈I i,j
dj, xi,j ≥0,
∀i ∈ I (Capacit ́e de production) ∀j ∈ J (Demandes a` satisfaire) ∀i∈I,j∈J
Mod ́elisation
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Probl`eme de planification
Planifier la production d’articles a` moindre couˆt pour les 4 prochains mois.
Production maximale normale : 1200 articles / mois Production maximale en heure sup : 400 articles /
mois Surcouˆt heures sup : 7 euros / article
Stockage : 3 euros / article / mois
mois 1 mois 2 mois 3 mois 4 Demandes 900 1100 1700 1300
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Mod ́elisation
• Variables :
xt :productionnormaleenp ́eriodet=1,...,4
yt : production en heure sup en periode t = 1,...,4 st : stock en fin de p ́eriode t = 1,...,3
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Mod ́elisation
• Variables :
xt :productionnormaleenp ́eriodet=1,...,4
yt : production en heure sup en periode t = 1,...,4 st : stock en fin de p ́eriode t = 1,...,3
• Objectif :
t=4 t=3
Minimiser 7 yt + 3 st t=1 t=1
• Contraintes : s1+
s2+ s3+ 0≤ 0≤
x1+ x2+ x3+ x4+
xt ≤ yt ≤ st ≥
y1 = y2 = y3 = y4 =
1200, 400, 0,
900+ s1 1100+ s2 1700+ s3
1300
t=1,...,4
t=1,...,4 t=1,...,3
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Introduction par l’exemple
Programme lin ́eaire
R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Sommaire
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
R`egles de r ́e ́ecriture (1)
Toute contrainte d’ ́egalit ́e peut s’ ́ecrire comme deux in ́egalit ́es :
n n aixi =b≡ n
i=1a ix i≤ b
i=1aixi ≥b
i=1
Toute contrainte ≥ peut s’ ́ecrire comme une contrainte ≤ :
nn
aixi ≥b≡ −aixi ≤−b
i=1 i=1
Tout probl`eme de minimisation peut s’ ́ecrire comme un probl`eme
de maximisation :
nn max cixi ≡ min −cixi
i=1 i=1
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Ecriture g ́en ́erale d’un programmation lin ́eaire
On peut ́ecrire ainsi un programme lin ́eaire avec n variables x1,...,xn etmcontraintes.
n
max i=1c ix i
n
sous les contraintes i=1 aijxi ≤ bj,(j = 1,...,m)
xi ∈ R,(i = 1,...,n)
• Lin ́earit ́e : Objectif et contraintes sont des fonctions lin ́eaires des variables de d ́ecision (les
coefficients ci et aij des variables sont constants)
• Continuit ́e : Les variables peuvent prendre n’importe quelle valeur r ́eelle respectant les contraintes
linaires
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Exemples simples de programmes non lin ́eaires (1)
m i n sous les contraintes
n
i=1
x ix i
n
i=1 aijxi ≤ bj,(j = 1,...,m) xi ∈ R,(i = 1,...,n)
n
i=1
xi
n
i=1 aijxi ≤ bj,(j = 1,...,m) xi ∈ N,(i = 1,...,n)
m i n sous les contraintes
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Exemples simples de programmes non lin ́eaires (2)
n
min i=1c ix i
n
sous les contraintes i=1 aijxi ≤ bj,(j = 1,...,m)
xi ∈R∩[l1,u1]∩[l2,u2],(i =1,...,n)
n
min i=1c ix i
n
sous les contraintes i=1 aijxi ≤ bj,(j = 1,...,m)
x1 = x2 ou x1 = x3 xi ∈ R,(i = 1,...,n)
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Forme normale d’un programme lin ́eaire
Tout programme lin ́eaire peut s’ ́ecrire sous forme normale.
n
max i=1c ix i
n
sous les contraintes i=1 aijxi ≤ bj,(j = 1,...,m)
xi ≥ 0,xi ∈ R,(i = 1,...,n)
+ − + −
Sionaunevariablexi ∈R,onintroduitxi ≥0etxi ≥0eton pose xi = xi + xi .
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Introduction par l’exemple
Programme lin ́eaire
R ́esolution graphique
Repr ́esentation graphique d’un PL R ́esolution graphique
Points extrˆemes Forme standard, bases Bilan
Sommaire
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
R ́esolution graphique
• On dispose d’un outil (la PL) pour mod ́eliser des probl`emes • Comment r ́esoudre les probl`emes a`
l’aide de la PL ?
• Plusieurs algorithmes existent, dont le simplexe (prochain cours)
• Pour des probl`emes avec deux variables, on peut r ́esoudre graphiquement (aide `a comprendre la structure du
probl`eme)
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Repr ́esentation graphique
xB
2xA + xB ≤ 800
max 4xA+ 5xB 2xA+ xB xA+ 2xB xB xA, xB
≤ 800 ≤700 ≤ 300 ≥0
xB ≤ 300
xA + 2xB ≤ 700
xA
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Repr ́esentation graphique
xB
2xA + xB ≤ 800
max 4xA+ 5xB 2xA+ xB xA+ 2xB xB xA, xB
≤ 800 ≤700 ≤ 300 ≥0
xB ≤ 300
xA + 2xB ≤ 700
xA
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Repr ́esentation graphique
xB
2xA + xB ≤ 800
max 4xA+ 5xB 2xA+ xB xA+ 2xB xB xA, xB
≤ 800 ≤700 ≤ 300 ≥0
xB ≤ 300
xA + 2xB ≤ 700
xA
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Repr ́esentation graphique
xB
2xA + xB ≤ 800
max 4xA + 5xB 2xA+ xB xA+ 2xB xB xA, xB
≤ 800 ≤700 ≤ 300 ≥0
xB ≤300
xA + 2xB ≤ 700
xA
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Terminologie
xB
• Solution :
affectation de valeurs aux variables
• Solution r ́ealisable :
solution r ́ealisable si les valeurs satisfont l’ensemble des contraintes
• R ́egion r ́ealisable : ensemble des solutions r ́ealisables.
2xA + xB ≤ 800
x = (80, 150)
xB ≤300
xA + 2xB ≤ 700
xA
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Terminologie
xB
• Solution :
affectation de valeurs aux variables
• Solution r ́ealisable :
solution r ́ealisable si les valeurs satisfont l’ensemble des contraintes
• R ́egion r ́ealisable : ensemble des solutions r ́ealisables.
2xA + xB ≤ 800
xB ≤300
xA + 2xB ≤ 700
xA
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
R ́esolution graphique
xB
2xA + xB ≤ 800
Max 4xA+ 5xB 2xA+ xB xA+ 2xB xB xA, xB
≤ 800 ≤700 ≤ 300 ≥0
xB ≤300
xA + 2xB ≤ 700
xA
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
R ́esolution graphique
xB
Max 4xA+ 5xB 2xA+ xB xA+ 2xB xB xA, xB
≤ 800 ≤700 ≤ 300 ≥0
2xA + xB ≤ 800
xB ≤300 4xA + 5xB = 2900
xA + 2xB ≤ 700 4xA + 5xB = 2200
4xA + 5xB = 1000 xA 4xA + 5xB = 0
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
R ́esolution graphique
xB
Max 4xA+ 5xB 2xA+ xB xA+ 2xB xB xA, xB
≤ 800 ≤700 ≤ 300 ≥0
2xA + xB ≤ 800
xB ≤300 4xA + 5xB = 2900
xA + 2xB ≤ 700 4xA + 5xB = 2200
4xA + 5xB = 1000 xA 4xA + 5xB = 0
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
R ́esolution graphique
xB
Max 4xA+ 5xB 2xA+ xB xA+ 2xB xB xA, xB
≤ 800 ≤700 ≤ 300 ≥0
2xA + xB ≤ 800
xB ≤300 4xA + 5xB = 2900
xA + 2xB ≤ 700 4xA + 5xB = 2200
4xA + 5xB = 1000 xA 4xA + 5xB = 0
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
R ́esolution graphique
xB
Max 4xA+ 5xB 2xA+ xB xA+ 2xB xB xA, xB
≤ 800 ≤700 ≤ 300 ≥0
2xA + xB ≤ 800
xB ≤300 4xA + 5xB = 2900
xA + 2xB ≤ 700 4xA + 5xB = 2200
4xA + 5xB = 1000 xA 4xA + 5xB = 0
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Existence d’une solution (optimale)
Quatre possibilit ́es
min x + 2y s.t. x ≤ 5 x+y≥3 x,y ≥0
Une solution optimale unique.
✻
✲x
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Quatre possibilit ́es
max x + 2y s.t. x ≤ 5 x+y≥3 x,y ≥0
Solution non born ́ee.
y
Existence d’une solution (optimale)
✲x
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Quatre possibilit ́es
max x + 2y s.t. x ≤ 5 x+y≥3 x + y ≤ −1 x,y ≥0
Pas de solution.
Existence d’une solution (optimale)
✲x
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Quatre possibilit ́es
max x s.t. x ≤ 5 x+y≥3 x,y ≥0
Infinit ́e de solutions.
Existence d’une solution (optimale)
✲x
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Introduction par l’exemple Programme lin ́eaire R ́esolution graphique
Points extrˆemes
Points extrˆemes et convexit ́e Algorithme g ́eom`etrique
Forme standard, bases Bilan
Sommaire
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Notion de point extrˆeme
xB
Proposition
S’il en existe, il y a toujours une solution optimale sur un sommet (point extrˆeme) de la r ́egion r
́ealisable
Corollaire
Pour trouver l’optimum, il ”suffit” d’examiner les points extrˆemes de la r ́egion r ́ealisable
2xA + xB ≤ 800
xB ≤300 4xA + 5xB = 2900
xA + 2xB ≤ 700 4xA + 5xB = 2200
4xA + 5xB = 1000 xA 4xA + 5xB = 0
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Poly`edres et points extrˆemes (1)
D ́efinition
Un poly`edre convexe est l’ensemble des solutions d’un syst`eme fini d’in ́egalit ́es lin ́eaires.
L’ensemble des solutions admissibles d’un PL est donc un poly`edre convexe.
On s’int ́eressera dans un premier temps aux poly`edres born ́es.
Rappel : S est convexe si
∀x, y ∈ S , ∀λ ∈ [0, 1], λx + (1 − λ)y ∈ S .
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Poly`edres et points extrˆemes (2)
D ́efinition
Un point x0 d’un ensemble convexe S est un point extrˆeme de S s’il n’existe pas deux points x1, x2 ∈
S t.q. x = λx1 + (1 − λx2).
Th ́eor`eme
Soit S un ensemble convexe born ́e de Rn et Se l’ensemble de ses points extrˆemes. Si x ∈ S alors x
peut s’ ́ecrire comme une combinaison convexe de n + 1 ́el ́ements de S e .
Rappel : soit x, y, z ∈ Rn. Si x = λy + (1 − λ)z alors pour tout a ∈ Rn, ax ≤ max{ay, az}.
Th ́eor`eme
Si le poly`edre form ́e par l’ensemble des solutions d’un PL est born ́e, alors il existe au moins une
solution optimale et l’une d’elles est obtenue sur un point extrˆeme.
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
1. Partir d’un point extrˆeme x de la r ́egion r ́ealisable
xB
Algorithme g ́eom ́etrique
4xA + 5xB = 0
xA
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
1. Partir d’un point extrˆeme x de la r ́egion r ́ealisable
2. D ́eterminer une arˆete le long de laquelle l’objectif augmente. S’il n’en existe pas, x est
optimal, STOP
xB
Algorithme g ́eom ́etrique
4xA + 5xB = 0
xA
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
1. Partir d’un point extrˆeme x de la r ́egion r ́ealisable
2. D ́eterminer une arˆete le long de laquelle l’objectif augmente. S’il n’en existe pas, x est
optimal, STOP
3. Se d ́eplacer le long de l’arˆete jusqu’au point extrˆeme y suivant.
S’il n’existe pas, le probl`eme est non born ́e, STOP
Sinon, poser x ← y et revenir en 2
xB
Algorithme g ́eom ́etrique
4xA +5xB = 0
xA
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
1. Partir d’un point extrˆeme x de la r ́egion r ́ealisable
2. D ́eterminer une arˆete le long de laquelle l’objectif augmente. S’il n’en existe pas, x est
optimal, STOP
3. Se d ́eplacer le long de l’arˆete jusqu’au point extrˆeme y suivant.
S’il n’existe pas, le probl`eme est non born ́e, STOP
Sinon, poser x ← y et revenir en 2
xB
Algorithme g ́eom ́etrique
4xA +5xB = 0
xA
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Algorithme g ́eom ́etrique
1. Partir d’un point extrˆeme x de xB la r ́egion r ́ealisable
2. D ́eterminer une arˆete le long de laquelle l’objectif augmente. S’il n’en existe pas, x est
optimal, STOP
3. Se d ́eplacer le long de l’arˆete jusqu’au point extrˆeme y suivant.
S’il n’existe pas, le probl`eme est non born ́e, STOP
Sinon, poser x ← y et revenir en 2
xA 4xA + 5xB = 1500
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Algorithme g ́eom ́etrique
1. Partir d’un point extrˆeme x de xB la r ́egion r ́ealisable
2. D ́eterminer une arˆete le long de laquelle l’objectif augmente. S’il n’en existe pas, x est
optimal, STOP
3. Se d ́eplacer le long de l’arˆete jusqu’au point extrˆeme y suivant.
S’il n’existe pas, le probl`eme est non born ́e, STOP
Sinon, poser x ← y et revenir en 2
xA 4xA + 5xB = 1500
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
1. Partir d’un point extrˆeme x de xB la r ́egion r ́ealisable
2. D ́eterminer une arˆete le long de laquelle l’objectif augmente. S’il n’en existe pas, x est
optimal, STOP
3. Se d ́eplacer le long de l’arˆete jusqu’au point extrˆeme y suivant.
S’il n’existe pas, le probl`eme est non born ́e, STOP
Sinon, poser x ← y et revenir en 2
Algorithme g ́eom ́etrique
4xA + 5xB = 1900 xA
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
1. Partir d’un point extrˆeme x de xB la r ́egion r ́ealisable
2. D ́eterminer une arˆete le long de laquelle l’objectif augmente. S’il n’en existe pas, x est
optimal, STOP
3. Se d ́eplacer le long de l’arˆete jusqu’au point extrˆeme y suivant.
S’il n’existe pas, le probl`eme est non born ́e, STOP
Sinon, poser x ← y et revenir en 2
Algorithme g ́eom ́etrique
4xA + 5xB = 1900 xA
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Algorithme g ́eom ́etrique
1. Partir d’un point extrˆeme x de xB la r ́egion r ́ealisable
2. D ́eterminer une arˆete le long de laquelle l’objectif augmente. S’il n’en existe pas, x est
optimal, STOP
3. Se d ́eplacer le long de l’arˆete jusqu’au point extrˆeme y suivant.
S’il n’existe pas, le probl`eme est non born ́e, STOP
Sinon, poser x ← y et revenir en 2
4xA + 5xB = 2200
xA
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
1. Partir d’un point extrˆeme x de la r ́egion r ́ealisable
2. D ́eterminer une arˆete le long de laquelle l’objectif augmente. S’il n’en existe pas, x est
optimal, STOP
3. Se d ́eplacer le long de l’arˆete jusqu’au point extrˆeme y suivant.
S’il n’existe pas, le probl`eme est non born ́e, STOP
Sinon, poser x ← y et revenir en 2
xB
Algorithme g ́eom ́etrique
4xA + 5xB = 2200
xA
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Introduction par l’exemple Programme lin ́eaire R ́esolution graphique Points extrˆemes
Forme standard, bases
Bilan
Sommaire
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Forme standard
Jusqu’a` pr ́esent on a utilis ́e la forme normale pour repr ́esenter un programme lin ́eaire.
On introduit la forme standard qui va ˆetre utilis ́ee dans l’algorithme du simplex.
maxz =4x1 +5y1 2x1 + x2
x1 + 2x2 − x2
x1,x2
≤ 4 ≤ 10 ≤ −2 ≥0
maxz =4x1 +5x2 2x1 + x2
x1 + 2x2 − x2
x1,x2,
+0s1 +0s2 +s1
+ s2 s1,s2,
+0s3
=4
= 10 +s3 = −2
s3 ≥0
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Forme standard
A` partir de tout PL sous forme normale, on peut construire un PL sous forme standard
n maxz = cixi
i=1
n
max z = ci xi
i=1
n
aij xi + sj = bj (j = 1, . . . , m) i=1
xi ≥0(i =1,...,n) sj ≥0(i =1,...,m)
n
aijxi ≤ bj(j = 1,...,m)
i=1
xi ≥0(i =1,...,n)
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Interpr ́etation de la forme standard
Les variables suppl ́ementaires si sont appel ́ees variables d’ ́ecart. Chaque variable d’ ́ecart est associ
́ee a` une contrainte.
max5x +y x+y≤10
max5x +y
x+y +s1
x−y
x x,y,
=10
= 1 +s3 = 3 s3 ≥0
x − y ≤ 1 x ≤ 3 x,y ≥0
+ s2
s1,s2,
Quand s1 = 0, la contrainte x + x ≤ 10 est v ́erifi ́ee a` l’ ́egalit ́e.
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Forme standard et points extrˆemes
max 5x + y x + y + s1 = 10 x − y + s2 = 1 x + s3 = 3 x,y,s1,s2,s3 ≥0
y
E
✻
Points extrˆemes : intersection d’hyperplans (contraintes)
x = 0, y = 0 : A x = 0, s2 = 0 : B s2 = 0, s3 = 0 : C s1 = 0, s3 = 0 : D y = 0, s1 = 0 : E
AB
✲x
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Interpr ́etation de la forme standard
max 5x + y x + y + s1 = 10 x − y + s2 = 1 x + s3 = 3 x,y,s1,s2,s3≥0
y
E
✻
Si on annule s2 et s3, il reste ce syst`eme qui a pour solution
x = 3, y = 3, s1 = 4
x + y + s1 = 10 x−y=0 x = 3 (x,y,s1 ≥0)
AB
✲x
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Sommets = bases
On dispose d’un PL a` n + m variables et m contraintes.
Si on annule n variables, on obtient un syst`eme de m
́ equations a` m inconnues
Si la matrice associ ́ee est de rang m (base), le syst`eme admet
une solution unique
Une base = une solution
Pour r ́esoudre le probl`eme obtenu : pivot de Gauss !
Attention : si la solution n’a pas des valeurs positives, elle n’est pas valide !
Exemples
Programme lin ́eaire
R ́esolution graphique Points extrˆemes
Forme standard, bases
Bilan
max 5x + y x + y + s1 = 10 x − y + s2 = 1 x + s3 = 3 x,y,s1,s2,s3≥0
Base non r ́ealisable
y
E
✻
C
y = 0, s1 = 0
Solution x = 10, s2 = −9, s3 = −3, non valide !
AB
✲x
x = 10
x + s2 = 1
x + s3 = 3 (x,s2,s3 ≥0)
Exemples
Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Id ́ee de r ́esolution
• Si on a une base r ́ealisable, on a un point extrˆeme = une solution dominante
• Pour calculer les valeurs des variables pour ces points : pivot de Gauss
Il reste `a voir
• comment trouver une premi`ere base r ́ealisable
• comment passer d’une base r ́ealisable a` une autre
Exemples Programme lin ́eaire R ́esolution graphique Points extrˆemes Forme standard, bases Bilan
Introduction par l’exemple Programme lin ́eaire R ́esolution graphique Points extrˆemes
Forme standard, bases
Bilan
Sommaire