[PDF] Programmation linéaire Théorème de dualité.

View - Download Programmation linéaire

Previous PDF

Next PDF

1

Programmation linéaire

1.Le problème, un exemple.

2.Le casb= 03.Théorème de dualité

4.L"algorithme du simplexe

5.Problèmes équivalents

6.Complexité de l"Algorithme

Robert Cori,Conception et analyse d"algorithmes 4

2

Position du problème

SoitAune matrice de réels de taillem×n,betcdeux vecteurs de réels de taillemet nrespectivement. Résoudre le problème linéaire défini parA,b,cconsiste à trouver des réelsx1,x2,...,xnsatisfaisant lesminéquations (une pour chaqueientre 1 et m) :n j=1A n j=1c jxj(2)Robert Cori,Conception et analyse d"algorithmes 4 3

Problème concret

Un fleuriste dispose de 50 lys, 80 roses et 80 jonquilles. Il réalise ou bien des bouquets qu"il vend 40 euros comprenant 10 lys, 10 roses et 20 jonquilles, ou bien des bouquets dont il tire un prix de 50 euros qui comprennent 10 lys, 20 roses et 10 jonquilles. Comment le fleuriste doit il former les bouquets pour réaliser une recette maximale ?Modélisation mathématique

10x: nombre de bouquets du premier type,

10y: nombre de bouquets du deuxième type.?

max4x+ 5yRobert Cori,Conception et analyse d"algorithmes 4 4

Remarques

On appelle souvent

?n

j=1cjxjlafonction économiqueLesAi,j,bi,cjne sont pas nécessairement positifs. On peut remplacer la recherche

1.Il n"existe pas dexjsatisfaisant les inéquations (1)2.Parmi lesxjsatisfaisant les inéquations la somme (2) peut être aussi grande que

l"on veut3.Il existe plusieurs valeurs donnant l"optimum

4.Il existe une et une seule valeur donnant l"optimum

Robert Cori,Conception et analyse d"algorithmes 4

5

Interprétation économique

•x jnombre de produits finis de typejfabriqués•a i,jquantité de matière première de typeinécessaire pour fabriquer un produit de typej•b iquantité de matière première de typeidisponible•c

jbénéfice réalisé par produit fini de typejRobert Cori,Conception et analyse d"algorithmes 4

6 Sur l" exemple très simple du fleursite il y a deux variablesxety, les contraintes sont? max4x+ 5yRobert Cori,Conception et analyse d"algorithmes 4 70
20 16 22
23

Robert Cori,Conception et analyse d"algorithmes 4

8

Résultats géomètriques

•L"ensemble desxsatisfaisant

forme un polyèdre convexe•Unsommetdu polyèdre est l"intersection denhyperplans•Si le polyèdre est borné, il existe nécessairement un sommet qui réalise l"optimum

•Un sommet réalise l"optimum si et seulement si ses voisins donnent une valeur plus faible à la fonction économiqueRobert Cori,Conception et analyse d"algorithmes 4 9

Trois situations possibles

1.Les contraintes sont impossibles à satisfaire

100Robert Cori,Conception et analyse d"algorithmes 4

11

Méthode du Simplexe

1.Partir d"un sommet quelconqueP0du polytope,i :=02.Tant qu"il existe un voisinQdePiqui améliore la fonction économique faireP

i+1=Q;i++3.Si on trouve une direction pour laquelle la fonction augmente indéfiniment :Arrêt

A préciser :

•Terminaison •Que faire si voisin égal? •Comment trouver si cela augmente indéfiniment?

Robert Cori,Conception et analyse d"algorithmes 4

12

Casb= 0Situation particulière:

•Il existe toujours un point qui satisfait les contraintes •On a soit un optimum infini soit un optimum nul, car s"il existe unusatisfaisant 13 •Sicn"est pas combinaison linéaire des lignes deA, alors il existeutel quecu >0

etAu= 0ainsi l"optimum est infini•Sics"exprime comme une combinaison des lignes deAalors ou bien il existe unu

yA=c?cu=yAu, y≥0?cuetAuont même signeRobert Cori,Conception et analyse d"algorithmes 4 14 ThéorèmeSi l"un des deux problèmes suivants 15

Algorithme du simplexe simplifié

SOITIUN ENSEMBLE D"INDICES QUI FORME UNE BASE DE L"ESPACE ENGENDRÉ PAR LES LIGNES DEA,EXPRIMERcCOMME UNE COMBINAISON LINÉAIRE DES

LIGNESLi, i?I.c=?

i?Iy iLiTANT QU"IL EXISTEyi<0FAIRESOIThLE PLUS PETIT INDICE TEL QUEyh<0ET SOITuLE VECTEUR DERnTEL EXPRIMERcCOMME PLUS HAUT.Robert Cori,Conception et analyse d"algorithmes 4 16

Preuve de terminaison (1)

Ensemble d"indicesItel queL

ipouri?Iest une base de l"espace engendré par les lignes. c=y1Li1+y1Li1+······+ykLik•Si pour touti?Ion ay i≥0c"est fini. •Sinon on prendhle plus petit tel quey h<0Robert Cori,Conception et analyse d"algorithmes 4 17

Preuve de terminaison (2)

Vecteurutel queL

iu= 0pouri?=h?IetL hu=-1.

On a toujours

cu=-yh>0•Si pour touti /?Ion aL •Sinon on prendsle plus petitidans{1,2,...,m}tel queL su >0et on pose I ?=I-h+s•On vérifie queI ?définit les indices de lignes qui forment une base de l"espace engendré par celles-ci.Robert Cori,Conception et analyse d"algorithmes 4 18

Preuve de terminaison (3)

On suppose que l"algorithme boucle

On retrouve deux fois le même ensembleI; soitrl"indice le plus grand qui sort de

Ientre les deux étapes

On remarque aussi que c"est le plus grand qui entre!.

On noteI

pla valeur deIavant quersorte etI pla valeur deIaprès querentre I→...→Ip→ ······ →Iq→...→I•Soitu ?la valeur deuavant construction deI q. •AlorsL ru?est le seulL iu?non nul pouri?Iqet: cu ?>0Robert Cori,Conception et analyse d"algorithmes 4 19

Preuve de terminaison (4)

On suppose que l"algorithme boucle ...

c=? i?Ipy iLiPouri?Ip,i < r, on ay i>0On remarque aussi que l"on a aussi pour ces valeurs dei,L iu?<0car au moment de rentrer dansI q,rest le plus petit parmi{1,2,...,m}tel queL ru?>0Robert Cori,Conception et analyse d"algorithmes 4 20

Preuve de terminaison (5)

On suppose que l"algorithme boucle ...

cu i?Ipy iLiu?cu i r,iest à la fois dansI

Pet dansI

qdoncL iu?= 0ainsi : cu iRobert Cori,Conception et analyse d"algorithmes 4 21

Système d"inéquations

?u=b•Ce qui est équivalent à:yA 22

Théorème de dualité

Si l"un des deux problèmes suivants

(D) min{by|y≥0, yA=c}admet une solution finie alors il en est de même pour l"autre et on a : 23

Interprétation économique du dual

RemarqueOn augmente la quantité de matière première d"une valeur marginaleti(petit), l"augmentation du gain est alorsyitioùyiest la valeur qui rend optimum le

problème dual.Robert Cori,Conception et analyse d"algorithmes 4 24

Algorithme du simplexe

SOITIUN SOUS-ENSEMBLE DEnÉLÉMENTS DE{1,2,...,m}ET SOITx

i?IyiLiETyj= 0POURj /?I.SIy≥0ALORSxEST SOLUTION DU SYSTÈME.SINON SOITiLE PLUS PETIT INDICE TEL QUEyi<0ET SOITUiLA COLONNE

CORRESPONDANTE DEA-1

I;DÉTERMINER POUR CHAQUE LIGNELjDE LA

jSOIT MINIMUM PARMI LESvjPOSITIFS. ON POSE ALORSI:=I- {i} ? {j}ET ON CALCULEx,INTERSECTION DES HYPERPLANS CORRESPONDANTS.Robert Cori,Conception et analyse d"algorithmes 4 25

Calcul effectif d"un exemple

On considère?

x I=( ((-1 0 0 0 0-1

2 1-1)

))AI-1=( ((-1 0 0 2-1 1

0-1 0)

))Robert Cori,Conception et analyse d"algorithmes 4 26

Etape 1.

cA I-1= (1,-2,1)On supprime la ligne2la colonne correspondante dansAI-1est :( ((0 -1 -1) ))Le produit de cette colonne par l"opposée de chacune des lignes de la matriceA donne0,-1,0,-1,-2,1.I={1,3,6}A I=( ((-1 0 0 2 1-1 -1 0-1) ))AI-1=( ((-1 0 0 1 1 1 -1 0-1) ))Robert Cori,Conception et analyse d"algorithmes 4 27

Etape 2.

Le pointxest égal à(0,12,8)cA

I-1= (-1,1,2)On supprime la ligne1, la colonne correspondante est alors( ((-1 1 -1) ))Le produit de cette colonne par l"opposée de chacune des lignes de la matriceA donne-1,-1,0,6,3,0. b j-Ljxv jqui vaut 3 pourj= 4et9.66pourj= 5on retient donc la ligne4et on obtient I= 3,4,6.Robert Cori,Conception et analyse d"algorithmes 4 28
A I=( ((2 1-1 3-2 1 -1 0-1) ))AI-1=16 ((2 1 1 4-1 5

2 1 7)

))Etape 3.

On trouve le pointx= (3,9,11)et on acA-1

I= 1/6(8,1,13)qui est positif on a

donc atteint l"optimum qui vaut 23 pour ce pointx.Robert Cori,Conception et analyse d"algorithmes 4 29
Problèmes posés par l"algorithme du simplexe •Risque de bouclage, car la fonction économique n"augmente pas strictement à chaque étape ?•Comment trouver une valeur initiale? •Algorithme non polynomial

Robert Cori,Conception et analyse d"algorithmes 4

30

Initialisation

polyèdre•On ajoute une nouvelle variablexn+1et on conside're :n j=1A debiLe problème initial est réalisable si et seulement si le deuxième admet pour solution optimalexn+1= 0Robert Cori,Conception et analyse d"algorithmes 4 31

Complexité

Robert Cori,Conception et analyse d"algorithmes 4

32

Algorithme non polynomial

On montre que le système suivant ànvariables donne lieu à un nombre d"étapes voisin de2n:max n? j=110 n-jxj(2 i-1? j=110 33

De l"obtention d"une solution

vers l"obtention de l"optimumSi on a un algorithme polynomial qui résout des systèmes d"inéquations linéaires,

alors on peut résoudre un problème d"optimisation linéaire en temps polynomialOn utilise la dualité

maxcx? yA≥c cx≥ybRobert Cori,Conception et analyse d"algorithmes 4 34

De l"existence d"une solution

vers l"obtention d"une solutionOn suppose que l"algorithmeAlg(S)donne pour résultattruesiSadmet une

solution etfalsesinonProcédure ReduitVariables(S) •J={1,2,...,n}•Pourj1= 1,2,...nfaire-Si Alg(? j?J\j1A J:=J\j1Robert Cori,Conception et analyse d"algorithmes 4 35

Remarques

•SiAlgest polynomialReduitVariablel"est aussi •LeJconstruit par la procédure est tel que :1.? j?JA

2.Pour toutj1?J?

j?J\j1A

Robert Cori,Conception et analyse d"algorithmes 4

36

Procédure ReduitEquation(S)

•I=∅•Pouri1= 1,2,...mfaire-Si Alg(? j?JA j?JA i,jxj≥bi;i?I? {i1})-Alors

I:=I? {i1}AprèsReduitEquationle système :?

j?JAi,jxj=bii?I?

Robert Cori,Conception et analyse d"algorithmes 4

37

On vérifie que le système réduit:?

j?JA i,jxj=bi?i?Iadmet une solution unique. S"il y a deux solutions on peut choisir une combinaison linéaire des deux qui : •a unxj= 0contredisant la minimalité deJ•satisfait une équation

j?JAi,jxj=bide plus contredisant la maximalité deI.La résolution du système réduit donne enO(n3)une solution du système

d"inéquations initial.Robert Cori,Conception et analyse d"algorithmes 4 38

Méthode de l"ellipsoïde

1. Réduction à la résolution de systèmes d"inéquations linéaires.

Si on sait résoudre les systèmes d"inéquations linéaires en temps polynomial, alors on sait résoudre un programme linéaire en temps polynomial.? ??maxcx x≥0et? ??minbu A

Tu≥c

u≥0??? A

Tu≥c

x,u≥0 cx≥buRobert Cori,Conception et analyse d"algorithmes 4 39

2. Résoudre un système d"inéquations.

SoitDle nombre total de bits dans l"écriture desai,jet desbien binaire. Si le 40
demi-ellipsoïde s"obtient en intersectantEavec un demi-espace limité par un hyperplan qui passant parc:hx≥hc. Tout demi-ellipsoïde est contenu dans un ellipsoïdeE?tel que 41

Principe de l"algorithme de l"ellipsoïde

Initialisation :E←la sphère?n

défini par la contrainte?D.•RemplacerEpar l"ellipsoïdeE?contenantDSortie :sicE?P, c"est une solution ; sinon, il n"y en a pasComplexité :polynomiale.

Robert Cori,Conception et analyse d"algorithmes 4

quotesdbs_dbs1.pdfusesText_1

[PDF] exercices corrigés de relativité générale pdf

[PDF] exercices corrigés de rmn 2d

[PDF] exercices corrigés de statistique ? deux variables pdf

[PDF] exercices corrigés de statistique descriptive avec rappels de cours pdf

[PDF] exercices corrigés de statistique descriptive bernard py pdf

[PDF] exercices corrigés de statistique descriptive problèmes exercices et qcm pdf

[PDF] exercices corrigés de statistique pdf

[PDF] exercices corrigés de statistiques mathématiques pdf

[PDF] exercices corrigés de thermochimie s2

[PDF] exercices corrigés de thermochimie s2 pdf

[PDF] exercices corriges de thermodynamique pdf

[PDF] exercices corrigés de thermodynamique pdf s1

[PDF] exercices corrigés de traitement des eaux pdf

[PDF] exercices corrigés de vibrations et ondes pdf

[PDF] exercices corrigés dérivées terminale s