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)
2
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.
3
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
4
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
5
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
6
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
7
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 .
8
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
Max Z = -40x1 – 24x2 – 0S1 – 0S2 - MA1 – MA2
9
Ensuite on va construire les tableaux du simplexe jusqu’à la dernier qui
vérifiée les critères d’arrêt.
On fin on trouve le tableau suivant .
c. Method Dual
Principe de la méthode :
Consiste à travailler simultanément sur les problèmes primal et dual;
partant du dual et d'une solution irréalisable du primal, choisie de façon
que le théorème des écarts complémentaires soit satisfait, cette méthode
«améliore» de façon itérative la solution du primal; lorsque celle-ci devient
primale-réalisable, la solution est optimale.
Règles a suivre.
10
Etapes de l’algorithme Primal-dual:
Y’a plusieurs exemples à donner mais on s’arrête ici pour parler un peu sur
l’implémentation du code et les cas qu’on n’a pas de chance de les traité.
III. Programmation C (code source)
Le Programme
Le code source que je rapporter avec mon rapport.. il consiste à différents
étapes de la résolutions du programmation linéaire
Lorsque le programme s’ouvre .. vous avez devant vous une page qui vous
demande d’entrer 1 ou 2 selon vos besoins.. 1 pour une maximisation et 2
pour une minimisation.. ensuite lorsque tu tape 1 .. le programme demande
d’entrer le nombre de variable que vous avez, et le nombre des inéquations..
Dans presque tout le programme je ne traite pas les cas où l’utilisateur tape
une lettre ou bien autre chose que les nombres ??
11
Lorsque tu tape 2 .. le programme a vous demander de choisir avec quelle
méthode vous voulez. Méthode BigM ou bien le Dual
Donc Il vous reste rien à faire, juste vous attendez un peu .. et le programme
va faire les calculs et ensuite affichera les différents tableau du simplexe..
Cas Non traité dans Le Programme :
Si vous tapez des lettres.. le programme sera bloqué. Donc il est obligé de
taper des nombres correcte..
Si vous essayez la méthode bigM vous trouver que dans l’affichage des tables
ne contiennent pas le nombre M .. parce que dons notre cas on a déclaré le
matrice de type entier .. et donc on peut pas stocker le M dans la matrice
Et donc comment peut-on faire !!
on peut déclarer un autre tableau qui de type char .. on suite on va prendre
les coefficients de M et faire nos opérations..
et à la fin on va ajouter l’affichage de cette table.. mais c’est très complique à
faire.
La deuxième cas non traité est la construction des interfaces graphique !!
Il y a plusieurs méthodes de faire ça.. la plus simple est d’installer la
bibliothèque SDL.. et on suite réagir avec elle pour créer des animations ; des
couleurs ; d‘insérer des images à notre programme et bien d’autres choses.
12
