[PDF] Recherche opérationnelle Un programme linéaire (PL)

View - Download Recherche opérationnelle

Previous PDF

Next PDF

1/56IntroductionM ´ethodegraphique Simplexe Dualit ´e

Programmation lin´eaire et recherche

op´erationnelle

Ioan 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 `a

maximiser 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´esoudre

5/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 ´e

Plan 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 ´e

Un 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 son

gain, 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 I

9/56IntroductionM ´ethodegraphique Simplexe Dualit ´e

Programme lin´eaire : d´efinition

Variablesr´eelles:

x

1,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 a

21x1+a22x2+···+a2nxn≥b2

a m1x1+am2x2+···+amnxn=bmSolution :toute affectation des va riablesqui r especteles contraintes

Solution optimale :

solution qui optimise (maximise ou minimise) la fonction objectif.10/56IntroductionM ´ethodegraphique Simplexe Dualit ´e

Un 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 ´e

La m´ethode graphique

Id´ee : repr´esenter graphiquement les contraintes et visualiser l"ensemble des solutions. Identifier une solution optimale.

Exemple :

maxx1+x2 x

1-2x2≥ -8

x

1≥0

x

2≥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 ´e

Questions

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 ´e

Algorithme du simplexe

[G. Dantzig, 1947] Algorithme de r´esolution de programmes lin´eaires

Facile `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 ´e

PL 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 x

1,x2,x3≥018/56IntroductionM ´ethodegraphique Simplexe Dualit ´e

Variables d"´ecart

PL

´ equivalent

x

4= 5-2x1-3x2-x3

x

5= 11-4x1-x2-2x3

x

6= 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 ´e

Augmenterx1

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 ´e

Nouveau dictionnaire

x 1=52 -32 x2-12 x3-12 x4 x

5= 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 3x

3= 1 (x6=...)`a droite :x2,x3,x6

21/56IntroductionM ´ethodegraphique Simplexe Dualit ´e

Nouveau dictionnaire (et de trois...)

x

3= 1 +x2+ 3x4-2x6

x

1= 2-2x2-2x4+x6

x

5= 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 ´e

Premier 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 ´e

Dictionnaires : un peu de vocabulaire

x

4= 5-2x1-3x2-x3

x

5= 11-4x1-x2-2x3

x

6= 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 x

4,x5,x6•

Variables "de droite" :

va riablesho rsbase x

1,x2,x3

25/56IntroductionM ´ethodegraphique Simplexe Dualit ´e

Vers une meilleure solution

x

4= 5-2x1-3x2-x3

x

5= 11-4x1-x2-2x3

x

6= 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 ´e

Algorithme 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 ´e

Simplexe : un deuxi`eme exemple

max 5x1+ 5x2+ 3x3 x

1,x2,x3≥028/56IntroductionM ´ethodegraphique Simplexe Dualit ´e

Mise sous forme standard

minx1+ 2x2 contraintesx1+x2= 10 x

1-x2≥ -10

x

1≥0•

minz→max-z• ?aixi=b→ ?aixi≥b→ pas de contraintex≥0→on remplacexparx+-x-, avecx+,x-≥0

29/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 ´e

Dictionnaires 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 minimum

33/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 faisable

Trouver 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 ´e

Initialisation : 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 ´e

Initialisation : exemple

maxx1-x2+x3 x

1,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 x

1,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 ´e

Simpl`exe par les tableaux

maxx1+x2 x

1,x2≥0

Une autre vision

du m ˆemealgo rithme Version tr`es facilement implantable39/56IntroductionM ´ethodegraphique Simplexe Dualit ´e

D"un tableau `a l"autre

2 1 1 0 014

-1 2 0 1 08

2-1 0 0 110

1 1 0 0 00

2 1

1 0 0 14

-1201 0 8

2-10 0 1 10

1 1

0 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].quotesdbs_dbs12.pdfusesText_18

[PDF] programmation linéaire définition

[PDF] programmation lineaire methode simplexe

[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