[PDF] Simplexe - Recherche Opérationnelle et Optimisation Master - LISIC

Programmation linéaire et recherche opérationnelle Recherche

[PDF] Programmation linéaire et recherche opérationnelle Recherche lim univ reunion staff fred Enseignement Optim doc PL pdf

Simplexe - Méthodes, Techniques et Outils pour le Raisonnement

[PDF] Simplexe Méthodes, Techniques et Outils pour le Raisonnementdossier univ st etienne pem public simplexeSlides pdf

Simplexe - Recherche Opérationnelle et Optimisation Master - LISIC

[PDF] Simplexe Recherche Opérationnelle et Optimisation Master LISIC lisic univ littoral ~verel TEACHING cours pdf

TP Recherche Opérationnelle Méthode du Simplexe - FSTM

[PDF] TP Recherche Opérationnelle Méthode du Simplexe FSTM fstm ac ma deptmath Taik TP RO pdf

Recherche opérationnelle Les démonstrations et les exemples

[PDF] Recherche opérationnelle Les démonstrations et les exemples fsr ac ma cours maths RO SMI Etudiants pdf

LES ÉTAPES DE L ALGORITHME DU SIMPLEXE

[PDF] LES ÉTAPES DE L 'ALGORITHME DU SIMPLEXE hec ca cam rubriques algorithme simplexe pdf

Optimisation linéaire Algorithme du simplexe Phase I

[PDF] Optimisation linéaire Algorithme du simplexe Phase Itransp or epfl ch courses RechOp slides PhaseI pdf

Recherche Opérationnelle - Chapitre 2 : Programmation linéaire

[PDF] Recherche Opérationnelle Chapitre Programmation linéaire tugaut perso math cnrs pdf enseignement RO CM pdf

Recherche opérationnelle et applications - SI Management

[PDF] Recherche opérationnelle et applications SI Management sietmanagement wp content uploads Cours ro pdf

PROGRAMMATION LINEAIRE

nov Recherche Opérationnelle Programmation linéaire ainsi que les indices des variables en base et hors base au cours des () Déterminer la solution optimale par la méthode du simplexe (utiliser les tableaux réduits de

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

[PDF] livre recherche opérationnelle pdf

[PDF] cours et exercices corrigés de recherche opérationnelle+pdf

[PDF] recherche opérationnelle cours maroc

[PDF] inpes

[PDF] methode boscher pdf download

[PDF] méthode boscher cahier de lecture pdf

[PDF] methode boscher en ligne

[PDF] méthode boscher gratuit

[PDF] méthode boscher cahier des sons pdf

[PDF] adjectif pour acrostiche

[PDF] recherche qualitative définition

[PDF] méthode qualitative et quantitative

[PDF] méthode qualitative mémoire

[PDF] méthode quantitative

Simplexe

Recherche Operationnelle et Optimisation

Master 1 I2L

S ebastien Verel verel@lisic.univ-littoral.fr http://www-lisic.univ-littoral.fr/ ~verel

Universite du Littoral C^ote d'Opale

Laboratoire LISIC

Equipe CAMOME

Base et points extr^emesAlgorithme du simplexe

Plan

1Base et points extr^emes

2Algorithme du simplexe

Base et points extr^emesAlgorithme du simplexe

Bibliographie

Cours de recherche operationnelle, Nadia Brauner, IMAG.

Base et points extr^emesAlgorithme du simplexe

Forme d'un probleme de prog. lin.

Forme normale

Max z=c:x

A xb x0 c= (ci)2IRn,x= (xi)2IRn,b= (bj)t2IRm,

A= (aij)2IRmn.Forme standard

Max z=c:x

A x=b x0 c= (ci)2IRn,x= (xi)2IRn,b= (bj)t2IRm,

A= (aij)2IRmn.

Base et points extr^emesAlgorithme du simplexe

Forme d'un probleme de prog. lin.

Forme normale

Max z=c:x

A xb x0 c= (ci)2IRn,x= (xi)2IRn,b= (bj)t2IRm,

A= (aij)2IRmn.Forme standard

Max z=c:x

A x=b x0 c= (ci)2IRn,x= (xi)2IRn,b= (bj)t2IRm,

A= (aij)2IRmn.

Base et points extr^emesAlgorithme du simplexe

Equivalence forme normale / forme standard

Exercice

Ecrire sous forme standard le systeme suivant :

Max z= 4x+ 5y

2x+y8 x+ 2y7 y3 x;y0

Base et points extr^emesAlgorithme du simplexe

Proprietes polytope

Proposition

Un polytope n'a qu'un nombre ni de sommets.

Tout pointMd'un polytope peut s'ecrire comme une combinaison lineaire convexe des sommets : M=X i iSi avec P ii= 1 eti0.

Base et points extr^emesAlgorithme du simplexe

Convexite

Ensemble convexe

Cest convexe ssi :

pour tous pointsMetM0deC, tout point du segment [M;M0] appartient aC pour tout2[0;1]

M+ (1)M02CFonction convexe

fest convexe ssi : pour toutxetx0deIRn, pour tout2[0;1] f(x+ (1)x0)f(x) + (1)f(x0)

Base et points extr^emesAlgorithme du simplexe

Maximums

Proposition

Une fonction convexefsur un polytopePa un maximum et celui-ci est est obtenu sur un sommet.Preuve : a faire Un algorithme serait donc d'enumererfsur les tous les sommets... mais qui peuvent ^etre tres nombreux...

Base et points extr^emesAlgorithme du simplexe

Solutions d'un probleme de prog. lin.

Forme normale

Max z=c:x

A xb x0 c= (ci)2IRn,x= (xi)2IRn,b= (bj)t2IRm, A= (aij)2IRmn.Les contraintes denissent le polyedre

La solution optimale est un sommet du polyedre

Comment enumerer les sommets?

Base et points extr^emesAlgorithme du simplexe

Base et points extr^emes

Version geometriqueExercice

A l'aide de la representation graphique du polyedre : enumerer les points interessants (points a l'intersection de contraintes)enumerer les sommets admissibles (points respectant les contraintes).

Base et points extr^emesAlgorithme du simplexe

Base et points extr^emes

Version algebrique8

>:2x+y+e1= 8 x+ 2y+e2+ = 7 y+ + +e3= 3 x;y;e1;e2;e30 Les solutions de base admissibles les intersections de contraintes (2 variables a 0).x ye1e2e3sol. base admiss.pt extr^eme

0 0 8 7 3ok ok(0;0):::

Base et points extr^emesAlgorithme du simplexe

Principe de resolution

Principe

Toute les methodes de resolution ont besoin d'au moins de calculer un point extr^eme : solution de baseliee a des variables de bases

Base et points extr^emesAlgorithme du simplexe

Bases et points extr^emes

Denition formelleSysteme lineaireAx=bAmatrice de dimensionmnet rangA=mnBase de la matriceAsous-matriceBde rangmdeA(n'est pas unique)

Bmatricemmavec detB6= 0PosonsA= (B N)

Ax=b,(B N)x=b,BxB+NxN=b

,xB=B1bB1NxNSolution de base associee aBx

N= 0 : variables hors basex

B=B1b: variables de baseProbleme : comment trouver une matriceB? etxB?

Base et points extr^emesAlgorithme du simplexe

Bases et points extr^emes

Denition formelleSysteme lineaireAx=bAmatrice de dimensionmnet rangA=mnBase de la matriceAsous-matriceBde rangmdeA(n'est pas unique)

Bmatricemmavec detB6= 0PosonsA= (B N)

Ax=b,(B N)x=b,BxB+NxN=b

,xB=B1bB1NxNSolution de base associee aBx

N= 0 : variables hors basex

B=B1b: variables de baseProbleme : comment trouver une matriceB? etxB?

Base et points extr^emesAlgorithme du simplexe

Exemple de calcul d'une base

8 >:2x+y+e1= 8 x+ 2y+e2= 7 y+e3= 3 x;y;e1;e2;e30

Pour trouver une base, en tenter une...

Par exemplefe1;e2;e3g

8< :2x+y+e1= 8 x+ 2y+e2= 7 y+e3= 3,8 :e

1= 82xy

e

2= 7x2y

e 3= 3y fe1;e2;e3g: variables de base etfx;ygvariables hors base

Base et points extr^emesAlgorithme du simplexe

Exemple de solution de base

fe1;e2;e3g: variables de base etfx;ygvariables hors base 8< :e

1= 82xy

e

2= 7x2y

e 3= 3y Pour calculer une solution de base :variables hors base = 0 variables de base a calculer (si possible, c'est ok)

Pourx=y= 0, on trouve :

8< :e

1= 82xy= 8

e

2= 7x2y= 7

e

3= 3y= 3

Base et points extr^emesAlgorithme du simplexe

Exemple de solution de base

fe1;e2;e3g: variables de base etfx;ygvariables hors base 8< :e

1= 82xy

e

2= 7x2y

e 3= 3y Pour calculer une solution de base :variables hors base = 0 variables de base a calculer (si possible, c'est ok)

Pourx=y= 0, on trouve :

8< :e

1= 82xy= 8

e

2= 7x2y= 7

e

3= 3y= 3

Base et points extr^emesAlgorithme du simplexe

Remarques nales

Ax=b,x0 ouA= (B N)(xB0) est est une solution de base admissible sixB0Equivalence points de vue geometrique / algebrique :

L'ensemble des points extr^emes du polyedre sont les solutions de base admissibles du syst. lin.Nombre de points extr^emes (maximum) : Solutions de base degeneres : lorsque certaines variables de base sont nullesPratique : lorsqueAest inversible, solution de base unique.

Base et points extr^emesAlgorithme du simplexe

Remarques nales

Ax=b,x0 ouA= (B N)(xB0) est est une solution de base admissible sixB0Equivalence points de vue geometrique / algebrique :

L'ensemble des points extr^emes du polyedre sont les solutions de base admissibles du syst. lin.Nombre de points extr^emes (maximum) : n mSolutions de base degeneres : lorsque certaines variables de base sont nullesPratique : lorsqueAest inversible, solution de base unique.

Base et points extr^emesAlgorithme du simplexe

Introduction

Une idee nave, simple mais impraticable :

Enumerer tous les sommets

Calculer l'objectif sur chacun eux

Retenir le meilleur

Cet algo termine et est correct (nombre ni), mais

malheureusement tres tres grand. Pourtant la geometrie du probleme joue en notre faveur...

Base et points extr^emesAlgorithme du simplexe

Introduction

Une idee nave, simple mais impraticable :

Enumerer tous les sommets

Calculer l'objectif sur chacun eux

Retenir le meilleur

Cet algo termine et est correct (nombre ni), mais

malheureusement tres tres grand. Pourtant la geometrie du probleme joue en notre faveur...

Base et points extr^emesAlgorithme du simplexe

Simplexe

Algorithme du simplexe

Dantzig, 1947

Algo iteratif de resolution de probleme de programmation lineairePrincipe A partir d'un sommet, chercher un sommet voisin qui ameliore l'objectif.Propriete du probleme Soitx0sommet non optimum. Alors il existex, un sommet voisin de x0, tel quef(x)>f(x0).Donc ca marche...

Base et points extr^emesAlgorithme du simplexe

Simplexe

Algorithme du simplexe

Dantzig, 1947

Algo iteratif de resolution de probleme de programmation lineairePrincipe A partir d'un sommet, chercher un sommet voisin qui ameliore l'objectif.Propriete du probleme Soitx0sommet non optimum. Alors il existex, un sommet voisin de x0, tel quef(x)>f(x0).Donc ca marche...

Base et points extr^emesAlgorithme du simplexe

Illustration

Max z= 4x+ 5y

2x+y8 x+ 2y7 y3 x;y0

A suivre sur votre graphique...x

0= (0;0) d'ouz= 0x

1= (0;3) d'ouz= 15x

2= (1;3) d'ouz= 19x

3= (3;2) d'ouz= 22

Base et points extr^emesAlgorithme du simplexe

Illustration

Max z= 4x+ 5y

2x+y8 x+ 2y7 y3 x;y0

A suivre sur votre graphique...x

0= (0;0) d'ouz= 0x

1= (0;3) d'ouz= 15x

2= (1;3) d'ouz= 19x

3= (3;2) d'ouz= 22

Base et points extr^emesAlgorithme du simplexe

Illustration

Max z= 4x+ 5y

2x+y8 x+ 2y7 y3 x;y0

A suivre sur votre graphique...x

0= (0;0) d'ouz= 0x

1= (0;3) d'ouz= 15x

2= (1;3) d'ouz= 19x

3= (3;2) d'ouz= 22

Base et points extr^emesAlgorithme du simplexe

Illustration

Max z= 4x+ 5y

2x+y8 x+ 2y7 y3 x;y0

A suivre sur votre graphique...x

0= (0;0) d'ouz= 0x

1= (0;3) d'ouz= 15x

2= (1;3) d'ouz= 19x

3= (3;2) d'ouz= 22

Base et points extr^emesAlgorithme du simplexe

Base voisine

Bases voisines

Deux sommets voisins correspondent a deux basesBetB0telles que qu'on remplace une variable deBpar une autre pour obtenir B

0.Passer d'un sommet a l'autre revient a changer de base (principe

du "pivotage")

Base et points extr^emesAlgorithme du simplexe

Algorithme du simplexe par l'exemple

Solution de base8

>>>:Maximizerz= 4x+ 5y 2x+y8 x+ 2y7 y3 x;y0,8 >>>:Maximizerz= 4x+ 5y

2x+y+e1= 8

x+ 2y+e2= 7 y+e3= 3 x;y;e1;e2;e30Pour trouver une base, en tenter une...

Par exemplefe1;e2;e3g

8< :2x+y+e1= 8 x+ 2y+e2= 7 y+e3= 3,8 :e

1= 82xy

e

2= 7x2y

e 3= 3y fe1;e2;e3g: variables de base etfx;ygvariables hors base

Base et points extr^emesAlgorithme du simplexe

Algorithme du simplexe par l'exemple

Solution de base8

>>>:Maximizerz= 4x+ 5y 2x+y8 x+ 2y7 y3 x;y0,8 >>>:Maximizerz= 4x+ 5y

2x+y+e1= 8

x+ 2y+e2= 7 y+e3= 3 x;y;e1;e2;e30Pour trouver une base, en tenter une...

Par exemplefe1;e2;e3g

8< :2x+y+e1= 8 x+ 2y+e2= 7 y+e3= 3,8 :e

1= 82xy

e

2= 7x2y

e 3= 3y fe1;e2;e3g: variables de base etfx;ygvariables hors base

Base et points extr^emesAlgorithme du simplexe

Algorithme du simplexe par l'exemple

Solution de basePour calculer une solution de base : variables hors base = 0 variables de base a calculer (si possible, c'est ok)

Valeur dez

fe1;e2;e3g: variables de base etfx;yg: variables hors basex=y= 0, on trouve : 8< :e

1= 82xy= 8

e

2= 7x2y= 7

e

3= 3y= 3

etz= 4x+ 5y= 0

Base et points extr^emesAlgorithme du simplexe

Algorithme du simplexe par l'exemple

Solution de basePour calculer une solution de base : variables hors base = 0 variables de base a calculer (si possible, c'est ok)

Valeur dez

fe1;e2;e3g: variables de base etfx;yg: variables hors basex=y= 0, on trouve : 8< :e

1= 82xy= 8

e

2= 7x2y= 7

e

3= 3y= 3

etz= 4x+ 5y= 0

Base et points extr^emesAlgorithme du simplexe

Changement de base

Regardons bien :z= 4x+ 5yOn peut faire augmenterzen faisant entrerxouydans la baseEssayonsy: quelle est la valeur maximale que pourra avoiry?

8< :e

1= 82xy0)y8

e

2= 7x2y0)y3:5

e

3= 3y0)y3Le max deyest 3, poury= 3, on obtenons

e

1= 5x,e2= 1xete3= 0.Nouvelle base candidate :

fe1;e2;e3g [ fyg n fe3g=fe1;e2;yg

Base et points extr^emesAlgorithme du simplexe

Changement de base

Regardons bien :z= 4x+ 5yOn peut faire augmenterzen faisant entrerxouydans la baseEssayonsy: quelle est la valeur maximale que pourra avoiry?

8< :e

1= 82xy0)y8

e

2= 7x2y0)y3:5

e

3= 3y0)y3Le max deyest 3, poury= 3, on obtenons

e

1= 5x,e2= 1xete3= 0.Nouvelle base candidate :

fe1;e2;e3g [ fyg n fe3g=fe1;e2;yg

Base et points extr^emesAlgorithme du simplexe

Changement de base

Regardons bien :z= 4x+ 5yOn peut faire augmenterzen faisant entrerxouydans la baseEssayonsy: quelle est la valeur maximale que pourra avoiry?

8< :e

1= 82xy0)y8

e

2= 7x2y0)y3:5

e

3= 3y0)y3Le max deyest 3, poury= 3, on obtenons

e

1= 5x,e2= 1xete3= 0.Nouvelle base candidate :

fe1;e2;e3g [ fyg n fe3g=fe1;e2;yg

Base et points extr^emesAlgorithme du simplexe

Changement de base

Regardons bien :z= 4x+ 5yOn peut faire augmenterzen faisant entrerxouydans la baseEssayonsy: quelle est la valeur maximale que pourra avoiry?

8< :e

1= 82xy0)y8

e

2= 7x2y0)y3:5

e

3= 3y0)y3Le max deyest 3, poury= 3, on obtenons

e

1= 5x,e2= 1xete3= 0.Nouvelle base candidate :

fe1;e2;e3g [ fyg n fe3g=fe1;e2;yg

Base et points extr^emesAlgorithme du simplexe

Changement de base

Regardons bien :z= 4x+ 5yOn peut faire augmenterzen faisant entrerxouydans la baseEssayonsy: quelle est la valeur maximale que pourra avoiry?

8< :e

1= 82xy0)y8

e

2= 7x2y0)y3:5

e

3= 3y0)y3Le max deyest 3, poury= 3, on obtenons

e

1= 5x,e2= 1xete3= 0.Nouvelle base candidate :

fe1;e2;e3g [ fyg n fe3g=fe1;e2;yg

Base et points extr^emesAlgorithme du simplexe

Nouvelle basefe1;e2;yg8

:e

1= 82xy

e

2= 7x2y

e

3= 3y,8

:e

1= 52x+e3

e

2= 1x+ 2e3

y= 3e3 zen fonction des variables hors base : z= 4x+ 5y= 15 + 4x5e3

Solution de base associee :

x=e3= 0 8< :e

1= 52x+e3= 5

e

2= 1x+ 2e3= 1

y= 3e3= 3 etz= 15.

Base et points extr^emesAlgorithme du simplexe

Nouvelle iteration

z= 15 + 4x5e3

Augmenter encorez?Faire entrerx

Quelle est la valeur maximale que pourra avoirx?8< :e

1= 52x+e30)x2:5

e

2= 1x+ 2e30)x1

y= 3e30)pas de contrainteLe max dexest 1, ete2peut sortir de la baseNouvelle base candidate :fe1;x;yg8>><

>:e

1= 3 + 2e23e3

x= 1e2+ 2e3 y= 3e3 z= 194e2+ 3e3

Base et points extr^emesAlgorithme du simplexe

quotesdbs_dbs11.pdfusesText_17