Licence Mathématiques

Appliquées
Recherche Opérationnelle

Travaux pratiques dans la

programmation linéaire par la
méthode de Simplex

Réalisé par : Mzioued Dounia

Mrhili Nisrine
Encadré par :Abouir Jilali
 SOMMAIRE
...............................................................................................................................................................1
Introduction...........................................................................................................................................3
TP2.........................................................................................................................................................7
I. Variables de décision  :...................................................................................................................7
Identification des variables de décision...........................................................................................7
II. Contraintes  :..............................................................................................................................7
Formulation des contraintes :..........................................................................................................8
III. Fonction objective  :....................................................................................................................8
IV. Solution Informatique  :.............................................................................................................8
Algorithme Lindo :...........................................................................................................................9
TP3.......................................................................................................................................................14
Problème de production1  :..................................................................................................................14
I. Variables de décision  :.................................................................................................................14
Identification des variables de décision :......................................................................................14
II. Contraintes  :............................................................................................................................14
Formulation des contraintes :........................................................................................................14
III. Fonction objective  :..................................................................................................................15
IV. Solution informatique (LINDO)  :..............................................................................................15
Algorithme LINDO :......................................................................................................................15
I. Variables de décision  :.................................................................................................................29
II. Contraintes:..............................................................................................................................29
Formulation des contraintes :........................................................................................................29
III. Fonction objective:...................................................................................................................29
IV. Solution informatique (LINDO)  :..............................................................................................29
ALGORITHME LINDO:..............................................................................................................30
.............................................................................................................................................................31
.............................................................................................................................................................31
Conclusion  :.........................................................................................................................................31
 Introduction
Un programme linéaire (PL) est un problème d’optimisation
consistant à maximiser (ou minimiser) une fonction objectif
linéaire de n variables de décision soumises à un ensemble de
contraintes exprimées sous forme d’équations ou d’inéquations
linéaires.
A l’origine, le terme programme a le sens de planification
opérationnelle mais il est aujourd’hui employé comme synonyme
de problème (d’optimisation).
La terminologie est due à G. B. Dantzig, inventeur de l’algorithme du
simplexe (1947).

Un des algorithmes utilisé pour résoudre ce type de problèmes est la

méthode du simplexe.

Théorie de la décision Programmation mathématique Combinatoire

Pascal (1654) Théorie de Graphe
Fermat (1654) Fourier (1824) Sainte-Laguë(1926)
Bernouilli(1713) König(1936)

Recherche opérationnelle

Première application militaire,

Bataille aérienne de Grande-Bretagne :

Meilleure utilisation des moyens disponibles

Simplexe

Premier grand algorithme (1947)

Premier ordinateur

Première application commerciale (1956)

L’algorithme du simplexe fut proposé en 1947 par Dantzig comme
méthode de résolution algébrique des programmes linéaires à
plusieurs variables. La solution optimale étant une solution de base
(point extrême ou sommet de la région réalisable), la méthode du
simplexe est une méthode itérative et consiste à partir d’un sommet
vers un sommet adjacent de manière à améliorer la fonction objective
à chaque itération jusqu’à aboutir à a solution optimale.
Le nombre des sommets pour un PL à n variables et m contraintes est
n!
de l’ordre m! ( n−m ) ! qui est assez grand pour m et n relativement
grands. Le principe de la méthode du simplexe propose de n’explorer
qu’un nombre limité de sommets parmi lesquelles se trouve à coup sûr
la solution optimale.
L’algorithme du simplexe consiste à :
1. mettre le programme sous une forme standard,
2. déterminer une solution de base (ou bien détecter l’impossibilité),
3. faire subir un test d’optimalité à cette solution de base pour
déterminer s’il s’agit ou non de la solution optimale,
- s’il s’agit de la solution optimale, le problème est terminé,
- s’il ne s’agit pas de la solution optimale, on passe à l’étape 4.,
4. changer de solution de base puis reprendre la procédure au 3.
Jusqu’à l’obtention de la solution optimale (ou bien détecter une
fonction objective non bornée). Chaque changement de solution de
base constitue une itération.
Nous présenterons dans cette section une résolution analytique en
détaillant deux procédures : méthode (ou algorithme) Simplexe et
tableaux Simplexe.
L'idée de l'algorithme du simplexe est de passer de base réalisable en
base réalisable en améliorant à chaque fois la valeur du critère.
Comme le nombre de bases est fini, on obtient l'optimum ou la preuve
que le programme est non borné en un nombre fini d'étapes.

Algorithme du Simplexe
TODO
step 0 : (Initialisation)
Soit B un ensemble d’indices de base initiale tel que la solution de base primale associ´ee xB est r
´ealisable.

Calculer xB = A−1 Bb et yT = cT A−1. BB

step 1 : (Test d’Optimalite)´

TT y A .
Calculer les couˆts r´eduits c−
N N
TT y A≤ 0 alors la solution courante est optimale.
Si c−
N N
Sinon choisir r ∈/ B tel que cr − yT ar >
0. xr entre en base)
(→

step 2 : (Pivot)
D´eterminer la variable qui sort de la base (→ xs).
S’il n’en existe aucune, alors le probl`eme est non born´e.
Mettre `a jour l’ensemble d’indices de bases B et d´eterminer les nouvelles solutions de
base xB et yB.
R`egle de Bland
s’il y a deux ou plusieurs variables qui peuvent entrer en base, alors on choisit celle qui a le plus
petit indice ;
s’il y a deux ou plusieurs variables qui peuvent sortir de la base, alors on choisit celle qui a le
plus petit indice ;

Lindo est un logiciel utilisé pour résoudre les modèles d’optimisation

linéaires, entiers et quadratiques. Une des caractéristiques de Lindo
c’est qu’il offre des outils qui peuvent aider à l’analyse des modèles
en utilisant la méthode de Simplexe.

TP2
Sélection d’un portefeuille d’investissements

I. Variables de décision  :

 Les inconnues de ce problème d’investissement sont : les portefeuilles

d’investissements pour une société.
 Il y a 6 variables de décision :
Identification des variables de décision
X₁ : montant à investir (en$) dans la société Simco (Pétrole)
X₂ : montant à investir (en$) dans la société Plurimax (Pétrole)
X₃ : montant à investir (en$) dans la société Microtel (Electronique)
X₄ : montant à investir (en$) dans la société CAX Electronique
(Electronique)
X₅ : montant à investir (en$) dans la société Biomed (Pharmaceutique)
X₆ : montant à investir (en$) dans la société Coronex (Pharmaceutique)

II. Contraintes  :

Les restrictions qui ont été imposées concernant les possibilités

d’investissements :
 1) Les fonds disponibles représentent un montant de 250 000$.
2) Les investissements dans le secteur pharmaceutique devraient représenter au
moins 30% des investissements dans un secteur électronique.
3) Aucun secteur d’activités ne devrait se voir allouer plus de 55% des fonds
disponibles.
4) Limiter le montant investi dans cette société à 60% des investissements dans
le secteur électronique.
5) Investir au moins 15000$ dans l’industrie pétrolière.
Formulation des contraintes :
 Fonds disponible :
X ₁+ X ₂+ X ₃+ X ₄+ X ₅+ X ₆ ≤250000

 Investissement dans le secteur pharmaceutique :

X ₅+ X ₆ ≥ 0.3( X ₃+ X ₄)
 Investissement maximal dans les différents secteurs :
X ₁+ X ₂ ≤137500
X ₃+ X ₄ ≤ 137500
X ₅+ X ₆ ≤ 137500
 Restriction concernant l’investissement dans la société Microtel :
X ₃=¿0.6(X₃ +X₄)

 Exigence concernant le montant à investir dans l’industrie pétrolière :

X ₁+ X ₂ ≥15000

 Positivité : Xⱼ ≥0, j=1, …, 6

III. Fonction objective  :

L’objectif est de maximiser le rendement anticipé. On aura donc la fonction

objective suivant à maximiser :
Z=0,0935X₁+0,08X₂+0,109X₃+0,078X₄+0,096X₅+0,085X₆
Z : les intérêts anticipés (en $) pour les différents investissements.

IV. Solution Informatique  :

 On utilise le modèle suivant pour appliquer l’algorithme en utilisant le
logiciel LINDO :

X ₁+ X ₂≤ 137500 X ₁+ X ₂≤ 137500

{ {
X ₃+ X ₄ ≤137500 X ₃+ X ₄ ≤137500
X ₅+ X ₆ ≤137500 X ₅+ X ₆ ≤137500
X ₁+ X ₂+ X ₃+ X ₄ + X ₅+ X ₆ ≤ 250000 X ₁+ X ₂+ X ₃+ X ₄ + X ₅+ X ₆ ≤ 250000
X ₅+ X ₆ ≥ 0.3( X ₃+ X ₄) ⇒ X ₅+ X ₆−0.3 X ₃+ 0.3 X ₄ ≥ 0
X ₃=0.6( X ₃+ X ₄) 0.4 X ₃−0.6 X ₄=0
X ₁+ X ₂≥ 15000 X ₁+ X ₂≥ 15000
X ⱼ≥ 0 , j=1 , … , 6 X ⱼ≥ 0 , j=1 , … , 6

Algorithme Lindo :
MAX 0.0935X1+0.08X2+0.109X3+0.078X4+0.096X5+0.085X6
SUBJECT TO
2)X1+X2<=137500
3)X3+X4<=137500
4)X5+X6<=137500
5)X1+X2+X3+X4+X5+X6<=250000
6)X5+X6-0.3X3+0.3X4>=0
7)0.4X3-0.6X4=0
8)X1+X2>=15000
END

Execution:
THE TABLEAU

ROW (BASIS) X1 X2 X3 X4 X5 X6
1 ART -0.094 -0.080 -0.109 -0.078 -0.096 -0.085
2 SLK 2 1.000 1.000 0.000 0.000 0.000 0.000
3 SLK 3 0.000 0.000 1.000 1.000 0.000 0.000
4 SLK 4 0.000 0.000 0.000 0.000 1.000 1.000
5 SLK 5 1.000 1.000 1.000 1.000 1.000 1.000
6 SLK 6 0.000 0.000 0.300 -0.300 -1.000 -1.000
7 ART 0.000 0.000 0.400 -0.600 0.000 0.000
8 SLK 8 -1.000 -1.000 0.000 0.000 0.000 0.000
ART ART -1.000 -1.000 0.000 0.000 0.000 0.000

ROW SLK 2 SLK 3 SLK 4 SLK 5 SLK 6 SLK 8

1 0.000 0.000 0.000 0.000 0.000 0.000 0.000
2 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.14E+06
3 0.00E+00 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.14E+06
4 0.00E+00 0.00E+00 1.0 0.00E+00 0.00E+00 0.00E+00 0.14E+06
5 0.00E+00 0.00E+00 0.00E+00 1.0 0.00E+00 0.00E+00 0.25E+06
6 0.000 0.000 0.000 0.000 1.000 0.000 0.000
7 0.000 0.000 0.000 0.000 0.000 0.000 0.000
8 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.00E+00 1.0 -0.15E+05
ART 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.00E+00 -0.15E+05

X1 ENTERS AT VALUE 0.13750E+06 IN ROW 2 OBJ. VALUE= 12856.

 1ere itération:
THE TABLEAU

ROW (BASIS) X1 X2 X3 X4 X5 X6
1 ART 0.000 0.014 -0.109 -0.078 -0.096 -0.085
2 X1 1.000 1.000 0.000 0.000 0.000 0.000
3 SLK 3 0.000 0.000 1.000 1.000 0.000 0.000
4 SLK 4 0.000 0.000 0.000 0.000 1.000 1.000
5 SLK 5 0.000 0.000 1.000 1.000 1.000 1.000
6 SLK 6 0.000 0.000 0.300 -0.300 -1.000 -1.000
7 ART 0.000 0.000 0.400 -0.600 0.000 0.000
8 SLK 8 0.000 0.000 0.000 0.000 0.000 0.000
ART ART 0.000 0.014 -0.109 -0.078 -0.096 -0.085

ROW SLK 2 SLK 3 SLK 4 SLK 5 SLK 6 SLK 8

1 0.094 0.000 0.000 0.000 0.000 0.000 12856.250
2 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.14E+06
3 0.00E+00 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.14E+06
4 0.00E+00 0.00E+00 1.0 0.00E+00 0.00E+00 0.00E+00 0.14E+06
5 -1.0 0.00E+00 0.00E+00 1.0 0.00E+00 0.00E+00 0.11E+06
6 0.000 0.000 0.000 0.000 1.000 0.000 0.000
7 0.000 0.000 0.000 0.000 0.000 0.000 0.000
8 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 1.0 0.12E+06
ART 0.094 0.000 0.000 0.000 0.000 0.000 0.000

X5 ENTERS AT VALUE 0.11250E+06 IN ROW 5 OBJ. VALUE= 23656.

2eme iteration:
THE TABLEAU

ROW (BASIS) X1 X2 X3 X4 X5 X6
1 ART 0.000 0.014 -0.013 0.018 0.000 0.011
2 X1 1.000 1.000 0.000 0.000 0.000 0.000
3 SLK 3 0.000 0.000 1.000 1.000 0.000 0.000
4 SLK 4 0.000 0.000 -1.000 -1.000 0.000 0.000
5 X5 0.000 0.000 1.000 1.000 1.000 1.000
6 SLK 6 0.000 0.000 1.300 0.700 0.000 0.000
7 ART 0.000 0.000 0.400 -0.600 0.000 0.000
8 SLK 8 0.000 0.000 0.000 0.000 0.000 0.000

ROW SLK 2 SLK 3 SLK 4 SLK 5 SLK 6 SLK 8

1 -0.002 0.000 0.000 0.096 0.000 0.000 23656.250
2 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.14E+06
3 0.00E+00 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.14E+06
4 1.000 0.000 1.000 -1.000 0.000 0.000 25000.000
5 -1.0 0.00E+00 0.00E+00 1.0 0.00E+00 0.00E+00 0.11E+06
6 -1.0 0.00E+00 0.00E+00 1.0 1.0 0.00E+00 0.11E+06
7 0.000 0.000 0.000 0.000 0.000 0.000 0.000
8 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 1.0 0.12E+06

X3 ENTERS AT VALUE 0.00000E+00 IN ROW 7 OBJ. VALUE= 23656.

3eme iteration:
THE TABLEAU

ROW (BASIS) X1 X2 X3 X4 X5 X6
1 ART 0.000 0.014 0.000 -0.001 0.000 0.011
2 X1 1.000 1.000 0.000 0.000 0.000 0.000
3 SLK 3 0.000 0.000 0.000 2.500 0.000 0.000
4 SLK 4 0.000 0.000 0.000 -2.500 0.000 0.000
5 X5 0.000 0.000 0.000 2.500 1.000 1.000
6 SLK 6 0.000 0.000 0.000 2.650 0.000 0.000
7 X3 0.000 0.000 1.000 -1.500 0.000 0.000
8 SLK 8 0.000 0.000 0.000 0.000 0.000 0.000

ROW SLK 2 SLK 3 SLK 4 SLK 5 SLK 6 SLK 8

1 -0.002 0.000 0.000 0.096 0.000 0.000 23656.250
2 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.14E+06
3 0.00E+00 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.14E+06
4 1.000 0.000 1.000 -1.000 0.000 0.000 25000.000
5 -1.0 0.00E+00 0.00E+00 1.0 0.00E+00 0.00E+00 0.11E+06
6 -1.0 0.00E+00 0.00E+00 1.0 1.0 0.00E+00 0.11E+06
7 0.000 0.000 0.000 0.000 0.000 0.000 0.000
8 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 1.0 0.12E+06

X4 ENTERS AT VALUE 42453. IN ROW 6 OBJ. VALUE= 23720.

4eme iteration:
THE TABLEAU

ROW (BASIS) X1 X2 X3 X4 X5 X6
1 ART 0.000 0.014 0.000 0.000 0.000 0.011
2 X1 1.000 1.000 0.000 0.000 0.000 0.000
3 SLK 3 0.000 0.000 0.000 0.000 0.000 0.000
4 SLK 4 0.000 0.000 0.000 0.000 0.000 0.000
5 X5 0.000 0.000 0.000 0.000 1.000 1.000
6 X4 0.000 0.000 0.000 1.000 0.000 0.000
7 X3 0.000 0.000 1.000 0.000 0.000 0.000
8 SLK 8 0.000 0.000 0.000 0.000 0.000 0.000

ROW SLK 2 SLK 3 SLK 4 SLK 5 SLK 6 SLK 8

1 -0.003 0.000 0.000 0.097 0.001 0.000 23719.930
2 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.00E+00 0.14E+06
3 0.943 1.000 0.000 -0.943 -0.943 0.000 31367.924
4 0.57E-01 0.00E+00 1.0 -0.57E-01 0.94 0.00E+00 0.13E+06
5 -0.057 0.000 0.000 0.057 -0.943 0.000 6367.924
6 -0.377 0.000 0.000 0.377 0.377 0.000 42452.832
7 -0.566 0.000 0.000 0.566 0.566 0.000 63679.246
8 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 1.0 0.12E+06

SLK 2 ENTERS AT VALUE 33250. IN ROW 3 OBJ. VALUE= 23822.

5eme iteration:

THE TABLEAU
 ROW (BASIS) X1 X2 X3 X4 X5 X6
1 ART 0.000 0.014 0.000 0.000 0.000 0.011
2 X1 1.000 1.000 0.000 0.000 0.000 0.000
3 SLK 2 0.000 0.000 0.000 0.000 0.000 0.000
4 SLK 4 0.000 0.000 0.000 0.000 0.000 0.000
5 X5 0.000 0.000 0.000 0.000 1.000 1.000
6 X4 0.000 0.000 0.000 1.000 0.000 0.000
7 X3 0.000 0.000 1.000 0.000 0.000 0.000
8 SLK 8 0.000 0.000 0.000 0.000 0.000 0.000

ROW SLK 2 SLK 3 SLK 4 SLK 5 SLK 6 SLK 8

1 0.000 0.003 0.000 0.094 -0.002 0.000 23821.875
2 0.00E+00 -1.1 0.00E+00 1.0 1.0 0.00E+00 0.10E+06
3 1.000 1.060 0.000 -1.000 -1.000 0.000 33250.000
4 0.28E-16 -0.60E-01 1.0 -0.28E-16 1.0 0.00E+00 0.13E+06
5 0.000 0.060 0.000 0.000 -1.000 0.000 8250.000
6 0.000 0.400 0.000 0.000 0.000 0.000 55000.000
7 0.000 0.600 0.000 0.000 0.000 0.000 82500.000
8 0.000 -1.060 0.000 1.000 1.000 1.000 89250.000

SLK 6 ENTERS AT VALUE 89250. IN ROW 8 OBJ. VALUE= 24045.

6eme iteration:
THE TABLEAU

ROW (BASIS) X1 X2 X3 X4 X5 X6
1 ART 0.000 0.014 0.000 0.000 0.000 0.011
2 X1 1.000 1.000 0.000 0.000 0.000 0.000
3 SLK 2 0.000 0.000 0.000 0.000 0.000 0.000
4 SLK 4 0.000 0.000 0.000 0.000 0.000 0.000
5 X5 0.000 0.000 0.000 0.000 1.000 1.000
6 X4 0.000 0.000 0.000 1.000 0.000 0.000
7 X3 0.000 0.000 1.000 0.000 0.000 0.000
8 SLK 6 0.000 0.000 0.000 0.000 0.000 0.000

ROW SLK 2 SLK 3 SLK 4 SLK 5 SLK 6 SLK 8

1 0.000 0.001 0.000 0.096 0.000 0.002 24045.000
2 0.000 0.000 0.000 0.000 0.000 -1.000 15000.000
3 1.0 0.00E+00 0.00E+00 0.00E+00 0.00E+00 1.0 0.12E+06
4 0.000 1.000 1.000 -1.000 0.000 -1.000 40000.000
5 0.000 -1.000 0.000 1.000 0.000 1.000 97500.000
6 0.000 0.400 0.000 0.000 0.000 0.000 55000.000
7 0.000 0.600 0.000 0.000 0.000 0.000 82500.000
8 0.000 -1.060 0.000 1.000 1.000 1.000 89250.000

LP OPTIMUM FOUND AT STEP 6

OBJECTIVE FUNCTION VALUE

1) 24045.00

VARIABLE VALUE REDUCED COST

X1 15000.000000 0.000000
X2 0.000000 0.013500
X3 82500.000000 0.000000
X4 55000.000000 0.000000
X5 97500.000000 0.000000
 X6 0.000000 0.011000

ROW SLACK OR SURPLUS DUAL PRICES

2) 122500.000000 0.000000
3) 0.000000 0.000600
4) 40000.000000 0.000000
5) 0.000000 0.096000
6) 89250.000000 0.000000
7) 0.000000 0.031000
8) 0.000000 -0.002500

NO. ITERATIONS= 6

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 0.093500 0.002500 0.013500
X2 0.080000 0.013500 INFINITY
X3 0.109000 INFINITY 0.001000
X4 0.078000 INFINITY 0.001500
X5 0.096000 0.000600 0.002500
X6 0.085000 0.011000 INFINITY

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 137500.000000 INFINITY 122500.000000
3 137500.000000 84198.117188 40000.000000
4 137500.000000 INFINITY 40000.000000
5 250000.000000 40000.000000 89250.000000
6 0.000000 89250.000000 INFINITY
7 0.000000 55000.000000 82500.000000
8 15000.000000 89250.000000 15000.000000

La solution réalisable de base (optimale) est :

X1 =15000
X2= 0
X3= 82500
X4 =55000
X5=97500
X6=0
Z=24045.00$
Interprétation :

Pour maximiser le rendement anticipé, d’une part on doit investir un montant de

15 000$ dans la société Simco,82500$ dans la société Microtel, 55 000$ dans la
société CAX électronique, 97 500$ dans la société Biomed. D’autre part on ne
dot rien investir dans les deux sociétés Plurimax et Coronex.
Les intérêts des investissements sont de montant 24045$.
24045∗100
Le rendement sur ces investissements est de 9.62% tel que R= 250000 =9.62$

TP3
Problème de production1  :

I. Variables de décision  :

 Les inconnues de ce problème d’investissement sont : les produits

AE100, AE200, AE300.
 Il y a trois variables de décision :
Identification des variables de décision :

X₁ : nombre d’unités à fabriquer par mois du produits AE100.

X₂ : nombre d’unités à fabriquer par mois du produits AE200.
X₃ : nombre d’unités à fabriquer par mois du produits AE300.
II. Contraintes  :
Formulation des contraintes :
Estampillage : 0.3 X₁ +1.5 X₂+0.5 X₃ ≤600
Perçage :1.5 X₁ +1.2 X₂+1 X₃ ≤1200
Assemblage :2 X₁ +3 X₂+ X₃ ≤1760
Vérification : 0.5 X₁ + X₂+0.5 X₃≤ 550
Emballage :0.2 X₁ +0.6 X₂+0.2 X₃≤ 250
200 ≤X₁ ≤520
120 ≤X₂≤400
340 ≤X₃≤700
X₁+ X₂+ X₃ ≤800

III. Fonction objective  :

Maximiser les bénéficies de l’entreprise tout en respectant es disponibilités

des ressources de l’entreprise et les exigences Xtronic.
On aura donc la fonction objective suivant à maximiser :
Z=80 X₁+37 X₂+70 X₃
Tel que : C₁=240-160=80
C₂=125-88=37
C₃=190-120=70

IV. Solution informatique (LINDO)  :

On utilise le modèle suivant pour appliquer l’algorithme en utilisant le logiciel

LINDO :
0.3 X ₁+1.5 X ₂+0.5 X ₃ ≤ 600∧¿ 1.5 X ₁+1.2 X ₂+1 X ₃ ≤1200

{
2 X ₁+3 X ₂+ X ₃ ≤1760
0.5 X ₁+ X ₂+0.5 X ₃ ≤ 550
0.2 X ₁+0.6 X ₂+0.2 X ₃ ≤ 250
200 ≤ X ₁≤ 520
120 ≤ X ₂ ≤ 400
340 ≤ X ₃≤ 700
0.8 X ₁+ X ₂+0.8 X ₃ ≤ 800
X ⱼ ≥0 , j=1 ,2,3

Algorithme LINDO :
MAX 80X1+37X2+70X3
SUBJECT TO
2)0.3X1+1.5X2+0.5X3<=600
3)1.5X1+1.2X2+X3<=1200
4)2X1+3X2+X3<=1760
5)0.5X1+X2+0.5X3<=550
6)0.2X1+0.6X2+0.2X3<=250
7)0.8X1+X2+0.8X3<=800
8)X1<=520
9)X1>=200
10)X2<=400
11)X2>=120
12)X3<=700
13)X3>=340
END

EXECUTION :
THE TABLEAU

ROW (BASIS) X1 X2 X3 SLK 2 SLK 3

SLK 4
1 ART -80.000 -37.000 -70.000 0.000 0.000
0.000
2 SLK 2 0.300 1.500 0.500 1.000 0.000
0.000
3 SLK 3 1.500 1.200 1.000 0.000 1.000
0.000
4 SLK 4 2.000 3.000 1.000 0.000 0.000
1.000
5 SLK 5 0.500 1.000 0.500 0.000 0.000
0.000
6 SLK 6 0.200 0.600 0.200 0.000 0.000
0.000
7 SLK 7 0.800 1.000 0.800 0.000 0.000
0.000
8 SLK 8 1.000 0.000 0.000 0.000 0.000
0.000
9 SLK 9 -1.000 0.000 0.000 0.000 0.000
0.000
 10 SLK 10 0.000 1.000 0.000 0.000 0.000
0.000
11 SLK 11 0.000 -1.000 0.000 0.000 0.000
0.000
12 SLK 12 0.000 0.000 1.000 0.000 0.000
0.000
13 SLK 13 0.000 0.000 -1.000 0.000 0.000
0.000
ART ART -1.000 -1.000 -1.000 0.000 0.000
0.000

ROW SLK 5 SLK 6 SLK 7 SLK 8 SLK 9 SLK 10

SLK 11
1 0.000 0.000 0.000 0.000 0.000 0.000
0.000
2 0.000 0.000 0.000 0.000 0.000 0.000
0.000
3 0.000 0.000 0.000 0.000 0.000 0.000
0.000
4 0.000 0.000 0.000 0.000 0.000 0.000
0.000
5 1.000 0.000 0.000 0.000 0.000 0.000
0.000
6 0.000 1.000 0.000 0.000 0.000 0.000
0.000
7 0.000 0.000 1.000 0.000 0.000 0.000
0.000
8 0.000 0.000 0.000 1.000 0.000 0.000
0.000
9 0.000 0.000 0.000 0.000 1.000 0.000
0.000
10 0.000 0.000 0.000 0.000 0.000 1.000
0.000
11 0.000 0.000 0.000 0.000 0.000 0.000
1.000
12 0.000 0.000 0.000 0.000 0.000 0.000
0.000
13 0.000 0.000 0.000 0.000 0.000 0.000
0.000
ART 0.000 0.000 0.000 0.000 0.000 0.000
0.000

ROW SLK 12 SLK 13

1 0.000 0.000 0.000
2 0.000 0.000 600.000
3 0.000 0.000 1200.000
4 0.000 0.000 1760.000
5 0.000 0.000 550.000
6 0.000 0.000 250.000
7 0.000 0.000 800.000
8 0.000 0.000 520.000
9 0.000 0.000 -200.000
10 0.000 0.000 400.000
11 0.000 0.000 -120.000
12 1.000 0.000 700.000
13 0.000 1.000 -340.000
 ART 0.000 0.000 -660.000

X1 ENTERS AT VALUE 520.00 IN ROW 8 OBJ. VALUE= 41600.

1ere itération :
THE TABLEAU

ROW (BASIS) X1 X2 X3 SLK 2 SLK 3

SLK 4
1 ART 0.000 -37.000 -70.000 0.000 0.000
0.000
2 SLK 2 0.000 1.500 0.500 1.000 0.000
0.000
3 SLK 3 0.000 1.200 1.000 0.000 1.000
0.000
4 SLK 4 0.000 3.000 1.000 0.000 0.000
1.000
5 SLK 5 0.000 1.000 0.500 0.000 0.000
0.000
6 SLK 6 0.000 0.600 0.200 0.000 0.000
0.000
7 SLK 7 0.000 1.000 0.800 0.000 0.000
0.000
8 X1 1.000 0.000 0.000 0.000 0.000
0.000
9 SLK 9 0.000 0.000 0.000 0.000 0.000
0.000
10 SLK 10 0.000 1.000 0.000 0.000 0.000
0.000
11 SLK 11 0.000 -1.000 0.000 0.000 0.000
0.000
12 SLK 12 0.000 0.000 1.000 0.000 0.000
0.000
13 SLK 13 0.000 0.000 -1.000 0.000 0.000
0.000
ART ART 0.000 -1.000 -1.000 0.000 0.000
0.000

ROW SLK 5 SLK 6 SLK 7 SLK 8 SLK 9 SLK 10

SLK 11
1 0.000 0.000 0.000 80.000 0.000 0.000
0.000
2 0.000 0.000 0.000 -0.300 0.000 0.000
0.000
3 0.000 0.000 0.000 -1.500 0.000 0.000
0.000
4 0.000 0.000 0.000 -2.000 0.000 0.000
0.000
5 1.000 0.000 0.000 -0.500 0.000 0.000
0.000
6 0.000 1.000 0.000 -0.200 0.000 0.000
0.000
7 0.000 0.000 1.000 -0.800 0.000 0.000
0.000
8 0.000 0.000 0.000 1.000 0.000 0.000
0.000
 9 0.000 0.000 0.000 1.000 1.000 0.000
0.000
10 0.000 0.000 0.000 0.000 0.000 1.000
0.000
11 0.000 0.000 0.000 0.000 0.000 0.000
1.000
12 0.000 0.000 0.000 0.000 0.000 0.000
0.000
13 0.000 0.000 0.000 0.000 0.000 0.000
0.000
ART 0.000 0.000 0.000 0.000 0.000 0.000
0.000

ROW SLK 12 SLK 13

1 0.000 0.000 41600.000
2 0.000 0.000 444.000
3 0.000 0.000 420.000
4 0.000 0.000 720.000
5 0.000 0.000 290.000
6 0.000 0.000 146.000
7 0.000 0.000 384.000
8 0.000 0.000 520.000
9 0.000 0.000 320.000
10 0.000 0.000 400.000
11 0.000 0.000 -120.000
12 1.000 0.000 700.000
13 0.000 1.000 -340.000
ART 0.000 0.000 -460.000

X2 ENTERS AT VALUE 240.00 IN ROW 4 OBJ. VALUE= 50480.

2eme itération :
THE TABLEAU

ROW (BASIS) X1 X2 X3 SLK 2 SLK 3

SLK 4
1 ART 0.000 0.000 -57.667 0.000 0.000
12.333
2 SLK 2 0.000 0.000 0.000 1.000 0.000
-0.500
3 SLK 3 0.000 0.000 0.600 0.000 1.000
-0.400
4 X2 0.000 1.000 0.333 0.000 0.000
0.333
5 SLK 5 0.000 0.000 0.167 0.000 0.000
-0.333
6 SLK 6 0.000 0.000 0.000 0.000 0.000
-0.200
7 SLK 7 0.000 0.000 0.467 0.000 0.000
-0.333
8 X1 1.000 0.000 0.000 0.000 0.000
0.000
9 SLK 9 0.000 0.000 0.000 0.000 0.000
0.000
 10 SLK 10 0.000 0.000 -0.333 0.000 0.000
-0.333
11 SLK 11 0.000 0.000 0.333 0.000 0.000
0.333
12 SLK 12 0.000 0.000 1.000 0.000 0.000
0.000
13 SLK 13 0.000 0.000 -1.000 0.000 0.000
0.000
ART ART 0.000 0.000 -1.000 0.000 0.000
0.000

ROW SLK 5 SLK 6 SLK 7 SLK 8 SLK 9 SLK 10

SLK 11
1 0.000 0.000 0.000 55.333 0.000 0.000
0.000
2 0.000 0.000 0.000 0.700 0.000 0.000
0.000
3 0.000 0.000 0.000 -0.700 0.000 0.000
0.000
4 0.000 0.000 0.000 -0.667 0.000 0.000
0.000
5 1.000 0.000 0.000 0.167 0.000 0.000
0.000
6 0.000 1.000 0.000 0.200 0.000 0.000
0.000
7 0.000 0.000 1.000 -0.133 0.000 0.000
0.000
8 0.000 0.000 0.000 1.000 0.000 0.000
0.000
9 0.000 0.000 0.000 1.000 1.000 0.000
0.000
10 0.000 0.000 0.000 0.667 0.000 1.000
0.000
11 0.000 0.000 0.000 -0.667 0.000 0.000
1.000
12 0.000 0.000 0.000 0.000 0.000 0.000
0.000
13 0.000 0.000 0.000 0.000 0.000 0.000
0.000
ART 0.000 0.000 0.000 0.000 0.000 0.000
0.000

ROW SLK 12 SLK 13

1 0.000 0.000 50480.000
2 0.000 0.000 84.000
3 0.000 0.000 132.000
4 0.000 0.000 240.000
5 0.000 0.000 50.000
6 0.000 0.000 2.000
7 0.000 0.000 144.000
8 0.000 0.000 520.000
9 0.000 0.000 320.000
10 0.000 0.000 160.000
11 0.000 0.000 120.000
12 1.000 0.000 700.000
13 0.000 1.000 -340.000
 ART 0.000 0.000 -340.000

X3 ENTERS AT VALUE 220.00 IN ROW 3 OBJ. VALUE= 63167.

3eme itération :
THE TABLEAU

ROW (BASIS) X1 X2 X3 SLK 2 SLK 3

SLK 4
1 ART 0.000 0.000 0.000 0.000 96.111
-26.111
2 SLK 2 0.000 0.000 0.000 1.000 0.000
-0.500
3 X3 0.000 0.000 1.000 0.000 1.667
-0.667
4 X2 0.000 1.000 0.000 0.000 -0.556
0.556
5 SLK 5 0.000 0.000 0.000 0.000 -0.278
-0.222
6 SLK 6 0.000 0.000 0.000 0.000 0.000
-0.200
7 SLK 7 0.000 0.000 0.000 0.000 -0.778
-0.022
8 X1 1.000 0.000 0.000 0.000 0.000
0.000
9 SLK 9 0.000 0.000 0.000 0.000 0.000
0.000
10 SLK 10 0.000 0.000 0.000 0.000 0.556
-0.556
11 SLK 11 0.000 0.000 0.000 0.000 -0.556
0.556
12 SLK 12 0.000 0.000 0.000 0.000 -1.667
0.667
13 SLK 13 0.000 0.000 0.000 0.000 1.667
-0.667
ART ART 0.000 0.000 0.000 0.000 1.667
-0.667

ROW SLK 5 SLK 6 SLK 7 SLK 8 SLK 9 SLK 10

SLK 11
1 0.000 0.000 0.000 -11.944 0.000 0.000
0.000
2 0.000 0.000 0.000 0.700 0.000 0.000
0.000
3 0.000 0.000 0.000 -1.167 0.000 0.000
0.000
4 0.000 0.000 0.000 -0.278 0.000 0.000
0.000
5 1.000 0.000 0.000 0.361 0.000 0.000
0.000
6 0.000 1.000 0.000 0.200 0.000 0.000
0.000
7 0.000 0.000 1.000 0.411 0.000 0.000
0.000
 8 0.000 0.000 0.000 1.000 0.000 0.000
0.000
9 0.000 0.000 0.000 1.000 1.000 0.000
0.000
10 0.000 0.000 0.000 0.278 0.000 1.000
0.000
11 0.000 0.000 0.000 -0.278 0.000 0.000
1.000
12 0.000 0.000 0.000 1.167 0.000 0.000
0.000
13 0.000 0.000 0.000 -1.167 0.000 0.000
0.000
ART 0.000 0.000 0.000 -1.167 0.000 0.000
0.000

ROW SLK 12 SLK 13

1 0.000 0.000 63166.668
2 0.000 0.000 84.000
3 0.000 0.000 220.000
4 0.000 0.000 166.667
5 0.000 0.000 13.333
6 0.000 0.000 2.000
7 0.000 0.000 41.333
8 0.000 0.000 520.000
9 0.000 0.000 320.000
10 0.000 0.000 233.333
11 0.000 0.000 46.667
12 1.000 0.000 480.000
13 0.000 1.000 -120.000
ART 0.000 0.000 -120.000

SLK 8 ENTERS AT VALUE 10.000 IN ROW 6 OBJ. VALUE= 63286.

4eme itération :
THE TABLEAU

ROW (BASIS) X1 X2 X3 SLK 2 SLK 3

SLK 4
1 ART 0.000 0.000 0.000 0.000 96.111
-38.056
2 SLK 2 0.000 0.000 0.000 1.000 0.000
0.200
3 X3 0.000 0.000 1.000 0.000 1.667
-1.833
4 X2 0.000 1.000 0.000 0.000 -0.556
0.278
5 SLK 5 0.000 0.000 0.000 0.000 -0.278
0.139
6 SLK 8 0.000 0.000 0.000 0.000 0.000
-1.000
7 SLK 7 0.000 0.000 0.000 0.000 -0.778
0.389
8 X1 1.000 0.000 0.000 0.000 0.000
1.000
 9 SLK 9 0.000 0.000 0.000 0.000 0.000
1.000
10 SLK 10 0.000 0.000 0.000 0.000 0.556
-0.278
11 SLK 11 0.000 0.000 0.000 0.000 -0.556
0.278
12 SLK 12 0.000 0.000 0.000 0.000 -1.667
1.833
13 SLK 13 0.000 0.000 0.000 0.000 1.667
-1.833
ART ART 0.000 0.000 0.000 0.000 1.667
-1.833

ROW SLK 5 SLK 6 SLK 7 SLK 8 SLK 9 SLK 10

SLK 11
1 0.000 59.722 0.000 0.000 0.000 0.000
0.000
2 0.000 -3.500 0.000 0.000 0.000 0.000
0.000
3 0.000 5.833 0.000 0.000 0.000 0.000
0.000
4 0.000 1.389 0.000 0.000 0.000 0.000
0.000
5 1.000 -1.806 0.000 0.000 0.000 0.000
0.000
6 0.000 5.000 0.000 1.000 0.000 0.000
0.000
7 0.000 -2.056 1.000 0.000 0.000 0.000
0.000
8 0.000 -5.000 0.000 0.000 0.000 0.000
0.000
9 0.000 -5.000 0.000 0.000 1.000 0.000
0.000
10 0.000 -1.389 0.000 0.000 0.000 1.000
0.000
11 0.000 1.389 0.000 0.000 0.000 0.000
1.000
12 0.000 -5.833 0.000 0.000 0.000 0.000
0.000
13 0.000 5.833 0.000 0.000 0.000 0.000
0.000
ART 0.000 5.833 0.000 0.000 0.000 0.000
0.000

ROW SLK 12 SLK 13

1 0.000 0.000 63286.109
2 0.000 0.000 77.000
3 0.000 0.000 231.667
4 0.000 0.000 169.444
5 0.000 0.000 9.722
6 0.000 0.000 10.000
7 0.000 0.000 37.222
8 0.000 0.000 510.000
9 0.000 0.000 310.000
10 0.000 0.000 230.556
11 0.000 0.000 49.444
 12 1.000 0.000 468.333
13 0.000 1.000 -108.333
ART 0.000 0.000 -108.333

SLK 4 ENTERS AT VALUE 70.000 IN ROW 5 OBJ. VALUE= 65950.

5eme itération :
THE TABLEAU

ROW (BASIS) X1 X2 X3 SLK 2 SLK 3

SLK 4
1 ART 0.000 0.000 0.000 0.000 20.000
0.000
2 SLK 2 0.000 0.000 0.000 1.000 0.400
0.000
3 X3 0.000 0.000 1.000 0.000 -2.000
0.000
4 X2 0.000 1.000 0.000 0.000 0.000
0.000
5 SLK 4 0.000 0.000 0.000 0.000 -2.000
1.000
6 SLK 8 0.000 0.000 0.000 0.000 -2.000
0.000
7 SLK 7 0.000 0.000 0.000 0.000 0.000
0.000
8 X1 1.000 0.000 0.000 0.000 2.000
0.000
9 SLK 9 0.000 0.000 0.000 0.000 2.000
0.000
10 SLK 10 0.000 0.000 0.000 0.000 0.000
0.000
11 SLK 11 0.000 0.000 0.000 0.000 0.000
0.000
12 SLK 12 0.000 0.000 0.000 0.000 2.000
0.000
13 SLK 13 0.000 0.000 0.000 0.000 -2.000
0.000
ART ART 0.000 0.000 0.000 0.000 20.000
0.000

ROW SLK 5 SLK 6 SLK 7 SLK 8 SLK 9 SLK 10

SLK 11
1 274.000 -435.000 0.000 0.000 0.000 0.000
0.000
2 -1.440 -0.900 0.000 0.000 0.000 0.000
0.000
3 13.200 -18.000 0.000 0.000 0.000 0.000
0.000
4 -2.000 5.000 0.000 0.000 0.000 0.000
0.000
5 7.200 -13.000 0.000 0.000 0.000 0.000
0.000
6 7.200 -8.000 0.000 1.000 0.000 0.000
0.000
 7 -2.800 3.000 1.000 0.000 0.000 0.000
0.000
8 -7.200 8.000 0.000 0.000 0.000 0.000
0.000
9 -7.200 8.000 0.000 0.000 1.000 0.000
0.000
10 2.000 -5.000 0.000 0.000 0.000 1.000
0.000
11 -2.000 5.000 0.000 0.000 0.000 0.000
1.000
12 -13.200 18.000 0.000 0.000 0.000 0.000
0.000
13 13.200 -18.000 0.000 0.000 0.000 0.000
0.000
ART 274.000 -435.000 0.000 0.000 0.000 0.000
0.000

ROW SLK 12 SLK 13

1 0.000 0.000 65950.000
2 0.000 0.000 63.000
3 0.000 0.000 360.000
4 0.000 0.000 150.000
5 0.000 0.000 70.000
6 0.000 0.000 80.000
7 0.000 0.000 10.000
8 0.000 0.000 440.000
9 0.000 0.000 240.000
10 0.000 0.000 250.000
11 0.000 0.000 30.000
12 1.000 0.000 340.000
13 0.000 1.000 20.000
ART 0.000 0.000 0.000

SLK 6 ENTERS AT VALUE 3.3333 IN ROW 7 OBJ. VALUE= 67400.

6eme itération :
THE TABLEAU

ROW (BASIS) X1 X2 X3 SLK 2 SLK 3

SLK 4
1 ART 0.000 0.000 0.000 0.000 20.000
0.000
2 SLK 2 0.000 0.000 0.000 1.000 0.400
0.000
3 X3 0.000 0.000 1.000 0.000 -2.000
0.000
4 X2 0.000 1.000 0.000 0.000 0.000
0.000
5 SLK 4 0.000 0.000 0.000 0.000 -2.000
1.000
6 SLK 8 0.000 0.000 0.000 0.000 -2.000
0.000
7 SLK 6 0.000 0.000 0.000 0.000 0.000
0.000
 8 X1 1.000 0.000 0.000 0.000 2.000
0.000
9 SLK 9 0.000 0.000 0.000 0.000 2.000
0.000
10 SLK 10 0.000 0.000 0.000 0.000 0.000
0.000
11 SLK 11 0.000 0.000 0.000 0.000 0.000
0.000
12 SLK 12 0.000 0.000 0.000 0.000 2.000
0.000
13 SLK 13 0.000 0.000 0.000 0.000 -2.000
0.000

ROW SLK 5 SLK 6 SLK 7 SLK 8 SLK 9 SLK 10

SLK 11
1 -132.000 0.000 145.000 0.000 0.000 0.000
0.000
2 -2.280 0.000 0.300 0.000 0.000 0.000
0.000
3 -3.600 0.000 6.000 0.000 0.000 0.000
0.000
4 2.667 0.000 -1.667 0.000 0.000 0.000
0.000
5 -4.933 0.000 4.333 0.000 0.000 0.000
0.000
6 -0.267 0.000 2.667 1.000 0.000 0.000
0.000
7 -0.933 1.000 0.333 0.000 0.000 0.000
0.000
8 0.267 0.000 -2.667 0.000 0.000 0.000
0.000
9 0.267 0.000 -2.667 0.000 1.000 0.000
0.000
10 -2.667 0.000 1.667 0.000 0.000 1.000
0.000
11 2.667 0.000 -1.667 0.000 0.000 0.000
1.000
12 3.600 0.000 -6.000 0.000 0.000 0.000
0.000
13 -3.600 0.000 6.000 0.000 0.000 0.000
0.000

ROW SLK 12 SLK 13

1 0.000 0.000 67400.000
2 0.000 0.000 66.000
3 0.000 0.000 420.000
4 0.000 0.000 133.333
5 0.000 0.000 113.333
6 0.000 0.000 106.667
7 0.000 0.000 3.333
8 0.000 0.000 413.333
9 0.000 0.000 213.333
10 0.000 0.000 266.667
11 0.000 0.000 13.333
12 1.000 0.000 280.000
13 0.000 1.000 80.000
 SLK 5 ENTERS AT VALUE 5.0000 IN ROW 11 OBJ. VALUE= 68060.

7eme itération :
THE TABLEAU

ROW (BASIS) X1 X2 X3 SLK 2 SLK 3

SLK 4
1 ART 0.000 0.000 0.000 0.000 20.000
0.000
2 SLK 2 0.000 0.000 0.000 1.000 0.400
0.000
3 X3 0.000 0.000 1.000 0.000 -2.000
0.000
4 X2 0.000 1.000 0.000 0.000 0.000
0.000
5 SLK 4 0.000 0.000 0.000 0.000 -2.000
1.000
6 SLK 8 0.000 0.000 0.000 0.000 -2.000
0.000
7 SLK 6 0.000 0.000 0.000 0.000 0.000
0.000
8 X1 1.000 0.000 0.000 0.000 2.000
0.000
9 SLK 9 0.000 0.000 0.000 0.000 2.000
0.000
10 SLK 10 0.000 0.000 0.000 0.000 0.000
0.000
11 SLK 5 0.000 0.000 0.000 0.000 0.000
0.000
12 SLK 12 0.000 0.000 0.000 0.000 2.000
0.000
13 SLK 13 0.000 0.000 0.000 0.000 -2.000
0.000

ROW SLK 5 SLK 6 SLK 7 SLK 8 SLK 9 SLK 10

SLK 11
1 0.000 0.000 62.500 0.000 0.000 0.000
49.500
2 0.000 0.000 -1.125 0.000 0.000 0.000
0.855
3 0.000 0.000 3.750 0.000 0.000 0.000
1.350
4 0.000 0.000 0.000 0.000 0.000 0.000
-1.000
5 0.000 0.000 1.250 0.000 0.000 0.000
1.850
6 0.000 0.000 2.500 1.000 0.000 0.000
0.100
7 0.000 1.000 -0.250 0.000 0.000 0.000
0.350
8 0.000 0.000 -2.500 0.000 0.000 0.000
-0.100
 9 0.000 0.000 -2.500 0.000 1.000 0.000
-0.100
10 0.000 0.000 0.000 0.000 0.000 1.000
1.000
11 1.000 0.000 -0.625 0.000 0.000 0.000
0.375
12 0.000 0.000 -3.750 0.000 0.000 0.000
-1.350
13 0.000 0.000 3.750 0.000 0.000 0.000
1.350

ROW SLK 12 SLK 13

1 0.000 0.000 68060.000
2 0.000 0.000 77.400
3 0.000 0.000 438.000
4 0.000 0.000 120.000
5 0.000 0.000 138.000
6 0.000 0.000 108.000
7 0.000 0.000 8.000
8 0.000 0.000 412.000
9 0.000 0.000 212.000
10 0.000 0.000 280.000
11 0.000 0.000 5.000
12 1.000 0.000 262.000
13 0.000 1.000 98.000

LP OPTIMUM FOUND AT STEP 7

OBJECTIVE FUNCTION VALUE

1) 68060.00

VARIABLE VALUE REDUCED COST

X1 412.000000 0.000000
X2 120.000000 0.000000
X3 438.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 77.400002 0.000000
3) 0.000000 20.000000
4) 138.000000 0.000000
5) 5.000000 0.000000
6) 8.000000 0.000000
7) 0.000000 62.500000
8) 108.000000 0.000000
9) 212.000000 0.000000
10) 280.000000 0.000000

La solution réalisable de base (optimale) est :

X1 =412
Interprétation :
D’après la résolution du programme, il faut produire 412 unités de AE100 ,120
unités de AE200, 438 unités de AE300.
En respectant les disponibilités des ressources de l’entreprise et les exigences du
marché on peut bénéficier jusqu’à 68060$.

Problème de production2:

I. Variables de décision  :

 Les inconnues du problème sont les nombres d’unités à fabriquer par mois
pour chaque produit l’entreprise du bois fabrique.
  On définit 4 variables de décision :
X1 : nombres d’unités à fabriquer par mois de produit CHAISES.
X2 : nombres d’unités à fabriquer par mois de produit TABLES.
X3 : nombres d’unités à fabriquer par mois de produit BUREAUX.
X4 : nombres d’unités à fabriquer par mois de produit ARMOIRES.

II. Contraintes:
Le temps disponible à l’atelier de menuiserie est de 800h/mois :
1.5X1+3X2+8X3+6X4<=800
Le temps disponible à l’atelier de finition est de 600h/mois :
0.5X1+X2+12X3+9X4<=600
Formulation des contraintes :
1.5X1+3X2+8X3+6X4<=800
0.5X1+X2+12X3+9X4<=600

III. Fonction objective:

Maximiser les bénéfices tout en n’excédant pas les temps disponibles à chaque
atelier :
Z=6X1+15X2+40X3+25X4

IV. Solution informatique (LINDO)  :

On utilise le modèle suivant pour appliquer l’algorithme en utilisant le logiciel

LINDO :
1.5 X 1+3 X 2+8 X 3+6 X 4 ≤ 800
{
0.5 X 1+ X 2+ 12 X 3+ 9 X 4 ≤ 600
Xj ≥ 0 j=1 , .. , 4

ALGORITHME LINDO:

MAX 6X1+15X2+40X3+25X4
SUBJECT TO
1)1.5X1+3X2+8X3+6X4<=800
2)0.5X1+X2+12X3+9X4<=600
END
THE TABLEAU

ROW (BASIS) X1 X2 X3 X4 SLK 2

1 ART -6.000 -15.000 -40.000 -25.000 0.000
1 SLK 2 1.500 3.000 8.000 6.000 1.000
2 SLK 3 0.500 1.000 12.000 9.000 0.000
ART ART -6.000 -15.000 -40.000 -25.000 0.000

ROW SLK 3
1 0.000 0.000
1 0.000 800.000
2 1.000 600.000
ART 0.000 0.000

X2 ENTERS AT VALUE 266.67 IN ROW 2 OBJ. VALUE= 4000.0

1ere itération:
THE TABLEAU

ROW (BASIS) X1 X2 X3 X4 SLK 2

1 ART 1.500 0.000 0.000 5.000 5.000
1 X2 0.500 1.000 2.667 2.000 0.333
2 SLK 3 0.000 0.000 9.333 7.000 -0.333

ROW SLK 3
1 0.000 4000.000
1 0.000 266.667
2 1.000 333.333

LP OPTIMUM FOUND AT STEP 1

OBJECTIVE FUNCTION VALUE

1) 4000.000

VARIABLE VALUE REDUCED COST

X1 0.000000 1.500000
X2 266.666656 0.000000
X3 0.000000 0.000000
X4 0.000000 5.000000

ROW SLACK OR SURPLUS DUAL PRICES

1) 0.000000 5.000000
2) 333.333344 0.000000

NO. ITERATIONS= 1

La solution Réalisable (optimale) est :

X1=0
X2=266
Interprétation :

D’prés la solution du programme il faut produire 266 unités des tables par contre
on peut produire aucun autre produit. Par conséquent on bénéficie de 3900 DH
par mois.

Conclusion  :
Pour des problèmes complexes impliquant de nombreuses variables, la
méthode de Simplex est beaucoup plus rapide que les autres
algorithmes de résolution de systèmes linéaires. L'efficacité de la
méthode Simplex est important pour la programmation informatique,
comme le besoin de puissance de traitement est de réduire
considérablement lors de son utilisation.