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 } .

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

Nous avons dtermin graphiquement que le point optimum a pour coordonnes x* = 4 , 4 , 0, 0 do:

x*


J

Auteur: Philippe Gollotte

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:

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

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:

Auteur: Philippe Gollotte

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

courbe de niveau de J
x* solution optimale (premier cas)

K gradient de K


J

aire des solutions ralisables

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:

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

-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

Auteur: Philippe Gollotte

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:

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

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

Auteur: Philippe Gollotte

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

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

courbe de niveau de L

gradient de L

courbe de niveau de J
x* solution optimale (premier cas)


J

aire des solutions ralisables

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

Auteur: Philippe Gollotte

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.

Soit le programme linaire suivant:

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 .

Auteur: Philippe Gollotte

Page 78 de 159
Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

Auteur: Philippe Gollotte

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:

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

(1)

gradient de J

solutions de base

courbe de niveau de J
x* solution optimale (premier cas)


J

aire des solutions ralisables

LGENDE:
contraintes

PROPOSITION DE RESOLUTION

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:

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

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,

Tableau simplexe associ:

Auteur: Philippe Gollotte

 8
b=
8

Second membre:

-1

Matrice des vecteurs hors base:

1 0
B=

0 1

Vecteurs hors base: = {e1 , e2 }

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

Auteur: Philippe Gollotte

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

aire des solutions ralisables

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.

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

(2)

courbe de niveau de J
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

Coordonnes de B y b dans la base :

Inverse de B:

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

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,

Tableau simplexe associ:

 8
b=
8

Second membre:

Auteur: Philippe Gollotte

Matrice des vecteurs hors base:

1 0
B=

0 1

Vecteurs hors base: = {e1 , e2 }

2 1
B=

1 4

Base: = { x1 , x2 } .

Explicitons le tableau simplexe associ ce nouvel optimum:

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

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

Auteur: Philippe Gollotte

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

Coordonnes de B y b dans la base :

Inverse de B:

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

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,

Tableau simplexe associ:

 8
b=
8

Second membre:

Auteur: Philippe Gollotte

Matrice des vecteurs hors base:

1 0
B=

0 1

Vecteurs hors base: = {e1 , e2 }

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:

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

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

Auteur: Philippe Gollotte

x2

x2

e1

x1

Tableau simplexe associ:

B b 0,

= {e1 , x2 } .

Page 85 de 159

w*

Auteur: Philippe Gollotte

x2


J

(1)

courbe de niveau de J

gradient de J

x1

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

(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

aire des solutions ralisables

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:

Soit le programme linaire suivant:

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

aire des solutions ralisables


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

courbe de niveau de J
x* solution optimale (premier cas)
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

Auteur: Philippe Gollotte

Page 87 de 159
Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

Auteur: Philippe Gollotte

x2

x*


J

(3) (1)

courbe de niveau de J

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

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

x* solution optimale


J

solutions de base

aire des solutions ralisables

contraintes
contrainte ajoute

LGENDE:

1.- Nous ajoutons la contrainte (3): x2 7 .

PROPOSITION DE RESOLUTION

Page 88 de 159

) x* a pour coordonnes

( )

CALCULS:

Tableau simplexe associ:

8

b= 8

7
2

Second membre:

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

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:
Coordonnes de B y b dans la base :
2 1 0
1 0 8
B = 1 2 0

0 1 1

0
1
8

0 0 7
Vecteurs hors base: = {e1 , e2 }
2

Matrice des vecteurs hors base:

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

Auteur: Philippe Gollotte

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

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

-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

Auteur: Philippe Gollotte

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 } .

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

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:

Auteur: Philippe Gollotte

2.- Nous ajoutons la contrainte (3): x1 + 3 x2 9 .

CALCULS:
Page 91 de 159

Matrice de base:

courbe de niveau de J

gradient de J

solutions de base

aire des solutions ralisables

(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

Coordonnes de B y b dans la base :

Inverse de B:

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

= { x1 , x2 , e2 } .

(1)

Appelons z* loptimum recherch.

z*


J

LGENDE:
contraintes
contrainte ajoute

z* nouvelle solution optimale


J

Auteur: Philippe Gollotte

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

Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

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

Tableau simplexe associ:

8

b = 8
9

Second membre:

Auteur: Philippe Gollotte

Matrice des vecteurs hors base:

1 0
B = 0 0
0 1

Vecteurs hors base: = {e1 , e3 }

2 1 0
B = 1 2 1
1 3 0

= 4 5

Page 93 de 159

Exercices du chaptre 3.
Exercice [Link] 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 [Link] 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.

Auteur: Philippe Gollotte

Page 94 de 159
Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation

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 [Link] 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.

Auteur: Philippe Gollotte

Page 95 de 159
Consorcio e-Miage - Universidad de San Martn de Porres, B105 Programmation Mathmatique et Optimisation