[PDF] [PDF] Graphes et Recherche Opérationnelle - Jean-François SCHEID

View - Download [PDF] Graphes et Recherche Opérationnelle - Jean-François SCHEID

Previous PDF

Next PDF

Graphes

et

Recherche Operationnelle

Programmation Lin

eaireJ.-F. Scheid

TELECOM Nancy 2A 2020-2021

2

Table des matieres

1 Introduction generale 4

2 Modelisation et resolution graphique 4

2.1 Modelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.2 Resolution graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3 Formes generales d'un programme lineaire 6

3.1 Forme canonique mixte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.2 Forme canonique pure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.3 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.4 Variable d'ecarts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

4 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 . . . . . . . . . . . . . . . . . . . . .

12

6.2 Calcul des co^uts reduits et variable entrante . . . . . . . . . . . . . . . . . . . . . . . . . .

12

6.3 Variable sortante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

7 Mises en uvre de l'algorithme du simplexe 14

7.1 Methode des dictionnaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

7.2 Methode des tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

8 Convergence du simplexe 21

9 Initialisation et variables articielles : la phase 1 23

9.1 Probleme auxiliaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

9.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

10 Analyse post-optimale 25

10.1 Analyse de sensibilite de l'objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

10.2 Analyse de sensibilite du second membre des contraintes . . . . . . . . . . . . . . . . . . .

27

11 Dualite29

11.1 Introduction et denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

11.2 Proprietes - Theoremes de dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

11.3 Conditions d'optimalite primal-dual (COPD) . . . . . . . . . . . . . . . . . . . . . . . . .

32

References34

3

1 Introduction generale

De nombreux phenomenes economiques et industriels peuvent se modeliser par des systemes

mathematiques 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. Dantzig

inventa 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 des

tableaux 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 consiste

a 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 reference

tout 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 sont

indiques dans le Tableau 1 ci-dessous. Par ailleurs, chaque ressource est disponible en quantite limitee

(cf. Tableau 1).P 1P

2disponibilite

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 P

2fabriques (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+ 9x281

4x1+ 5x255

2x1+x220

x

1;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 ou

apparaissent 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 des

contraintes 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. 5

2x +x =20x

3x +9x =81

4x +5x =5512

1 1 x

1F(x ,x )=6x +4x =

121
2 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 4

F(x1;:::;xn) =c1x1+cnxn=nX

j=1c jxj3 5

8>>>>>>>>>><

>>>>>>>>>:contraintes inegalites :8i2I1;nX j=1a ijxj=ai1x1++ainxnbi contraintes egalites :8i2I2;nX j=1a ijxj=bi contraintes de signes :8j2J1; xj0

8j2J2; 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. 6

3.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 @a

11a12a1n......

a m1am2amn1 C A: Un programme lineaire (PL) est dit sous formecanonique pures'il s'ecrit : max xh

F(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 xh

F(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'ecarts

Les 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 a

Axb,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 e

0,~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 a

Ax=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= 81

4x1+ 5x2+e2= 55

2x1+x2+e3= 20

x

1;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.quotesdbs_dbs28.pdfusesText_34

[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

[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