[PDF] Programmation linéaire et recherche opérationnelle Recherche

View - Download Programmation linéaire et recherche opérationnelle Recherche

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

xquotesdbs_dbs47.pdfusesText_47

[PDF] méthode lecture syllabique télécharger

[PDF] méthode lettre anglais

[PDF] methode meaning

[PDF] methode merise pour les nuls

[PDF] methode nombre premier

[PDF] methode oral philo

[PDF] methode par balayage calculatrice casio

[PDF] méthode par combinaison

[PDF] Méthode par dichotomie (J'ai vraiment besoins d'aide)

[PDF] méthode par substitution exemple

[PDF] Méthode par substitution probleme du premier degre a une inconnue

[PDF] Methode par substitutions

[PDF] méthode physique chimie terminale s

[PDF] méthode pivot exercices résolus

[PDF] Méthode plan en philo