Deux problèmes avec la méthode du simplexe

Trouver une solution de base pour commencer

Un petit exemple

Les contraintes: x1+x2 £ 10,x1-3x2 £ -5,  -5x1+x2 £ -3 deviennent x1+x2 £ 10+y,  x1-3x2 £ -5+y,-5x1+x2 £ -3+y

et le problème avec ces contraintes et la fonction objective z = -y a la solution réalisable de base x1=x2=0, x1-3x2 = -5+y

Une solution optimale est x1=1, x2=2,y=0, x1-3x2 = -5+y,  -5x1+x2 = -3+y

Donc x1=1, x2=2,, x1-3x2 = -5,
5x1+x2 = -3 est une solution réalisable de base du vrai problème.

Et les équations vérifiées à cette solution du vrai problème se trouve en supprimant le y = 0 dans les équations de la solution optimale du problème auxiliaire!

Amélioration nulle

Comment? Si le nombre d'équations des contraintes vérifiées à une solution est supérieure à n.
Une itération jette une contrainte et en ajoute une autre; ça peut donner la même solution.
Et l'algorithme pourrait boucler (même point; ensembles différents d'équations).

Mais il existe au moins un bon ensemble d'équations qui permet à l'algorithme de continuer (vraie amélioration de z s'il y en a). Donc deux possibilités,

  1. choisir les équations à supprimer et à rajouter comme normale avec un choix aléatoire quand plus d'un candidat
    peut marcher de façon acceptable quand il existe une meilleur solution mais risque de ne peut pas trouver qu'il n'y en a pas.
  2. ajouter (virtuellement) une petite quantité ei à la constante bi de la contrainte i;
    Agir comme si 1 >> e1 >> e2 >> e3¼;
    Impossibilité d'avoir plus de n équations vérifiées!!
    Et on résout un programme indistinguable de l'initial!

Pourquoi ne pas jeter les contraintes inutiles?
Trop difficile de les trouver!

Le dual d'un programme linéaire
Motivation

Une solution réalisable d'un programme (de maximisation) donne un z possible, donc un minorant du z optimal.

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.33x1+44x2+34.67x3+20x4+16x6+20x7
£ 106.67
Donc z=30x1+40x2+30x3+10x4+15x6+20x7 £ 106.67

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

Le problème de base: maximiser åj=1n cjxj
avec m contraintes åj=1n ai,jxj £ bi
et xj ³ 0

En essayant de trouver un majorant de la solution, j'ai cherché des multiplicateurs yi pour les contraintes avec les propriétés:
yi ³ 0
åi=1m ai,jyi ³ cj
Et je veux trouver un ensemble de tels multiplicateurs qui me donne la valeur la plus petite possible de åi=1m bi yi.

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=1m bi yi avec les contraintes åi=1m ai,jyi ³ cj équivaut à maximiser åi=1m -bi yi avec les contraintes åi=1m -ai,jyi £ -cj.
(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 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.

L'interprétation économique de la solution du dual

La solution du problème dual (c'est-à-dire les yi) nous dit par combien la solution optimale ( z) va changer si la contrainte (numéro i) est modifiée.
(parce que la valeur trouvée pour z est åi biyi)

Si 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 ...)

Les méthodes plus récentes

Depuis une vingtaine d'années de nouveaux algorithmes existent avec des différences importantes par rapport à celui du simplexe:
Novembre 2002
Un prof aux E.U. annonce un algorithme fortement polynomial (nombre d'opérations arithmétiques borné par un polynôme indépendant du nombre de chiffres dans les coefficients).
Est-il vrai? L'algorithme reste secret pour le moment.




File translated from TEX by TTH, version 3.05.
On 13 Nov 2002, 16:23.