Correction de devoir maison n1 :

Exercice 11 :
Les données de l’exercice :
PV1 PV1 OFFRES
R1 3 4 100
R2 1 3 20
Demandes 40 80

a) Formulation mathèmatique:

Puisque l’entreprise veut savoir comment acheminer la marchandise, donc les variables de
dècision sont :
Xij : ”quantitè de carburant à acheminer de la raffinerie i vers le point de vent j” , avec : i = 1,2
et j = 1 , 2 ; où :
-raffinerie 1 : RA
-raffinerie 2 : RB
-point de vente 1 : PV1
-pointdevente2:PV2 .
Xij ≥ 0  i=1,2 , j=1,2.

Contraintes de l’offre : une raffinerie ne peut vendre plus que sa production max :
X11 + X12 ≤ 100
X21 + X22 ≤ 20

Contraintes de la demande : la quantitè à acheminer vers un point de vente est au moins sa

demande min :
X11 + X21 ≥ 40
X12 + X22 ≥ 80

La fonction objectif : l’objectif vise à minimiser le coût total de transport, dont l’expression
mathèmatique est :
Min(Z) = 3X11 + 4X12 + X21 + 3X22.

Si on somme les deux premiéres contraintes, on obtient :

X11 +X12 +X21 +X22 ≤ 120
Aussi,si on somme les deux derniéres contraintes, on obtient : X11 + X21 + X12 + X22 ≥ 120 Donc, X11 + X12 + X21 + X22 =
120 car l’offre = demande. Toutes les contraintes peuvent alors être mise sous forme d’ ́egalitès.

Ainsi le PL (P).
X11 + X12 = 100
X21 + X22 = 20
X11 + X21 = 40
X12 + X22 = 80
Xij ≥0,i=1,2etj=1,2
min Z = 3X11 + 4X12 + X21 + X22.

b) Le programme linéaire dual :

On fait correspondre aux contraintes de l’offre les variables u i et aux contraintes de demande les variables vj, i = 1,2 et j =
1,2.
u 1 + v1 ≤ 3
u 1 + v2 ≤ 4
u 2 + v1 ≤ 1
u 2 + v2 ≤ 3
ui ∈R,vj ∈R,i=1,2etj=1,2.
MaxW = 100u1 + 20u2 + 40v1 + 80v2.
c) Interprètation économique du dual:
Le problème dual exprime le point de vue du transporteur qui veut maximiser son profit. Ses variables sont les prix d’achat
à la raffinerie 1 (u1) et à la raffinerie 2 (u1) et ses prix de vente à PV1 (v1) et à PV2 (v1).

d)Résoudre le (PL) par l’algorithme du simplexe :

(Pour appliquer l’algorithme du simplexe j’ai changé les notations des variables comme suite X 1,1 = X1 , X1,2 = X2 , X2,1 = X3 , X2,2
= X4).

Parceque le problème d'optimisation n'a pas une solution base valide pour commencer l'algorithme du simplexe on utilise
a méthode de deux phases. D'abord on ajouter les variables d’écart et les variables artificielles et puis on applique
l’algorithme du simplexe avec une nouvelle fonction objectif .
Et on obtient le PL auxiliaire suivant :
X1 + X 2 + X5 = 100.

X 3 + X4 + X6 = 20.

X1 + X3 - X7 + V1 =40…………. (1)

+ X2 + X4. – X8 + V2 =80…………. (2)

V 1 + V2 = min W……… (*)

De (1) et (2) on a :

V1 = 40 - X1 -X3 +X7 et V2 = 80 - X2 – X4 + X8

Alors (*) devient :

- X1 - X2 - X3 – X4 +X7 + X8 = min W – 120.

(On commence avec X5, X6, V1, V2 comme variables de base)

Phase 1 :

X1 X2 X3 X4 X5 X6 X7 X8 V1 V2 b
X5 1 1 0 0 1 0 0 0 0 0 100
X6 0 0 1 1 0 1 0 0 0 0 20
V1 1 0 1 0 0 0 -1 0 1 0 40
V2 0 1 0 1 0 0 0 -1 0 1 80
-W -1 -1 -1 -1 0 0 1 1 0 0 -120

C1 = -1 <0 alors S= 1

I= {i: A1i >0} = {1}

⇒
L= {l: bl\ A1l = min { bi\ A1i} } = {40} ❑ r= 3 ; col(r)= V1.

X1 X2 X3 X4 X5 X6 X7 X8 V1 V2 b
X5 0 1 -1 0 1 0 1 0 -1 0 60
X6 0 0 1 1 0 1 0 0 0 0 20
X1 1 0 1 0 0 0 -1 0 1 0 40
V2 0 1 0 1 0 0 0 -1 0 1 80
-W 0 -1 0 -1 0 0 0 1 1 0 -80

C2= -1 <0 alors S= 2

I= {i: A2i >0} = {1}

 ⇒
L= {l: bl\ A2l = min { bi\ A2i} } = {60} ❑ r= 1 ; col(r)= X5.

X1 X2 X3 X4 X5 X6 X7 X8 V1 V2 b
X2 0 1 -1 0 1 0 1 0 -1 0 60
X6 0 0 1 1 0 1 0 0 0 0 20
X1 1 0 1 0 0 0 -1 0 1 0 40
V2 0 0 1 1 -1 0 -1 -1 1 1 20
-W 0 0 -1 -1 1 0 1 1 0 0 -20

C3= -1 <0 alors S= 3

I= {i: A3i >0} = {1}

⇒
L= {l: bl\ A3l = min { bi\ A2i} } = {20} ❑ r= 2 ; col(r)= X6.

X1 X2 X3 X4 X5 X6 X7 X8 V1 V2 b
X2 0 1 0 1 0 1 1 0 -1 0 80
X3 0 0 1 1 0 1 0 0 0 0 20
X1 1 0 0 -1 0 -1 -1 0 1 0 20
V2 0 0 0 0 -1 -1 -1 -1 1 1 00
-W 0 0 0 0 1 1 1 1 0 0 00

W=0 alors on s’arrête là. On a donc terminé la phase 1 et maintenant on a une solution réalisable
pour le PL initiale il nous reste donc qu’à vérifier Si cette solution est optimale.

Pour cela on peut procéder en appliquant le simplexe encore une fois mais cette fois avec les
coefficients qu’on a eu à la fin du phase 1 en remplaçant la fonction objectif W avec celle du PL
initiale Z et en supprimant la 4éme contrainte contenant la variable artificielle V 2 (i.e on applique la
Phase 2 de simplexe). Sinon on a qu’à écrire le PL sous forme canonique dans la base réalisable
qu’on a eu J= (X2, X3, X1).

Posant A la matrice associée au PL dans la base canonique en supprimant la contrainte (2) avec la
variable artificielle V2).
1 0 1
j
A =0 1 0 le det |AJ|=1#0 alors Aj est inversible.
0 1 1

On utilisant la méthode de gausse on chercher l’inverse de A j , (Aj)-1 :

1 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 1 −1
j=
A 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0
0 1 1 0 0 1 0 0 1 0 −1 1 0 0 1 0 −1 1

Alors :
1 1 −1
i -1
(A ) = 0 1 0
0 −1 1

Maintenant cherchons la matrice associé au (PL) dans la base J , ^A  :

1 1 −1 1 1 00 0 1 0 1
A  = (Ai)-1 * A
^ = 0 1 0 * 0 0 11 = 0 0 1 1
0 −1 1 1 0 10 1 0 0 −1

Le second membre dans la base J,~b  :

80
~
b = (Ai)-1 * b = 20
20

Et enfin le cout de transport dans la base J, ~

C  :
 0 1 0 1
~
C = C- Ci * ^
A = ( 3 4 1 3) – ( 4 1 3) * 0 0 1 1 = ( 0 0 0 1 ).
1 0 0 −1

Puisqu’il s’agit d’un problème de minimisation et ~

C >= 0 ❑ ⇒ alors la base J est une une base
*
optimale pour le (PL) et donc la solution X est une solution optimale du (PL) avec :

X* = (20,80,20,00) i.e. : (X1,1=20 , X2,1 =80, X2,1=20 ,X2,2=00)

Cela veut dire que pour satisfaire les demandes des clients en minimisant les couts de transport et
en respectant les quantités du production max des raffineries l’entreprise doit transporter :

- 20 unités du Raffinerie A vers le point de vente 1.

- 80 unités du Raffinerie A vers le point de vente 2.

- 20 unités du Raffinerie B vers le point de vente 1.

Avec un coût minimum totale Z*= 400.

e) Résoudre le (PL) avec l’algorithme de transport :

Méthode du coin nord-ouest :

PV 1 PV 2

3 4
→ →
Raffinerie A 100 ❑ 60 ❑ 0
40 60

1 3 →
20 ❑ 0
Raffinerie B
20 →
40 ❑ 0 →
80 ❑ →
20 ❑ 0

Puisque tous les rangés (lignes et colonnes sont éliminés i.e : l`offre est alloués) on arrête le processus
et une solution réalisable de base est obtenue :
UB= {X1,1 = 40, X1,2 = 60, X2,1 = 0, X2,2 = 20}.
Le coût totale de transport correspondant à cette base est :
Z = 40*3 + 60*4 + 0*1 + 20*3 = 420.
Vérifiant maintenant si cette base est optimale :
Par le théorème des écarts complémentaires on sait que si X* est une solution optimale du primale et (U*, V*)
est une solution optimale du dual alors :
Ui + Vj = Ci,j si Xi,j*> et Ui + Vj <= Ci,j si Xi,j*=0 .
On a Δij = Ui + Vj – CIJ avec (i,j) dans UB.
On aura donc :
U1 + V1 = 3
U1 + V2 = 4
U2 + V2 = 3
On pose U1= 0 et on résout le système on obtient : V1 =3 , V2 = 4 , U2 = -1.
On sait aussi par le critère d’optimalité que :
Δij<= 0 pour tout (i,j) pas dans UB est suffisant pour l’optimalité.
Dans notre cas :
Δ2.1 = U2 + V1 – C2,1 = -1+3-1=1 > 0
Alors la solution de base actuelle n’est pas optimale.
Changement de base :
On crée un cycle à l’aide de la case (2,1) et les cases de U B (qui est unique) et dans le sens des aiguilles d’une
montre on affecte successivement des signes + et – au sommets de cycle en commençant par la case (2,1)
affecté par un +.
On retrouve le cycle {(2,1), (1,1), (1,2), (2,2)}, les case (sommets) affecté par un signe – sont (1,1) et (2,2) on
prend le min entre eux Min{X1,1 , X2,2} = { 40,20} =20 et on pose ß=20 .
Pour tous les sommets marqués + on rajoute ß=20 et pour tous les sommets marqués – on soustrait 20 et on
obtient donc une nouvelle base.

PV1 PV2 PV1 PV2

- 3 + 4 3 4
RA RA
40 60 20 80
+ 1 - 3 1 3
RB RB
20 20 00

Alors la nouvelle base est :

UB = {X1,1 = 20, X2,2 =80, X2,1=20}
Z= 20*3 + 80*4 + 20*1 = 400.
On refait le test d’optimalité sur la nouvelle base obtenue :
U1 + V1 = 3
U1 + V2 = 4
U2 + V1 = 1
En posant U1=0 on aura : V1=3 , V2 =4 , U2= -2.
Vérifiant maintenant les Δi,j avec (i,j) qui n’appartienne pas à UB :
Δ2,2= U2 + V2 – C2,2 = -2+4-3= -1 < 0 d’où l’optimalité.
Alors la nouvelle base obtenue est une solution optimale pour notre problème de transport.
L’entreprise doit transporter :
 20 unités du raffinerie 1 vers le point de vente 1.
 80 unités du raffinerie 1 vers le point de vente 2.
 20 unités du raffinerie 2 vers le point de vente 1.
Avec un coût minimum totale de transport égale à Z*=400.

La résolution du problème avec le solveur Cplex :

le modèle :

/*********************************************
* OPL 12.9.0.0 Model
* Author: shiishii
* Creation Date: Apr 17, 2020 at 3:02:42 PM
*********************************************/
int n=...;

range raff=1..n;
range pv=1..n;
int couts[raff][pv]=...;
int demande[pv]=...;
int production[raff]=...;

dvar float+ x[raff][pv];

dexpr float cost=sum(i in raff ,j in pv) x[i][j]*couts[i][j];

minimize cost;
subject to {
forall(i in raff)
contrprod:
sum(j in pv ) x[i][j] <= production[i];
forall (j in pv)
 contrdemande:
sum(i in raff) x[i][j]>= demande[j];
}

Les données:

n=2;

couts =[[3,4],[1,3]];
production =[100,20] ;
demande=[40,80];

Solution données :

[ 20 80 ]
X= 20 00 X1,1 = 20 , X2,1 = 80 , X2,1 = 20, X2,2 =0