REPUBLIQUE DU CAMEROUN REPUBLIC OF CAMEROON
******* ******
PAIX - TRAVAIL - PATRIE PEACE – WORK - FATHERLAND
********
********
ECOLE NATIONALE SUPERIEURE
NATIONAL ADVANCED SCHOOL OF
POLYTECHNIQUE DE YAOUNDE ENGINEERING YAOUNDE
******** *******
DEPARTEMENT DU GENIE ELECTRIQUE ELECTRICAL AND
ET TELECOMMUNICATIONS TELECOMMUNICATIONS ENGINEERING
DEPARTMENT
GTEL 4028 : THEORIE DES GRAPHES ET RECHERCHE OPERATIONNELLE
RAPPORT DE RESOLUTION D’UN PROBLEME DE
PROGRAMMATION LINEAIRE PAR ALGORITHME DE BASE
MEMBRES DU GROUPE :
❖ MILIGUIA MI MABAYA JEANNE ALINE
❖ PETNGA NJEMFA STEPLOIC
EXAMINATEUR : Dr LELE
Contents
INTRODUCTION......................................................................................................................................................2
I. OBJECTIF DU TP...........................................................................................................................................3
II. PRÉSENTATION DU PROBLÈME ........................................................................................................3
i. Mettre sous la forme standard ......................................................................................................................3
ii. Application d’un algorithme de résolution du problème standard ...................................................4
iii. Ajustements pour obtenir la solution du problème originel ..........................................................4
III. IMPLÉMENTATION DE LA FONCTION DANS SCILAB......................................................4
IV. TESTS ET EXEMPLES ...........................................................................................................................8
CONCLUSION ........................................................................................................................................................ 13
INTRODUCTION
La programmation linéaire (PL) est une branche de l’optimisation mathématique
permettant de résoudre des problèmes où une fonction linéaire doit être optimisée sous
des contraintes linéaires. Ce rapport présente les fondements théoriques de la méthode
des bases appliquée aux problèmes de PL, puis une implémentation pratique en langage
Scilab.
I. OBJECTIF DU TP
Écrire une fonction scilab [𝑍𝑚𝑖𝑛 ; B] = algorithme1 (A, b, c) qui prend en paramètre la
matrice A, les vecteurs b et c du problème ∑
Ou ∑ : min f(x⃗) = ⃗⃗⃗⃗
c t x⃗
⃗
A ⃗⃗x = b
x⃗ ≥ ⃗0
Ou A est de taille m×n avec m < n et A de rang plein. La fonction retourne la valeur
minimale dans 𝑍𝑚𝑖𝑛 et la base B dans laquelle le minimum est obtenue.
II. PRÉSENTATION DU PROBLÈME
La recherche opérationnelle est une branche des mathématiques appliquées qui
vise à modéliser et résoudre des problèmes complexes d’optimisation dans divers
domaines tels que la logistique, la production, la finance ou encore l’ingénierie.
L’un des outils centraux de cette discipline est la programmation linéaire, qui
permet de maximiser ou minimiser une fonction objective sous des contraintes linéaires.
La résolution d’un problème de programmation linéaire suit les étapes suivantes :
➢ Mettre sous la forme standard
➢ Application d’un algorithme de résolution du problème standard
➢ Ajustements pour obtenir la solution du problème originel
i. Mettre sous la forme standard
Tout problème de programmation linéaire peut-être mis sous la forme standard. Cela pourrait se
⃗ ) = ⃗⃗⃗⃗
faire par ajout de variables. La forme standard peut se définir comme suit : min f(x c t x⃗
Sous contrainte: A ⃗⃗x = ⃗b
x⃗ ≥ ⃗0
𝑥1
𝑥2
Où la rotation 𝑥 . ≥ ⃗0 veut dire xk≥ 0 ∀ 𝑘 ∈ [|1, 𝑛|]
.
(𝑥𝑛 )
𝑐1
𝑐2
𝑐=[.]
.
𝑐𝑛
𝑎11 ⋯ 𝑎1𝑛
𝐴= ( ⋮ ⋱ ⋮ ) ↕ 𝑛 𝑐𝑜𝑙𝑜𝑛𝑛𝑒𝑠
𝑎𝑚1 ⋯ 𝑎𝑚𝑛
𝑏1
𝑏2
𝑏⃗ = . ↕𝑛
.
(𝑏𝑛 )
ii. Application d’un algorithme de résolution du problème
standard
La fonction que nous avons écrit met en œuvre les fondements de la méthode du
simplexe, illustrant de manière concrète la traduction algorithmique d’un processus
d’optimisation. Elle constitue une passerelle entre la théorie mathématique et la mise en
œuvre informatique d’un algorithme de résolution, et démontre l’intérêt de la recherche
opérationnelle pour la prise de décision rationnelle et efficace dans les systèmes
complexes.
iii. Ajustements pour obtenir la solution du problème originel
III. IMPLÉMENTATION DE LA FONCTION DANS SCILAB
➢ On déclare une fonction qui génère toutes les combinaisons possibles de k éléments
parmi un vecteur v : function C = generate_combinations(v, k)
function C=generate_combinations(v, k)
C = []; // Initialise une matrice vide C pour stocker les combinaisons.
l = length(v); // l est la taille de v.
if k == 1 then // Si on veut des combinaisons d’un seul élément, on les ajoute individuellement
à C.
for i = 1:l
C(i,:) = [v(i)];
end
elseif k == l then // Si on veut tous les éléments, il n’existe qu'une seule combinaison possible
(le vecteur complet).
C = [v]; // une seule combinaison possible
else // Appel récursif : on fixe un élément, et on cherche les combinaisons
restantes parmi les éléments suivants.
idx = 0;
for i = 1:l-k+1
sub = generate_combinations(v(i+1:$), k-1);
for j = 1:size(sub,1) //Chaque sous-combinaison est ajoutée au tableau final.
idx = idx + 1;
C(idx,:) = [v(i), sub(j,:)];
end
end
end
Endfunction
➢ Ensuite nous écrivons la Fonction principale qui va résoudre les problèmes de
programmation linéaire de type ∑ : min f(x⃗) = ⃗⃗⃗⃗
c t x⃗
⃗
A ⃗⃗x = b
⃗x ≥ ⃗0 en testant toutes les bases possibles : function [Zmin, x_opt,
B_opt] = algorithme1_console ()
function [Zmin, x_opt, B_opt]=algorithme1_console ()
// Lecture des dimensions
m = input("Entrer le nombre de contraintes m : "); // m contraintes (lignes)
n = input("Entrer le nombre de variables n : "); // n variables (colonnes).
// Lecture manuelle de la matrice A (m x n).
disp("Entrer la matrice A (" + string(m) + "x" + string(n) + ") :");
A = zeros(m, n);
for i = 1:m
for j = 1:n
A(i, j) = input("A(" + string(i) + "," + string(j) + ") = ");
end
end
// Lecture du vecteur b (termes constants des contraintes).
b = zeros(m, 1);
disp("Entrer le vecteur b (" + string(m) + "x1) :");
for i = 1:m
b(i) = input("b(" + string(i) + ") = ");
end
// Lecture du vecteur c (coefficients de la fonction objectif).
c = zeros(n, 1);
disp("Entrer le vecteur c (" + string(n) + "x1) :");
for i = 1:n
c(i) = input("c(" + string(i) + ") = ");
end
// Initialisation
Zmin = %inf; // initialisé à l’infini (sera minimisé).
x_opt = []; //vecteur solution optimale.
B_opt = []; // indices de la base optimale.
solutions = list();
combs = generate_combinations(1:n, m); // Génère toutes les combinaisons de m colonnes
parmi n.
disp("Combinations possibles :");
disp(combs);
for i = 1:size(combs, 1) // On teste chaque sous-matrice de base ABA_BAB, correspondant à
une combinaison.
indices = combs(i, :);
A_B = A(:, indices);
// Vérification d’inversibilité (Si la base est inversible, on résout 𝐴𝐵 𝑥𝐵 = 𝑏)
if det(A_B) <> 0 then
x_B = A_B \ b; // méthode plus stable que inv()
if min(x_B) >= 0 then // Si la solution est réalisable (x ≥ 0), on la complète en la
réinsérant dans un vecteur complet x de taille n.
x = zeros(n, 1);
for j = 1:m
x(indices(j)) = x_B(j);
end
Z = c' * x; // Calcul du coût Z = cᵗx et stockage de la solution. solutions($+1) =
list(Z, x);
if Z < Zmin then // Mise à jour du minimum si besoin.
Zmin = Z;
x_opt = x;
B_opt = indices;
end
end
end
end
// Affichage des résultats
if Zmin == %inf then // Si aucune solution n’a été trouvée, renvoyer NaN.
disp("Aucune solution réalisable.");
Zmin = %nan;
else //Affichage de toutes les solutions réalisables trouvées.
disp("-------- Solutions réalisables trouvées --------");
for k = 1:length(solutions)
Zk = solutions(k)(1);
xk = solutions(k)(2);
mprintf("Z = %.4f\n", Zk);
disp("x = ");
disp(xk);
end
disp("-------- Solution optimale --------"); // Affichage du résultat optimal : valeur de ZZZ,
vecteur xxx optimal, et indices de la base optimale.
mprintf("Zmin = %.4f\n", Zmin);
disp("x optimal = ");
disp(x_opt);
mprintf("Base optimale B = ");
disp(B_opt);
end
endfunction
➢ Pour finir, nous Exécutons tout l’algorithme avec saisie manuelle de A, b et c avec
Appel de la fonction [Zmin, x_opt, B_opt] = algorithme1_console();
// Appel de la fonction principale
[Zmin, x_opt, B_opt] = algorithme1_console ();
IV. TESTS ET EXEMPLES
Nous allons tester le bon fonctionnement de notre fonction en utilisant les cas vus en
classe (s’ils sont égaux, alors nous aurons réussi notre TP).
Cas 1 : Min ( 𝑥1 + 9𝑥2 + 𝑥3 )
Sous contraintes : 𝑥1 + 2𝑥2 + 3𝑥3 ≤ 9
3𝑥1 + 2𝑥2 + 2𝑥3 ≤ 15
x1 ≥ 0; x2 ≥ 0; x3 ≥ 0
* sa forme standard est la suivante :
A = (13 2 3 1 0
2 2 0 1
) ; ⃗⃗⃗ 9
𝑏 = (15 ) ; 𝑐⃗⃗ = (−1, −9, −1, 0, 0)
⃗⃗⃗ = (0, 4.5 , 0, 0, 6)
Nous avons obtenu en cours 𝑍𝑚𝑖𝑛 = -40.5 dans la base (2 ; 5) avec 𝑥
En utilisant notre fonction nous avons le résultat suivant le même résultat :
CONCLUSION
La méthode des bases est une technique fondamentale pour comprendre le
fonctionnement du simplexe. Bien qu’elle soit brute et limitée à de petits problèmes, son
implémentation permet de comprendre les mécanismes internes des algorithmes
d’optimisation.
