maximiser le profit obtenu apr`es deux ans? 3/56 Introduction Méthode graphique Simplexe Dualité Des probl
Previous PDF | Next PDF |
[PDF] TD 5 Programmation linéaire et optimisation Dualité Exercice 1 - grug
Corrigé: Exercice 2 Dans le cas d'un problème de programmation linéaire ( minimisation) possédant une solution optimale finie, l'algorithme primal du simplexe
[PDF] 174 EXERCICES SUPPLÉMENTAIRES — PARTIE II
La programmation linéaire constitue l'origine de l'optimisation mathématique moderne linéaire, l'algorithme du simplexe révisé, les notions de dualité, et
[PDF] Exercices de Programmation Linéaire – Modélisation –
exercice 1 : Résoudre le programme linéaire suivant par la méthode du simplexe Dualité – exercice 1 : Écrire le dual du programme linéaire suivant :
[PDF] 1 Programmation linéaire
Master d'économie Cours de M Desgraupes Méthodes Numériques Document 4 : Corrigé des exercices d'optimisation linéaire 1 Programmation linéaire 1
[PDF] Série 1: Programmation linéaire
Série 1: Programmation linéaire Formulation mathématique-résolution graphique Pour chaque exercice, formuler le probl`eme de programmation linéaire et le
[PDF] Exercices corrigés PROGRAMMATION LINÉAIRE
Optimisation discrète, Séance 5 : Exercices corrigés Quest 1 £ On a là un problème d'optimisation (linéaire)sous contraintes (linéaires) : ¤¦¥¨§ © #" $ ' ) (1 327/5 Phi Programmation linéaire et dualité Dualité Primal (P) Dual (D) S
[PDF] Programmation linéaire et recherche opérationnelle Recherche
maximiser le profit obtenu apr`es deux ans? 3/56 Introduction Méthode graphique Simplexe Dualité Des probl
[PDF] Dualité en Programmation Linéaire Algorithmes primal et - ENSIIE
Dualité et programmation linéaire 13 min ≥0 3- En déduire que le dual lagrangien de (P) est le problème (D) Exercice (th de dualité faible) Exercice
[PDF] Programmation linéaire - JavMathch
6 5 Exemple accompagné (reprise de l'exercice 3 1 déjà étudié en page 17) : 47 (IV) Résolution de problèmes de programmation linéaire à 2 variables par voie graphique Un corrigé complet peut être vu à votre demande
[PDF] photo visa canada maroc
[PDF] photo visa canada 2016
[PDF] probleme dual
[PDF] photo citoyenneté canadienne
[PDF] photo visa canada 2017
[PDF] photo visa touriste canada
[PDF] tracer la hauteur d'un triangle cm2
[PDF] hauteur triangle obtusangle
[PDF] comment tracer une hauteur d'un triangle
[PDF] tracer les hauteurs d'un triangle exercices
[PDF] comment tracer la hauteur d'un triangle isocele
[PDF] dimensionnement pompe de relevage eaux usées
[PDF] calcul hmt pompe immergée
[PDF] calcul hmt pompe immergée forage
1/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Programmation lin´eaire et recherche
op´erationnelleIoan Todinca
Ioan.Todinca@univ-orleans.fr
t´el. 02 38 41 72 93 bureau : en bas `a gauche2/56IntroductionM ´ethodegraphique Simplexe Dualit ´e Recherche op´erationnelleTentative de d´efinition Ensemble de m´ethodes (algorithmiques, math´ematiques, mod´elisation) afin de prendre des d´ecisions optimales ou proches de l"optimum dans des probl`emes complexes, qui traitent de la maximisation d"un p rofitou la minimisation d"un co ˆut.• Comment aller le plus vite d"Orl´eans `a Berlin, en voiture? Comment ordonnancer les tˆaches d"un projet en fonction de la main d"oeuvre, tout en minimisant sa dur´ee? Comment investir ses 1000 euros d"´economie de sorte `amaximiser le profit obtenu apr`es deux ans?3/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Des probl`emes de RO que vous savez r´esoudre
Trouver un (plus court) chemin entre deux villes→plus courts chemins dans les graphes• Broadcast de coˆut minimum dans un r´eseau→arbres recouvrants de poids minimum.•Envoi d"un maximum d"information dans un r´eseau→probl`eme du flot maximum.4/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Programmation lin´eaireLes probl`emes de programmation lin´eaire (PL) sont des probl`emes d"optimisation o`u la fonction objectif et les contraintes sont toutes lin´eaires.•Mod´elisationd"un probl`eme r´eel
Si l"on constate que ce probl`eme s"exprime comme un PL, le r´esoudre5/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Pourquoi un cours sur la programmation lin´eaire?Objectif :
app rendre` amod´eliserles probl`emes r´eels et `ar´esoudre les programmes lin´eaires. De nombreux probl`emes r´eels peuvent ˆetre exprim´es comme des programmes lin´eaires. Les programmes lin´eaires peuvent ˆetre r´esolus efficacement par certains algorithmes.• Ce sont d"excellents exemples de questions pratiques dont la r´esolution n´ecessite une combinaison de m´ethodes algorithmiques, demath´ematiques´el´ementaires et debon sens.6/56IntroductionM ´ethodegraphique Simplexe Dualit ´ePlan du cours
1. Intro duction+ une app rochena ¨ıve: la m ´ethodegraphique 2.L"algo rithmedu simplexe
3.Simplexe : comment ´ eviterles pi `eges
4.Dualit ´e
5.Programmation lin ´eaireen nomb rese ntiers
Bibliographe :
[V. Chv ´atal,Linear Programming]7/56IntroductionM ´ethodegraphique Simplexe Dualit ´eUn exemple : le probl`eme
Consid´erons un agriculteur qui poss`ede des terres, de superficie ´egale `aHhectares, dans lesquelles il peut planter du bl´e et du ma¨ıs. L"agriculteur poss`ede une quantit´eEd"engrais etI d"insecticide. Le bl´e n´ecessite une quantit´eEbd"engrais par hectare etIbd"insecticide par hectare. Les quantit´es correspondantes pour le ma¨ıs sont not´eesEmetIm. SoitPble prix de vente du bl´e etPmcelui du ma¨ıs. Si l"on note parxbetxmle nombre d"hectares `a planter en bl´e et en ma¨ıs, comment exprimer le fait que l"agriculteur souhaite maximiser songain, tout en restant dans les limites de ses ressources?8/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Le mˆeme exemple apr`es mod´elisation
maximiserPbxb+Pmxm(maximiser le revenu net) x b≥0 x m≥0 E I9/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Programme lin´eaire : d´efinition
Variablesr´eelles:
x1,x2,...,xn
Fonction objectif lin´eaire, `a optimiser (min ou max) : z=c1x1+c2x2+···+cnxn Contraintes lin´eaires (´egalit´es ou in´egalit´es) : a a21x1+a22x2+···+a2nxn≥b2
a m1x1+am2x2+···+amnxn=bmSolution :toute affectation des va riablesqui r especteles contraintesSolution optimale :
solution qui optimise (maximise ou minimise) la fonction objectif.10/56IntroductionM ´ethodegraphique Simplexe Dualit ´eUn autre exemple
Vous disposez de 10000 euros que vous souhaitez investir. Votre banque vous propose trois types d"investissements. Pour l"investissement A le rendement est de 9% et la somme maximum que l"on peut investir est de 4000 euros. Pour l"investissement B on peut investir jusqu"`a 5000 euros, avec un rendement de 4%. Enfin le produit C a un rendement de 8% pour un montant maximum de 5000 euros. 1. Exp rimerce p robl`emecomme un PL. Donner la solution optimale.2.La banque c hanged"avis. Si vous souhaitez faire un investissement (A, B ou C) il faut y mettre la somme exacte (respectivement 4000, 5000, et 5000 euros). Mettre `a jour votre mod`ele ; est-ce toujours un PL?11/56IntroductionM ´ethodegraphique Simplexe Dualit ´eLa m´ethode graphique
Id´ee : repr´esenter graphiquement les contraintes et visualiser l"ensemble des solutions. Identifier une solution optimale.Exemple :
maxx1+x2 x1-2x2≥ -8
x1≥0
x2≥012/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
La m´ethode graphique
Variables :xety(oux1etx2).•
L"ensemble de points qui satisfont une´equation(´egalit´e) lin´eaire forme unedroite.• Les points qui satisfont unein´egalit´e lin´eaireforment undemi-plan.• L"ensemble des solutions d"un ensemble de contraintes : polygone convexe.• Solution optimale (si elle existe) :sommetdu polygone.13/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Trois variables ou plus
Variables :x1,...,xn
L"ensemble de points qui satisfont une´equation(´egalit´e) lin´eaire forme unhyperplan. Les points qui satisfont unein´egalit´e lin´eaireforment un demi-espace. L"ensemble des solutions d"un ensemble de contraintes : poly`edre convexe.Solution optimale (si elle existe) :sommetdu poly`edre.Limites : pr´ecision ; maximum 3 variables.
Si vous arrivez `a visualiser un PL avec 4 variables ou plus...pensez `a consulter un bon psy.14/56IntroductionM ´ethodegraphique Simplexe Dualit ´eQuestions
Donner un exemple de programme lin´eaire qui n"a pas de solution. Proposer un PL qui a des solutions, mais pas de solution optimale. Proposer un PL qui a plusieurs solutions optimales. Essayer de r´esoudre par la m´ethode graphique le syst`eme suivant : objectif : max2x+y x≥0,y≥015/56IntroductionM ´ethodegraphique Simplexe Dualit ´eAlgorithme du simplexe
[G. Dantzig, 1947] Algorithme de r´esolution de programmes lin´eairesFacile `a comprendre et `a implanter
Efficace en pratique, mˆeme pour un nombre important de variables et de contraintes Efficacit´e au pire cas : on en reparlera, voir aussi cours d"algorithmique.16/56IntroductionM ´ethodegraphique Simplexe Dualit ´ePL sous forme standard
max n? j=1c jxj contraintes : n? j=1a x j≥0j= 1,2,...,nQuestion : comment mettre un probl`eme quelconque sous forme standard?17/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Simplexe : un exemple
max 5x1+ 4x2+ 3x3 x1,x2,x3≥018/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Variables d"´ecart
PL´ equivalent
x4= 5-2x1-3x2-x3
x5= 11-4x1-x2-2x3
x6= 8-3x1-4x2-2x3z= 5x1+ 4x2+ 3x3
maxz,sous contraintes :x1,x2,x3,x4,x5,x6≥0Solution initiale :x1=x2=x3= 0,x4= 5,x5= 11,x6= 8 ; z= 0.Si on augmentex1, ¸ca augmentez!19/56IntroductionM ´ethodegraphique Simplexe Dualit ´eAugmenterx1
1.De combien ? x
carx4= 5-2x1-3x2-x3≥0.2.Nouvelle solution ? x 1=12 ,x2=x3=x4= 0,x5= 1,x6=12 ;z=252 .3.Refo rmulerle syst `emeafin d"exp rimerles va riablesx1,x5,x6en fonction dex2,x3,x4.x 1=52 -32 x2-12 x3-12 x420/56IntroductionM ´ethodegraphique Simplexe Dualit ´eNouveau dictionnaire
x 1=52 -32 x2-12 x3-12 x4 x5= 1 + 5x2+ 2x4
x 6=12 +12 x2-12 x3+32 x4z=252 -72 x2+12 x3-54 x4Augmenter qui? De combien? Qu"obtient-on? x 3x3= 1 (x6=...)`a droite :x2,x3,x6
21/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Nouveau dictionnaire (et de trois...)
x3= 1 +x2+ 3x4-2x6
x1= 2-2x2-2x4+x6
x5= 1 + 5x2+ 2x4z= 13-3x2-x4-x6
Solution actuelle :x2=x4=x6= 0,x1= 2,x3= 1,x5= 1 ;Algorithme du simplexe : cas g´en´eral
Entr´ee :
max n? j=1c jxj contraintes : n? j=1a x j≥0j= 1,2,...,n•On introduitmvariables d"´ecart:
x n+i=bi-n? j=1a ijxj(i= 1...,m)• Lai`eme contrainte devientxn+i≥0.23/56IntroductionM ´ethodegraphique Simplexe Dualit ´ePremier dictionnaire
x n+i=bi-n? j=1a ijxj(i= 1,...,m) z=n? j=1c jxj maxz,sous contraintes :xk≥0 (k= 1,...n+m)Dictionnaires : ´equivalents au PL d"origine n+m+ 1 variablesx1,...,xn+metz m´equations lin´eaires de typexk=... tous les membres droits ont les mˆemesnvariables objectif : maxzsous contraintes ci-dessus plus x k≥0 (k= 1,...n+m)24/56IntroductionM ´ethodegraphique Simplexe Dualit ´eDictionnaires : un peu de vocabulaire
x4= 5-2x1-3x2-x3
x5= 11-4x1-x2-2x3
x6= 8-3x1-4x2-2x3z= 5x1+ 4x2+ 3x3
Dictionaire
faisable : en mettant ` a0 toutes les va riablesdes membres droits, on obtient une solution du PL• On suppose que notre premier dictionnaire est faisable• Nous verrons plus tard comment faire pour que ce soit toujours le cas• Variables "de gauche" (saufz) :va riablesde base x4,x5,x6•
Variables "de droite" :
va riablesho rsbase x1,x2,x3
25/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Vers une meilleure solution
x4= 5-2x1-3x2-x3
x5= 11-4x1-x2-2x3
x6= 8-3x1-4x2-2x3z= 5x1+ 4x2+ 3x3
1.Solution courante : va riablesho rsbase ` a0
2. T rouverune va riableho rsbase xkdont le coefficient dans l"expression dezsoit strictement positif. 3. S"il n"en existe pas, la solution courante est optimale! 4. T rouverla contrainte la plus fo rtep ourl"augmentation de xk; soitxl=···cette contrainte. 5.Augmenter xkjusqu"`a ce que l"on aitxl= 0.
6. Exp rimerxken fonction dexlet des autres variables hors base. 7. Mettre ` ajour le dictionnaire, en faisant rentrer xkdans la nouvelle base et en sortantxl.26/56IntroductionM ´ethodegraphique Simplexe Dualit ´eAlgorithme du simplexe
Initialisation :introduire les variables d"´ecart et calculer un premier dictionnaire faisable ; mettre `a 0 les variables hors base tantqueil existe une variable hors basexkayant un coeff positif dans l"expression dezfaire soitxl=···la contrainte la plus contraignante pour augmenterxk pivoter afin de so rtirxlde la base en y faisant rentrerxk retournerla solution courante27/56IntroductionM ´ethodegraphique Simplexe Dualit ´eSimplexe : un deuxi`eme exemple
max 5x1+ 5x2+ 3x3 x1,x2,x3≥028/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Mise sous forme standard
minx1+ 2x2 contraintesx1+x2= 10 x1-x2≥ -10
x1≥0•
minz→max-z• ?aixi=b→ ?aixi≥b→ pas de contraintex≥0→on remplacexparx+-x-, avecx+,x-≥029/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Simplexe : les pi`eges
1.Difficult ´e` atrouver une solution initial e
2.It ´eration: p eut-ontoujours augmenter
strictem ent l"objectif ? 3.T erminaison,complexit ´e.
30/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
It´eration
Choix de la variable qui entre dans la base.
Choix de la variable qui sort de la base.Et si aucune contrainte ne limite l"augmentation de la variable
hors base?Peut-on toujours augmenterstrictement l"objectif ? Non . Il se peut que l"on ait une variable hors base avec co´efficient positif dansz, mais qu"elle ne puisse ˆetre augment´ee `a cause d"une contrainte.31/56IntroductionM ´ethodegraphique Simplexe Dualit ´eDictionnaires d´eg´en´er´es
Une ou plusieurs variables de base ont une valeur nulle. On ne peut augmenter aucune variable hors base.On fait n´eanmoins un changement de base.La valeur de l"objectif n"augmente pas
... mais ¸ca devrait aller mieux dans quelques ´etapes.32/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
TerminaisonLemme
Si deux dictionnaires ont les mˆemes variables de base, ils sont identiques.Th´eor`eme L"algorithme du simplexe termine sur une solution optimale, ou alors il boucle.•Les cas de bouclage sont tr`es rares.
Le bouclage est facile `a d´etecter.•
Il existe des solutions simples pour ´eviter le bouclage, par exemple en choisissant ` achaque it ´erationcomme va riables sortante et entrante celles d"indice minimum33/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Complexit´e : nombre d"it´erations
Dans la pratique :
Le nombre d"it´erations est proportionnel au nombre de contraintes initiales (typiquement entre 3m/2 et 3m). Croit tr`es peu avec le nombrende variables initiales.En th´eorie (au pire cas) :
Il existe des exemples qui n´ecessitent 2nit´erations[Klee,Minty 1972]
Nombre de dictionnaires : autant que de bases possibles, donc?n+m m?34/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Initialisation : premier dictionnaire non faisableTrouver un autre dictionnaire faisable.•
Ou prouver que le probl`eme n"a pas de solution!La m´ethode du simplexe `a deux phases : d"une pierre deux coups.
Introduction d"un probl`eme auxiliaire.
En le r´esolvant, nous trouverons un dictionnaire faisable du probl`eme initial ou bien nous saurons que notre probl`eme n"a pas de solution.35/56IntroductionM ´ethodegraphique Simplexe Dualit ´eInitialisation : le probl`eme auxiliaire
max n? j=1c jxj contraintes : n? j=1a x j≥0j= 1,2,...,n devient : minx0 contraintes : n? j=1a x j≥0j=0 ,1,...,n36/56IntroductionM ´ethodegraphique Simplexe Dualit ´eInitialisation : exemple
maxx1-x2+x3 x1,x2,x3≥0
37/56IntroductionM ´ethodegraphique Simplexe Dualit ´e
Simplexe : interpr´etation g´eom´etrique
Observer graphiquement l"´evolution de l"algorithme du simplexe sur cet exemple : maxx1+x2 x1,x2≥0•
Chaque solution interm´ediaire du simplexe correspond `a un sommet du poly`edre des contraintes.• Les "d´eplacements" d"une solution `a la suivante se font le long des arˆetes.38/56IntroductionM ´ethodegraphique Simplexe Dualit ´eSimpl`exe par les tableaux
maxx1+x2 x1,x2≥0
Une autre vision
du m ˆemealgo rithme Version tr`es facilement implantable39/56IntroductionM ´ethodegraphique Simplexe Dualit ´eD"un tableau `a l"autre
2 1 1 0 014
-1 2 0 1 082-1 0 0 110
1 1 0 0 00
2 11 0 0 14
-1201 0 82-10 0 1 10
1 10 0 0 0
Choix de la
colonne pivot : co efficientp ositifsur la derni `ere ligne.S"il n"en existe pas, l"optimum est atteint :
z=-t[m+ 1,n+m+ 1].Choix de la
ligne pivot : celle qui minimise sir iparmi toutes les lignes avecripositif(ri, resp.sisont les ´el´ements de lai`eme lignese trouvant sur la colonne pivot, resp. la derni`ere colonne.)40/56IntroductionM ´ethodegraphique Simplexe Dualit ´e