Programmation linéaire V. Ledda DRAFT2.4 La méthode de Dantzig Il s’agit, à l’aide de «pivotements», de faire entrer et sortir judicieusement des vecteurs de l’ensemble

DRAFT

Faculté des Sciences Économiques et Sociales - Université de LilleLicence 3 MISEG

Optimisation

Programmation linéaire

V. Ledda

23 juin 2018

Table des matières

1 Introduction1 Introduction 21.1 Présentation du problème1.1 Présentation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Le cas de deux variables1.2 Le cas de deux variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 La méthode du simplexe2 La méthode du simplexe 22.1 Écriture matricielle2.1 Écriture matricielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2 Solutions de base2.2 Solutions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3 Le tableau du simplexe2.3 Le tableau du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.4 La méthode de Dantzig2.4 La méthode de Dantzig . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Formalisme et démonstration3 Formalisme et démonstration 6

4 Quelques prolongements4 Quelques prolongements 124.1 Cas où la base de départ n’est pas évidente4.1 Cas où la base de départ n’est pas évidente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.2 Dualité4.2 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

DRAFTProgrammation linéaire Chapitre 1

1 Introduction

1.1 Présentation du problème

On se donne une grandeur économique M qui dépend linéairement de plusieurs paramètres X = (x1;x2; · · · ;xn).On cherche à optimiser cette grandeur, c’est à dire que l’on cherche les valeurs Xm = (xm1 ;xm2 ; · · · ;xmn ) quirendent M maximale (ou minimale). Bien évidement, les valeurs de X sont contraintes ! Premièrement, les xisont positifs ; de plus on suppose qu’il existe k relation du type ai1x1 + ai2x2 + · · ·+ ainxn 6 ki .

Exemple 1. Une entreprise vend trois produits différents. On note P1,P2,P3 les quantités produites parl’entreprise de chacun de ces produits. Le prix de vente de chaque produit est fixé à l’année. L’entreprisecherche à maximiser la fonction :

(P1; P2; P3) 7−→ 4P1 + 12P2 + 3P3

Cette fonction est appelée la fonction économique.Ces articles sont produits sur une chaîne qui «tourne» 45 h par semaine. Sur cette chaîne, l’entreprise peutproduire 50 articles P1 par heure, 25 articles P2 par heure et 75 articles P3 par heure. De plus les études demarché, montre que les possibilités de vente des 3 produits ne dépassent pas respectivement 1 000, 500et 1 500 unités par semaine. Quelle répartition hebdomadaire de la production assure un chiffre d’affairemaximum?

1.2 Le cas de deux variables

Une usine produit deux ciments Portland :— le ciment «OPTIM» rapportant 30 € la tonne ;— le ciment «EXTREM» rapportant 40 € la tonne.

Pour réaliser une tonne de ciment «OPTIM» 40 minutes de calcination dans un four à chaux et 20 minutesde broyage sont nécessaires.Pour réaliser une tonne de ciment «EXTREM» 30 minutes de calcination dans un four à chaux et 30 minutesde broyage sont nécessaires.Le four et l’atelier de broyage sont disponibles respectivement 12 heures et 8 heures par jour. Pour desraisons de stockage, l’entreprise ne peut stocker que 19 tonnes de ciment par jour.Combien de ciment de chaque type peut-on produire par jour pour maximiser le bénéfice?

2 La méthode du simplexe

2.1 Écriture matricielle

Dans la partie précédente 1.21.2 on a obtenu le système de contraintes suivant :4x+ 3y 6 72

x+ y 6 19

2x+ 3y 6 48

0 6 x et 0 6 y

(1)

représenté par le polygone des contraintes :

2 V. Ledda


La fonction économique est :B = 30x+ 40y

Dans cette partie, nous allons présenter le même problème de manière matricielle. Cette démarche nouspermettra de généraliser au cas de plusieurs variables. Introduisons, trois variables positives, appeléesvariables d’écart, e1, e2 et e3 pour écrire les inégalités du système (11) sous forme d’égalités.

4x+ 3y + e1 = 72

x+ y + e2 = 19

2x+ 3y + e3 = 48

0 6 x,0 6 y,0 6 e1,0 6 e2,0 6 e3

(2)

On peut écrire matriciellement ce système :

4 3 1 0 01 1 0 1 02 3 0 0 1

×xye1e2e3

=

721948

(S)

2.2 Solutions de base

Lorsque x = y = 0, le système admet une unique solution. Mais B = 0, on est loin du maximum! ! C’est unesolution de base réalisable du système.Lorsque y = e2 = 0, le système admet pour solution x = 19, e1 = −4 < 0 et e3 = 4. C’est une solution de basedu système. Mais, ici, cette solution n’est pas réalisable.

Exemple 2. Reprendre le travail précédent : annuler 2 variables, résoudre, calculer B, interpréter graphi-quement, dire s’il s’agit d’une solution de base réalisable ; pour tous les cas possibles. (Il y a

(52)

= 10 cas àtraiter)

3 V. Ledda


2.3 Le tableau du simplexe

Considérons le tableau suivant :

Hors base En base︷︸︸︷︷︸︸︷x y e1 e2 e34 3 1 0 0 721 1 0 1 0 192 3 0 0 1 48

Lors que x = y = 0, e1, e2 et e3 forment une base de R3. (Il s’agit de la base canonique de R3). On dit que e1,e2 et e3 sont «en base» et que x et y sont «hors base».À l’aide du pivot de Gauss, remplacer la deuxième colonne du tableau par la colonne :

010

Que remarque-t-on? Interpréter géométriquement. Cette opération s’appelle un «pivotement», y est entréen base et e2 est sorti, il est maintenant hors base.En général parcourir tous les sommets n’est pas réalisable car leur nombre croît très vite avec le nombre decontraintes et de variables 11.L’idée de l’algorithme du simplexe 22 est de parcourir un chemin parmi les solutions de bases réalisablesen augmentant à chaque étape la valeur de la fonction économique pour arriver à une solution de baseréalisable optimale.L’algorithme du simplexe se présente généralement sous la forme d’une succession de tableaux, dans le casprésent le tableau initial pourrait être :

4 3 1 0 0 721 1 0 1 0 192 3 0 0 1 48

30 40 0 0 0 0

(3)

2.4 La méthode de Dantzig

Il s’agit, à l’aide de «pivotements», de faire entrer et sortir judicieusement des vecteurs de l’ensemble desvecteurs de base. On parcourt ainsi le polygone des contraintes et l’on s’arrête une fois que l’on a trouvé unesolution de base réalisable optimale.

L’algorithme du simplexe On appelle S le tableau à n+1 lignes et m+n+1 colonnes issue d’un problème deprogrammation linéaire à m variables et n contraintes. La dernière ligne représente la fonction économiqueque l’on cherche à maximiser.

1. Pour n variable et m contraintes, il est inférieur ou égal à(nm)

2. George Dantzig (1951)

4 V. Ledda


1 Algorithme Simplexe

2 TantQue La dernière ligne contient des coefficients strictement positifs Faire

3 j←{j |Sn+1,j = maxi∈~1,··· ,m+n� Sn+1,i}

4 i← {i| Si,n+m+1Si,j

= mink∈~1,··· ,n�,Si,j>0Sk,n+m+1

Sk,j}

5 Par pivotement, faire entrer la colonne j et sortir la colonne i de la liste

des colonnes «en base»

6 FinTantQue

7 Dans le tableau, on lit les variables en base

8 Si la variable i est «en base» alors Si,n+m+1 donne la valeur à donner à la

variable i pour obtenir une solution optimale

9 −Sn+1,n+m+1 est le maximum de la fonction économique

Quelques explications• À la ligne 3, Pour déterminer la variable qui entre en base, on choisit parmi les variables celle qui

«rapporte» le plus. Autrement dit, on choisit la variable associée au plus grand gain marginal. S’il y aplusieurs colonnes où le coefficient est maximal, on en choisit une.

• À la ligne 4, Pour déterminer la variable qui sort de la base, on prend la ligne où le rapport Sk,n+m+1Si,j

est le plus petit possible pour ne pas sortir du polygone des contraintes. En effet, se faisant, lors dupivotement on a pour k , i :

Lk← Lk −Sk,j

Si,jLi

Plus précisément pour la dernière colonne :

Sk,n+m+1← Sk,n+m+1 −Sk,jSi,j

Si,n+m+1

Donc Sk,n+m+1 6 0 car par le choix de i , Sk,n+m+1Sk,j

− Si,n+m+1Si,j

> 0.S’il y a plusieurs lignes où le rapport est minimal, on en choisit une.

• À la ligne 2, dès que tous les coefficients sur la dernière ligne sont tous négatifs ou nuls, on s’arrête.

Remarque 1. À côté des tableaux simplexes, il peut être intéressant de tenir à jour les listes des variablesen base et des variables hors base.

Remarque 2. Les coefficients Si,j et Sn+1,j sont par construction de l’algorithme strictement positifs. Lors du

pivotement, la dernière ligne est transformée par Ln+1← Ln+1 −Sn+1,j

Si,jLj . Pour le coefficient Sn+1,n+m+1 étant

donné que les coefficients Sk,n+m+1 sont positifs pour 1 6 k 6 n, on est assuré qu’à chaque étape le coefficientsera négatif et plus petit que le précédent. C’est à dire, que la nouvelle solution de base est équivalente oumeilleure que la précédente.

Exemple 3. Appliquer l’algorithme du simplexe au tableau (33) et retrouver les résultats obtenus graphique-ment lors d’une séance précédente.

5 V. Ledda


3 Formalisme et démonstration

Définition 1. On appelle programme linéaire, (P), la donnée :

1. d’un système d’équations ou d’inéquations linéaires :X > 0

a11x1 + a12x2 + · · ·+ a1nxn ≶1 b1...

...ap1x1 + ap2x2 + · · ·+ apnxn ≶p bp

(I)

avec X =

x1x2...xn

et ≶i est soit le symbole “=”, soit “6”, soit “>” ;

2. d’une forme linéaire m = tC ·X où C =

c1c2...cn

.

Résoudre un programme linéaire consiste à trouver le ou les valeurs de X qui optimisent m, c’est à dire le oules valeurs de X qui rende(nt) m maximale ou minimale selon les cas.

Définition 2. Une solution réalisable est une solution de (II). Une solution optimale est une solution réalisablequi optimise m. La fonction objectif, ou la fonction économique, est la forme linéaire m. La valeur de (P) est lenombre tC ·Xo où Xo est une solution optimale.

Définition 3. On appelle programme linéaire canonique de type max tout programme linéaire de la forme :X > 0AX 6 Bm = tC ·X (max)

où A ∈Mp,n, B ∈Mp,1 et C ∈Mn,1.

En remplaçant AX 6 B par AX > B et m = tC ·X (max) par m = tC ·X (min) on obtient un programmelinéaire canonique de type min. Un programme linéaire standard est un P.L. canonique où les contraintes(hormis celles de positivitées) sont des égalités.

Proposition 1. Tout programme linéaire est équivalent à un programme linéaire canonique de type max. Toutprogramme linéaire est équivalent à un programme linéaire standard de type max.

Exemple 4. Considérons le programme linéaire suivant :X > 02x+ y − z 6 4−3x+ y + z > 22x+ 7y = 3m = x+ y − z (min)

(P)

6 V. Ledda


(PP) est équivalent à

X > 02x+ y − z 6 43x − y − z 6 −22x+ 7y 6 3−2x − 7y 6 −3m = −x − y + z (max)

(P’)

(PP) est équivalent à

X′ > 02x+ y − z + e1 = 43x − y − z + e2 = −22x+ 7y + e3 = 3−2x − 7y + e4 = −3m = −x − y + z (max)

(P”)

où X′ =

xyze1e2e3e4

.

Les variables ei sont appelées variables d’écarts.

Proposition 2. L’ensemble des solutions réalisables d’un programme linéaire est une partie convexe de Rn.

Preuve. Soit t ∈ [0;1], X = tX0 +(1−t)X1 où X0 et X1 sont deux solutions réalisable d’un programme linéaire,que l’on peut supposer sous la forme canonique de type max. Comme t et 1− t sont positifs,

AX = tAX0 + (1− t)X1 6 tB + (1− t)B = B

Ainsi X est une solution réalisable.cqfd

Définition 4. Soit (P) un programme linéaire. On dit qu’une solution réalisable est un sommet de (P) s’iln’existe pas deux solutions réalisables distinctes X1 et X2 de (P) telles que X soit le milieu du segment [X1; X2].

Proposition 3. Si un programme linéaire (P) admet une unique solution maximale X alors X est un sommetde P.

Preuve. Procédons par l’absurde. Supposons qu’il existe deux solutions réalisables distinctes X1 et X2 de(P) telles que X soit le milieu du segment [X1; X2]. Sans perte de généralité, on peut supposer également quele programme linéaire (P) est sous la forme canonique de type max.Considérons la fonction

f :

[0;1]→ Rx 7→ tC(xX1 + (1− x)X2).

La fonction f est une fonction affine, f (x) = tC(X1 − X2)x + tCX2 ; cette fonction est soit croissante soitdécroissante. Supposons qu’elle soit croissante. f (0,5) = tCX 6 f (1) = tCX1. Comme X est l’unique solutionoptimale, X = X1. Or X est le milieu du segment [X1; X2], donc X1 = X = X2 ; ceci contredit l’hypothèse.Donc X est un sommet de l’ensemble des contraintes. cqfd

De la même manière on peut démontrer la proposition suivante :

7 V. Ledda


Proposition 4. Si X1 et X2 sont deux solutions optimales distinctes d’un programme linéaire (P) alors tousles points du segment [X1; X2] sont des solutions optimales de (P).

Dans la suite on suppose que (P) est un programme linéaire standardX > 0AX = Bm = tC ·X (max)

où A ∈Mp,n, B ∈Mp,1 et C ∈Mn,1 ; tel que p 6 n et rang A = p. Ces deux conditions sont raisonnables car :— On peut toujours rajouter des variables— Si rang A < p alors soit le système n’a pas de solution ! soit il en a et certaines équations sont

redondantes (combinaisons linéaires des autres)

Définition 5. On appelle base réalisable de (P) toute famille B de vecteurs colonnes extraites de A telle que :

i) B est une base de Rp

ii) les coordonnées de B dans la base B sont toutes positives ou nulles.

Définition 6. Soit B une base réalisable de (P). Notons i1, i2, · · · , ip les indices des colonnes de A sélectionnéespour former B. En particulier B = xi1 Ai1 + xi2 Ai2 + · · ·+ xipAip = xi1B1 + xi2B2 + · · ·+ xipBp.On appelle solution de base réalisable associée à la base réalisable B, le vecteur de Rn dont la coordonnée derang ik vaut xk et 0 sinon.

Exemple 5. Dans l’exemple de la cimenterie, A =

4 3 1 0 01 1 0 1 02 3 0 0 1

les 3 dernières colonnes forment une

base de R3. B =

721948

ainsi B = 72A3 + 19A4 + 48A5 = 72B1 + 19B2 + 48B3. Le vecteur

00

721948

est la solution de

base réalisable associé à la base réalisable B.

On dit que les variables xik sont les variables de base (ou en base), les autres sont les variables hors-base.

Remarque 3. Lorsque l’on transforme un programme linéaire canonique en un programme linéaire standarden ajoutant k variables d’écart, les k dernières colonnes forment une base réalisable.

Théorème 1 (admis). Soit X une solution réalisable de (P). Notons i1, i2, · · · , ir les indices des coordonnéesstrictement positives.On a l’équivalence suivante :X est un sommet de (P) si et seulement si le système (Ai1 ; Ai2 ; · · · ; Air ) est libre.

O

En conséquence toute solution de base réalisable de (P) est un sommet de (P). Réciproquement, si X est unsommet, en sélectionnant les colonnes de A dont les indices sont ceux des coordonnées strictement positivesde X, on obtient une famille libre. On obtient une base de Rp en complétant si besoin cette famille.

En général pour un sommet donné, il existe plusieurs bases réalisables correspondantes.Attention

8 V. Ledda


Remarque 4. Comme il y a au plus(nm

)bases de m vecteurs sélectionnés parmi les n colonnes de A, le

programme linéaire (P) possède au plus(nm

)sommets.

Remarque 5. Dans le cas où un sommet à r < p coordonnées strictement positive, il y a autant de baseréalisable associée à ce sommet que de façon de compléter la famille libre en une base. On dit qu’il s’agitd’un sommet dégénéré. Géométriquement, il s’agit de situation où au moins r + 1 hyperplan “se coupent”au même point.

Théorème 2. Soit (P) un programme linéaire. Si (P) possède des solutions optimales, alors au moins un dessommets de (P) est solution optimale.

O

Preuve. Soit X une solution optimale de (P). On suppose que X possède r coordonnées strictement positives.On peut supposer, sans perte de généralité, qu’il s’agit des r premières coordonnées.Si X est un sommet, il n’y a rien à démontrer. Sinon, d’après le théorème 11, A1; A2; · · · ; Ar forment une familleliée de Rp. C’est à dire qu’il existe un vecteur non nul W ∈ Rn dont les n− r coordonnées sont nulles (commeX) tel que AW = 0. Nous allons construire une solution optimale de (P) qui possède au plus r−1 coordonnéesstrictement positives. (C’est à dire un zéro de plus que X).

Construction de solutions réalisables Soit t un réel strictement positif et cherchons notre vecteur sous laforme X + tW. Posons Xt = X + tW et X−t = X − tW. Par construction ces deux vecteurs sont des solutions dusystème (A(Xt) = A(X−t) = A(X) = B). Cherchons les valeurs de t qui rendent réalisable ses solutions. Pourcela, il est nécessaire que :

∀i ∈ ~1;r�{xi + twi > 0

xi − twi > 0⇔

si wi > 0 t 6

xiwi

si wi < 0 t 6 − xiwi

⇔ t 6 τ = mini∈~1;r�

(xiwi

,wi > 0 ; − xiwi

,wi < 0)

Lorsque t = τ, non seulement Xt et X−t sont des solutions réalisables (coordonnées positives) mais de plussoit Xt soit X−t a une coordonnées nulles supplémentaires.

9 V. Ledda


Montrons que Xt et X−t sont optimales. Par définition de X, tCXt 6tCX et tCX−t 6

tCX{ tCXt = tCX + t tCW 6 tCXtCX−t = tCX − t tCW 6 tCX

⇔{

t tCW 6 0

−t tCW 6 0

Or t > 0, donc tCW = 0 et tCXt = tCX−t = tCX.Ainsi Xt et X−t sont optimales.

Conclusion Nous avons donc une nouvelle solution optimale qui possède au plus k − 1 coordonnées nonnulles, d’après le théorème 11 soit il s’agit d’un sommet soit nous avons une famille d’au plus k − 1 vecteursliés parmi les colonnes de A. On peut reprendre le raisonnement précédent et diminuer encore le nombrede colonnes. Or rang(A) = m, donc nécessairement après un certain nombre d’itération, on obtiendra unefamille libre et donc un sommet de (P) cqfd

Remarque 6. Une conséquence du théorème 22 est la suivante : tout programme linéaire réalisable possèdeau moins un sommet.

Définition 7. Deux bases réalisables sont dites voisines si elles ne diffèrent que d’un seul vecteur.

Une base B peut être améliorable s’il existe une meilleure base voisine. Plus précisément, B est meilleur queB′ si tCXB 6

tCXB′ . Elle peut être optimale dans le cas où il n’y a pas de meilleur base. Il se peut égalementque le programme linéaire (P) ne possède pas de solution optimale.

Définition 8. Mettre la base B en position test c’est construire le programme linéaire (P′) = (PB) équivalent àP où :

i) les colonnes de A′ correspondant aux colonnes de B forment (à l’ordre près) la matrice Ip ;

ii) les coefficients de C′ dont les indices sont ceux des colonne de B sont nulles.

Lorsque le système standard provient d’un système canonique. La matrice identité se lit sur les dernièrescolonne de A.

Proposition 5. Considérons (PB) un programme linéaire standard à second membre positif où la base réalisableB est en position test. Notons XB la solution de base réalisable associée.

1. Si tous les coefficients de C sont négatifs ou nul alors XB est une solution optimale.

2. S’il existe ci un coefficient de C strictement positif alors en posant XB(t) = XB + tei on a pour t > 0,m(XB(t)) = tci

(a) Si ∀k ∈ ~1;p�, aki < 0 alors (P) n’a pas de solution optimale.

(b) S’il existe des indices k tels que aki > 0 alors B est améliorable en remplaçant dans le B le vecteurd’indice i de A par le vecteur d’indice j = mink∈~1;p�(

bkaik|aik > 0) de A.

Preuve. 1. Quel que soit X > 0, tCX 6 0, comme tCXB = 0, ∀X > 0, tCX 6 XB .

2. m(XB(t)) = tci car d’une part tCXB = 0 et d’autre part tCei = ci .

(a) Observons que AXB(t) = A(XB + tei) = B+ tAi 6 B. Donc XB(t) est une solution réalisable quelquesoit t > 0 et m(XB(t)) = tci est aussi grand que l’on veut : (P) n’a pas de solution optimale.

(b) Sans sacrifier à la généralité, on peut supposer que A est de la forme

10 V. Ledda


a1i

a2i

...

...

api

Ip

Ai

Cherchons un vecteur X(t) de la forme

0...t...0x1x2...xp

où t est à la ième position.

Pour que la solution soit réalisable il est nécessaire que

∀k ∈ ~1;p� akit + xk = bk⇔ bk − akit = xk > 0 (4)

Si aki < 0 alors bk − akit > 0 quelque soit t.Donc (44) est équivalent à

∀k ∈ ~1;p� tel que aki > 0 , t 6bkaki

La plus grande solution que l’on peut obtenir est atteinte pour t = mini∈~1;r�,aki>0

(bkaki

).

Soit j un indice pour lequel mini∈~1;r�,aki>0

(bkaki

)est atteint.

On montre en utilisant le théorème 11 qu’avec de tels choix de i et de j, B est améliorable et quecette solution réalisable est un sommet du programme linéaire.

cqfd

11 V. Ledda


4 Quelques prolongements

4.1 Cas où la base de départ n’est pas évidente

4.2 Dualité

Exemple 6. Une entreprise fabrique deux types produits, ces produits requièrent 3 matières premières. Onnote c1 et c2 les bénéfices obtenus par la vente des produits fabriqués et l’on suppose que les quantités x1 etx2 vérifient le système des contraintes suivant :

x1 + 3x2 6 18x1 + x2 6 82x1 + x2 6 14

Que l’on peut écrire : X > 0AX 6 Bm = tC ·X (max)

(P)

La résolution de ce problème par la méthode du simplexe donne :1 3 1 0 0 181 1 0 1 0 82 1 0 0 1 141 1 0 0 0 0

L1← L1−1

2 L3L2← L2−1

2 L3L3← 1

2 L3L4← L4−1

2 L3

0 5

2 1 0 −12 11

0 12 0 1 −1

2 11 1

2 0 0 12 7

0 12 0 0 −1

2 −7

L1← L1−5L2L2← 2L2L3← L3−1L2L4← L4−1L2

0 0 1 −5 2 60 1 0 2 −1 21 0 0 −1 1 60 0 0 −1 0 −8

En donnant les valeurs : 6 à la variable x1, 2 à la variable x2, on obtient un maximum de 8. Dans cettesituation, les variables d’écart e2 et e3 sont nulles, donc les deux dernières contraintes sont serrées et lapremière contrainte est lâche, il reste 6 unités de la première matière première. L’entreprise peut êtreintéressée par la revente de ces 6 unités de matière première inutilisée.Notons y1, y2 et y3 le prix de revente des matières premières. Si 18y1 + 8y2 + 14y3 > 8 produire n’est pasrentable.Notons tY = (y1;y2;y3). Le bénéfice pour l’entreprise s’écrit donc :

tCX + tY(B−AX) = tCX + tY(B−AX) = tYB + (tC− tYA)X

Lorsque (tC− tYA)X est négatif, la production des quantités X n’est pas rentable.Plaçons nous maintenant du point de vue d’une entreprise qui rachète les matières premières, si elle souhaitedissuader l’entreprise de produire elle doit proposer un système de prix tY = (y1;y2;y3) tel que tC− tYA 6 0tout en minimisant son coût tYB.Donc l’entreprise qui rachète les matières premières doit résoudre le programme linéaire suivant :

Y > 0tAY > Cm = tB ·Y (min)

(D)

12 V. Ledda


Où de manière explicite : y1 + y2 + 2y3 > 13y1 + y2 + y3 > 218y1 + 8y2 + 14y3 = m (min)

Le programme linéaire (DD) est appelé programme linéaire dual de (PP).

Exemple 7. La cimenterie. Le dual du système (11) est :a> 0,b > 0, c > 04a+ b+ 2c > 303a+ b+ 3c > 4072a+ 19b+ 48c (min)

On peut résoudre ce problème qui a pour solution a = 0, b = 10 et c = 10. À l’optimum 72a+ 19b+ 48c vaut670 comme pour le primal.Si l’on augmente la capacité de stockage d’une unité, le primal devient :

4x+ 3y 6 72

x+ y 6 20

2x+ 3y 6 48

0 6 x et 0 6 y

(5)

Sa résolution donne :

une augmentation du bénéfice de 10 unités. Ce qui correspond à la solution pour la deuxième variable dudual. Les solutions du dual sont les élasticités du bénéfice par rapport à chacune des contraintes.

Définition 9. À tout programme linéaire canonique de type max de la forme :X > 0AX 6 Bm = tC ·X (max)

on associe le programme linéaire canonique de type min de la forme :Y > 0tAY > Cm = tB ·Y (min)

appelé programme linéaire dual.

13 V. Ledda


Proposition 6. Le dual du dual est le primal.

Théorème 3. Soit X et Y des solutions réalisables respectivement du primal et du dual. On a l’inégalitésuivante :

tCX 6 tBY.

O

Preuve.

AX 6 BtYAX 6 tYBtYAX 6 tBY

t(tAY)X 6 tBYtCX 6 tYAX 6 tBY

cqfd

Corollaire 1. Soit X et Y des solutions réalisables respectivement du primal et du dual. Si tCX > tBY alors

tCX = tBY

et X et Y sont respectivement des solutions réalisables optimales du primal et du dual.

Preuve. Soit X′ une autre solution réalisable de (P), d’après le théorème (33) :

tCX′ 6 tBY = tCX

Donc X est optimale. En reprenant le même raisonnement avec une solution réalisable quelconque du dualon obtient le résultat annoncé. cqfd

Théorème 4 (Théorème fondamental de la programmation linéaire). Soit un programme linéaire. Alors

1. s’il admet une solution réalisable alors il admet une solution réalisable de base ;

2. s’il admet une solution optimale, alors il admet une solution optimale de base ;

3. s’il admet une solution réalisable et si la valeur de la fonction objectif est bornée, alors il admet unesolution optimale de base.

O

Théorème 5. 1. Si le programme linéaire primal et le PL dual admettent des solutions réalisable, alors ilsadmettent tous les deux une solution optimale et les fonctions objectifs sont égales à l’optimum.

2. Si le programme linéaire primal n’est pas borné alors le PL dual n’admet pas de solution de base réalisable.

O

Exemple 8. X > 02x1 − x2 6 23x1 − 2x2 6 6z = 2x1 + x2 (max)

(6)

14 V. Ledda


Le PL (66) n’est pas borné, on peut faire croître x2 indéfiniment.Examinons le dual :

Y > 02y1 + 3y2 > 2−y1 − 2y2 > 1z = 2y1 + 6y2 (min)

La seconde contrainte ne peut être satisfaite.

Exemple 9. X > 0x1 + 2x2 > 122x1 + x2 > 9z = −3x1 − 4x2 (min)

15 V. Ledda

Documents

Programmation linéaire V. Ledda DRAFT2.4 La méthode de Dantzig Il s’agit, à l’aide de «pivotements», de faire entrer et sortir judicieusement des vecteurs de l’ensemble