Exemple de calcul dans différents cas

Considérons le problème

max z = 20×1 + 25×2

sous les contraintes

Capture

Au préalable, on écrit le problème sous la forme canonique

                      max z = 20×1 + 25×2

sous les contraintes

                      Capture1

Voici les étapes du simplexe. 0. On forme le tableau initial T.

                         Capture2

Les variables de base sont {x3, x4} et la solution de base est (0, 0, 40, 48) ce qui correspond à l’origine dans le plan.

1. La fonction z varie plus rapidement en fonction de la variable x2. Donc, on choisit la deuxième colonne comme colonne de pivot. La variable x2 entre dans la base mais une variable doit sortir.

2. On doit choisir la ligne de pivot. Pour cela, on utilise le critère du quotient

                            Capture3

où j est la colonne de pivot de l’étape 2. Le critère assure que la solution sera admissible.

1

La ligne de pivot sera la première : i = 1. Les variables de base deviennent B = {x2, x4}.

3. On pivote autour de l’élément T1,2

 2

La solution de base sera x2 = 40/3, x4 = 64/3, x1 = x3 = 0.

4. On choisit la première colonne comme colonne de pivot car x1 est la seule variable qui augmente z.

4

On applique le critère du quotient pour chercher la ligne de pivot et on trouve i = 2. La nouvelle base sera B = {x2, x1}.

5. On pivote autour de l’élément T2,1

5

6. L’algorithme se termine ici car tous les coefficients des colonnes x1, x2, x3, x4 sont négatifs. Donc, on ne peut augmenter davantage z. La solution optimale sera x1 = 8, x2 = 8, x3 = 0, x4 = 0 et z = 360. ce qui correspond au sommet (8, 8) dans le plan. Le signe − dans le coin inférieur droit est dû au fait que l’on avait initialement ajouté la ligne c tx − z = 0. Donc, à la fin, on aura −z = −360.

 

un problème de minimisation

min 3×1 − 6×2,                                                 min 3×1 − 6×2,

x1 + 2×2 ≥ −1,                                                  −x1 − 2×2 ≤ 1,

2×1 + x2 ≥ 0,               ⇐⇒                              −2×1 − x2 ≤ 0,

x1 − x2 ≥ −1,                                                     −x1 + x2 ≤ 1

x1 − 4×2 ≥ −13,                                                 −x1 + 4×2 ≤ 13,

−4×1 + x2 ≥ −23,                                              4×1 − x2 ≤ 23,

x1, x2 ≥ 0.                                                           x1, x2 ≥ 0.

 

On ajoute les variables d’écart

min 3×1 − 6×2,

−x1 − 2×2 + x3 = 1,

−2×1 − x2 + x4 = 0,

−x1 + x2 + x5 = 1,

−x1 + 4×2 + x6 = 13,

4×1 − x2 + x7 = 23,

x1, x2, x3, x4, x5, x6, x7 ≥ 0.

 

Le tableau initial s’écrit

1

La colonne de pivot est j = 2 et la ligne de pivot est i = 3. On pivote autour de ce pivot.

2

La colonne de pivot est j = 1 et la ligne de pivot est i = 4. On pivote autour de ce pivot

3

L’algorithme se termine à cette étape car tous les ci ≥ 0. La solution optimale sera x1 = 3, x2 = 4, x3 = 12, x4 = 10, x5 = 0, x6 = 0, x7 = 15 =⇒ (x1.x2) = (3.4) et z = −15.

 

Un cas de solution non borné.

Capture

On ajoute les variables d’écart

1

Le tableau initial s’écrit

2

La colonne de pivot est j = 2 et la ligne de pivot est i = 3. On pivote autour de ce pivot.

3

La colonne de pivot est j = 1. Toutefois, le critère du quotient ne s’applique plus car toutes les entrées (lignes 1 à 3) de la colonne 1 sont négatives ou nulles. Analysons cette situation en écrivant les équations correspondantes du tableau

4

La dernière base était B = {x4, x5, x2}. On voulait faire entrer dans la base la variable x1. Posons les autres variables x3 = x6 = 0 dans le système ci-dessus

5

Donc nous obtenons une famille de solutions admissibles qui dépend de la variables x1 ≥ 0.

Reportons dans la fonction objective (voir la dernière ligne du tableau), on obtient z = −3 − 5×1 + 7×3 + 3×6 Or x3 = x6 = 0. z = −3 − 5×1 → −∞ si x1 → ∞.

Donc le problème est non borné inférieurement et de ce fait n’admet pas de solution optimale.

 

dégénrescence

Dans l’application du critère, il peut y avoir plusieurs variables candidates pour sortir de la base : dans ce cas, la base suivante sera dégénérée : une ou plusieurs variables de base sont nulles.

Interprétation géométrique : plusieurs hyperplans supplémentaires passent par un des sommets.

Pas encore de commentaire.

Laisser un commentaire

Techno95 |
MANJ |
TOUT SUR LE MAC |
Unblog.fr | Annuaire | Signaler un abus | Informatique11
| Cartiertechno
| Supermarketlady