Programmation Linéaire

Exemples

Un Exemple de Modèle de Maximisation

L'entreprise d'images de poterie est une petite opération artisanale dirigée par le conseil tribal népalais autochtone.
l'entreprise emploie des artisans qualifiés pour produire des bols et des tasses en argile avec une authentique culture népalaise
designs et couleurs. Les deux ressources principales utilisées par l'entreprise sont une argile à poterie spéciale et
main-d'œuvre qualifiée. Étant donné ces ressources limitées, l'entreprise souhaite savoir combien de bols et
tasses à produire chaque jour afin de maximiser le profit. Ceci est généralement appelé un produit
type de problème de mélange. Les deux produits ont les exigences en ressources suivantes pour la production
et le profit par article produit (c'est-à-dire, les paramètres du modèle) :

Produit Exigences en matière de ressources

Travail (Hr./Unité)
Bol 1 4 40
Mug 2 3 50

Il y a 40 heures de travail et 120 kg d'argile disponibles chaque jour pour la production. Nous allons
formulez ce problème comme un modèle de programmation linéaire en définissant chaque composant du modèle
séparément puis en combinant les composants en un seul modèle. Les étapes de cette formulation
processus

Variables de décision

x1nombre de bols à produire

x2nombre de tasses à produire

La fonction objective

Maximiser Z = 40x1+50x2

Contraintes du modèle

1x1+ 2x2≤ 40 h.

4x1+ 3x2≤ 120 kg

Non-négativité

x1≥ 0, x2≥0
Le modèle de programmation linéaire pour ce problème peut maintenant être résumé comme suit

Max Z = 40x1+50x2
Sous réserve de

x1+ 2x2≤ 40

4x1+ 3x2≤ 120

x1≥ 0, x2≥0

Solution graphique de l'exemple 1 : Rappelons que le problème décrit l'entreprise Image Pottery.
essayer de décider combien de bols et de tasses produire quotidiennement, compte tenu de la quantité limitée de main-d'œuvre
et argile. Le modèle complet de programmation linéaire a été formulé comme :

Max Z = 40x1+50x2
Sous réserve de

x1+ 2x2≤ 40 ……………………….. (1)

4x1+ 3x2≤ 120……………………….. (2)

x1≥ 0, x2≥0

Où x1nombre de bols produits

x2nombre de mugs produits

La première étape pour tracer le graphique est de tracer les contraintes sur le graphique. Cela se fait en
traiter les deux contraintes comme des équations (ou des droites, ou prendre seulement le signe d'égalité) et tracer
chaque ligne sur le graphique.

En considérant la contrainte (1)

x1+ 2x2≤ 40

Prenant seulement le signe égal

x1+ 2x2= 40
Une procédure simple pour tracer cette ligne consiste à déterminer deux points qui se trouvent sur la ligne et ensuite
tracez une ligne droite à travers les points. Un point peut être trouvé en laissant x1= 0 et résolution pour
x2

(1) + 2x2= 40

x2= 20

Ainsi, un point est à la coordonnée x1= 0 et x2= 20. Un second point peut être trouvé en laissant
x2= 0 et résoudre pour x1

x1+ 2(0) = 40

x1= 40

Maintenant, nous avons un deuxième point, x1= 40, et x2= 0.

La ligne sur le graphique représentant cette équation est tracée en reliant ces deux points comme
montré dans le graphique. Cependant, ceci n'est que le graphique de la ligne de contrainte (1) et ne reflète pas le
contrainte entière, qui inclut également les valeurs inférieures ou égales à (≤) cette ligne.

Pour identifier la zone (région faisable) de la contrainte (1), en prenant (0, 0) comme point de test [mettant x1
= 0 et x2= 0 dans la contrainte (1)]

0 + 2 (0) ≤ 40

0 ≤ 40 (vrai)
c'est-à-dire que la région faisable se trouve du même côté que le point de test (c'est-à-dire l'origine (0,0)). [c'est-à-dire que la flèche va

vers le point d'essai].

[Notez qu'il n'est pas toujours nécessaire de prendre (0,0) comme point de test, nous pouvons prendre n'importe quel point]
sauf les points qui ne se trouvent pas sur la ligne et pour la contrainte ayant un RHS nul, nous
ne devrait pas prendre (0,0) comme point de test car la contrainte ayant un RHS zéro réussit toujours
à travers le (0,0)

En considérant la contrainte (2)

4x1+ 3x2≤ 120

Prendre uniquement le signe égal

4x1+ 3x2≤ 120

Quand x1= 0, x2= 40 c'est-à-dire (0, 40)

Quand x2= 0, x1= 30 c'est-à-dire (30,0)

Joindre ces deux points (0,40) et (30,0) dans le graphique donne la ligne de contrainte (2).

En prenant (0,0) comme point de test,

4(0) + 3(0) ≤ 120

0 ≤ 120

La zone faisable de cette contrainte se situe du même côté que le point de test [c'est-à-dire que la flèche va
vers le point de test
Pour les contraintes de non-négation (axe graphique) x 1≥ 0, x2≥ 0; seul le quadrant positif est
prendre comme indiqué dans le graphique (c'est-à-dire, le quadrant x)1et x2sera toujours positif).

X2
Graphique

45

40

35

30
(2)
25
A(0, 20)
20

15

10 B(24, 8)
5
C(30, 0) (1)
X1
0
5 10 15 20 25 30 35 40 45

La zone ombragée dans le graphique 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 x 1et x2) qui satisfera les deux
Les contraintes simultanément. Cette zone ombragée dans le graphique est appelée la zone de solution faisable.
car tous les points de cette zone satisfont aux deux contraintes. Certains points dans cette zone réalisable
la zone de solution permettra d'obtenir un maximum de profit pour l'Image Pottery Company.

Le point de solution sera à la frontière de la zone de solution feasible et à l'un des coins.
de la frontière où deux lignes de contrainte se croisent. Ces points de coin (point A, B, C et O dans
les points extrêmes.

Il a été démontré mathématiquement que la solution optimale dans un modèle de programmation linéaire sera
se produisent toujours à un point extrême.

Par conséquent, dans ce problème, les points de solution possibles sont limités aux quatre points extrêmes A,
B, C et O. Le point extrême optimal est celui qui donne la valeur maximale
(valeur minimale pour un problème de minimisation).
Maintenant, à partir du graphique, les points extrêmes (coins) et leurs valeurs respectives de la fonction objective sont

Extrême Coordonnée (à partir du graphique) Valeur de la fonction objective

valeur Max Z = 40x1+50x2

A (0,20) 1000
B (24, 8) 1360 (Max)
C (30, 0) 1200
O (0,0) 0
Ici, la valeur extrême B (24, 8) donne la valeur maximale. Par conséquent, la solution optimale (SO) est (24, 8) et
la valeur optimale est 1360.

En termes de problème original, la solution indique que l'entreprise de poterie produit 24

bols et 8 tasses, il recevra 1360 Rs, le bénéfice quotidien maximum possible (étant donné la ressource
contraintes).

Un exemple de modèle de minimisation

Un agriculteur se prépare à planter une culture au printemps et doit fertiliser un champ. Il y a deux
marques d'engrais à choisir, Super-gro et Crop-quick. Chaque marque produit un rendement spécifique
quantité d'azote et de phosphates par sac comme suit :

Marque Contribution Chimique

Azote (Kg/sac) Phosphate (Kg/sac)
Super-gro 2 4
Culture-rapide 4 3
Le champ du fermier nécessite au moins 16 kg d'azote et 24 kg de phosphate. Le Super-gro coûte
Rs60 par sac et Crop-quick coûte Rs30. L'agriculteur veut savoir combien de sacs de chacun.
marque à acheter afin de minimiser le coût total de fertilisation.

Solution

Variables de décision

Ce problème contient deux variables de décision, représentant le nombre de sacs de chaque marque de
engrais à acheter

x1sacs de Super-gro

x2sacs de Crop-quick

La fonction objectif

Minimiser Z = 60 x1+ 30 x2
Contraintes de modèle

2 x1+ 4 x2≥ 16 kg

4 x1+ 3 x2≥ 24 kg

Non-négativité

Ici, la non-négativité indique que des sacs de engrais négatifs ne peuvent pas être achetés.

x1≥0 x2≥0

La formulation complète du modèle pour ce problème de minimisation est

Minimiser Z = 60 x1+ 30 x2

Sous réserve de

2 x1+ 4 x2≥ 16

4 x1+ 3 x2≥ 24

x1≥0 x2≥0

Solutions graphiques d'un modèle de minimisation (exemple 2)

Nous suivons les mêmes étapes de base dans la solution graphique d'un modèle de minimisation que dans un
modèle de maximisation. Solution graphique de l'exemple d'engrais :

Minimiser Z = 60 x1+ 30 x2

Sous réserve de

2 x1+ 4 x2≥ 16 ……………….. (1)

4 x1+ 3 x2≥ 24 ………………. (2)

x1≥0 x2≥0

En considérant la contrainte (1)

2 x1+ 4 x2≥ 16
Prenant seulement le signe d'égalité

2 x1+ 4 x2= 16
Quand x1= 0 x2= 4 c'est-à-dire (0, 4)

Quand x2= 0 x1= 8 (8, 0)

Le joining de ces deux points (0, 4) et (8, 0) dans le graphique donne la ligne de contrainte (1).

En prenant (0, 0) comme point de test

2 (0) + 4 (0) ≥ 16

0 ≥ 16 (Faux)

Ainsi, la région faisable se trouve de l'autre côté du point de test (c'est-à-dire que la flèche va)
vers l'opposé du point de test).

Considérant la contrainte (2)

4 x1+ 3 x2≥ 24

Ne prendre que le signe égal

4 x1+ 3 x2= 24

Quand x1= 0 x2= 8 (0, 8)

Quand x2= 0 x1= 6 (6, 0)

Relier ces deux points (0, 8) et (6, 0) dans le graphique donne la ligne de contrainte (2).

Prenant (0, 0) comme point de test

4 (0) + 3 (0) ≥ 24

0 ≥ 24 (Faux)

Donc, la région faisable se trouve du côté opposé du point de test (c'est-à-dire que la flèche va)
vers le côté opposé du point de test).

Pour les contraintes de non-négativité (axe graphique) x 1≥ 0, x2≥0; seul le quadrant positif est
dessiné comme indiqué dans le graphique (c'est-à-dire, le quadrant x1et x2sera toujours positif).
Graphique
X2

9
A(0, 8)
8

2 B(4.8, 1.6)
1
C(8, 0)
0 X1
1 2 3 4 5 6 7 8 9

D'après le graphique, les points extrêmes sont

Extrême Coordonnée (du graphique) Valeur de la fonction objective

valeur Minimiser Z = 60 x1+ 30 x2
Un (0,8) 240 (min)
B (4.8, 1.6) 336
C (8,0) 480

Ici, le point extrême (0, 8) donne la valeur la plus basse, c'est-à-dire 240, donc la solution optimale (SO) est (0, 8) et
La valeur optimale (VO) est de 240 Rs.

Cela signifie que l'agriculteur ne devrait pas acheter de Super-gro mais, à la place, devrait acheter 8
sacs de Crop-quick, pour un coût total de 240 Rs.
Exemple 3 : Un menuisier a 90, 80 et 50 mètres de teck, de contreplaqué et de bois de rose. Le produit
A nécessite 2, 1 et 1 unité et le produit B nécessite 1, 2 et 1 unités de teck, contreplaqué et
bois de rose, resp. Si le produit A et B ont des bénéfices de 48 Rs et de 40 Rs par unité respectivement, alors
combien de chaque produit devrait être produit pour maximiser le profit. [PU 2007 printemps]
i. Donnez un modèle mathématique à ce problème de PL

ii. Résoudre le problème graphiquement

Solution :

Résumé des informations données sous forme de tableau

Type de bois Produit A Produit B Disponibilité (mètres)

Teck 2 1 90
Contreplaqué 1 2 80
Bois de rose 1 1 50
Profit Rs. 48 Rs. 40

Laissezx1indique le nombre de produit A à produire

x2dénote le nombre de produit B à produire

Puisque le profit de chaque produit est donné afin que l'objectif du problème donné soit
maximisation du profit total

Max Z = 48x1+ 40x2

Sous réserve de

2x1+ x2≤ 90 ……………..(1)

x1+ 2x2≤ 80 …………….(2)

x1+ x2≤ 50 …………….(3)

Non-négativité

x1≥0, x2≥0

Solution graphique

Considérant la contrainte (1)

2x1+ x2≤ 90

Prenant seulement le signe égal

2x1+ x2= 90

Quand x1= 0, x2= 90 (0, 90)

Quand x2= 0, x1= 45 c'est-à-dire (45, 0)

Relier ces deux points (0, 90) et (45, 0) dans le graphique donne la ligne de contrainte (1).

Prenant (0, 0) comme point de test

2 (0) +(0) ≤ 90

0 ≤ 90 (vrai)

Ainsi, la région réalisable se trouve du même côté que le point de test (c'est-à-dire que la flèche va vers
le point de test).

Considérant la contrainte (2)

x1+ 2x2≤ 80
Ne prenant que le signe d'égalité

x1+ 2x2= 80

Quand x1= 0, x2= 40 (0, 40)

Quand x2= 0, x1= 80 c'est-à-dire (80, 0)

Relier ces deux points (0, 40) et (80, 0) dans le graphique donne la ligne de contrainte (2).

Prenant (0, 0) comme point de test

(0) + 2 (0) ≤ 80

0 ≤ 80 (vrai)

Ainsi, la région faisable se trouve du même côté que le point de test (c'est-à-dire que la flèche va vers
le point de test).

En considérant la contrainte (3)

x1+ x2≤ 50
Prenant seulement le signe d'égalité

x1+ x2≤ 50

Quand x1= 0, x2= 50 c'est-à-dire (0, 50)

Quand x2= 0, x1= 50 c'est-à-dire (50, 0)

Rejoindre ces deux points (0, 50) et (50, 0) dans le graphique donne la droite de contrainte (3).

Prendre (0, 0) comme point de test

(0) + (0) ≤ 50

0 ≤ 50 (vrai)

Ainsi, la région réalisable se trouve du même côté que le point de test (c'est-à-dire que la flèche va vers)
le point de test).
x2
Graphique :
100

90

80

70

60

50
A(0, 40)
40
B(20, 30)
30

20

10 C(40, 10)
(45, 0)D x1
0
10 20 30 40 50 60 70 80 90 100

D'après le graphique, nous avons

Extrême Coordonnée (du graphe) Valeur de la fonction objective

valeur Max Z = 48x1+ 40x2

Un (0, 40) 1600

B (20, 30) 2160
C (40, 10) 2320 (Max)
D (45, 0) 2160

Ici, le point extrême (40, 10) donne une valeur maximale, c'est-à-dire 2320, donc la solution optimale (SO) est (40,
10) et la valeur optimale (OV) est de 2320 Rs
La société ExampleATV produit deux types de téléviseurs, l'Astro et le Cosmo. Il y a
deux lignes de production, une pour chaque ensemble, et il y a deux départements, tous deux utilisés dans
la production de chaque ensemble. La capacité de la ligne de production Astro est de 70 ensembles par jour.
La capacité de la ligne Cosmo est de 50 ensembles par jour. Dans le département A, des tubes d'image sont produits. Dans ce
le set Astro nécessite 5 heures de travail et le set Cosmo nécessite 4 heures de travail.
Actuellement, dans le département A, un maximum de 120 heures de travail et les heures peuvent être attribuées à
production des deux types de ensembles. Dans le département B, le châssis est construit. Dans ce département
le set Astro nécessite 4 heures de travail et le Cosmo nécessite également 2 heures de travail. Actuellement, dans
le département B peut affecter un maximum de 90 heures de travail par jour à la production des deux
types de collections. Les contributions au profit sont respectivement de 20 et 10 roupies pour chaque Astro et
Set Cosmo.
i. Formuler ce problème de PL.
ii. Résoudre ce problème de PL graphiquement.

Solution :

Résumé des informations données comme suit

Types de télévision Quotidien Utilisation de la main-d'œuvre par ensemble (Heures)
Profit
par
Capacité Départ A Départ B ensemble
Astro 70 5 4 20
Cosmo 50 4 2 10
Disponibilité totale 120 90

Laissezx1désigne la production quotidienne des ensembles Astro

x2dénote la production quotidienne des ensembles Cosmo

Fonction objective

Max Z = 20x1+ 10x2

Sous réserve de

x1≤ 70……………………..(1)

x2≤ 50……………………..(2)

x1+2x2≤ 120………………(3)

x1+x2≤ 90………………….(4)
x1≥ 0, x2≥0

Solution
En tenant compte de la contrainte (1)

x1≤ 70
Ne prenant que le signe d'égalité

x1= 70

Cela représente une ligne verticale à x1= 70

et, la région faisable est la zone à gauche de la ligne verticale x1= 70

Considérant la contrainte (2)

x2≤ 50

Prenant seulement le signe égal

x2= 50

Ceci représente une ligne horizontale à x2= 50

et, la région faisable est la zone en dessous de la ligne horizontale x2= 50

Considérant la contrainte (3)

x1+2x2≤ 120
Prendre seulement le signe d'égalité

x1+2x2= 120

Quand x1= 0, x2= 60 c'est-à-dire (0, 60)

Quand x2= 0, x1= 120 c'est-à-dire (120, 0)

Joindre ces deux points (0, 60) et (120, 0) dans le graphique donne la ligne de contrainte (3).

En prenant (0, 0) comme point de test

(0) + 2 (0) ≤ 120

0 ≤ 120 (vrai)
Ainsi, la région faisable se trouve du même côté que le point de test (c'est-à-dire que la flèche pointe vers
le point de test).

En tenant compte de la contrainte (4)

x1+x2≤ 90

Prendre seulement le signe égal

x1+x2= 90

Quand x1= 0, x2= 90 (0, 90)

Quand x2= 0, x1= 90 c'est-à-dire (90, 0)

Joindre ces deux points (0, 90) et (90, 0) dans le graphique donne la ligne de contrainte (4).

Prendre (0, 0) comme point de test

(0) + (0) ≤ 90

0 ≤ 90 (vrai)

Ainsi, la région faisable se situe du même côté que le point de test (c'est-à-dire que la flèche va vers
le point de test).

Graphique : x2

100

90
(4)
80 (1)

70

60
(3)
B(10.8,50) (2)
50 A(0, 50)

40

30 C(60, 30)

20 D(70, 20)

10
E(70, 0) x1
0
10 20 30 40 50 60 70 80 90 100 110 120
D'après le graphique, nous avons

Extrême Coordonnée (à partir du graphique) Valeur de la fonction objectif

valeur Max Z = 20x1+ 10x2
Un (0, 50) 500
B (10.8, 50) 716
C (60, 30) 1500
D (70, 20) 1600 (max)
E (70, 0) 1400
O (0, 0) 0

Ici, le point extrême (70, 20) donne une valeur maximale, c'est-à-dire 1600, donc la solution optimale (SO) est (70,
20) et la valeur optimale (OV) est de 1600 Rs.

Contraintes Actives et Inactives

Si, à l'optimalité (c'est-à-dire lorsque évalué à la solution optimale), le côté gauche d'un
la contrainte égale le côté droit, cette contrainte est dite active ou liant.
Ainsi, une contrainte d'égalité est toujours active. Une contrainte d'inégalité peut l'être ou non.
actif.

Géométriquement, une contrainte active est celle qui passe par la solution optimale.

Si une contrainte n'est pas active, on dit qu'elle est inactive.

Géométriquement, une contrainte inactive est celle qui ne passe pas par l'optimal
solution.

Slack et Surplus

À l'optimalité, chaque contrainte d'inégalité dans un modèle a une valeur de marge ou de surplus et pour
Les décisions réalisables, cette valeur est toujours non négative. Pour une contrainte donnée, le slack ou
la valeur ajoutée est nulle si et seulement si cette contrainte est active.

Pour une contrainte de type ≤, la différence entre le côté droit et le côté gauche
le côté (le montant inutilisé) s'appelle marge. Donc, la marge est liée à une contrainte ≤ ; c'est le
montant d'une contrainte qui n'est pas utilisée par une solution. Par exemple, si une contrainte dans un
le problème est que ≤ 100 heures et la solution nécessite l'utilisation de 90 heures de travail, donc
nous pouvons dire que la contrainte de travail a une marge de 10 heures. Ainsi, la marge est le montant par
dont le côté gauche d'une contrainte a ≤ est inférieur au côté droit de la contrainte.

Pour une contrainte de type ≥, la différence entre le côté gauche et le côté droit
(l'excédent) est appelé surplus. Ainsi, le surplus est lié à une contrainte a ≥ ; c'est le montant par
qu'une contrainte est dépassée par une solution. Par exemple, si une contrainte exige que le
le nombre d'unités du produit A qui sont fabriquées doit être ≥ 10, et une solution donne 12 unités
étant produit, nous pouvons dire qu'il y a un surplus de 2 unités. Ainsi, le surplus est le montant
par lequel le côté gauche de la contrainte ≥ dépasse le côté droit.

La détermination du flottement et de l'excédent est simple. Tout d'abord, notez si la contrainte est
une contrainte a ≤ ou a ≥. Ensuite, substituez les valeurs optimales des variables de décision dans la gauche
côté droit de la contrainte et résolvez. Ensuite, comparez la valeur résultante au côté droit
côté de la contrainte. La différence entre les deux est le montant de marge (pour a ≤
contrainte) ou surplus (pour une contrainte ≥).

Par exemple, supposons que nous avons la contrainte 2x1+ 3x2≤ 50 et que x1 = 4 et x2 =
5. Parce que c'est une contrainte ≤, nous savons que le relâchement plutôt que l'excédent est pertinent.
En substituant les valeurs de x1 et x2 dans le côté gauche de la contrainte, nous obtenons

2(4) + 3(5) = 23

Ceci est 27 de moins que la valeur du côté droit. Donc, le slack = 27.

Maintenant, supposons que nous avons la contrainte 4x1 + 2x2 ≥ 10 et x1 = 3 et x2 = 1. Parce que cela
est une contrainte ≥, nous savons qu'un excédent est impliqué. En substituant les valeurs de x1 et x2
dans le côté gauche, nous obtenons

4(3) + 2(1) = 14

Cela dépasse la valeur du côté droit de 10 de 4. Donc, le surplus = 4.

Considérez le problème suivant de programmation linéaire :

max 5000E + 4000F

sous réserve de

E + F ≥ 5

E - 3F ≤ 0

10E + 15F ≤ 150

20E + 10F ≤ 160

30E + 10F ≥ 135

E, F ≥ 0

i) Trouvez une solution optimale et la fonction objectif associée de ce programme linéaire.

ii) Quelles contraintes sont actives ? Quelles sont inactives ?
iii) Quelles sont les valeurs d'absence et de surplus associées à chaque contrainte ?
iv) Combien de points extrêmes la région faisable a-t-elle ?

Solution
La fonction objective donnée est

Max. Z= 5000E + 4000F

Et les contraintes sont

E+F>5 ... (1)

E - 3F < 0 ... (2)
10E + 15F < 150 ... (3)
20E + 10F < 160 (4)
30E + 10F > 135 ... (5)
E, F > 0
Pour la contrainte (1)

E+F>5
Ne prendre que le signe égal
E+F=5
 Quand E = 0, F = 5 (0, 5)
Quand F = 0, E = 5 c'est-à-dire (5, 0)

Prenant l'origine (0, 0) comme point d'essai (point de test)

ou 0+0>5
0 > 5 (faux)
c'est-à-dire que la région feasible se trouve du côté opposé du point d'essai (point de test).

Pour la contrainte (2)

E - 3F < 0
Prendre seulement le signe d'égalité

E - 3F = 0
Quand E = 0, F = 0 (0, 0)
Lorsque E = 6, F = 2 (6, 2)
[Remarque : Cette contrainte a un RHS nul pour passer par l'origine et nous n'avons jamais]
obtenir le prochain point en prenant F=0. Pour ce cas, il sera préférable de sélectionner une valeur de E de telle sorte que
manière d'avoir plusieurs coefficients de F]
Prenant (3, 5) comme point d'essai (point de test) [Si la ligne passe par l'origine alors
nous devons prendre le point de test sauf l'origine (0,0) et tout point qui touche la ligne
ou 3-3×5<0
ou 3 - 15 < 0
-12 < 0 (vrai)
c'est-à-dire que la région réalisable se trouve du même côté que le point d'essai ou le point de test.

Pour la contrainte (3)

10E + 15 F < 150
Prendre uniquement le signe d'égalité

10E + 15F = 150

Quand E = 0, F = 10 c'est-à-dire (0, 10)

Quand F = 0, E = 15 c'est-à-dire (15, 0)

Prendre l'origine (0, 0) comme point d'essai (point de test)

ou 10 × 0 + 15 × 0 < 150
0 < 150 (vrai)
c'est-à-dire que la région faisable se trouve du même côté que le point d'essai (point de test)
Pour la contrainte (4)

20E + 10F < 160

Prendre seulement le signe égal

20E + 10F = 160

Lorsque E = 0, F = 16 c'est-à-dire (0, 16)

Quand F = 0, E = 8 (8, 0)
Prenant le point d'origine (0, 0) comme point d'essai (point de test)

ou 20 × 0 + 10 × 0 < 160
0 < 160 (vrai)
c'est-à-dire que la région faisable se trouve du même côté que le point d'essai (point de test)

Pour la contrainte (5)

30E + 10F > 135

Prenant seulement le signe égal

30E + 10F = 135

Quand E = 0, F = 13.5 (0, 13.5)
Lorsque F = 0, E = 4,5 c'est-à-dire (4,5, 0)

Prenant l'origine (0, 0) comme point d'essai pour tester des points

ou 30 × 0 + 10 × 0 > 135
0 > 135 (faux)
c'est-à-dire que la région réalisable se trouve de l'autre côté de l'essai (point de test)
 Graphique : F
17
16
15
14
13
12
(4)
11

10

9 A(1.5, 9)

8
B(4.5, 7)
7
6
(5)
5

4 (2)
(1)
3
2 C(6,8, 2,3)
D(4, 1.8) (3)
1
E
0 1 2 3 4 5 6 7 8 neuf10 11 12 13 14 15

Depuis le graphique

Point Extrême (Coordonnées de Coin (E, F) Max. Z= 5000E + 4000F

Point)
Un 1,5, 9 5000 × 1,5 + 4000 × 9 = 43500
B 9 5000 × 4,5 + 4000 × 7 = 50500
C 4.5, 7 (Max)
7 5000 × 6,8 + 4000 × 2,3 = 43200
D
6.8, 2.3 5000 × 4 + 4000 × 1.8 = 27200
6.8, 2.3
4, 1.8
1.8
 Ici, le point d'angle (4,5, 7) donne la valeur maximale (c'est-à-dire 50 500). Par conséquent, la solution optimale.
(4,5, 7)
(ii) Ici, les contraintes (3) et (4) sont des contraintes actives car elles passent par l'optimal
la solution (4.5, 7) et les contraintes (1), (2) et (5) sont des contraintes inactives car elles ne
passer par la solution optimale (4,5, 7).
(iii) Comme nous le savons, le slack et le surplus sont associés uniquement aux contraintes inactives. Slack
est associé au signe ≤ et le surplus est associé au signe ≥.
Excédent pour la contrainte (1)

E+F>5
1,5 + 7 > 5
11,5 ≥ 5
Surplus = LHS-RHS = 11.5 - 5 = 6.5
Slack pour la contrainte (2)
E - 3F < 0
4,5 - 3 (7) < 0
– 16,5 < 0 (marge)
Maintenant, Slack = RHS-LHS = 0 - (- 16,5) = 16,5
Excédent pour la contrainte (5)

30E + 10F > 135

Ou, 30 × 4,5 + 10 × 7 > 135
205 > 135
Maintenant, Surplus = LHS – RHS = 205 - 135 = 70

(iv) Le faisable a à nouveau quatre points extrêmes

i.e. A(1.5, 9), B(4.5, 7), C(6.8, 2.3), D (4, 1.8)