Methode du simplex

Introduction

La méthode du simplex impose l'utilisation d'équation (et non d'inéquation comme c'était le cas jusqu'ici...)
Pour remedier a ce problème, on introduit des variables d'écart :

  • [MIN] Z = 10.x1 + 4.x2
  • x1 >= 4
  • x2 >= 6
  • 1.x1 + 2.x2 >= 20
  • 2.x1 + 1.x2 >= 17
  <=>  
  • [MIN] Z = 10.x1 + 4.x2
  • x1 - x3 = 4
  • x2 - x4 = 6
  • 1.x1 + 2.x2 - x5 = 20
  • 2.x1 + 1.x2 - x6 = 17

Dans cet exemple, ont a introduit les variables d'écart x3, x4, x5, x6.

La methode par l'exemple...

Etant donné le caractère relativement complexe de la methode du simplex, nous allons etayer cette présentation par un problème concret qui sera résolu au fur et a mesure... Voici l'énnoncé de cet exemple :

  • La fonction a optimiser : [MAX] Z = 3.x1 + 2.x2 + x3 + x4 + 5.x5
  • Les contraintes :
    • 3.x1 + x3 - x5 = 3
    • x1 + x2 - 3.x4 = -12
    • x2 + x3 + x5 = 4
  • La contrainte de positivité : x1, x2, x3, x4, x5 >= 0

Quelques conventions / notation

Quelques définitions

Pour faire le lien entre la méthode géométrique et le calcul matriciel...

Etape 1 : choix d'une solution initiale

La méthode :

Dans notre cas :

Etape 2 : détermination du Γ

Notation...

dans notre exemple

On remplace les vecteurs A1, ..., A5 par leurs valeurs : L'équation matricielle a résoudre est :

Inversion de la matrice K (calcul de K-1)

On décrit le système linéaire associé à la matrice K :

calcul des coeficients Γij

On peut alors déterminer les coeficients Γij:

Ce qui nous donne :