Cours de Programmation Lineaire.pdf

7/30/2019 Cours de Programmation Lineaire.pdf

1/28

Annee 2007

Departement des Licence de Mathematiques L3Sciences et Techniques Henri Bonnel

Cours de Programmation Lineaire

1 Introduction

1.1 Un exemple tres simple

On se propose de trouver le modele mathematique du probleme de production propose dans lexercice

no 1 :

Considerons une usine ou, grace a la presence de deux chanes, il est possible dassembler simultanement

deux modeles de voiture. On peut produire 100 voitures du premier type en 6 heures. On peut aussi pro-duire 100 voitures du second type en 5 heures seulement. Le nombre dheures de travail est au maximumde 60 heures par semaine.Les voitures produites sont enlevees une fois par semaine et doivent etre stockees dans un depot de 15 000m2. Une voiture du type 1 occupe 10 m2et une voiture du type 2 occupe 20 m2.La marge (difference entre le prix de vente et le cout de la production) sur le premier type de voiture estde 50 000 F par vehicule tandis que, sur le second, el le est de 45 000 F par vehicule. La demande pourle premier type de voiture est limitee a 800 unites par semaine ; la demande pour le deuxieme type est

tellement forte quon peut la considerer comme illimitee.Combien de voitures de chaque type le constructeur doit-il produire par semaine pour maximiser son profitnet?

Choix des variables de decision.

Posonsx1 = nombre de milliers de voitures de type 1 produites par semainex2 = nombre de milliers de voitures de type 2 produites par semaine.

Formulation des contraintes.

On constate (apres simplifications) que

6x1 + 5x2 610x1 + 20x2 15

x1 0, 8x1, x2 0

Determination de lobjectif.

Posons z = le profit net (marge) exprime en MF. On a

z = 50x1 + 45x2

1


2/28

Donc on est amenes a resoudre le probleme (programme) suivant(i) :

max z = 50x1 + 45x2 s.c.

6x1 + 5x2 610x1 + 20x2 15

x1 0, 8x1, x2 0

1.2 Solution graphique dun programme lineaire en deux variables

On constate que lensemble des points du plan P rapporte a on repere (orthonorme pour la beaute de laforme mais pas necessaire !) {O,i,j} verifiant les contraintes est un polygone (pentagone) quon appellerapolygone (ou region) admissible (ou realisable ). La famille de droites disovaleur (dz)zR donnees par

z=0z=40

z*=zmax=360/7

P(9/14;3/7)

0,8

1,5

1,2

x1

x2

O

Fig. 1 Polygone admissible et droites disovaleur

dz : 50x1 + 45x2 = z

represente une famille de droites paralleles (car elles ont toutes le meme coefficient directeur = -50/45)et les points qui se trouvent sur une droite fixee dz0 representent les points qui correspondent a la memevaleurs du benefice z = z0. Dans la figure 1 on a represente les droites correspondant a z = 0, z = 40 et ala plus grande valeur dez pour laquelle la droitedz a une intersection non vide avec lensemble realisableautrement dit, la plus grande valeur de z pour laquelle il existe une decision admissible (realisable) qui

assure cette performance. Donc la valeur optimale zmax =

360

7 ce qui correspond a la solution optimale(x1, x

2) = (

9

14,

3

7). A noter que, en deplacant la droite dz vers la gauche la valeur de z diminue, tandis

que, en deplacant dz vers la droite, la valeur de z augmente.

On remarquera que :

(a) La solution optimale est un sommet du polygone realisable, et dans cet exemple elle est unique.

(b) Si la droite dz etait parallele au cote ou loptimum est atteint, alors il y aura deux sommets (lesextremites du cote optimal) correspondants a des solutions optimales. Donc dans tous les cas ou il

(i)s.c. signifie

sous les contraintes

2


3/28

existe une valeur optimale de z, il existe toujours au moins un sommet correspondant a une solutionoptimale.

(c) Le long dun cote du polygone, la valeur de lobjectif peut etre soit constante ; soit strictementcroissante, soit strictement decroissante.

On peut donc suggerer lalgorithme suivant :

(i) Choisir comme point de depart un sommet x du polygone admissible.

(ii) Determiner les cotes passant par ce sommet x. Trouver un cote le long duquel z crot. Sil ny apas, STOP : le x courant est optimal.

(iii) Determiner le sommet y a lautre bout du cote et poser x = y. Retour en (ii).

Evidemment il y a des exemples ou lensemble realisable est vide (voir lexo 3. E.) ou dautres ou il nya pas un valeur optimale finie, i.e. zmax = + quand on peut augmenter autant que lon veut la valeurde z (la region realisable nest pas bornee, voir exo 3.C.) ou zmin = (exo 3.D.).

1.3 La forme generale dun probleme de programmation lineaire

Un probleme de programmation lineaire est defini par les elements suivants :

Les variables de decisions x1, x2, . . . , xn R. Certaines variables sont toujours positives xi 0, i I+, dautres sont toujours negatives xi 0, i I et les autres peuvent avoir nimporte quel signexi R, i I \ (I+ I) (avec I = {1, . . . , n}, I+, I I, I+ I = ).

Les contraintes qui peuvent etre de type :

(i) inegalites :n

j=1

aijxj bi, i = 1, . . . , m

(ii) egalites :n

j=1aijxj = bi, i = m + 1, . . . , m + p

(iii) inegalites :n

j=1

aijxj bi, i = m + p + 1, . . . , m + p + q.

Les nombres aij et bi sont supposes connus.

On appelle solution admissible tout element (x1, . . . , xn) Rn verifiant toutes les contraintes. Len-

semble de solutions admissibles sera dit ensemble (ou polyedre si borne) admissible. lobjectif (critere ou indice de performance, ou fonction economique etc.) donne par :

z =n

j=1cjxj

ou cj sont des nombres connus.

Le but dun probleme doptimisation est doptimiser lobjectif sur lensemble admissible.

optimiser

{

maximiser

,

minimiser

}.

On peut donc chercher soit a minimiser lobjectif sur lensemble admissible, donc on a un probleme deminimisation, soit a le maximiser , et dans ce cas on a un probleme de maximisation.

Lorsquon utilise un logiciel capable a resoudre des programmes lineaires il faut preciser soigneusementtous ces elements.

3


4/28

1.4 La forme standard dun programme lineaire

Si dans le probleme de programmation lineaire sous forme generale expose dans la section precedente ona :

(a) I+ = I i.e. toutes les variables sont positives ;

(b) m = q = 0, i.e. il ny a pas de contraintes de type inegalite ;

(c) le probleme est de maximisation

alors on dit que le programme est donne sous la forme standard. En ecriture matricielle (voir le chapitresuivant pour les rappels) on a

(PS)max z = cx

s.c.

Ax = b

x 0

ou A = (aij) Mp,n(R), b =

b1b2...

bp

, c = [c1 c2 cn] et x =

x1x2...

xn

.

Proposition 1. Tout programme lineaire peut etre mis sous la forme standard.

Demonstration. En effet, sil y a des variables negatives (i.e.I = ) alors on remplace xi par xi = xi, i I.Evidemment xi 0 i I. Sil y a des variables sans contraintes de signe (i.e. I \ (I+ I) = ) alors, pour touti I \ (I+ I) on pose xi = x

+i x

i ou x+i = max(xi, 0) et x

i = max(xi, 0). Les nouvelles variables x+i , x

i sontevidemment positives. Donc par ces changements toutes les nouvelles variables seront positives. Les contraintes de type

on les transforme dabord en inegalites de type en les multipliant par -1. Une inegalites de la forme

nXj=1

aijxj bi(1)

sera transforme en une egalite en introduisant une nouvelle variable positive ei dite variable decart par les relations

ei +

nXj=1

aijxj = bi, ei 0.(2)

Il est aise de voir que les relations (1) et (2) sont equivalentes, donc en remplacant (1) par (2) (et on va proceder de cettemaniere avec toutes les contraintes de type inegalite) on obtient un probleme equivalent mais sous la forme standard.

1.5 La forme canonique dun programme lineaire

Si dans le probleme de programmation lineaire sous forme generale expose dans la section 1.3 on a :

(a) I+ = I i.e. toutes les variables sont positives ;

(b) p = q = 0, i.e. il ny a pas de contraintes de type egalite, ni de type inegalite ;

(c) le probleme est de maximisation

alors on dit que le programme est donne sous la forme canonique. En ecriture matricielle on a

(PC)max z = cx

s.c.

Ax b

x 0

ou A = (aij) Mm,n(R), b =

b1b2...

bm

, c = [c1 c2 cn] et x =

x1x2...

xn

.

4


5/28

Proposition 2. Tout probleme de programmation lineaire peut etre mis sous la forme canonique.

Demonstration. On transforme les variables qui ne sont pas positives en variables positives comme dans la demonstrationde la proposition 1. Les contraintes de type egalites on les ecrit comme deux inegalites :

u = v [u v et u v].

Ensuite, les contraintes de type

on les transforme en inegalites de type

en les multipliant par -1.

2 Un peu dalgebre lineaire

2.1 Generalites

On note Mm,n(K) lensemble de matrices de la forme A =

a11 a12 . . . a1na21 a22 . . . a2n...

......

am1 am2 . . . amn

, a coefficients dans

K = Z,Q,R. On ecrira pour simplifier A = (aij) ou aij est lelement de A situe a lintersection de la lignei et de la colonne j. La somme de deux matrices (aij) + (bij) = (aij + bij) et le produit dune matriceA par un nombre R defini par (aij) = (aij) verifient toutes les bonnes proprietes ce qui nous

permet de dire

Mm,n(R) a une structure deR espace vectoriel.

Le produit de la matrice A Mm,n(R) par la matrice B Mn,p est une matrice C = AB Mm,p(R)definie par cij =

nk=1 aikbkj . La multiplication des matrices nest pas commutative. Elle a par contre

toutes les autres

bonnes proprietes

(associativite, lexistence de lelement neutre : la matrice carree

notee I ou In =

1 0 . . . 00 1 . . . 0...

......

0 0 . . . 1

Mn,n(R), distributivite par rapport a la somme ....)

Une matrice carree A est dite inversible sil existe un matrice B telle que

AB = BA = I.

Dans ce cas la matrice B est unique (prouvez le !) et sera notee B = A1.

Proposition 3. Soit A Mn,n(R). Les affirmations suivantes sont equivalentes :

(i) A est inversible.

(ii) det(A) = 0(ii)

(iii) Il existe B Mn,n(R) tel que AB = In

(iv) Il existe C Mn,n(R) tel que CA = In

Les matrices ligne de M1,n(R) on les appelle vecteurs ligne et les matrices colonne de Mn,1(R) sontappelees vecteurs colonne. Dans la suite, quand on fait des operations avec des vecteurs on sous-entendsvecteurs de meme type.

Definition 1. Une famille de vecteurs (vi)iI (avec I un ensemble fini) sera dite liee sil existe i I et j R, j = i tels que

vi =

jI\{i}

jvj.

(ii)On suppose que le lecteur est familiarise avec la notion de determinant.

5


6/28

libre si elle nest pas liee, cest-a-dire

i R,iI

ivi = 0 = i = 0 i I.

generatrice si tout vecteur v secrit comme une combinaison lineairedes vecteurs de la famille, i.e. pourtout v il existe des nombres i tels que

v =iI

ivi.

Definition 2. Lespace vectoriel V engendre par une famille de vecteurs (vi)iI avec I = {1, . . . , p} estlensemble de toutes les combinaisons lineaires de cette famille et sera notee Vect (v1, . . . , vp). Donc

V = Vect (v1, . . . , vp) = {1v1 + + pvp| 1, . . . , p R}.

Exemple 1. Lespace V = Mn,1(R) est engendre par les colonnes de la matrice unite In, et lespaceW = M1,n(R) est engendre par les lignes de la matrice In. (Prouvez le !)

Definition 3. La famille de vecteurs (e1, . . . ek) est une base de lespace vectoriel V si elle est libre etgeneratrice.

Theoreme 1. Soit V un espace vectoriel (V Mn,1(R) ou V M1,n(R)) qui possede une base ayant pelements. Alors :

(a) Toute autre base de V a le meme nombre p delements. Ce nombre sera dit la dimension de V etsera note p = dim V.

(b) Toute famille libre de V a au plus p elements.

(c) Toute famille generatrice de V a au moins p elements.

(d) Toute famille libre de V ayant exactement p elements est une base de V.

(d) Toute famille generatrice de V ayant exactement p elements est une base de V.

(e) Toute famille libre est contenue dans une base (i.e. on peut completer une famille libre pour obtenirune base).

(f ) De toute famil le generatrice on peut extraire une base.

Definition 4. Le rang dune matrice A est la dimension de lespace vectoriel engendre par les colonnesde A. Donc, si A = [A1 A2 An] Mp,n(R), avec Aj Mp,1(R), alors

rang (A) = dim Vect (A1, . . . , An)

Remarque 1. Evidemment on arang (A) min(p, n).

Theoreme 2. Soit A Mm,n(R). Les affirmations suivantes sont equivalentes :(i) rang (A) = r.

(ii) Il existe un mineur dordre r de A non nul et tous les mineurs dordrer + 1 (sil y en a !) sont nuls.

(iii) Lespace engendre par les lignes de A est de dimension r.

(iv) Il existe une sous-matrice carree deA dordrer inversible et toutes les sous- matrices carrees dordrer + 1 (sil y en a) sont non inversibles.

Remarque 2. Si A Mn,n(R) est une matrice carree, alors

rang (A) = n det(A) = 0 A est inversible.

6


7/28

2.2 Transformations elementaires et les matrices watsoniennes(ii)

Il existe trois types de transformations elementaires sur les lignes dune matrice A Mp,n(R), a savoir

(a) permutation des lignes i et j et on ecriraLi Lj

(b) multiplication de la ligne i par un nombre non nul R :

Li Li

(c) laddition a la ligne i de la ligne j multipliee par R :

Li Li + Lj.

Definition 5. Soient : Hij la matrice obtenue en appliquant la transformation Li Lj a la matrice unite Ip Hi() la matrice obtenue en appliquant la transformation Li Li a la matrice unite Ip (avec = 0) Hij() la matrice obtenue en appliquant la transformation Li Li + Lj a la matrice unite Ip.

Theoreme 3. Les matrices Hij, Hi() et Hij() sont inversibles et chaque transformation elementaire(a), (b), (c) appliquee a la matrice A peut etre realisee en multipliant a gauche la matrice A par lamatrice watsonienne correspondante. Par exemple la matrice A = Hij()A est la matrice obtenue de Aen faisant Li Li + Lj .

Demonstration. Un b on exercice (facile !) pour ceux qui apprecient les matrices !

2.3 Les systemes lineaires et les operations de pivotage

2.3.1 Les systemes lineaires sous-determines et les variables de base

On va considerer un systeme degalites lineaires sous-determine i.e. le nombre m dequations est inferieur

au nombre n dinconnues qui seront notees x1, . . . , xn :

(S)

a11x1 + a12x2 + . . . + a1nxn = b1a21x1 + a22x2 + . . . + a2nxn = b2...

...am1x1 + am2x2 + . . . + amnxn = bm.

Si on considere

x =

x1...

xn

A = (aij) et b =

b1...

bm

alors le systeme (S) secritAx = b.(3)

On va supposer que le rang de la matrice A = [A1 An] (avec Ai Mm,1(R) la colonne i de A) estmaximum, i.e.

rang (A) = m.

Definition 6. On appelle ensemble de base (de la matrice A) tout ensemble ordonne ayant m elementsB = {i1, . . . , im} {1, . . . , n}, tel que les colonnes (Ai)iB forment une base de Vect (A1, . . . , An).

(iii)Lappellation watsonien vient de Dr. Watson liee a la notion elementaire et a ete introduite par Pierre Brondeau

7


8/28

On va noter AB = [Ai1 Aim] la matrice carree ayant les colonnes Ai, i B (donc AB est inversible !)

et on va dire que les variables (xi)iB sont les variables de base, et on va noter xB =

xi1...

xim

la matrice

colonne formee par les variables de base. Notons N = {1, . . . , n} \ B lensemble des indices hors base(toujours ordonne) et dune maniere analogue AN la matrice formee par les colonnes de A en dehors dela base A

Bet x

Nla matrice colonne des variables hors base. Donc, comme

Ax = [A1 . . . An]

x1...xn

= n

i=1

Aixi =iB

Aixi +iN

Aixi = ABxB + ANxN

on peut ecrire le systeme (S) sous la forme

ABxB + ANxN = b.(4)

Proposition 4. Soit T Mm,m(R) inversible et B {1, . . . , n}, |B| = m(iv). Alors :1. Les systemes Ax = b et T Ax = T b sont equivalents (i.e. ils ont les memes solutions.)

2. B est un ensemble de base de A B est un ensemble de base de T A.

Demonstration. 1. Soit x verifiant Ax = b. En multipliant cette egalite par T a gauche on obtient que x verifie lesysteme T Ax = T b. Reciproquement, si x verifie T Ax = T b, en multipliant cette egalite a gauche par T1 on obtient que xverifie le systeme Ax = b.2. Il suffit de remarquer que T AB = (T A)B ce qui entrane que AB est inversible (T A)B est inversible.

En multipliant legalite (4) a gauche par A1B , on obtient grace a la proposition 4 que le systeme (3) estequivalent au systeme

xB = A1B b A

1B ANxN.

Donc

on peut toujours exprimer les variables de base en fonction de variables hors base.

En considerant xN = 0 on obtient xB = A1B b et cette solution joue un role fondamental dans la methode

du simplexe.

Definition 7. La solution (x1, . . . , xn) verifiant

xN = 0; xB = A1B b

sera dite solution de base associee a lensemble de base B.

Geometriquement une solution de base correspond a un sommet du polyedre (generalisation du polygoneen dimension 2) defini par Ax = b (plus correctement on doit dire surface polyedrale lorsque cetensemble nest pas borne).

(iv)|B| designe le nombre delements (le cardinal) de lensemble B.

8


9/28

2.3.2 Pivotage

Definition 8. Deux ensembles de base B et B sont dits adjacentssil different par un seul element, i.e.il existe i B, j B, i = j tels que B = B {j} \ {i}.(v) Autrement dit on peut passer de B a B enechangeant dans B lindice de base i = ip par lindice hors base j (avec 1 p m).

Loperation de passage du systeme xB = A1B b A

1B ANxN au nouveau systeme xB = A

1B b

A1

B ANxN sappelle pivotage. Notons par A (resp. A

) la matrice de coefficients du systeme correspondant

a lensemble de base B (resp. B) et par b (resp. b) le second membre (donc AB = Im, AN = A1B AN et

AB = Im, AN = A1B AN). A noter que

Ax = b, Ax = b

sont des systemes equivalents au systeme (S) ayant la propriete que

les variables de base (xk)kB (resp. (xk)kB) apparaissent chacune dans une seule equation et ellesont comme coefficient 1.

Lidee est de changer la variable de base xi par la variable hors base xj dans le systeme Ax = b de

sorte que xj devienne une variable de base (et evidemment xi quittera la base). On dit que xj est lavariable entrante tandis que xi est la variable sortante. Les autres variables de base restent dans la base.Pour que cet echange soit possible il faut que lequation p contenant la variable xi (avec le coeff. api = 1)contienne aussi la variable xj avec un coefficient apj = 0 (autrement B = B {j} \ {i} nest pas unensemble de base !(vi)). Donc on a

api = 1, apj = 0.

Lelement apj = 0 sappelle pivot. Pour pivoter on doit effectuer les operations suivantes :

(i) On divise la ligne du pivot (i.e. la ligne p de A) par le pivot, i.e. on multiplie A et b a gauche par lamatrice inversible Hp(1/apj).

(ii) On elimine la variable xj de toutes les autres equations (sauf lequation p) en faisant Lk LkakjLppour tout k {1, . . . , m} \ {p}. Cela revient donc a multiplier successivement a gauche par lesmatrices inversibles Hkp(akj).

Donc apres toutes ces transformations on obtient les matrices A = TA et b = Tb avec

T =

k=p

Hkp(akj)

Hp(1/apj).

On a bien AB = AB = Im car la seule operation concernant la ligne k (avec k = p) de A a ete

Lk Lk akjLp ce qui na aucun effet sur les elements akl, l B \ {i}, et dautre part la colonne dupivot devient la colonne correspondante de Im. Ceci montre que A = A

.

(v)Comme les ensembles B, B sont supposes ordonnes, alors lelement j de B prend la place occupee par i dans B et tousles autres elements ne changent pas de position.(vi)En effet, grace a la proposition 4 on a que la matrice A admet les memes ensembles de base que la matrice A. Alors les

colonnes (Ak)kB doivent former une famille libre, i.e. AB est inversible. Si le coefficient apj de xj dans lequation i estnul, alors la ligne p de la matrice AB serait nulle, donc la matrice ne serait pas inversible.

9


10/28

En fait le passage des matrices A, b aux matrices A, b seffectue grace aux formules suivantes :

akl = akl aplakj

apjk = p

apl =apl

apj

bk = bk bpakj

apjk = p

bp =bp

apj

(5)

Ces formules sont faciles a retenir avec la regle du rectangle :

akl~

akj~

apl

~pja

~

Fig. 2 Pivotage : la regle du rectangle.

On doit former un rectangle ayant le pivot apj comme sommet et lelement a modifier comme sommetoppose. Ensuite on doit soustraire de lelement a modifier akl (ou bk) le produit des elements sur ladiagonale qui ne contient pas le pivot (le pivot est entoure dun carre) divise par le pivot.La colonne du pivot doit etre completee par des zeros (a part le pivot qui devient 1).

3 Lalgorithme du simplexe

Lalgorithme (tres important vu ses multiples applications !) considere dans ce chapitre, decouvert en

1947 par lamericain G.B. Dantzig, a fete ces 50 ans a EPFL de Lausanne en 1997 a loccasion du 16thInternational Symposium on Mathematical Programming en la presence de son auteur !

3.1 Un exemple simple

Considerons le programme lineairemax z = 3x1 + 4x2

s.c.

x1 + 2x2 21x1 + x2 12

x1, x2 0

10


11/28

Transformons ce programme en un programme equivalent mis sous la forme standard

max z = cx

s.c.

Ax = b

x 0

(voir le chapitre precedent). Donc en introduisant les variables decart x3, x4 on obtient le programmeequivalent :

max z = 3x1 + 4x2

s.c.

x1 + 2x2 + x3 = 21x1 + x2 + x4 = 12

x1, x2, x3, x4 0

On a donc

A =

1 2 1 01 1 0 1

, b =

2112

, c = [3 4 0 0].

On constate que B = {3, 4} est un ensemble de base. La solution de basecorrespondante est x1 = 0, x2 =0, x3 = 21, x4 = 12. Cette solution est egalement admissible, donc sera dite solution de base admissible.La valeur de lobjectif associee est z = 0. On va augmenter la valeur de z en introduisant dans la basela variable x2 (car x2 a le plus grand coefficient dans z, mais evidemment on aurait pu introduire x1egalement).

Le choix de la variable entrante. Donc la variable entrante (dans notre cas x2) est choisie en utili-sant la regle :

le coefficient dans la fonction z de la variable entrante est le plus grand des coefficients (posi-tifs)(vii) de z.

Ainsi on espere une augmentation plus forte de z par rapport a dautres choix de variables en-trantes.

Le choix de la variable sortante. On va augmenter la valeur de x2 le plus possible tout en restantdans lensemble admissible. Les autres variables hors base (dans notre cas x1) sont maintenuesnulles. Comme x3 et x4 sont positifs on doit avoir

21 2x2 0 et 12 x2 0,

donc x2 min(21/2, 12) = 21/2.

On constate que la plus grande valeur de x2 satisfaisant ces inegalites est x2 = 21/2. Cela entranex3 = 0, x4 = 3/2. La solution x1 = 0, x2 = 21/2, x3 = 0, x4 = 3/2 pourrait correspondre aune solution de base associee a B = {2, 4} (car les variables hors base sont nulles dans une so-lution de base). Autrement dit la variable sortante devrait etre x3. Remarquons que (si tout est ok !)

la variable sortante correspond au plus petit des rapports (positifs) entre les elements du secondmembre du systeme et les coefficients associes a la variable entrante.

(vii)Si tous les coeff. de z sont negatifs ou nuls alors la solution de base est optimale, voir plus loin.

11


12/28

Montrons que dans cet exemple on peut effectuer ce choix. On choisit donc comme pivot le co-efficient de la variable entrante x2 correspondant a la variable sortante x3 (donc de la premiereequation, la variable sortante ne peux pas apparatre dans plusieurs equations, car elle est (etait)une variable de base). Alors, apres pivotage (utiliser la regle du rectangle) ce qui consiste en fait afaire L1

12L1 et apres L2 L2 L1, on obtient le systeme

12x1 + x2 + 12x3 = 212

12x1

12x3 + x4 =

32 .

On constate donc que B = {2, 4} est bien un ensemble de base et la solution de base associeex1 = 0, x2 = 21/2, x3 = 0, x4 = 3/2 est admissible.

Lob jectif reduit. On va toujours exprimer lobjectif en fonction de variables hors base. Cela estpossible car les variables de base sont donnees en fonction de variables hors base. On pourraitcalculer z en posant x2 = 21/2 1/2x1 1/2x3 (x4 ce nest pas necessaire). Mais en fait en ecrivantlegalite definissant lobjectif comme une equation 3x1 + 4x2 = z (avec z comme second membre !)on peut obtenir les coefficients par pivotage. On va noter cette equation Lz et on va remarquer que

on peut lecrire comme3x1 + 4x2 = z z0

avec z0 = la valeur de lobjectif pour la solution de base associee au systeme respectif (dans ce cas(x1 = 0, x2 = 0, x3 = 21, x4 = 12), donc z0 = 0.) Et cela est possible toujours car en exprimantz en fonction de variables hors base seulement, celles-ci sont toutes nulles dans la solution de basedonc on obtient que 0 = z z0, ce qui correspond bien a la valeur de z associee a la solution de base.Donc dans notre cas, apres pivotage (ce qui revient a Lz Lz 4L1) on obtient x1 2x3 = z 42.Donc la valeur de z pour la nouvelle solution de base est z = 42 superieure a la valeur precedente(z = 0).Ecrivons le nouveau programme :

12x1 + x2 +

12x3 =

212

12x1

12x3 + x4 =

32

x1 2x2 = z 42

On constate quil est encore possible daugmenter z en augmentant x1. Donc on va choisir comme variableentrante x1, et pour determiner la variable sortante on calcule min(21/2 : 1/2; 3/2 : 1/2) = 3 donc ilsagit de la deuxieme equation ce qui correspond a la variable de base x4. Donc le pivot est 1/2 le coefficientde x1 dans la deuxieme equation. On doit effectuer les transformations L2 2L2, L1 L1

12L2,

Lz Lz 3L2. On obtient

x2 + x3 x4 = 9

x1 x3 + 2x4 = 3

x3 2x4 = z 45

On constate que le nouvel ensemble de base est {1, 2} la solution de base est (x1 = 3, x2 = 9, x3 =0, x4 = 0) et que

tous les coefficients de z sont negatifs donc la solution de base est optimale.

12


13/28

En effet, notre nouveau systeme est equivalent au systeme initial

x1 + 2x2 + x3 = 21

x1 + x2 + x4 = 12

3x1 + 4x2 = z

Alors pour toute solution admissible on doit avoir x3 0, x4 0 donc

z(x1 = 3, x2 = 9, x3 = 0, x4 = 0) = 45 45x32x4 = z(x1, x2, x3, x4) (x1, x2, x3, x4) admissible.

Donc on a bien zmax = 45 et x1 = 3, x

2 = 9 est la solution optimale du programme initial (ou il faut

ajouter x3 = 0, x4 = 0) pour le programme transforme sous la forme standard.

Exercice 1. Resoudre le meme probleme par la methode geometrique et comparer avec les etapes parcourues

dans la methode du simplexe.

Les calculs precedents sorganisent sous la forme des tableaux :

x1 x2 x3 x4 s.m. v.d.b.

1 2 1 0 21 x31 1 0 1 12 x43 4 0 0 0 z12 1

12 0

212 x2

12 0

12 1

32 x4

1 0 2 0 42 z

0 1 1 1 9 x21 0 1 2 3 x10 0 1 2 45 z

3.2 Le cas general

Considerons un programme standard et supposons connu un ensemble de base B = {i1, . . . , im} admis-sible. Notons N = {j1, . . . jnm} = {1, . . . , n} \ B lensemble hors base. On peut donc admettre que leprogramme est donne sous la forme reduite associee a lensemble de base B :

max z = cx

s.c.

xB + A

1B ANxN = A

1B b

xB 0, xN 0

On a

z = cx =n

i=1

cixi =iB

cixi +iN

cixi = cBxB + cNxN

avec cB = [ci1 cim] et cN = [cj1 cjnm]. Posons aussi AN = A1B AN et b = A

1B b. On a xB =

ANxN + b doncz = (cN cBAN)xN + cB b = dNxN + zB

13


14/28

avec dN = cN cBAN et zB = cB b. Donc le probleme consiste a maximiser z sachantxB + ANxN = b

dNxN = z zB

et que xN 0, xB 0. Lhypothese B ensemble de base admissible signifie que b 0. A noter que lasolution de base est donnee par xN = 0, xB = b et la valeur de lobjectifz associee a cette solution est zB.

Le tableau du simplexe associe a la base B est (a une permutation de colonnes pres) de la forme :

xB xN s.m. v.d.b.

Im AN b xB

0 dN zB z

On constate que la premiere colonne du tableau est inutile ! Donc en pratique il suffit de garder que letableau

xN s.m. v.d.b.

AN b xB

dN zB z

mais, pour la commodite du calcul manuel, on va utiliser le tableau complet.

Rappelons nous que, une fois etablit le pivot, le passage dun tableau simplexe au tableau suivant seffectueen utilisant les regles :

(i) On divise la ligne du pivot par le pivot

(ii) Tous les autres elements du nouveau tableau (y compris le second membre ou la ligne de z) sob-tiennent en utilisant la regle du rectangle (on peut alleger les calculs en sachant que les colonnesdes variables de base corresponds aux colonnes de la matrice unite).

Definition 9. 1. Un ensemble (solution) de base est dit non degenere si

A1B b > 0 cest-a-dire le second membre du systeme reduit b > 0

autrement dit si toutes les variables de base ont des valeurs strictement positives dans la solution de basexB > 0.

2. Un programme lineaire est non degenere si toute solution de base admissible est non degeneree.

Theoreme 4. (Critere doptimalite) Si

dN 0

alors la solution de base admissible xN = 0, xB = b est optimale.

Demonstration. Soit (x1, . . . , xn) une solution admissible quelconque et soit (x1, . . . , xn) la solution de base associeea B. Comme xi 0 i, on a

z(x1, . . . , x

n) = zB zB + dNxN = z(x1, . . . , xn).

14


15/28

Si le critere doptimalite nest pas verifie on va proceder soit a une iteration, soit on vadecouvrir que sup z = +.

Supposons maintenant que dn 0. Cela signifie quil existe au moins une composante dj de dN (avecj N) strictement positive.

Le choix de la variable entrante

Considerons alors lindice j N tel que

dj = max{dk| k N}.

On a les possiblites suivantes :

(a) akj 0 k = 1, . . . , m .

Dans ce cas

Lensemble admissible est non borne et sup z = +

En effet, on constate que (x1, . . . , xn) avec xk = 0 k N \ {j}, xj = t et xB = b tAj est unesolution admissible pour tout t > 0. On a z(x1, . . . , xn) = zB + tdj + quand t +.

(b) Il existe k {1, . . . , m} tel que akj > 0.

Dans ce cas on va proceder a une iteration, la variable entrante etant xj. On va supposermaintenant que :

lensemble de base B est non degenere

Le choix de la variable sortante xi (avec i = ip) est determine dapres la regle suivante :

p verifiebp

apj= min{

bkakj

| akj > 0}

En effet, en utilisant cette regle on constate que, en effectuant le pivotage avec le pivot apj, la nouvellesolution de base donnee par xN = 0 et xB = b

est admissible car, dapres les formules (5) on aura

bk 0 pour tous les k grace a la regle utilisee (verification tres simple : exercice !) Montrons que par cetteiteration la valeur de z augmente. En effet notons (x1, . . . , x

n) la solution de base apres literation. On

a donc xk = 0 k N \ {j} et xj = b

j 0 avec inegalite stricte si le choix de la ligne du pivot (i.e. dela variable sortante) est unique. En effet, dans ce cas pour tout l = p tel que alj > 0 on a

blalj

>bp

apj

ce qui entrane grace a (5) que

bl = alj

bl

alj

bpapj

> 0

15


16/28

et

bp =bp

apj> 0.

Pour les autres indices l pour lesquels alj 0 on a

bl bl > 0.

Donc, si le choix de la variable sortante est unique on a xj = bp > 0, ce qui donne :

z(x1, . . . , xn) = zB + djx

j > zB.

On a donc montre aussi que,

si le choix de la variable sortante est unique alors le nouvel ensemble de base B est non degenere(avec lhypothese qui a ete faite que B est non degenere).

Montrons aussi que

si le choix de la variable sortante nest pas unique alors B

est degenere.

En effet, dans ce cas il existe au moins deux indices differents p et q tels que

bpapj

=bq

aqj= min{

bkakj

| akj > 0}

Si on choisit par exemple apj comme pivot on obtient que

bq = aqj

bq

aqj

bpapj

= 0,

donc B est degenere.

On a montre entre autre le suivant.

Theoreme 5. Supposons que le programme lineaire est non degenere et quil admette au moins unesolution optimale (avec zmax fini). Alors a chaque iteration du simplexe le choix de la ligne du pivot(i.e. de la variable sortante) est unique et lobjectif crot strictement. Comme le nombre densembles debase est fini (il est inferieur ou egal a Cmn ), il resulte quapres un nombre fini diterations lalgorithmeva trouver une solution de base optimale. Cela montre aussi que, si le programme admet une solutionoptimale, alors il existe toujours une solutionde base optimale.

3.3 Un regard plus attentif sur le simplexe

Dans la section precedente on a fait plusieurs suppositions pour simplifier lexpose :

(a) La connaissance dun tableau initial, i.e. la connaissance a priori dune solution de base admissibledonc du systeme reduit associe.

(b) Le probleme non degenere.

On a vu que sous ces conditions lalgorithme du simplexe, apres un nombre fini diterations, va trouverune solution optimale, ou bien il va indiquer que la valeur optimale est infinie.Maintenant on va essayer de voir quelles sont les issues quand ces hypotheses ne sont pas verifiees. Onpeut supposer, sans restreindre la generalite grace aux resultats presentes au chapitre 1, section 1.5, quele probleme initial soit donne sous la forme canonique.

16


17/28

(PC)max z = cx

s.c.

Ax b

x 0

ou A = (aij) Mm,p(R), b =

b1b2

...bm

, c = [c1 c2 cp] et x = x1x2

...xp

.En introduisant les variables decart (xp+1, . . . , xn) on obtient le programme standard

max z = cxN

AxN + ImxB = b, xN 0, xB 0

avec

xN = x =

x1...

xp

et xB =

xp+1...

xn

.

Il est evident que B = {p + 1, . . . , n} est un ensemble de base pour ce systeme et xB sont les variables debase. Si b 0 alors la solution de base xB = b, xN = 0 est admissible et on peut demarrer le simplexe.Le cas interessant pour nous est celui ou b 0, i.e. il existe au moins un indice j tel que bj < 0. Dans cecas xB = b, xN = 0 est une solution de base mais non admissible.Pour trouver donc une solution de base admissible et le systeme associe, ou le cas echeant pour determinersi lensemble admissible est vide, il existe plusieurs methodes dont une des plus importante fera lobjetde la section suivante.

3.4 La methode du Simplexe en deux phases

Cette methode consiste a introduire une variable artificielle x0 et a resoudre dans un premier temps unprobleme auxiliaire dit la phase I.

(PA)

max w = x0

s.c.

AxN + ImxB ex0 = b

xN 0, xB 0, x0 0

ou e =

11...1

. Il est facile a voir que ce programme admet la valeur optimale wmax = 0 si et seulementsi le programme initial est realisable (i.e. lensemble admissible est non vide).Dautre part, en prenant xB = b, xN = 0, x0 = 0 on obtient une solution de base non admissible duprogramme auxiliaire (PA). On va effectuer un pivotage non standard en considerant x0 comme variableentrante et en lechangeant avec la variable de base la plus negative. Donc la colonne du pivot va etre lacolonne de x0 et la ligne p du pivot est donnee par

bp =m

minj=1

bj.

17


18/28

On constate facilement que le tableau ( ou lensemble de base B) obtenu apres cet echange sera admissible(i.e. avec le second membre 0) car bj = bj bp 0 j. De cette maniere on peut demarrer le simplexepour le probleme auxiliaire. Le probleme auxiliaire (PA) admet toujours une solution optimale car :

1. Son ensemble admissible est non vide (on vient de trouver une solution de base admissible)

2. lobjectif w est borne sur lensemble admissible car w(x1, . . . , xn, x0) = x0 0 pour toute solutionadmissible (x1, . . . , xn, x0).

Donc, si la valeur optimale du probleme auxiliaire (PA) wmax < 0 alors cela signifie que leprobleme initial (PC) nadmet pas de solution admissible.Si la valeur optimale wmax = 0 alors le probleme initial admet des solutions admissibles. On a donc

x0 = 0.

1. Si x0 est dans la base, cela signifie que le tableau optimal du probleme auxiliaire (PA) est degenere.Dans ce cas, en effectuant un pivotage non standard, en prenant comme variable sortante x0 (avecnimporte quelle variable entrante) on constate que le second membre ne change pas, donc on vatrouver une autre solution de base admissible qui ne contient pas x0 en base, donc on est dans lecas suivant :

2. Si x0 est hors base alors le tableau optimal de (P A) nous fournit directement un tableau associe a une

solution de base admissible du probleme initial (PC). Il reste seulement a exprimer z en fonctiondes variables hors base, et on peut demarrer le simplexe pour le probleme initial (PC).

3.5 Degenerescence

Quand lalgorithme du simplexe trouve un tableau (base) degenere il peut y avoir le phenomene decyclage, cest-a-dire, a partir dune base degeneree, apres quelques iterations (pendant ce temps lobjectifest stationnaire, car on passe dune base degeneree a une autre base degeneree) on retrouve le tableau dedepart. Pour mieux comprendre, considerons lexemple suivant, dans lequel on adopte les regles suivantesen presence de candidats multiples pour les variable entrantes et sortantes :

(i) La variable entrante est toujours la variable hors base qui a le plus grand coefficient dans la fonction

objectif. En cas dex aequo, on prend la variable de plus petit indice.

(ii) En cas de plusieurs variables de base candidates a la sortie de la base, on prend la variable de pluspetit indice.

x1 x2 x3 x4 x5 x6 x7 s.m. v.d.b.

0.5 5.5 2.5 9 1 0 0 0 x50.5 1.5 0.5 1 0 1 0 0 x6

1 0 0 0 0 0 1 1 x710 57 9 24 0 0 0 0 z

premiere iteration

x1 x2 x3 x4 x5 x6 x7 s.m. v.d.b.

1 11 5 18 2 0 0 0 x10 4 2 8 1 1 0 0 x60 11 5 18 2 0 1 1 x70 53 41 204 20 0 0 0 z

deuxieme iteration

18


19/28

x1 x2 x3 x4 x5 x6 x7 s.m. v.d.b.

1 0 0.5 4 0.75 2.75 0 0 x10 1 0.5 2 0.25 0.25 0 0 x20 0 0.5 4 0.75 2.75 1 1 x70 0 14.5 98 6.75 13.25 0 0 z

troisieme iteration

x1 x2 x3 x4 x5 x6 x7 s.m. v.d.b.

2 0 1 8 1.5 5.5 0 0 x31 1 0 2 0.5 2.5 0 0 x2

1 0 0 0 0 0 1 1 x729 0 0 18 15 93 0 0 z

quatrieme iteration

x1

x2

x3

x4

x5

x6

x7

s.m. v.d.b.

2 4 1 0 0.5 4.5 0 0 x30.5 0.5 0 1 0.25 1.25 0 0 x4

1 0 0 0 0 0 1 1 x729 9 0 0 10.5 70.5 0 0 z

cinquieme iteration

x1 x2 x3 x4 x5 x6 x7 s.m. v.d.b.

4 8 2 0 1 9 0 0 x50.5 1.5 0.5 1 0 1 0 0 x4

1 0 0 0 0 0 1 1 x722 93 21 0 0 24 0 0 z

sixieme iteration

x1 x2 x3 x4 x5 x6 x7 s.m. v.d.b.

0.5 5.5 2.5 9 1 0 0 0 x50.5 1.5 0.5 1 0 1 0 0 x6

1 0 0 0 0 0 1 1 x710 57 9 24 0 0 0 0 z

On retrouve le tableau initial. Lalgorithme du Simplexe va donc repeter inlassablement la meme suitede six iterations sans jamais atteindre la solution optimale, laquelle existe cependant avec zmax = 1comme on verra dans la suite.Evidemment ce phenomene de cyclage est necessairement lie a la presence de bases degenerees, carautrement, comme on la vu (theoreme 5) si le probleme est non degenere alors a chaque iterationlobjectif augmente strictement ce qui empeche le cyclage (pourquoi ?).On ne va pas etudier ici les methodes qui previennent le cyclage. Signalons cependant la regle extremementsimple du plus petit indice qui a ete decouverte par R. Bland. Cette regle consiste a choisir systematiquementcomme variable entrante et comme variable sortante la variable xk qui correspond au plus petit indice kparmi les multiples candidats. Donc, pour la variable entrante on doit choisir parmi toutes les variables

19


20/28

dont le coefficient dans la ligne objectif est positif, celle qui a le plus petit indice. Pour la variable sortante,il sagit, en cas dex-aequo, de choisir la variable de base qui a le plus petit indice.

Appliquons cette methode a lexemple precedent. On constate que jusqua la cinquieme iteration on autilise cette regle, car pour la variable entrante on a eu un seul choix. Par contre a la cinquieme iteration,dapres la regle de Bland, on doit choisir x1 comme variable entrante, et donc la variable sortante va etrex4. On propose comme exercice de continuer les calculs avec cette regle.

Il semble que le cyclage est un phenomene assez rare dans la pratique de sorte que beaucoup de lo-giciels mettant en oeuvre la methode du simplexe ignorent totalement ce probleme.

3.6 Exercices

Exercice 2. On considere une entreprise produisant deux biens en quantites x1 et x2 respectivement souscontraintes de capacites de production relatives a deux ateliers de production. Le programme lineaire corres-pondant a la maximisation de la marge est le suivant :

max z = 3x1 + 5x2

s.c.

2x2 123x1 + 2x2 18

x1, x2 0

(a) Determiner graphiquement le sommet optimal et donner ses coordonnees.

(b) Mettre le probleme sous la forme degalite par lajout de variables decart.

(c) A loptimum, quelles sont les variables en base et les variables hors base ?

(d) Des progres importants dans lorganisation du travail permettraient de reduire le temps dusinage dusecond bien dans le premier atelier. La premiere contrainte devient donc x2 12, ou , le nouveautemps dusinage, est un parametre inferieur a 2. Jusqua quelle valeur peut-on faire descendre pour

que la meme base (cest-a-dire les memes variables de base) reste optimale ?(e) En dessous de cette valeur quel est le sommet optimal (donner ses coordonnees) et quelle est la nouvelle

base (cest-a-dire quelles sont les nouvelles variables de base) ?

Exercice 3. Resoudre avec la methode du simplexe :

max z = 3x1 + 2x2 + 4x3

s.c.

x1 + x2 + 2x3 42x1 + 3x3 5

2x1 + x2 + 3x3 7x1, x2, x3 0


max z = 5x1 + 6x2 + 9x3 + 8x4

s.c.

x1 + 2x2 + 3x3 + x4 5x1 + x2 + 2x3 + 3x4 3

x1, x2, x3, x4 0


max z = 2x1 + x2

20


21/28

s.c.

x1 2x2 + x3 = 22x1 + x2 + x4 = 2

x1, x2, x3, x4 0

Exercice 6. Resoudre avec la methode du simplexe en deux phases :

max z = x1 x2 + x3

s.c.

2x1 x2 + 2x3 42x1 3x2 + x3 5

x1 + x2 2x3 1x1, x2, x3 0

Exercice 7. Resoudre avec la methode du simplexe en deux phases :

max z = 3x1 + x2

s.c.

x1 x2 1x1 x2 32x1 + x2 2

x1, x2, 0

4 Dualite en programmation lineaire

Dans ce chapitre on va voir comment on peut, a partir dun programme lineaire donne (qui sera appeleprogramme primal), construire un autre programme lineaire appele programme dual. Entre ces deuxprogrammes il y a des liens tres etroits : si un des deux a une solution optimale lautre en possedeegalement une et les valeurs optimales des deux programmes concident. Des fois la resolution du problemedual peut etre plus simple que celle du probleme primal (par exemple on connat une solution de baseadmissible pour le dual et on peut demarrer directement le simplexe, tandis que pour le primal on estobliges dutiliser les deux phases).

Mais, a part linteret mathematique ou numerique pour letude du probleme dual, un aspect tres importantest linterpretation economique des variables duales. Ces variables representent des couts marginaux etpeuvent etre considerees comme laugmentation maximale du revenu, par rapport a la solution optimale,qui resulterait de lutilisation dune unite supplementaire de lun des biens.

4.1 La construction du programme dual

Considerons un programme lineaire sous la forme canonique appele programme primal :

(P)max z = cx

s.c. Ax bx 0

ou A = (aij) Mm,p(R), b =

b1b2...

bm

Mm,1(R), c = [c1 c2 cp] M1,p(R) et x =

x1x2...

xp

Mp,1(R).

21


22/28

Le programme dual a m variables notees 1, . . . , m et on va ranger ces variables sous la forme dunvecteur ligne(viii) :

= [1 m] M1,m(R).

A noter la difference par rapport aux variables primales qui sont donnees sous la forme dun vecteurcolonne x. Alors le programme dual est defini par

(D)min w = b

s.c.

A c

0

On constate la correspondance suivante entre les deux problemes :

Probleme primal Probleme dual

maximisation minimisation

p variables (vecteur colonne) p contraintesm contraintes m variables (vecteur ligne)

variable n j 0 contrainte n j

contrainte n i variable n i 0

(ligne de) coefficients fonction objectif second membre

second membre (colonne de) coeff. fonction ob jectif

Tab. 1 Les correspondences entre le probleme primal et le probleme dual

On peut constater facilement (exercice !) que le dual du probleme dual cest le probleme primal(ix).

4.2 Le theoreme de dualite

Considerons les problemes en dualite (P) et (D) definis dans la section precedente. Une propriete essen-tielle du probleme dual est que toute solution admissible du dual fournit une borne superieure sur lavaleur optimale du primal.

Theoreme 6. (Dualite faible) Soit une solution admissible du dual et x une solution admissibledu primal. Alors on a

z = cx b = w,(6)

autrement dit chaque valeur admissible du critere dual est un majorant pour chaque valeur admissible ducritere primal.

Demonstration. Soit donc x tel que Ax b, x 0 et soit verifiant A b, 0. On a

z = cx Ax b = w.

(viii)Mathematiquement parlant on peut interpreter le vecteur colonne des inconnues du probleme primal comme un elementde lespace vectoriel Mp,1(R) tandis que le vecteur ligne des inconnues du probleme dual represente un element dun espacedual Mm,1(R)

= M1,m(R), i.e. lensemble de formes lineaires sur Mm,1(R) identifiees a des matrices ligne ; le produitscalaire de dualite etant donne par le produit dune matrice ligne (la forme lineaire) et une matrice colonne (la variable)(ix)Indication : Ecrire le dual comme un probleme de maximisation dans lespace primal Mp,1(R), i.e. max(b

T)T s.c.ATT cT; T 0 etc.

22


23/28

Corollaire 1. Soit x une solution admissible du primal et une solution admissible du dual. Si

cx = b

alors x est une solution optimale de (P) et une solution optimale de (D).

Demonstration. Soit x une solution admissible de (P) et une solution admissible de (D). On a grace a (6), pour lecouple (x, ) :

z=

cx

b=

cx

et pour le couple (x, ) :w = b cx = b.

A noter que la reciproque nest pas evidente, a savoir que si x est une solution optimale du primal et

une solution optimale du dual alors les valeurs optimales concident. Cest lobjet du theoreme central dela programmation lineaire.

Theoreme 7. (La dualite forte) Si le probleme primal (P) a une solution optimale x alors leprobleme dual (D) a une solution optimale et les valeurs optimales concident :

cx = b(7)

autrement dit z = w.

Demonstration. Grace au corollaire precedent il suffit de trouver une solution admissible telle que

cx = b.

Introduisons des variables decart xE =

0BBB@

xp+1xp+2

...xn

1CCCA Mnp,1(R) (donc E = {p + 1, . . . , n}) et ecrivons donc (P) sous la

forme standard

max z = cx

s.c.

Ax + xE = bx 0, xE 0

Considerons le tableau optimal du simplexe(x) correspondant a une solution de base (ensemble de base B) optimale. Letableau est associe au systeme

xB + A1B ANxN = A

1B b

z = cBA1B b + (cN cBA

1B AN)xN

On az = cBA

1B b.

Considerons = cBA

1B .

Comme b = z, grace au corollaire 1, il suffit de demontrer que est admissible. On a

z = b + (cN

AN)xN.

Comme le tableau est optimal on a que le cout reduit des variables de base est nul et le cout reduit des variables hors baseest negatif ou nul. Donc

pour j B \ E on a dj = cj Aj = 0

(xi)

pour j N\ E on a dj = cj Aj 0,

(x)On accepte le fait que

si un probleme lineaire a une solution optimale alors il a une solution de base optimale

(on ademontre ce resultat seulement si le probleme est non degenere).(xi)car 0 = dB = cB cBA

1B AB = cB

AB

23


24/28

doncc

A.

Dautre part, pour les variables decart on a que

j B E = dj = 0 (Im)j = 0

j N E = dj = 0 (Im)j 0,

ce qui signifie 0.

Comme le dual du probleme dual est le probleme primal (propose comme exercice avec indication), sile probleme dual a une solution optimale, alors le probleme primal en a une egalement. Donc on peutaffirmer le suivant.

Corollaire 2. Le probleme primal (P) a une solution optimale si et seulement si le probleme dual aune solution optimale.

Le theoreme suivant, en decomposant la relation de dualite forte (7) on obtient les conditions necessaireset suffisantes doptimalite appelees conditions de complementarite.

Theoreme 8. (Conditions de complementarite) Soit x une solution admissible du probleme primal

(P) et une solution admissible du probleme dual (D). Les conditions suivantes sont necessaires etsuffisantes pour que x et soient optimales :cj

mi=1

iaij

xj = 0, j = 1, . . . , p(8)

i

p

j=1

aijxj bi

= 0, i = 1, . . . , m .(9)

Demonstration.Condition suffisante. Supposons les conditions de complementarite satisfaites. On p eut les recrire comme :

cj

xj =

m

Xi=1

iaij

xj

j= 1

, . . . , p(10)

ibi =

pXj=1

iaijxj i = 1, . . . , m .(11)

En additionnant les egalites (10) par rapport a j et les egalites (11) par rapport a i, on obtientpX

j=1

cjxj =

pXj=1

mXi=1

iaijxj =mXi=1

ibi

cest-a-dire les relations de dualite forte (7).

Condition neces saire. Supposons x et optimales. Posons

si = bi p

Xj=1aijx

j ; tj =m

Xi=1

i aij cj .

On peut recrire les relations de dualite forte (7) comme :

pXj=1

cjx

j =

pXj=1

mXi=1

i aij tj

!x

j

=mXi=1

i

pXj=1

aijx

j

pXj=1

tjx

j

=mXi=1

i (bi si) pX

j=1

tjx

j

=mXi=1

i bi mXi=1

i si pX

j=1

tjx

j =mXi=1

i bi,

24


25/28

la derniere egalite provenant des relations de dualite forte (7). Il resulte que

mXi=1

i si +

pXj=1

tjx

j = 0.

Or, comme i , si, tj, x

j 0, i,j, on obtient immediatement la conclusion.

.

On obtient comme consequence le resultat suivant (qui est un cas particulier dun theoreme plus generalde programmation convexe)

Theoreme 9. (Karush-Kuhn-Tucker) Une solution x admissible pour le probleme primal (P) estoptimale si et seulement si il existe les nombres 1, . . . ,

m tels que :

cj mi=1

i aij

xj = 0, j = 1, . . . , p(12)

i

p

j=1aijx

j bi

= 0, i = 1, . . . , m .(13)

et tels que :A c, 0.(14)

Demonstration. Si x est optimale, par le th. de dualite forte, il existe solution optimale du dual (D). Cette solutionest donc admissible pour (D) est satisfait les conditions de complementarite par le th. 8.Reciproquement, si verifie (14) alors est une solution admissible de (D). Si elle satisfait (12) et (13) elle satisfait lesconditions de complementarite. Donc x et sont toutes les deux optimales.

4.3 Interpretation economique des variables duales

Considerons un exemple de probleme ou x1, x2 representent les quantites de deux produits P1 et P2.Leurs marges respectives sont de 4 et 3. Les contraintes representent des contraintes de production.Supposons la premiere contrainte soit une contrainte sur le stock de matiere premiere et la seconde unecontraintes sur le nombres dheures de travail par jour. Plus precisement, pour produire une unite duproduit P1 on utilise 2 unites de matiere premiere et 5 heures de travail, tandis que pour une unite deP2 on a besoin de 1 unite de matiere premiere et de 6 heures de travail. Le stock est de 3 unites et lenombres dheures de travail par jour est de 11h. Donc on a le programme lineaire suivant

max z = 4x1 + 3x2

s.c.

2x1 + x2 35x1 + 6x2 11x1 0, x2 0.

(15)

Le chef dentreprise voudrait savoir ce que lui rapporterait le fait que son atelier soit ouvert une heure deplus par jour. Autrement dit, il voudrait connatre laugmentation de sa marge beneficiaire si le deuxiemecoefficient du membre de droite passait de 11 a 12.

Graphiquement, laugmentation de capacite (ici horaire) se traduit par un deplacement de la secondecontrainte vers la droite (voir figure 3)La solution optimale se deplace du point A(1, 1) vers le nouveau point A correspondant a lintersectiondes droites

2x1 + x2 = 35x1 + 6x2 = 12

25


26/28

O x1

x2

A'

z=7z'=51/7

Fig. 3 Interpretation des variables duales

La nouvelle solution optimale correspond a

A(6

7,

9

7).

A cette nouvelle solution correspond une valeur de lobjectif de

z = 4 6

7+ 3

9

7=

51

7.

Laugmentation de lobjectif est de

z = z z =51

7 7 =

2

7.

Le probleme dual correspondant a (15) est

min w = 31 + 112

s.c.

21 + 52 41 + 62 31 0, 2 0.

(16)

26


27/28

La solution optimale du dual (16) est

(1, 2) = (

9

7,

2

7).

On voit que 2 represente laugmentation de lobjectif. Si on avait augmente la capacite de stockage duneunite (i.e. de 3 a 4) sans augmenter le nombre dheures, on aurait pu constater une augmentation delobjectif egale a 1 =

97 . En general on a le resultat suivant :

le taux daugmentation de la fonction ob jectif par rapport a la ieme composante du membrede droite du probleme primal est egal a la valeur de la ieme variable duale.(xii) A noter quecette interpretation a une limite de validite : elle est valable tant que le meme ensemble de base resteoptimal. Par exemple si on continue a augmenter le nombre dheures de travail, au dela de 18 heuresde travail journalier, la solution optimale devient le point A(0, 3). Il ny a plus daugmentation de lafonction objectif au dela. Au dela de ce point la base optimale change et la solution optimale du dualchange egalement. Elle devient (1,

2) = (3, 0). Cette nouvelle solution sinterprete egalement par le fait

que une valeur nulle de la seconde variable duale signifie que laugmentation de la capacite de la secondecontrainte du primal ne permet plus daccrotre lobjectif.Les valeurs des variables duales sont appelees couts marginaux (en anglais shadow prices). A no-ter que si une contrainte et non saturee, alors grace a la complementarite on a que la variable dualecorrespondante est nulle ce qui montre que la valeur marginale est nulle, i.e. on na pas interet a aug-menter la capacite si on na pas utilise toutes les ressources ! Par contre si la cout (valeur) marginal(e)est non nulle cela montre, grace a la complementarite, que toutes les ressources ont ete utilisees, doncune augmentation de la capacite permettra daugmenter le benefice.

4.4 Exercices

Exercice 8. Considerons le probleme

max z = 4x1 + 6x2 + 20x3 + 17x4

s.c.

x1 + x3 + 2x4 10x2 + 2x3 + x4 4

x1, x2, x3, x4 0.

Ecrire le probleme dual et le resoudre graphiquement . En deduire la solution optimale du probleme primal.

Exercice 9. Considerer le tableau Simplexe final de lexercice 3. Remarquez que si lon prend loppose descoefficients des variables decart dans la ligne objectif, on obtient exactement la solution optimale du dual.Verifiez et expliquez.

Exercice 10. Montrer que si le probleme primal est sous la forme standard, alors les variables duales sontnon contraintes en signe.

Exercice 11. Pour le probleme ci-dessous, verifiez loptimalite de la solution proposee :

max z = 7x1 + 6x2 + 5x3 2x4 + 3x5

s.c.

x1 + 3x2 + 5x3 2x4 + 2x5 44x1 + 2x2 2x3 + x4 + x5 32x1 + 4x2 + 4x3 2x4 + 5x5 53x1 + x2 + 2x3 x4 2x5 1x1, x2, x3, x4, x5 0

(xii)Mathematiquement parlant cela traduit le fait que, a loptimum, en considerant z comme fonction de (A,b,c) on agrace a la dualite forte :

z

bi=

w

bi= i .

27


28/28

Solution proposee : x1 = 0, x2 =

4

3, x3 =

2

3, x4 =

5

3, x5 = 0.

28

Documents

Cours de Programmation Lineaire.pdf