(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 |
Je peux aussi déduire des minorants de ce prix par manipulation directe des inéquations:
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
Donc
Quel est le meilleur minorant que je peux trouver de cette façon?
Le problème de base: maximiser
avec
contraintes
et
En essayant de trouver un majorant de la solution, j'ai
cherché des multiplicateurs
pour les contraintes avec les propriétés:
Et je veux trouver un ensemble de tels multiplicateurs qui me donne la valeur
la plus petite possible de
.
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, à savoir minimiser
avec les contraintes
équivaut à maximiser
avec les contraintes
.
(pour l'exprimer
en forme canonique)
On a multiplié les deux vecteurs
et
et la matrice
par
,
é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.
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.
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.
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
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 ...)