Problèmes avec l'algorithme du simplexe

• Modifier le problème de sorte que le nouveau problème auxiliaire aie une solution de base triviale et une solution optimale du nouveau problème soit forcément une solution réalisable (de base) de l'ancien ;
• Résoudre ce nouveau problème par
  l'algorithme du simplexe !
• Enfin commencer a résoudre le vrai problème.

• Pour construire le nouveau problème:

  • Ajouter une nouvelle variable, disons y (avec y ≥ 0)
  • Remplacer toute contrainte lin  ≤  const par lin-y ≤  const (et transformer dans la forme canonique)
  • Il existe une solution réalisable de base avec n+1 équations vérifiées
  • Minimiser y (maximiser -y) ; si le résultat est nul, on a trouvé une solution réalisable de base de l'ancien problème ; sinon il n'y en a pas.

Le dual d'un programme linéaire

Je peux aussi déduire des majorants de z par manipulation directe des inéquations:

10	10	20	50	0	40	25	x  ≤	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

Si je calcule 2/5× (1) + 2/3× (2), j'obtiens
37.33x₁+44x₂+34.67x₃+20x₄+16x₆+20x₇
≤ 106.67 et, donc,
z=30x₁+40x₂+30x₃+10x₄+15x₆+20x₇ ≤ 106.67

Quel est le meilleur majorant que je peux trouver de cette façon ?
Le problème de base: maximiser ∑_j=1ⁿ c_jx_j
avec m contraintes ∑_j=1ⁿ a_i,jx_j ≤ b_i
et x_j ≥ 0

En essayant de trouver un majorant de la solution, j'ai cherché des multiplicateurs y_i pour les contraintes avec les propriétés :

y_i ≥ 0
∑_i=1^m a_i,jy_i ≥ c_j
Et je veux trouver un ensemble de tels multiplicateurs qui me donne la valeur la plus petite possible de ∑_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 ∑_i=1^m b_i y_i avec les contraintes ∑_i=1^m a_i,jy_i ≥ c_j équivaut à maximiser ∑_i=1^m -b_i y_i avec les contraintes ∑_i=1^m -a_i,jy_i ≤ -c_j.
(pour l'exprimer en forme canonique)

On a multiplié les deux vecteurs b et c et la matrice a par -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 retrouve le problème de base.

La même solution ! 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;
En effet, à la fin de l'exécution de l'algorithme, la dernière ligne contient sa valeur initiale (la fonction objective) moins une somme de multiples des autres lignes; mettons m_j pour le multiplicateur de la ligne j.

En regardant les valeurs finales dans cette dernière ligne, on trouve

• (colonne de la j-ième variable d'écart) -m_j; donc on a m_j ≥ 0 par la condition d'arrêt,
• (colonne de la j-ième variable du programme de départ) c_j-∑a_i,jm_j; donc ∑a_i,jm_j ≥ c_j (par la même condition)
• (colonne des constantes) ∑-c_jm_j; donc la solution trouvée pour le programme de départ était ∑c_jm_j.

Il reste trois cas possibles ou ni l'un ni l'autre n'a pas de solution optimale:

• les deux programmes sont infaisables
• le primal est infaisable et le dual a des solutions sans borne
• le primal a des solutions sans borne et le dual est infaisable

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

Un autre algorithme Celui de Khachiyan (1979) a l'avantage d'être certain de terminer dans un temps polynomial (dans la taille des entrées ... ) dans tous les cas.

• Il suffit de pouvoir décider si un programme est faisable ou non (recherche dichotomique peut ensuite donner le résultat exact dans un nombre polynomial d'itérations)
• Toutes les solutions de base (et donc une solution réalisable s'il y en a, même si l'espace de solutions est infini) sont à l'intérieur d'une (hyper-)sphère de taille calculable (et pas trop grande)
• Considérer le point au centre de cette sphère

• S'il est une solution réalisable, le programme est faisable.
• Sinon, toute solution réalisable est à l'intérieur d'une hémisphère bornée par la moitié de la sphère et un plan parallel à la contrainte violée
• Trouver la plus petite ellisoïde qui contient cette hémisphère ;
• Et appliquer une transformation linéaire qui transforme cette ellipsoïde en une sphère !