Scribd
Importer
48 vues13 pages

TP Recherche Opérationnelle

Transféré par

Elvis El
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
48 vues13 pages

TP Recherche Opérationnelle

Transféré par

Elvis El
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

WEMAKOYE ELANGA ELVIS

L1 ECONOMIE INDUSTRIELLE
U.O.M

TRAVAIL PRATIQUE DU COURS DE RECHERCHE OPERATIONNELLE

1. Objectif de l’entreprise
L’objectif de l’entreprise est d’attirer le maximum de clients tout en respectant les
contraintes budgétaires et les exigences spécifiques concernant les différents modes de
publicité.

2. Détermination des quantités relatives à l’objectif poursuivi par l’entreprise.

Pour maximiser le nombre de clients atteints tout en respectant les contraintes, nous
devons optimiser le nombre d’annonces pour chaque mode de publicité. Voici les
données et les contraintes :

Formalisation du problème linéaire


Identification des variables de décision
X1 = Nombre d’annonces sur la Télévision TNT
X2 =Nombre d’annonces sur la Télévision Satellite
X3 = Nombre d’annonces à la Radi
X4 =Nombre d’annonces sur Internet
Forme canonique
Max Z = 200 X1 + 450 X2 + 250 X3 + 380 X4

Sous-
400X1+750X2+300X3+500X4 ≤ 8000
contraintes :
140X1+200X2+110X3+250X4 ≥ 2000
400X1+750X2 ≤ 400
X1 ≥ 4
X2 ≥ 2
X3 ≥ 5
X3 ≤ 10
X4 ≥ 5
X4 ≤ 10
Avec X1, X2, X3, X4 ≥ 0

1
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M
Forme standard

Max Z = 200 X1 + 450 X2 + 250 X3 + 380 X4 + 0 S1 + 0 S2 + 0 S3 + 0 S4 + 0 S5 + 0 S6 + 0 S7 + 0 S8 + 0 S9 - M V1 - M V2 - M V3 - M V4 - M V5

Sous-contraintes :

400X1+750X2+300X3+500X4+ S1 =8000

140X1+200X2+110X3+250X4 - S2 + V1 =2000

400X1+750X2 + S3 =400

X1 - S4 + V2 =4

X2 - S5 + V3 =2

X3 - S6 + V4 =5

X3 + S7 =10

X4 - S8 + V5=5

X4 + S9 =10

Avec X1, X2, X3, X4, S1, S2, S3, S4, S5, S6, S7, S8, S9, V1, V2, V3, V4, V5 ≥ 0

2
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M
RESOLUTION DU PROBLEME

Cj 200 450 250 380 0 0 0 0 0 0 0 0 0 -M -M -M -M -M

CB B b X1 X2 X3 X4 S1 S2 S3 S4 S5 S6 S7 S8 S9 V1 V2 V3 V4 V5

0 S1 8000 400 750 300 500 1 0 0 0 0 0 0 0 0 0 0 0 0 0

-M V1 2000 140 200 110 250 0 -1 0 0 0 0 0 0 0 1 0 0 0 0

0 S3 400 400 750 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

-M V2 4 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0 0

-M V3 2 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0

-M V4 5 0 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0

0 S7 10 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

-M V5 5 0 0 0 (1) 0 0 0 0 0 0 0 -1 0 0 0 0 0 1

0 S9 10 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0

Z=-2016M Zj -141M -201M -111M -251M 0 M 0 M M M 0 M 0 -M -M -M -M -M

3
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M
Cj-Zj 141M+200 201M+450 111M+250 251M+380↑ 0 -M 0 -M -M -M 0 -M 0 0 0 0 0 0

TABLEAU 2

0 S1 5500 400 750 300 0 1 0 0 0 0 0 0 500 0 0 0 0 0 -500

-M V1 750 140 200 110 0 0 -1 0 0 0 0 0 (250) 0 1 0 0 0 -250

0 S3 400 400 750 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

-M V2 4 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0 0

-M V3 2 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0

-M V4 5 0 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0

0 S7 10 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

380 X4 5 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 1

0 S9 5 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 -1

Z=-761M+1900 Zj -141M -201M -111M 380 0 M 0 M M M 0 -250M-380 0 -M -M -M -M 250M+380

4
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M
Cj-Zj 141M+200 201M+450 111M+250 0 0 -M 0 -M -M -M 0 250M+380↑ 0 0 0 0 0 -251M-380

TABLEAU 3

0 S1 4000 120 350 80 0 1 2 0 0 0 0 0 0 0 -2 0 0 0 0

14 4 11 1
0 S8 3 0 0 -1250 0 0 0 0 0 1 0 0 0 0 -1
25 5 25 250

0 S3 400 400 (750) 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

-M V2 4 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0 0

-M V3 2 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0

-M V4 5 0 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0

0 S7 10 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

14 4 11 1 1
380 X4 8 1 0 − 0 0 0 0 0 0 0 0 0 0 0
25 5 25 250 250

1
0 S9 2 -1425 -45 -1125 0 0 1250 0 0 0 0 0 0 1 − 0 0 0 0
250

5
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M
-M -M+
�� ��
Z= - 11M+3040 Zj 1064 -M+304 836 380 0 − 0 M M M 0 0 0 -M -M -M 0
+ �� ��
5 5

M M
�� 38
Cj-Zj 64 M+146↑ 414 0 0 0 -M -M -M 0 0 0 -M− 25 0 0 0 -M
− + ��
5 5

TABLEAU 4

0 S1 11440/3 -200/3 0 80 0 1 2 -7/15 0 0 0 0 0 0 -2 0 0 0 0

0 S8 193/75 215 0 11/25 0 0 -1/250 -0,0011 0 0 0 0 1 0 1/250 0 0 0 -1

450 X2 8/15 815 1 0 0 0 0 1750 0 0 0 0 0 0 0 0 0 0 0

-M V2 4 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0 0

-M V3 22/15 -815 0 0 0 0 0 -1750 0 -1 0 0 0 0 0 0 1 0 0

-M V4 5 0 0 (1) 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0

0 S7 10 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

6
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M
380 X4 568/75 215 0 11/25 1 0 -1/250 -0,0011 0 0 0 0 0 0 1/250 0 0 0 0

0 S9 182/75 -215 0 -11/25 0 0 1/250 0,0011 0 0 0 0 0 1 -1/250 0 0 0 0

Z=-
Zj -7M/15+872/3 450 -M+836/5 380 0 -38/25 M/750+0,1947 M M M 0 0 0 38/25 -M -M -M 0
157M/15+46768/15

Cj-Zj 7M/15-272/3 0 M+414/5↑ 0 0 38/25 -M/750-0,1947 -M -M -M 0 0 0 -M-38/25 0 0 0 -M

TABLBEAU 5

0 S1 10240/3 -200/3 0 0 0 1 2 -7/15 0 0 80 0 0 0 -2 0 0 -80 0

0 S8 2875 215 0 0 0 0 -1250 -0,0011 0 0 11/25 0 1 0 1/250 0 0 -11/25 -1

450 X2 8/15 (8/15) 1 0 0 0 0 1/750 0 0 0 0 0 0 0 0 0 0 0

-M V2 4 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0 0

-M V3 22/15 -8/15 0 0 0 0 0 -1/750 0 -1 0 0 0 0 0 0 1 0 0

250 X3 5 0 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0

7
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M
0 S7 5 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0

380 X4 403/75 2/15 0 0 1 0 -1/250 -0,0011 0 0 11/25 0 0 0 1/250 0 0 -11/25 0

0 S9 347/75 -2/15 0 0 0 0 1/250 0,0011 0 0 -11/25 0 0 1 -1/250 0 0 11/25 0

Z=-
Zj -7M/15+872/3 450 250 380 0 -38/25 M/750+0,1947 M M -414/5 0 0 0 38/25 -M -M 414/5 0
82M/15+52978/15

Cj-Zj 7M/15-272/3↑ 0 0 0 0 38/25 -M/750-0,1947 -M -M 414/5 0 0 0 -M-38/25 0 0 -M-414/5 -M

TABLEAU 6

0 S1 3480 0 125 0 0 1 2 -3/10 0 0 80 0 0 0 -2 0 0 -80 0

0 S8 6/25 0 -14 0 0 0 -1250 -0,0014 0 0 (11/25) 0 1 0 1/250 0 0 -11/25 -1

200 X1 1 1 15/8 0 0 0 0 1/400 0 0 0 0 0 0 0 0 0 0 0

-M V2 3 0 -15/8 0 0 0 0 -1/400 -1 0 0 0 0 0 0 1 0 0 0

-M V3 2 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0

8
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M
250 X3 5 0 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0

0 S7 5 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0

380 X4 131/25 0 -14 0 1 0 -1/250 -0,0014 0 0 1/125 0 0 0 1/250 0 0 -1/125 0

0 S9 119/25 0 14 0 0 0 1/250 0,0014 0 0 -1/125 0 0 1 -1/250 0 0 1/125 0

Z=-
Zj 200 7M/8+280 250 380 0 -38/25 M/400-0,032 M M -41/45 0 0 0 38/25 -M -M 414/5 0
5M+17206/5

Cj-Zj 0 -7M/8+170 0 0 0 38/25 -M/400+0,032 -M -M 414/5↑ 0 0 0 -M-38/25 0 0 -M-414/5 -M

TABLEAU 7

3780/
0 S1 0 1875/11 0 0 1 30/11 -0,0455 0 0 0 0 -2000/11 0 -30/11 0 0 0 2000/11
11

0 S6 6/11 0 -25/44 0 0 0 -1110 -0,0032 0 0 1 0 25/11 0 1/110 0 0 -1 -25/11

200 X1 1 1 15/8 0 0 0 0 1/400 0 0 0 0 0 0 0 0 0 0 0

-M V2 3 0 -15/8 0 0 0 0 -1/400 -1 0 0 0 0 0 0 1 0 0 0

9
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M
-M V3 2 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0

250 X3 6111 0 -25/44 1 0 0 -1/110 -0,0032 0 0 0 0 25/11 0 1/110 0 0 0 -25/11

0 S7 49/11 0 25/44 0 0 0 (1/110) 0,0032 0 0 0 1 -25/11 0 -1/110 0 0 0 25/11

380 X4 5 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 1

0 S9 5 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 -1

M/400-
Z=-5M+38350/11 Zj 200 7M/8+5125/22 250 380 0 -25/11 M M 0 0 2070/11 0 25/11 -M -M 0 -2070/11
0,2955

-
Cj-Zj 0 -7M/8+4775/22 0 0 0 25/11↑ M/400+0,295 -M -M 0 0 -2070/11 0 -M-25/11 0 0 -M -M+2070/11
5

TABLEAU 8

0 S1 2100 0 0 0 0 1 0 -1 0 0 0 -300 (500) 0 0 0 0 0 -500

0 S6 5 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0

10
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M
200 X1 1 1 15/8 0 0 0 0 1/400 0 0 0 0 0 0 0 0 0 0 0

-M V2 3 0 -15/8 0 0 0 0 -1/400 -1 0 0 0 0 0 0 1 0 0 0

-M V3 2 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0

250 X3 10 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

0 S2 490 0 125/2 0 0 0 1 0,35 0 0 0 110 -250 0 -1 0 0 0 250

380 X4 5 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 1

0 S9 5 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 -1

Z=-5M+4600 Zj 200 7M/8+375 250 380 0 0 M/400+1/2 M M 0 250 -380 0 0 -M -M 0 380

Cj-Zj 0 -7M/8+75 0 0 0 0 -M/400-12 -M -M 0 -250 380↑ 0 -M 0 0 -M -M-380

TABLEAU 9

0 S8 21/5 0 0 0 0 1/500 0 -1/500 0 0 0 -35 1 0 0 0 0 0 -1

0 S6 5 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 -1 0

11
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M
200 X1 1 1 15/8 0 0 0 0 1/400 0 0 0 0 0 0 0 0 0 0 0

-M V2 3 0 -15/8 0 0 0 0 -1/400 -1 0 0 0 0 0 0 1 0 0 0

-M V3 2 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0

250 X3 10 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

0 S2 1540 0 125/2 0 0 12 1 -0,15 0 0 0 -40 0 0 -1 0 0 0 0

380 X4 46/5 0 0 0 1 1500 0 -1/500 0 0 0 -3/5 0 0 0 0 0 0 0

0 S9 45 0 0 0 0 -1/500 0 1/500 0 0 0 3/5 0 1 0 0 0 0 0

Z=-5M+6196 Zj 200 7M/8+375 250 380 1925 0 M/400-13/50 M M 0 22 0 0 0 -M -M 0 0

Cj-Zj 0 -7M/8+75 0 0 -19/25 0 -M/400+13/50 -M -M 0 -22 0 0 -M 0 0 -M -M

En conclusion, puisque toutes les différences sont �� − �� ≤ 0, une solution optimale est obtenue est censée être obtenue avec la valeur des variables :
48
�1 = 1, �2 = 0, �3 = 10, �4 = 5
�� Max � = 6196 Ces valeurs ne respectent pas du tout les conditions de départ telles que :

 �1 ≥ 4
 �2 ≥ 2. Par ailleurs, la variable artificielle V2 apparaît dans la base avec une valeur positive 3

En definitive, ce problème n’a pas de solution optimale (avec l’algorithme de simplexe).

12
WEMAKOYE ELANGA ELVIS
L1 ECONOMIE INDUSTRIELLE
U.O.M

13

Vous aimerez peut-être aussi