Chapitre 3 Méthode du simplexe
Le principe de la méthode du simplexe est d'éviter de calculer tous les de ne pas changer de notation pour la matrice A et des vecteurs b et c en cours.
Simplexe - Recherche Opérationnelle et Optimisation Master 1 I2L
Cours de recherche opérationnelle Nadia Brauner
LES ÉTAPES DE LALGORITHME DU SIMPLEXE
Un programme linéaire qui contient des contraintes (technologiques) de type est noté (PL). Un programme linéaire qui contient des contraintes
Modèles de Recherche Opérationnelle
une et une seule solution;. Page 23. 2.5. LA MÉTHODE DU SIMPLEXE. 17. 3. une infinité de solutions. Nous supposerons que toutes les variables sont positives. Le
FSJES-AC RECHERCHE OPERATIONNELLE Semestre 6 Filière
La méthode du simplexe est un algorithme qui permet la recherche de la solution optimale d'un programme linéaire donné. Dans la partie précédente ( Partie
Cours - Recherche Opérationnelle.pdf
une variable de base (variable sortante). Introduction. Phase 2 – Progression. Méthode des dictionnaires. Finitude du simplexe. Phase 1 –
COURS DE RECHERCHE OPERATIONNELLE
On a alors recours à une méthode algébrique basée sur un algorithme appelé algorithme du simplexe. I. L'ALGORITHME DU SIMPLEXE a. Notion du point extrême.
Chapitre 4 Dualité
On ajoute les variables d'écart x4x5
Recherche opérationnelle Les démonstrations et les exemples
Recherche opérationnelle. Les démonstrations et les exemples seront traités en cours linéaires en nombre réels est la méthode du Simplex. En théorie.
Graphes et Recherche Opérationnelle
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`ere méthode permet de bien
Chapitre 3 Méthode du simplexe - Université Laval
a)On applique la procédure d’élimination de Gauss-Jordan autour du pivot situé à l’intersectiondelalignei etdelacolonnej Ensuiteondiviselalignei parlepivot pourlemettreégalà1 b)Onretourneàl’étape1etonrecommence Remarque 3 2 3 Expliquonslecritèreduquotient A une certaine itération du simplexe nous disposons d’une solution
C D - EPFL
la recherche opérationnelle (2017–2018) Professeur : Michel Bierlaire Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe – corrigé (20 octobre 2017) On peut alors identi?er la matrice A le vecteur b et le vecteur c : A = 1 1 ?1 0 2 3 0 1 b = 4 18 et c = ?3 4 0 0
Simplexe - Recherche Opérationnelle et Optimisation Master 1 I2L
Algorithme du simplexe Dantzig 1947 Algo it eratif de r esolution de probl eme de programmation lin eaire Principe A partir d’un sommet chercher un sommet voisin qui am eliore l’objectif Propri et e du probl eme Soit x 0 sommet non optimum Alors il existe x un sommet voisin de x0 tel que f(x) >f(x 0) Donc ca marche
Searches related to cours recherche opérationnelle methode de simplexe PDF
solution de base pour ce système est obtenue de la manière suivante : a) On pose J F I variables égales à 0 Ces variables sont appelées variables hors base (V H B ) b) On résout le système pour les I variables restantes Ces variables sont appelées les variables de base (V B )
Qu'est-ce que la méthode simplexe ?
La méthode de simplexe est une procédure algébrique qui tient compte de ces trois considérations. Pour illustrer cette procédure, supposons que x2 = 0 et S1 = 0. Notre système devient Les variables x1, S2, S3 et S4 (non nulles) sont dites variables de base et les variables S1, x2, (nulles) sont dites variables hors base.
Quel est le principe de résolution de la méthode de Simplexe?
La méthode de simplexe commence par l'identification d'une solution réalisable de base et ensuite, elle essaye de trouver d'autres solutions réalisables de base jusqu’à atteindre à la solution optimale. Ainsi, on doit, tout d’abord, retrouver cette solution réalisable de base.
Qu'est-ce que la recherche opérationnelle?
La recherche opérationnelle (R.O) ou (la science delà décision) est la discipline des méthodes scientifiques utilisable pour élaborer de meilleurs décisions. Elle permet de rationaliser, de simuler, de planifier et d’optimiser l’architecture et le fonctionnement des systèmes de production ou d’organisation.
Comment trouver une solution optimale pour un programme linéaire ?
Ainsi une autre solution optimale peut être trouvée pour notre programme linéaire. Ceci confirme le résultat de la méthode graphique qui indique que ce problème admet un ensemble de solution optimale décrit par le segment [BC]. La solution optimale donnée par le dernier tableau de simplexe correspond au point C.
Graphes
etRecherche Operationnelle
Programmation Lin
eaireJ.-F. ScheidTELECOM Nancy 2A 2020-2021
2Table des matieres
1 Introduction generale 4
2 Modelisation et resolution graphique 4
2.1 Modelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42.2 Resolution graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53 Formes generales d'un programme lineaire 6
3.1 Forme canonique mixte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63.2 Forme canonique pure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73.3 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73.4 Variable d'ecarts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74 Solutions de base realisables 8
5 Proprietes geometriques des solutions de base realisables 10
6 Algorithme du simplexe 11
6.1 L'algorithme du simplexe proprement dit : la phase 2 . . . . . . . . . . . . . . . . . . . . .
126.2 Calcul des co^uts reduits et variable entrante . . . . . . . . . . . . . . . . . . . . . . . . . .
126.3 Variable sortante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
137 Mises en uvre de l'algorithme du simplexe 14
7.1 Methode des dictionnaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
147.2 Methode des tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
168 Convergence du simplexe 21
9 Initialisation et variables articielles : la phase 1 23
9.1 Probleme auxiliaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
239.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2410 Analyse post-optimale 25
10.1 Analyse de sensibilite de l'objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2510.2 Analyse de sensibilite du second membre des contraintes . . . . . . . . . . . . . . . . . . .
2711 Dualite29
11.1 Introduction et denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2911.2 Proprietes - Theoremes de dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3011.3 Conditions d'optimalite primal-dual (COPD) . . . . . . . . . . . . . . . . . . . . . . . . .
32References34
31 Introduction generale
De nombreux phenomenes economiques et industriels peuvent se modeliser par des systemesmathematiques d'inegalites et d'egalites lineaires conduisant a des problemes d'optimisation lineaire.
Dans ces problemes d'optimisation lineaire, on cherche a minimiser ou maximiser une fonction lineaire
sous des contraintes lineaires portant sur les variables du probleme. On parle souvent deprogramma- tion lineaire(ou encore deprogramme lineaire), le terme deprogrammationfaisant reference a l'idee d'organisation et de planication lie a la nature des phenomenes modelises. Ce terme a ete introduit pendant la Seconde Guerre mondiale et systematiquement utilise a partir de 1947 lorsque G. Dantziginventa la methode du simplexe pour resoudre les problemes de programmation lineaire. Les applications
industrielles de la programmation lineaire sont tres presentes par exemple dans l'industrie petroliere (pour
l'extraction, le ranage et la distribution du petrole), dans l'agroalimentaire (composition optimale des
ingredients de plats cuisines, etc.), industrie du fer et de l'acier (composition optimale des aciers), l'in-
dustrie du papier (problemes de decoupe), les transports (plan de vols d'avions, minimisation des co^uts
de transport...) et les reseaux (optimisation des reseaux informatiques et de communication). Ce cours presente les proprietes et les concepts fondamentaux de la programmation lineaire puis expose l'algorithme du simplexe pour resoudre un programme lineaire. L'algorithme du simplexe est mis en uvre selon deux methodes, lamethode des dictionnaireset lamethode des tableaux. La premiere methode permet de bien comprendre le deroulement du simplexe alors que la methode destableaux est plus algebrique et elle conduit a la mise en uvre eective de l'algorithme du simplexe. Une
application de la methode du simplexe a l'analyse de sensibilite d'un programme lineaire est egalement
presentee ainsi qu'une introduction a la dualite en programmation lineaire.2 Modelisation et resolution graphique
2.1 Modelisation
En optimisation et plus generalement en Recherche Operationnelle, modeliser un probleme consistea identier les variables intrinseques, les dierentes contraintes auxquelles sont soumises ces variables et
enn a denir l'objectif vise (optimisation). Dans un probleme de programmation lineaire (PL en abrege)
les contraintes et l'objectif sont des fonctionslineairesdes variables. On va etudier un exemple particulier de programmation lineaire qui servira d'exemple de referencetout au long de ce cours. Il s'agit d'un probleme de production volontairement tres simple. Le but ici
n'etant pas de resoudre ce probleme mais d'introduire les notions et concepts fondamentaux lies a la programmation lineaire. Dans cet exemple, on considere une usine qui fabrique deux produitsP1etP2 en utilisant 3 types de ressources : equipement, main d'uvre et matieres premieres. Ces besoins sontindiques dans le Tableau 1 ci-dessous. Par ailleurs, chaque ressource est disponible en quantite limitee
(cf. Tableau 1).P 1P2disponibilite
equipement3981 main d'oeuvre4555 matiere premiere2120 Table1 { Un probleme de production : ressources necessaires et equipements disponibles Les deux produitsP1etP2rapportent a la vente respectivement des beneces de 6 euros et 4 euros par unite. On cherche a savoir quelles quantites de produitsP1etP2doit produire l'usine an de maxi-miser le benece total venant de la vente des 2 produits. Les quantites de produits sont des valeurs non
4 necessairement entieres. Choix des variables (les inconnues):x1etx2sont respectivement les quantites des produitsP1et P2fabriques (x1;x22R).
Choix de la fonction objectif a maximiser: La fonction objectifFcorrespond au benece total provenant de la vente des produitsP1etP2en quantitex1etx2. Elle vautF(x1;x2) = 6x1+4x2.Le probleme se traduit donc par
max (x1;x2)[F(x1;x2) = 6x1+ 4x2]:Determination des contraintes.
La disp onibilitede c hacunedes r essourcess' ecrit:3x1+ 9x281 (equipement)
4x1+ 5x255 (main-d'oeuvre)
2x1+x220 (matiere premiere)
P ositivitedes v ariables: x1;x20.
En resume, le probleme de production se modelise sous la forme max (x1;x2)[F(x1;x2) = 6x1+ 4x2]: sous les contraintes : 8>>< >:3x1+ 9x2814x1+ 5x255
2x1+x220
x1;x20(2.1)Remarque.Pour un probleme d'optimisation ou on cherche a minimiser une fonction objectifF(au
lieu de maximiser comme dans l'exemple precedent du probleme de production), on peut toujours se ramener a un probleme de maximisation gr^ace a la relation min(F) =max(F) (2.2)2.2 Resolution graphique Dans le cas d'un PL a deux variables, on peut envisager une resolution graphique. Les contraintes ouapparaissent des inegalites correspondent geometriquement a des demi-plans. L'intersection de ces demi-
plans forme l'ensemble des variables satisfaisant a toutes les contraintes (la partie hachuree de la gure 1).
A la fonction objectifFcorrespond une droiteF(x1;x2) = 6x1+4x2= constante, de coecient directeur(1;6=4). La constante precedente qui denie la droite doit ^etre la plus grande possible (maximisation) et
rencontrer l'ensemble des variables qui satisfont les contraintes. Pour determiner cette valeur maximale,
on fait donc "glisser" la droite (translation parallele a la direction de la droite) du haut vers le bas jusqu'a
rencontrer l'ensemble des variables satisfaisant les contraintes. Le maximum deFsur cet ensemble descontraintes est alors atteint. On obtient ainsi la solution optimale (x1;x2) = (15=2;5) et ce qui donne une
valeur maximale max(F) = 65. On remarque que l'ensemble des contraintes (la partie hachuree de la gure 1) est unpolygone convexeet que le maximum deFest atteint enun sommetde ce polygone. Cette observation est, en fait, un resultat general que l'on etabliera dans les sections suivantes. 52x +x =20x
3x +9x =81
4x +5x =5512
1 1 x1F(x ,x )=6x +4x =
1212 22
2 optimum (-1,6/4) 05 10 5
15/210constanteFigure1 { Resolution graphique du probleme de production
3 Formes generales d'un programme lineaire
3.1 Forme canonique mixte
Il s'agit d'un probleme de programmation lineaire (encore appeleprogramme lineaire) ecrit sous la forme suivante. max (x1;;xn)2 4F(x1;:::;xn) =c1x1+cnxn=nX
j=1c jxj3 58>>>>>>>>>><
>>>>>>>>>:contraintes inegalites :8i2I1;nX j=1a ijxj=ai1x1++ainxnbi contraintes egalites :8i2I2;nX j=1a ijxj=bi contraintes de signes :8j2J1; xj08j2J2; xjde signe quelconque:(3.1)
Les valeurs reellesci,bietaijpour 1inet 1jn, sont donnees. L'ensembleI=I1[I2est l'ensemble des indices de contraintes avec card(I) =m. Autrement dit, il y amcontraintes. L'ensemble J=J1[J2est l'ensemble des indices des variables avec card(J) =n. Il y anvariables. 63.2 Forme canonique pure
Sous cette forme, il n'y a pas de contraintes d'egalite c'est-a-direI2=;etJ2=;.On notex= (x1;;xn)>2Rn
c= (c1;;cn)>2Rn b= (b1;;bm)>2Rm et la matriceAde taillemn: A=0 B @a11a12a1n......
a m1am2amn1 C A: Un programme lineaire (PL) est dit sous formecanonique pures'il s'ecrit : max xhF(x) =c>x=c1x1+cnxni
sous les contraintes : Axb x0(3.2)3.3 Forme standard
Sous cette forme,I1=;etJ2=;. Un programme lineaire (PL) est dit sous formestandards'il s'ecrit : max xhF(x) =c>xi
sous les contraintes : Ax=b x0(3.3) On dit de plus que le PL est sous forme standardsimplicialesiAde taillemnavecmn, se decompose en : A= I mjH (3.4)ouImdesigne la matrice identite de taillemmetHest une matrice de taillem(nm).Remarque sur la positivite des variables.Sous forme canonique pure ou standard, on impose
toujours la positivite des variablesx0. En fait, on peut toujours se ramener au casx0 : Si la v ariablex(composante) a une borne inferieure non nullexl, il sut de considerer la nouvelle variable (composante)y=xla la place dexet alors on ay0. S'il n'y a pas de b ornein ferieuresur x(variable libre), on peut toujours poserx=yzavec les nouvelles variablesy0,z0.3.4 Variable d'ecartsLes variables d'ecarts sont des variables supplementaires qui permettent de transformer des contraintes
d'inegalites en contraintes d'egalite.Proposition 3.1.Tout PL sous forme standard s'ecritde facon equivalente en un PL sous forme
canonique pure et inversement. 7 Demonstration.i)Soit un PL sous forme canonique pure. On aAxb,nX
j=1a ijxj+ei=bi;8i= 1;;m avec les variables supplementairesei=binX j=1a ijxj0, pour touti= 1;;m. Ainsi, Axb x0,8 AjImx e =b x e0,~A~x=b
x0 On a introduit lesmvariables supplementairese= (e1;;em)>qui sont appeleesvariables d'ecart. ii)Soit un PL sous forme standard. Montrons qu'on peut le transformer en un programme lineaire sous forme canonique pure. On aAx=b,Axb
Axb,Axb
Ax b,AA
xbb ,~~Ax~b ou ~~A=A A est une matrice de taille 2mnet~b=b b 2R2m.Exemple. Le probleme de production (2.1) est sous forme canonique pure. Mettons le sous forme standard
en introduisant 3 variables d'ecarts . La forme standard s'ecrit max (x1;x2;e1;e2;e3)[F(x1;x2;e1;e2;e3) = 6x1+ 4x2]: sous les contraintes : 8>>< >:3x1+ 9x2+e1= 814x1+ 5x2+e2= 55
2x1+x2+e3= 20
x1;x2;e1;e2;e30(3.5)
Il y a desormais 5 variablesx1;x2;e1;e2;e3.
4 Solutions de base realisables
On considere desormais (sauf mention contraire) un PL toujours sousforme standardc'est-a-dire avec des contraintes de la formeAx=b,x0. Faisons a present une hypothese sur la matriceA. Hypothese de rang plein: On suppose que la matriceAest de taillemnavecrang(A) =mn. On rappelle que le rang deAest le nombre maximal de lignes deAlineairement independantes. C'est aussi le nombre de colonnes deAlineairement independantes.Sous l'hypothese de rang plein :
le syst emeAx=badmet toujours des solutions; si m < n, le systemeAx=badmet une innite de solutions; si m=n, la matriceAest inversible. Dans ce cas, la solution du systeme lineaire est unique et vautx=A1bet il n'y a rien a maximiser. 8 L'hypothese de rang plein n'est pas restrictive car si rang(A)< mle systemeAx=bn'a pas de solutionen general. Si rang(A)< metb2Im(A), il y a des equations redondantes dans le systemeAx=b, qu'on peut donc supprimer pour obtenir un nouveau systeme de rang plein.Denition 4.1.On appellesolution realisabletout vecteurxqui satisfait les contraintes du PL i.e.
tel queAx=betx0: Remarque. Pour la forme canonique pure avecAxb, l'hypothese de rang plein n'est pas non plusrestrictive car si rang(A)< m, il y a des contraintes inegalites redondantes qu'on peut supprimer pour
obtenir un systeme de rang plein.Denition 4.2.SoitB f1;;ngun ensemble d'indices avec card(B) =mtel que les colonnesAj,
j2B, deAsont lineairement independantes. Autrement dit, la matrice carreeABformee des colonnes A j,j2B, estinversible. On dit que l'ensembleBdes indices est unebase. Les variablesxB= (xj; j2B)sont appeleesvariables de base. Les variablesxH= (xj; j =2B)sont appeleesvariables hors-base. On noteraH=fj2 f1;;ng;j62Bgl'ensemble des indices correspondants aux variables hors-base.Remarques. Sous l'h ypothesede rang plein, il existe toujours une base non vide. Quitte aren umeroterles in dices,on p euttoujours ecrireles d ecompositionspar blo cs: A= (ABjAH) ouAHest la matrice formee des colonnesAj; j =2B x=xB x H :Le systemeAx=best equivalent a ABxB+AHxH=b:
Par la relation precedente et du fait que la matriceABest inversible, on peut xer les variables hors-base
et les variables de base sont alors completement determinees.Denition 4.3.On dit quex=xB x H estsolution de baseassociee a la baseBsixH= 0: Proprietes des solutions de base realisables: Six=xB x H est une solution de base realisablealors xH= 0 etxB=A1
Bb. Exemple. Reprenons l'exemple du probleme de production de l'introduction. Sous forme standard (cf. (3.5)) , le PL s'ecrit max(x1;x2)[F(x1;x2) = 6x1+ 4x2]: sous les contraintes : 8>>< >:3x1+ 9x2+e1= 814x1+ 5x2+e2= 55
2x1+x2+e3= 20
x1;x2;e1;e2;e30(4.1)
9 On am= 3,n= 5, rang(A) =m= 3. Une base est donnee parB=f3;4;5gavecAB=0 @1 0 0 0 1 00 0 11
A La solution de base realisable correspondante estx= (x1;x2;e1;e2;e3)>= (0;0|{z} xH;81;55;20|{z}
xquotesdbs_dbs33.pdfusesText_39[PDF] livre recherche opérationnelle pdf
[PDF] cours et exercices corrigés de recherche opérationnelle+pdf
[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
[PDF] méthodologie de recherche qualitative pdf
