-
1
-
2
-
3
-
4
Pour rsoudre numriquement un programme
linaire, il faut quil ait une certaine forme que lon appelle "
forme standard ".
-
5
Il faut utiliser de nouvelles variables (variables
dcart ou variables artificielles) afin de transformer les
contraintes ingalits en
contraintes galits. Pour cela, nous devons
appliquer les rgles de transformation suivantes :
Donc pour obtenir le programme standard dun programme linaire,
on doit appliquer
lalgorithme suivant :
-
6
-
7
On dit quune contrainte est sature
pour une solution optimale, si son membre de
gauche gal son membre adroite.
En utilisant la forme standard du programme
linaire, le modle gnral pour chaque itration,
de la mthode des tableaux de simplexe est :
Cj
Toutes les variables
Ci VB Qi A = (aij)ij
Z zj
cj - zj
Aprs initialisation de toutes les variables, dans la colonne VB
on note les variables qui sont
dans la base (variables non nulles) ;
Dans la colonne Qi, on note les valeurs des variables qui sont
dans la base ;
Dans la ligne Cj, on note les coefficients des variables qui
figurent dans lexpression de la fonction conomique ;
-
8
zj est la somme des termes obtenus en multipliant les
coefficients de la colonne Ci par
les coefficients de xj ;
Dans la colonne Ci, on note les coefficients de la fonction
conomique des variables qui sont
dans la base.
: Un tableau du
simplexe est optimal lorsque tous les coefficients de
la ligne cj zj sont ngatifs ou nuls.
La
variable entrante est la variable associe
Max{cj-zj} pour les variables hors base. Toutefois,
si la valeur la plus leve nest pas unique, on slectionne alors
lune ou lautre des variables correspondantes.
1. On divise chacune des valeurs dans la colonne
quantit Qj par les lments correspondants
-
9
qui apparaissent dans la colonne de la variable
entrante. Nous ne divisons toutefois que par les
lments strictement positifs pour assurer que le
prochain programme soit ralisable.
2. Nous choisissons parmi les valeurs obtenues en 1, celle qui a
la plus petite valeur strictement
positive.
3. La variable en ligne avec cette plus petite valeur
strictement positive devient alors la variable
sortante
Une solution est unique, dans le cas
dune maximisation, si tous les coefficients de la ligne cj-zj
pour les variables hors base sont < 0.
Un tableau du
simplexe est optimal lorsque tous les coefficients de
la ligne cj zj sont ngatifs ou nuls.
La
variable entrante est la variable associe
Min{cjzj} pour les variables hors base. Toutefois,
-
10
si la valeur la plus petite nest pas unique, on slectionne alors
lune ou lautre des variables correspondantes
Le mme que
celui du problme de maximisation.
Une solution est unique, dans le cas
dune minimisation, si tous les coefficients de la ligne cj-zj
pour les variables hors base sont > 0.
Le tableau suivant rsume les tapes de la
mthode de simplexe :
1. Formuler le programme linaire ; 2. Vrifier que le second
membre du PL est
positif, sinon multiplier toutes contraintes
dont le second membre est ngatif par -1 ;
3. Ecrire le programme linaire sous la forme standard ;
4. Construire tableau initial du simplexe ; 5. Choisir la
variable entrante ; 6. Choisir la variable sortante et changer
la
variable sortante par la variable entrante sans
oublier de changer aussi ci associ ;
-
11
7. Identifier le pivot (intersection de la colonne de la
variable entrante et de la ligne de la
variable sortante). Ramener llment pivot 1 et tous les lments de
la colonne du pivot
0 par soustraction de lignes ;
8. Calculer Z en multipliant les coefficients de la colonne Ci
par les coefficients de Qi et den faire la somme ;
9. Calculer les zj en faisant la somme des termes obtenus en
multipliant les coefficients de la
colonne Ci par les coefficients de xj ;
10. Calculer les cj - zj ; 11. Faire le test doptimalit. Si le
test est valid, alors
la solution obtenue est optimale. Sinon retourner
ltape 5.
-
12
-
13
-
14
Le problme est impossible si une ou plusieurs
variables artificielles sont prsentes dans la base
du tableau de simplexe optimal, ce qui signifie
que la solution donne par ce tableau nest pas rellement
ralisable.
Un programme de maximisation ou
de minimisation avec seulement des contraintes
de type ne peut pas tre impossible (sous lhypothse que le second
membre est positif). Ceci est d au fait que lors de la rsolution de
ce
-
15
genre de programme par la mthode de simplexe
on n'utilise pas des variables artificielles.
Le problme est solutions multiples (la solution
nest pas unique) lorsquun des effets nets (cj-zj) relatif une
variable hors base est nul.
-
16
Le problme est solution infinie ou non borne
si la variable entrante nadmet aucune limite sur sa valeur
dentre, cest dire que tous les ratios Qi /aij sont ngatifs ou
nuls.
Un programme linaire est dit dgnr si une ou
plusieurs variables dans la base optimale sont
nulles.
-
17
La solution optimale de ce problme
est : x1 = 1, x2 = 0, x3 = 2 avec Z = 5
La forme standard du programme linaire est
Max (2x1 + 0 x2 + (3/2)x3 + 0S1 + 0S2 + 0S3)
S.C x1 - x2 + S1 = 2
2x1 + x3 + S2 = 4
x1 + x2 + x3 + S3 = 3
x1, x2, x3, S1, S2, S3 0
Le tableau de simplexe initial est :
2 0 3/2 0 0 0
x1 x2 x3 S1 S2 S3
0 S1 2 1 -1 0 1 0 0
0 S2 4 2 0 1 0 1 0
0 S3 3 1 1 1 0 0 1
Z = 0 0 0 0 0 0 0
2 0 3/2 0 0 0
-
18
La variable entrante est x1, mais les deux
premires contraintes donnent la mme valeur
minimale du ratio (2/1 ; 4/2 ; 3/1). Ceci indique
que lorsque x1 passe 2, les variables dcart S1 et S2 vont
sannuler malgr que lun des deux demeure encore dans la base.
Choisissons arbitrairement de faire sortir de la
base la variable dcart S1.
2 0 3/2 0 0 0
x1 x2 x3 S1 S2 S3
2 x1 2 1 -1 0 1 0 0
0 S2 0 0 2 1 -2 1 0
0 S3 1 0 2 1 -1 0 1
Z = 4 2 -2 0 2 0 0
0 2 3/2 -2 0 0 La nouvelle solution ralisable de base est :
x1 = 2, x2 = 0, x3 = 0, S1 = 0, S2 = 0, S3 = 1 et Z = 4.
Cette solution de base est dite dgnre.
Continuons les itrations relatives la mthode
de simplexe. La variable entrante est x2.
Le problme est quun des ratios est nul ce qui indique quon ne
peut pas augmenter la valeur de
-
19
x2 puisque la valeur de la fonction objectif ne va
pas augmenter et reste gale 4.
Si on ritre une autre fois, on obtient :
2 0 3/2 0 0 0
x1 x2 x3 S1 S2 S3
2 x1 5/2 1 0 1/2 1/2 0 3/2
0 S2 -1 0 0 0 -1 1 -1
0 x2 1/2 0 1 1/2 -1/2 0 1/2
Z = 5/2 2 0 1 1 0 3
0 0 1/2 0 0 -3
Ce tableau nest pas optimal, la variable entrante est x3 et la
variable sortante est x2. On remarque
aussi que ce passage dune solution une autre ne saccompagne pas
dune augmentation de la valeur de la fonction conomique.
On peut facilement vrifier que nous sommes en
train de cycler sans atteindre la solution
optimale. Ce genre de cyclage dans la mthode de
simplexe est dangereux et on doit lidentifier avant de commencer
rsoudre le problme,
sinon on passera un temps norme sans atteindre
la solution optimale.
-
20
-
21
-
22
-
23
Dans la plupart des problmes que nous traitons,
les variables considres x1, x2, , xn sont supposs valeurs
relles. Or, dans certaines
applications, on peut se trouver dans les trois
situations suivantes :
Les variables (x1, x2, ..., xn) ne peuvent prendre que des
valeurs entires (par exemple lorsque
ces variables reprsentent un nombre dunit non fractionnables
telles que nombre de
machines, units produites, nombre de
personnes). Les programmes correspondants
sont dits PROGRAMME LINAIRE EN
NOMBRES ENTIERS (PLNE).
Certaines des variables x1, x2, , xn ne peuvent prendre que des
valeurs entires, les autres
tant valeurs relles. Les programmes
correspondants sont dits PROGRAMME
LINAIRE EN NOMBRES MIXTES.
-
24
Un cas particulier de la premire situation est celle o toutes
les variables entires doivent
prendre les valeurs 0 ou 1. Les programmes
correspondants sont dits PROGRAMME
LINAIRE A VARIABLES BINAIRES.
Pour ces divers cas, on pourrait penser quil s'agit simplement
de rsoudre ces problmes par
la mthode de simplexe dans laquelle les variables
sont supposes valeurs relles et arrondir les
rsultats obtenus aux valeurs entires les plus
proches.
Avec un tel raisonnement, il nest pas possible daffirmer que la
solution arrondie soit une solution ralisable du programme linaire
ou
encore quil nexiste pas une meilleure solution entire.
-
25
La rsolution des modles suivants permet
dillustrer les consquences darrondir les solutions valeurs
relles pour obtenir des
solutions entires :
Modle 1 Modle 2 Max (60x1 + 54x2)
S. C. 21x1+15x2 147
12x1+24x2 120
x1 0 ; x2 0
Min (45x1 + 90x2)
S. C. 18x1+45x2 155
8x1+ 6x2 22
x1 0 ; x2 0
Modle 3 Max (16x1 + 20x2)
S. C. 21x1+10x2 64
8x1+40x2 92
x1 0 ; x2 0
-
26
Modle Solution optimale par
la mthode simplexe
Solution entire
arrondie
Solution
optimale
1
x1 = 5,333
x2 = 2,333
Z = 466
x1 = 5
x2 = 2
Z = 408
x1 = 7
x2 = 0
Z = 420
2
x1 = 0,238
x2 = 3,349
Z = 312,4
x1 = 0
x2 = 3
Non ralisable
x1 = 0
x2 = 4
Z = 360
3
x1 = 2,518
x2 = 1,868
Z = 71,895
x1 = 2
x2 = 2
non ralisable
x1 = 1
x2 = 2
Z = 56
Nous avons arrondi les valeurs de x1 et x2 au plus proche entier
; on obtient toutefois dans le
cas des modles 2 et 3, des solutions non
ralisables.
Pour obtenir une solution ralisable entire, il faut arrondir les
valeurs des variables
lentier suprieur dans le cas Min et lentier infrieur dans le cas
Max, ce qui donnera des
solutions ralisables mais non optimales.
Les solutions optimales entires ont t obtenues laide de la
mthode graphique.
-
27
Maximiser (ou Minimiser) :
Z = c1x1 + c2x2 + + cnxn
avec les contraints :
a11x1 + a12x2 + + a1nxn (, =, ) b1 a21x1 + a22x2 + + a2nxn (, =,
) b2 . . . .
. .
am1x1 + am2x2 + + amnxn (, =, ) bm xj 0, j = 1, , n ; xj entier,
j = 1, , k (k n)
Considrons dabord le programme linaire suivant (sans contrainte
de valeurs entires) :
{
-
28
La solution optimale de ce programme se situe au
point extrme suivant :
x1 = 316
et x2 = 37
avec Z = 3290
La figure 1 suivante illustre la rgion des
solutions ralisables avec la solution optimale :
Figure 1
Supposons maintenant que les variables doivent
prendre des valeurs entires. Le programme
linaire devient alors :
-
29
{
Lensemble des solutions possibles pour ce programme linaire en
nombres entiers comporte
uniquement les points dont les composantes sont
valeurs entires. Il existe 24 solutions entires
ralisables (voir la figure 2 ci-dessus). La plus
grande valeur de la fonction conomique en ces
points est 90 et elle est ralise au point (4, 3)
(voir tableau ci-dessus).
Figure 2
-
30
Lexigence supplmentaire concernant les valeurs entires des xj
fait dcrotre la valeur
maximale de la fonction conomique de 290/3 =
(90+2/3) 90.
Les valeurs arrondies de la solution optimale du PL aux plus
proches valeurs entires donnent x1
= 5, x2 = 2 et Z = 88. Cette solution entire est
ralisable mais nest pas optimale puisque la valeur maximale de
la fonction conomique est
90 x1 = 4 et x2 = 3.
-
31
Dans le cas dune maximisation, la valeur de la fonction
conomique dun programme linaire est toujours une borne suprieure
celle dun PLNE ou variables mixtes (PLVM). Lajout des contraintes
de variables entires diminue ou
naffecte pas la valeur de la fonction conomique dun programme
linaire.
Dans le cas dune minimisation, la valeur de la fonction
conomique dun programme linaire est toujours une borne infrieure
celle dun PLNE ou variables mixtes (PLVM). Lajout des contraintes
de variables entires augmente
ou naffecte pas la valeur de la fonction conomique dun programme
linaire.
-
32
1. Ecrire le modle de programmation linaire en additionnant et
/ou en soustrayant les variables
dcart requises ;
2. Multiplier par -1, les contraintes dont on a soustrait une
variable dcart ;
3. Obtenir une solution de dpart
avec cj zj 0, j = 1, 2, ., n dans le cas dune maximisation
-
33
avec cj zj 0, j = 1, 2, ., n dans le cas dune minimisation ;
4. La variable
sortante est la variable correspondant
Min{variables de base xi, xi < 0} ;
5. Soit k = la
ligne pivot c'est--dire, la ligne o se trouve la
variable sortante. La variable entrante est la
variable xr correspondant
{
}
, dans le cas
de minimisation ;
{
}
, dans le cas
de maximisation ;
Le dual na pas de solution optimale finie si, pour la ligne
pivot k, la variable dans la base est
ngative et akj 0 ;
6. Pivoter sur akr en utilisant les mmes rgles que lalgorithme
du simplexe ;
-
34
7. On obtient une solution
de base ralisable optimale si toutes les
variables de base sont positives et
tous les cj zj 0 dans le cas de minimisation
tous les cj zj 0 dans le cas de maximisation
8. si la solution de base ralisable nest pas optimale, on
poursuit lalgorithme (allez 4).
Soit un programme linaire en nombres
entiers dfini par :
-
35
Max ou Min : Z = CT X
(3.1) S. C. A X = b
X n
C et X sont des vecteurs (colonnes) de , b un vecteur (colonne)
de m, A une matrice m lignes et n colonnes. La notation X n
signifie que le vecteur X a toutes ses composantes entires.
Considrons le tableau du simplexe loptimum du programme linaire
continu correspondant
obtenu en imposant seulement aux variables
dtre positives.
Soit xi une variable de base non entire ; la ligne
du tableau correspondant cette variable scrit :
o JN est lensemble des indices des variables hors base, cij le
coefficient du tableau situ
lintersection de la ligne correspondant la variable de base xi
et de la colonne correspondant
la variable hors base xj et la valeur numrique de xi.
-
36
On a pour toute solution admissible du PLNE
(3.1), la proprit de Troncature associe la
variable xi :
o [a] dsigne le plus grand entier infrieur ou
gal a.
On peut vrifier aussi que la solution optimale
considre ne satisfait pas cette contrainte si nest pas
entier.
La mthode des troncatures fournit une mthode
de rsolution des programmes linaires en
nombres entiers (PLNE). Elle est rsume comme
suit :
1. tant un PLNE, rsoudre le PL laide dun algorithme de simplexe.
si la solution du PL
contient uniquement des valeurs entires, elle
est galement une solution optimale au PLNE
et la rsolution est termine.
-
37
2. Si une ou plusieurs variables de base dans la solution
optimale du PL ne sont pas entires,
on doit alors gnrer, partir dune des lignes du tableau (celle
dont la partie fractionnaire
pour la variable de base correspondante est la
plus leve) une contrainte supplmentaire dite
coupe de Gomory (indique par lquation (3.2)). Cette contrainte
est ajoute au tableau
optimal du PL et on dtermine le nouveau
tableau optimal laide de la mthode duale du simplexe (voir
paragraphe 3.3).
3. Si les variables de base dans le nouveau tableau optimal sont
entires, nous avons
obtenu galement la solution optimale au
PLNE. La rsolution est termine.
4. Sinon, on doit gnrer ( partir du dernier tableau optimal) une
nouvelle coupe de
Gomory, lajouter au dernier tableau et trouver la solution
optimale laide de la mthode duale de simplexe. Si la solution
obtenue est valeur entire, la rsolution est
termine. Sinon, on rpte la procdure
jusqu lobtention dune solution optimale entire.
-
38
Rsoudre le PLNE suivant :
Max (100x1+120x2)
S. C. 3x1 + 4x2 4100
x1 + 3x2 2400
2x1 + 2x2 2625
x1 et x2 des entiers
Rsoudre le PLNE suivant en
utilisant lAlgorithme de GOMORY :
Min (2x1 + 3x2 + 4x3)
S. C. x1 + 2x2 + 2x3 6
x1 + 4x2 + 2x3 10
3x1 + x3 2625
xi 0 pour i = 1, 2, 3
Une socit dispose de 1 400 000 Dh
investir. Les experts proposent 4 investissements
possibles
800 000
1 200 000
2 200 000
1 600 000
Bnfice
2.67 300 000 Inv. 4
3.00 400 000 Inv. 3
3.14 700 000 Inv. 2
3.20 500 000 Inv. 1
Rendement Cot
-
39
Question : donner une solution au problme qui
maximise le bnfice.
Variables de dcision : xi, i=1,,4
xi = 1 si investissement i est choisi
xi = 0 sinon
Objectif : maximiser bnfice
Max(16105 x1 + 2210
5 x2 + 1210
5 x3 + 810
5 x4)
Contrainte : budget dinvestissement
5 x1 + 7 x2 + 4 x3 + 3 x4 14
Max (16 x1 + 22 x2 + 12 x3 + 8 x4)105
S. C. 5 x1 + 7 x2 + 4 x3 + 3 x4 14
x1, x2, x3, x4 0
Solution : x1 = 2.8, x2 = 0, x3 = 0, x4 = 0.
-
40
Interprtation :
Effectuer linvestissement 1.
Bnfice : 1 600 000 DH.
Cot : 500 000 DH
Max (16 x1 + 22 x2 + 12 x3 + 8 x4)
S. C. 5 x1 + 7 x2 + 4 x3 + 3 x4 14
x1, x2, x3, x4 1
x1, x2, x3, x4 0
Solution : x1 = 1, x2 = 1, x3 = 0,5, x4 = 0.
Interprtation :
Effectuer les investissements 1 et 2.
Bnfice : 3 800 000 DH.
Cot : 1 200 000 DH
Plus assez de budget pour linvestissement 3.
-
41
Max (16 x1 + 22 x2 + 12 x3 + 8 x4)
S. C. 5 x1 + 7 x2 + 4 x3 + 3 x4 14
x1, x2, x3, x4 {0, 1}
Solution : x1 = 0, x2 = 1, x3 = 1, x4 = 1.
Interprtation :
Effectuer les investissements 2, 3 et 4.
Bnfice : 4 200 000 DH.
Cot : 1 400 000 DH
Les contraintes dintgralit peuvent modifier significativement la
structure de la solution.
Lintuition acquise avec les variables continues nest pas
directement utilisable.
Dans lexemple, linvestissement 1 est le plus rentable, mais il
nest pas repris dans la solution optimale
Ahmed le campeur part en
randonne dans la montagne. Il ne peut emporter
-
42
dans son sac dos quun poids limit P. Chaque article i quil peut
potentiellement emporter pse pi et lui procure une utilit ui pour
sa randonne.
Question : quels articles emporter pour
maximiser son utilit sans dpasser la limite de
poids ?
Corrig :
Variables de dcision
xi = 1 si Ahmed emporte larticle i
xi = 0 sinon
Programme linaire
Max (u1x1 + u2x2 + + unxn)
S. C. p1x1 + p2x2 + + pnxn P
x1, , xn {0,1}
Le nombre de manires de choisir un sous-ensemble de n lments est
2
n.
Il est impossible de considrer toutes les possibilits.
Un algorithme efficace devrait obtenir la solution
optimale en examinant un trs petit nombre de
solutions
-
43
Jusquici nous avons formul nos problmes comme des problmes de
programmation linaire
et nous nous sommes concentrs sur les solutions
optimales. Malheureusement, dans certain cas,
les donnes dont nous disposons ne sont pas
fiables 100% mais sont des donnes estimes.
Dans dautres cas, on peut se demander quel prix nous serions
prts payer pour augmenter nos
ressources. Il est donc ncessaire de comprendre
comment varient les solutions optimales en
fonction dune petite modification de certaines donnes.
Que se passe-t-il si les ressources changent ?
Que se passe-t-il si les cots changent ?
Quand les donnes sont incertaines, quelle
marge derreur avons-nous ?
Do lanalyse de sensibilit qui est un processus par lequel on
value la robustesse dun modle
-
44
conomique en examinant comment les rsultats
de lanalyse varient lorsque la valeur des variables cls est
modifie dans un intervalle
dtermin.
Les lments cls dun programme linaire standard sont :
La fonction conomique. Qui peut reprsenter un cot, un profit,
etc...
Les contraintes sont composes, des coefficients aij de la
matrice A, dite matrice
technologique, et des constantes bi, qui
forment le vecteur du second membre. Le
second membre peut reprsenter la
disponibilit des ressources, les niveaux de
demande, etc...
Les variables dcart peuvent reprsenter lexcdent de chacune des
ressources : terrain, eau, heures de travail, bureau dirrigation, .
Elles sont aussi dites variables de surplus.
-
45
Quand une variable dcart est nulle, on dit que la contrainte
correspondante est sature. Elle est
dite aussi restrictive car une variation du second
membre (par exemple) engendre un changement
dans les valeurs de la solution optimale.
Toute contrainte non sature loptimum nest pas restrictive pour
le problme, cest dire quelle na aucune influence sur la solution
considre pour des petites perturbations.
Un agriculteur veut allouer 150
hectares de surface irrigable entre culture de
tomates et celles de piments. Il dispose de 440 m3
deau et de 480 heures de main duvre. Un hectare de tomates
demande 4 m
3 deau, 1 heure
de main duvre et donne un bnfice net de 1000 DH. Un hectare de
piments demande 2 m
3
deau et 4 heures de main duvre et donne un bnfice net de 2000
DH. Le bureau du primtre
irrigu veut protger le prix des tomates et ne lui
permet pas de cultiver plus de 90 hectares de
tomates.
1. Modliser le problme sous forme dun programme linaire ;
-
46
2. Le tableau de simplexe optimal est
1000 2000 0 0 0 0
x1 x2 S1 S2 S3 S4
1000 x1 40 1 0 4/3 0 -1/3 0
0 S2 60 0 0 14/3 1 2/3 0
2000 x2 110 0 1 -1/3 0 1/3 0
0 S4 50 0 0 -4/3 0 1/3 1
Z = 260 000 1000 2000 2000/3 0 1000/3 0
0 0 -2000/3 0 -1000/3 0
O :
x1 est le nombre dhectares cultivs de tomates et x2 est le
nombre dhectares cultivs de piment ;
S1, S2, S3 et S4 sont les variables dcart associes
respectivement aux contraintes terre,
eau, main duvre et bureau.
a. Dterminer la solution optimale, les contraintes satures et
les contraintes non
satures ;
b. Ecrire la fonction conomique en fonction des variables hors
base.
-
47
Le Plan Comptable Gnral (PCG) dfinit le cot
marginal comme tant la diffrence entre
lensemble des charges courantes ncessaires une production donne
et lensemble de celles qui sont ncessaires cette mme production
majore ou minore dune unit . Cette unit peut tre soit :
un article fabriqu,
un lot de produits,
une srie dlments,
une prestation de service,
Une entreprise produit en sries des
articles lectromnagers.
-
48
Les cots marginaux sont les effets
nets associs aux variables dcart (cj-zj), puisque ce sont ces
variables qui dterminent les
excdents (ou les insuffisances) de biens.
Si une variable dcart nest pas nulle, dans la solution optimale,
cest que le bien correspondant est dj excdentaire. Par consquent,
le fait de
disposer dune unit supplmentaire de ce bien naura aucune
influence sur le revenu. On dit alors que ce bien une valeur
marginale nulle, ou
par extension, que la variable dcart associe ce bien a une
valeur marginale nulle.
Par contre, si une variable dcart est nulle dans la solution
optimale, cest que le bien correspondant est totalement utilis. Par
la suite
une variation de la disponibilit aura
gnralement une influence sur le revenu. Cest pourquoi cette
variable dcart nulle dans la solution optimale une valeur marginale
non
nulle, et cette valeur marginale prcise la
variation de la fonction conomique rsultant de
lutilisation dune unit supplmentaire du bien associ.
-
49
Une solution de base optimale est dite stable si
lensemble des variables de base loptimum ne change pas lorsque
les paramtres du programme
sont modifis.
On cherche dterminer un intervalle dans
lequel peut varier cj sans que la base de la
solution optimale change.
Lintervalle sur lequel ck dune variable hors base dans la
solution optimale peut varier sans que la
base optimale soit modifie est :
- < ck zk cas de maximisation
zk ck < + cas de minimisation
-
50
Soit le programme linaire suivant :
Max (12 x1 + 20 x2)
S.C. 6 x1 + 10 x2 60
8 x1 + 25 x2 200
2 x1 + 8 x2 80
x1 0 , x2 0
Lalgorithme du simplexe nous conduit au tableau optimal suivant
(les variables x3, x4 et x5
sont des variables dcart).
12 20 0 0 0
x1 x2 x3 x4 x5
12 x1 40 1 4 0 0 1/2
0 x3 180 0 14 1 0 3
0 x4 120 0 7 0 1 4
Z = 480 12 48 0 0 6
0 -28 0 0 -6
Dterminer la plage de variation pour c2 pour
que la solution demeure optimale.
-
51
Soit le programme linaire suivant :
Min (8 x1 + 10 x2 + 20 x3)
S.C. 5 x1 + 10 x2 + 20 x3 = 16 000
x1 400
x2 600
x3 600
x1 + x2 + x3 1000
x1 0 , x2 0 , x3 0
Le tableau optimal (sans variable artificielle) est
le suivant :
8 10 20 0 0 0 0
x1 x2 x3 x4 x5 x6 x7
10 x2 400 3/2 1 0 0 0 0 2
0 x4 400 1 0 0 1 0 0 0
0 x5 200 -3/2 0 0 0 1 0 -2
0 x6 0 1/2 0 0 0 0 1 1
20 x3 600 -1/2 0 1 0 0 0 -1
Z = 16 000 5 10 20 0 0 0 0
3 0 0 0 0 0 0
Dterminer les bornes de variation pour c1 qui
permettent de maintenir toujours une base
optimale.
-
52
Soient j lindice dune variable hors base et l le numro de la
ligne o se trouve la variable hors
base xk dans la solution optimale, lintervalle sur lequel ck
peut varier sans que la base optimale
soit modifie est :
cas de maximisation
{
}
{
}
cas de minimisation
{
}
{
}
Dans lexercice 1, dterminer les
bornes de variation pour c1 qui permettent de
maintenir toujours une base optimale.
Dans lexercice 3, dterminer les
limites de validit de loptimum pour le coefficient de la
variable x2 et celui de la variable
x3.
-
53
Dterminer lintervalle pour lequel, la
solution optimale reste stable, pour une variation
du second membre de la kme
contrainte bk.
Soit Q = (Qi) la colonne quantit (colonne des valeurs prises par
les variables dans la base).
Lintervalle sur lequel bk peut varier sans que la base optimale
soit modifie est :
{
}
{
}
On peut obtenir laide des valeurs du tableau
sous la colonne quantit et des lments sous la variable dcart
xn+k, les nouvelles quantits (nouvelles valeurs de la solution)
rsultant
dune modification bk de la contrainte k par :
[
] [
] [
]
-
54
Dans Exercice 1
1. dterminer les bornes de variation pour b1 qui permettent de
maintenir toujours une base
optimale ;
2. Dterminer dans ce cas, les nouvelles valeurs
de la solution pour b1 = 3 ; 3. Dterminer lintervalle dans
lequel peut varier
b1 et b3 (les ressources en surface et en main
duvre) sans que la base optimale change.
Supposons que le nombre dunits de la ime ressources (i
me contraintes) ncessaire pour
produire une unit de produit j, soit (aij + ) ou lieu de aij.
Ainsi, on se pose la question si la
solution optimale demeure stable suite un tel
changement.
Il est impossible de modifier le coefficient aij sans
que la base dans la solution optimale ne change
pas (la solution optimale n'est pas stable).
-
55
Il est possible de modifier le coefficient aij dune
valeur ij et la solution optimale demeure stable
condition que :
On remarque quon ne va pas produire le produit j
Si ij 0, alors il est encore moins conomique de fabriquer ce
produit si le coefficient
technologique aij augmenterait de ij
Si ij 0, alors la fabrication du produit j peut devenir
conomique si on utilise moins de
ressources.
-
56
Soit le programme linaire
Max 66 x1 + 84 x2
S.c 3 x1 + 4 x2 4200 x1 + 3 x2 2250
2 x1 + 2 x2 2600 x1 1100
x1 0 , x2 0
Lalgorithme du simplexe nous conduit au tableau optimal suivant
(les variables x3, x4 x5 et
x6 sont des variables dcart).
66 84 0 0 0 0
x1 x2 x3 x4 x5 x6
66 x1 1000 1 0 -1 0 2 0
84 x2 300 0 1 1 0 -3/2 0
0 x3 180 0 0 -2 1 5/2 0
0 x4 120 0 0 1 0 -2 1
Z = 91200 66 84 18 0 6 0
0 0 -18 0 -6 0
-
57
1. Quelles sont les limites de variation pour b1. 2. Prciser le
variable qui devient nulle (puis
ngative si on excde la limite permise) pour
chaque limite de b1.
3. Que deviennent les valeurs de x1, x2, x4, x6 et Z si b1 =
4375.
4. Quelles sont les limites de variation pour b2 ?
Soit le programme linaire avec le
tableau optimal donn par la mthode de
Simplexe :
Max (10 x1 + 6 x2 + 8 x3)
S.c 6 x1 + 3 x2 + 6 x3 120
4 x1 + 4 x2 + 6 x3 100
4 x1 + 12 x2 + 8 x3 200
x1 0 , x2 0 , x3 0
10 6 8 0 0 0
x1 x2 x3 x4 x5 x6
10 x1 15 1 0 1/2 1/3 -1/4 0
6 x2 10 0 1 1 -1/3 1/2 0
0 x6 20 0 0 -6 8/3 -5 1
Z = 210 10 6 11 4/3 1/2 0
0 0 -3 -4/3 -1/2 0
-
58
O x4, x5 et x6 sont les variables dcart. 1. Quelles sont les
variables hors base ; 2. Donner lexpression de la fonction
conomique en fonction des variables hors
base ;
3. Quelles sont les contraintes satures ? Justifier votre rponse
;
4. Que devient la 1ire contrainte dans ce cas ; 5. Dterminer les
bornes de variation pour c2
qui permettent de maintenir la solution
optimale stable. Justifier votre rponse ;
6. Dterminer les bornes de variation pour b1 qui permettent de
maintenir la solution
optimale stable. Justifier votre rponse ;
