PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

INVESTIGATION DES OPÉRATIONS

PROGRAMMATION LINÉAIRE : SOLUTION

DE PROBLÈMES AVEC LE "MÉTHODE
GRAPHIQUE

JOSÉ E. VÁZQUEZ ARÉVALO

PROCESSES TECHNOLOGIES AND INDUSTRIAL
ITESO

PROGRAMMATION LINÉAIRE : SOLUTION DE PROBLÈMES AVEC LA "MÉTHODE GRAPHIQUE"

JEVA / PTI
1
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

Il existe deux méthodologies pour résoudre un problème modélisé en Programmation Linéaire : la Méthode Graphique
La méthode du Simplex.

El Método Gráfico se utiliza para ilustrar tres conceptos básicos: la metodología para la resolución de un
problème de deux variables de décision, l'interprétation de la solution du problème modélisé et l'observation
graphique de la manière dont les changements affectent la solution du problème. La méthode graphique est peu puissante car
il est limité à résoudre des problèmes de deux ou au maximum trois variables de décision. Cependant, son importance
radique dans le fait de permettre de visualiser les concepts mathématiques impliqués dans la Programmation Linéaire.

Pour sa part, la méthode du Simplex est utilisée pour résoudre des problèmes plus complexes de programmation linéaire.
C'est une méthode puissante, utilisée pour résoudre des problèmes de "n" variables de décision, bien qu'elle soit aussi
peut être utilisé pour résoudre des problèmes à deux variables comme le fait la Méthode Graphique.

L'approche proposée ici est d'utiliser l'ordinateur comme un outil d'aide à la résolution de problèmes.
de Programmation Linéaire de toute taille. Cependant, il faut d'abord étudier les fondamentaux de
ces méthodes de solution pour ensuite utiliser l'ordinateur à cet effet.

L'utilisation de l'ordinateur dans la résolution de problèmes en Programmation Linéaire implique d'utiliser n'importe lequel de
ces deux alternatives : première, utiliser une feuille de calcul comme Excel, où l'utilisateur fait
directement la programmation pour résoudre le problème modélisé; deuxièmement, l'utilisation d'un paquet de
logiciel commercial, déjà conçu pour la résolution de la Méthode Graphique et du Simplex.

Certains des logiciels commerciaux les plus connus sont : Storm, WinQSB, Lindo, Eureka, etc.
Ces types de logiciels ont évolué en fonction des avancées technologiques de l'époque, avec la tendance
d'avoir un outil plus puissant mais avec une certaine perte de faire des utilisateurs plus réfléchis et pas seulement
manipulateurs de celle-ci. Il est évident que l'utilisation de l'ordinateur permet un gain de temps considérable dans le
traitement des données et qui permet de résoudre des problèmes plus complexes auxquels on est normalement confronté
se hacen dentro del aula.

Cependant, l'utilisation de tout paquet logiciel nécessite que le problème soit déjà modélisé, pour être
capturé dans le format requis par ce logiciel. De cette manière, on peut obtenir la solution optimale de
problème comme un rapport de sortie de l'ordinateur mais cette solution mathématique nécessite un
interprétation par l'utilisateur pour la prise de décision.

Le cycle complet à réaliser dans la solution d'un problème est : modéliser le problème, résoudre le problème.
modéliser et interpréter la solution obtenue. Parmi ces trois parties, celles qui développent le plus les compétences du
La pensée est la modélisation du problème et l'interprétation de la solution trouvée. Dans ce cas, on
considera de menor contribución a la etapa de la solución del problema, que se puede hacer a través de la
ordinateur.

Cependant, l'objectif de ce chapitre est de fonder les concepts de base de la Programmation Linéaire à
à travers la Méthode Graphique. À cet effet, deux exercices ont été développés, le premier étant axé sur
montrer "la méthodologie et les concepts de base" de la Méthode Graphique et le second présente le "cycle complet"
que se suit dans la solution d'un problème de Programmation Linéaire.

Exercice 1. Méthodologie et concepts de base de la "Méthode Graphique".

La méthodologie utilisée par la Méthode Graphique pour trouver la solution optimale d'un problème est présentée.
modélisation et les concepts de base de la Programmation Linéaire qui peuvent être visualisés à travers elle. Se
présente le problème suivant :

Fonction Objectif : Max. Z = 3X1+ 6X2

JEVA / PTI
2
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

Restricciones: a. X1 ≤10
b. X2≤10
c. X1+ X2≤16
d. 6X1+ 4X2≥48
e. X1+ X2≤20
f. 2X1+ 4X2≥16
g. X1- X2≤0
h. Pas de négativité : X1, X2≥0

1.1. Metodología.
La Méthode Graphique utilise la méthodologie suivante pour trouver la solution optimale d'un problème :
a. Calculer les points pour tracer chaque contrainte.
b. Représenter graphiquement les restrictions.
c. Déterminer la région réalisable.
d. Calcular las coordenadas de los vértices de la región factible.
e. Calculer la valeur de la Fonction Objetif à ces sommets.
f. Trouver la solution optimale du problème.

Calculer les points pour tracer chaque contrainte.

Pour tracer une contrainte, on la considère d'abord comme une droite, c'est-à-dire comme si elle était une
égalité, puis on trouve l'espace solution qui satisfait la condition de cette contrainte,
mettant une petite flèche pour l'indiquer.

En este problema se presentan tres variantes que se pueden encontrar al graficar una restricción: cuando
est parallèle à un des axes de coordonnées, quand il croise les deux axes de coordonnées et quand
passe par le point d'origine (0,0). Voici les variantes :

Les contraintes "a" et "b" du problème sont parallèles aux axes X1y X2. On reconnaît qu'un
la restriction est parallèle lorsqu'elle n'a qu'une seule des variables, par exemple la restriction "a" seulement
il a la X1donc elle est parallèle à l'axe X2.

Un autre type de restrictions est celui qui traverse les deux axes comme les restrictions "c", "d", "e" et
f

Il existe également des restrictions qui passent par le point (0,0) comme la restriction "g".

Para graficar una recta existen diferentes métodos, uno de ellos es el "método de los dos puntos". En
dudit méthode stipule que, pour tracer une droite, il est nécessaire de connaître au moins deux points
lui appartenant.

Pour calculer les coordonnées des deux points P1y P2, on choisit arbitrairement l'une des variables de
la restriction, par exemple X1et est égal à zéro, calculant l'autre variable X2; ensuite, procéder à
la inversée, se fait X2= 0 et X est calculé1Si la contrainte est parallèle à l'un des axes, il suffit de
Fixez la coordonnée et tracez la droite. Ci-dessous, les points calculés pour chaque
restricción:

Restrictions Points pour tracer la droite :

P1X1,0) P2(0,X2)
a. X1 ≤10 10,0 -
b. X2 ≤10 - 0,10
c. X1+ X2≤16 16,0 0,16
d. 6X1+ 4X2 ≥48 8,0 0,12
e. X1+ X2≤20 20,0 0,20
f. 2X1+ 4X2≥16 8,0 0,4
g. X1- X2≤0 0,0 0,0
Graphier les restrictions.
Voici comment tracer chacune des variantes des contraintes :

JEVA / PTI
3
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

Pour tracer une contrainte parallèle à l'un des axes, comme c'est le cas pour "a", on marque le point (10,0)
qui est sur l'axe X1et se trace parallèlement à l'axe X2. L'espace de solution est évident pour
ce type de restrictions, qui dans ce cas, le sens de la restriction est vers la gauche comme
on peut le voir dans le graphique de la Figure 1.

Pour tracer une contrainte qui croise les deux axes, comme serait "d", on marque le point un (8,0) sur
l'axe X1et le point deux (0,12) sur l'axe X2y se rejoignent en traçant une droite. Pour déterminer le
espace de solution, cela peut être fait directement en observant le type d'inégalité qu'il a
restricción, sin embargo, se recomienda probar el sentido de la restricción con el punto (0,0). Al
substituer ces valeurs dans la contrainte, on vérifie si cela respecte ou non la condition imposée par
cette restriction. S'il respecte la condition, alors l'espace solution sera de la droite vers le
origine (0,0), qui était le point testé. Si cela ne remplit pas la condition, l'espace solution sera en
sens opposé. Par exemple, si nous substituons ce point dans la contrainte "d", nous aurons 0≥48 qui
ne respecte pas la contrainte, donc sa direction sera contraire à l'origine (0,0) comme
On peut le voir dans le graphique de la Figure 1.

Pour tracer une contrainte qui passe par le point d'origine (0,0), comme c'est le cas pour "g", il faut
générer un « point auxiliaire ». Ce point auxiliaire se calcule en donnant une valeur arbitraire à l'une des
variables pour la substituer dans l'équation de la contrainte et pouvoir isoler l'autre variable, par
exemple, si nous considérons X1= 2 se doit :

2 - X2= 0
X 2= 2

El punto auxiliar es (2,2). Ahora se tienen dos puntos, el (0,0) y el (2,2) por donde pasará la recta.
Pour déterminer l'espace de solution, il est nécessaire d'essayer avec n'importe quel point séparé de la droite,
soit par-dessus ou par-dessous elle. Si le point testé satisfait la contrainte, l'espace de
la solution sera dans cette direction sinon elle sera dans le sens inverse. Par exemple, si l'on essaie avec le
point (10,2) which is below the line, when substituted in the constraint, will have 8≤0 which does not
il respecte la contrainte, de sorte que l'espace solution sera vers le haut (voir Figure 1), c'est-à-dire
en sens contraire au point prouvé. S'il avait été prouvé un point au-dessus de la droite comme
el (2,20) on parviendrait à la même conclusion.

Determinar la región factible.

Pour déterminer la région feasible dans le graphique de la Figure 1, il est important de prendre en compte le sens des
restrictions pour trouver la zone commune à toutes. Pour ce faire, nous pouvons nous aider des
petites flèches qui indiquent le sens de chaque restriction.

Lorsque l'on a de nombreuses restrictions graphiques, une façon simple de trouver la région admissible est
considérer chaque contrainte comme la coupe qui se fait dans un gâteau. On offre la part qui ne
cela respecte le sens de la restriction et nous laissons celle qui respecte. En continuant à faire les autres coupes,
la tranche qui reste deviendra de plus en plus petite. La partie qui reste à la fin sera la région réalisable.
Cette conception proposée peut être visualisée en considérant que chaque contrainte divise l'espace en
deux parties. La partie qui respecte le sens de la restriction est indiquée par une petite flèche.

Voici le graphique des contraintes du problème et de la région réalisable :

JEVA / PTI
4
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

Figure 1. Graph of the constraints and the feasible region.

Calcular las coordenadas de los vértices de la región factible.

Dans le graphique de la Figure 1, les sommets formant la région faisable ont été marqués. L'importance de
calculer les coordonnées de ces sommets, cela aide à calculer la valeur de la Fonction Objectif à
Chacun d'eux et sur la base de cette liste, se trouve la solution optimale du problème.

Une façon simple de calculer les coordonnées d'un sommet est de les lire directement sur le graphique, mais
La précision de la lecture dépendra de la qualité de ce graphique. Une autre façon que ne ...
Cela dépend de la précision du graphique, il faut voir quelles restrictions forment au sommet et résoudre ce système.
de deux équations par une méthode algébrique. Cependant, les calculs peuvent être réduits si
nous classifions les sommets en deux types : ceux qui se trouvent sur l'un des axes de coordonnées et ceux qui
sont hors des axes.

Cuando un vértice está sobre uno de los ejes, se pueden leer directamente sus coordenadas en el gráfico
ou dans les points calculés pour tracer la contrainte. Si le sommet est en dehors des axes, cela est requis
calculer ses coordonnées à travers un système d'équations simultanées, donné par les deux
restricciones que se cruzan para formar dicho vértice. Si una de las restricciones es paralela,
il suffit de substituer la valeur de cette variable dans l'autre contrainte.

En analysant le graphique, on peut voir que tous les sommets de la région faisable sont en dehors des axes. Le
vértice "A" esta formado por la intersección de las restricciones "d" y "g", el vértice "B" por "b" y "d", el "C"
par "b" et "c" et le "D" par "c" et "g". Ensuite, les coordonnées de chaque sommet sont calculées :

Sommet "A": Restriction "d" 6X1+ 4X2= 48

Restriction "g" 4( X1- X2= 0)
10X1 = 48

X1= 4.8
X2 = 4,8

Vértice "B": Restriction "b" X2= 10

En substituant dans la Restriction "d", on obtient :

6X1+ 4(10) = 48
X11.3

Sommet "C": Restriction "b" X2= 10

En remplaçant dans la contrainte "c", on obtient :
X1+ X2= 16
X1 = 6

JEVA / PTI
5
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

Vortex "D": Restriction "c" X1+ X2= 16

Restriction "g" X1- X2= 0
2X1 = 16

X 1= 8
X 2= 8

Calculez la valeur de la fonction objectif à ces sommets.

Pour calculer la valeur de la fonction objectif en un sommet, il suffit de substituer dans celle-ci la valeur de X.1
y X2donné par les coordonnées de ce sommet.

Ci-dessous se trouve un tableau avec les coordonnées des sommets de la région réalisable et la valeur de la
Fonction Objectif dans chacun d'eux :

Coordonnées
Vértice (X1 , X2) Z = 3X1+ 6X2
Un 4.8, 4.8 43,2
B 1,3, 10,0 63,9
C 6,0, 10,0 78,0 ←Max. Z
D 8.0, 8.0 72.0

Trouver la solution optimale du problème.

Dans le tableau précédent, les valeurs de la Fonction Objectif ont été présentées à chaque sommet de la
région réalisable, parmi ceux-ci on choisit la valeur qui respecte ce qui est établi dans la Fonction Objectif, dans
ce cas le Max. Z.

En sélectionnant dans le tableau la ligne de la Max. Z, on peut lire directement les valeurs de la solution.
optimale du problème et le sommet où elle se trouve.

La solution optimale du problème se trouve au sommet "C" de la région réalisable et ses valeurs sont :
X1 = 6
X2= 10
Max. Z = 78

Dans ce problème, si la Fonction Objetive avait été de minimisation, on aurait choisi le 43.2 qui est
la valeur minimale du tableau. Alors, la solution optimale aurait été localisée au sommet "A" avec les
valeurs suivantes :

X1= 4,8
X2= 4.8
mín. Z = 43,2

Comme il a été observé, la solution optimale d'un problème dépend de la région faisable qui se forme.
avec l'ensemble des contraintes et de l'inclinaison que possède la Fonction Objectif qui lui permet d'atteindre
son valeur optimale, qu'elle soit de maximisation ou de minimisation.

1.2. Concepts de base.

Quelques concepts de base de la Programmation Linéaire qui peuvent être visualisés à travers la Méthode Graphique
fils

a. Région faisable.
b. Restriction active et restriction redondante.
c. Démontrer que : Max. Z = min.(-Z)
d. Demostrar que:
La solution optimale de tout problème de Programmation Linéaire se trouvera toujours dans
un des sommets ou sur tout un côté de sa région faisable.
e. Sommets en dehors de la région faisable.

JEVA / PTI
6
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

f. Analyse des changements qui affectent le modèle du problème.

Région réalisable.
La région feasible est formée par les contraintes du problème et se trouve à l'un ou plusieurs de ses sommets.
la solution optimale.

La forme de la région réalisable dépend du type de contraintes que l'on a. Néanmoins, on peut
considérer deux types de base : la région réalisable 'fermée' et la 'ouverte'.

La région réalisable fermée se produit lorsque les contraintes, y compris celles de "non-négativité", délimitent
la région faisable du problème. Dans le type ouvert, on a une région faisable non bornée qui ne permet que
la minimisation. Les graphiques de ces types de région faisable sont présentés ci-dessous :

Figure 2. Région fermée réalisable : Région réalisable ouverte :

a. Appuyée sur les 2 axes. a. Vers la droite.
b. Soutenue sur un axe. b. Vers le haut.
c. Sans soutien sur les axes.

Lorsqu'un problème modélisé n'a pas de région faisable, c'est parce que certaines de ses contraintes sont
contradictoires entre eux. Ce type de problèmes est «infaisable», c'est-à-dire que le problème modélisé n
il y a une solution. Dans ces cas, il est nécessaire de revoir le modèle du problème, car il existe une certaine
incohérence dans les contraintes qui ne permet pas d'avoir une région faisable.

Restricción activa y Restricción redundante.

Les restrictions qui font partie de la région réalisable sont les "restrictions actives" tandis que celles qui ne le sont pas
la forman son les "redondantes".

Les contraintes actives sont celles qui forment réellement la région faisable où se trouve la solution optimale. Celles-ci
les restrictions sont l'essence du problème modélisé, de sorte que, si l'une d'elles est supprimée, elle
cambia la solución óptima. Las restricciones activas que se tienen en el problema son "b", "c", "d" y "g".

Une contrainte redondante n'a aucun effet sur la solution optimale du problème, c'est une contrainte
fictive qui ne change rien de la laisser dans le modèle ou de l'enlever. Les contraintes redondantes qui existent dans le
le problème est "a", "e" et "f".

Démontrer que : Max. Z = min.(-Z)

En démontrant que Max. Z = min.(-Z), on démontre également que l'inverse est vrai, c'est-à-dire
que mín. Z = Máx. (-Z).

Ce principe est très puissant dans la résolution de problèmes de minimisation par la méthode
Simplex, méthode qui sera étudiée ultérieurement pour résoudre des problèmes de n'importe quelle taille. Cela

JEVA / PTI
7
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

permet qu'un problème de minimisation soit transformé et résolu comme un problème de

Maximisation, en ne changeant que les signes de sa Fonction Objectif.

Un exemple de la façon dont un problème modélisé de minimisation peut être transformé pour être
résolu par la méthode du Simplex, est le suivant :

min. Z = 30X1+ 10X2→Máx. Z = - 30X1- 10X2

Restrictions 2X1+ 4X2 ≤80

X1+ X2= 25
8X1+ 6X2≥120

Maintenant, il y a un problème de maximisation modélisé, où seule la fonction a changé de signe.

L'objectif et les contraintes sont restés les mêmes. Ce problème se résout par la méthode du Simplex pour
trouver la solution optimale et la valeur de la Max. Z, valeur qui sera toujours négative. La solution au
Le problème original de minimisation sera la même solution que celle trouvée pour le problème résolu de
Max (-Z) et la valeur de la min. Z sera la même que la Max. Z mais avec un signe positif.

En revenant à la démonstration demandée, nous pouvons la réaliser de manière très simple. Profitant des
les coordonnées des sommets de la région faisable qui se trouvent dans le tableau peuvent être substituées dans la
Fonction Objectif qui est devenue transformée comme mín. Z = -3X1-6X2. A continuación se presenta le
analyse qui permet de faire la démonstration :

Coordonnées
Un sommet (X1, X2) Z = 3X1+ 6X2 Z = -3X1+ 6X2
Un 4.8, 4.8 43,2 -43,2
B 1.3, 10.0 63.9 -63.9
C 6.0, 10.0 78,0 -78.0 ←Max. Z
D 8.0, 8.0 72,0 -72.0

En comparant les valeurs de la solution optimale du problème, on peut conclure que :

Máx. Z = mín(-Z) et par conséquent que mín. Z = Máx.(-Z)

Démontrer que :
la solution optimale de tout problème de programmation linéaire sera toujours
à un des sommets ou sur tout un côté de sa région réalisable.
La solution optimale d'un problème de programmation linéaire peut être de deux types : solution "ponctuelle ou
unique" et la solution sous forme de "plage".
La solution du type ponctuel se trouvera toujours à l'un des sommets de la région faisable, comme
conséquence de la pente que possède la Fonction Objectif en traversant cette région. Si elle se déplace
parallèlement à la Fonction Objectif à travers la région faisable, on verra que la solution optimale sera dans
un des sommets.

Lorsque la fonction objective est parallèle à l'une des contraintes qui forment la région faisable, cela
provoca un "rango óptimo" de soluciones. Este rango óptimo es consecuencia de que la Función Objetivo
traverse la région réalisable d'un côté à l'autre, d'un sommet à l'autre. Cette plage de solutions optimales
cela signifie qu'il est possible de générer au moins une "solution optimale alternative" pour le problème, ou bien, une
gamme de "solutions optimales multiples".

Pour démontrer que la solution optimale se trouve à l'un des sommets de la région faisable, on peut le voir dans
le tableau précédent, la liste des valeurs adoptées par la Fonction Objectif en croisant chacun des
les sommets et simplement sélectionner la valeur maximale qui est la Max. Z. Il sera observé que cette solution
optimum est au sommet "C".

Une autre façon de faire cette démonstration est qu'en traçant la Fonction Objectif avec la valeur
de la Máx. Z devra passer par le sommet 'C'. Le traçage de la droite de la Fonction Objectif est exactement

JEVA / PTI
8
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

tout comme tracer la droite d'une contrainte. L'équation de la Fonction Objectif à tracer est
la siguiente:
78 = 3X1+ 6X2

Avec cette équation, on peut calculer les deux points sur les axes par lesquels passe la Fonction Objectif
quedant P1(26,0) et P2(0,13). En traçant la droite, on observe qu'elle passe effectivement par le sommet "C"
comme le montre le graphique des contraintes.

Avec l'intention de montrer un problème ayant "plusieurs solutions optimales", il a été modifié
légèrement le problème actuel. Les mêmes contraintes ont été laissées et la Fonction Objectif a été changée en :

Max. Z = 6X1+ 6X2

Comme les restrictions n'ont pas changé, on a la même région faisable avec les mêmes sommets et
coordonnées qui peuvent être utilisées pour obtenir les valeurs de la Fonction Objectif qui sont affichées dans la
tableau suivant :

Coordonnées
Sommet (X1, X2) Z = 6X1+ 6X2
Un 4.8, 4.8 57,6
B 1,3, 10,0 67.8
C
D
6.0, 10.0
8,0, 8,0
96,0
96,0 } Rang optimal
En recherchant dans le tableau précédent la solution optimale du problème, on trouve deux solutions optimales, c'est
dire que l'une d'elles sera la solution optimale et l'autre sera une solution optimale alternative, restant dans la
forme suivante :

Solution Optimale Solution Optimale Alternative

(Sommet "C") (Sommet "D")

X 1= 6 X 1= 8
X2= 10 X 2= 8
Max. Z = 96 Max. Z = 96

En ayant deux solutions optimales, on peut calculer le "plage optimale" pour le problème, qui reste dans la
suivant la forme :

6≤X1≤8
8≤X2≤10
Max. Z = 96

Connaissant la plage optimale, il est possible de générer plusieurs solutions optimales pour le problème.
exemple, pour calculer une autre solution optimale, qui soit différente de celles que nous connaissons, on peut donner un
valeur arbitraire à l'une des variables tant qu'elle est dans sa plage. Si nous considérons X1= 7
alors, en substituant cette valeur dans la Fonction Objectif, cela donne :

96 = 6(7) + 6X2
X 2= 9

Cette nouvelle solution optimale du problème a été tirée de la plage optimale, devenant ainsi :
X 1= 7
X 2= 9
Max. Z = 96

De cette manière, différentes solutions optimales peuvent être générées pour le problème, mais toutes elles
auront comme caractéristique la même valeur de Max. Z = 96. Quelques autres solutions optimales qui se
peuvent sortir de la plage optimale sont :

JEVA / PTI
9
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

X 1= 6 X 1= 8
X2= 10 X 2= 8
Máx Z = 96 Máx. Z = 96
Un avertissement, si vous fixez les deux variables en même temps, même avec des valeurs qui sont dans leurs
Rangos, pas nécessairement cela sera une solution optimale au problème. Par exemple, considérez X1=
6 y X2= 9. Cette solution n'est pas optimale, car en substituant dans la fonction objectif, on a un Max. Z =
90 mais pas de 96. La raison peut être vue graphiquement, si on place ce point, on observera qu'il est
dans la région réalisable mais pas sur la droite qui relie les sommets "C" et "D", donc ce point est
une solution réalisable mais pas optimale. Seulement les points qui sont exactement sur la droite qui relie les
Les sommets "C" et "D" donneront des solutions optimales.

Sommets en dehors de la région faisable.

Anteriormente, se estableció que la solución óptima está en algún vértice de la región factible. También
on peut voir dans le graphique, des sommets qui sont en dehors de la région faisable, donc nous pouvons nous demander :

Quelle est la signification du sommet formé par le croisement des contraintes "a" et "c" ?

Ce sommet est formé par la contrainte "a" qui est redondante et par la contrainte "c" qui est déjà active.
qui fait partie de la région réalisable. De plus, ce sommet est en dehors de la région réalisable comme le montre
le graphique, ce qui signifie que ce point ne respecte pas toutes les contraintes du problème modélisé et
que tiene algún recurso sobrante. El recurso sobrante estará en la restricción redundante por lo que se
vous pouvez calculer sa valeur. La contrainte active indique que la ressource a été entièrement utilisée par les
qu'il n'y a pas de surplus.

Si vous voulez connaître toutes les restrictions que le sommet peut respecter et celles qu'il ne peut pas, il est nécessaire de calculer
ses coordonnées pour avoir une valeur de X1y de X2. Résoudre les équations des contraintes "a" et
"c", il faut que X1= 10 y X2 = 6. En remplaçant ces valeurs dans chacune des contraintes du problème
modélisation, on pourra dire si cela respecte ou non la contrainte particulière. En faisant cela, nous nous rendons compte
que ce sommet ne respecte pas la contrainte "g" mais respecte toutes les autres.

En plus d'identifier la contrainte avec laquelle le sommet ne respecte pas, il est également possible de faire une "analyse
des ressources". Pour effectuer cette analyse, il faut remplacer les valeurs de la solution optimale (X1=6 y
X2=10) dans les contraintes qui forment le sommet. Voici l'analyse :

Restriction "a": X1≤10

6≤10 Il en reste 4.

Restriction "c": X1+ X2 ≤16

6 + 10≤16 Il ne reste rien.

Il en ressort qu'il reste 4 de la ressource utilisée dans la restriction "a" étant donné qu'il en a été dépensé 6 sur 10
disponibles. Por otra parte, se gastó totalmente el recurso de la restricción "c" que forma parte de la
région faisable.

Quelle est la signification du sommet formé par les contraintes "a" et "e" ?

C'est un sommet en dehors de la région réalisable où ses deux restrictions sont redondantes car elles ne forment pas
partie de la région faisable. En remplaçant les valeurs de la solution optimale dans les deux contraintes, on peut
faire l'analyse suivante des ressources :

Restriction "a": X1≤10

6≤10 Il en reste 4

Restricción "e": X1 + X2≤20

6 + 10 ≤ 20 Il reste 4

Il est conclu que, un sommet en dehors de la région faisable aura toujours des ressources excédentaires à chaque
restriction redondante qu'elle ait.

JEVA / PTI
10
PROGRAMMATION LINÉAIRE MÉTODO GRÁFICO

Analyse des changements qui affectent le modèle du problème.

Un problème modélisé de Programmation Linéaire, qui expérimente un type de changement, peut ou non
changer sa solution optimale en fonction du changement. Il existe deux types de changement de base : le changement de
un coefficient de contribution de la Fonction Objectif ou le changement de la disponibilité des ressources de
les restrictions.

Un changement dans l'un des coefficients de la fonction objectif équivaut à faire pivoter cette fonction objectif.
Lorsque l'on veut provoquer une solution optimale alternative, on fait tourner la Fonction Objectif jusqu'à ce qu'elle soit parallèle.
à une contrainte active. Selon le sens de la rotation effectuée dans la Fonction Objectif ainsi
ce sera le changement qui aura son équation.

Auparavant, un problème de rotation de la Fonction Objectif a été traité où l'équation a été modifiée.
d'une Max. Z = 3X1+ 6X2a Máx. Z = 6X1+6X2. Plus tard, les étapes suivies sont présentées.
pour calculer cette "nouvelle Fonction Objectif" qui a une solution optimale alternative.

Si le changement apporté affecte la "disponibilité de la ressource" de la contrainte, c'est-à-dire le terme

indépendant, alors la droite se déplacera parallèlement. Si le terme indépendant augmente de valeur,
cela fera que la droite se déplace parallèlement vers le haut ou vers la droite. Au contraire, si elle diminue
de valeur, la droite se déplacera parallèlement vers le bas ou vers la gauche.

Il existe d'autres types de changements que le modèle du problème peut subir, par exemple, retirer un
restriction, ajouter une nouvelle restriction, changer le sens d'une restriction. Selon le type de
cambio será el efecto que tenga en la solución óptima del problema. Estos cambios se analizan a
poursuite avec les questions suivantes :

Que se passe-t-il avec la solution optimale du problème si la contrainte "a" est "enlevée" ?

Comme la contrainte "a" est une contrainte redondante, la retirer du modèle n'affecte en rien la région.
viable donc la solution optimale reste la même.

La région faisable du problème est-elle modifiée en supprimant la contrainte "b" ?

Si dans le modèle du problème la contrainte "b" qui est une contrainte active est supprimée, si la modification est faite
région faisable et par conséquent change la solution optimale du problème.

Est-ce que la solution optimale du problème change si une nouvelle contrainte est ajoutée au problème, par
exemple X2<= 7?

Cette nouvelle restriction diminue la région réalisable qui existait auparavant, par conséquent elle change
la solution optimale du problème.

La solution optimale du problème est-elle affectée si le « sens » de la contrainte « e » est modifié ?

En faisant ce changement, le problème modélisé n'a pas de solution optimale car il devient "infaisable".
conséquence du fait qu'il n'y a pas de région réalisable qui respecte toutes les contraintes.

Comment peut-on modifier l'équation d'une fonction objectif pour qu'elle ait une solution ?
alternance optimale?

Il est possible de rendre délibérément un problème ayant une solution optimale alternative comme dans le cas
qui s'est présenté. Pour calculer une nouvelle Fonction Objectif qui soit parallèle à l'une des
les restrictions du problème modélisé, il est nécessaire de faire pivoter la Fonction Objectif jusqu'à ce qu'elle soit atteinte
ceci.

JEVA / PTI
11
 PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

La Fonction Objectif du problème original (Max Z = 3X1+ 6X2) se forza à tourner jusqu'à ce qu'elle soit parallèle à
la contrainte "c" pour générer une solution optimale alternative.

Une condition indispensable pour que deux droites soient parallèles est qu'elles aient la même
pente. L'une des méthodes qui existent pour calculer la pente d'une droite, est de la mettre en le
format
y = mx + b, où le "m" est la pente de la droite. En utilisant cette méthode, on calcule la pente du
restriction "c" and the slope that the new Objective Function must take. Both are expressed
équations avec le format requis en isolant la même variable, dans ce cas X1(variable
dépendant). Le coefficient de la X1dans la Fonction Objectif changera de valeur, donc on laisse
exprimé comme une variable "a" qu'il est nécessaire de calculer. Voici les calculs :

Restriction "c" Nouvelle Fonction Objectif

X1+ X2= 16 Z = aX1+ 6X2

X1= -X2+ 16 X1= (-6/a)X2+ Z/a

m = -1 m = -6/a

Pour rendre ces deux droites parallèles, on égalise leurs pentes, ce qui donne :

-1 = -6/a
a=6

Sachant que a = 6, on peut substituer cette valeur pour donner l'équation de la nouvelle Fonction Objectif.
que sera

Máx. Z = 6X1+ 6X2.

On peut établir que, si la rotation de la Fonction Objectif est dans le sens des aiguilles d'une montre,
le coefficient de la variable dépendante (dans notre cas X1) augmentera sa valeur. Au contraire, si le
rotación es en contra de las manecillas del reloj, el coeficiente de la variable independiente (en nuestro
cas X2) augmentera sa valeur. Dans les deux cas, on aura une équation modifiée par la rotation de la
Fonction Objectif.

Dans le problème développé, le coefficient de la X1(variable dependiente) pasó de 3 a 6, es decir que se

a tourné la Fonction Objectif dans le sens des aiguilles d'une montre. Cette rotation peut être visualisée
facilement
dans le graphique.

Exercice 2. Modélisation, solution et interprétation pour un problème de Programmation Linéaire.

Partant d'un problème, le développement de chacune des parties qui constituent le cycle complet est présenté.
de la solution d'un problème de Programmation Linéaire : la modélisation du problème, la solution de celui-ci et la
interprétation de la solution optimale obtenue :

Fabrication d'engrais.

Une entreprise de produits chimiques fabrique, entre autres articles, deux types d'engrais qui nécessitent
de la combinaison de certains ingrédients qui sont achetés auprès de fournisseurs étrangers. Comme chaque
Il faut planifier les tonnes qui doivent être produites de chaque engrais, il faut.
considérer pour établir le programme de production, le prix de vente des engrais, le coût des
ingrédients, toute commande qui doit être exécutée et les restrictions propres à l'usine comme par exemple la
disponibilité de la main-d'œuvre, la disponibilité des matières premières dans l'entrepôt et les délais
requis nécessaires au processus de fabrication.

Un autre aspect à considérer est que l'entreprise met en œuvre une nouvelle stratégie de
mercadotecnia qui consiste à vendre ses engrais par le biais d'un grossiste au lieu de le faire elle-même

JEVA / PTI
12
PROGRAMMATION LINAIRE MÉTHODE GRAPHIQUE

la même. Cela a changé la façon normale de programmer la production, car maintenant il suffit de
considérer les contraintes de production mais pas celles de vente.

Un des engrais fabriqués est le 5-5-10, indiquant avec ces chiffres, le mélange des ingrédients
qui utilise l'engrais, dans ce cas, il y a 5 % de nitrate, 5 % de phosphate, 10 % de potassium et le reste est un
stabilisateur formé par un remblai de terre. L'autre engrais appelé 5-10-5, a 5% de Nitrate, 10%
de Phosphate, 5% de Potassium et le reste est le remplissage de terre. Le grossiste paiera 715 $ la tonne du 5-5-
10 y 690 $ pour le 5-10-5. La disponibilité et les coûts des matières premières pour le mois prochain sont :
1 100 tonnes de Nitrate à 2 000 $ la tonne, 1 800 tonnes de Phosphate à 800 $ chacune et 2 000
tonnes de Potassium à 1600 $ chacune. La terre est disponible en quantités illimitées à un coût de
100 $ par tonne. Considérez qu'il n'y a pas de restrictions sur la capacité de production mais qu'il existe une
coût de mélange de 150 $ par tonne pour l'un des engrais.

L'entreprise souhaite développer un modèle qui l'aide à utiliser correctement les ingrédients.
importe, pour élaborer son programme de production mensuel de manière à maximiser son
utilité.

Après avoir pris connaissance du problème, il est judicieux d'organiser les données qui y sont fournies pour
posteriormente modelarlo. En la siguiente tabla se presentan los datos del problema ya estructurados:

Tableau de Données.
Fertilizante (%) Disponibilité Coût
Ingredientes 5-5-10 5-10-5 (ton/mes) ($/tonne)
Nitrate 5 5 1 100 2000
Phosphate 5 10 1 800 800
Potassium 10 5 2 000 1600
Rembourrage 80 80 illimité 100
Precio Venta 715 690
($/tonne)

Le coût de mélange de n'importe quel engrais est de 150 $ par tonne.

Modélisation.
Variables de Décision.
Xi = Tonnes de l'engrais "i" à fabriquer par mois
(ton/mes)

Fonction Objectif.
Pour établir la Fonction Objectif, il faut d'abord calculer la marge de profit par tonne de chacun.
des engrais en fonction de l'équation suivante :

Utilité = Prix de vente - Coût total

( $/tonne ) ($/tonne) ($/tonne)

Le coût total par tonne d'engrais est calculé sur la base de l'équation suivante :
Coût total = Coût des matières premières + Coût du mélange
($/tonne) ($/tonne) ($/tonne)

Fertilizante 5-5-10:
Costo Materia Prima = 0.05(2000)+0.05(800)+0.10(1600)+0.80(100)
= 380 $/tonne
Costo de Mezclado = $150/ton
Costo Total = 530 $/tonne

Margen de Utilidad = 715 - 530 = $185/ton

Engrais 5-10-5 :
Coût des matières premières = 0,05(2000) + 0,10(800) + 0,05(1600) + 0,80(100)

JEVA / PTI
13
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

= 340 $/tonne
Costo de Mezclado = $150/ton
Coût total = 490 $/tonne

Marge de profit = 690 - 490 = 200 $/tonne

La fonction objectif sera :

Max. Z = 185X1 + 200X2
$/mes ($/ton)(ton/mes) = $/mes

Restrictions.
1. Matière Première.
Nitrate 0,05X1+ 0.05X2≤1,100
Fosfate 0.05X1+ 0,10X2≤1 800
Potasio 0,10X1+ 0.05X2≤2 000
% (ton/mes) = ton/mes ton/mes

2. Pas de négativité. Xje≥0

Analyse Dimensionnelle : Testé.

Solution par Méthode Graphique.

En appliquant la méthodologie de la méthode graphique, nous avons :

Calculer les points pour tracer chaque contrainte.

Points à tracer :
(X1,0) (0,X2)
Nitrate 0.05X1+ 0,05X2<=1 100 22 000 22 000
Phosphate 0,05X1+ 0,10X2≤1 800 36 000 18 000
Potassium 0,10X1+ 0,05X2 2 000 20 000 40 000

Tracer les contraintes et la région faisable.

Calculer les coordonnées des sommets de la région faisable et la valeur de la fonction

Objectif.

Les sommets "A" et "D" se trouvent sur les axes, donc ils peuvent être lus directement à partir du graphique, du tableau.
des points à tracer ou bien on peut calculer. Ci-dessous est illustré le calcul du sommet
"A":

JEVA / PTI
14
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

0,05X1+ 0,10 X2= 1 800

X 1= 0

Comme X1=0 car il est sur l'axe X2, alors en substituant dans l'équation, on a que
X2=18 000, then the coordinates of vertex 'A' are (0, 18000).

On peut lire directement les coordonnées du sommet "D" qui sont (20000,0).

Le sommet "E" a pour coordonnées (0,0).

Les sommets "B" et "C" sont en dehors des axes, il est donc nécessaire de résoudre les deux équations qui...
formez chacun des sommets et résolvez-les par simultanées.

Vértice "B": Phosphate 0,05X1+ 0,10X21 800

Nitrate -(0,05X1+ 0,05X2= 1,100)
0 0,05X2= 700
X2= 14 000

En remplaçant X2dans l'une des équations originales, on a :

Fosfate
0.05X1+ 0,10(14 000) = 1 800
X1= 8 000
Les coordonnées du sommet "B" sont (8000,14000).

Vértice "C": Potasium 0,10X1+ 0.05X2 = 2 000

Nitrate -(0.05X1+ 0,05X2= 1,100)
0,05X1 0 = 900
X1 = 18 000

Remplaçant X1on a : 0.10(18,000) + 0.05X2= 2 000

X2= 4 000

Les coordonnées du sommet "C" sont (18000,4000).

Dans le tableau suivant, un résumé des coordonnées de chaque sommet de la région faisable est donné et le
valeur de la Fonction Objectif :

Coordonnées Z = 185X1+ 200X2

Sommet (X1, X2) ($/mois)
Un 0 18 000 3 600 000
B 8,000 14,000 4280,000 ←Max. Z
C 18,000 4,000 4130,000
D 20 000 0 3 700 000
E 0 0 ["0"]

Trouver la solution optimale du problème.

Sur la base du tableau précédent, il est déterminé que la solution optimale se trouve au sommet "B" et est :
X1= 8 000
X2= 14,000
Máx. Z = 4280 000 $

Interprétation de la Solution Optimum.

Dans l'interprétation, il est important de se concentrer sur le type de variables que le problème manipule. Les variables peuvent
être de deux types : discrètes et continues. Les "variables discrètes" ne peuvent s'exprimer qu'en valeurs entières,
tandis que les « variables continues » peuvent s'exprimer en n'importe quelle valeur, entière ou fractionnée.

Ce problème a des variables continues, donc on peut faire l'interprétation suivante :

JEVA / PTI
15
PROGRAMMATION LINÉAIRE MÉTHODE GRAPHIQUE

Le programme de production pour le mois prochain sera de 8 000 tonnes de l'engrais 5-5-10 (X 1= 8 000)
y 14 000 tonnes de l'engrais 5-10-5 (X 2= 14,000) para tener la máxima utilidad de $4280,000 (Máx.
Z = 4280,000).
Après avoir réalisé ce programme de production, il restera 500 tonnes de potassium.

JEVA / PTI
16