Optimisation linéaire: Applications · Voir chier Ex1-Oak Products.xlsx MTH8415: Optimisation lin eaire: Applications 17/60 Solveur Excel Autres solveurs Approx. lin eaires Jeux

Solveur Excel Autres solveurs Approx. lineaires Jeux matriciels References

Optimisation lineaire: Applications

MTH8415

S. Le Digabel, Polytechnique Montreal

H2020(v2)

MTH8415: Optimisation lineaire: Applications 1/60


Plan

1. Optimisation lineaire avec le solveur de Excel

2. Autres solveurs

3. Application : Approximations lineaires

4. Application : Jeux matriciels

References




2. Autres solveurs



References



Introduction

I Outil integre dans Excel pour l’optimisation lineaire, nonlineaire, et en nombres entiers

I Optimisation lineaire avec le simplexe

I Avantages :I Simplicite d’utilisation. Base sur ExcelI Efficace pour des problemes de taille raisonnableI Outils pour l’analyse de sensibilite

I Inconvenients :I Pas adapte aux problemes de grande tailleI Difficilement integrable au sein d’autres applications

I Bonnes pratiques donnees dans [Ragsdale, 2010]



Principes de base

I Communication : Le fichier doit etre clair (noms, couleurs,commentaires, etc.)

I Fiabilite : Les sorties doivent etre correctes et consistantes

I Comprehension : On devrait pouvoir comprendre le modeleet verifier les resultats

I Flexibilite : Un modele devrait etre facilement modifiable lejour ou les donnees changent



Trucs (1/2)

I Organiser le format des donnees puis construire le modele apartir des donnees

I Ne jamais mettre de constante dans une formule maisl’adresse de la cellule contenant cette constante

I Les valeurs dont le sens est relie devraient etre situees prochesles unes des autres

I Les formules identiques devraient etre copiees/collees

I Le total d’une colonne devrait etre au bas de la colonne

I Le total d’une ligne devrait etre a droite de la ligne



Trucs (2/2)

I On lit habituellement de gauche a droite et de haut en bas.Un modele devrait respecter cet ordre

I Utiliser les caracteristiques de Excel pour distinguer variables,parametres, formules, etc.

I Utiliser des zones de textes et des commentaires pour faciliterla lecture du modele

I Laisser les parametres en orange



Variables d’optimisation

I Une cellule par variable

I Les placer sur une meme ligne dans des colonnes contigues

I Ajouter une particularite (couleur bleue) pour identificationrapide

I Placer le nom des variables dans les cellules juste au-dessus eta gauche (lecture facile des sorties)

I Optionnel : Fournir une valeur initiale aux variables



Fonction objectif

I Placer les coefficients de maniere similaire aux variables

I Calculer avec la fonction Excel SOMMEPROD (SUMPRODUCT)

I Placer le nom juste au-dessus ou nommer la cellule

I Ajouter une particularite (couleur jaune) pour identificationrapide



Contraintes

I Une contrainte par ligne

I Un seul nombre a droite dans une cellule distincte

I Toutes les variables a gauche

I Placer les coefficients dans colonnes correspondant auxvariables

I Faire le calcul (avec SOMMEPROD) du membre de gauche etplacer le resultat dans une cellule

I Placer le nom de la contrainte a gauche

I Ajouter particularite (couleur verte) pour identification rapide



Execution du solveurI Lancer l’interface du solveur depuis le menu Outils ou

Donnees

I Cellule cible a definir : fonction objectif (min/max)

I Cellules variables : variables de decision

I Contraintes : contraintes

I Via les Options du solveur :I Suppose non-negatif : contraintes de non negativite

I Indiquer Modele suppose lineaire

I Cocher Echelle automatique

I Cliquer sur Resoudre, puis Reponses (Sensibilite) et surOk

I Apres : Bien lire le message pour savoir si ca a marche



Exemple 1 : Oak Products

I [Weatherford, 1997]

I La compagnie Oak Products fabrique 6 types de chaises apartir de 11 composantes

I Chaque semaine on regarde l’inventaire des composantes eton etablit le plan de production

I Chaque type de chaise induit un profit unitaire

I Combien doit on produire de chaises de chaque type ?



Oak Products : Donnees



Oak Products : Variables et objectif

I Une variable de decision par type de chaise :x = (C,M,H,L,K,Q), avec :

I C : nombre de chaises Captain produitesI M (Mate)I H (American High)I L (American Low)I K (Spanish King)I Q (Spanish Queen)

I Profit : Fonction objectif a maximiser :

f(x) = 36C + 40M + 45H + 38L+ 35K + 25Q



Oak Products : Contraintes

I Une condition contrainte d’inventaire a respecter pourchacune des composantes (contraintes ≤) :I Nombre de grandes chevilles :

c1(x) = 8C + 12H + 8K + 4Q ≤ 1280I Nombre de petites chevilles :

c2(x) = 4C + 12M + 12L+ 4K + 8Q ≤ 1900. . .

I Nombre de dossiers type Spanish : c11(x) = K +Q ≤ 85

I Finalement, il y a des imperatifs de production a respecter : ilfaut produire des nombres positifs de chaises (contraintes ≥) :C ≥ 0, M ≥ 0, H ≥ 0, . . ., Q ≥ 0



Oak Products : Modele

maxC,M,H,L,K,Q

36C + 40M + 45H + 38L+ 35K + 25Q

s.c.

8C + 12H + 8K + 4Q ≤ 12804C + 12M + 12L+ 4K + 8Q ≤ 19004C + 4M + 4H + 4L+ 4K + 4Q ≤ 1090C +K +Q ≤ 190M +H + L ≤ 170. . .K +Q ≤ 85C,M,H,L,K,Q ≥ 0



Oak Products : Resolution

Voir fichier Ex1-Oak Products.xlsx



Exemple 2 : Blue Ridge Hot Tubs (BRHT)

I [Ragsdale, 2010]

I Modele :

Max. profit 350X1 + 300X2

Pompes X1 +X2 ≤ 200Main d’œuvre 9X1 + 6X2 ≤ 1566

Tuyaux 12X1 + 16X2 ≤ 2880non-negativite X1, X2 ≥ 0



BRHT : Rapport de sensibilite



BRHT : Sensibilite aux coefficients de l’objectifI Les valeurs appelees “Augmentation admissible” et “Reduction

admissible” pour les cellules variables indiquent la taille maximaledes variations du coefficient de l’objectif qui laissent la solutionoptimale inchangee (meme point extreme) en supposant que tousles autres coefficients restent inchanges

I Un zero pour “Augmentation admissible” ou “Reductionadmissible” indique qu’il existe plus d’une solution optimale

I L’intervalle admissible de changement decrit dans le rapport desensibilite n’est valable que si tous les autres coefficients restentfixes (i.e. seulement un est change)

I Si le changement sort de l’intervalle admissible, il faut resoudre leprobleme a nouveau pour en connaıtre l’impact sur la solutionoptimale (i.e. les nouvelles valeurs optimales des variables et del’objectif)



BRHT : Interpretation des couts reduits desvariables

I Pour une variable qui n’est pas a sa borne superieure ouinferieure, le cout reduit est de zero

I Pour une variable qui est a sa borne sup. ou inf., le coutreduit indique l’impact sur la valeur optimale de l’objectifd’une augmentation d’une unite de cette variable

I Une variable dont la valeur optimale est a son minimum a uncout reduit relie au changement minimum du coefficient del’objectif qui rend une augmentation de cette variableprofitable



BRHT : Sensibilite aux membres de droite descontraintes



BRHT : Sensibilite aux mdd des contraintesI Changer le membre de droite d’une contrainte :

I Peut changer la valeur optimale de l’objectifI Peut changer la solution optimale (un nouveau point extreme)

I Le rapport de sensibilite associe un cout ombre (shadow price)a chacune des contraintes. Celui-ci indique de combienl’objectif augmentera par unite d’augmentation du membre dedroite, en supposant que tous les autres parametres restentconstants

I Le cout ombre n’est valable que si le mdd reste dansl’intervalle admissible, defini par les valeurs de “Augmentationadmissible” et de “Reduction admissible”

I Les couts ombre correspondent aux opposes des couts reduitsdes variables d’ecart et aux solutions duales



BRHT : Sensibilite aux mdd des contraintesI Si la variation du mdd est dans cet intervalle, la nouvelle

valeur optimale de l’objectif se calcule comme suit :Variation de l’obj. = variation du mdd × cout ombre

I Le cout ombre des contraintes inactives est toujours zero :Changer la valeur du mdd d’une contrainte inactive n’affectepas la solution optimale

I Ces regles ne s’appliquent que si seulement un parametre(mdd) est modifie

I Le cout ombre indique seulement la variation de la valeuroptimale de l’objectif. Si la contrainte est active, changer sonmdd affecte l’ensemble des solution admissibles et mene a unenouvelle solution optimale. Pour trouver la nouvelle solutionoptimale, nous devons resoudre a nouveau le probleme



BRHT : Autre usage des couts ombre

I Supposons qu’un nouveau bain (le Typhoon-Lagoon) peutetre produit par BRHT. Son profit unitaire serait de 320$ etrequiert : 1 pompe (cout ombre = 200$), 8 heures de maind’œuvre (cout ombre = 16.67$), 13 pieds de tuyaux (coutombre = 0$)

I Est-il profitable de produire ce bain ?

I 320− 200× 1− 16.67× 8− 0× 13 = −13.33$ : Non

I Un produit dont le profit marginal est au dessous du coutmarginal de sa production (mesure avec les couts ombre desressources) ne peut etre produit dans une solution optimale (amoins d’ajouter une contrainte de production minimale)



BRHT : Solution degeneree

I La solution d’un POL est appelee degeneree si une desvariables de base est a sa borne superieure ou a sa borneinferieure

I On detecte une solution degeneree si l’augmentation ou ladiminution admissible pour le mdd d’une contrainte est a zero

I Dans ce cas, le rapport de sensibilite est difficilementinterpretable



Exemple 3 : Eastern Steel

I ES achete du minerai provenant de 4 mines et melange cesminerais pour obtenir de l’acier. La qualite de l’acier se mesureen fonction de la teneur du melange, selon 3 types d’elementA, B et C. Par tonne d’acier, il faut au moins 5 kilos de A,100 de B, 30 de C. A, B et C sont en quantites differentesdans le minerai des 4 mines exploitees et a des prix differents :

Mine 1 Mine 2 Mine 3 Mine 4A (kg/tonne) 10 3 8 2B (kg/tonne) 90 150 75 175C (kg/tonne) 45 25 20 37$/tonne 800 400 600 500

I Il faut determiner le melange a cout minimal



ES : Modele

I Variables : M1,M2,M3,M4 : Quantite de minerai des mines1 a 4 dans une tonne d’acier

I Modele :

min 800M1 + 400M2 + 600M3 + 500M4

s.c.

10M1 + 3M2 + 8M3 + 2M4 ≥ 5 (1)90M1 + 150M2 + 75M3 + 175M4 ≥ 100 (2)45M1 + 25M2 + 20M3 + 37M4 ≥ 30 (3)M1 +M2 +M3 +M4 = 1 (4)M1,M2,M3,M4 ≥ 0



ES : Rapport de sensibilite



ES : Questions

I De combien au maximum la mine 2 peut-elle augmenter sonprix sans voir ses ventes aupres de ES baisser ?Reponse : 66.85$

I De combien la mine 4 doit-elle baisser son prix pour reussir avendre son minerai a ES ?Reponse : 91.11$

I Sans renegocier le prix des minerais aupres des mines,comment ES peut-elle baisser son cout de minerai a 500$ partonne ?Possibilite 1 : Relaxer la contrainte (1) de 5 a 4.75(511.11− 0.25× 44.44 = 500)Possibilite 2 : Relaxer la contrainte (3) de 30 a 27.5(511.11− 2.5× 4.444 = 500)




2. Autres solveurs



References



Optimisation lineaire avec Matlab

I Pour resoudre minx∈Rn

f(x) = c>x

s.c.

Ax ≤ bDx = e` ≤ x ≤ u

I Executer la commande :

[x f flag output lambda] = linprog(c, A, b, D, e, l, u)

I lambda.ineqlin et lambda.eqlin permettent d’acceder auxvariables duales



CPLEX

I IBM CPLEX : Logiciel commercial

I Utilisation gratuite pour le monde academique

I Deux facons de l’utiliser : Via la ligne de commande ou enmode librairie



Autres solveurs

I Gurobi, Mosek

I AMPL / GAMS : Avec langage de modelisation

I GLPK, CLP (gratuits)

I Et beaucoup d’autres. Voir page Wikipedia de l’optimisationlineaire


https://en.wikipedia.org/wiki/Linear_programming

https://en.wikipedia.org/wiki/Linear_programming



2. Autres solveurs



References



IntroductionI On cherche a resoudre le systeme d’equations lineairesAx = b, c’est-a-dire trouver x = (xj) ∈ Rn tel que

n∑j=1

aijxj = bi pour i ∈ {1, 2, . . . ,m}

avec A = (aij) ∈ Rm×n, b = (bi) ∈ Rm et m > n (plusd’equations que d’inconnues)

I On suppose que A est de plein rang colonne (r(A) = n)

I La plupart du temps, ce systeme ne possede pas de solution

I On cherche donc une approximation, c’est-a-dire un pointx∗ ∈ Rn qui minimise une erreur entre

∑nj=1 aijx

∗j et bi pour

chaque equation (i)



Exemple

On veut trouver une approximation pour

x1 +x2 +x3 = 603x1 +2x2 +x3 = 100x1 +x2 = 31

x2 +x3 = 49

ou encore Ax = b avec A =

1 1 13 2 11 1 00 1 1

et b = (60, 100, 31, 49)



Residus

I On definit le vecteur de residus associe a une solution x ∈ Rnpar

r = (r1, r2, . . . , rm)

avec

ri = bi −n∑j=1

aijxj pour tout i = 1, 2, . . . ,m

I La meilleure approximation lineaire est celle qui minimise lanorme des residus, mais il y a plusieurs normes possibles



Normes des residusNorme p :

‖r‖p = ‖b−Ax‖p = (|r1|p + |r2|p + . . .+ |rm|p)1/p

Ce qui donne :

I Pour p = 1 (norme `1) :

‖r‖1 = |r1|+ |r2|+ . . .+ |rm|

I Pour p = 2 (norme euclidienne) :

‖r‖2 =√r21 + r22 + . . .+ r2m

I Pour p =∞ (norme `inf) :

‖r‖∞ = limp→∞

‖r‖p = maxi∈{1,2,...,m}

|ri|



Comparaison de differentes solutions

x1 x2 x3 r1 r2 r3 r4 ‖r‖1 ‖r‖2 ‖r‖∞

10 20 30 0 0 1 −1 2 1.4142 1

9 22 29 0 0 0 −2 2 2 2

11 18 31 0 0 2 0 2 2 2

11 20 29 0 −2 0 0 2 2 2

x∗`1 10 21 28 1 0 0 0 1 1 1

x∗`2 10.1429 20.5714 28.7143 0.5714 −0.2857 0.2857 −0.2857 1.4286 0.7559 0.5714

x∗`∞ 10.2 20.4 29 0.4 −0.4 0.4 −0.4 1.6 0.8 0.4



Solution pour p = 2I Revient a resoudre le probleme d’optimisation non lineaire

sans contrainte

minx∈Rn

m∑i=1

n∑j=1

aijxj − bi

2

I Il s’agit de la regression au sens des moindres carres, pourlaquelle on a une solution analytique donnee par

x∗ = (A>A)−1A>b

(preuve dans cours d’algebre)

I Si r(A) = n, (A>A)−1 et x∗ existent

I Pour l’exemple, on obtient

x∗ = x∗`2 = (10.1429, 20.5714, 28.7143)



Solution pour p = 1 : Modele lineaireAvec A> = [a1 a2 . . . am] (i.e. ai : ieme ligne de A), on veutresoudre

minx∈Rn

‖b−Ax‖1 = minx∈Rn

m∑i=1

∣∣∣bi − a>i x∣∣∣= min

x∈Rn,τ∈Rm

m∑i=1

τi s.c. τi ≥∣∣bi − a>i x∣∣ , i = 1, 2, . . . ,m

= minx∈Rn,τ∈Rm

m∑i=1

τi s.c.

{τi ≥ bi − a>i x i = 1, 2, . . . ,mτi ≥ −bi + a>i x i = 1, 2, . . . ,m

= minx∈Rn,τ∈Rm

1>τ s.c.

{Ax+ τ ≥ b−Ax+ τ ≥ −b

(avec 1 = (1, 1, . . . , 1))



Solution pour p = 1 : Dual

I Primal (n+m variables, 2m contraintes) :min

x∈Rn,τ∈Rm1>τ

s.c.

{Ax+ τ ≥ b (u)−Ax+ τ ≥ −b (v)

I Dual (2m variables, m+ n contraintes) :maxu,v∈Rm

b>u− b>v

s.c.

A>u−A>v = 0 (x)

u+ v = 1 (τ)u, v ≥ 0



Solution pour p = 1 : Dual simplifie

I A partir du dual :maxu,v∈Rm

b>u− b>v

s.c.

A>u−A>v = 0

u+ v = 1u, v ≥ 0

I On pose v = 1− u et le probleme devient

−b>1+ 2 maxu∈Rm

b>u

s.c.

{A>u = 1

2A>1

0 ≤ u ≤ 1

(m variables, n contraintes)



Solution pour p = 1 : Pour l’exempleI Il faut resoudre

maxu1,...,u4

60u1 + 100u2 + 31u3 + 49u4

s.c.

u1 + 3u2 + u3 = 5/2u1 + 2u2 + u3 + u4 = 5/2u1 + u2 + u4 = 3/20 ≤ u1, u2, u3, u4 ≤ 1

I La solution est u∗ = (1, 1/4, 3/4, 1/4) qui permet de retrouver

x∗ = x∗`1 = (10, 21, 28)

de valeur

‖r‖1 = −b>1+ 2b>u∗ = −240 + 241 = 1



Solution pour p =∞ : Modele lineaire

On veut resoudre

minx∈Rn

‖b−Ax‖∞ = minx∈Rn

maxi=1,2,...,m

∣∣∣bi − a>i x∣∣∣= min

x∈Rn,τ∈Rτ s.c. τ ≥

∣∣bi − a>i x∣∣ , i = 1, 2, . . . ,m

= minx∈Rn,τ∈R

τ s.c.

{τ ≥ bi − a>i x i = 1, 2, . . . ,mτ ≥ −bi + a>i x i = 1, 2, . . . ,m

= minx∈Rn,τ∈R

τ s.c.

{Ax+ τ1 ≥ b−Ax+ τ1 ≥ −b



Solution pour p =∞ : Dual

I Primal (n+ 1 variables, 2m contraintes) :

minx∈Rn,τ∈R

τ s.c.

{Ax+ τ1 ≥ b (u)−Ax+ τ1 ≥ −b (v)

I Dual (2m variables, n+ 1 contraintes) :maxu,v∈Rm

b>u− b>v

s.c.

A>u−A>v = 0 (x)1>u+ 1>v = 1 (τ)

u, v ≥ 0



Solution pour p =∞ : Pour l’exempleI Il faut resoudre

maxu1,...,v4

60(u1− v1) + 100(u2− v2) + 31(u3− v3) + 49(u4− v4)

s.c.

u1 − v1 + 3(u2 − v2) + u3 − v3 = 0u1 − v1 + 2(u2 − v2) + u3 − v3 + u4 − v4 = 0u1 − v1 + u2 − v2 + u4 − v4 = 0u1 + u2 + u3 + u4 + v1 + v2 + v3 + v4 = 1u1, . . . , u4, v1, . . . , v4 ≥ 0

I La solution est (u∗, v∗) = (0.4, 0, 0.2, 0, 0, 0.2, 0, 0.2) quipermet de retrouver

x∗ = x∗`∞ = (10.2, 20.4, 29)

de valeur‖r‖∞ = 0.4




2. Autres solveurs



References



Introduction : Exemple

I Jeu du “roche, papier, ciseaux” pour deux joueurs

I Chaque joueur possede trois strategies pures : {P,R, S}

I Matrice de profit A :

P R S

P 0 1 −1R −1 0 1S 1 −1 0



Strategies

I Strategie du joueur 1 : Tirer p au hasard dans [0; 1] et :

Si p ∈ [0; 1/2] → jouer PSi p ∈]1/2; 5/6] → jouer R

Si p ∈]5/6; 1] → jouer S

I Cette strategie mixte est representee par le vecteurstochastique x = (1/2, 1/3, 1/6)

I Tout vecteur x ∈ R3 tel que x ≥ 0 et 1>x = 1 definit unestrategie mixte

I Similairement, le joueur 2 joue une strategie mixte y ∈ R3

avec y ≥ 0 et 1>y = 1



Profit moyenI Le profit moyen du joueur 1 est donne par :

∑i,j∈{P,R,S}

Ai,j×P (joueur 1 joue i)×P (joueur 2 joue j) = x>Ay

I Pour l’exemple :

x>Ay =

[1

2

1

3

1

6

]>A

y1y2y3

= −1

6y1 +

1

3y2 −

1

6y3

I Si le joueur 2 joue y = (1/3, 1/3, 1/3), alors le profit moyendu joueur 1 est 0. Si y = (1/2, 1/4, 1/4), le profit devient−1/24 : Sur le long terme, le joueur 1 aura paye 1/24$ aujoueur 2 par partie



Strategie du joueur 2 en reponse au joueur 1

I Si le joueur 2 connaıt la strategie du joueur 1, il devrait choisiry avec le modele d’OL suivant :

miny∈R3

x>Ay = −1

6y1 +

1

3y2 −

1

6y3

s.c.

{y1 + y2 + y3 = 1

y1, y2, y3 ≥ 0dont la solution est de la forme y = (k, 0, 1− k) aveck ∈ [0; 1] pour un profit moyen de −1/6(a montrer en exercice)

I Donc le joueur 1 devrait changer de strategie



Strategies d’equilibre

I (x, y) sont des strategies d’equilibre si x est la meilleurereponse a y et si y est la meilleure reponse a x

I C’est a dire :

x ∈ argmaxx∈X

x>Ay avec X ={x ≥ 0 : 1>x = 1

}ety ∈ argmin

y∈Yx>Ay avec Y =

{y ≥ 0 : 1>y = 1

}I On recherche de telles solutions



Chercher les strategies d’equilibre

I Le joueur 1 doit anticiper la strategie du joueur 2 et resoudremaxx∈X

x>Ay ou y resout miny∈Y

x>Ay

I Le joueur 1 doit donc resoudre

maxx∈X

(miny∈Y

x>Ay

)

I Et le joueur 2 doit resoudre

miny∈Y

(maxx∈X

x>Ay

)



Duaux des deux problemes a resoudre

(1) maxx∈X

(miny∈Y

x>Ay

)= max

x∈Rn,z∈Rz

s.c.

1>z − x>A ≤ 0

1>x = 1x ≥ 0

(2) miny∈Y

(maxx∈X

x>Ay

)= min

y∈Rn,w∈Rw

s.c.

1w −Ay ≥ 0

1>y = 1y ≥ 0

De plus (2) est le dual de (1)



Theoreme du minimax

Theoreme

maxx∈X

(miny∈Y

x>Ay

)= min

y∈Y

(maxx∈X

x>Ay

)

Corollaire

Il existe toujours des strategies d’equilibre

En effet, si (x, z) resout (1) et si (y, w) resout (2), alors (x, y)sont des strategies d’equilibre



Strategie d’equilibre pour roche, papier, ciseauxI Le joueur 1 doit resoudre

maxz,x1,x2,x3

z

s.c.

z + x2 − x3 ≤ 0z − x1 + x3 ≤ 0z + x1 − x2 ≤ 0x1 + x2 + x3 = 1x1, x2, x3 ≥ 0

dont la solution est x = (1/3, 1/3, 1/3), qui correspond ay = (1/3, 1/3, 1/3), le tout pour un profit moyen de 0

I Le jeu matriciel est dit juste

I Les jeux symetriques (tels que A> = A) sont justes




2. Autres solveurs



References



References I

Ragsdale, C. (2010).

Spreadsheet Modeling & Decision Analysis.

South-Western, Cengage Learning, 6th edition.

Weatherford, L. (1997).

Introductory Management Science : Decision Modeling with Spreadsheets.

Prentice Hall, 5th edition.


Documents

Optimisation linéaire: Applications · Voir chier Ex1-Oak Products.xlsx MTH8415: Optimisation lin eaire: Applications 17/60 Solveur Excel Autres solveurs Approx. lin eaires Jeux