Programmation Lin ́eaire

Programmation Lin ́eaire
Cours 1 : programmes lin ́eaires, mod ́elisation et r ́esolution graphique

F. Clautiaux
francois.clautiaux@math.u-bordeaux1.fr
Universit ́e Bordeaux 1 Baˆt A33
Exemples Programme lin ́eaire R ́esolution graphique Points extrêmes 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èmes d’optimisation. Existence de solveurs efficace pour la PL

Exemples
Programme lin ́eaire R ́esolution graphique Points extrêmes Forme standard, bases Bilan
Ouvrages de r ́ef ́erence

 V. Chv ́atal - Linear Programming, W.H.Freeman, 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èmes 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èmes d’optimisation mod ́elis ́es
pas à pas et r ́esolus avec Excel, Eyrolles, 2011.
Introduction par l’exemple
Exemple 1 : Production Exemple 2 : Transport Exemple 3 : Planification
Sommaire
Problème 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ères premières.
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.

• Sur quelles quantit ́es peut-on travailler ? • Que cherche-t-on a` optimiser ?

• Quelles sont les contraintes du problème ?
Mod ́elisation
Exemples
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 ?

Exemples
• Sur quelles quantit ́es peut-on travailler ? • Variables : xA et xB
• Que cherche-t-on a` optimiser ? • Le profit z
• Calcul ́e à partir de xA et xB • On parle de fonction objectif • z=4xA+5xB
Mod ́elisation
Exemples
Mod ́elisation
• Que cherche-t-on a` optimiser ? • maxz=4xA+5xB
• Première contrainte : 800 Kg de fraises disponibles

• la quantit ́e utilis ́ee d ́epend de la production : 2xA + xB • 2xA + xB ≤ 800
Exemples
Mod ́elisation
2xA+ xB xA+ 2xB
≤ 800
(fraises) (lait) (sucre)
≤ 700 xB ≤ 300
Exemples
Mod ́elisation
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
Mon premier programme lin ́eaire

max4xA+ 5xB
2xA+ xB ≤ 800
xA+ 2xB ≤700 xB ≤ 300
xA, xB ≥0
Problème 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
• Variables :
xi,j : quantit ́e transport ́ee de i a` j
Mod ́elisation
Exemples
• Variables :
• Objectif :
􏰁 􏰁
Minimiser i∈I j∈J ci,jxi,j
Mod ́elisation
Exemples
• Variables :
• 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
Problème 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
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
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
Programme lin ́eaire
R ́esolution graphique Points extrêmes Forme standard, bases Bilan
Sommaire
Règles 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ème de minimisation peut s’ ́ecrire comme un problème
de maximisation :
􏰂 􏰂
nn max cixi ≡ min −cixi
i=1 i=1
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
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
Exemples simples de programmes non lin ́eaires (2)

􏰁n
min i=1c ix i
􏰁n
xi ∈R∩[l1,u1]∩[l2,u2],(i =1,...,n)
􏰁n
min i=1c ix i
􏰁n
x1 = x2 ou x1 = x3 xi ∈ R,(i = 1,...,n)
Forme normale d’un programme lin ́eaire

Tout programme lin ́eaire peut s’ ́ecrire sous forme normale.
􏰁n
max i=1c ix i
􏰁n
xi ≥ 0,xi ∈ R,(i = 1,...,n)
+ − + −
Sionaunevariablexi ∈R,onintroduitxi ≥0etxi ≥0eton pose xi = xi + xi .
R ́esolution graphique
Repr ́esentation graphique d’un PL R ́esolution graphique
Points extrêmes Forme standard, bases Bilan
Sommaire
Exemples
• On dispose d’un outil (la PL) pour mod ́eliser des problèmes • Comment r ́esoudre les problèmes a`
l’aide de la PL ?
• Plusieurs algorithmes existent, dont le simplexe (prochain cours)
• Pour des problèmes avec deux variables, on peut r ́esoudre graphiquement (aide à comprendre la structure du
problème)
Exemples
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

xB
2xA + xB ≤ 800
≤ 800 ≤700 ≤ 300 ≥0
xB ≤ 300
xA + 2xB ≤ 700
xA
Exemples

xB
2xA + xB ≤ 800
≤ 800 ≤700 ≤ 300 ≥0
xB ≤ 300
xA + 2xB ≤ 700
xA
Exemples

xB
2xA + xB ≤ 800
max 4xA + 5xB 2xA+ xB xA+ 2xB xB xA, xB
≤ 800 ≤700 ≤ 300 ≥0
xB ≤300
xA + 2xB ≤ 700
xA
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
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
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
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
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
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
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

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
max x + 2y s.t. x ≤ 5 x+y≥3 x,y ≥0
Solution non born ́ee.

y
✲x
max x + 2y s.t. x ≤ 5 x+y≥3 x + y ≤ −1 x,y ≥0
Pas de solution.
✲x
max x s.t. x ≤ 5 x+y≥3 x,y ≥0
Infinit ́e de solutions.

✲x
Introduction par l’exemple Programme lin ́eaire R ́esolution graphique
Points extrêmes
Points extrêmes et convexit ́e Algorithme g ́eomètrique

Forme standard, bases Bilan
Sommaire
Notion de point extrême

xB
Proposition
S’il en existe, il y a toujours une solution optimale sur un sommet (point extrême) de la r ́egion r
́ealisable
Corollaire
Pour trouver l’optimum, il ”suffit” d’examiner les points extrêmes 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

Polyèdres et points extrêmes (1)
D ́efinition
Un polyèdre convexe est l’ensemble des solutions d’un système fini d’in ́egalit ́es lin ́eaires.
L’ensemble des solutions admissibles d’un PL est donc un polyèdre convexe.

On s’int ́eressera dans un premier temps aux polyèdres born ́es.
Rappel : S est convexe si

∀x, y ∈ S , ∀λ ∈ [0, 1], λx + (1 − λ)y ∈ S .
Polyèdres et points extrêmes (2)
D ́efinition
Un point x0 d’un ensemble convexe S est un point extrême de S s’il n’existe pas deux points x1, x2 ∈
S t.q. x = λx1 + (1 − λx2).
Th ́eorème
Soit S un ensemble convexe born ́e de Rn et Se l’ensemble de ses points extrêmes. 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ème
Si le polyèdre 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ême.
1. Partir d’un point extrême x de la r ́egion r ́ealisable
xB
Algorithme g ́eom ́etrique

􏰄􏰃
4xA + 5xB = 0
xA

2. D ́eterminer une arête le long de laquelle l’objectif augmente. S’il n’en existe pas, x est
optimal, STOP
xB

􏰃􏰄
4xA + 5xB = 0
xA

optimal, STOP
3. Se d ́eplacer le long de l’arête jusqu’au point extrême y suivant.
S’il n’existe pas, le problème est non born ́e, STOP
Sinon, poser x ← y et revenir en 2
xB

􏰄􏰃
4xA +5xB = 0
xA

optimal, STOP
xB

􏰄􏰃
4xA +5xB = 0
xA

1. Partir d’un point extrême x de xB la r ́egion r ́ealisable
optimal, STOP
􏰄􏰃 􏰃􏰄
xA 4xA + 5xB = 1500


optimal, STOP
􏰄􏰃 􏰃􏰄
xA 4xA + 5xB = 1500


optimal, STOP
􏰄􏰃 􏰄􏰃 􏰄􏰃 􏰃􏰄

4xA + 5xB = 1900 xA

optimal, STOP
􏰄􏰃 􏰄􏰃 􏰄􏰃 􏰃􏰄
4xA + 5xB = 1900 xA


optimal, STOP

􏰃􏰄 􏰃􏰄4xA + 5xB = 2200 􏰃􏰄 􏰄􏰃
xA

optimal, STOP
xB

􏰃􏰄 􏰃􏰄4xA + 5xB = 2200 􏰄􏰃 􏰃􏰄
xA
Introduction par l’exemple Programme lin ́eaire R ́esolution graphique Points extrêmes
Forme standard, bases
Bilan
Sommaire
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 être 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
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)
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
Forme standard et points extrêmes
max 5x + y x + y + s1 = 10 x − y + s2 = 1 x + s3 = 3 x,y,s1,s2,s3 ≥0
y
E
✻
Points extrêmes : 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
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ème 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
Sommets = bases
 On dispose d’un PL a` n + m variables et m contraintes.
 Si on annule n variables, on obtient un système de m
́ equations a` m inconnues
 Si la matrice associ ́ee est de rang m (base), le système admet
une solution unique
 Une base = une solution

 Pour r ́esoudre le problème obtenu : pivot de Gauss !
 Attention : si la solution n’a pas des valeurs positives, elle n’est pas valide !
Exemples
R ́esolution graphique Points extrêmes
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
Id ́ee de r ́esolution
• Si on a une base r ́ealisable, on a un point extrême = une solution dominante
• Pour calculer les valeurs des variables pour ces points : pivot de Gauss
Il reste à voir
• comment trouver une première base r ́ealisable
• comment passer d’une base r ́ealisable a` une autre
Introduction par l’exemple Programme lin ́eaire R ́esolution graphique Points extrêmes
Bilan
Sommaire

Programmation Lin ́eaire

Transféré par

Informations du documentcliquez pour développer les informations du document

Informations du documentcliquez pour développer les informations du document

Droits d'auteur :

Formats disponibles

Programmation Lin ́eaire

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Programmation Lin ́eaire

Transféré par

Droits d'auteur :

Formats disponibles

Programmation Lin ́eaire

Cours 1 : programmes lin ́eaires, mod ́elisation et r ́esolution graphique

Universit ́e Bordeaux 1 Baˆt A33

Motivation et objectif du cours

toute une classe de probl`emes d’optimisation. Existence de solveurs efficace pour la PL

Ouvrages de r ́ef ́erence

Introduction par l’exemple

Exemple 1 : Production Exemple 2 : Transport Exemple 3 : Planification

On dispose de 800 Kg de Fraises, 700 Kg de Lait et 300 Kg de sucre.

Le fabricant cherche a` maximiser son profit.

• Sur quelles quantit ́es peut-on travailler ? • Que cherche-t-on a` optimiser ?

• 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 ?

• 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 ?

• Que cherche-t-on a` optimiser ? • maxz=4xA+5xB

• Quelles sont les contraintes du probl`eme ?

• Premi`ere contrainte : 800 Kg de fraises disponibles

• Que cherche-t-on a` optimiser ? • maxz=4xA+5xB

• Quelles sont les contraintes du probl`eme ?

2xA+ xB xA+ 2xB

(fraises) (lait) (sucre)

• 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)

Mon premier programme lin ́eaire

xA+ 2xB ≤700 xB ≤ 300

Usines (i ∈ I) Bordeaux Biarritz Toulouse

∀i ∈ I (Capacit ́e de production) ∀j ∈ J (Demandes a` satisfaire) ∀i∈I,j∈J

mois 1 mois 2 mois 3 mois 4 Demandes 900 1100 1700 1300

x1+ x2+ x3+ x4+

900+ s1 1100+ s2 1700+ s3

Introduction par l’exemple

Programme lin ́eaire

R ́esolution graphique Points extrˆemes Forme standard, bases Bilan

R`egles de r ́e ́ecriture (1)

Ecriture g ́en ́erale d’un programmation lin ́eaire

Exemples simples de programmes non lin ́eaires (1)

m i n sous les contraintes

Exemples simples de programmes non lin ́eaires (2)

Forme normale d’un programme lin ́eaire

xi ≥ 0,xi ∈ R,(i = 1,...,n)

Introduction par l’exemple

Programme lin ́eaire

Repr ́esentation graphique d’un PL R ́esolution graphique

Points extrˆemes Forme standard, bases Bilan

• Plusieurs algorithmes existent, dont le simplexe (prochain cours)

Repr ́esentation graphique

≤ 800 ≤700 ≤ 300 ≥0

Repr ́esentation graphique

≤ 800 ≤700 ≤ 300 ≥0

Repr ́esentation graphique

≤ 800 ≤700 ≤ 300 ≥0