[PDF] Programmation Linéaire Cours 1 : programmes linéaires





Previous PDF Next PDF



LES ÉTAPES DE LALGORITHME DU SIMPLEXE

Un programme linéaire (PL) mis sous la forme particulière où toutes les contraintes sont des équations et toutes les variables sont non négatives est dit sous 



Chapitre 3 Méthode du simplexe

Le principe de la méthode du simplexe est d'éviter de calculer tous les du système augmenté obtenu en ajoutant au système Ax = b la relation linéaire.



Méthode du simplexe

implantation de l'algorithme du simplexe méthode révisée du simplexe (relation entre deux Si un problème de programmation linéaire admet au moins une.



1 Programmation linéaire Algorithme du simplexe Résolution de

Si oui donner la solution optimale de (P) et son coût. Page 3. 3. Corrigé. Résolution de programmes linéaires par la méthode des tableaux du simplexe.



Programmation linéaire. Méthode du simplexe.

25 oct. 2010 Un programme linéaire est la maximisation ou la minimisation d'une fonction linéaire sous des contraintes linéaires. 2.1 Exemple. Voici un petit ...



Leçon 0603C La programmation linéaire 2 le simplexe

Lorsque nous sommes en présence de plus de deux produits la méthode du simplexe est la seule méthode permettant de trouver la combinaison de produits qui rend 



Programmation Linéaire Cours 1 : programmes linéaires

C. Prins et M. Sevaux - Programmation linéaire avec Excel : 55 Prochain cours. • Méthode pour résoudre les probl`emes linéaires : le simplex.



1 Programmation linéaire

Document 4 : Corrigé des exercices d'optimisation linéaire. 1 Programmation linéaire Le tableau de départ pour la méthode du simplexe est donc :.



Programmation Linéaire - Cours 2

réels : la programmation linéaire Apprendre la méthode du simplex. • Comprendre son fonctionnement ... Méthode du dictionnaire - version générique.



LA PROGRAMMATION LINEAIRE : RESOLUTION ANALYTIQUE

La programmation linéaire : Résolution analytique La méthode que nous venons d'utiliser est l'algorithme du simplexe du à Dantzig (1947).



Chapitre 3 Méthode du simplexe - Université Laval

Méthode du simplexe CommetoujoursonsupposequeA unematricedeformatm n etb 2Rm Onnoterales colonnesdeA par[a 1;a 2;:::;a n] Aussionferal’hypothèsequelerangdelamatriceA est égalàm Selonlechapitreprécédentnoussavonsquelasolutionoptimaleduproblèmed’optimisation linéaire max z = ctx; Ax = b; x 0: (3 1)



Module 06 - Leçon 03 : La méthode du simplexe

Avant que l’algorithme du simplexe puisse être utilisé pour résoudre un programme linéaire ce programme linéaire doit être converti en un programme équivalent où toutes les contraintes technologiques sont des équations et toutes les variables sont non négatives a Contraintes de type



1 INTRODUCTION 2 AJOUT DES VARIABLES ARTIFICIELLES 3 L

base réalisable au modèle de programmation linéaire 3 L’ALGORITHME DU SIMPLEXE EN DEUX PHASES: La méthode des deux phases consiste à segmenter l’algorithme du simplexe en deux étapes La première étape dite Phase 1 consiste à éliminer les variables artificielles de la base (ou au moins à les rendre nulles)



Programmation linéaire Algorithme du simplexe Résolution de

Programmation linéaire Algorithme du simplexe Résolution de programmes linéaires par la méthode des tableaux du simplexe Soit le programme linéaire : max????=2????1+????2 Sous les contraintes x 1 0 x 2 0 et {????1?????2?3 ????1+22?6 ?????1+2????2?2 1-Rajouter les variables d’écart (positives ou nulles)

Qu'est-ce que la méthode du simplexe?

1 - Principe Lorsque nous sommes en présence de plus de deux produits, la méthode du simplexe est la seule méthode permettant de trouver la combinaison de produits qui rend optimal la fonction économique.

Comment fonctionne l’algorithme du simplexe ?

L’algorithme du simplexe est mis en œuvre selon deux méthodes, la méthode des dictionnaires et la méthode des tableaux. La première méthode permet de bien comprendre le déroulement du simplexe alors que la méthode des tableaux est plus algébrique et elle conduit à la mise en œuvre effective de l’algorithme du simplexe.

Qui a inventé le simplexe ?

Ce terme a été introduit pendant la Seconde Guerre mondiale et systématiquement utilisé à partir de 1947 lorsque G. Dantzig inventa la méthode du simplexe pour résoudre les problèmes de programmation linéaire.

Comment résoudre un programme linéaire ?

Cet article présente les propriétés et les concepts fondamentaux de la programmation linéaire puis expose l’algorithme du simplexe pour résoudre un programme linéaire. L’algorithme du simplexe est mis en œuvre selon deux méthodes, la méthode des dictionnaires et la méthode des tableaux.

Programmation Linéaire Cours 1 : programmes linéaires 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

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

Notion de point extrˆeme

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 x

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

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

Poly`edres et points extrˆemes (1)

D´efinition

Unpoly`edre convexeest 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`edresborn´es.

Rappel : S est convexe si

?x,y?S,?λ?[0,1],λx+ (1-λ)y?S. ExemplesProgramme lin´eaireR´esolution graphiquePoints extrˆemesForme standard, basesBilanquotesdbs_dbs33.pdfusesText_39
[PDF] programmation linéaire recherche opérationnelle

[PDF] interprétation droite de henry

[PDF] principe droite de henry

[PDF] exercice corrigé droite de henry

[PDF] courbe de henry excel

[PDF] droite de henry pdf

[PDF] programmation linéaire exercices corrigés pdf

[PDF] programmation linéaire exercices corrigés

[PDF] programmation linéaire simplexe

[PDF] recherche opérationnelle programmation linéaire exercices corrigés pdf

[PDF] exercices recherche operationnelle

[PDF] theme astral chinois complet gratuit interpretation

[PDF] cours recherche opérationnelle methode de simplexe

[PDF] recherche opérationnelle simplexe exercices corrigés

[PDF] livre recherche opérationnelle pdf