Scribd
Importer
41 vues39 pages

Simplexe

Le chapitre 2 traite des méthodes de Simplexe pour résoudre des problèmes de programmation linéaire, en commençant par la résolution graphique avec des contraintes géométriques. Il présente également l'algorithme du Simplexe, les méthodes des dictionnaires et des tableaux pour simplifier les calculs. Enfin, il aborde la recherche de la nouvelle base et les coûts réduits dans le cadre de la résolution de systèmes simpliciaux.

Transféré par

Youssef Khallouki
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
41 vues39 pages

Simplexe

Le chapitre 2 traite des méthodes de Simplexe pour résoudre des problèmes de programmation linéaire, en commençant par la résolution graphique avec des contraintes géométriques. Il présente également l'algorithme du Simplexe, les méthodes des dictionnaires et des tableaux pour simplifier les calculs. Enfin, il aborde la recherche de la nouvelle base et les coûts réduits dans le cadre de la résolution de systèmes simpliciaux.

Transféré par

Youssef Khallouki
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Chapitre 2 : Méthodes de Simplexe

Pr. Dr. Abdlekbir


HADRI AISSAM Afraites

2023-2024
Rappel: Résolution graphique
• PL à deux variables :

- Les contraintes ou apparaissent des inégalités correspondent


géométriquement à des demi-plans.

- Intersection de ces demi-plans = ensemble des variables satisfaisant à


toutes les contraintes.

- L'ensemble des contraintes est un polygone convexe.


• Résolution du problème de production par la
méthode graphique :

max [𝐹𝐹 𝑥𝑥1 , 𝑥𝑥2 = 4𝑥𝑥1 + 6𝑥𝑥2 ]


𝑥𝑥1 ,𝑥𝑥2

sous les contraintes :

3𝑥𝑥1 + 9𝑥𝑥2 ≤ 81
4𝑥𝑥1 + 5𝑥𝑥2 ≤ 55
2𝑥𝑥1 + 𝑥𝑥2 ≤ 20
𝑥𝑥1 , 𝑥𝑥2 ≥ 0
• Détermination de maximum de 𝑭𝑭:
- La fonction objectif 𝐹𝐹 𝑥𝑥1 , 𝑥𝑥2 = 6𝑥𝑥1 + 4𝑥𝑥2 à comme
6
coefficient directeur (-1, )
4
- Pour déterminer max 𝐹𝐹, on fait "glisser" la droite (translation
parallèle à la direction de la droite) du haut vers le bas jusqu’à
rencontrer l'ensemble des variables satisfaisant les contraintes

- Solution optimale :
15
𝑥𝑥1 , 𝑥𝑥2 = , 5 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 max 𝐹𝐹 = 65
2

On remarque que le maximum de 𝐹𝐹 est atteint en un


sommet du polygone convexe des contraintes.
Résolution algébrique
Propriétés géométriques des solutions de base réalisables
Caractérisation de l'optimum
Algorithme de Simplexe
II: L'algorithme du simplexe proprement dit : Phase 2
III: Méthode des dictionnaires
Méthode des tableaux
Méthode des tableaux
• Les calculs précédents peuvent se simplifier si
on s’arrange pour avoir toujours .
• De cette façon, la résolution d’un système
est immédiate, puisque
• On va donc chercher à travailler avec la forme
simpliciale de PL, on suppose donc que la
matrice A se décompose en
On dispose d’une solution réalisable
avec
Dans ce cas, les coûts réduits se simplifient en :

et les indices e et s des variables entrante et


sortante sont données par :

avec
Recherche de la nouvelle base
• Une fois les variables entrante et sortante choisies,
on doit retrouver un système simplicial :

La nouvelle matrice s’écrit alors


• La matrice es est donnée par :
Proposition :
On note par la i-eme ligne de la Matrice M.
On a les relations suivantes pour les Matrices :

Le second membre donné par :


Les Coûts réduits
• On a avec

Vous aimerez peut-être aussi