[PDF] Programmation Linéaire - Cours 3 - u-bordeauxfr

View - Download Programmation Linéaire - Cours 3 - u-bordeauxfr

Previous PDF

Next PDF

Forme matricielleDualiteTheoremes

Programmation Lineaire - Cours 3

F. Clautiaux

francois.clautiaux@math.u-bordeaux1.fr

Universite Bordeaux 1

B^at A33 - Bur 265

Forme matricielleDualiteTheoremes

SommaireSimplex : forme matricielle

Forme matricielle

Dualite

Dualite faible / forte

Forme matricielleDualiteTheoremes

Notations matricielles

En forme standard :

maxcx s.c.Ax=b x0n+m avec c= (c1c2:::cn0 0:::0) ja1;1a1;2:::a1;n1j jb1j

A=ja2;1a2;2:::a2;n1jb=jb2j

j ............j... jam;1am;2:::am;n1j jbmj x= (x1x2:::xnxn+1:::xn+m)

Forme matricielleDualiteTheoremes

Partitionnement des indices

On peut partitionner les indices des variables en deux parties :

Ceux des variables en base :B

Ceux des variables hors-base :N

Cette partition peut-^etre eectuee dans chacune des contraintes : P n+m j=1ai;jxj=P j2Bai;jxj+P j2Nai;jxj=bipouri= 1; :::;n. D'un point de vue matriciel : partition des colonnes deAet des composantes des vecteurscetx: c= (cBcN)

A= (B N)

x= (xBxN) (on notera queBest une matrice carree)

Forme matricielleDualiteTheoremes

Dictionnaire au format matriciel

Exprimons les variables en base en fonction des variables hors-base :Ax=b,BxB+NxN=b ,xB=B1bB1NxN Possible uniquement siBest une matrice inversible.

En remplacantxBdans l'objectif, on obtient :

z=cx=cBxB+cNxN =cB(B1bB1NxN+cNxN =cBB1b+ (cNcBB1N)xN

On a : maxz=cBB1b+ (cNcBB1N)xN

s.c.xB=B1bB1NxN x B;xN0

Forme matricielleDualiteTheoremes

Solutions de base

Toute sous-matrice carreemmdeAinversible (Best une base deRm) est appeleematrice de base.A chaque matrice de baseBest associee une solution de base denie par un dictionnaire. maxz=cBB1b+ (cNcBB1N)xN s.c.xB=B1bB1NxN x B;xN0

Solution de base :xB=B1b

z=cBB1b

Condition de realisabilite :B1b0

Condition d'optimalite :cNcBB1N0

Forme matricielleDualiteTheoremes

Algorithme du simplex matriciel

On commence avec une solution de base realisable donnee par un dictionnaire : maxz=cBB1b+ (cNcBB1N)xN s.c.xB=B1bB1NxN x B;xN0 1. Si cN=cNcBB1N0, alors cette solution est optimale, STOP. 2. choisir une va riableentrante k2 Ntelle que (cN)k>0. 3. Si ( ai;k)i=1;:::;m= (B1N)k0, le probleme est non borne, STOP. 4.

Choisir une va riableso rtantes2 Btelle que

s= argminj2B bjaj;k=B1 j;:bB 1 j;:N:;k: aj;k>0 5.

Pivoter : B= (B n fsg)[ fkgetN= (N n fkg)[ fsget

retourner en 1.

Forme matricielleDualiteTheoremes

SommaireSimplex : forme matricielle

Dualite

Motivation

Primal / dual

Dualite faible / forte

Forme matricielleDualiteTheoremes

Motivation

Obtenir une borne superieure sur le prot maximum

Toute solution realisable donne uneborne inferieure (LB) sur le prot maximum. Uneborne superieure (UB)est utile pour juger de la qualite d'une solution realisable (voire prouver son optimalite si LB = UB).

Remarque :

Toute combinaison lineaire de contraintes du programme lineaire donne une contrainte valide (satisfaite par toutes les solutions realisables)

Forme matricielleDualiteTheoremes

Exemple du yaourt

max 4x1+ 5x2

2x1+x2800 (1)

x

1+ 2x2700 (2)

x

2300 (3)

x

1,x205(1))4x1+ 5x210x1+ 5x240004(2))4x1+ 5x24x1+ 8x228002(1) + 3(3))4x1+ 5x22500

Forme matricielleDualiteTheoremes

Exemple du yaourt

max 4x1+ 5x2

2x1+x2800 (1)

x

1+ 2x2700 (2)

x

2300 (3)

x

1,x205(1))4x1+ 5x210x1+ 5x240004(2))4x1+ 5x24x1+ 8x228002(1) + 3(3))4x1+ 5x22500

Forme matricielleDualiteTheoremes

Deuxieme exemple

(le PL n'est pas sous forme normale) max 4x1+ 2x2x3 x

1+x2+x310 (1)

x

2+x36 (2)

x

1x30 (3)

x

1,x2x30

Par exemple 2(1)2(3)

Forme matricielleDualiteTheoremes

Modelisation du probleme

Probleme :Trouver les meilleurs coecients multiplicatifs pour chaque contrainte an d'obtenir la meilleure borne superieure. A chaque contraintei= 1; :::;3, on associe une variableyi. La combinaison lineaire doit ^etre telle que le coecient obtenu pour chaque variable doit ^etre plus grand que le coecient de la variable dans l'objectif. On cherche a minimiser le membre de droite de la contrainte issue de la combinaison lineaire.

Forme matricielleDualiteTheoremes

Modelisation du probleme

Max 4x1+ 5x2

2x1+x2800 (y1)

x

1+ 2x2700 (y2)

x

2300 (y3)

x

1,x20Min 800y1+ 700y2+ 300y3

2y1+y24

y

1+ 2y2+y35

y

1,y2,y30Solution optimale :y1= 1,y2= 2,y3= 0 et opt = 2200.

Forme matricielleDualiteTheoremes

Modelisation du probleme

Max 4x1+ 5x2

2x1+x2800 (y1)

x

1+ 2x2700 (y2)

x

2300 (y3)

x

1,x20Min 800y1+ 700y2+ 300y3

2y1+y24

y

1+ 2y2+y35

y

1,y2,y30Solution optimale :y1= 1,y2= 2,y3= 0 et opt = 2200.

Forme matricielleDualiteTheoremes

Modelisation du probleme

Max 4x1+ 5x2

2x1+x2800 (y1)

x

1+ 2x2700 (y2)

x

2300 (y3)

x

1,x20Min 800y1+ 700y2+ 300y3

2y1+y24

y

1+ 2y2+y35

y

1,y2,y30Solution optimale :y1= 1,y2= 2,y3= 0 et opt = 2200.

Forme matricielleDualiteTheoremes

Primal / Dual

Les PL vont toujours par paires :

Primal :

max P jcjxj s.c.P jai;jxjbipouri= 1; :::;m x j0 pourj= 1; :::;n

Dual :

min P ibiyi s.c.P iai;jyicjpourj= 1; :::;n y i0 pouri= 1; :::;m

A venir : si solutions optimales alors egales

Forme matricielleDualiteTheoremes

Primal / Dual : forme matricielle

Les PL vont toujours par paires :

Primal :

maxcx s.c.Axb x0n

Dual :

minby s.c.A>yc y0m

Forme matricielleDualiteTheoremes

Interpretation economique du dual

Sans ressource, le prot serait nul. L'idee est d'essayer d'evaluer la contribution de chaque ressource au prot observe. Dans ce contexte, les variables y i0 pouri= 1; :::;m representent les valeurs unitaires des ressourcesi:yiest la mesure de la contribution d'une unite deidans le prot. C'est donc aussi le prix auquel on evalue la ressourcei(prix auquel on serait pr^et a vendre la ressource au lieu de l'utiliser).

Forme matricielleDualiteTheoremes

Interpretation economique du dual

Un systeme de prixy(auquel on serait pr^et a vendre nos ressources) pour ^etre acceptable doit compenser le prot qu'on aurait pu faire en utilisant ces ressources. Il fautP iai;jyicjpourj= 1; :::;n ce qu'on interprete aussi comme le fait que la valeur des ingredients doit justier entierement le prot attribue a chaque produit. L'acheteur de nos ressources veillera a minimiser le co^ut total d'achat

MinimiserP

ibiyi

Forme matricielleDualiteTheoremes

Interpretation economique du dual

Un systeme de prixy(auquel on serait pr^et a vendre nos ressources) pour ^etre acceptable doit compenser le prot qu'on aurait pu faire en utilisant ces ressources. Il fautP iai;jyicjpourj= 1; :::;n ce qu'on interprete aussi comme le fait que la valeur des ingredients doit justier entierement le prot attribue a chaque produit. L'acheteur de nos ressources veillera a minimiser le co^ut total d'achat

MinimiserP

ibiyi

Forme matricielleDualiteTheoremes

Int. eco. de la solution optimale du dual

A l'optimum :

z =P jcjxj=P ibiyiP jai;jxjbietP iai;jyicj Les multiplicateurs optimaux (solution optimale du dual) expliquent la responsabilite de chacune des contraintes de capacite en ressource dans la limitation du prot. Ces valeurs duales indiquent \localement" de combien augmenterait le prot par unite d'augmentation des ressources associees. yiest une mesure de l'augmentation marginale du prot par unite d'augmentation debi. y i= lim!0z(bi+)z(bi)

Forme matricielleDualiteTheoremes

Int. eco. de la solution optimale du dual

A l'optimum :

z =P jcjxj=P ibiyiP jai;jxjbietP iai;jyicj Les multiplicateurs optimaux (solution optimale du dual) expliquent la responsabilite de chacune des contraintes de capacite en ressource dans la limitation du prot. Ces valeurs duales indiquent \localement" de combien augmenterait le prot par unite d'augmentation des ressources associees. yiest une mesure de l'augmentation marginale du prot par unite d'augmentation debi. y i= lim!0z(bi+)z(bi)

Forme matricielleDualiteTheoremes

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