B105 Ch3

CHAPITRE III: MODIFICATIONS DES DONNES DUN PROBLME CONOMIQUE
Dans ce court chaptre nous nous intresserons aux faons de traiter avec efficience les
changements qui pourraient se prsenter dans un programme linaire. En effet le changement du prix de
vente dun produit ou du prix dachat dune matire peuvent ou non changer loptimum.
Cependant dans certains cas nous pouvons incorporer ces changements dans notre problme original sans
avoir raliser nouvellement tout le travail initial.
3.1- Changements dans la fonction objectif:

Nous essayerons de comprendre ici quelles modifications un changement dans la fonction objectif
peut apporter. Prenons un exemple:
Soit le programme linaire suivant:
Max 2 x1 + 3 x2
2x + x 4
P
( ) s 1 2
c x1 + 2 x2 4
x1 , x2 0
( 1)
( 2)
Rsoudre graphiquement le problme et expliciter le tableau simplexe associ loptimum x*.
La fonction objectif devient 3 x1 + 2 x2 . Modifier le graphique antrieur et commenter les

ventuels changements observs. Expliciter le tableau simplexe associ au point x* antrieur.
Est-il toujours optimum? Si non expliciter le tableau simplexe associ loptimum.
La fonction objectif devient 3 x1 + 1x2 . Expliciter le tableau simplexe associ au point x*

antrieur. Est-il toujours optimum? Si non expliciter le tableau simplexe associ loptimum.
Modifier le graphique antrieur et commenter les ventuels changements observs.
Commenons par rsoudre graphiquement le problme: nous applerons J ( x1 , x2 ) la fonction

objectif J ( x1 , x2 ) = 2 x1 + 3 x2 .
Auteur: Philippe Gollotte

Page 72 de 159
Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation
(2)
gradient de J
solutions de base
aire des solutions ralisables
500
(1)
5
courbe de niveau de J
x* solution optimale (premier cas)

J
LGENDE:
contraintes
x1
2 4
( 3 ) + 3( 4 3 ) = 20 3
(
La fonction est alors maximum, elle vaut:
2 x1* + 4 = 1 x1* + 2 x1* = 4

2
3
*
*
*
x2 = 2 x1 + 4 x2 = 4
3
Do:
x1* + 2 x2* = 4 ( 2 ) x2* = 1 x1* + 2 ( 2 )

2
2 x1* + x2* = 4 (1) x2* = 2 x1* + 4 (1)
Loptimum x * se situe lintersection des contraintes (1)

et (2). Ses coordonnes vrifient donc les quations des
deux droites:
Matrice de base:
2 1
B=
1 2
Base: = { x1 , x2 } .
Nous avons dtermin graphiquement que le point optimum a pour coordonnes x* = 4 , 4 , 0, 0 do:
x*

J
x2
1.- Graphiquement.
PROPOSITION DE RESOLUTION
Page 73 de 159
e 2 point ralisable
-1/3 -4/3 J = 20/3
-1/3 2/3 4/3
2/3 -1/3 4/3
e1
CALCULS:
( 3 ) + 3( 4 3 ) = 20 3
2 4
Fonction objectif:
1 3 2
Ce2 = 0
; = 4 3
2 3 3
2 3 2
Ce1 = 0
; = 1 3
1 3 3
Cots dopportunit:
Reprsentons sur le graphique son gradient et la courbe de niveau passant par loptimum afin de constater
les changements ventuels.
2.- Nous appellerons K ( x1 , x2 ) la nouvelle fonction objectif K ( x1 , x2 ) = 3 x1 + 2 x2 .
fonction vaut 20 .
point est ralisable. Les cots dopportunit des variables hors base sont positifs. Le point est optimum. La
Evaluation de loptimalit: au point x* = 4 , 4 , 0, 0 : les lments du second membre sont positifs. Le
x2
x2
x1
x1
-1
B b 0,
Tableau simplexe associ:
4
b=
4
Second membre:
Matrice des vecteurs hors base:
1 0
B=
0 1
Vecteurs hors base: = {e1 , e2 }
Page 74 de 159
(2)
gradient de J
solutions de base
500

K
(1)
courbe de niveau de K

K gradient de K

J
contraintes
LGENDE:
x1
)
est
- Les contraintes nont pas t modifies donc le corps du

tableau simplexe qui est constitu par les coefficients des
variables de dcision dans les contraintes ne sera pas
modifi.
Nous dduirons donc le tableau simplexe relatif ce

point en prenant en compte ce qui suit:
3 4
( 3 ) + 2 ( 4 3 ) = 20 3
toujours optimum. La fonction vaut:
Loptimum antrieur le point x* = 4 , 4 , 0, 0
Relativement au problme original nous navons modifi

que la fonction objectif. Nous voyons graphiquement que
lensemble des solutions ralisables et les solutions de
base restent inchangs.
x2
x2
x1
e 2 point ralisable
CALCULS:
3 4
( 3 ) + 2 ( 4 3 ) = 20 3
Fonction objectif:
1 3 3
Ce2 = 0
; = 1 3
2 3 2
2 3 3
Ce1 = 0
; = 4 3
1 3 2
Cots dopportunit:
-4/3 -1/3 K = 20/3
-1/3 2/3 4/3
2/3 -1/3 4/3
e1
B b 0,
-1
Seule la fonction objectif a t modifie. Les seuls endroits du tableau simplexe o intervient la fonction
objectif sont les cots dopportunit et la valeur de la fonction objectif cela va sans dire. Les modifications
apporter au tableau antrieur sont minimes.
x1
x*

J
x2
Page 75 de 159
e 2 point ralisable
-5/3 1/3 L = 16/3
-1/3 2/3 4/3
2/3 -1/3 4/3
e1
entre
-5/3 1/3 L = 16/3
-1/3 2/3 4/3 2/3 = 2
pivot
e 2 point ralisable
2/3 -1/3 4/3 -1/3 N/A
e1
sort
e2
0
x1
x1
e1
vaut 3 ( 2 ) + ( 0 ) = 6 .
3 4
( 3 ) + 1( 4 3 ) = 16 3
Fonction objectif:
1 3 3
1
Ce2 = 0
; = 3
2
3
1
2 3 3
5
Ce1 = 0
; = 3
1 3 1
Cots dopportunit:
CALCULS:
3 ( 2 ) + 1( 0 ) = 6
Fonction objectif:
e 2 point ralisable Cots dopportunit:

1 2 3
1
1/2 1/2 0
2
C x2 = 1
; = 2
3
2
0

3/2 -1/2 1
2
1 2 3
-1/2 -3/2 0 L = 6
3
Ce1 = 0
; = 2
1 2 0
x2
-1
B b 0,
A la suite dune itration nous obtenons le nouvel optimum, le point z* = ( 2, 0, 0, 2 ) pour lequel la fonction
x2
x2
x1
x1
B b 0,
-1
fait de la modification de la fonction objectif. Cependant expliciter le tableau simplexe associ ce point
ntait pas vain car sil est vrai quil nest plus optimum, le nouvel optimum ne doit pas tre loin. Nous
itrerons.
Le cot dopportunit de la variable hors base e2 est positif. Le point considr nest donc plus optimum du
x2
x2
x1
x1
B b 0,
-1
au point x* = 4 , 4 , 0, 0 seront minimes (cots dopportunit et fonction objectif).
Une fois de plus seule la fonction objectif a chang, les modifications apporter au tableau simplexe relatif
3.- Nous appellerons L ( x1 , x2 ) la nouvelle fonction objectif L ( x1 , x2 ) = 3 x1 + x2 .
Page 76 de 159

J

L

L
x* 500
(2)
gradient de J
solutions de base
(1)
5
x1
courbe de niveau de L
gradient de L

J
LGENDE:
contraintes
coordonnes z* = ( 2, 0 ) .
Graphiquement nous observons la confirmation de ce que nous avons dtect au niveau des tableaux
simplexes: Le changement de fonction objectif provoque le dplacement de loptimum vers le point de
x2
Page 77 de 159
3.2- Changements dans les contraintes:

Il sagit ici de dterminer linfluence que peut avoir la modification de contraintes sur notre
poursuite dobjectif doptimisation.
La question ici est diffrente du cas antrieur du fait quune modification de contrainte (du fait dun
changement du prix dune matire premire ou du remplacement dune machine par un autre de meilleur
rendement) entrane un changement de laire des solutions ralisables, des coordonnes des solutions de
base et peut-tre des coordonnes de loptimum tandis que la base associe ces dernires ne se trouve
pas ncessairement modifie.
Max 2 x1 + 3 x2
2x + x 8
( P ) s 1 2
c x1 + 2 x2 8
x1 , x2 0
(1 )
(2)
Rsoudre graphiquement le problme et expliciter le tableau simplexe associ loptimum x*.
Nous changeons la seconde contrainte. Elle devient x1 + 4 x2 8 . Modifier le graphique

antrieur et commenter les ventuels changements observs. Expliciter le tableau simplexe
associ au point x* antrieur. Est-il toujours optimum? Si non expliciter le tableau simplexe
associ loptimum (nous lappellerons z*).
Nous changeons nouveau la seconde contrainte. Elle devient x1 + x2 6 . Expliciter le tableau

simplexe associ au point z* antrieur. Est-il toujours optimum? Si non expliciter le tableau
simplexe associ loptimum (nous lapplerons w*). Modifier le graphique antrieur et
commenter les ventuels changements observs.
Commenons par rsoudre graphiquement le problme: nous applerons J ( x1 , x2 ) la fonction

objectif J ( x1 , x2 ) = 2 x1 + 3 x2 .

Page 78 de 159
x2
x*
1.- Graphiquement.

J
(2)
x1
2 8
( 3 ) + 3 ( 8 3 ) = 40 3
La fonction est alors maximum, elle vaut:
2 x1* + 8 = 1 x1* + 4 x1* = 8

2
3
*
*
*
x2 = 2 x1 + 8 x2 = 8
3
Do:
(1) 2 x1* + x2* = 8 x2* = 2 x1* + 8

( 2 ) x1* + 2 x2* = 8 x2* = 1 x1* + 4
2
Loptimum x * se situe lintersection

des contraintes (1) et (2). Ses coordonnes
vrifient donc les quations des deux
droites:
(1)
gradient de J
solutions de base

J
LGENDE:
contraintes
Page 79 de 159
Matrice de base:
e 2 point ralisable
-1/3 -4/3 J = 40/3
-1/3 2/3 8/3
2/3 -1/3 8/3
e1
CALCULS:
( )
2 8
( 3 ) + 3 ( 8 3 ) = 40 3
Fonction objectif:
1 3 2
Ce2 = 0
; = 4 3
2 3 3
2 3 2
Ce1 = 0
; = 1 3
1 3 3
Cots dopportunit:
Page 80 de 159
1 2 1 2 3 1 3 8
B 1 B b =
=
3 1 2 1 3 2 3 8
1 0 8
0 1 8
2 1
1 2 1
1
B=
B =
3 1 2
1 2

Coordonnes de B y b dans la base :
Inverse de B:
hors base sont positifs. Le point est optimum. La fonction vaut 40 .
Evaluation de loptimalit: Le point x* = 8 , 8 , 0, 0 est ralisable. Les cots dopportunit des variables
x2
x2
x1
x1
B b 0,
8
b=
8
Second membre:
-1
1 0
B=
0 1
2 1
B=
1 2
Base: = { x1 , x2 } .
Nous avons dtermin graphiquement que le point optimum a pour coordonnes x* = 8 , 8 , 0, 0 do:

J
x2
z*
Max 2 x1 + 3 x2
2x + x 8
( P ) s 1 2
c x1 + 4 x2 8
x1 , x2 0
(1)
(2)
(1 )
gradient de J
solutions de base
x1
(1)
et
(2)
donc e1 , e2 = 0 et
mme base que prcdemment bien

que les coordonnes du point ne
soient plus les mmes.
nouvel optimum est = { x1 , x2 } , la
En conclusion la base associe au
e1 et e2 sont hors base.
contraintes
sont en base. De plus z* se situe sur les
donc que x1 , x2 0 et que, x1 et x2
Le nouvel optimum z* se situe au

milieu du graphique nous concluons
Nous remarquons que le changement

de contrainte rtrcit laire des
solutions ralisables et change
loptimum.
(2)
z* solution optimale (second cas)

J
contrainte modifie
LGENDE:
contraintes
2.- Nous changeons la seconde contrainte. Le problme devient:
Page 81 de 159
Matrice de base:
e 2 point ralisable
-5/7 -4/7 J = 88/7
-1/7 2/7 8/7
4/7 -1/7 24/7
e1
CALCULS:
( )
3 24
( 7 ) + 2 ( 8 7 ) = 88 7
Fonction objectif:
1 7 2
Ce2 = 0
; = 4 7
2 7 3
4 7 2
Ce1 = 0
; = 5 7
1 7 3
Cots dopportunit:
Page 82 de 159
1 4 1 4 7 1 7 24 7
B 1 B b =
=
7 1 2 1 7 2 7 8 7
1 0 8
0 1 8
2 1
1 4 1
1
B=
B =
7 1 2
1 4

Inverse de B:
sont ngatifs. Le point est optimum. La fonction vaut 88 .
Evaluation de loptimalit: au point z* = 24 , 8 , 0, 0 , les cots dopportunit des variables hors base
x2
x2
x1
x1
-1
B b 0,
8
b=
8
Second membre:
1 0
B=
0 1
2 1
B=
1 4
Base: = { x1 , x2 } .
Explicitons le tableau simplexe associ ce nouvel optimum:
optimum w*. Cependant, il est possible que la base associe lancien optimum z* soit toujours base
associe loptimum. Si ce ntait pas le cas il serait raisonnable de penser que la base associe au nouvel
optimum ne se trouve pas loin (dans le sens se trouve quelques itrations).
Nous savons donc maintenant que le point z* nest plus optimum, il nest mme pas solution de base. Le
changement de contrainte a donc chang substantiellement le problme, nous devrons trouver le nouvel
plus sommet du polydre des solutions ralisables sinon un point quelconque ralisable (ralisable
nanmoins du fait que ces coordonnes sont toutes positives ou nulles). Nous ne pouvons donc pas tablir
un tableau simplexe pour ce point du fait quun tableau simplexe correspond toujours une base laquelle
correspond toujours un sommet.
vecteurs ( x1 , x2 , e2 ) est donc lie et ne peut pas tre base de 2 ). Cela signifie donc que le point z* nest
Nous aurions donc potentiellement trois vecteurs en base pour un problme deux dimensions (la famille de
) . En remplaant dans les contraintes nous obtenons:

2 x + x 8 ( ) 2 x + x + e = 8 2 ( 24 ) + ( 8 ) + e = 8 e = 0
7
7
x + x 6 ( ) x + x + e = 6 ( 24 ) + ( 8 ) + e = 6 e = 10
7
7
7
En conclusion les coordonnes compltes du point z* sont z* = ( 24 , 8 , 0,10 ) .

7 7
7
point en question a pour coordonnes z* = 24 , 8
On nous demande tout dabord dexpliciter le tableau simplexe associ au point z*. Nous rapplerons que le
Max 2 x1 + 3 x2
2 x + x 8 ( 1)
( P ) s 1 2
c x1 + x2 6 ( 2 )
x1 , x2 0
3.- Nous changeons la seconde contrainte. Le problme devient:
Page 83 de 159
Matrice de base:
-1
entre
-1
-4 J = 16
2
sort
e 2 point ralisable
pivot
e1
loptimum. On itre.
CALCULS:
( )
2 ( 2 ) + 3 ( 4 ) = 16
Fonction objectif:
1 2
Ce2 = 0 ; = 4
2 3
1 2
Ce1 = 0 ; = 1
1 3
Cots dopportunit:
1 1 1 1 2
B 1 B b =
=
1 2 1 2 4
1 0 8
0 1 6
2 1
1 1
1
B=
B =
1 1
1 2

Inverse de B:
optimum. Avec le changement de contrainte ralis, la base = { x1 , x2 } nest plus base associe
Evaluation de loptimalit: le cot dopportunit de la variable hors base e1 est positif. Le point nest pas
x2
x2
x1
x1
-1
B b 0,
8
b=
8
Second membre:
1 0
B=
0 1
2 1
B=
1 1
Base = { x1 , x2 } .
Page 84 de 159
e1
-1
-3 J = 18
-1
e 2 point ralisable
Graphiquement:
CALCULS:
2 ( 0 ) + 3 ( 6 ) = 18
Fonction objectif:
1 0
Ce2 = 0 ; = 3
1 3
1 0
Ce1 = 0 ; = 3
1 3
Cots dopportunit:
w* = (0, 6, 2, 0) est optimum. La fonction vaut 18.
Evaluation de loptimalit: les cots dopportunit des variables hors base sont tous ngatifs. Le point
-3
x2
x2
e1
x1
B b 0,
= {e1 , x2 } .
Page 85 de 159
w*
x2

J
(1)
gradient de J
x1
(2)
point w* de coordonnes (0,6)-
Graphiquement le nouvel optimum est le
optimum conformment ce que nous

avons conclu plus haut.
associ la base = { x1 , x2 } nest pas
Nous observons galement que le sommet
excluant le point z* de celui-ci.
solutions de base
w* solution optimale (troisime cas)

J
contrainte modifie
Nous observons effectivement que le

changement
de
contrainte
modifie
lensemble des solutions ralisables
LGENDE:
contraintes
Page 86 de 159
3.3- Ajout dune contrainte:

Loriginalit de ce cas de figure rside dans le fait que nous allons ajouter une ligne au tableau simplexe du
fait de lajout dune contrainte, toute chose gale par ailleurs. Reprenons le problme antrieur:
Max 2 x1 + 3 x2
2x + x 8
( P ) s 1 2
c x1 + 2 x2 8
x1 , x2 0
(1 )
(2)
Nous ajoutons la contrainte (3): x2 7 .
Modifier le graphique antrieur et commenter les ventuels changements observs. Le point x*

est-il toujours optimum? Si oui expliciter le tableau simplexe associ au point x*.
-
Si non expliciter le tableau simplexe associ loptimum (nous lappellerons z*).

Supposons maintenant quau lieu de la contrainte (3) nous eussions ajout la contrainte
(4):
x1 + 3 x2 9 . Expliciter le tableau simplexe associ au point optimum antrieur. Est-il toujours

optimum? Si non expliciter le tableau simplexe associ loptimum (nous lappellerons w*).
x2
Conformment ce que nous avons

dtermin plus haut:
LGENDE:
contraintes

J
Loptimum
se
situe
x*
lintersection des contraintes (1) et (2).
Ses coordonnes vrifient donc les
quations des deux droites:
solutions de base
gradient de J
6
(1) 2 x1* + x2* = 8 x2* = 2 x1* + 8

( 2 ) x1* + 2 x2* = 8 x2* = 1 x1* + 4
2

J
Do:
2 x1* + 8 = 1 x1* + 4 x1* = 8

2
3
*
*
*
x2 = 2 x1 + 8 x2 = 8
3
x*
La fonction est alors maximum, elle

vaut:
( 3 ) + 3 ( 8 3 ) = 40 3
2 8
(2)
(1)
0
x1

Page 87 de 159
x2
x*

J
(3) (1)
gradient de J
(2)
x1
x * ne sen trouve pas
point x* na que deux vecteurs. Nous

devons donc dterminer quel est le
troisime vecteur qui complte la base.
Nous voyons que nous avons trois

contraintes prsent donc le tableau
simplexe trois lignes.
Cependant la base antrieure associe au
Max 2 x1 + 3 x2
2 x1 + x2 8 (1)
( P ) s x1 + 2 x2 8 ( 2 )
cx 7
( 3)
2
2
x ,x 0
1 2
Le nouveau problme est:
loptimum
modifi.
Graphiquement nous observons que

lajout dune contrainte rduit lensemble
des solutions ralisables. Cependant
x* solution optimale

J
solutions de base
contraintes
contrainte ajoute
LGENDE:
1.- Nous ajoutons la contrainte (3): x2 7 .
Page 88 de 159
) x* a pour coordonnes
( )
CALCULS:
8

b= 8

7
2
Second membre:
2
3 2

Ce1 = 0 1 ; 3
3
1 0
3
Cots dopportunit:
= 1 3
Page 89 de 159
x* = 8 , 8 , 0, 0, 5 . De mme nous aurions pu remarquer que graphiquement le point x* se trouve au Inverse de B:

3 3
6
2 1 0
2 1 0
milieu du graphique donc x1 , x2 0 puis nous nous trouvons sous la contrainte (3) donc e3 0 ce qui nous
1
1
B = 1 2 0 B = 1 2 0
3
donne comme base associe au sommet = { x1 , x2 , e3 } .
0 1 1
1 2 1

Matrice de base:
2 1 0
1 0 8
B = 1 2 0
0 1 1
0
1
8
0 0 7
2

2
1 83
3
2 1 0 3
1 0
1
8
1
2
B B b = 1 2 0 =
3
3 3
B = 0 1
3
1 2 1 1
0 0
2 5
3
3
6
En remplaant dans les contraintes nous obtenons que le point x* = 8 , 8
e2
-1/3 -4/3
1/3 -2/3
-1/3 2/3
2/3 -1/3
e1
J = 40/3
5/6
8/3
8/3
e 3 point ralisable
x2
x2
x1
x1
e 2 point ralisable
2 8
( 3 ) + 3 ( 8 3 ) = 40 3
Fonction objectif:
1
3 2

Ce2 = 0 2 ; 3
3
2 0
3
-1/3 -4/3 J = 40/3
-1/3 2/3 8/3
2/3 -1/3 8/3
e1
B b 0,
-1
de changements par rapport au tableau simplexe optimum antrieur associ la base = { x1 , x2 } .
Nous remarquerons galement que le tableau simplexe associ la base = { x1 , x2 , e3 } a souffert trs peu
optimum. La fonction vaut 40 .
Evaluation de loptimalit: les cots dopportunit des variables hors base sont ngatifs. Le point est
e3
x2
x2
x1
x1
-1
B b 0,
= 4 3
Page 90 de 159
(4)
(2)
(1 )
) . En remplaant dans les contraintes nous obtenons:
optimum = { x1 , x2 , e2 } .
Graphiquement nous confirmons lhypothse que nous venons de formuler. Le nouvel optimum se situe
lintersection des contraintes (1) et (3), en dessous de la contrainte (2) donnant pour base associe au sommet
point x* des solutions de base.
Nous conclurons donc que la contrainte ajoute a tronqu le polydre des solutions ralisables excluant le
ralisable. Il ny a donc aucun intrt expliciter le tableau simplexe associ la base = { x1 , x2 , e3 } .
x* = 8 , 8 , 0, 0, 5 . Nous remarquons une coordonne ngative indiquant que le point nest pas
3 3
3
Examinons les coordonnes du point x* = 8 , 8
Max 2 x1 + 3 x2
2 x1 + x2 8
( P ) s x1 + 2 x2 8
c x + 3x 9
2
1
x1 , x2 0
Le problme devient:
2.- Nous ajoutons la contrainte (3): x1 + 3 x2 9 .
CALCULS:
Page 91 de 159
Matrice de base:
gradient de J
solutions de base
(2)
x1
(3)
( )
3
5 2

Ce1 = 0 1 ; 3
5
1 0
5
Cots dopportunit:
B 1
= 3 5
Page 92 de 159
3
1
5 3
3 0 1 5
1
1
2
B b = 1 0 2 =
2
5
5
5
1
1 5 3 1
3
5
5
1 0 8
0 0 8
0 1 9
2 1 0
3 0 1
1
1
B = 1 2 1 B = 1 0 2
5
1 3 0
1 5 3

Inverse de B:
= { x1 , x2 , e2 } .
(1)
Appelons z* loptimum recherch.
z*

J
LGENDE:
contraintes
contrainte ajoute
z* nouvelle solution optimale

J
x2
e2
-3/5
-1/5
-1/5
3/5
e1
e2
-4/5 J = 12
-3/5
2/5
-1/5
e 3 point ralisable
-1
B b 0,
2 ( 3) + 3 ( 2 ) = 12
Fonction objectif:
1
5 2

Ce2 = 0 2 ; 3
5
3 0
ngatifs. Le point est optimum. La fonction vaut 12.
Evaluation de loptimalit: au point z* = ( 3, 2, 0,1, 0 ) , les cots dopportunit des variables hors base sont
x2
x2
x1
x1
8

b = 8
9

Second membre:
1 0
B = 0 0
0 1
2 1 0
B = 1 2 1
1 3 0
= 4 5
Page 93 de 159
Exercices du chaptre 3.
Exercice 1.Soit le programme linaire:
Max 3 x1 + 2 x2
2 x1 + x2 8
( P) s
c x1 + x2 5
x1 , x2 0
Rsoudre le problme grce lalgorithme du simplexe. Le point optimum sera appel x*.
La seconde contrainte se voit modifie et devient 2 x1 + 3 x2 12

-
Vrifier si la base associe loptimum antrieur est ralisable et expliciter le tableau simplexe
associ dans le cas chant. Sagit-il toujours du mme point x*? Si non, donner les
coordonnes du point associ cette base (appelons-le z*) et la valeur de la fonction objectif.
La base est-elle toujours optimum? Si non, trouver le nouvel optimum (nous lappellerons v*).
Raliser le graphique relatif ce nouveau problme.
Nous ajoutons maintenant la contrainte x2 3 .

-
Modifier le graphique antrieur et commenter les ventuels changements observs. Loptimum

a-t-il chang? Si oui expliciter le tableau simplexe associ au nouvel optimum.
Si non expliciter le tableau simplexe associ loptimum z*).
Nous retirons la contrainte x2 3 et la remplaons par la contrainte x1 2 .

-
Expliciter les coordonnes du sommet associ la base optimum antrieur. Est-il ralisable?
Si non, rsoudre ce nouveau problme par la mthode de votre choix.
Exercice 2.Soit le programme linaire:
Max x1 + 3 x2
x1 + 2 x2 12
( P ) s 5 x1 + 3x2 30
cx +x 7
1 2
x1 , x2 0
-
Reprsenter lensemble des solutions ralisables et expliciter les coordonnes de toutes les
solutions de base.
Rsoudre graphiquement le problme.
Expliciter le tableau simplexe associ la base optimum.

Page 94 de 159
La fonction objectif se voit modifie et devient 2 x1 + 3 x2

-
Actualiser le graphique antrieur et commenter les changements observs.
Expliciter le tableau simplexe associ loptimum (nous lappellerons x*).
La fonction objectif se voit modifie et devient 3x1 + x2

-
Expliciter le tableau simplexe associ loptimum antrieur. Est-il toujours optimum?
Dterminer la solution optimum en utilisant lalgorithme du simplexe depuis le sommet x*.
Exercice 3.Une entreprise fabrique deux produits 1 et 2 lesquels requirent tre travaills par deux machines A et B.
Les rendements quotidiens des machines sont donns dans le tableau continuation:
Rendement quotidien en produits 1

Rendement quotidien en produits 2
Machine A
Machine B
8
8
6
12
La demande est bien connue des services marketing de lentreprise et si bien le produit 1 prsente une
importante demande non satisfaite, nous ne saurions vendre plus de 7 produits 2 par jour.
Le produit 1 se vend S/. 2 000 et le produit 2 S/. 3 000.
-
Rsoudre le problme graphiquement.

Expliciter le tableau simplexe associ loptimum.
Lentreprise ayant ces derniers mois provisionn partie de ses revenus, elle est aujourdhui confronte un
choix relatif une amlioration quelle pourrait apporter ses machines. Nous supposerons que les deux
amliorations reprsentent un cot similaire.
Choix n1: investir dans une amlioration de la machine A portant son rendement quotidien en
produits 1 et 2 a 9 chacun.
Choix n2: investir dans une amlioration de la machine B portant son rendement quotidien en
produits 1 et 2 a 7 et 14 respectivement.
-
Justifier clairement quel serait le choix le plus appropri en saidant ventuellement du

graphique. Le cot relatif dune amlioration par rapport lautre a-t-elle vraiment de
limportance? Justifier.
Exprimer le problme de lentreprise en prenant en compte lamlioration choisie.
La base optimum antrieure est-elle toujours optimum? Expliciter le tableau simplexe associ
loptimum.

Page 95 de 159

B105 Ch3

Transféré par

Droits d'auteur :

Formats disponibles

B105 Ch3

Transféré par

Informations du document

Description originale:

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

B105 Ch3

Transféré par

Droits d'auteur :

Formats disponibles

CHAPITRE III: MODIFICATIONS DES DONNES DUN PROBLME CONOMIQUE

3.1- Changements dans la fonction objectif:

Soit le programme linaire suivant:

Rsoudre graphiquement le problme et expliciter le tableau simplexe associ loptimum x*.

La fonction objectif devient 3 x1 + 2 x2 . Modifier le graphique antrieur et commenter les

La fonction objectif devient 3 x1 + 1x2 . Expliciter le tableau simplexe associ au point x*

Commenons par rsoudre graphiquement le problme: nous applerons J ( x1 , x2 ) la fonction

Auteur: Philippe Gollotte

aire des solutions ralisables

La fonction est alors maximum, elle vaut:

2 x1* + 4 = 1 x1* + 2 x1* = 4

x1* + 2 x2* = 4 ( 2 ) x2* = 1 x1* + 2 ( 2 )

2 x1* + x2* = 4 (1) x2* = 2 x1* + 4 (1)

Loptimum x * se situe lintersection des contraintes (1)

Auteur: Philippe Gollotte

-1/3 -4/3 J = 20/3

-1/3 2/3 4/3

2/3 -1/3 4/3

2.- Nous appellerons K ( x1 , x2 ) la nouvelle fonction objectif K ( x1 , x2 ) = 3 x1 + 2 x2 .

Evaluation de loptimalit: au point x* = 4 , 4 , 0, 0 : les lments du second membre sont positifs. Le

Tableau simplexe associ:

Auteur: Philippe Gollotte

Matrice des vecteurs hors base:

Vecteurs hors base: = {e1 , e2 }

aire des solutions ralisables

- Les contraintes nont pas t modifies donc le corps du

Nous dduirons donc le tableau simplexe relatif ce

toujours optimum. La fonction vaut:

Loptimum antrieur le point x* = 4 , 4 , 0, 0

Relativement au problme original nous navons modifi

-4/3 -1/3 K = 20/3

-1/3 2/3 4/3

2/3 -1/3 4/3

Auteur: Philippe Gollotte

-5/3 1/3 L = 16/3

-1/3 2/3 4/3

2/3 -1/3 4/3

-5/3 1/3 L = 16/3

-1/3 2/3 4/3 2/3 = 2

2/3 -1/3 4/3 -1/3 N/A

e 2 point ralisable Cots dopportunit:

au point x* = 4 , 4 , 0, 0 seront minimes (cots dopportunit et fonction objectif).

Auteur: Philippe Gollotte

3.- Nous appellerons L ( x1 , x2 ) la nouvelle fonction objectif L ( x1 , x2 ) = 3 x1 + x2 .

aire des solutions ralisables

Auteur: Philippe Gollotte

3.2- Changements dans les contraintes:

Soit le programme linaire suivant:

Rsoudre graphiquement le problme et expliciter le tableau simplexe associ loptimum x*.

Nous changeons la seconde contrainte. Elle devient x1 + 4 x2 8 . Modifier le graphique

Nous changeons nouveau la seconde contrainte. Elle devient x1 + x2 6 . Expliciter le tableau

Commenons par rsoudre graphiquement le problme: nous applerons J ( x1 , x2 ) la fonction

Auteur: Philippe Gollotte

Auteur: Philippe Gollotte

La fonction est alors maximum, elle vaut:

2 x1* + 8 = 1 x1* + 4 x1* = 8

(1) 2 x1* + x2* = 8 x2* = 2 x1* + 8

Loptimum x * se situe lintersection

aire des solutions ralisables