Programme Automatic Simplexe –

Introduction et Explications

Réalisé par le groupe , composé de:

• Mademoiselle Mandrindra Rovatiana N°40

• Mademoiselle Rahasinjato Fy Miharisoa N°13
• Mademoiselle Rakotonindrina Koloina Ida N°38
• Monsieur ANDRIAMBOLOLONA Doré Happiness N°03
• Monsieur RANAIVOSON Tambiniaina Kévin N°18

1
1. INTRODUCTION
La programmation linéaire est une méthode d’optimisation largement utilisée dans de nombreux
domaines tels que l’économie, la logistique, l’ingénierie et la gestion des ressources. Elle consiste
à maximiser ou minimiser une fonction objectif linéaire tout en respectant un ensemble de
contraintes également linéaires.

L’une des méthodes les plus connues pour résoudre les problèmes de programmation linéaire est
la méthode du simplexe, développée par George Dantzig en 1947. Cette méthode permet de
parcourir les solutions de base réalisables d’un problème afin de trouver la solution optimale.

Dans ce travail, nous avons développé un programme MATLAB appelé « Auto Simplex » qui
permet de résoudre automatiquement un problème de programmation linéaire. Le programme
choisit automatiquement la méthode la plus adaptée parmi:

• le simplexe primal
• le simplexe via la dualité
• la méthode des deux phases

Ce programme permet également d’afficher les tableaux du simplexe à chaque itération afin de
suivre l’évolution de la solution jusqu’à l’optimum.

2. PRINCIPE GÉNÉRAL DU PROGRAMME

Le programme fonctionne selon les étapes suivantes :
1. Saisie des données du problème
2. Analyse de la structure du problème
3. Choix automatique de la méthode de résolution
4. Application de l’algorithme du simplexe
5. Affichage de la solution optimale

Les données nécessaires pour résoudre le problème sont :

- le vecteur des coefficients de la fonction objectif (c)
- la matrice des contraintes (A)
- le vecteur du second membre (b)
- le type de contraintes (≤, =, ≥)
- le type d’optimisation (maximisation ou minimisation)

3. STRUCTURE GÉNÉRALE DU CODE

Le programme est composé d’une fonction principale et de plusieurs fonctions secondaires.

2
 3.1 Fonction principale : auto_simplex
La fonction auto_simplex constitue le cœur du programme. Elle réalise les opérations suivantes :
- lecture des données entrées par l’utilisateur
- analyse du type de contraintes
- choix automatique de la méthode de résolution
- appel de la fonction appropriée
- affichage de la solution optimale

Exemple de saisie dans MATLAB :

c = [3 5]
A = [1 0; 0 2; 3 2]
b = [4; 12; 18]
ctype = [-1 -1 -1]
Type = 1

Dans ce cas :
- -1 représente une contrainte ≤
- 1 représente une contrainte ≥
- 0 représente une égalité

4. Méthodes de résolution utilisées

4.1 Méthode du simplexe primal
La méthode du simplexe primal est utilisée lorsque toutes les contraintes sont de type ≤ et que le
second membre est positif. Le programme ajoute alors des variables d’écart (slack) afin de
transformer les contraintes en égalités.

Par exemple :
x1 + x2 ≤ 5
devient
x1 + x2 + s1 = 5

où s1 est la variable d’écart.

4.2 Méthode du simplexe via la dualité

Lorsque le problème est un problème de minimisation avec des contraintes ≥, il peut être plus
efficace de résoudre le problème dual.

Le programme construit automatiquement le problème dual :

Primal : min c^T x avec Ax ≥ b
Dual : max b^T u avec A^T u ≤ c

3
Après la résolution du problème dual, la solution du problème primal est reconstruite à partir des
contraintes actives.

4.3 Méthode des deux phases

Lorsque le problème ne peut pas être directement résolu par le simplexe primal, la méthode des
deux phases est utilisée.

Phase 1 : introduction de variables artificielles et minimisation de leur somme afin de trouver une
solution de base réalisable.

Phase 2 : remplacement de la fonction objectif artificielle par la fonction objectif réelle et

poursuite de l’algorithme du simplexe jusqu’à l’optimalité.

5. Fonction de pivot du simplexe

Le cœur de l’algorithme du simplexe est l’opération de pivot. Chaque itération comprend :
1. Choix de la colonne pivot (variable entrante)
2. Calcul du test des ratios b_i / a_ij
3. Choix de la ligne pivot (variable sortante)
4. Normalisation de la ligne pivot
5. Élimination des autres coefficients de la colonne pivot

Le processus continue jusqu’à ce que tous les coefficients de la ligne objectif soient positifs ou
nuls, ce qui indique que la solution optimale est atteinte.

6. Affichage des résultats

À la fin de l’exécution, le programme affiche la solution optimale ainsi que la valeur optimale de
la fonction objectif.

Voici le code:

function automatic_simplex()
clc;

%% =============================
% Entrée utilisateur
%% =============================
fprintf('Entrez c = [coefficients de l''objectif]\n');
c = input('c = ');

fprintf('Entrez A = [coefficients des contraintes]\n');

4
A = input('A = ');

fprintf('Entrez b = [second membre]\n');

b = input('b = ');

fprintf('Valeur de ctype = [-1 pour <= ; 0 pour = ; 1 pour

>=]\n');
ctype = input('ctype = ');

fprintf('Type objectif (1 = Max, 0 = Min) : ');

obj_type = input('Type = ');

[m,n] = size(A);

%% =============================
% Choix automatique de la méthode
%% =============================
use_dual = false;

if all(ctype == -1) && all(b >= 0)

fprintf('\nMéthode choisie : SIMPLEXE PRIMAL\n');
if obj_type == 0 % Min ? multiplier par -1 pour primal
[sol, z] = solve_primal(-c, A, b);
z = -z;
else
[sol, z] = solve_primal(c, A, b);
end

elseif all(ctype == 1) && obj_type == 0

% Min avec contraintes >= ? Dual
fprintf('\nMéthode choisie : SIMPLEXE DU DUAL (par
transformation)\n');
[sol, z] = solve_via_duality(c, A, b);
use_dual = true;

elseif all(ctype == -1) && obj_type == 1

% Max avec <= ? Primal
fprintf('\nMéthode choisie : SIMPLEXE PRIMAL\n');
[sol, z] = solve_primal(c, A, b);

else
fprintf('\nMéthode choisie : DEUX PHASES\n');
[sol, z] = solve_two_phases(c, A, b, ctype);
end

5
%% =============================
% Affichage de la solution
%% =============================
fprintf('\n==============================\n');
fprintf('SOLUTION OPTIMALE\n');

if use_dual
fprintf('Solution calculée via dual.\n');
end
disp(sol);

fprintf('Z = %.6f\n', z);

end

%% =============================
% FONCTION PRIMAL SIMPLEXE
%% =============================
function [x_opt,z_opt] = solve_primal(c,A,b)
[m,n] = size(A);
A = [A eye(m)];
tab = [A b; -c zeros(1,m+1)];
basis = n+1:n+m;

[tab,basis] = primal_pivot(tab,basis);

x = zeros(n+m,1);
x(basis) = tab(1:m,end);
x_opt = x(1:n);
z_opt = tab(end,end);
end

%% =============================
% FONCTION DUAL
%% =============================
function [x_opt,z_opt] = solve_via_duality(c,A,b)
[m,n] = size(A);

% Construction dual : max b^T u, A^T u <= c

c_dual = b';
A_dual = A';
b_dual = c';

6
fprintf('\n--- PROBLEME DUAL CONSTRUIT ---\n');

[u_opt, ~] = solve_primal(c_dual, A_dual, b_dual);

tol = 1e-8;
idx_actives = find(u_opt > tol);

% Extraire uniquement les contraintes actives

A_active = A(idx_actives,:);
b_active = b(idx_actives);

if rank(A_active) < n
error('Le système actif ne permet pas une solution
unique.');
end

x_primal = A_active \ b_active;

z_opt = c(:)' * x_primal;
x_opt = x_primal;

fprintf('\n--- SOLUTION PRIMALE TROUVÉE ---\n');

disp(x_opt)
fprintf('Z_min = %.6f\n', z_opt);

end

%% =============================
% FONCTION DEUX PHASES
%% =============================
function [x_opt,z_opt] = solve_two_phases(c,A,b,ctype)
[m,n] = size(A);
A_aug = A;
basis = [];
artificial = [];

% Construction de la matrice augmentée

for i = 1:m
e = zeros(m,1); e(i) = 1;
if ctype(i) == -1
% <= : slack
A_aug = [A_aug e];
basis = [basis size(A_aug,2)];
elseif ctype(i) == 1
% >= : surplus + artificielle

7
 A_aug = [A_aug -e]; % surplus
A_aug = [A_aug e]; % artificielle
artificial = [artificial size(A_aug,2)];
basis = [basis size(A_aug,2)];
elseif ctype(i) == 0
% = : artificielle
A_aug = [A_aug e];
artificial = [artificial size(A_aug,2)];
basis = [basis size(A_aug,2)];
end
end

%% Phase 1
fprintf('\n========== PHASE 1 ==========\n');
c_phase1 = zeros(1,size(A_aug,2));
c_phase1(artificial) = 1;
tab = [A_aug b; c_phase1 0];

% Mise en forme canonique

for k = 1:length(basis)
if ismember(basis(k), artificial)
tab(end,:) = tab(end,:) - tab(k,:);
end
end

[tab,basis] = primal_pivot(tab,basis);

if abs(tab(end,end)) > 1e-8

error('Problème infaisable.');
end

% Supprimer colonnes artificielles

tab(:,artificial) = [];
for k = 1:length(basis)
shift = sum(artificial < basis(k));
basis(k) = basis(k) - shift;
end

%% Phase 2
fprintf('\n========== PHASE 2 ==========\n');
tab(end,:) = 0;
tab(end,1:n) = -c;

for i = 1:m

8
 col = basis(i);
tab(end,:) = tab(end,:) - tab(end,col)*tab(i,:);
end

[tab,basis] = primal_pivot(tab,basis);

x = zeros(size(tab,2)-1,1);
x(basis) = tab(1:m,end);
x_opt = x(1:n);
z_opt = tab(end,end);
end

%% =============================
% FONCTION PIVOT PRIMAL
%% =============================
function [tab,basis] = primal_pivot(tab,basis)
[m,n] = size(tab);
iter = 0;
tol = 1e-10;

while any(tab(end,1:n-1) < -tol)

iter = iter + 1;
fprintf('\nItération %d\n', iter);
disp(tab);

[~, col] = min(tab(end,1:n-1));

ratios = inf(m-1,1);
for i = 1:m-1
if tab(i,col) > tol
ratios(i) = tab(i,end) / tab(i,col);
end
end

if all(isinf(ratios))
error('Problème non borné ou mauvaise initialisation
de base.');
end

[~, row] = min(ratios);

tab(row,:) = tab(row,:) / tab(row,col);

for i = 1:m
if i ~= row

9
 tab(i,:) = tab(i,:) - tab(i,col)*tab(row,:);
end
end

basis(row) = col;
end

fprintf('\nTableau final :\n');

disp(tab);
end

Voici une exemple de calcul faite avec ce code:

Entrez c = [coefficients de l'objectif]

c = [3 5]

Entrez A = [coefficients des contraintes]

A = [1 -1;1 1]

Entrez b = [second membre]

b = [0;9]

Valeur de ctype = [-1 pour <= ; 0 pour = ; 1 pour >=]

ctype = [1;-1]

Type objectif (1 = Max, 0 = Min) : Type = 1

Méthode choisie : DEUX PHASES

========== PHASE 1 ==========

Itération 1

1 -1 -1 1 0 0

1 1 0 0 1 9

-1 1 1 0 0 0

Tableau final :

10
 1 -1 -1 1 0 0

0 2 1 -1 1 9

0 0 0 1 0 0

========== PHASE 2 ==========

Itération 1

1 -1 -1 0 0

0 2 1 1 9

0 -8 -3 0 0

Tableau final :

1.0000 0 -0.5000 0.5000 4.5000

0 1.0000 0.5000 0.5000 4.5000

0 0 1.0000 4.0000 36.0000

==============================

SOLUTION OPTIMALE

4.5000

4.5000

Z = 36.000000

7. Conclusion
Le programme Automatic Simplex développé dans ce travail permet de résoudre
automatiquement différents types de problèmes de programmation linéaire. Il combine plusieurs
approches de résolution, notamment le simplexe primal, la dualité et la méthode des deux phases.

L’avantage principal de ce programme est sa capacité à sélectionner automatiquement la méthode

la plus adaptée en fonction de la structure du problème. De plus, l’affichage des tableaux du
simplexe à chaque itération permet de mieux comprendre le fonctionnement de l’algorithme.

Cet outil constitue donc un support pédagogique utile pour l’apprentissage des méthodes
d’optimisation et leur application pratique.

11