r.o .pdf



Nom original: r.o.pdf
Titre: III
Auteur: TANOH JACQUES

Ce document au format PDF 1.4 a été généré par PDFCreator Version 1.2.3 / GPL Ghostscript 9.04, et a été envoyé sur fichier-pdf.fr le 18/01/2019 à 22:23, depuis l'adresse IP 160.178.x.x. La présente page de téléchargement du fichier a été vue 136 fois.
Taille du document: 141 Ko (5 pages).
Confidentialité: fichier public


Aperçu du document


III- Résolution d’un programme linéaire par la méthode
des variables artificielles
Introduction

Dans une contrainte du type" ", une variable d’écart positive apparaît précédée d’un signe
« - ». La présence de ces signes « -» ne nous permet plus de prendre les variables d’écart
comme variables de base dans le premier tableau.
Pour résoudre le problème, on introduit de nouvelles variables appelées variables
artificielles.
Une variable artificielle est une variable fictive introduite spécialement pour engendrer
une solution de base accessible. Elle n’a pas de signification économique.

1) Principe de la méthode des variables
L’introduction de variables artificielles permet de résoudre le problème posé par les
contraintes posé par les contraintes " ".
Quand un programme linéaire comporte une contrainte , la contrainte de positivité liée à
la variable d’écart n’est pas respectée pour la forme standard.
Soit la contrainte :
2
16
- Prenons une solution qui respecte la contrainte. Par exemple, 5,5,5 donne 5+10+5=20.
qui permet l’égalité est telle que :
Dans la forme standard, la variable d’écart

20
16, soit
4 (ce qui ne respecte pas la condition
0 ) . La forme standard
de la contrainte est donc :
2
16.
- La variable est alors mise hors base, et l’introduction dans la base d’une variable
artificielle , positive ou nulle, affectée du coefficient 1 permet d’obtenir une solution de
départ admissible :
2
16.
Les variables hors base sont :
0, et en base
16 (ce qui respecte
0).

VARIABLES ARTIFICIELLES
a) Introduire une variable artificielle par contrainte .
La variable d’écart de la contrainte, affectée du coefficient -1, est mise hors base.
b) Elles permettent simplement l’égalité dans la forme standard et ne sont pas une
donnée du problème. En conséquence, elles doivent être nulles à l’optimum.
Pour cela, il faut les faire sortir de la base en leur donnant un coefficient fortement
pénalisant dans la fonction économique :
• S’il s’agit d’une maximisation, le coefficient affecté à la variable est très
négatif : -M.
• S’il s’agit d’une minimisation, le coefficient affecté à la variable est très
positif : +M.
M étant suffisamment grand pour qu’on soit sûr que
est exclue de la solution
optimale.

2) Résolution d’une maximisation
Soit le programme linéaire : 1
2
100

0;
3
1

0;

0
10000
5000
500
200

La forme standard de ce programme est :

#
!

" 1
3
!
2
1

0;
0;
0;

$
$

100
500
200
D’après la deuxième contrainte :
5000 2
D’où
100
500
200
0
0 $
5000 2
100
500
200
0
0 $ 2%

0;
0;
0;

$

0

0

0

0
10 000
5000
0

$

$

$

5000

Premier tableau :


Hors Base
En Base

F

R

$



B

1

3

1

1

0

0

10 000

2

1

1

0

-1

1

5 000

100
+2M

500
+1M

200
+1M

0

0
-1M

0

0
+5 000M

2M est le plus fort coefficient.

10000/1=10000
5000/2=2500
changer le signe puisque F
est lue au signe près

Deuxième tableau :
Hors Base
En Base

·

·

0

2,5

$

R

B

1

1

0,5

-0,5

7500

7500/2,5=3000
2500/0,5=5000

F

1

0,5

0,5

0

-0,5

0,5

2500

150
+0M

0

0

450
+0M

50
+0M

-50
-M

-250000
+0M

450 est le plus fort coefficient positif



La sortie de la base d’une variable artificielle étant définitive, sa colonne peut être
supprimée.

Hors Base
En Base

F

·

·

$

0

1

0,4

0,4

0,2

3 000

1

0

0,3

- 0,2

-0,6

1 000

0

0

-30

-180

-40

-1 600 000

La solution optimale est atteinte :



B

1000 ;

3000 ;

0 '

1 600 000.

Une variable artificielle n’apparaît jamais dans la base du tableau final si on a atteint
une solution optimale accessible.

3) Résolution directe d’une minimisation
Les principes de résolution sont les mêmes à l’exception du choix de la variable qui entre dans
la base :
la variable entrante est celle dont les taux marginaux de substitution est le plus négatif.
L’optimum est atteint quand tous les taux marginaux de substitution sont positifs ou nuls.
a) Comment passer d’un tableau à un autre
Toutes règles et les principes de calcul vus au chapitre1 restent valables, sauf la règle du
choix de la variable entrante (règle 1) qui devient :
Règle 4 : Dans un problème de minimisation, la variable entrante est la variable hors base
qui a le coefficient « le plus négatif » dans la fonction économique.
b) Tableau optimal et solution optimale
Règle 5 : Dans un problème de minimisation, on obtient un tableau optimal dès que tous
les coefficients de la fonction économique sont positifs ou nuls.
c) Application

1
Soit le programme linéaire suivant: )
2,5

0;

2
1

*+ 195

0;

1
1,5

160

0

16
10

0;
2
Forme standard pour une minimisation directe : 1
2,5
1
*+ 195
160
120

120

$

0;
1
1,5
0
0

D’après la première contrainte:
16 1
2
1
D’après la deuxième contrainte: $ 10 2,5
1
1,5
D’où
195
160
120
0
0 $
195

160

120

10

0

2,5
0

$

1

3,5

1,5

3

$

2,5

$

16

0;

$

$

$

1

2

$

0
16
10

$

1
$

26

Premier tableau :
$

Hors Base

·

·

1
0
0

0
1
0

B

En Base

F

$

1
2,5
195
-3,5M

2
1
160
-3M

1
1,5
120
-2,5M

-1
0
0
+M

0
-1
0
+M

16
10
0
-26M

Deuxième tableau :
·

$

Hors Base

·

B

En Base

F

0
1
0

1,6
0,4
82
-1,6M

0,4
0,6
3
-0,4M

-1
0
0
1M

0,4
-0,4
78
-0,4

1
0
0

-0,4
0,4
-78
1,4M

12
4
-780
-12M

Troisième tableau :
.

Hors Base

.

$

$

B

En Base

F

0
1
0

1
0
0

0,25
0,5
-17,5

-0,625 0,25 0,625
0,25
-0,5 -0,25
51,25 57,5 -51,25
1M

7,5
1
-1395

Quatrième tableau :
Hors Base

.

.

$

$

B

En Base
-0,5
1
0
-0,75 0,5
7
2
0
1
0,5
-1
2
35
0
0
60
40
-1360
F
L’optimum de la minimisation est atteint puisque tous les taux marginaux de substitution
sont positifs ou nuls.
La variable est hors base et en conséquence,
0.
La solution optimale est donc
0;
7;
2 pour un coût minimum égal à 1 360
francs. Il est préférable de passer par le programme dual qui réduit les calculs.




Télécharger le fichier (PDF)

r.o.pdf (PDF, 141 Ko)

Télécharger
Formats alternatifs: ZIP







Documents similaires


ro
r vision
184787880 programmation lineaire ppt
cours programmation lineaire 7 1
cours programmation lineaire 4 1
chapitre4sil

Sur le même sujet..