(B) SIMPLEX METHOD

Lors de la dernière discussion, nous avons utilisé la méthode graphique pour résoudre des problèmes de programmation linéaire, mais

l'approche graphique ne fonctionnera pas pour les problèmes ayant plus de deux variables. Dans la vie réelle
Dans certaines situations, les problèmes de programmation linéaire se composent littéralement de milliers de variables et sont résolus
par des ordinateurs. Nous pouvons résoudre ces problèmes algébriquement, mais cela ne sera pas très efficace. Donc
nous avons besoin d'une méthode qui possède un algorithme systématique et qui peut être programmé pour un ordinateur.
la méthode doit être suffisamment efficace pour que nous n'ayons pas à évaluer la fonction objective à chaque fois
point de coin. Nous avons justement une telle méthode, et elle s'appelle la méthode du simplexe.
La méthode du simplexe pour la programmation linéaire, développée par Dantzig (1914-2005) au milieu de
le vingtième siècle (1963) est la première méthode pratiquement et économiquement viable pour résoudre
systèmes d'inégalités linéaires. Cela a conduit aux développements de la programmation linéaire (PL), une
branche des mathématiques développée au vingtième siècle comme une extension de l'algèbre linéaire à
solve systems of linear inequalities.
Le développement de la programmation linéaire est un événement marquant dans l'histoire des mathématiques et de ses applications.
cela a amélioré notre capacité à résoudre des systèmes généraux de contraintes linéaires (y compris les équations linéaires,
inégalités) à un état d'achèvement. Depuis des applications plus réalistes de la programmation linéaire
impliquer de nombreuses variables et de nombreuses contraintes, il est nécessaire d'avoir une méthode autre que le
méthode graphique. Une méthode fréquemment utilisée est la méthode du simplexe.
L'« algorithme du simplex » est une procédure itérative pour trouver, de manière systématique, l'optimal
solution à un problème de programmation linéaire. Le fonctionnement de la méthode du simplex se déroule par
préparer une série de tableaux appelés tableaux simplex, le dernier indiquant la solution optimale
du problème donné. Graphiquement, nous avons trouvé la procédure comme cherchant différents points de coins de
la région réalisable. La solution trouvée à chaque itération de la méthode du simplexe représente une telle
points de coin. Cependant, tous les points de coin ne sont pas examinés. La recherche choisit uniquement un sous-ensemble de
ces points de coin, en sélectionnant un nouveau si et seulement si la fonction objective est au moins aussi bonne que
le point d'angle actuel. La méthode est assez simple et la première étape nécessite la détermination
de solution de base faisable. Ensuite, avec l'aide d'un nombre limité d'étapes, la solution optimale
peut être déterminé.
Supposons qu'il n'y ait pas de fonction objective à optimiser, et seulement une solution faisable d'un système de
des contraintes linéaires doit être trouvé. Quand il y a des contraintes d'inégalité dans le système, le seul
Une méthode pratique pour trouver une solution réalisable est de résoudre une formulation de programmation linéaire.
comme un problème de programmation linéaire de Phase I. Dantzig a développé cette formulation de Phase I comme
partie de la méthode du simplexe pour les PLs qu'il a développée au milieu du XXe siècle.

Remarque. L'ensemble des points d'angle de la région faisable correspond à l'ensemble des solutions de base faisables.
solutions. En d'autres termes, les points d'angle sont des solutions réalisables de base, et vice versa.

Remarque. Les solutions réalisables sont infinies en nombre (car il existe un nombre infini de points dans
la région réalisable, OABC). Il est donc plutôt impossible de chercher la solution optimale
parmi toutes les solutions réalisables. Mais heureusement, le nombre de solutions réalisables de base est

1
fini en nombres (qui correspondent aux points extrêmes O, A, B, C, respectivement). Même
Alors, un grand travail est nécessaire pour trouver tous les BFS et sélectionner celui qui optimise le
fonction objective.
La méthode du simplexe fournit un algorithme systématique qui consiste à passer d'une BFS à l'autre.
(un sommet) à un autre d'une manière prescrite afin que la valeur de la fonction objective soit
amélioré. Cette procédure de saut d'un sommet à l'autre est répétée. Si la fonction objective
s'améliore à chaque saut, alors aucune base ne peut jamais se répéter et il n'est pas nécessaire de revenir au sommet
déjà couvert. Puisque le nombre de sommets est fini, le processus doit conduire à l'optimal
sommet en un nombre fini d'étapes.

C
B

O Un

CONTRAINTES OBLIGATOIRES ET NON OBLIGATOIRES

Une fois la solution optimale à un PLP obtenue, nous pouvons classer les contraintes comme étant
obligatoire ou non obligatoire. Une contrainte est qualifiée d'obligatoire si le côté gauche (C.G.) et le côté droit (C.D.) de celle-ci sont égaux.

lorsque les valeurs optimales des variables de décision sont substituées dans la contrainte. D'autre part
main, si la substitution des variables de décision ne conduit pas à l'égalité entre la gauche et
Les côtés droits de la contrainte, il est dit qu'ils ne sont pas contraignants.
Par exemple, considérez le PLP comme
Max Z = 40x + 35y
≤ 60
Sous réserve de 2x + 3y
4x + 3y 96≤
Et, x, y 0 ≥
Les valeurs optimales des variables de décision sont : x = 18 et y = 8. En substituant ces valeurs dans le
deux contraintes que nous obtenons

2x + 3y ou 2 x 18 + 3 x 8 = 60 = M.P.D., et
4x + 3y ou 4 x 18 + 3 x 8 = 96 = M.P.D.
Ainsi, les deux contraintes sont de nature contraignante.

D'autre part, si nous considérons l'exemple suivant comme

Min Z = 40x + 24y

2
 ≥ 4800
Sous réserve de 20x + 50y
≥
80x + 50y 7200
Et, x, y 0 ≥
Les valeurs optimales des variables de décision sont : x = 0 et y = 144. En substituant ces valeurs dans le
deux contraintes que nous obtenons

20x + 50y ou 20 x 0 + 50 x 144 = 7200≠4800 (R.H.S), et

80x + 50y ou 80 x 0 + 50 x 144 = 7200 = M.P.D.
En conséquence, la première contrainte est non contraignante et la deuxième est contraignante.

CONTRAINTE(S) REDONDANTE(S)
Comme nous l'avons observé, le tracé de chacune des contraintes sur le graphique sert à déterminer le
région réalisable d'un problème donné. Si et quand une contrainte, lorsqu'elle est tracée, ne fait pas partie de
la frontière marquant la région réalisable du problème, on dit qu'elle est redondante. L'inclusion
L'exclusion d'une contrainte redondante n'affecte manifestement pas la solution optimale à la.
problème. En d'autres termes, une contrainte, qui n'affecte pas la région réalisable, est appelée une
contrainte redondante. Une telle contrainte n'est pas nécessaire à la solution du problème. Elle peut
il convient donc de l'omettre lors de la formulation du problème. Cela permettra d'économiser du temps de calcul.

QUELQUES DÉFINITIONS IMPORTANTES

Voici quelques termes importants pour la PPL standard qui sont nécessaires à comprendre
discussion supplémentaire.
1. Solution de base (SB): Pour un système de m équations linéaires simultanées dans n inconnues (n
> m), une solution obtenue en fixant n-m variables à zéro et en résolvant pour
variables restantes, à condition que le déterminant des coefficients de ces variables
est non nul est appelé une solution de base. De telles variables (bien sûr, certaines d'entre elles peuvent être
zero) are calledbasic variablesand remainingn-mzero valued variables whose values
n'apparaissant pas dans la solution sont appelées variables non de base.
Le nombre de solutions de base ainsi obtenu sera au maximum Cnm= n! / ((n-m)! m!)
quel est le nombre de combinaisons de n choses prises m à la fois.
[Link] : L'ensemble des variables de base qui ne sont pas limitées à zéro dans la solution de base et
sont listés dans la colonne de solution.
[Link] de base faisable (BFS) : une solution de base faisable est une solution de base qui est également
satisfait les restrictions de non-négativité, c'est-à-dire que toutes les variables de base sont non négatives.
Les solutions de base faisables sont de deux types :
(a)Solution de base faisable non dégénérée : Une solution de base faisable non dégénérée est la base faisable.
solution qui a exactement m positif xje(i= 1, 2, … , m). En d'autres termes, tous les mbasiques
les variables sont positives, et les autres variables seront toutes nulles.
(b)BFS dégénéré : Une solution de base réalisable est appelée dégénérée, si une ou plusieurs bases
les variables sont à valeur nulle.

3
 L'importance du BFS découle du fait que pour tout PPL, il existe un extrême unique.
point de la région faisable correspondant à chaque BFS et aussi il y a au moins un BFS
correspondant à chaque point extrême de la région faisable.
[Link] de base réalisable optimale : une solution de base réalisable est dite optimale si elle
optimise également (maximise ou minimise) la fonction objective.
[Link] sans bornes : Si la valeur de la fonction objective z peut être augmentée ou
diminé indéfiniment, de telles solutions sont appelées solutions non bornées. Si le faisable
la région (zone ombragée) est ouverte, c'est-à-dire qu'elle n'a pas de limite confiné. Alors, cela peut être
il est possible que le PPL n'ait pas de solution finie, et par conséquent, que la solution soit illimitée.
[Link]ération : C'est une séquence d'étapes prises pour passer d'une solution réalisable de base à
une autre solution faisable de base.
[Link]:It is a row in the simplex tableau which contains the coefficients of the variables
dans la fonction objective.
[Link]:It is a row in the simplex tableau whose elements represent the increase
diminution de la valeur de la fonction objective si une unité de la jème variable est apportée
dans la solution.
[Link]- CjC'est une ligne dont les éléments représentent la contribution nette par unité du jème.
variable dans la fonction objective, si la variable est intégrée dans la nouvelle solution de base.
[Link] column:It is the column with the most negative (positive)Zj- Cjet cela indique
quelle variable entrera dans la prochaine solution dans un cas de maximisation (minimisation).
[Link] clé : C'est la ligne avec la plus petite valeur positive du ratio de remplacement de l'
contraindre les rangées. Le ratio de remplacement est obtenu en divisant les éléments dans la solution
colonne par les éléments correspondants dans la colonne clé. La ligne clé indique le
variable qui laissera la base pour faire place à une nouvelle variable entrant.
12.Élément clé (pivot) : C'est l'élément à l'intersection de la ligne clé et de la colonne clé.
Remarque. Sauf indication contraire, une solution signifie une solution réalisable. Cependant, une optimale
solution to a linear programming problem implies thatzhas a finite maximum or finite
valeur minimale.
En plus de ces termes dans un tableau simplifié, nous avons les termes suivants qui sont nécessaires.
pour adapter un problème de programmation linéaire à être résolu par la méthode du simplexe.
≤ ou égal à ( ) en
. Variable d'écart : Une variable utilisée pour convertir une contrainte de type inférieur
contrainte d'égalité. Elle est ajoutée au côté gauche de la contrainte. En économique
La terminologie, la variable d'écart représente la capacité inutilisée.
≥ ou égale à ( )
. Variable de surplus : Une variable utilisée pour convertir une contrainte de supérieure
dans la contrainte d'égalité. Il est soustrait du côté gauche de la contrainte.
. Variable artificielle : C'est une variable ajoutée à égal (=) et supérieur ou égal à ( ) ≥
contrainte de type. Ces variables sont utilisées pour obtenir une solution initiale faisable dans le simplexe
méthode. Ces variables sont réduites à zéro à l'optimalité. Les variables artificielles sont temporaires
variables de slack qui sont utilisées à des fins de calcul, et qui sont ensuite supprimées.
Les variables ci-dessus sont utilisées pour convertir les inégalités en équations d'égalité.

4
FORME STANDARD D'UN PPL
L'utilisation de la méthode du simplexe pour résoudre un problème de programmation linéaire nécessite que le problème soit

converti en sa forme standard. La forme standard du problème LP doit avoir les éléments suivants
characteristics:
[Link] les contraintes doivent être converties en équations, sauf pour la non-négativité.
les restrictions qui demeurent comme des inégalités (≥ 0). Les contraintes de type ‘≤’ peuvent être transformées en
type d'égalité, en ajoutant des variables connues sous le nom de variables d'écart. Le type '≥'
les contraintes peuvent être transformées en égalités en soustrayant des variables appelées surplus
variables.
Considérez les équations,
Exemple : 11ax1+ un12x2≤ b1
un21x1+ un22x2≥ b 2
En convertissant ces équations en égalité, nous obtenons :
un11x1+ un12x2+ xs1= b1
a21x1+ un22x2x−s2= b2
Ici xs2serait la variable d'écart et xs2serait une variable excédentaire.
Dans chaque équation, soit une seule variable d'écart serait ajoutée, soit un seul surplus.
la variable serait soustraite.
Nous assignons un coût nul à chacune des variables de marge et de surplus.
2.L'élément du côté droit de chaque contrainte doit être rendu non négatif (si ce n'est pas le cas).
le côté droit peut toujours être rendu positif en multipliant les deux côtés de l'équation résultante
par −1 quand c'est nécessaire.
Par exemple, considérons la contrainte comme 3x - 4y− ≥ 4 qui peut être écrite sous la forme de
équation 3x – 4y – w = 4 en −introduisant la variable de surplus w ≥ 0. Encore une fois, en multipliant
des deux côtés par−1, nous obtenons
− 3x + 4y + w = 4 qui est l'équation de contrainte dans la forme standard
forme.
[Link] les variables doivent avoir des valeurs non négatives. Parfois, un problème peut avoir un
variable qui est 'sans restriction en signe' ou 'libre', de sorte qu'elle peut assumer des valeurs négatives comme
bien que non négatif. Cette situation est gérée en traitant une telle variable comme le
différence de deux variables qui sont toutes deux non négatives, car une telle différence peut
soyez positif, négatif ou zéro.
Considérez l'exemple suivant :

Maximiser Z = 5x + 7y−2w
Sous 2x + 5y + 3w ≤ 80
5x + 2y - 2w ≤ 30
y + 6w ≤ 42
5
 Et, x, y ≥ 0, w est sans restriction de signe
Puisque w n'est pas restreint par le signe, nous pouvons le représenter par une différence de deux non-négatifs.
variables, disonsw ' et w' . Substituer w= danswce' w ' précède et en simplifiant, nous
–qui
obtenir
Maximiser Z = 5x + 7y - 2 w ' + 2 w'
Sous réserve de 2x + 5y +w3 ' - 3 w' ≤ 80
5x + 2y – 2 w+ '2 w' ≤30
y + 6 w ' - 6 w' ≤ 42
Et, x, y, , w ' w '' ≥ 0
Après l'obtention de la solution, nous substituerons la différence des valeurs de w ' et
w' comme la valeur de w.

CONDITIONS D'APPLICATIONS DE LA MÉTHODE SIMPLEX

1. Le côté droit de chacune des contraintes bjedoit être non négatif. (Voir point 2 ci-dessus)
2. Chacune des variables de décision du problème doit être non négative. (Voir point 3
ci-dessus

PROCÉDURE DE RÉSOLUTION D'UN PROBLÈME PAR LA MÉTHODE SIMPLEX

La méthode de résolution d'un problème par la méthode du simplexe implique les étapes suivantes :-
Étape 1 : Formulation du PPL.
Étape 2 : Convertir les contraintes en forme d'égalité en utilisant les règles données dans la forme standard d'un
LPP.
Étape 3 : Construire le tableau simplexe de départ.
Étape 4. Mettre en place la Solution de Base Initiale Faisable. La quatrième étape consiste à trouver la base faisable.
solution. Pour cela, nous pouvons prendre les m variables d'écart ou les variables artificielles s.1, s2, …, smou un1, un2,
… , unmou un mélange de celles-ci (certaines variables de relâche et certaines variables artificielles) comme les variables de base. Nous

peuvent déterminer leurs valeurs directement, car les variables restantes x1, x2, …, xnne sont pas basiques
et donc chacun a la valeur zéro. Ainsi s1=b1, s2=b2, …, sm=bmou (a1=b1, un2=b2, …., am=bm)
ou (s1= b1, un1= b2, …, am= bmou toute autre combinaison de ce type).
Chacun des slack (s1, s2, …, sm)ou excédent (sl1, sl2, …, slm) la variable aura un coefficient zéro dans
la fonction objectif, tandis que chacun des artificiels (a1, un2, …, unm) les variables auront un
coefficient +M en cas de maximisation ou -M en cas de minimisation dans la fonction objective,
M étant un très grand nombre. C'est juste pour les tenir à l'écart de la solution finale.
La méthode du simplexe procède ensuite à résoudre le problème ci-dessus en concevant et en redéveloppant
des solutions réalisables de base de mieux en mieux jusqu'à l'obtention d'une solution optimale.
Step 5. To set up the Initial Simplex [Link] set up the simplex table, the next step is to
localiser la matrice d'identité et les variables qui y sont impliquées. L'identité contient tous des zéros sauf
les éléments diagonaux comme 1. L'identité doit avoir cette forme carrée avec tous les zéros et une diagonale
de (plus) uns. La taille de cette matrice carrée serait déterminée par le nombre de contraintes
dans le système. Localiser l'identité est d'une importance primordiale car la solution est identifiée dans

6
Référence à cela. Les variables correspondant à la matrice identité sont appelées variables de base et
les restantes sont appelées variables non de base.
Pour des raisons d'efficacité computationnelle et de simplicité, l'algorithme du simplexe est généralement exécuté dans un
tableau appelé asimplex. Les variables de base initiales sont les variables de slack ou artificielles
associé à chaque contrainte (toutes les variables de décision sont nulles). Le tableau simplex initial est
montré dans le Tableau 1.
L'interprétation des données du tableau 1 est donnée après le tableau. D'autres tableaux simplex auront
interprétations similaires.
Tableau Simplex 1
Table 1 c1c2… cn 0 0 … 0 M ou 0 ou M ou ... 0 ou M
−M −M ou − M
xB cB x1x2… xn sl1sl3… slja1 s2ou un2 … smou unmbje
a1 0 ou M a11un12… un1n -1 0 ... 0 1 0 … 0 b1
−
ou M
s2ou 0 or M a21un22… un2n 0 0 … 00 1 … 0 b2
un2 −
or M
a3 0 ou M a31a32… un3n0-1 … 0 0 0 … 0 b
−
ou M
M M M M M M M M M M M M M M M
unj 0 ou M aj1aj2… unjn… -1 0 0 0 0 ... 0
ou − M
M M M M M M M M M M M M M M M
sm 0 ou M am1am2… unmn 0 0 … 00 0 … 1 bm
ou ou − M
am
ZjC−j -c1-c2… -cn 0 0 … 0 −M 0 ou−M … 0 ou −
ou M ou M M ou M

a. Dans la première ligne, nous écrivons les coefficients des variables dans la fonction objectif. Ces
les valeurs resteront les mêmes dans le tableau suivant.
[Link] deuxième ligne montre les principaux titres de colonne. Ces titres restent les mêmes dans
le tableau suivant et appliquer aux valeurs énumérées dans les premières lignes.
[Link] la première colonne intitulée "x"B(également appelé colonne de mélange de produits) sont énumérés les éléments de base
variables. Ainsi, dans le tableau initial du simplexe, ces variables sont les variables d'amortissement ou
variables artificielles.
[Link] la deuxième colonne étiquetée « cBNous écrivons les coefficients (dans la fonction objective)
des variables de base incluses dans le tableau spécifique. Ainsi, les coefficients de marge ou
les variables artificielles qui sont incluses dans le premier tableau sont écrites dans le cBcolonne.
[Link] matrice de base (sous des variables non basiques) dans le tableau simplexe initial se compose de
coefficients des variables de décision dans l'ensemble des contraintes.

7
 f. La matrice d'identité (sous les variables d'engagement ou artificielles) dans le tableau simplexe initial
représente les coefficients des variables de réserve ou artificielles dans l'ensemble des contraintes. Chaque
le tableau simplex contient une matrice d'identité sous les variables de base.
[Link] la colonne intitulée "bje (également appelé colonne quantité), nous écrivons les valeurs de solution de
les variables de base. Puisque les valeurs de notre solution de base réalisable initiale sont représentées
par les côtés droits des contraintes, ces valeurs sont répertoriées dans le simplexe initial
table.
[Link] obtenir une entrée pour le Zj, nous multiplions les entrées dans les colonnes respectives par le
les entrées correspondantes de Cjcolonne et ajouter les produits. Le Zj les entrées seront toutes égales
à zéro dans le tableau simple initial. L'autre Zjles entrées représentent la diminution de le
fonction objective qui en résulterait si l'une des variables n'était pas incluse dans la solution
ont été intégrés à la solution.
[Link] dernière ligne intitulée « Zj – Cjappelée la ligne d'index ou la ligne d'évaluation nette, et est utilisée pour
déterminez si la solution actuelle est optimale ou non. Le calcul de Zj– Cjrangée
impliquant simplement de soustraire chaque Cjvaleur du Z correspondantjvaleur pour cela
colonne. Nous observons que Zj– Cjles valeurs sont significatives uniquement pour les variables non basiques.
C'est parce qu'une variable de base Zj= (valeur de jthvariable d'écart ou variable artificielle c'est-à-dire 1) x
Cj= Cj pour que Zj– Cj= Cj– Cj= 0.
Les chiffres dans le ZjCjla rangée représente la contribution nette à la fonction objectif que
résultats en introduisant une unité de chacun des variables de colonne respectives. Une valeur positive indique
qu'une plus grande contribution peut être faite en intégrant la variable de cette colonne dans la solution.
Une valeur négative indique le montant par lequel la contribution diminuerait si une unité de
La variable pour cette colonne a été intégrée à la solution.
Étape 6. Tester la solution pour optimalité. Examiner les entrées Zj– Cjligne. En cas de maximisation
problème, si toutes les entrées dans Zj– Cjles lignes sont positives ou nulles, la solution optimale a été
obtenu, sinon la présence de toute entrée négative indique que la solution peut encore être
amélioré.
Et, en cas de problème de minimisation, si toutes les entrées dans Zj– Cjla ligne est négative ou nulle, le
une solution optimale a été obtenue, sinon la présence de toute entrée positive indique que
la solution peut être encore améliorée.
Étape 7. Révision du tableau simplex actuel. À chaque itération, la méthode du simplex passe de
le BFS actuel par un meilleur BFS. Cela implique de remplacer une variable de base actuelle (appelée le
variable sortante) par une nouvelle variable non basique (appelée variable entrante).
Déterminer la variable d'entrée. Dans le cas d'un problème de maximisation, la colonne qui a le plus
entrée négative dans le Zj– Cjla ligne est appelée la colonne clé (ou colonne pivot) (indiqué par ). Cela
↑
localise la variable à introduire dans la base. Ainsi, la variable non basique qui sera
remplacer une variable de base est celle qui se trouve dans la colonne clé.
Et, en cas de problème de minimisation, la colonne avec l'entrée la plus positive dans le Zj– Cjrang
s'appelle la colonne clé (ou pivot) (indiquée par ).↑ Cela localise la variable à introduire

8
dans la base. Ainsi, la variable non basique qui remplacera une variable basique est celle qui se trouve dans
la colonne clé.
Déterminer la variable sortante. La décision de laquelle des variables de base remplacer est prise par
en se concentrant sur la colonne clé et la colonne de solution. Divisez chaque entrée de la colonne de solution
par l'entrée positive correspondante dans la colonne clé. Ces quotients sont inscrits dans le dernier
colonne étiquetée "Ratio" du tableau simplex à remplacer. La ligne qui correspond à la
← départ
le plus petit quotient non négatif est appelé la ligne clé (ou pivot) (indiqué par ). Le
la variable est la variable correspondante dans cette ligne. Le nombre qui se trouve à l'intersection de la
La colonne clé et la ligne clé d'un tableau donné sont appelées le nombre clé (ou pivot). Nous plaçons un
entourez ce nombre.
Dérivation d'une nouvelle table. Après avoir identifié la variable d'entrée et la variable de sortie, il ne reste plus que
pour trouver le nouveau BPA en construisant un nouveau tableau de simplex à partir de l'actuel. Ceci est
accompli en utilisant des opérations élémentaires sur les lignes de sorte que le nombre clé soit réduit à 1 et
d'autres entrées dans la colonne clé sont transformées en zéro. Pour changer la ligne clé afin que la clé
le numéro est 1. Nous pouvons utiliser la formule suivante :
Nouvelle ligne de clé = ancienne ligne de clé / numéro de clé (élément pivot)
Pour modifier les lignes non-clés, nous pouvons utiliser la formule :
Nouvelles lignes non clés = anciennes lignes non clés - (entrée de la colonne clé) x nouvelle ligne clé, où colonne clé
l'entrée est l'entrée dans cette ligne c'est-à-dire dans la colonne clé.
Étape 8. Tester l'optimalité. Encore une fois, nous appliquons le test d'optimalité pour déterminer si le nouveau
la solution est optimale. En cas de problème de maximisation, s'il n'y a pas de Z négatifj– Cjentrées, nous
avoir une solution optimale et avoir terminé le problème. Sinon, revenez à l'étape 7.
De même, en cas de problème de minimisation, s'il n'y a pas de Z positif.j - Cjentrées, nous avons un
solution optimale et avoir terminé le problème. Sinon, revenez à l'étape 7.

Remarque
Le vecteur qui est retiré de la base à une itération dans la méthode du simplexe ne peut pas
réintégrer immédiatement la base lors de la prochaine itération.
•L'existence d'une variable d'écart dans le tableau final du simplexe indique que la ressource a
n'a pas été pleinement utilisé. L'absence de variables d'inactivité indique une utilisation complète de
les ressources existantes. Ainsi, si l'entreprise prévoit d'élargir ses ressources, elle peut chercher à
uniquement les ressources qui sont entièrement utilisées. Pour évaluer la valeur des ressources supplémentaires,
nous pouvons considérer quelle différence cela ferait si nous pouvions fournir une unité supplémentaire de chaque
des ressources entièrement utilisées. L'augmentation du bénéfice en raison de l'unité supplémentaire de
la ressource est considérée comme la valeur marginale de la ressource et est appelée l'ombre
prix de cette ressource. Le prix d'ombre pour chaque ressource est affiché dans le Zj– Cjligne de
le tableau final du simplex sous la variable d'écart correspondante.
•S'il n'y a pas de x1, x2variables dans le tableau d'itération final, les valeurs de x1et x2sont zéro.

Q1. Résoudre le problème suivant en utilisant la méthode du simplexe.

9
 Maximiser Z = 40x + 35y (Profit)
Sous réserve de 2x + 3y ≤ 60 (Contrainte de Matière Première)
4x + 3y ≤ 96 (Contrainte des heures de travail)
Et x, y ≥ 0 (Réponse : x = 18, y = 8 et Z = 1000)

LA M-TECHNIQUE DE CHARNES POUR LES PROBLÈMES AVEC SURPLUS ET

VARIABLES ARTIFICIELLES
Jusqu'à présent, nous avons vu les contraintes de programmation linéaire de type inférieur. Nous rencontrons
problèmes avec les types 'plus grand que' et 'égal à' également. Chacun de ces types doit être converti en
équations. Dans le cas de type « supérieur à », les contraintes sont réécrites avec un excès négatif.
variable et en ajoutant une variable artificielle. Les variables artificielles sont simplement utilisées pour trouver le
solutions de base initiales et sont par la suite éliminées. En cas de contrainte 'égal à', il suffit d'ajouter
la variable artificielle à la contrainte.
Les coefficients des variables artificielles a1, a2,….. sont représentés par une valeur très élevée –M ou M,
et donc la méthode est connue sous le nom de méthode BIG-M.
Une variable artificielle est ajoutée à toute contrainte d'égalité afin d'introduire une colonne pour le
matrice de base standard. Une variable artificielle est introduite uniquement lorsqu'il y a un besoin. Si le
la colonne correspondante de la base standard est déjà disponible par toute variable originale, nous avons besoin
ne pas introduire la variable artificielle correspondante. La valeur de la variable artificielle est zéro, si
le LPP donné est cohérent. Par conséquent, si le LPP est cohérent, la variable artificielle doit soit
être non basique ou apparaître à un niveau zéro dans le tableau optimal final. Comme cela doit devenir non basique à
la table optimale finale du problème résolu par la méthode du simplexe, une fois une variable artificielle
laisse la base que nous ne considérons pas pour les itérations restantes pour nous en débarrasser, ce qui va
finira par arriver, si le problème est réalisable.
Dans la méthode du grand M de Charnes, nous attribuons un coût de '-M' à la variable artificielle dans un problème de maximisation.
et le coût ‘+M’ dans un problème de minimisation, où M est très grand.
Le coût important M empêche la variable artificielle de réintégrer la base, une fois qu'elle l'a quittée. Car si cela
il y aura une augmentation de la valeur de la fonction objective dans un problème de minimisation. Mais
la méthode du simplex veille à réduire la valeur de la fonction objective à chaque itération dans un
problème de minimisation. Alors que dans un problème de maximisation, '-M' est le coût correspondant
variable artificielle, si elle entre à un moment donné après avoir été retirée, il y aura une forte baisse dans le
valeur de la fonction objectif, contrairement à la procédure de la méthode du simplexe, car à chaque itération elle
augmente la valeur de la fonction objectif.
Si toutes les variables artificielles sont égales à zéro dans la solution optimale, nous avons trouvé l'optimal.
solution au problème d'origine. Dans tout PPL, si la variable artificielle reste à un niveau positif
dans le tableau final optimal, le problème devient alors incohérent et nous déclarons le problème comme
être infaisable.

Question1Pourquoi choisissons-nous l'entrée la plus négative dans la ligne du bas?

10
L'entrée la plus négative (positive) dans la dernière ligne représente le plus grand (le plus petit)
coefficient dans la fonction objective - le coefficient dont l'entrée augmentera (diminuer) le
valeur de la fonction objective très rapidement.

Question2Why do we identify the pivot element?

Comme nous l'avons mentionné précédemment, la méthode du simplexe commence par un point d'angle et ensuite
se déplace vers le prochain point d'angle en améliorant toujours la valeur de la fonction objective. La valeur
la fonction objective est améliorée en changeant le nombre d'unités des variables. Nous pouvons
ajouter le nombre d'unités d'une variable, tout en se débarrassant des unités d'une autre. Pivoter
nous permet de faire exactement cela.

Problème avec des contraintes mixtes

Q2. (i) Maximize Z = 2x1+ 4x2 (ii) Maximiser Z = 2x1+ x2+3x3
Objet à 2x1+ x2≤ 18 Sujet à x1+ x2+ 2x3≤ 5
3x1+2 x2≥ 30 2x1+ 3x2 + 4x3= 12
x1+2 x2 = 26 Et, x1, x2, x3≥ 0
Et, x1, x2≥ 0
(iii) Minimiser Z = 5x + 8y (iv) Maximiser Z = 8x1- 4x2
Sous réserve que x + y = 5 Objet à 4x1+ 5x220 ≤
x≤4 ≥
–x1+ 3x2-23
y≥2 Et, x10, x≥2non restreint en signe.
Et x, y ≥ 0
La solution optimale est (2, 12) et la valeur de la fonction objectif est 52.
Réponse. (i)
(ii) La solution optimale est (3, 2, 0) et la valeur de la fonction objective est 8.
(iii) La solution optimale est (3, 2) et la valeur de la fonction objective est 31.
(iv) La solution optimale est (175/17, –72/17) et la valeur de la fonction objective est 1688/17.

ÉGALITÉ POUR LA VARIABLE D'ENTRÉE

Dans un tableau simplex, supposons que deux ou plusieurs variables non de base soient à égalité pour avoir le plus.
négatif (positif) Zj- Cjentrée. Dans ce cas, nous choisissons l'un d'eux pour trouver l'entrée
La solution optimale sera finalement atteinte, peu importe la variable liée choisie.

SOLUTIONS OPTIMALES MULTIPLES

Dans chaque tableau du simplexe, les variables de base ont toutes Zj– Cj≥ 0, mais pas les non-basiques. Quand
une solution est indiquée comme optimale et le Zj– Cjla valeur pour aucun des variables non fondamentales n'est
zéro, la solution est unique en ce sens qu'aucune autre solution au problème donné n'existe, ce qui
produirait la valeur identique de la fonction objective. Lorsqu'une variable non basique dans un
la solution optimale a une valeur nulle pour Zj– Cj, alors la solution n'est pas unique, et il existe plusieurs optimales
Des solutions existent. Les autres solutions optimales sont généralement obtenues en effectuant des actions supplémentaires.

11
itérations de la méthode du simplexe, choisissant à chaque fois une variable non basique avec un Z nulj– Cj
entrée en tant que variable d'entrée.
Q3. (i) Maximiser Z = 8x1+ 16x2 (ii) Maximise Z = x1+ 2x2+3x3
Sujet à x1+ x2≤ 200 Subject to x1+ 2x2+ 3x3≤ 10
x2≤ 125 x1+ x2≤ 5
3x1+6 x2≤ 900 x1≤ 1
et, x1, x2≥ 0 et, x1, x2, x3≥ 0
Réponse. (i) Les solutions de base optimales sont (50, 125) et (100, 100) ayant un objectif optimal.
valeur de fonction 2400.
10 1
(ii) Les solutions de base optimales sont (0, 0, ), (1, 0, 3), (0, 5, 0) et (1, 4, ) ayant
3 3
valeur optimale de la fonction objective 10.

INFEASIBILITÉ
Lorsqu'une variable artificielle est à la base à une valeur positive dans la solution finale, alors il n'y a pas de
solution réalisable au problème.
Q4. (i) Maximiser Z = 20x1+ 30x2 (ii) Maximiser Z = x1+ 4x2+3x3
Sous 2x1+ 3x2≤ 40 Sous 2x1– x2+ 5x3= 40
4x1– x2≤ 20 x1+ 2x2- 3x3≥ 22
x1≥ 30 3x1+ x2+ 2x3= 30
et, x1, x2≥ 0 et, x1, x2, x3≥ 0
Réponse. (i) et (ii) le problème est infaisable.

SOLUTION SANS LIMITE

On dit qu'un PLP a une solution non bornée si la valeur de sa fonction objective peut être augmentée (dans
s'il s'agit d'un problème de maximisation) ou diminuée (s'il s'agit d'un problème de minimisation) sans limite.
S'il n'y a pas de ratios de remplacement non négatifs dans une certaine situation ou lorsque toutes les valeurs de
Les colonnes clés sont négatives, c'est-à-dire que toutes sont négatives ou elles sont égales à ∞ (pour la raison de la
le dénominateur égal à zéro), alors l'algorithme se termine. Cela indique que le problème sous
la considération a une solution illimitée.
Si nous rencontrons l'unboundedness en résolvant des problèmes réels, alors le problème n'est pas correctement défini.
formulé. Puisqu'aucune situation réelle ne permet à une direction d'avoir une production infinie de biens
et des profits infinis, des résultats de solution illimitée si dans un problème de maximisation toutes les contraintes sont
de type supérieur ou égal. Dans une telle situation, il n'y a pas de limite supérieure à la région faisable.
De même, une solution non bornée se produit dans un problème de minimisation si toutes les contraintes sont de moins
que ou égal à type.
Q5. (i) Maximiser Z = 10x1+ 20x2 (ii) Maximiser Z = 5x1+ 2x2+2x3
Sous 2x1+ 4x2≥ 16 Subject à 3x1- 2x2- 2x3= –8
x1+ 5x2≥ 15 3x1- 4x2– x3= –7
et, x1, x2≥ 0 et, x1, x2, x3≥ 0
12
Réponse. (i) et (ii) la solution est non bornée.

INFEASIBILITÉ VS UNBOUNDEDNESS
À la fois l'inadéquation et l'illimité ont une similitude en ce qu'il n'y a pas de solution optimale dans
dans les deux cas. Mais il y a une différence frappante entre les deux : tandis que dans l'infeasibilité, il n'y a pas de
solution unique faisable, dans l'infinitude il y a d'infinités de solutions faisables mais aucune d'entre elles
peut être qualifié d'optimal.

ÉGALITÉ POUR LA VARIABLE DEPARTANTE - DÉGÉNÉRESCENCE

La dégénération dans la PPL se produit lorsque l'une ou plusieurs des variables de base prennent une valeur de zéro. Comme
Comme déjà indiqué, pour un problème à n variables et m contraintes, il y aurait m basiques et n-m non-basiques.
les variables, et les variables de base prendraient des valeurs positives. Cependant, dans le cas où une variable de base
la variable prend une valeur égale à zéro, alors la variable et la solution sont qualifiées de dégénérées.
Ainsi, en condition de dégénérescence, la solution contiendrait un plus petit nombre de valeurs non nulles.
variables que le nombre de contraintes, m.
Chaque fois qu'il y a égalité dans les ratios de remplacement pour déterminer la variable sortante, le tableau suivant
donnerait une solution dégénérée. De plus, nous pouvons choisir l'un de ces quotients pour trouver
variable de départ.
Q6. Maximiser Z = 28x1+ 30x2 (Profit)
Sous 6x1+ 3x2≤ 18 (Contrainte de Matière Première)
3x1+ x2≤ 8 (Contrainte des heures de travail)
4x1+5 x2≤ 30
et, x1, x2≥ 0
La solution optimale est (0, 6) et la valeur de la fonction objectif est 180.

Remarque
•Nous savons que les tables simplex successives représentent des améliorations dans la valeur de la
fonction objective – des augmentations sont observées pour la maximisation et des diminutions pour le
problèmes minimes. Cependant, lorsque la variable sortante s'avère être dégénérée
variable, la valeur de la fonction objective dans le tableau suivant ne change pas. La valeur Z pour un
La table 'non optimale' n'est pas différente de la valeur Z obtenue de la table suivante.
•S'il n'y a pas d'amélioration de la solution en termes de fonction objective, alors pourquoi
ne devrions-nous pas nous arrêter à l'itération où une solution dégénérée apparaît ? La réponse à
c'est que l'on ne peut pas être sûr que la première apparition d'une solution dégénérée sera
coïncider avec la solution optimale. En d'autres termes, le problème peut être temporairement
dégénéré. Nous pouvons considérer la question suivante où une solution dégénérée est
rencontré mais par la suite la dégénérescence disparaît.
Q7. Maximiser Z = 5x + 2y
Sous réserve de 4x + 2y ≤ 16
3x + y ≤ 9
13
 3x - y ≤ 9
et, x, y ≥ 0
Réponse. La solution optimale est (1, 6) et la valeur de la fonction objectif est 17.

14