UNIVERSITE SULTAN MOULAY SLIMANE
Faculté des Sciences et
Techniques Béni-Mellal
Mini Projet
Recherche opérationnelle, programmation dans
C
Préparé par :
Mohamed BOUSSAKSSOU
1
Plan :
I. Introduction générale
II. Les méthodes du Programmations linéaire
a. Method simplexe
b. Method Big M
c. Method Dual
III. Programmation C (code source)
I. Introduction générale
Ce mini projet a pour but de créer un programme sous language C .. qui
nous facilite les calculs et nous permet d’affiche les tables et les résultats
optimum pour chaque problème !!
Pourquoi on choisit comme langage de programmation le C !!
Ce choix n’est pas arbitraire.. On peut choisir d’autres langauges plus
performance comme Java ou bien matlab.
mais le C a des avantage plus délicieux est aussi le C est presque la
language basic de tous les language .. Donc c’est on compile notre
problème du simplexe par C .. on va le compiler par tous les autres langage
sans aucune problème ..
Le C est un langage incontournable qui en a inspiré beaucoup d'autres.
Inventé dans les années 70, il est toujours d'actualité dans la
programmation système et la robotique. Il est plutôt complexe, mais si
vous le maîtrisez ,vous aurez des bases de programmation très solides.
Maintenant on va entrer un peu dans les détails pour bien comprendre la
situation de la programmation linéaire et ensuite faire un petit programme
dans c qui résume tout ça.
II. Les méthodes du Programmations linéaire
a. Method simplexe
Cette schéma représente l’algorithme du simplexe ou bien les différents
étapes pour le manipuler..
Commençons par vérifier si le programme est optimale ou non .. c’est oui
alors Stop le programme est déjà résolu.
Sinon on va choisir la variable d’entré et de sortie.. l’étape qui suit consiste a
faire le pivotage..
On répète tous ces opérations jusqu’on trouve tous les coefficients de la
fonction objectif inferieur ou égale a 0.
On va maintenait expliquer pas à pas ces étapes..
Etape 1
Avant que l’algorithme du simplexe puisse être utilisé pour résoudre un
programme linéaire, ce programme linéaire doit être converti en un
programme équivalent où toutes les contraintes technologiques sont des
équations et toutes les variables sont non négatives.
a. Contraintes de type (<=) : Pour chaque contrainte de ce type, on rajoute
une variable d’écart ei, tel que ei est une variable positive ou nulle.
Exemple : 3x1 + 2x2 <= 2 se transforme en 3x1 + 2x2 + e1 = 2, e1 > 0
b. Contraintes de type (>=) : Pour chaque contrainte de ce type, on
retranche une variable d’excédent ei, tel que ei est une variable positive ou
nulle.
Exemple : 3x1 + 2x2 >= 2 se transforme en 3x1 + 2x2–e2 = 2, e2>0
Un programme linéaire qui contient des contraintes (technologiques) de type
<= est noté (PL). Un programme linéaire qui contient des contraintes
(technologiques) de type (<, >, =) est noté (PG). Un programme linéaire (PL)
resp (PG) converti tel que toutes les Contraintes technologiques sont des
équations et toutes les variables sont non négatives est noté (PL=) resp (PG=)
Etape 2 : variables de bases et horsbase
Considérons un système d’équations à n variables et m équations où n>=m.
Une solution de base pour ce système est obtenue de la manière suivante :
a) On pose n-m variables égales à 0. Ces variables sont appelées variables
horsbase (V.H.B.).
b) On résout le système pour les variables restantes. Ces variables sont
appelées les variables de base (V. B.)
c) Le vecteur de variables obtenu est appelé solution de base (il contient les
variables de base et les variables hors base) Une solution de base est
admissible si toutes les variables de la solution de base sont supérieur ou
égale à 0.
Il est vraiment important d’avoir le même nombre de variables que
d’équations.
Etape 3 : Solutions admissibles
Toute solution de base de (PL=) pour laquelle toutes les variables sont non
négatives, est appelée solution de base admissible. Cette solution de base
admissible correspond à un point extrême.
Exemple d’application :
(n-m)=0
n= 6 et m = 4
(6 – 4) = 2 variables = 0
Variables hors base alors Variables de base:
si x1 = x2 = 0 e1= 200
e2 = 60
e3 = 34
e4=14
Étape A: tableau initial
Coeff. dans Z 1000 1200 0 0 0 0
Base X1 X2 E1 E2 E3 E4 bi
Coef.
Z Var.base
0 e1 10 5 1 0 0 0 200
0 e2 2 3 0 1 0 0 60
0 e3 1 0 0 0 1 0 34
0 e4 0 1 0 0 0 1 14
Zj 0 0 0 0 0 0 0
Cj – zj 1000 1200 0 0 0 0
Étape b: variable entrantes (dans la base )
Maximum des Cj– Zj pour des problèmes de max.
Minimum des Cj– Zj pour des problèmes de min.
Dans notre exemple : x2 a le plus grand Cj– Zj donc, il entre dans la base.
Étape C : choix de la variable sortante
Dans un problème de min OU de max, la variable sortante sera le minimum
des
bi /aik | aik >0
Dans notre exemple, nous devons évaluer :
Var. entrante est X2. il a Cj-Zj le plus grand et >0
200 /50 = 40
60/3=20
14/1 =14 c’est le minimum, donc e4 est la variable qui sort de la base.
Etape d : pivotage
Le pivotage s’effectue de la manière suivante :
On commence par diviser la ligne du pivot par le chiffre du pivot.
Nous poursuivons avec la matrice identité pour les variables de base. Nous
inscrivons 1 à l’intersection de chaque variable et 0 ailleurs.
Nous devons calculer les nouvelles valeurs pour les cases restantes à partir du
tableau précédent (tableau initial pour la première itération).
La formule de calcul est :
Nouveau valeur = ancienne valeur – (projection sur ligne pivot * projection sur
ligne pivot)/pivot .
Le critère d’arrêt
Nous arrêtons lorsque nous obtenons le critère d'optimalité. L'algorithme du
simplexe s'arrête lorsque:
Cj - Zj <= 0 pour un problème de max
Cj – Zj >= 0 pour un problème de min
b. Method Big M
La méthode Big M nous aidé à trouver des solutions a des programmes
linéaire de la minimisation ou lorsque les contraintes contenant le symbole
supérieur
On choisit un nombre M assez très grand..
Etapes à suivre dans la méthode Big M :
- Ajouter les variables artificielles pour obtenir une solution optimale
- On les ajoute seulement pour les contraintes de type ‘ >=’ ou ‘=’
- M est associe aux variables artificiels
- Finalement on utilise la méthode simplexe pour résoudre notre
problème on éliminant les variables artificielles .. comme on a déjà vu
dans la première partie .
Exemple :
Minimize Z = 40x1 + 24x2
Subject to 20x1 + 50x2 >= 4800
80x1 + 50x2 >= 7200
x1 , x2 >= 0
Mini Z = 40x1 + 24x2+ 0s1 + 0s2 + MA1 + MA1
Subject to 20x1 + 50x2 –S1 + A1 = 4800
80x1 + 50x2 –S2 + A2 = 7200
x1 , x2 >= 0
S1 and S2------Surplus Variable
A1 and A2-----Artificial Variable
