494 CHAPITRE9 PROGRAMMATIONLINÉAIRE

9.3 LA MÉTHODE SIMPLEXE : MAXIMISATION

Pour les problèmes de programmation linéaire impliquant deux variables, la méthode de solution graphique
introduit dans la section 9.2 est pratique. Cependant, pour des problèmes impliquant plus de deux
des variables ou des problèmes impliquant un grand nombre de contraintes, il est préférable d'utiliser une solution
méthodes qui sont adaptables aux ordinateurs. Une de ces méthodes s'appelle la méthode du simplexe,
développé par George Dantzig en 1946. Il nous fournit un moyen systématique d'examiner
les sommets de la région faisable pour déterminer la valeur optimale de la fonction objective.
Nous introduisons cette méthode avec un exemple.
Supposons que nous voulons trouver la valeur maximale de zϭ 4x1ϩ 6x2,oùx1Ն 0andx2Ն 0
sous réserve des contraintes suivantes.
Ϫx1ϩ 5x2Յ 11
Ϫx1ϩ 5x2Յ 27
2x1ϩ 5x2Յ 90
Puisque le côté gauche de chaque inégalité est inférieur ou égal au côté droit, il y a
doit exister des nombres non négatifs s,s
1 2et3quispeut être ajouté au côté gauche de chaque équation
tion de produire le système suivant d'équations linéaires.
Ϫx1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 11
Ϫx1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 27
2x1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 90
Les numéros1,s2et3sont appelées des variables slack car elles prennent le "slack" dans
chaque inégalité.

Forme standard d'un Un problème de programmation linéaire est sous forme standard s'il cherche à maximiser l'objectif
fonctionz tivesϭ c1x1ϩ c2 x2ϩ . . . ϩ cn xnsous réserve des contraintes
Programmation Linéaire
a11x1ϩ a12x2ϩ . . . ϩ a1nxnՅ b1
Problème
un21x1ϩ a22x2ϩ . . . ϩ a2nxnՅ b2
.
.
.
unm1 x1ϩ am2 x2 ϩ . . . ϩ amnxnՅ bm
où es-tu jeՆ0andbjeՆ 0. Après l'ajout de variables d'écart, le système correspondant de
les équations de contrainte

a11x1ϩ a12x2ϩ . . . ϩ a1nxnϩ s1 ϭ b1

a21x1ϩ a22x2ϩ . . . ϩ a2nxn ϩ s2 ϭ b2
.
.
.
am1x1ϩ am2x2 ϩ . . . ϩ amnxn ϩ smϭ bm
où estjeՆ 0.
 SECTION9.3 LAMÉTHODESIMPLEXE:MAXIMISATION 495

REMARQUE : Notez que pour un problème de programmation linéaire sous forme standard, l'objectif
La fonction doit être maximisée, pas minimisée. (Les problèmes de minimisation seront discutés dans)
Sections 9.4 et 9.5.)

Une solution de base d'un problème de programmation linéaire sous forme standard est une solution
͑x1,x2, . . . ,xn,s1,s2, . . . ,sm͒ des équations de contrainte dans lesquelles au plus m variables sont
non nul––les variables qui sont non nulles sont appelées variables de base. Une solution de base pour
toutes les variables non négatives sont appelées une solution réalisable de base.

Le tableau Simplex
La méthode du simplexe est réalisée en effectuant des opérations élémentaires sur les lignes d'une matrice.
que nous appelons le tableau simplex. Ce tableau consiste en la matrice augmentée correspondante.
répondant aux équations de contrainte ainsi qu'aux coefficients de la fonction objective
écrit sous la forme
Ϫc1x1Ϫ c2x2 Ϫ . . . Ϫ cnxnϩ ͑0s͒ 1ϩ ͑0s͒ 2ϩ . . . ϩ ͑0͒ smϩ zϭ 0.

Dans le tableau, il est d'usage d'omettre le coefficient de z. Par exemple, le tableau du simplexe
pour le problème de programmation linéaire

zϭ 4x1ϩ 6x2 Fonction objective

}
Ϫx1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 11
Ϫx1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 27 Contraintes
2x1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 90
est comme suit.
De base
x1 x2 s1 s2 s3 b Variables
Ϫ1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0
↑
Valeur z actuelle

Pour ce tableau simple initial, les variables de base sont12,ands3, et ensuite sur une base non fondamentale
les variables (qui ont une valeur de zéro) sont x1etx2Ainsi, à partir des deux colonnes qui sont
à l'extrême droite, nous voyons que la solution actuelle est
x1ϭ 0,x2ϭ 0,s1ϭ 11,s2ϭ 27, et3ϭ 90.
Cette solution est une solution réalisable de base et est souvent écrite comme

͑x1,x2,s1,s2,s3͒ ϭ ͑0, 0, 11, 27, 90͒.

496 CHAPITRE9 PROGRAMMATIONLINÉAIRE

L'entrée dans le coin inférieur droit du tableau du simplex est la valeur actuelle de z. Remarque
que les entrées de la dernière ligne sous et xsont
1 xles
2 négatifs des coefficients de etx1
x2dans la fonction objective
zϭ 4x1ϩ 6x2.
Pour effectuer un contrôle d'optimalité pour une solution représentée par un tableau simplexe, nous examinons
aux entrées de la dernière ligne du tableau. Si l'une de ces entrées est négative (comme
au-dessus), alors la solution actuelle n'est pas optimale.

Pivoter
Une fois que nous avons établi le tableau simplex initial pour un problème de programmation linéaire, le sim-
La méthode du plex consiste à vérifier l'optimalité et ensuite, si la solution actuelle n'est pas optimale
Timal, améliorant la solution actuelle. (Une solution améliorée est celle qui a une valeur z plus grande)
que la solution actuelle.) Pour améliorer la solution actuelle, nous introduisons une nouvelle variable de base
dans la solution––nous appelons cette variable la variable d'entrée. Cela implique que l'un des
les variables de base actuelles doivent partir, sinon nous aurions trop de variables pour un élément de base
solution––nous appelons cette variable la variable sortante. Nous choisissons l'entrant et
départ des variables comme suit.
1. La variable d'entrée correspond à la plus petite (la plus négative) entrée dans le
ligne du bas du tableau.
2. La variable de départ correspond au plus petit ratio non négatif de bje͞aij, dans le
colonne déterminée par la variable d'entrée.
3. L'entrée dans le tableau simplex dans la colonne de la variable entrante et celle du départ
La ligne de la variable s'appelle le pivot.
Enfin, pour former la solution améliorée, nous appliquons l'élimination de Gauss-Jordan à la colonne
qui contient le pivot, comme illustré dans l'exemple suivant. (Ce processus est appelé
pivotement.)

E X E M P L E 1 Changer de cap pour trouver une solution améliorée

Utilisez la méthode du simplexe pour trouver une solution améliorée au problème de programmation linéaire.
représenté par le tableau suivant.
De base
x1 x2 s1 s2 s3 b Variables

Ϫ1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0

La fonction objective pour ce problème est zϭ 4x1ϩ 6x2.

 SECTION9.3 LAMÉTHODESIMPLEX:MAXIMISATION 497

SolutionNotez que la solution ͑xactuelle

ϭ1 0,xϭ 0,sϭ
2 11,sϭ
1 27,sϭ 90͒
2 3 correspond à
x2 est la variable d'entrée,
az–valeur de 0. Pour améliorer cette solution, nous déterminons que
parce queϪ6 est la plus petite entrée dans la dernière rangée.
De base
x1 x2 s1 s2 s3 b Variables

Ϫ1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0
↑
Entrée

Pourvoirpourquoinouschoisissonsx2en tant que variable d'entrée, souviens-toi de celaϭ 4x1ϩ 6x2Ainsi, cela
il semble qu'un changement d'unité dans x2produit un changement de 6 inz, tandis qu'un changement unitaire en x1
produit un changement de seulement 4 pouces.

Pour trouver la variable de départ, nous localisons le bjequi ont des éléments positifs correspondants
dans la colonne des variables d'entrée et formez les ratios suivants.
11 27 90
ϭ 11, ϭ 27 ϭ 18
1 1 5
Ici, le plus petit rapport positif est 11, donc nous choisissons1comme la variable de départ.
De base
x1 x2 s1 s2 s3 b Variables

Ϫ1 1 1 0 0 11 s1 ← Départ
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0
↑
Entrer

Notez que le pivot est l'entrée de la première ligne et de la deuxième colonne. Maintenant, nous utilisons Gauss-
L'élimination de Jordan pour obtenir la solution améliorée suivante.
Avant le pivotement Après avoir pivoté

Ϫ1 1 1 0 0 11 Ϫ1 1 1 0 0 11

΄ 1
2
Ϫ4Ϫ6
1
5
0
0
0
1
0
0
0
1
0
27
90
0
΅ ΄ 2
7
Ϫ10
0
0
0
Ϫ1
Ϫ5
6
1
0
0
0
1
0
16
35
66
΅
Le nouveau tableau apparaît désormais comme suit.
498 CHAPITRE9 PROGRAMMATIONLINÉAIRE

De base
x1 x2 s1 s2 s3 b Variables

Ϫ1 1 1 0 0 11 x2
2 0 Ϫ1 1 0 16 s2
7 0 Ϫ5 0 1 35 3

Ϫ10 0 6 0 0 66

Remarque que2a remplacé1dans la colonne de base et la solution améliorée

͑x1,x2,s1,s2,s3͒ ϭ ͑0, 11, 0, 16, 35͒

a une valeur az de

zϭ 4x1ϩ 6x2ϭ 4͑0͒ ϩ 6͑11͒ ϭ 66.

Dans l'exemple 1, la solution améliorée n'est pas encore optimale puisque la ligne du bas a encore un
entrée négative. Ainsi, nous pouvons appliquer une autre itération de la méthode du simplexe pour aller plus loin.
x la variable d'entrée. De plus, le petit-
prouver notre solution comme suit. Nous choisissons1comme
est un ratio non négatif de 11͞ ͑ Ϫ1͒, 16͞2ϭ 8 et 35͞7ϭ 5 est 5, sos3est le départ
variable. L'élimination de Gauss-Jordan produit ce qui suit.

Ϫ1 1 1 0 0 11 Ϫ1 1 1 0 0 11

΄ 2
7
Ϫ10
0
0
0
Ϫ1
Ϫ5
6
1
0
0
0
1
0
16
35
66
΅ ΄ 2
1
Ϫ10
0
0
0
Ϫ1
Ϫ57
6
1
0
0
0
1
7
0
16
5
66
΅
2 1
0 1 0 16

΄ ΅
7 7
3
0 0 7 1 Ϫ27 6
1
1 0 Ϫ57 0 7 5
10
0 0 Ϫ87 0 7 116

Ainsi, le nouveau tableau simplex est le suivant.

Basique
x1 x2 s1 s2 s3 b Variables
2 1
0 1 7 0 7 16 x2
3
0 0 7 1 Ϫ27 6 s2
1
1 0 Ϫ57 0 7 5 x1
10
0 0 Ϫ87 0 7 116
Dans ce tableau, il y a encore une entrée négative dans la dernière ligne. Ainsi, nous choisissons1en tant que
entrée des variables et2comme la variable de départ, comme indiqué dans le tableau suivant.
 SECTION9.3 LAMÉTHODESIMPLEXE:MAXIMISATION 499

Basique
x1 x2 s1 s2 s3 b Variables
2 1
0 1 7 0 7 16 x2
3
0 0 7 1 Ϫ27 6 s2 ← Départ
1
1 0 Ϫ57 0 7 5 x1
dix
0 0 Ϫ87 0 7 116
↑
Entrée

En effectuant une itération de plus de la méthode du simplexe, nous obtenons le tableau suivant.
(Essayez de vérifier cela.)
De base
x1 x2 s1 s2 s3 b Variables
1
0 1 0 Ϫ23 3 12 x2
7
0 0 1 3 Ϫ23 14 s1
5
1 0 0 3 Ϫ13 15 x1
8 2
0 0 0 3 3 132 Valeur z maximale
Dans ce tableau, il n'y a pas d'éléments négatifs dans la dernière ligne. Nous avons donc déterminé
extrait la solution optimale à être

͑x1,x2,s1,s2,s3͒ ϭ ͑15, 12, 14, 0, 0͒

avec

zϭ 4x1ϩ 6x2ϭ 4͑quinze͒ ϩ 6͑12͒ ϭ 132.

REMARQUE : Des égalités peuvent survenir dans le choix des variables d'entrée et/ou de sortie. Cela devrait

il peut être fait un choix parmi les variables à égalité.

Parce que le problème de programmation linéaire dans l'exemple 1 impliquait seulement deux variables de décision.
tables, nous aurions pu utiliser une technique de solution graphique, comme nous l'avons fait dans l'Exemple 2, Section
Figure 9.18
x2 9.2. Remarquez à la Figure 9.18 que chaque itération dans la méthode du simplexe correspond à un déplacement
d'un sommet donné à un sommet adjacent avec une valeur-z améliorée.
25

20
(5, 16) ͑0, 0͒ ͑0, 11͒ ͑5, 16͒ ͑15, 12͒
15 (15, 12) zϭ 0 zϭ 66 zϭ 116 zϭ 132
10 (0, 11)
5
(0, 0) (27, 0)
La méthode du Simplex
x1
5 10 15 20 25 30 Nous résumons les étapes impliquées dans la méthode du simplexe comme suit.
500 CHAPITRE9 PROGRAMMATIONLINÉAIRE

La méthode du simplexe Pour résoudre un problème de programmation linéaire sous forme standard, suivez les étapes suivantes.
1. Convertissez chaque inégalité dans l'ensemble des contraintes en une équation en ajoutant des variables d'écart.
(Forme Standard) variables.
2. Créez le tableau simplexe initial.
3. Localisez l'entrée la plus négative dans la dernière ligne. La colonne pour cette entrée s'appelle
la colonne d'entrée. (S'il y a des égalités, n'importe quelle entrée ex aequo peut être utilisée pour déterminer
la colonne d'entrée.)
4. Formez les ratios des entrées dans la « colonne-b » avec leurs correspondants positifs
les entrées dans la colonne d'entrée. La ligne de départ correspond au plus petit non-
ratio négatifje͞ajej (Si toutes les entrées dans la colonne d'entrée sont 0 ou négatives, alors il
il n'y a pas de solution maximale. En cas d'égalité, choisissez soit l'une soit l'autre entrée.) L'entrée dans la ligne de départ

et la colonne d'entrée s'appelle le pivot.

5. Utilisez des opérations élémentaires sur les lignes pour que le pivot soit 1, et que toutes les autres entrées dans le
les colonnes entrantes sont 0. Ce processus s'appelle le pivotement.
6. Si toutes les entrées dans la dernière ligne sont nulles ou positives, c'est le tableau final. Sinon, allez
retour à l'étape 3.
7. Si vous obtenez un tableau final, alors le problème de programmation linéaire a un maximum
solution, qui est donnée par l'entrée dans le coin inférieur droit du tableau.

Notez que la solution réalisable de base d'un tableau simple initial est
͑x1,x2, . . . ,xn,s1,s2, . . . ,sm ͒ ϭ ͑0, 0, . . . , 0,b1,b2, . . . ,bm .͒
Cette solution est basique car au maximum, les variables sont non nulles (à savoir les variables d'écart).
C'est faisable car chaque variable est non négative.
Dans les deux exemples suivants, nous illustrons l'utilisation de la méthode du simplexe pour résoudre un
problème impliquant trois variables de décision.

E X A M P L E 2La méthode du simplexe avec trois variables de décision

Utilisez la méthode du simplexe pour trouver la valeur maximale de

zϭ 2x1Ϫ x2ϩ 2x3 Fonction objective

sous réserve des contraintes

2x1ϩ 2x2Ϫ 2x3Յ 10
2x1ϩ 2x2Ϫ 2x3Յ 20
2x1ϩ 2x2ϩ 2x3Յ 25

où est1Ն 0,x2Ն 0,etx3Ն 0.

Solution en utilisant la solution réalisable de base

͑x1,x2,x3,s1,s2,s3͒ ϭ ͑0, 0, 0, 10, 20, 5͒

le tableau simplexe initial pour ce problème est comme suit. (Essayez de vérifier ces calculs,
et notez le « lien » qui se produit lors du choix de la première variable d'entrée.)
 SECTION9.3 LAMÉTHODESIMPLEXE:MAXIMISATION 501

Basique
x1 x2 x3 s1 s2 s3 b Variables

2 1 0 1 0 0 10 s1
1 2 Ϫ2 0 1 0 20 s2
0 1 2 0 0 1 5 s3 ← Départ
Ϫ2 1 Ϫ2 0 0 0 0
↑
Entrer

De base
x1 x2 x3 s1 s2 s3 b Variables

2 1 0 1 0 0 10 s1 ← Départ
1 3 0 0 1 1 25 s2
1 1 5
0 2 1 0 0 2 2 x3

Ϫ2 2 0 0 0 1 5
↑
Entrée

Basique
x1 x2 x3 s1 s2 s3 b Variables
1 1
1 2 0 2 0 0 5 x1
5
0 2 0 Ϫ12 1 1 20 s2
1 1 5
0 2 1 0 0 2 2 x3

0 3 0 1 0 1 15

Cela implique que la solution optimale est

͑x1,x2,x3,s1,s2,s3͒ ϭ ͑5, 052 , 0, 20, 0͒

et la valeur maximale de z est 15.

Parfois, les contraintes d'un problème de programmation linéaire incluront une équation.
Dans de tels cas, nous ajoutons toujours une « variable d'écart » appelée variable artificielle pour former le ini-
tableau du simplexe d'essai. Techniquement, cette nouvelle variable n'est pas une variable d'amortissement (parce qu'il y a)
aucun relâchement à prendre). Une fois que vous avez déterminé une solution optimale dans un tel problème,
vous devriez vérifier que toutes les équations données dans les contraintes originales sont satisfaites.
L'exemple 3 illustre un tel cas.

E X A M P L E 3La méthode du Simplex avec trois variables de décision

Utilisez la méthode du simplexe pour trouver la valeur maximale de

zϭ 3x1ϩ 2x2ϩ x3 Fonction objective

502 CHAPITRE9 PROGRAMMATIONLINÉAIRE

sous réserve des contraintes

4x1ϩ 3x2ϩ 3x3ϭ 30
2x1ϩ 3x2ϩ 3x3Յ 60
2x1ϩ 2x2ϩ 3x3Յ 40

où est x1Ն 0,x2Ն 0,etx3Ն 0.

Solution en utilisant la solution de base réalisable

͑x1,x2,x3,s1,s2,s3͒ ϭ ͑0, 0, 0, 30, 60, 40͒

Le tableau de simplex initial pour ce problème est le suivant. (Remarque que1est une vari-
capable, plutôt qu'une variable d'inaction.)
De base
x1 x2 x3 s1 s2 s3 b Variables

4 1 1 1 0 0 30 s1 ← Départ
2 3 1 0 1 0 60 s2
1 2 3 0 0 1 40 s3

Ϫ3Ϫ2Ϫ1 0 0 0 0
↑
Entrée

De base
x1 x2 x3 s1 s2 s3 b Variables
1 1 1 15
1 4 4 4 0 0 2 x1
5 1
0 2 2 Ϫ12 1 0 45 s2 ← Départ
7 11 65
0 4 4 Ϫ14 0 1 2 s3
3 45
0 Ϫ54Ϫ14 4 0 0 2
↑
Entrée

De base
x1 x2 x3 s1 s2 s3 b Variables
1 3
1 0 5 10 Ϫ110 0 3 x1
1 2
0 1 5 Ϫ15 5 0 18 x2
12 1
0 0 5 10 Ϫ170 1 1 s3
1 1
0 0 0 2 2 0 45
Cela implique que la solution optimale est
͑x1,x2,x3,s1,s2,s3͒ ϭ ͑3, 18, 0, 0, 0, 1͒
et la valeur maximale de z est 45. (Cette solution satisfait l'équation donnée dans le con-
restrictions parce que4͑ 3͒ ϩ 1͑ 18͒ ϩ 1͑ 0͒ ϭ 30.͒
 SECTION9.3 LAMÉTHODESIMPLEXE:MAXIMISATION 503

Applications

E X A M P L E 4A Application Commerciale : Profit Maximum

Un fabricant produit trois types de pièces en plastique. Le temps nécessaire pour le moulage,
l'ébarbage et l'emballage sont indiqués dans le tableau 9.1. (Les temps sont donnés en heures par douzaine)
accessoires.)
TABLEAU9.1

Processus TypeA Type B Type C Temps total disponible

3
Moulage 1 2 2 12 000
2 2
Élagage 3 3 1 4 600
1 1 1
Emballage 2 3 2 2 400

Bénéfice 11 $ 16 $ 15 $ —

Combien de douzaines de chaque type d'appareil doivent être produites pour obtenir un profit maximum ?

SolutionLaisserx1,x2,etx3représenter le nombre de douzaines d'unités des types A, B et C, respectivement

la fonction objectif est donnée par
Bénéficeϭ Pϭ 11x1ϩ 16x2ϩ 15x3.
De plus, en utilisant les informations dans le tableau, nous construisons les contraintes suivantes.
2
3 x1ϩ 2x2ϩ 32 x3Յ 12 000
2 2 3
3 x1ϩ 3 x2ϩ 2 x3Յ 14 600
1 1 1
2 x1ϩ 3 x2ϩ 2 x3Յ 12 400
(Nous supposons également que x1Ն
0,x2Ն 0,etx3Ն 0.) Maintenant, appliquer la méthode du simplexe avec
la solution de base faisable
͑x1x2,x3,s1,s2,s3͒ ϭ ͑0, 0, 0, 12,000, 4,600, 2,400͒
nous obtenons les tableaux suivants.
De base
x1 x2 x3 s1 s2 s3 b Variables
3
1 2 2 1 0 0 12 000 s1 ← Départ
2 2
3 3 1 0 1 0 4 600 s2
1 1 1
2 3 2 0 0 1 2 400 s3

Ϫ11Ϫ16Ϫ15 0 0 0 0
↑
Entrer
504 CHAPITRE9 PROGRAMMATIONLINÉAIRE

De base
x1 x2 x3 s1 s2 s3 b Variables
1 3 1
2 1 4 2 0 0 6 000 x2
1 1 1
3 0 2 Ϫ3 1 0 600 s2
1 1
3 0 4 Ϫ16 0 1 400 s3 ← Départ
Ϫ3 0 -3 8 0 0 96 000
↑
Entrée

De base
x1 x2 x3 s1 s2 s3 b Variables
3 3
0 1 8 4 0 Ϫ32 5 400 x2
1
0 0 4 Ϫ16 1 Ϫ1 200 s2 ← Départ
3
1 0 4 Ϫ12 0 3 1 200 x1
13
0 0 Ϫ34 2 0 9 99 600
↑
Entrée

De base
x1 x2 x3 s1 s2 s3 b Variables

0 1 0 1 Ϫ32 0 5 100 x2
0 0 1 Ϫ23 4 Ϫ4 800 x3
1 0 0 0 Ϫ3 6 600 x1

0 0 0 6 3 6 100,200
À partir de ce tableau final du simplexe, nous voyons que le profit maximum est de 100 200 $, et ceci est
obtenue par les niveaux de production suivants.
TypeA: 600 douzaines d'unités

Type B : 5 100 douzaines d'unités

Type C : 800 douzaines d'unités

REMARQUE : Dans l'Exemple 4, notez que le deuxième tableau simplexe contient un « tie » pour le
entrée minimale dans la ligne du bas. (Les première et troisième entrées dans la ligne du bas sont
Ϫ3.) Bien que nous ayons choisi la première colonne pour représenter la variable de départ, nous aurions pu
choisi la troisième colonne. Essayez de retravailler le problème avec ce choix pour voir ce que vous obtenez
la même solution.

E X A M P L E 5A Application commerciale : Sélection des médias

Les alternatives publicitaires pour une entreprise incluent la télévision, la radio et les journaux.
les publicités. Les coûts et estimations pour la couverture du public sont donnés dans le tableau 9.2
 SECTION9.3 LAMÉTHODESIMPLEXE:MAXIMISATION 505

TABLEAU9.2

Télévision Journal Radio

Coût par publicité 2 000 $ $ 600 $ 300

Audience par annonce 100 000 40 000 18 000

Le journal local limite le nombre de publicités hebdomadaires d'une seule entreprise à

dix. De plus, afin d'équilibrer la publicité entre les trois types de médias, pas plus
plus de la moitié du nombre total de publicités devrait être diffusée à la radio, et au moins 10 %
devrait se dérouler à la télévision. Le budget publicitaire hebdomadaire est de 18 200 $. Combien de publicités
Les publicités devraient être diffusées dans chacun des trois types de médias pour maximiser l'audience totale ?

SolutionPour commencer, nous laissons x1,x2,etx3représenter le nombre de publicités à la télévision, dans les actualités
papier, et radio, respectivement. La fonction objective (à maximiser) est donc

zϭ 100,000x1ϩ 40 000x2ϩ 18 000x3 Fonction objective

où1Ն 0,x2Ն 0,etx3Ն 0. Les contraintes pour ce problème sont les suivantes.
2000x1ϩ 600x2ϩ 300x3Յ 18 200
2000x1ϩ 600x2ϩ 300x3Յ 10
2000x1ϩ 600x2ϩ 300x3 Յ 0,5͑x1ϩ x2ϩ x3͒
2000x1ϩ 600x2ϩ 300x3Ն 0,1͑x1ϩ x2ϩ x3͒

Une forme plus gérable de ce système de contraintes est la suivante.

}
20x1ϩ 6x2ϩ 3x3Յ 182
20x1ϩ 6x2ϩ 3x3Յ 110
Ϫx1Ϫ 6x2ϩ 3x3Յ 180 Contraintes
Ϫ9x1ϩ 6x2ϩ 3x3Յ 180

Ainsi, le tableau du simplexe initial est le suivant.

De base
x1 x2 x3 s1 s2 s3 s4 b Variables

20 6 3 1 0 0 0 182 s1 ← Départ
0 1 0 0 1 0 0 10 s2
Ϫ1 Ϫ1 1 0 0 1 0 0 s3
Ϫ9 1 1 0 0 0 1 0 s4

Ϫ100 000Ϫ40 000Ϫ18 000 0 0 0 0 0

↑
Entrer
506 CHAPITRE9 PROGRAMMATIONLINEAIRE

Maintenant, à ce tableau initial, nous appliquons la méthode du simplexe comme suit.

Basique
x1 x2 x3 s1 s2 s3 s4 b Variables
3 3 1 91
1 10 20 20 0 0 0 10 x1
0 1 0 0 1 0 0 10 s2 ← Départ
23 1 91
0 Ϫ170 20 20 0 1 0 10 s3
37 47 neuf 819
0 10 20 20 0 0 1 10 s4

0 Ϫ10 000Ϫ3,0005,000 0 0 0 910,000

↑
Entrée

De base
x1 x2 x3 s1 s2 s3 s4 b Variables
3 1 61
1 0 20 20 Ϫ130 0 0 10 x1
0 1 0 0 1 0 0 10 x2
23 1 7 161
0 0 20 20 10 1 0 10 s3 ← Départ
47 9 37 449
0 0 20 20 Ϫ 10 0 1 10 s4

0 0 Ϫ3 000 5,000 10,000 0 0 1 010 000

↑
Entrée

De base
x1 x2 x3 s1 s2 s3 s4 b Variables
1
1 0 0 23 Ϫ293 Ϫ233 0 4 x1
0 1 0 0 1 0 0 10 x2
1 14 20
0 0 1 23 23 23 0 14 x3
8 118 47
0 0 0 23 Ϫ 23 Ϫ 23 1 12 s4
118 000 272 000 60,000
0 0 0 23 23 23 0 1 052 000
À partir de ce tableau, nous voyons que l'audience hebdomadaire maximale pour un budget publicitaire de
18 200 $ est
zϭ 1 052 000 Audience hebdomadaire maximum

et cela se produit lorsque1ϭ 4,x2ϭ 10, etx3ϭ 14. Nous résumons les résultats ici.

Nombre de
Média Annonces Coût Public
Télévision 4 8 000 $ 400 000
Journal 10 6 000 $ 400 000
Radio 14 4 200 $ 252 000
Total 28 18 200 $ 1 052 000
 SECTION9.3 EXERCICES 507

SECTION 9.3❑ EXERCICES

Dans les exercices 1 à 4, écrivez le tableau du simplexe pour le problème linéaire donné. [Link] objective : [Link] objective :
problème de programmation. Vous n'avez pas besoin de résoudre le problème. (Dans chaque zϭ 5x1ϩ 2x2ϩ 8x3 zϭ x1Ϫ x2ϩ 2x3
le cas où la fonction objective doit être maximisée.) Contraintes : Contraintes :
[Link] objective : [Link] objective : 2x1Ϫ 4x2ϩ 3x3Յ 42 2x1ϩ 2x2Յ 8
zϭ x1ϩ 2x2 zϭ x1ϩ 3x2 2x1ϩ 3x2Ϫ 3x3Յ 42 2x1ϩ 2x3Յ 5
Contraintes : Contraintes : 6x1Ϫ 3x2ϩ 3x3Յ 42 x1,x2,x3Ն 0
2x1ϩ x2Յ 8 x1ϩ x2Յ 4 x1,x2,x3Ն 40
2x1ϩ x2Յ 5 x1Ϫ x2Յ 1 [Link] objective : [Link] objective :
2x1,x2Ն 0 x1,x2Ն 0 zϭ 4x1ϩ 5x2 zϭ x1ϩ 2x2
3. Fonction objectif : [Link] objective : Contraintes : Contraintes :
zϭ 2x1ϩ 3x2ϩ 4x3 zϭ 6x1Ϫ 9x2 3x1ϩ 7x2Յ 10 2x1ϩ 3x2Յ 15
Contraintes : Contraintes : 3x1ϩ 7x2Յ 42 2x1Ϫ 3x2Յ 12
x1ϩ 2x2ϩ x3Յ 12 2x1Ϫ 3x2Յ 26 x1,x2Ն 40 x1,x2Ն 10
x1ϩ 2x2ϩ x3Յ 18 2x1ϩ 3x2Յ 20 15. Fonction objectif : [Link] objectif :
x1,x2,x3Ն 10 x1,x2Ն 20 zϭ 3x1ϩ 4x2ϩ x3ϩ 7x4 zϭ x1
Contraintes : Contraintes :
Dans les exercices 5 à 8, expliquez pourquoi le problème de programmation linéaire est
8x1ϩ 3x2ϩ 4x3ϩ 5x4Յ 7 3x1ϩ 2x2Յ 60
pas sous forme standard comme indiqué.
2x1ϩ 6x2ϩ 4x3ϩ 5x4Յ 3 3x1ϩ 2x2Յ 28
5. (Minimiser) 6.(Maximiser)
2x1ϩ 4x2ϩ 5x3ϩ 2x4Յ 8 3x1ϩ 4x2Յ 48
Fonction objectif : Fonction objective :
x1,x2,x3,x4Ն 0 x1,x2Ն 40
zϭ x1ϩ x2 zϭ x1ϩ x2
Contraintes : Contraintes : [Link] objective : [Link] objective :
zϭ x1Ϫ x2ϩ x3 zϭ 2x1ϩ x2ϩ 3x3
x1ϩ 2x2Յ 4 2x1ϩ 2x2Յ Ϫ6
x1x2Ն 0 2x1Ϫ 2x2Յ Ϫ1 Contraintes : Contraintes :
x1,x2Ն Ϫ0 2x1ϩ 2x2Ϫ 3x3Յ 40 2x1ϩ x2ϩ 3x3Յ 59
2x1ϩ 2x2ϩ 3x3Յ 25 2x1ϩ x2ϩ 3x3Յ 75
7. (Maximiser) 8.(Maximiser)
2x1ϩ 2x2ϩ 3x3Յ 32 2x1ϩ x2ϩ 6x3Յ 54
Fonction objective : Fonction objectif :
x1,x2,x3Ն 30 x1,x2,x3Ն 50
zϭ x1ϩ x2 zϭ x1ϩ x2
Contraintes : Contraintes : [Link] objective :
zϭ x1ϩ 2x2Ϫ x4
2x1ϩ x2ϩ 3x3Յ 5 x1ϩ x2Ն 4
Contraintes :
2x1ϩ x2Ϫ 2x3Ն 1 2x1ϩ x2Ն 6
x1ϩ 2x2ϩ 3x3ϩ x4Յ 24
2x1ϩ x2ϩ 3x3Յ 0 x1,x2Ն 0
x1ϩ 3x2ϩ 7x3ϩ x4Յ 42
x1,x2,x3 Ն 0
x1,x2,x3,x4Ն 40
Dans les exercices 9 à 20, utilisez la méthode du simplexe pour résoudre le problème donné.
[Link] objective :
problème de programmation linéaire. (Dans chaque cas, la fonction objective
zϭ x1ϩ 2x2ϩ x3Ϫ x4
doit être maximisé.)
Contraintes :
[Link] objectif : [Link] objective :
2x1ϩ 3x2ϩ 3x3ϩ 4x4Յ 60
zϭ x1ϩ 2x2 zϭ x1ϩ x2
2x1ϩ 3x2ϩ 2x3ϩ 5x4Յ 50
Contraintes : Contraintes : 2x1ϩ 3x2ϩ 2x3ϩ 6x4Յ 72
x1ϩ 4x2Յ 18 3x1ϩ 2x2Յ 16 x1,x2,x3,x4Ն 70
x1ϩ 4x2Յ 12 3x1ϩ 2x2Յ 12
x1,x2Ն 10 x1,x2Ն 10
508 CHAPITRE9 PROGRAMMATIONLINÉAIRE

Un commerçant prévoit de vendre deux modèles d'ordinateurs personnels à 26. Supposons que dans l'exercice 25, le temps total disponible pour l'assemblage...
des coûts de 250 $ et 400 $, respectivement. Le modèle à 250 $ génère un bling
un bénéfice de 45 $ et le modèle de 400 $ génère un bénéfice de 50 $. Le 1500 heures, respectivement, et que le profit par unité est de 48 $
le marchand estime que la demande totale mensuelle ne sera pas (Modèle A), 50 $ (Modèle B), et 52 $ (Modèle C). Combien de
dépasser 250 unités. Trouvez le nombre d'unités de chaque modèle que de chaque type devrait être produit pour obtenir un profit maximum ?
doit être stocké afin de maximiser le profit. Supposons que [Link] entreprise a budgété un maximum de 600 000 $ pour la publicité.
le commerçant ne veut pas investir plus de 70 000 $ dans annonçant un certain produit au niveau national. Chaque minute de télévision
inventaire d'ordinateurs. (Voir l'exercice 21 dans la section 9.2.) le temps coûte 60 000 $ et chaque annonce d'une page dans un journal coûte
22. Un fruiticulteur dispose de 150 acres de terre pour élever deux. 15 000 $. Chaque publicité télévisée devrait être vue par 15
cultures, A et B. Il faut un jour pour tailler un hectare de culture A et un million de téléspectateurs, et chaque annonce dans le journal devrait être
deux jours pour couper un acre de culture B, et il y a 240 jours par vues par 3 millions de lecteurs. Les recherches de marché de l'entreprise
année disponible pour la taille. Il faut 0,3 jour pour récolter un acre de le département conseille à l'entreprise d'utiliser au maximum 90% de la
culture A et 0,1 jour pour récolter un acre de culture B, et il y en a 30 budget publicitaire pour les annonces télévisées. Comment devrait le
jours par an disponibles pour la cueillette. Trouvez le nombre d'acres le budget publicitaire doit être alloué pour maximiser l'audience totale
de chaque fruit qui devrait être planté pour maximiser le profit, comme- ence?
en supposant que le profit est de 140 $ par acre pour la culture A et 235 $ 28. Révisez l'exercice 27 en supposant que chaque journal d'une page
par acre pour B. (Voir l'exercice 22 dans la section 9.2.) les frais de publicité coûtent 30 000 dollars.
[Link] cultivateur a 50 acres de terre pour laquelle elle prévoit de cultiver [Link] investisseur a jusqu'à 250 000 $ à investir dans trois types de...
trois cultures. Il en coûte 200 $ pour produire un acre de carottes et vêtements. Le type A paie 8 % par an et a un facteur de risque de
le profit est de 60 $ par acre. Il en coûte 80 $ pour produire une acre de Le type B paie 10 % par an et a un facteur de risque de 0,06.
le céleri et le profit est de 20 $ par acre. Enfin, cela coûte 140 $ à Le type C paie 14 % par an et a un facteur de risque de 0,10. Pour
produire un acre de laitue et le bénéfice est de 30 $ par acre. Utiliser avoir un portefeuille bien équilibré, l'investisseur impose le fol-
la méthode du simplexe pour trouver le nombre d'acres de chaque culture Les conditions suivantes. Le facteur de risque moyen ne devrait pas être
elle devrait planter afin de maximiser son profit. Supposons que supérieur à 0,05. De plus, au moins un quart du total
son coût ne peut pas dépasser 10 000 $. le portefeuille doit être alloué aux investissements de type A et au moins
Une entreprise de jus de fruits fabrique deux boissons spéciales en les mélangeant. un quart du portefeuille doit être alloué à l'investissement de type B
jus de pomme et de ananas. La première boisson utilise 30 % de pomme combien devrait être attribué à chaque type d'investissement
jus et 70 % d'ananas, tandis que la deuxième boisson utilise 60 % ment pour obtenir un rendement maximal ?
pomme et 40 % d'ananas. Il y a 1000 litres de pomme et 30. Un investisseur a jusqu'à 450 000 $ à investir dans trois types de
1500 litres de jus d'ananas disponibles. Si le bénéfice pour le les investissements. Le type A paie 6% par an et a un facteur de risque
la première boisson est à 0,60 $ le litre et celle de la deuxième boisson est de 0. Le type B paie 10 % par an et a un facteur de risque de 0,06.
0,50 $, utilisez la méthode du simplexe pour trouver le nombre de litres de Le type C paie 12 % par an et a un facteur de risque de 0,08. Pour
chaque boisson qui devrait être produite pour maximiser le avoir un portefeuille bien équilibré, l'investisseur impose le
profit. les conditions suivantes. Le facteur de risque moyen ne devrait pas être
[Link] fabricant produit trois modèles de bicycles. Le temps supérieur à 0,05. De plus, au moins la moitié du total
(en heures) requises pour l'assemblage, la peinture et l'emballage le portefeuille doit être alloué aux investissements de type A et au moins
chaque modèle est comme suit. un quart du portefeuille doit être attribué aux investissements de Type B
combinaisons. Combien devrait être alloué à chaque type de
Modèle A Modèle B Modèle C investissement pour obtenir un rendement maximum ?
[Link] entreprise de comptabilité dispose de 900 heures de temps de personnel et de 100 heures
Assemblage 2 2.5 3
de la révision du temps disponible chaque semaine. L'entreprise facture
Peinture 1,5 2 1 $2000 pour un audit et $300 pour une déclaration fiscale. Chaque audit
nécessite 100 heures de temps du personnel et 10 heures de temps de révision,
Emballage 1 0,75 1,25
et chaque déclaration de revenus nécessite 12,5 heures de temps de personnel et 2,5
Le temps total disponible pour l'assemblage, la peinture et l'emballage heures de temps de révision. Quel nombre d'audits et de déclarations fiscales
ing est de 4006 heures, 2495 heures et 1500 heures, respectivement. rapportera un revenu maximal ?
Le bénéfice par unité pour chaque modèle est de 45 $ (Modèle A), 50 $
(Modèle B), et 55 $ (Modèle C). Combien de chaque type
devrait être produit pour obtenir un profit maximum ?
 SECTION9.4 LAMÉTHODESIMPLEXE:MINIMISATION 509

32. Le cabinet comptable de l'exercice 31 augmente son tarif pour un 35.(Maximiser) 36.(Maximiser)
audit à 2500 $. Quel nombre d'audits et de déclarations fiscales sera Fonction objective : Fonction objectif :
générer un chiffre d'affaires maximum ?
zϭ 2,5x1ϩ x2 zϭ x1ϩ 12x2
Dans la méthode du simplexe, il peut arriver que lors de la sélection du départ Contraintes : Contraintes :
tous les ratios calculés sont négatifs. Cela indique un- 3x1ϩ 5x2Յ 15 2x1ϩ 3x2Յ 20
solution bornée. Démontrer cela dans les Exercices 33 et 34. 5x1ϩ 2x2Յ 10 2x1ϩ 3x2Յ 35
x1,x2Ն 10 x1,x2Ն 30
33.(Maximiser) 34. (Maximiser)
C [Link] un ordinateur pour maximiser la fonction objective
Fonction objectif : Fonction objective :
zϭ x1ϩ 2x2 zϭ x1ϩ 3x2 zϭ 2x1ϩ 7x2ϩ 6x3ϩ 4x4
Contraintes : Contraintes : sous réserve des contraintes
Ϫx1Ϫ 3x2Յ 1 Ϫx1ϩ x2Յ 20 1,2x1ϩ 0,7x2ϩ 0,83x3ϩ 0,5x4Յ 65
Ϫx1ϩ 2x2Յ 4 Ϫ2x1ϩ x2Յ 50 1,2x1ϩ 0,7x2ϩ 0,83x3ϩ 1,2x4Յ 96
x1,x2Ն 0 x1,x2Ն 50 0.5x1ϩ 0.7x2ϩ 01.2x3ϩ 0,4x4Յ 80

Si la méthode du simplexe prend fin et qu'une ou plusieurs variables ne sont pas dans
où1,x2,x3,x4Ն 0.
C [Link] un ordinateur pour maximiser la fonction objective
la base finale a des entrées de la ligne du bas égales à zéro, apportant cela
Les variables dans la base détermineront d'autres solutions optimales. zϭ 1,2x1ϩ x2ϩ x3ϩ x4
Démontrez cela dans les exercices 35 et 36. sous le même ensemble de contraintes données dans l'Exercice 37.

9.4 LA MÉTHODE SIMPLEX : MINIMISATION

Dans la section 9.3, nous avons appliqué la méthode du simplexe uniquement aux problèmes de programmation linéaire dans
forme standard où la fonction objective devait être maximisée. Dans cette section, nous étendons
cette procédure pour des problèmes de programmation linéaire dans lesquels la fonction objective est de minimiser
imiqué.
Un problème de minimisation est en forme standard si la fonction objective wϭ c1x1ϩ c2x2
ϩ . . . ϩ cn xndoit être minimisé, sous réserve des contraintes

un11x1ϩ a12x2ϩ . . . ϩ a1nxnՆ b1

un21x1ϩ a22x2ϩ . . . ϩ a2nxnՆ b2

..
.
unm1x1ϩ am2x2ϩ . . . ϩ amnxnՆ bm

oùjeՆ 0 andbjeՆ 0. La procédure de base utilisée pour résoudre un tel problème est de le convertir
à un problème de maximisation sous forme standard, puis appliquer la méthode du simplexe comme dis-
prévues à la section 9.3.
Dans l'Exemple 5 de la Section 9.2, nous avons utilisé des méthodes géométriques pour résoudre ce qui suit
problème de minimisation.