[PDF] programmes linéaires modélisation et résolution graphique

View - Download programmes linéaires modélisation et résolution graphique

Previous PDF

Next PDF

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

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

Bˆat A33

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

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

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

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`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.

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Sommaire

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 ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

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

Fraise21

Lait12

Sucre01

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 4eet 5e.

Le fabricant cherche `a maximiser son profit.

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Que cherche-t-on `a optimiser? •Quelles sont les contraintes du probl`eme? ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Seules valeurs non constantes : les quantit´es de yaourtsAetB produites •On parle devariables •On les noteraxAetxB •Que cherche-t-on `a optimiser? •Quelles sont les contraintes du probl`eme? ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •Que cherche-t-on `a optimiser? •Le profitz •Calcul´e `a partir dexAetxB •On parle defonction objectif •z= 4xA+ 5xB •Quelles sont les contraintes du probl`eme? ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •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 ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •Que cherche-t-on `a optimiser? •maxz= 4xA+ 5xB •Quelles sont les contraintes du probl`eme? x x ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Sur quelles quantit´es peut-on travailler?

•Variables :xAetxB •Que cherche-t-on `a optimiser? •maxz= 4xA+ 5xB •Quelles sont les contraintes du probl`eme? x x x

A,xB≥0

positivit´e! ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mon premier programme lin´eaire

max4xA+ 5xB x x x

A,xB≥0

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Probl`eme de transport

Approvisionner au moindre coˆut les clients `a partir des usines.

Usines (i?I)BordeauxBiarritzToulouse

Productions (pi)251520

Clients (j?J)PauBayonneBordeauxLibourne

Demandes (dj)2012914

Prix/unit´e (ci,j)PauBayonneBordeauxLibourne

Bordeaux261904

Biarritz1222024

Toulouse19302428

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x i,j: quantit´e transport´ee dei`aj ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x i,j: quantit´e transport´ee dei`aj •Objectif :

Minimiser?

i?I? j?Jci,jxi,j ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x i,j: quantit´e transport´ee dei`aj •Objectif :

Minimiser?

i?I? j?Jci,jxi,j •Contraintes :? i?Ixi,j=dj,?j?J(Demandes `a satisfaire) x i,j≥0,?i?I,j?J ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Probl`eme de planification

Planifier la production d"articles `a moindre coˆut pour les 4 prochains mois. Production maximale normale : 1200 articles / mois Production maximale en heure sup : 400 articles / mois

Surcoˆut heures sup : 7 euros / article

Stockage : 3 euros / article / mois

mois 1mois 2mois 3mois 4

Demandes900110017001300

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x t: production normale en p´eriodet= 1,...,4 y t: production en heure sup en periodet= 1,...,4 s t: stock en fin de p´eriodet= 1,...,3 ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Mod´elisation

Variables :

x t: production normale en p´eriodet= 1,...,4 y t: production en heure sup en periodet= 1,...,4 s t: stock en fin de p´eriodet= 1,...,3 •Objectif :

Minimiser 7?t=4

t=1yt+ 3?t=3 t=1st •Contraintes : x

1+y1= 900+s1

s

1+x2+y2= 1100+s2

s

2+x3+y3= 1700+s3

s

3+x4+y4= 1300

s t≥0,t= 1, ...,3 ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Sommaire

Introduction par l"exemple

Programme lin´eaire

R´esolution graphique

Points extrˆemes

Forme standard, bases

Bilan ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

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

Toute contrainte d"´egalit´e peut s"´ecrire comme deux in´egalit´es : n i=1a ixi=b≡? n i=1a ixi≥b≡n? Tout probl`eme de minimisation peut s"´ecrire comme un probl`eme de maximisation : max n? i=1c ixi≡minn? i=1-cixi ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan Ecriture g´en´erale d"un programmation lin´eaire On peut ´ecrire ainsi un programme lin´eaire avecnvariables x

1,...,xnetmcontraintes.

max ?ni=1cixi x i?R,(i= 1,...,n) •Lin´earit´e :Objectif et contraintes sont des fonctions lin´eaires des variables de d´ecision (les coefficientscietaijdes variables sont constants) •Continuit´e :Les variables peuvent prendre n"importe quelle valeur r´eelle respectant les contraintes linaires ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan Exemples simples de programmes non lin´eaires (1) min?ni=1xixi x i?R,(i= 1,...,n) min ?ni=1xi x i?

N,(i= 1,...,n)

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan Exemples simples de programmes non lin´eaires (2) min?ni=1cixi x i?

R∩[l1,u1]∩[l2,u2],(i= 1,...,n)

min ?ni=1cixi x 1=x2 oux1=x3 x i?R,(i= 1,...,n) ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Forme normale d"un programme lin´eaire

Tout programme lin´eaire peut s"´ecrire sousforme normale. max ?ni=1cixi x i≥0,xi?R,(i= 1,...,n)

Si on a une variablexi?R, on introduitx+

i≥0 etx- i≥0 et on posexi=x+ i+x- i. ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Sommaire

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 ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

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´esoudregraphiquement (aide `a comprendre la structure du probl`eme)

ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Repr´esentation graphique

max 4xA+ 5xB x x x

A,xB≥0

x xAx B ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Repr´esentation graphique

max 4xA+ 5xB x x x

A,xB≥0

xAx B ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Repr´esentation graphique

max 4xA+ 5xB x x x xAx B x ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Repr´esentation graphique

max 4xA+ 5xB x x x

A,xB≥0

xAx B x ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Terminologie

Solution :

affectation de valeurs aux variables

•Solution r´ealisable :solution r´ealisable si les valeurssatisfont l"ensemble descontraintes

•R´egion r´ealisable :ensemble des solutionsr´ealisables. xAx B x x= (80,150) ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Terminologie

Solution :

affectation de valeurs aux variables

•Solution r´ealisable :solution r´ealisable si les valeurssatisfont l"ensemble descontraintes

•R´egion r´ealisable :ensemble des solutionsr´ealisables. xAx B x ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

R´esolution graphique

Max 4xA+ 5xB

x x x

A,xB≥0

xAx B x ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

R´esolution graphique

Max 4xA+ 5xB

x x x

A,xB≥0

x

4xA+ 5xB= 10004xA+ 5xB= 22004xA+ 5xB= 2900

4xA+ 5xB= 0x

Ax B ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

R´esolution graphique

Max 4xA+ 5xB

x x x

A,xB≥0

x

4xA+ 5xB= 22004xA+ 5xB= 2900

4xA+ 5xB= 04xA+ 5xB= 1000xAx

B ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

R´esolution graphique

Max 4xA+ 5xB

x x x

A,xB≥0

x

4xA+ 5xB= 2900

4xA+ 5xB= 04xA+ 5xB= 10004xA+ 5xB= 2200

x Ax B ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

R´esolution graphique

Max 4xA+ 5xB

x x x

A,xB≥0

x

4xA+ 5xB= 04xA+ 5xB= 10004xA+ 5xB= 22004xA+ 5xB= 2900

x Ax B ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Existence d"une solution (optimale)

Quatre possibilit´es

minx+ 2y x+y≥3 x,y≥0

Une solution optimale unique.

?x ?y ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Existence d"une solution (optimale)

Quatre possibilit´es

maxx+ 2y x+y≥3 x,y≥0

Solution non born´ee.

?x ?y ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Existence d"une solution (optimale)

Quatre possibilit´es

maxx+ 2y x+y≥3 x,y≥0

Pas de solution.

?x ?y ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Existence d"une solution (optimale)

Quatre possibilit´es

maxx x+y≥3 x,y≥0

Infinit´e de solutions.

?x ?y ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilan

Sommaire

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

Bilanquotesdbs_dbs47.pdfusesText_47

[PDF] méthode lecture syllabique télécharger

[PDF] méthode lettre anglais

[PDF] methode meaning

[PDF] methode merise pour les nuls

[PDF] methode nombre premier

[PDF] methode oral philo

[PDF] methode par balayage calculatrice casio

[PDF] méthode par combinaison

[PDF] Méthode par dichotomie (J'ai vraiment besoins d'aide)

[PDF] méthode par substitution exemple

[PDF] Méthode par substitution probleme du premier degre a une inconnue

[PDF] Methode par substitutions

[PDF] méthode physique chimie terminale s

[PDF] méthode pivot exercices résolus

[PDF] Méthode plan en philo