L'algorithme du simplexe
Le simplexe en tableaux pour un problème de maximisation : choix de la variable entrante et du pivot, itération, critère d'arrêt, lecture de la solution et chemin de sommet en sommet.
- 24 cartes
- 4 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
Quelques cartes du deck
Algorithme du simplexe : de quoi s'agit-il ?
Voir la réponse
Méthode de résolution d'un programme linéaire qui passe d'un sommet de la région admissible à un sommet voisin de meilleure valeur, jusqu'à ne plus pouvoir améliorer.
Il part d'une solution de base admissible (l'origine, quand toutes les contraintes sont des ≤ à seconds membres positifs) et n'examine en pratique qu'une petite partie des sommets.
Voici le tableau initial de l'atelier (objectif 30x + 20y). Quelle case est le pivot de la première itération (règle du plus grand gain) ?
```text
x y e1 e2 | b
L1 2 1 1 0 | 100
L2 1 1 0 1 | 80
z -30 -20 0 0 | 0`- Colonne x, ligne L1 (le coefficient 2)
- Colonne x, ligne L2 (le coefficient 1)
- Colonne y, ligne L2 (le coefficient 1)
- Colonne y, ligne L1 (le coefficient 1)
Voir la réponse
Colonne x, ligne L1 (le coefficient 2)
−30 est le coefficient le plus négatif, donc x entre. Rapports : 100 / 2 = 50 pour L1 et 80 / 1 = 80 pour L2. Le plus petit est 50 : L1 donne le pivot.
À chaque itération, la variable … est choisie dans la ligne de l'objectif, et la variable … par le plus petit rapport entre second membre et coefficient positif de la colonne.
Voir la réponse
À chaque itération, la variable entrante est choisie dans la ligne de l'objectif, et la variable sortante par le plus petit rapport entre second membre et coefficient positif de la colonne.
Choisir le plus petit rapport garde tous les seconds membres positifs : la nouvelle solution reste admissible.
Tableau du simplexe : de quoi s'agit-il ?
Voir la réponse
Tableau qui range les contraintes mises en égalités, avec les coefficients des variables, les seconds membres et, en dernière ligne, l'objectif.
Pour un maximum, la ligne de l'objectif est écrite z − c·x : un coefficient négatif signale un gain possible, la dernière case donne la valeur de l'objectif.