next up previous
Next: About this document ...

Comment fournir les besoins de nutrition d'un MIAGiste?

(pourcentage des besoins par portion vendue)

  Via Poi Piz Cho Vin Biè Chi
Calories 10 10 20 50 0 40 25
Protéines 50 60 40 0 0 0 15
Vitamines 30 50 40 5 5 20 10
Alcool 0 0 0 0 50 30 0
Prix 40 50 50 60 30 20 20



Le dual d'un programme linéaire
Motivation
Une solution faisable donne un prix possible, donc un majorant du prix optimal.

Je peux aussi déduire des minorants de ce prix par manipulation directe des inéquations:

$\begin{array}{rrrrrrrcr}
10&10&20&50&0&40&25& ~~x~\geq~~ &100 \\
50&60&40&0&0&0&15& &100 \\
30&50&40&5&5&20&10& &100 \\
0&0&0&0&50&30&0& &100 \\
\end{array}$

avec z=40x1+50x2+50x3+60x4+30x5+20x6+20x7

Si je calcule 2/5 x (1) + 2/3 x (2), j'obtiens
37.33x1+44x2+34.67x3+20x4+16x6+20x7
$\geq 106.67$
Donc $z\geq 106.67$

Quel est le meilleur minorant que je peux trouver de cette façon?

Le problème de base: maximiser $\displaystyle \sum_{j=1}^n c_jx_j$
avec $\displaystyle m$ contraintes $\displaystyle \sum_{j=1}^n a_{i,j}x_j \leq b_i$
et $\displaystyle x_j \geq 0$

En essayant de trouver un majorant de la solution, j'ai cherché des multiplicateurs $\displaystyle y_i$ pour les contraintes avec les propriétés:
$\displaystyle y_i \geq 0$
$\displaystyle \sum_{i=1}^m a_{i,j}y_i \geq c_j$
Et je veux trouver un ensemble de tels multiplicateurs qui me donne la valeur la plus petite possible de $\displaystyle \sum_{i=1}^m b_i y_i$.

Un nouveau programme linéaire!
appelé le dual.

Propriété évidente: chaque solution réalisable du dual est supérieure ou égale à chaque solution réalisable du problème de base.

Le dual du dual

Le dual, à savoir minimiser $\displaystyle \sum_{i=1}^m b_i y_i$ avec les contraintes $\displaystyle \sum_{i=1}^m a_{i,j}y_i \geq c_j$ équivaut à maximiser $\displaystyle \sum_{i=1}^m -b_i y_i$ avec les contraintes $\displaystyle \sum_{i=1}^m -a_{i,j}y_i \leq -c_j$.
(pour l'exprimer en forme canonique)

On a multiplié les deux vecteurs $\displaystyle \bf b$ et $\bf c$ et la matrice $\bf a$ par $\displaystyle -1$, échangé les 2 vecteurs et transposé la matrice.

Donc, si on le fait une deuxième fois pour obtenir le dual du dual, on trouve le problème de base.

Les deux problèmes ont la même solution!
(c'est-à-dire la même valeur optimale de la fonction objective)

Le théorème le plus important de la programmation linéaire.

Démonstration compliquée.

Mais, il n'est pas difficile de voir que l'algorithme du simplexe calcule (dans le cas d'un programme faisable et borné) une valeur qui est une solution réalisable des deux problèmes;
donc, forcément la solution optimale des deux.

On peut choisir le problème à résoudre!
Résoudre un problème ou son dual par
l'algorithme du simplexe donne la valeur optimale de z et des xj et des yi.

Le temps de calcul peut être différent entre les deux.

Le temps de calcul dépend plus du nombre de variables que de celui des contraintes.

Et, peut-être, on peut éviter la nécessité du programme auxiliaire pour trouver une solution initiale.

Le cas de problèmes non bornés ou infaisables
Le théorème de dualité démontre que (si un problème possède une solution optimale) son dual possède la même solution optimale.
Il reste trois autres possibilités:

L'interprétation économique de la solution du dual
La solution du problème dual (c'est-à-dire les $\displaystyle y_i$) nous dit par combien la solution optimale ( $\displaystyle z$) va changer si la contrainte (numéro $\displaystyle i$) est modifiée.
(parce que la valeur trouvée pour z est $\sum_i b_iy_i$ qui dimininue par bi si on fait un pas de longueur 1 dans la direction dans le polytope et, donc, augmente par bi dans le sens inverse dans un rayon de la solution trouvée)

Dans l'exemple des aliments, le prix ``raisonnable'' d'1% des besoins serait 0.05 (calories), 0.79 (protéines), 0 (vitamines) et 0.6 (alcool).

La dinde au whiskey (10% de nos besoins de calories, 50% des protéines et 100% de l'alcool par portion vendue 50) est-elle rentable?

Si $\displaystyle z$ est mon profit, yi est le maximum que je devrait payer (par unité) pour lâcher la contrainte (acheter plus d'une matière de base ...)




next up previous
Next: About this document ...
Mike ROBSON
2000-10-19