Chapitre

PROGRAMMATION LINÉAIRE

De nombreuses décisions importantes auxquelles un gestionnaire d'entreprise est confronté se concentrent sur le meilleur

manière d'atteindre les objectifs de l'entreprise, sous réserve des restrictions imposées sur le

manager by the operating environment. These restrictions can take the form of
ressources limitées, telles que le temps, le travail, l'énergie, le matériel ou l'argent ; ou elles peuvent être

sous forme de directives restrictives, comme une recette pour faire des céréales ou
spécifications techniques. L'un des objectifs les plus fréquents des entreprises
est de réaliser le plus de profit possible ou, en d'autres termes, de maximiser le profit. Le
objectif des unités organisationnelles individuelles au sein d'une entreprise (tel qu'une production ou

Le département d'emballage vise souvent à minimiser les coûts. Lorsqu'un manager tente de

résoudre un type général de problème en recherchant un objectif qui est soumis à

les restrictions, la technique de science de la gestion appelée programmation linéaire est

fréquemment utilisé. Il existe deux types, le modèle de maximisation et le modèle de minimisation.

Il y a trois étapes dans l'application de la technique de programmation linéaire. D'abord,

le problème doit être identifié comme étant soluble par la programmation linéaire. Deuxièmement,

le problème non structuré doit être formulé comme un modèle mathématique. Troisièmement, le
le modèle doit être résolu en utilisant des techniques mathématiques établies. Le linéaire

La technique de programmation tire son nom du fait que la fonctionnelle

les relations dans le modèle mathématique sont linéaires, et la technique de solution
consiste en des étapes mathématiques prédéterminées - c'est-à-dire, un programme. Dans ce chapitre

nous nous préoccuperons de la formulation du modèle mathématique qui

représente le problème et ensuite en résolvant ce modèle en utilisant un graphique.
Objectifs généraux :

À la fin du chapitre, vous devriez être capable de :

apprécier l'utilisation et l'application de la programmation linéaire dans la décision-

faire
2. formuler un modèle pour résoudre des problèmes commerciaux en particulier sur le

maximisation et minimisation des ressources de l'entreprise ; et

 3. apprécier l'utilisation du graphique dans le problème de prise de décision.

Leçon 1 : Modèle de maximisation

Un modèle de programmation linéaire se compose de certains composants communs et

caractéristiques. Les composants du modèle comprennent des variables de décision, un objectif

fonction, et contraintes du modèle, qui consistent en des variables de décision et

paramètres. Les variables de décision sont des symboles mathématiques qui représentent des niveaux de

activity by the firm. For example, an electrical manufacturing firm desires to

produire des radios, des grille-pains et des réveils, où, et sont des symboles représentant

quantités variables inconnues de chaque article. Les valeurs finales de, et, telles que déterminées

par l'entreprise, constituent une décision (par exemple, l'équation des radios est une décision de l'entreprise

produire 100 radios).

À la fin de la leçon, vous devriez être capable de :

1. énumérer les composants du modèle de programmation linéaire;
2. appliquer le modèle de maximisation sur le problème de prise de décision;

3. formuler un programme linéaire de maximisation ; et

4. formulate mathematical model using a graph.

La fonction objective est une relation mathématique linéaire qui décrit

l'objectif de l'entreprise en termes de variables de décision. La fonction objectif
consiste toujours soit à maximiser soit à minimiser une certaine valeur (par exemple, maximiser le

profit ou minimiser le coût de production des radios).

Les contraintes du modèle sont également des relations linéaires des variables décisionnelles ;

ils représentent les restrictions imposées à l'entreprise par l'environnement opérationnel.

Les restrictions peuvent prendre la forme de ressources limitées ou de directives restrictives.
Par exemple, seules 40 heures de travail peuvent être disponibles pour produire des radios pendant

production. Les valeurs numériques réelles dans la fonction objective et les contraintes,
tels que les 40 heures de main-d'œuvre disponibles, sont des paramètres.

La section suivante présente un exemple de la façon dont un modèle de programmation linéaire

est formulé. Bien que cet exemple soit simplifié, il est réaliste et représente le
type de problème auquel la programmation linéaire peut être appliquée. Dans l'exemple, le
Les composants du modèle sont clairement identifiés et décrits. En étudiant attentivement
cet exemple, vous pouvez vous familiariser avec le processus de formulation linéaire
modèles de programmation.

Modèle de maximisation
Beaver Creek Pottery Company est une petite entreprise de métiers d'art gérée par un Autochtone.

Conseil tribal américain. L'entreprise emploie des artisans qualifiés pour produire de l'argile.

des bols et des tasses avec des motifs et des couleurs amérindiens authentiques. Les deux
les ressources principales utilisées par l'entreprise sont l'argile spéciale pour la poterie et la main-d'œuvre qualifiée.

Given these limited resources, the company desires to know how many bowls and
tasses à produire chaque jour afin de maximiser le profit. Cela est généralement appelé
comme un type de problème de mélange de produits. Ce scénario est illustré dans la Figure 2.1.
 Les deux produits ont les exigences en ressources suivantes pour la production
et le bénéfice par article produit (c'est-à-dire, les paramètres du modèle) :

Resource Requirements
Produit Travail Argile Bénéfice
(h./unité) (lb./unité) (par unité)
Bol 1 4 40
Mug 2 3 50

Il y a 40 heures de travail et 120 livres d'argile disponibles chaque jour pour

production. Nous allons formuler ce problème sous forme d'un modèle de programmation linéaire par

définir chaque composant du modèle séparément puis les combiner

composants en un seul modèle. Les étapes de ce processus de formulation sont
résumé comme suit :

Résumé des étapes de formulation du modèle de programmation linéaire

Étape 1 : Définir les variables de décision

Combien de bols et de tasses produire
Étape 2 : Définir la fonction objectif
Maximiser le profit
Étape 3 : Définir les contraintes
Les ressources (argile et main-d'œuvre) disponibles

Decision Variables
La décision à laquelle la direction est confrontée dans ce problème est de savoir combien de bols

et des tasses à produire. Les deux variables de décision représentent le nombre de bols
et des tasses à produire sur une base quotidienne. Les quantités à produire peuvent être
représenté symboliquement comme

1=

2=
La fonction objectif
L'objectif de l'entreprise est de maximiser le profit total. L'entreprise
Le profit est la somme des bénéfices individuels gagnés de chaque bol et tasse. Profit
Le bénéfice dérivé des bols est déterminé en multipliant le bénéfice unitaire de chaque bol, 40 $,

par le nombre de bols produits, 1De même, le profit tiré des mugs est dérivé

du profit unitaire d'une tasse, 50 $, multiplié par le nombre de tasses

produit 2 Ainsi, le profit total, que nous définirons symboliquement comme Z, peut être
exprimé mathématiquement comme$40x1+ 50$ x2En plaçant le terme maximiser dans
devant la fonction de profit, nous exprimons l'objectif de l'entreprise : maximiser le total
profit:
maximiser Z = 40x1+ 50$ 2

où
Z = bénéfice total par jour
$40x1profit des bols
$50x2profit des mugs
Contraintes du modèle
Dans ce problème, deux ressources sont utilisées pour la production : le travail et l'argile.
qui sont limités. La production de bols et de tasses nécessite à la fois de la main-d'œuvre et de l'argile. Pour

Chaque bol produit nécessite 1 heure de travail. Par conséquent, le travail utilisé pour le
la production de bols est1 1 heures. De même, chaque tasse nécessite 2 heures de travail;
Ainsi, le travail utilisé pour produire des tasses chaque jour est2 2heures. Le total du travail utilisé

par la société est la somme des montants individuels de travail utilisés pour chaque

product:
1 1+ 2 2

Cependant, la quantité de travail représentée par est limitée à 40 heures par jour;
Ainsi, la contrainte de travail complète est

1 1+ 2 2≤ 40 h
L'inégalité « inférieur ou égal à » (≤) est employée à la place d'une égalité.
car les 40 heures de travail sont une limitation maximale qui peut être utilisée, pas une
le montant qui doit être utilisé. Cette contrainte permet à l'entreprise une certaine flexibilité ; le

l'entreprise n'est pas limitée à utiliser exactement 40 heures mais peut utiliser n'importe quel montant
il est nécessaire de maximiser le profit, jusqu'à 40 heures comprises. Cela signifie donc qu'il est
possible d'avoir une capacité idle ou excédentaire (c'est-à-dire que certaines des 40 heures peuvent ne pas être

utilisé).
The constraint for clay is formulated in the same way as the labor constraint.
Parce que chaque bol nécessite 4 livres d'argile, la quantité d'argile utilisée quotidiennement pour

la production de bols est4x1 livres ; et parce que chaque tasse nécessite 3 livres
d'argile, la quantité d'argile utilisée quotidiennement pour les tasses est3x2 Étant donné que le montant de
l'argile disponible pour la production chaque jour est de 120 livres, la contrainte de matériel peut

être formulé comme

4x1+ 3x2≤ 120 lb
Une restriction finale est que le nombre de bols et de tasses produits doit être
soit zéro soit une valeur positive car il est impossible de produire des articles négatifs.
Ces restrictions sont appelées contraintes de non-négativité et sont exprimées
mathématiquement comme

1≥ 0, x2≥ 0
Le modèle de programmation linéaire complet pour ce problème peut maintenant être

résumé comme suit :

maximisez Z = 40x1+ 50$ 2
Sous réserve de

1 1+ 2 2≤ 40
4x1+ 3x2≤ 120
1, 2≥ 0
La solution de ce modèle aboutira à des valeurs numériques pour et qui vont
maximiser le profit total, Z. Comme une solution possible, considérez 1 = 5bols et 2=

10tasses. Tout d'abord, nous allons substituer cette solution hypothétique dans chacune des
contraintes afin de s'assurer que la solution ne nécessite pas plus de ressources
que les contraintes montrent sont disponibles :

15( +
) 2(10) ≤ 40
25 ≤ 40
et
4 ( 5+
) 3(10) ≤ 120
 50 ≤ 120
Because neither of the constraints is violated by this hypothetical solution, we say
la solution est faisable (c'est-à-dire, possible). En substituant ces valeurs de solution dans le

la fonction objective donne Z = 40 (5) + 50 (10) = 700 $. Cependant, pour le moment,

Nous n'avons aucun moyen de savoir si 700 $ est le profit maximum.
Considérons maintenant une solution de 1= 10bols et 2= 20mugs. Cette solution
résultats en un bénéfice de

( +
Z = 40 $10 ) $50(20)
= 400 +1,000
= $1,400
Bien que cela soit certainement une meilleure solution en termes de profit, cela est irréalisable.

(c'est-à-dire, pas possible) car cela viole la contrainte de ressource pour le travail :

1 (10 ) + 2 (20 ) ≤ 40
50 ≤ 40
La solution à ce problème doit maximiser le profit sans violer le
contraintes. La solution qui atteint cet objectif est 1= 24bols et 2= 8
des mugs, avec un bénéfice correspondant de 1 360 $. La détermination de cette solution est
présenté en utilisant l'approche de solution graphique dans la section suivante.
Solutions graphiques des modèles de programmation linéaire

Suite à la formulation d'un modèle mathématique, la prochaine étape dans le

L'application de la programmation linéaire à un problème de prise de décision consiste à trouver le

solution du modèle. Une approche commune de solution consiste à résoudre algébriquement le

ensemble de relations mathématiques qui forment le modèle soit manuellement soit en utilisant un

programme informatique, déterminant ainsi les valeurs des variables de décision.

Cependant, en raison des relations linéaires, certains modèles et solutions peuvent être
illustré graphiquement.
La méthode graphique est réalistiquement limitée aux modèles avec seulement deux décisions.
des variables, qui peuvent être représentées sur un graphique en deux dimensions. Des modèles avec

trois variables de décision peuvent être représentées graphiquement en trois dimensions, mais le processus est

assez encombrant, et les modèles avec quatre variables de décision ou plus ne peuvent pas être

graphiques du tout.
 Bien que la méthode graphique soit limitée en tant qu'approche de solution, elle est très

utile à ce stade de notre présentation de la programmation linéaire car elle donne un

image de la manière dont une solution est dérivée. Les graphes peuvent fournir une compréhension plus claire

de la manière dont les approches de solutions informatiques et mathématiques présentées dans

les chapitres suivants fonctionnent et, ainsi, une meilleure compréhension des solutions.

Solution Graphique d'un Modèle de Maximisation

Le modèle de mélange de produits sera utilisé pour démontrer le graphique
interprétation d'un problème de programmation linéaire. Rappelez-vous que le problème décrit
La tentative de Beaver Creek Pottery Company de décider combien de bols et de tasses produire.
produire quotidiennement, étant donné des quantités limitées de travail et d'argile.

Le modèle de programmation linéaire complet a été formulé comme

maximiser Z = 40x1+ 50$ 2

Sous réserve de

1 1+ 2 2≤ 40 h
4x1+ 3x2≤ 120lb d'argile

1, 2≥ 0
où
1=

2=
La figure 2.2 est un ensemble de coordonnées pour les variables de décision et, sur lequel le graphique

de notre modèle sera tracé. Notez que seul le quadrant positif est tracé (c'est-à-dire que le
quadrant où 1, 2sera toujours positif) en raison de la non-négativité
contraintes 1≥ 0 et x2≥ 0.
 La première étape pour tracer le graphique du modèle est de représenter les contraintes sur
le graphique. Cela se fait en traitant les deux contraintes comme des équations (ou des lignes droites)

et en traçant chaque ligne sur le graphique. Considérons d'abord la ligne de contrainte de travail :

1+ 2 2= 40
Une procédure simple pour tracer cette ligne consiste à déterminer deux points qui sont
sur la ligne puis tracer une ligne droite à travers les points. Un point peut être trouvé
en laissant et en résolvant pour 2:

0 +2 2 = 40

2= 20
Ainsi, un point se trouve aux coordonnées 1= 0 et x2= 20 Un deuxième point
peut être trouvé en laissant 2= 0et résoudre pour 1 :

1+ 2 (0) = 40

1= 40
Maintenant, nous avons un deuxième point, 1= 40, 2= 0. La ligne sur le graphique
représentant cette équation est tracé en reliant ces deux points, comme indiqué dans
Figure 2.3. Cependant, ceci n'est que le graphique de la ligne de contrainte et ne reflète pas
l'ensemble de la contrainte, qui inclut également les valeurs qui sont inférieures ou égales à
(≤) cette ligne. La représentation de la contrainte entière est montrée dans la Figure 2.4.
 Pour tester la validité de la contrainte de zone, nous vérifions deux points quelconques—
l'un à l'intérieur de la zone de contrainte et l'autre à l'extérieur. Par exemple, vérifiez le point A dans

Figure 2.4, qui se trouve à l'intersection de 1= 10, a et x2= 10. Remplaçant ces
valeurs dans la contrainte de travail suivante,
10 + 2(10) ≤ 40
30 ≤ 40 h
montre que le point A est en effet à l'intérieur de la zone de contrainte, car ces valeurs

pour 1 2produire une quantité qui ne dépasse pas la limite de 40 heures. Ensuite, nous
vérifiez le point B à et 1= 40 et x2 =30:

40 +2(30) ≤ 40
 100 ≤ 40 h

Le point B est manifestement en dehors de la zone de contrainte car les valeurs pour

1 2 produire une quantité (100) qui dépasse la limite de 40 heures.

Nous traçons la ligne pour la contrainte d'argile de la même manière que celle pour le

contrainte de travail - en trouvant deux points sur la ligne de contrainte et en les reliant

avec une ligne droite. D'abord, laissez 1= 0 et résolvez pour x2:

40 (0 ) +3 x2= 120

2= 40
L'exécution de cette opération donne un point, 1= 0, 2= 40. Ensuite, nous

, 2= 0et puis résoudre pour 1:

40 x1+ 3(0)= 120

130

Combinaison des deux graphiques individuels pour le travail et l'argile (Figures 2.4 et 2.5)
produit un graphique des contraintes du modèle, comme montré dans la Figure 2.6. L'ombrage
La zone dans la Figure 2.6 est la zone qui est commune aux deux contraintes du modèle. Par conséquent,
 c'est la seule zone du graphique qui contient des points (c'est-à-dire des valeurs pour 1 2)

qui satisferont les deux contraintes simultanément. Par exemple, considérez les points
R, S et T dans la Figure 2.7. Le point R satisfait aux deux contraintes ; ainsi, nous disons qu'il est un
le point de solution faisable. Le point S satisfait la contrainte d'argile mais dépasse la contrainte de main-d'œuvre.

contrainte ; ainsi, il est infaisable. Le point T ne satisfait à aucune contrainte ; ainsi, il est également

irréalisable.
La zone ombragée dans la Figure 2.7 est appelée la zone de solution faisable
car tous les points dans cette zone satisfont aux deux contraintes. Certains points à l'intérieur de cela

la zone de solution réalisable entraînera un maximum de profit pour Beaver Creek Pottery

Entreprise. La prochaine étape de l'approche de solution graphique est de localiser ce point.

La zone de solution faisable est

une zone sur le graphique qui est
limité par la contrainte
équations
The Optimal Solution Point
La deuxième étape de la méthode de solution graphique consiste à localiser le point dans

la zone de solution réalisable qui aboutira au plus grand profit total. Pour commencer le
analyse de solution, nous traçons d'abord la ligne de la fonction objectif pour un sélectionné arbitraire

niveau de profit. Par exemple, si nous disons que le profit, Z, est de 800 $, la fonction objective est

$800 = 40 1+ 50 2

Tracer cette ligne de la même manière que nous avons tracé les lignes de contrainte donne le graphique

montré dans la Figure 2.8. Chaque point sur cette ligne est dans la zone de solution faisable et va

résultant en un profit de 800 $ (c'est-à-dire, chaque combinaison de 1 2sur cette ligne donnera
une valeur Z de 800 $. Cependant, voyons si un profit encore plus grand sera toujours
fournir une solution réalisable. Par exemple, considérer des bénéfices de 1 200 $ et 1 600 $, comme

montré dans la Figure 2.9.

Une partie de la ligne de la fonction objective pour un profit de 1 200 $ est à l'extérieur de la

zone de solution faisable, mais une partie de la ligne reste dans la zone faisable.
Par conséquent, cette ligne de profit indique qu'il existe des points de solution réalisables qui donnent

un profit supérieur à 800 $. Maintenant, augmentons à nouveau le profit, à 1 600 $. Ce profit

la ligne, également montrée dans la Figure 2.9, est complètement en dehors de la zone de solution réalisable. Le

le fait qu'aucun point sur cette ligne ne soit faisable indique qu'un profit de 1 600 $ n'est pas
possible.
 Parce qu'un bénéfice de 1 600 $ est trop important pour les limitations des contraintes, car

comme montré dans la Figure 2.9, la question de la valeur du profit maximum demeure. Nous pouvons

voir à partir de la Figure 2.9 que le profit augmente à mesure que la ligne de la fonction objectif s'éloigne

de l'origine (c'est-à-dire, le point 1= 0, 2= 0). Étant donné cette caractéristique, le

le profit maximum sera atteint au point où la ligne de la fonction objective est
le plus éloigné de l'origine et touche toujours un point dans la zone de solution faisable.
Ce point est représenté comme le point B dans la Figure 2.10.

Pour trouver le point B, nous plaçons une règle parallèle à la fonction objective.
ligne$800 = 40 1+ 50 2dans la Figure 2.10 et éloignez-le de l'origine autant que possible

as we can without losing contact with the feasible solution area. Point B is referred
comme la solution optimale (c'est-à-dire la meilleure).

Les valeurs de solution

La troisième étape de l'approche graphique est de déterminer les valeurs.

de 1 2une fois que le point de solution optimal a été trouvé. Il est possible de
déterminer le 1 2coordonnées du point B dans la Figure 2.10 directement à partir du
graphique, comme montré dans la Figure 2.11. Les coordonnées graphiques correspondant au point

B dans la Figure 2.11 sont 1= 24 et 2= 8. This is the optimal solution for the
décision
variables dans le problème. Cependant, à moins qu'un graphique absolument précis ne soit dessiné,

il est souvent difficile de déterminer la solution correcte directement à partir du graphique. Un

une approche plus exacte consiste à déterminer les valeurs de solution mathématiquement une fois que le

Le point optimal sur le graphique a été déterminé. L'approche mathématique pour

la détermination de la solution est décrite dans les pages suivantes. Tout d'abord, cependant, nous allons

considérer quelques caractéristiques de la solution.

Dans la Figure 2.10, à mesure que la fonction objective était augmentée, le dernier point qu'il

toucher dans la zone de solution réalisable était à la limite de la solution réalisable

zone. Le point de solution est toujours sur cette frontière car la frontière contient
les points les plus éloignés de l'origine (c'est-à-dire, les points correspondant aux plus grands

profit). Cette caractéristique des problèmes de programmation linéaire réduit le nombre de

des points de solution possibles considérablement, de tous les points dans la zone de solution à juste

ces points sur la frontière. Cependant, le nombre de points de solution possibles est
réduit encore plus par une autre caractéristique des problèmes de programmation linéaire.

Le point de solution sera sur la frontière de la zone de solution réalisable et

à un des coins de la limite où deux lignes de contrainte se croisent. (Le
Les axes graphiques, vous vous souvenez, sont également des contraintes parce que 1≥ 0 et 2≥ 0).
Ces coins (points A, B et C dans la Figure 2.11) sont des saillies, ou des extrêmes, dans
la zone de solution réalisable ; elles sont appelées points extrêmes. Il a été prouvé
mathématiquement que la solution optimale dans un modèle de programmation linéaire sera toujours
se produire à un point extrême. Par conséquent, dans notre problème d'exemple, la solution possible

les points sont limités aux trois points extrêmes, A, B et C. L'extrême optimal
le point est le point extrême que la fonction objectif touche en dernier en quittant le
zone de solution faisable, comme indiqué dans la Figure 2.10.

D'après le graphique montré dans la Figure 2.10, nous savons que la solution optimale

le point est B. Parce que le point B est formé par l'intersection de deux lignes de contrainte, comme

illustré dans la Figure 2.11, ces deux lignes sont égales au point B. Ainsi, les valeurs de et
à cette intersection peut être trouvée en résolvant les deux équations simultanément.
D'abord, nous convertissons les deux équations en fonctions de 1:

1+ 2 2= 40

1= 40 −2 2

et
 4x1+ 3x2= 120
4x1= 120 − 3x2

1= 30 − 3x2 /4
Maintenant, nous laissons 1dans la première équation égal 1dans la deuxième équation

40 −2 2= 30 − 3x2 /4
et résoudre pour 2 :

5x2 /4 =10

2= 8
Substitution 2= 8 dans l'une des équations originales donné une valeur
pour 1 :

1= 40 −2 2

1= 40 −2(8)

1= 24
Thus, the optimal solution at point B in Figure 2.11 is 1= 24 et x2= 8.
Substituer ces valeurs dans la fonction objective donne le profit maximal,
Z = 40 x1+ 50 2

Z = 40(24) +50(8)
Z = $1,360
En ce qui concerne le problème original, la solution indique que si la poterie
l'entreprise produit 24 bols et 8 tasses, elle recevra 1 360 $, le maximum quotidien
profit possible (compte tenu des contraintes de ressources).

Étant donné que la solution optimale sera à l'un des points extrêmes,
A, B ou C, nous pouvons également trouver la solution en testant chacun des trois points pour voir

ce qui entraîne le plus grand profit, plutôt que de tracer la fonction objective
et en voyant quel point il touche en dernier en sortant de la zone de solution réalisable.
La figure 2.12 montre les valeurs de solution pour les trois points, A, B et C, et le
montant du profit, Z, à chaque point.
Comme indiqué dans la discussion de la Figure 2.10, le point B est la solution optimale
point car c'est le dernier point que la fonction objective touche avant de quitter le
zone de solution. En d'autres termes, la fonction objective détermine quel extrême
le point est optimal. Cela est dû au fait que la fonction objectif désigne le profit que
s'accumulera à partir de chaque combinaison de 1 2valeurs aux points extrêmes. Si
la fonction objective avait des coefficients différents (c'est-à-dire différents 1 2profit

des valeurs), un des points extrêmes autres que x B aurait pu être optimal.

Supposons un instant que le bénéfice pour un bol soit de 70 $ au lieu de 40 $.

et le bénéfice pour une tasse est de 20 $ au lieu de 50 $. Ces valeurs entraînent un nouveau

fonction objectifZ = 70 x1+ 20 x2 . If the model constraints for labor or clay are
non changé, la zone de solution réalisable reste la même, comme montré dans la Figure 2.13.
Cependant, l'emplacement de la fonction objective dans la Figure 2.13 est différent de celui-ci.
de la fonction objective originale dans la Figure 2.10. La raison de ce changement est que
les nouveaux coefficients de profit donnent à la fonction objective linéaire une nouvelle pente.
 La pente peut être déterminée en transformant la fonction objectif en
équation générale d'une droitey = a + bx, où y est la variable dépendante,
a est l'ordonnée à l'origine, b est la pente, et x est la variable indépendante. Pour notre échantillon

fonction objectif, 2la variable dépendante correspondant au jouet (c'est-à-dire, elle est sur le

axe vertical), et 1est la variable indépendante. Ainsi, la fonction objective peut

être transformé en l'équation générale d'une ligne comme suit :
Z = 70 x1+ 20 x2
20 x2= Z − 70 x1

Cette transformation identifie la pente de la nouvelle fonction objective comme

-7/2 (le signe moins indique que la ligne descend). En revanche, le
la pente de la fonction objective originale était-4/5.
Si nous déplaçons cette nouvelle fonction objective à travers la zone de solution faisable,

le dernier point extrême qu'il touche est le point C. Résolvant simultanément la contrainte
les lignes au point C donnent la solution suivante :
1= 30
4x1+ 3x2= 120
et

2= 40 − ( 4x1 /3)

2= 40 − 4(30)/3)

2= 0
Ainsi, la solution optimale au point C dans la Figure 2.13 est 1= 30bols 2=

0tasses, et = $2,100profit. Alterer les coefficients de la fonction objectif entraîne

une nouvelle solution.

Ce bref points. Tout d'abord, le point extrême optimal est déterminé par le
fonction objective, et un point extrême sur un axe du graphique est aussi susceptible d'être
la solution optimale est un point extrême sur un axe différent. Deuxièmement, la solution
est sensible aux valeurs des coefficients dans la fonction objectif. Si l'objectif
les coefficients de la fonction sont modifiés, comme dans notre exemple, la solution peut changer.

De même, si les coefficients de contrainte sont modifiés, l'espace de solution et la solution

les points peuvent également changer. Cette information peut avoir des conséquences sur la décision

Fabricant essayant de déterminer combien d'un produit produire. Sensibilité

analyse—l'utilisation de la programmation linéaire pour évaluer les effets des changements dans
paramètres du modèle.
Il convient de noter que certains problèmes n'ont pas un seul point extrême.
solution. Par exemple, lorsque la ligne de la fonction objective est parallèle à l'une des
les lignes de contrainte, un segment de ligne entier est limité par deux points de coin adjacents

qui sont optimaux ; il n'y a pas de point extrême unique sur la ligne de la fonction objectif. Dans
dans cette situation, il existe plusieurs solutions optimales. Cela et d'autres types irréguliers

les résultats de solution en programmation linéaire sont discutés à la fin de ce chapitre

Variable d'écart
Une fois que la solution optimale a été trouvée au point B dans la Figure 2.12, simultanément

des équations ont été résolues pour déterminer les valeurs de 1 2. Rappelez-vous que le
la solution se situe à un point extrême où les lignes de l'équation de contrainte se croisent avec

l'un l'autre ou avec l'axe. Ainsi, les contraintes du modèle sont considérées comme
équations (=) plutôt que ≤ ou ≥ inégalités.
Il existe une procédure standard pour transformer les contraintes d'inégalité ≤ en
équations. Cette transformation est réalisée en ajoutant une nouvelle variable, appelée un

variable de slack, à chaque contrainte.

Pour l'exemple de l'entreprise de poterie, les contraintes du modèle sont

1+ 2 2≤ 40 h. tableau de travail

1+ 3x2≤ 120 lb. de pâte d'argile

L'ajout d'une variable slack unique, 1, à la contrainte de travail et 2à

la contrainte pour l'argile donne lieu aux équations suivantes :

1+ 2 2+ 1= 40 heures. Prof de laboratoire

4 x1+ 3x2+ 2= 120 lb. de poterie

 Les variables d'écart dans ces équations, 1 2, prendra n'importe quelle valeur

nécessaire pour rendre le côté gauche de l'équation égal au côté droit.

Par exemple, considérons une solution hypothétique de 1= 5 et 2= 10. Substitution
ces valeurs dans les équations qui précèdent donnent

1+ 2 2+ 1= 40ℎ .
5 +2(10) + 1= 40ℎ .

1= 15 hr. de travail
et
4x1+ 3x2+ 2 = 120 lb. de poterie
5 ( 5+
)( 3)10 + 2= 120 lb d'argile

2= 70 .
Dans cet exemple, 1= 5bols et 2= 10les tasses représentent une solution qui
ne fait pas usage de la totalité du montant disponible de travail et d'argile. Dans le travail

la contrainte, 5 bols et 10 tasses nécessitent seulement 25 heures de travail. Cela laisse 15

heures qui ne sont pas utilisées. Ainsi, 1représente la quantité de travail inutilisé, ou de marge.

Dans la contrainte d'argile, 5 bols et 10 tasses nécessitent seulement 50 livres d'argile.

Il reste 70 livres d'argile inutilisées. Ainsi, 2représente le montant de non utilisé

argile. En général, les variables d'écart représentent la quantité de ressources inutilisées.

L'ultime instance de ressources inutilisées se produit à l'origine, où 1=

0 et 2= 0. Substituer ces valeurs dans les équations donne

1+ 2 2+ 1= 40
0 +2 0( +) s1= 40

1= 400ℎ .
et
4x1+ 3x2+ 2 = 120
4(0) +3(0) + s2= 120

2= 120 lb. de pâte d'argile

 Parce qu'aucune production n'a lieu à l'origine, toutes les ressources sont
non utilisé ; ainsi, les variables d'écart sont égales aux montants totaux disponibles de chacune

resource: 1= 40heures de travail et 2= 120livres d'argile.

Quel est l'effet de ces nouvelles variables d'écart sur la fonction objective ?
La fonction objective de notre exemple représente le profit obtenu à partir de
production de bols et de tasses
Z = 40x1+ 50x2
Le coefficient 40 est la contribution au profit de chaque bol; 50 est le
contribution au profit de chaque tasse. Qu'en est-il alors des variables d'écart et
contribuer ? Ils ne contribuent rien au profit car ils représentent des ressources inutilisées.

Les ressources. Le profit n'est réalisé qu'après que les ressources ont été mises à profit pour fabriquer des bols.

et tasses. En utilisant des variables d'écart, nous pouvons écrire la fonction objective comme

maximiser (Z) = 40x1+ 50x2+ 0s1+ 0 2

Comme dans le cas des variables de décision ( 1 2 ), les variables d'écart peuvent avoir

seules des valeurs non négatives car des ressources négatives ne sont pas possibles. Par conséquent,

pour cette formulation de modèle 1 , 2, 1 2≥ 0.

Le modèle de programmation linéaire complet peut être écrit dans ce qui est désigné
au format standard avec des variables d'amortissement comme suit :

maximiser (Z) = 40x1+ 50x2+ 0s1 + 0 2

Sous réserve de

1+ 2 2+ 0s1= 40

4x1+ 3x2+ 2= 120

1, 2, 1 2≥ 0.
Les valeurs de la solution, y compris le supplément à chaque point de solution, sont

résumé comme suit :

 La figure 2.14 montre la solution graphique de cet exemple, avec marge.
variables incluses à chaque point de solution

Résumé des étapes de solution graphique

Les étapes pour résoudre un modèle de programmation linéaire graphique sont

résumé ici :
1. Tracez les contraintes du modèle sous forme d'équations sur le graphique ; puis, en considérant

les inégalités des contraintes indiquent la zone de solution faisable.

2. Tracez la fonction objectif ; puis déplacez cette ligne loin de l'origine vers
localiser le point de solution optimal.
3. Résoudre des équations simultanées au point de solution pour trouver l'optimal
valeurs de solution.

Ou
1. Résoudre des équations simultanées à chaque point d'angle pour trouver la solution

values at each point.

2. Substituez ces valeurs dans la fonction objectif pour trouver l'ensemble de
valeurs qui résultent en la valeur Z maximale
Leçon 2 : Modèle de Minimisation

Comme mentionné au début de ce chapitre, il existe deux types de linéaires

problèmes de programmation : problèmes de maximisation (comme la poterie de Beaver Creek)

Exemple d'entreprise) et problèmes de minimisation. Un problème de minimisation est

formulé de la même manière de base qu'un problème de maximisation, sauf pour quelques petites

différences. Le problème d'échantillon suivant démontrera la formulation d'un

modèle de minimisation.
À la fin de la leçon, vous devriez être capable de :
1. énumérer les composants du modèle de programmation linéaire;
2. appliquer un modèle de minimisation au problème de prise de décision;

3. formuler la minimisation de la programmation linéaire ; et

4. formuler un modèle mathématique en utilisant un graphique.

Un agriculteur se prépare à planter une culture et doit fertiliser un champ. Il y a deux

des marques d'engrais parmi lesquelles choisir, Super-gro et Crop-quick. Chaque marque produit un

quantité spécifique d'azote et de phosphate par sac, comme suit :

Le champ du fermier nécessite au moins 16 livres d'azote et au moins 24

livres de phosphate. Super-gro coûte 6 $ par sac, et Crop-quick coûte 3 $.
le fermier veut savoir combien de sacs de chaque marque acheter afin de
minimiser le coût total de la fertilisation. Ce scénario est illustré dans la Figure 2.15.
Les étapes du processus de formulation du modèle de programmation linéaire sont

résumé comme suit :

Variables de Décision

L'objectif du fermier est de minimiser le coût total de la fertilisation. Le total

le coût est la somme des coûts individuels de chaque type d'engrais acheté. Le
La fonction objective qui représente le coût total est exprimée comme

maximiser (Z) = 6x1+ 3x2

où
6x1= −
3x2= −
Contraintes du modèle

Les exigences en azote et en phosphate représentent les contraintes de

le modèle. Chaque sac d'engrais contribue un nombre de livres d'azote et
phosphate sur le champ. La contrainte pour l'azote est
2 1+ 4x2≥ 16 lb.
où
2 1= ℎ ( ) −
4x2= ℎ ( ) −

Plutôt qu'une inégalité a≤(moins que ou égal à), comme utilisée dans le Castor
Modèle de la société Creek Pottery, cette contrainte exige que a≥(supérieur ou égal
à) inégalité. Cela est dû au fait que la teneur en azote pour le champ est un minimum
exigence spécifiant qu'au moins 16 livres d'azote doivent être déposées sur le
champ de fermier. Si une solution à coût minimum entraîne plus de 16 livres d'azote
sur le terrain, c'est acceptable ; cependant, le montant ne peut pas être inférieur à 16

livres.
La contrainte pour le phosphate est construite comme la contrainte pour l'azote :
4x1 + 3x2≥ 24 lb.
Avec cet exemple, nous avons montré deux des trois types de linéaire.
les contraintes du modèle de programmation, ≤ et ≥. Le troisième type est une égalité exacte, =.

Le type spécifie qu'une exigence de contrainte doit être exacte. Par exemple, si le
le fermier avait dit que le besoin en phosphate pour le champ était exactement de 24
livres, la contrainte aurait été
4x1+ 3x2≥ 24 lb.
Comme dans notre modèle de maximisation, il y a également des contraintes de non-négativité dans

ce problème pour indiquer que des sacs deengrais négatifs ne peuvent pas être achetés :

1, 2≥ 0
La formulation complète du modèle pour ce problème de minimisation est

maximiser (Z) = 6x1+ 3x2

Sous réserve de
 2 1+ 4x2≥ 16 lb. d'azote
4x1+ 3x2≥ 24 lb. de phosphate

1, 2≥ 0

Solution graphique d'un modèle de minimisation

Nous suivons les mêmes étapes de base dans la solution graphique d'une minimisation.
modèle comme dans un modèle de maximisation. L'exemple de l'engrais sera utilisé pour

démontrer la solution graphique d'un modèle de minimisation.

 La première étape consiste à tracer les équations des deux contraintes du modèle, comme
montré dans la Figure 2.16. Ensuite, la zone de solution réalisable est choisie, pour refléter le ≥

inégalités dans les contraintes, comme montré dans la Figure 2.17

Après avoir déterminé la zone de solution faisable, la deuxième étape dans le

l'approche de solution graphique consiste à localiser le point optimal. Rappelez-vous que dans un

problème de maximisation, la solution optimale se trouve à la frontière de la faisabilité

zone de solution qui contient le(s) point(s) le plus éloigné(s) de l'origine. La solution optimale
un point dans un problème de minimisation est également sur la frontière de la solution faisable

zone ; cependant, la frontière contient le(s) point(s) le plus proche de l'origine (zéro étant

le coût le plus bas possible).

Comme dans un problème de maximisation, la solution optimale se trouve à l'un des
points extrêmes de la frontière. Dans ce cas, les points d'angle représentent
extrémités à la limite de la zone de solution faisable qui sont les plus proches de la
origine. La figure 2.18 montre les trois points d'angle - A, B et C - et l'objectif
fonction ligne.
À mesure que la fonction objective se rapproche de l'origine, le dernier point qu'elle touche dans

le
la zone de solution réalisable est A. En d'autres termes, le point A est le plus proche de l'objectif

la fonction peut atteindre l'origine sans englober de points non réalisables. Ainsi, elle
correspond au coût le plus bas qui peut être atteint

La dernière étape de l'approche graphique est de résoudre pour les valeurs de

et au point A. Parce que le point A est sur le 2axe 1= 0;; donc,4 0 + 3x
( 2=) 24
2= 8
Étant donné que la solution optimale est 1 = 0, 2= 8, le coût minimum, Z, est
Z = 6x1+ 3x2
Z =6(0) + 3(8)
Z =$24
Cela signifie que le fermier ne devrait pas acheter de Super-gro mais, à la place,

should purchase eight bags of Crop-quick, at a total cost of $24.

Variables de surplus
Les contraintes de supérieur ou égal ne peuvent pas être converties en équations par
ajout de variables slack, comme avec des contraintes. Rappelons notre modèle d'engrais, formulé
as
maximiser (Z) = 6x1+ 3x2
Sous réserve de

2 1+ 4x2≥ 16 lb. d'azote

4x1+ 3x2≥ 24 lb de phosphate

1, 2≥ 0
où

1= −

2= −
= ′ ℎ
Parce que ce problème a des contraintes contrairement aux contraintes de le
Exemple de maximisation de la société Beaver Creek Pottery, les contraintes sont
converti en équations un peu différemment. Au lieu d'ajouter une variable de marge comme nous
avec une contrainte, nous soustrayons une variable excédentaire. Alors qu'une variable d'excès est

ajouté et reflète les ressources non utilisées, une variable de surplus est soustraite et reflète
l'excès au-dessus d'un niveau minimum de ressources requises. Comme une variable de marge, un

le surplus variable est symboliquement représenté par et doit être non négatif. Pour le
la contrainte d'azote, la soustraction d'une variable excédentaire donne
2 1+ 4x2− 1= 16
La variable de surplus transforme la contrainte d'azote en une équation.
Prenons par exemple la solution hypothétique

1= 0

2= 10
Substituer ces valeurs dans l'équation précédente donne
2(0) + 4(10) − 1= 16
− 1= 16 - 40
 − 1= 24 lb. d'azote
Dans cette équation, peut être interprété comme le montant supplémentaire d'azote au-dessus de

l'exigence minimale de 16 livres qui serait obtenue en achetant 10

sacs d'engrais Crop-quick. De manière similaire, la contrainte pour le phosphate est
converti en une équation en soustrayant une variable excédentaire, 2:

4x1+ 3x2− 2= 24
Comme c'est le cas avec les variables d'écart, les variables de surplus n'apportent rien à

le coût global d'un modèle. Par exemple, mettre de l'azote ou du phosphate supplémentaire
sur le terrain n'affectera pas le coût de l'agriculteur ; la seule chose qui affecte le coût est le

nombre de sacs d'engrais achetés. En tant que tel, la forme standard de cette linéaire
le modèle de programmation est résumé comme

maximiser (Z) = 6x1+ 3x2+ 0s1+0 s2

Sous réserve de

2 1+ 4x2− 1= 16
4x1+ 3x2− 2= 24

1, 2, 1, 2≥ 0
La figure 2.19 montre les solutions graphiques pour notre exemple, avec des variables de surplus.

inclus à chaque point de solution.

Exercices
1. La société de transformation de viande de Moore produit un mélange de hot-dogs de 1 000 livres

batches. Le mélange contient deux ingrédients : du poulet et du boeuf. Le coût

par livre de chacun de ces ingrédients est comme suit
Ingredient Coût/lb
Poulet Php75
Boeuf Php125

Chaque lot a les exigences de recette suivantes :

Au moins 500 livres de poulet
Au moins 200 livres de bœuf
Le ratio de poulet à bœuf doit être d'au moins 2 à 1. L'entreprise veut
know the optimal mixture of ingredients that will minimize cost. Formulate a
modèle de programmation linéaire pour ce problème
2. Résoudre le modèle de programmation linéaire suivant graphiquement :

= 4x1+ 5x2
Sous réserve de

1+ 2 2≤ 10
6x1+ 6x2≤ 36
1≤ 4
1, 2≥ 0