Embed Size (px)
Citation preview
Cours de mathematiques - Alternance GeaProgrammation lineaire a plusieurs variables
Anne Fredet
2 janvier 2006
1 Definitions
Definition 1.1 Un programme lineaire est un programme consistant a trou-ver un extremum (maximum ou minimum) d’une fonction a plusieurs va-riables, verifiant en outre un systeme d’equations ou d’inequations, ces fonc-tions etant lineaires.
La methode graphique devient difficile a realiser lorsqu’il y a 3 variables,et impossible s’il y a plus de 3 variables. Il faut donc trouver une autremethode : celle du simplexe. Sous sa forme la plus generale, le modele deprogrammation lineaire est le modele d’optimisation suivant :
minimiser (ou maximiser) z(x) =n∑
i=1
cjxj fonction objectif
sous les contraintes
n∑j=1
aijxj
≤=≥
bi i = 1, · · · , m
Les nombres cj, aij, bi sont les parametres du modele, ils sont connus avantla resolution. Les variables de decision xj sont indetermines a priori.
Definition 1.2 On appelle :– point realisable tout point x qui satisfait aux contraintes,
1
– espace realisable ou polyhedre des contraintes l’ensemble des pointsrealisables,
– solution optimale un point realisable qui optimise (maximise ou mini-mise) z(x)
– valeur optimale la valeur de z(x) atteinte pour toute solution optimale.
2 Methode du simplexe
2.1 Idee
On sait que la solution, si elle existe, se trouve au moins sur un sommetdu domaine des solutions realisables, la recherche de la solution optimales’effectue uniquement sur ces sommets.L’algorithme du simplexe examine comme premiere solution un des sommets(en general l’origine), qui constitue la solution de base de l’algorithme. Puisil se deplace de sommet en sommet, afin d’ameliorer la fonction economiquea chaque etape. Apres un nombre fini d’iterations, il arrive a un sommet apartir duquel tout deplacement vers un autre sommet n’ameliore plus cettevaleur. On est alors au sommet optimal.
2.2 Systeme canonique
Pour appliquer la methode du simplexe, on suppose que le systeme estdonne sous forme canonique, c’est a dire qu’il comprend une contrainte depositivite pour chaque variable et que les autres contraintes sont des inegalitesmajorantes. On suppose de plus que la fonction objectif est a maximiser :
Definition 2.1 On appelle programme lineaire canonique un programme dutype
x1 ≥ 0...
xn ≥ 0a11x1 + · · ·+ a1nxn ≤ b1
...a1px1 + · · ·+ apnxn ≤ bp
max(c1x1 + · · ·+ cnxn)
2
Afin de resoudre ce systeme, on commence par transformer les inequationsdu syseme en equations, en ajoutant de nouvelles variables appeles variablesd’ecart. On obtient le systeme :
x1 ≥ 0...
xn ≥ 0e1 ≥ 0
...ep ≥ 0
a11x1 + · · ·+ a1nxn + e1 = b1...
a1px1 + · · ·+ apnxn + ep = bp
max(c1x1 + · · ·+ cnxn)
On notera Z la fonction objectif : Z = c1x1 + · · ·+ cnxn.On va considerer ce systeme sous forme de tableau afin de le resoudre :
x1 x2 · · · xn e1 e2 · · · ep
e1 a11 a12 · · · a1n 1 0 0 0 b1
e2 a21 a22 · · · a2n 0 1 0 0 b2
......
...ep ap1 ap2 · · · apn 0 0 · · · 1 bp
−Z c1 c2 · · · cp 0 0 · · · 0 0
Les variables correspondant a des coefficients non nuls de la fonction objectifsont des variables hors base. Elles ne figurent pas dans la premiere colonne.La solution de base est x1 = · · · = xn = 0 et e1 = b1, · · · , ep = bp. Dans cecas, la fonction economique vaut 0, les variables xi sont hors base.
2.3 Systeme generique
On peut transformer certaines contraintes afin d’obtenir un systeme generique :
1. Toute inegalite de la forme a1x1 + a2x2 + · · · + anxn ≥ b peut etretransformee en −a1x1 − a2x2 − · · · − anxn ≤ −
3
2. Toute egalite de la forme a1x1 + a2x2 + · · ·+ anxn = b peut etre trans-formee en deux inegalites a1x1 + a2x2 + · · · + anxn ≤ b et a1x1 +a2x2 + · · · + anxn ≥ b, c’est-a-dire a1x1 + a2x2 + · · · + anxn ≤ b et−a1x1 − a2x2 − · · · − anxn ≤ −b
2.4 Algorithme du simplexe
L’algorithme du simplexe consiste a parcourir le polyhedre des pointsrealisables de sommet en sommet jusqu’a ce qu’on ne puisse plus ameliorerla solution. Au point de depart, la fonction objectif est nulle, et il s’agit del’augmenter. Si certains de ses coefficients sont positifs, il apparait clairementqu’en augmentant l’une des variables correspondant a un coefficients positifs,on augmente cette fonction objectif. On a donc un critere d’obtention del’optimum : tant que la derniere ligne d’un tableau du simplexe contient aumoins un coefficient positif, la solution examinee peut etre amelioree.
Premiere etape : Recherche du pivot
Le pivot est un coefficient du tableau qui permet, grace a la methode dupivot, d’annuler tous les coefficients de la colonne contenant ce pivot, exceptecet element qui est ramene a 1 apres division de la ligne le contenant par cenombre.
1. Choix de la colonne pivotLa colonne pivot est definie a partir des coefficients de la fonctioneconomique.On cherche a se focaliser sur la variable qui, en augmentant, augmen-tera le plus possible la fonction objectif. Cette variable correspond auplus grand coefficient positif de la fonction objectif. Considerons lescoefficients c1, · · · , cn de la fonction economique. Parmi tous les coef-ficients positifs, on considere le plus grand. La colonne pivot est lacolonne qui le contient.S’il existe plusieurs coefficients correspondant a cette valeur positivemaximale, on peut choisir celui que l’on veut.La variable correspondante sera la variable entrante car elle ne va pluss’annuler.
4
Exemple 2.1 Si on considere le programme lineaire suivant :
x1 ≥ 0, x1 ≥ 0, x3 ≥ 0x1 + x2 ≤ 1
x2 ≤ 23x1 + 4x2 ≤ 12
x1 + x2 ≤ 3max(3x1 − x2 + x3)
En introduisant les variables d’ecart, on obtient
x1 ≥ 0, x1 ≥ 0, x3 ≥ 0x1 + x2 + e1 = 1
x2 + e2 = 23x1 + 4x2 + e3 = 12
x1 + x2 + e4 = 3max(3x1 − x2 + x3)
e1 ≥ 0, e2 ≥ 0, e3 ≥ 0, e4 ≥ 0
Le premier tableau se presente donc ainsi :
x1 x2 x3 e1 e2 e3 e4
e1 1 1 0 1 0 0 0 1e2 0 1 0 0 1 0 0 2e3 3 4 0 0 0 1 0 12e4 1 0 1 0 0 0 1 3−Z 3 −1 1 0 0 0 0 0
Le plus grand coefficient positif de la fonction economique est c1 = 3.La colonne pivot est donc la premiere colonne. La variable x1 est doncentrante.
2. Choix de la ligne pivotLa variable entrante va prendre la place d’une des variables de base,appele variable sortante. Il faut maintenant trouver quelle valeur maxi-mum peut prendre cette variable entrante afin de maximiser la fonctionobjectif. Pour cela, chaque coefficient de la derniere colonne est divisepar le coefficient correspondant de la colonne pivot : si la colonne pivot
5
est a1i
a2i...
api
ci
,
on calcule les rapports
bj
aji
pour j = 1, · · · , p lorsque aij > 0.
On obtient de cette facon, pour chaque contrainte prise separement, lavaleur maximal que peut prendre la variable entrante. On selectionne leplus petit rapport positif, correspondant a la contrainte la plus forte :on cherche l’indice k tel que
0 ≤ bk
aki
≤ bj
aji
en ne considerant les j que si aij > 0.
La k-ieme ligne est la ligne pivot, et aki est le pivot : la ligne pivot estla ligne k telle que bk
akisoit positif et minimal.
La variable correspondant a cette ligne est la variable sortante.
Exemple 2.2 Si on considere l’exemple precedent, on avait le tableausuivant :
x1 x2 x3 e1 e2 e3 e4
e1 1 1 0 1 0 0 0 1e2 0 1 0 0 1 0 0 2e3 3 4 0 0 0 1 0 12e4 1 0 1 0 0 0 1 3−Z 3 −1 1 0 0 0 0 0
La premiere ligne est la ligne pivot. Les seuls coefficients positifs nonnuls de cette colonne sont a11 = 1, a31 = 3 et a41 = 1. Calculons les
6
rapportsbj
a1jcorrespondants. On a
b1
a11
=1
1= 1
b3
a31
=12
3= 4
b4
a41
=3
1= 3
Le plus petit rapport est le premier, donc la ligne pivot est la premiere.Le pivot associe est a11 = 1. La variable entrante est x1 et la variablesortante est e1.
Deuxieme etape : Reduction du tableau
On divise la ligne pivot par le pivot puis on annule ensuite les coefficientsdu tableau situes au-dessus et au-dessous du pivot, en soustrayant la lignepivot aux autres lignes.
x1 x2 x3 e1 e2 e3 e4
x1 1 1 0 1 0 0 0 1e2 0 1 0 0 1 0 0 2e3 0 1 0 −3 0 1 0 9 on effectue L3 ← L3 − 3L1
e4 0 −1 1 −1 0 0 1 2 on effectue L4 ← L4 − L1
−Z 0 −4 1 −3 0 0 0 −3 on effectue L5 ← L5 − 3L1
La solution correspondante est definie par x1 = 1, x2 = x3 = 0, e1 = 0,e2 = 2, e3 = 9 et e4 = 2. La fonction economique vaut 3 en ce point.
Troisieme etape : Iteration
S’il existe un coefficient ci positif dans le nouveau tableau, on retourne a lapremiere etape (choix du pivot) puis a la deuxieme (reduction du tableau).On reitere ce processus jusqu’a ce que tous les coefficients de la fonctioneconomique soient negatifs.Cela se produira forcement.
Exemple 2.3 Si on reprend le tableau de l’exemple precedent, on avait Ilexiste un coefficient ci positif, a savoir c3 = 1. La troisieme colonne est donc
7
la colonne pivot. Le seul coefficient positif de cette colonne est a43 = 1, c’estdonc le pivot. On reduit le tableau et on obtient
x1 x2 x3 e1 e2 e3 e4
x1 1 1 0 1 0 0 0 1e2 0 1 0 0 1 0 0 2e3 0 1 0 −3 0 1 0 9x3 0 −1 1 −1 0 0 1 2−Z 0 −3 0 −2 0 0 −1 −5
Tous les coefficients de la fonction economique sont negatifs, on a donc lasolution optimale. Elle est definie par x1 = 1, x2 = 0, x3 = 2, e1 = 0, e2 =2, e3 = 9 et e4 = 0. Dans ce cas, max(3x1 − x2 + x3) = 5.
2.5 Autre exemple
On considere le programme lineaire suivantx1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 03x1 + 2x2 + 4x3 + 3x4 ≤ 70
7x1 + 8x2 + 10x3 + 12x4 ≤ 120x1 + x2 + x3 + x4 ≤ 15
max(6x1 + 112x2 + 7x3 + 8x4)
La resolution de ce programme nous donnes ces tableaux successifs :
x2 x3 x4 e1 e2 e3
e1 3 2 4 3 1 0 0 70e2 7 8 10 12 0 1 0 120e3 1 1 1 1 0 0 1 15−Z 6 11
27 8 0 0 0 0
La solution correspondante est x1 = x2 = x3 = x4 = 0 et e1 = 70, e2 = 120,e3 = 15. La variable entrante est x4 et la variable sortante est e2.
x1 x2 x3 x4 e1 e2 e3
e154
0 32
0 1 0 0 40 on effectue L1 ← L1 − 14L2
x4712
23
56
1 0 112
0 10 on effectue L2 ← 112
L2
e3512
13
16
0 0 − 112
1 5 on effectue L3 ← L3 − 112
L2
−Z 43
16−2
30 0 −2
30 −80 on effectue L4 ← L4 − 2
3L2
8
La solution correspondante est x4 = 10, e1 = 40 et e3 = 5, les autres variablesetant nulles. La fonction economique vaut 80.On cherche le pivot, et on le trouve sur la premiere colonne, trosieme ligne.La variable entrante est donc x1 et la variable sortante est e3 :
x1 x2 x3 x4 e1 e2 e3
e1 0 −1 1 0 1 0 −3 25 on effectue L1 ← L1 − 3L3
x4 0 −533
35
1 0 15−7
53 on effectue L2 ← L2 − 7
5L3
x1 1 45
25
0 0 −15
125
12 on effectue L3 ← 125L3
−Z 0 − 910−6
50 0 −2
5−36
15−96 on effectue L4 ← L4 − 16
5L3
Ce tableau est le dernier car tous les coefficients de la derniere ligne sontnegatifs. La solution optimale correspondante est x1 = 12, x4 = 3, e1 = 25.La fonction economique vaut en ce point 96.
2.6 Autre presentation
On peut ne pas garder les variables de la base dans la premiere colonne.La solution correspondante est alors definie par les coefficients nuls de lafonction objectif. Les autres variables seront nulles.On considere le programme lineaire suivant
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 03x1 + 2x2 + 4x3 + 3x4 ≤ 70
7x1 + 8x2 + 10x3 + 12x4 ≤ 120x1 + x2 + x3 + x4 ≤ 15
max(6x1 + 112x2 + 7x3 + 8x4)
La resolution de ce programme nous donnes ces tableaux successifs :
x1 x2 x3 x4 e1 e2 e3
3 2 4 3 1 0 0 707 8 10 12 0 1 0 1201 1 1 1 0 0 1 156 11
27 8 0 0 0 0
La solution correspondante est e1 = 70, e2 = 120, e3 = 15 (les coefficients de
9
la derniere ligne sont nuls) et x1 = x2 = x3 = x4 = 0. On obtient ensuite
x1 x2 x3 x4 e1 e2 e354
0 32
0 1 0 0 40712
23
56
1 0 112
0 10512
13
16
0 0 − 112
1 543
16−2
30 0 −2
30 −80
La solution correspondante est x4 = 10, e1 = 40 et e3 = 5, les autres variablesetant nulles. La fonction economique vaut 80.Le dernier tableau est :
x1 x2 x3 x4 e1 e2 e3
0 −1 1 0 1 0 −3 250 −53
335
1 0 15−7
53
1 45
25
0 0 −15
125
120 − 9
10−6
50 0 −2
5−36
15−96
Ce tableau est le dernier car tous les coefficients de la derniere ligne sontnegatifs. La solution optimale correspondante est x1 = 12, x4 = 3, e1 = 25.La fonction economique vaut en ce point 96.
2.7 Contraintes saturees et gains marginaux
Une contrainte est saturee au point solution si sa variable d’ecart est nulleen ce point.Les gains marginaux sont les nombres de la derniere ligne du tableau, situesdans les colonnes des variables d’ecart.Seuls les contraintes satures conduisent a des gains marginaux non nuls.
2.8 Exercices
Exercice 2.1 Resoudre le programmex1, x2, x3 ≥ 0
2x1 − x2 + 2x3 ≤ 72x1 − 4x2 ≤ 12
−4x1 + 3x2 + 8x3 ≤ 10max(2x1 + x2 + x3)
10
Exercice 2.2 Resoudre le programme
x1, x2, x3 ≥ 0x1 ≤ 100x2 ≤ 150
x1 + x2 + 2x3 ≤ 2002x1 + x2 + x3 ≤ 300
max(3x1 + 4x2 + 2x3)
Exercice 2.3 Resoudre le probleme suivant en utilisant l’algorithme du sim-plexe :Un artisan fabrique deux articles A et B necessitant chacun deux operations :un usinage et un traitement thermique. Le produit A subit un usinage d’1heure et un traitement thermique de 3h. B subit un usinage de 2h et untraitement thermique de 3h. De plus, 2kg de matiere premiere entrent dansla composition de A et 1kg dans celle de B. La fabrication de B se terminepar un travail de finition qui dure 1h.Toutes les 3 semaines, l’artisan dispose de l’atelier d’usinage pendant 80h etdu four pendant 150h. De plus, pendant cette periode, il ne peut pas consacrerplus de 35h au travail de finition ni stocker plus de 80kg de matiere premiere.Quelles quantites de A et B l’artisan doit-il fabriquer pendant cette periodesi la marge beneficiaire est de 30 euros pour l’article A et de 20 euros pourl’article B.
3 Methode duale
3.1 Definition
Si on compare le probleme (P1) :
maximiser z1 =∑n
j=1 cjxj
avec∑n
j=1 aijxj ≤ bi pour i = 1, · · · , m
avec le probleme (P2)
minimiser z2 =∑m
i=1 biyi
avec∑m
i=1 aijyi ≥ cj pour j = 1, · · · , n
On dit que P1 et P2 sont le primal et le dual d’un meme programme lineaire.Le programme dual d’un programme lineaire est un programme lineaire. Le
11
nombre de variables du dual est egal au nombre de contraintes du primal etle nombre de ses contraintes est egal au nombre de variables du primal.Par exemple
primal dualvariables :x1, x2 variables :y1, y2, y3, y4
contraintes : contraintes :a11x1 + a12x2 ≤ b1
a21x1 + a22x2 ≤ b2 a11y1 + a21y2 + a31y3 + a41y4 ≥ c1
a31x1 + a32x2 ≤ b3 a12y1 + a22y2 + a32y3 + a42y4 ≥ c2
a41x1 + a42x2 ≤ b4
fonction economique : fonction economique :z1 = c1x1 + c2x2 z2 = b1y1 + b2y2 + b3y3 + b4y4
La resolution du primal donne la solution du dual et reciproquement.Les donnees du primal sont utilisees horizontalement pour l’ecriture du pro-gramme. Ces memes donnees sont utilisees verticalement pour l’ecriture duprogramme dual. De plus, le type d’extremum du dual est le contraire decelui du primal.Si on considere le programme lineaire suivant :
2 variables independantes x1 et x2
4 contraintes :2x1 + x2 ≤ 1000x1 + x2 ≤ 800x1 ≤ 400x2 ≤ 700fonction economique : z1 = 20x1 + 30x2 a maximiser
La solution optimale de ce probleme est x1 = 100 et x2 = 700.Le programme dual du precedent est :
4 variables independantes y1, y2, y3 et y4
2 contraintes :2y1 + y2 + y3 ≥ 20y1 + y2 + y4 ≥ 30fonction economique : z2 = 1000y1 + 800y2 + 400y3 + 700y4 a minimiser
12
La valeur optimale de z2 est 23000. On a :
etat initial etat optimalx1 x2 e1 e2 e3 e4
2 1 1 0 0 0 10001 1 0 1 0 0 8001 0 0 0 1 0 4000 1 0 0 0 1 70020 30 0 0 0 0 0
x1 x2 e1 e2 e3 e4
0 0 1 −2 0 1 1001 0 0 1 0 −1 1000 0 0 −1 1 −1 3000 1 0 0 0 1 7000 0 0 −20 0 −10 23000
La solution optimale qui donne z1 = 23000 est x1 = 100, x2 = 700, e1 = 100,e2 = 0, e3 = 300 et e4 = 0.En regardant la derniere ligne du tableau, on trouve les valeurs correspondanta la solution optimale du probleme dual : y2 = 20 et y4 = 10, qui nous donnele bon resultat : z2 = 800× 20 + 700× 10 = 23000.On remarque que le dual du dual est le probleme initial.
3.2 Exercices
Exercice 3.1 Resoudreminimiser 80u1 + 50u2 + 80u3 + 35u4
u1 ≥ 0, u1 ≥ 0, u3 ≥ 0, u4 ≥ 0u1 + u2 + 2u3 ≥ 40
2u1 + u2 + u3 + u4 ≥ 20
4 Applications
Exercice 4.1 Une usine produit deux modeles de machines, l’une que l’onappellera modele A exige 2 kg de matiere premiere et de 30 heures de fabri-cation et donne un benefice de 7 euros. L’autre que l’on appellera B exige 4kg de matiere premiere et de 15 heures de fabrication et donne un benefice de6 euros . On dispose de 200 kg de matiere premiere et de 1200 h de travail.Quelle production doit on avoir pour obtenir un benefice maximal ?
Exercice 4.2 L’entreprise Duralumin fabrique des pieces en inox, de troistypes A, B et C ; elles sont fabriquees par lot de 50 dans un grand atelierou sont rassemblees deux machines de decoupe de l’inox, une emboutisseuse
13
et deux polisseuses ; chaque machine fonctionne 120 heures par mois. Lescaracteristiques de fabrication sont rassemblees dans le tableau suivant :
cout horaire lot A lot B lot Cdecoupe 20 euros 1h 1, 5h 1, 5h
emboutissage 30 euros 0, 5h 1hpolissage 40 euros 2h 1h 1h
inox (mat. premiere) 50 euros 85 euros 68 eurosprix de vente (H.T.) 200 euros 200 euros 210 euros
Quel est le programme de production optimal (pour un mois) ?
Exercice 4.3 Dans une cafeteria, on sert 2 sortes de desserts glaces, a basede cocktails exotiques, de glace et de fruits confits : la creole et la tropicale. Lacreole necessite 8cl de cocktail exotique, 2dl de glace et 15g de fruits confits.La tropicale necessite 5cl de cocktail exotique, 2dl de glace et 25g de fruitsconfits. Chaque jour, l’atelier de patisserie peut preparer 1600 cl de cocktailexotique, 520 dl de glace et 5 kg de fruits confits. Une creole est vendue 1,2euros et une tropicale 1 euro. Maximiser le profit.
Exercice 4.4 Un agriculteur peut utiliser 2 type d’engrais X et Y pourepandre sur ses cultures. Les besoins par an et par hectare de 60 kg depotasse, 120 kg de calcium et 90 kg de nitrates.
Pour une meme quantite, les 2 types d’engrais coutent la meme chose.Leur composition pour 10 kg est de :
– produit X : 1 kg de potasse, 3 kg de calcium, 3 kg de nitrates et 3 kgde produit neutre
– produit Y : 2 kg de potasse, 2 kg de calcium, 1 kg de nitrates et 5 kgde produit neutre
Question : Comment fertiliser les cultures a moindre cout ?
Exercice 4.5 Ce probleme a ete donne au DECF 2004.La Societe des Scieries Vosgienne (SSV) souhaite s’apprivisionner en bois dedifferentes essences courantes. Compte tenu de la demande actuelle en boisscie, elle souhaite acquerir au moins 200m3 de chene, au moins 160 m3 dehetre et au moins 300m3 de sapin.Les prix au m3 sur la marche traditionnel sont de 140 euros pour le chene,90 euros pour le hetre et 70 euros pour le sapin.Mais la SSV peut aussi profiter des offres de certains exploitants forestiers
14
dont les foretes ont ete devastees par la tempete du 26 decembre 1999 et quiproposent par lots, a moindre cout, du bois de qualite equivalente.Trois offres ont ete selectionnees :
– offre A : lots de 15m3 de chene, 15m3 de hetre, 20m3 de sapin. Prixd’un lot : 3840 euros.
– offre B : lots de 16m3 de chene, 8m3 de hetre, 24m3 de sapin. Prixd’un lot : 3960 euros.
– offre C : lots de 9m3 de chene, 24m3 de hetre, 12m3 de sapin. Prixd’un lot : 2880 euros.
1. Determiner le prix et la quantite de bois que souhaite acquerir la SSV,si elle se fournit sur le marche traditionnel et achete les quantites mi-nimales qu’elle desire acquerir.
2. L’objectif des questions suivantes est de determiner si la SSV a interet ase fournir sur la marche traditionnel ou a profiter des offres selctionnees.On supposera dans ce qui suit qu’elle choisit d’acheter uniquement deslots A,B et C.
(a) En notant respectivement a, b et c les quantites de lots A, B etC a acheter pour obtenir la quantite de bois desiree, ecrire laforme canonique du programme P , etablissant les contraintes etla fonction economique Z a minimiser pour satisfaire la SSV.
(b) Ecrire, sous forme canonique puis sous forme standard, le pro-gramme P
′, dual du programme P . On notera x, y et z les va-
riables duales, e1, e2, e3 les variables d’ecart du programme dualet Z
′la fonction economique du programme dual.
(c) Etablir les deux premiers tableaux permettant de resoudre le pro-gramme P
′par la methode du simplexe. Indiquer soigneusement
les variables entrantes et sortantes dans le premier tableau.
(d) Le troisieme tableau est le suivant :
x y z e1 e2 e3 Re1
54
0 0 1 −58− 5
12165
z 1320
0 1 0 120
− 160
150y 1
201 0 0 − 1
4012
45
Z′ −3 0 0 0 −11 −3 −52200
i. Montrer que ce tableau correspond a l’optimum, et determinerles nombres de lots A, B et C que la SSV doit acheter pourminimiser ses couts.
15
ii. Indiquer le prix minimum a payer par la SSV pour satisfaireses besoins. Quel est alors, en pourcentage, le rabais obtenupar rapport au prix du marche traditionnel ?
iii. Si la SSV desire acheter le nombre de lots A,B et C lui per-mettant de minimiser ses couts, la quantite de bois achetecorrespond-elle exactement a la quantite souhaitee ?
16
5 Solutions des exercices
Solution 2.1 En ajoutant les variables d’ecart, on s’interesse au systeme sui-vant :
x1, x2, x3, e1, e2, e3 ≥ 02x1 − x2 + 2x3 + e1 = 7
2x1 − 4x2 + e2 = 12−4x1 + 3x2 + 8x3 + e3 = 10
max(2x1 + x2 + x3)
En appliquant l’algorithme du simplexe, on obtient les tableaux suivants (lepivot est en rouge)
x1 x2 x3 e1 e2 e3
e1 2 −1 2 1 0 0 7e2 2 −4 0 0 1 0 12e3 −4 3 8 0 0 1 10−Z 2 1 1 0 0 0 0
La solution de base est alors x1 = x2 = x3 = 0, e1 = 7, e2 = 12, e3 = 10, Z =0.
x1 x2 x3 e1 e2 e3
x1 1 −12
1 12
0 0 72
e2 0 −3 −2 −1 1 0 5e3 0 1 12 2 0 1 24−Z 0 2 −1 −1 0 0 −7
La solution est alors x2 = x3 = e1 = 0, x1 = 72, e2 = 5, e3 = 24 et Z = 7.
x1 x2 x3 e1 e2 e3
x1 1 0 7 2 12
12
312
e2 0 0 34 5 1 3 77x2 0 1 12 2 0 1 24−Z 0 0 −25 −5 0 −2 −55
La solution est alors e1 = e3 = x3 = 0, x1 = 312, x2 = 24, e2 = 77 et Z = 55.
C’est la solution optimale car tous les coefficients de la fonction economiquesont negatifs ou nuls.
17
Solution 2.2 En ajoutant les variables d’ecart, on s’interesse au systeme sui-vant :
x1, x2, x3, e1, e2, e3, e4 ≥ 0x1 + e1 = 100x2 + e2 = 150
x1 + x2 + 2x3 + e3 = 2002x1 + x2 + x3 + e4 = 300max(3x1 + 4x2 + 2x3)
En appliquant l’algorithme du simplexe, on obtient les tableaux suivants (lepivot est en rouge)
x1 x2 x3 e1 e2 e3 e4
e1 1 0 0 1 0 0 0 100e2 0 1 0 0 1 0 0 150e3 1 1 2 0 0 1 0 200e4 2 1 1 0 0 0 1 300−Z 3 4 2 0 0 0 0
La solution de base est alors x1 = x2 = x3 = 0, e1 = 100, e2 = 150, e3 =200, e4 = 300, Z = 0.
x1 x2 x3 e1 e2 e3 e4
e1 1 0 0 1 0 0 0 100x2 0 1 0 0 1 0 0 150e3 1 0 2 0 −1 1 0 50e4 2 0 1 0 −1 0 1 100−Z 3 0 2 −3 0 0 0 −600
La solution correspondante est e2 = x1 = x3 = 0, e1 = 100, x2 = 150, e3 =50, e4 = 100, Z = 600.
x1 x2 x3 e1 e2 e3 e4
e1 0 0 −2 1 1 −1 −1 50x2 0 1 0 0 1 0 0 150x1 1 0 2 0 −1 1 0 50e4 0 0 −3 0 −1 −2 1 50−Z 0 0 −4 0 −1 −3 0 −750
La solution optimale est x1 = 50, x2 = 150, x3 = 0, Z = 750, e1 = 50, e2 =0, e3 = 0, e4 = 50 (tous les coefficients de la fonction objectif sont nuls).
18
Solution 2.3 On a le tableau suivant :
article A article B dispo maxusinage 1h 2h 80h
traitement thermique 3h 3h 150hmatiere premiere 2kg 1kg 80kg
finition 1h 35hmarge 30 20
Soit x la quantite d’articles A et y la quantite d’articles B fabriques en troissemaines. On s’interesse donc au programme lineaire suivant :
maximiser 30x + 20yx ≥ 0, y ≥ 0x + 2y ≤ 80
3x + 3y ≤ 1502x + y ≤ 80
y ≤ 35
c’est-a-dire
maximiser 30x + 20yx ≥ 0, y ≥ 0x + 2y ≤ 80x + y ≤ 502x + y ≤ 80
y ≤ 35
En ajoutant les variables d’ecart, cela nous donne le systeme suivant :
maximiser 30x + 20yx ≥ 0, y ≥ 0, e1 ≥ 0, e2 ≥ 0, e3 ≥ 0, e4 ≥ 0
x + 2y + e1 = 80x + y + e2 = 502x + y + e3 = 80
y + e4 = 35
19
On obtient le tableau suivant :
x y e1 e2 e3 e4
e1 1 2 1 0 0 0 80e2 1 1 0 1 0 0 50e3 2 1 0 0 1 0 80e4 0 1 0 0 0 1 35−Z 30 20 0 0 0 0 0
Le pivot est sur la premiere colonne, troisieme ligne. x est donc la variableentrante et e3 la variable sortante :
x y e1 e2 e3 e4
e1 0 32
1 0 −12
0 40e2 0 1
20 1 −1
20 10
x 1 12
0 0 12
0 40e4 0 1 0 0 0 1 35−Z 0 5 0 0 −15 0 −1200
Le pivot est maintenant sur la deuxieme colonne, deuxieme ligne. La variableentrante est y et la variable sortante est e2 :
x y e1 e2 e3 e4
e1 0 0 1 −3 1 0 10y 0 1 0 2 −1 0 20x 1 0 0 −1 1 0 30e4 0 0 0 −2 1 1 15−Z 0 0 0 −10 −10 0 −1300
Les coefficients de la derniere ligne etant tous negatifs, l’algorithme s’arrete.La solution optimale est donc x = 30, y = 20, e1 = 10, e4 = 15 et e2 = e3 = 0.Les contraintes deux et trois sont donc saturees. On retrouve bien les solutionsobtenues par la methode graphique.
Solution 3.1 il suffit d’effectuer la resolution de son dual :
maximiser 30x + 20yx ≥ 0, y ≥ 0x + 2y ≤ 80x + y ≤ 502x + y ≤ 80
y ≤ 35
20
Le dernier tableau de l’algorithme du simplexe est
x y e1 e2 e3 e4
e1 0 0 1 −3 1 0 10y 0 1 0 2 −1 0 20x 1 0 0 −1 1 0 30e4 0 0 0 −2 1 1 15−Z 0 0 0 −10 −10 0 −1300
La valeur minimale du probleme initial est donc 1300. Il correspond a u1 = 0,u2 = 10, u3 = 10 et u4 = 0.
Solution 4.1 Soit x le nombre d’appareils de modele A et y le nombre d’ap-pareils de modele B. On s’interesse donc au systeme suivant :
x ≥ 0, y ≥ 02x + 4y ≤ 200
30x + 15y ≤ 1200max(7x + 6y)
En introduisans les variables d’ecart, on obtientx ≥ 0, y ≥ 0, e1 ≥ 0, e2 ≥ 0
2x + 4y + e1 = 20030x + 15y + e2 = 1200
max(7x + 6y)
La methode du simplexe nous donne les tableaux suivants :
x y ∗ ∗e1 2 4 1 0 200e2 30 15 0 1 1200−Z 7 6 0 0 0
qui nous donne
e2 y ∗ ∗e1 0 3 1 − 1
15120
x 1 12
0 130
40−Z 0 5
20 − 7
30−280
21
On obtient
e2 e1 ∗ ∗y 0 1 1
3− 1
4540
x 1 0 −16
115
20−Z 0 0 −5
6− 2
30−380
La solution optimale est donc x = 20 et y = 40. Le benefice est alors de 380euros.
Solution 4.2 Soient x1, x2, x3 les quantites de pieces de type A, B, C fa-briquees. Chaque piece A coute 20 euros pour la decoupe, 0, 5 × 30 = 15euros pour l’emboutissage, 2× 40 = 80 euros pour le polissage et 50 euros dematiere premiere, soit 165 euros. Elle rapporte donc 200− 165 = 35 euros.Chaque piece B coute 1, 5× 20 = 30 euros pour la decoupe, 40 euros pour lepolissage et 85 euros de matiere premiere, soit 155 euros. Elle rapporte donc200− 155 = 45 euros.Chaque piece C coute 1, 5 × 20 = 30 euros pour la decoupe, 30 euros pourl’emboutissage, 40 euros pour le polissage et 68 euros de matiere premiere,soit 138 euros. Elle rapporte donc 210− 138 = 72 euros.On s’interesse au systeme suivant :
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0x1 + 0, 5x2 + 2x3 ≤ 120
1, 5x1 + x3 ≤ 1201, 5x1 + x2 + x3 ≤ 120
max(35x1 + 45x2 + 72x3)
En introduisans les variables d’ecart, on obtientx1 ≥ 0, x2 ≥ 0, x3 ≥ 0, e1 ≥ 0, e2 ≥ 0, e3 ≥ 0
x1 + 0, 5x2 + 2x3 + e1 = 1201, 5x1 + x3 + e2 = 120
1, 5x1 + x2 + x3 + e3 = 120max(35x1 + 45x2 + 72x3)
En utilisant la methode du simplexe, on considere le tableau suivant
x1 x2 x3 ∗ ∗ ∗e1 1 0, 5 2 1 0 0 120e2 1, 5 0 1 0 1 0 120e3 1, 5 1 1 0 0 1 120−Z 35 45 72 0 0 0 0
22
qui nous donne
x1 x2 e1 ∗ ∗ ∗x3 0, 5 0, 25 1 0, 5 0 0 60e2 1 −0, 25 0 −0, 5 1 0 60e3 1 0, 75 0 −0, 5 0 1 60−Z −1 27 0 −36 0 0 −4320
On obtient
x1 e3 e1 ∗ ∗ ∗x3
16
0 1 23
0 −13
40e2
43
0 0 −23
1 13
80x2
43
1 0 −23
0 43
80−Z −37 0 0 −18 0 −36 −6480
La solution optimale est donc obtenue en x1 = 0, x2 = 80, x3 = 40. Lebenefice est alors de 6480 euros.
Solution 4.3 Soit X le nombre de creoles vendues et Y le nombre de tropi-cales. On a
8X + 5Y ≤ 1600 (cocktail)2X + 2Y ≤ 520 (glace)
15X + 25Y ≤ 5000 (fruits)
On veut maximiser la fonction 1, 2X + Y . On a les tableaux suivants :
X Y ∗ ∗ ∗ 2nd membre rapportse1 8 5 1 0 0 1600 200e2 2 2 0 1 0 520 260e3 15 25 0 0 1 5000 1000/3F 12 10 0 0 0 0 0
En modifiant la ligne e1, cela nous donne
∗ Y e1 ∗ ∗ 2nd membre rapportsx 1 0, 625 0, 125 0 0 200 320e2 0 0, 75 −0, 25 1 0 120 160e3 0 15, 625 −1, 875 0 1 2000 128F 0 2, 5 −1, 5 0 0 −2400
23
En modifiant la ligne e3, cela nous donne
∗ ∗ e1 ∗ e3 2nd membrex 1 0 0, 2 0 −0, 04 120e2 0 0 −0, 16 1 −0, 048 24Y 0 1 −0, 12 0 0, 064 128F 0 0 −1, 2 0 −0, 16 −2720
On a donc X = 120 creoles et Y = 128 tropicales. Le profit est alors de 2720euros (et il reste 24dl de glace)
Solution 4.4 Soit x et y les quantites d’engrais X et Y utiliser par an et parhectare. On veut alors :
x + 2y ≥ 603x + 2y ≥ 1203x + y ≥ 90
min(x + y)
Solution 4.5 1. Sur le marche traditionnel, les 200m3 de chene couteraient200 × 140 euros, les 160m3 de sapin couteraient 160 × 90 euros et les300m3 de sapin couteraient 300 × 70 euros, soit un total de 63 400euros.
2. On s’interesse mainteant aux lots A,B et C
(a) On cherche donc a minimiser Z = 3840a + 3960b + 2880c aveca ≥ 0, b ≥ 0, c ≥ 0
15a + 16b + 9c ≥ 0 (chene)15a + 8b + 24x ≥ 160 (hetre)20a + 24b + 12c ≥ 300 (sapin)
(b) le dual P′est donc
maximiser Z′= 200x + 160y + 300z
avec
x ≥ 0, y ≥ 0, z ≥ 0
15x + 15y + 20z ≤ 384016x + 8y + 24z ≤ 39609x + 24y + 12z ≤ 2880
24
On obtient la forme standard en introduisant les variables decart :
maximiser Z′= 200x + 160y + 300z
avec
x ≥ 0, y ≥ 0, z ≥ 0, e1 ≥ 0, e2 ≥ 0, e3 ≥ 0
15x + 15y + 20z + e1 = 384016x + 8y + 24z + e2 = 39609x + 24y + 12z + e3 = 2880
(c) On a donc les tableaux suivants :
x y z e1 e2 e3
e1 15 15 20 1 0 0 3840e2 16 8 24 0 1 0 3960e3 9 24 12 0 0 1 2880
−Z′
200 160 300 0 0 0 0
La variable entrante est donc z et la variable sortante est e2. Onobtient alors :
x y z e1 e2 e3
e153
253
0 1 −56
0 540z 2
313
1 0 124
0 165e3 1 20 0 0 −1
21 900
−Z′
0 60 0 0 −12, 5 0 −49500
(d) Le troisieme tableau est le suivant :
x y z e1 e2 e3 Re1
54
0 0 1 −58− 5
12165
z 1320
0 1 0 120
− 160
150y 1
201 0 0 − 1
4012
45
Z′ −3 0 0 0 −11 −3 −52200
i. L’optimum est atteint au troisieme tableau car tous les co-efficients de la fonction economique sont negatifs ou nuls. Lemaximum de P
′est alors de 52 200 euros. C’est egalement le
minimum du probleme primal P . En derniere ligne du tableau3, on lit que les valeurs des variables reeles du primal permet-tant d’atteindre l’optimum sont a = 0, b = 11 et c = 3. Pourminimiser ses couts, la SSV doit donc acheter 0 lot A, 11 lotsB et 3 lots C. Le prix correpondant est 52 200 euros, ce uqiest plus interessant qu’au marche traditionnel.
25
ii. On cherche le rabais r tel que 1 + r = 5220063400
. On trouve r ≈0, 1767. Le rabais est donc de 17,67%.
iii. On a achete 3m3 de chene en trop (cela se lit dans la premierecolonne de la derniere ligne du tableau 3.
26
