[PDF] Optimisation linéaire: Applications

View - Download Optimisation linéaire: Applications

Previous PDF

Next PDF

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Optimisation lineaire: Applications

MTH8415

S. Le Digabel, Polytechnique Montreal

H2020 (v2)

MTH8415: Optimisation lineaire: Applications1/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences Plan

1. Optimisation lineaire avec le solveur deExcel

2. Autres solveurs

3. Application : Approximations lineaires

4. Application : Jeux matriciels

References

MTH8415: Optimisation lineaire: Applications2/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

1. Optimisation lineaire avec le solveur deExcel

2. Autres solveurs

3. Application : Approximations lineaires

4. Application : Jeux matriciels

References

MTH8415: Optimisation lineaire: Applications3/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Introduction

I Outil integre dansExcelpour l'optimisation lineaire, non lineaire, et en nombres entiers I

Optimisation lineaire avec le simplexe

I

Avantages :

I

Simplicite d'utilisation. Base surExcel

IEcace pour des problemes de taille raisonnable

IOutils pour l'analyse de sensibilite

I

Inconvenients :

I

Pas adapte aux problemes de grande taille

IDicilement integrable au sein d'autres applications I Bonnes pratiques donnees dans [Ragsdale, 2010]MTH8415: Optimisation lineaire: Applications4/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Principes de base

I Communication :Le chier doit ^etre clair (noms, couleurs, commentaires, etc.) I Fiabilite :Les sorties doivent ^etre correctes et consistantes I Comprehension :On devrait pouvoir comprendre le modele et verier les resultats I Flexibilite :Un modele devrait ^etre facilement modiable le jour ou les donnees changent

MTH8415: Optimisation lineaire: Applications5/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Trucs (1/2)

I Organiser le format des donnees puis construire le modele a partir des donnees I Ne jamais mettre de constante dans une formule mais l'adresse de la cellule contenant cette constante I Les valeurs dont le sens est relie devraient ^etre situees proches les 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 ligneMTH8415: Optimisation lineaire: Applications6/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

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 deExcelpour distinguer variables, parametres, formules, etc. I Utiliser des zones de textes et des commentaires pour faciliter la lecture du modele I

Laisser les parametres en

o rangeMTH8415: Optimisation lineaire: Applications7/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Variables d'optimisation

I

Une cellule par variable

I Les placer sur une m^eme ligne dans des colonnes contigues I

Ajouter une particularite (couleur

ble ue )p ouridentication rapide I Placer le nom des variables dans les cellules juste au-dessus et a gauche (lecture facile des sorties) I

Optionnel : Fournir une valeur initiale aux variablesMTH8415: Optimisation lineaire: Applications8/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Fonction objectif

I Placer les coecients de maniere similaire aux variables I Calculer avec la fonctionExcel SOMMEPROD(SUMPRODUCT) I Placer le nom juste au-dessus ou nommer la cellule I

Ajouter une particularite (couleur

jaune ) pour identication rapide

MTH8415: Optimisation lineaire: Applications9/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

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 coecients dans colonnes correspondant aux variables I Faire le calcul (avecSOMMEPROD) du membre de gauche et placer le resultat dans une cellule I

Placer le nom de la contrainte a gauche

I

Ajouter particularite (couleur

verte ) pour identication rapideMTH8415: Optimisation lineaire: Applications10/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Execution du solveur

I Lancer l'interface du solveur depuis le menuOutilsou

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

IndiquerModele suppose lineaire

I

CocherEchelle automatique

I Cliquer surResoudre, puisReponses(Sensibilite) et sur Ok I

Apres : Bien lire le message pour savoir si ca a marcheMTH8415: Optimisation lineaire: Applications11/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Exemple 1 : Oak Products

I [Weatherford, 1997] I La compagnieOak Productsfabrique 6 types de chaises a partir de 11 composantes I Chaque semaine on regarde l'inventaire des composantes et on etablit le plan de production I

Chaque type de chaise induit un prot unitaire

I Combien doit on produire de chaises de chaque type?MTH8415: Optimisation lineaire: Applications12/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Oak Products : Donnees

MTH8415: Optimisation lineaire: Applications13/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

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 chaisesCaptainproduites

IM(Mate)

IH(American High)

IL(American Low)

IK(Spanish King)

IQ(Spanish Queen)

I

Prot : Fonction objectif a maximiser :

f(x) = 36C+ 40M+ 45H+ 38L+ 35K+ 25QMTH8415: Optimisation lineaire: Applications14/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Oak Products : Contraintes

I Une condition contrainte d'inventaire a respecter pour chacune des composantes (contraintes) : I

Nombre de grandes chevilles :

c

1(x) = 8C+ 12H+ 8K+ 4Q1280

INombre de petites chevilles :

c

2(x) = 4C+ 12M+ 12L+ 4K+ 8Q1900

INombre de dossiers type Spanish :c11(x) =K+Q85

I Finalement, il y a des imperatifs de production a respecter : il faut produire des nombres positifs de chaises (contraintes) : C0,M0,H0,:::,Q0MTH8415: Optimisation lineaire: Applications15/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Oak Products : Modele

max

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

s.c. 8 >>>>>>>>>:8C+ 12H+ 8K+ 4Q1280

4C+ 12M+ 12L+ 4K+ 8Q1900

4C+ 4M+ 4H+ 4L+ 4K+ 4Q1090

C+K+Q190

M+H+L170

K+Q85 C;M;H;L;K;Q0MTH8415: Optimisation lineaire: Applications16/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Oak Products : Resolution

Voir chierEx1-Oak Products.xlsxMTH8415: Optimisation lineaire: Applications17/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Exemple 2 : Blue Ridge Hot Tubs (BRHT)

I [Ragsdale, 2010] I

Modele :

Max. prot350X1 + 300X2PompesX1 +X2200

Main d'uvre9X1 + 6X21566

Tuyaux12X1 + 16X22880

non-negativiteX1;X20MTH8415: Optimisation lineaire: Applications18/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

BRHT : Rapport de sensibilite

MTH8415: Optimisation lineaire: Applications19/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

BRHT : Sensibilite aux coecients de l'objectif

I Les valeurs appelees \Augmentation admissible" et \Reduction admissible" pour les cellules variables indiquent la taille maximale des variations du coecient de l'objectif qui laissent la solution optimale inchangee (m^eme point extr^eme) en supposant que tous les autres coecients restent inchanges I Un zero pour \Augmentation admissible" ou \Reduction admissible" indique qu'il existe plus d'une solution optimale I L'intervalle admissible de changement decrit dans le rapport de sensibilite n'est valable que si tous les autres coecients restent xes (i.e. seulement un est change) I Si le changement sort de l'intervalle admissible, il faut resoudre le probleme a nouveau pour en conna^tre l'impact sur la solution optimale (i.e. les nouvelles valeurs optimales des variables et de l'objectif)

MTH8415: Optimisation lineaire: Applications20/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

BRHT : Interpretation des co^uts reduits des

variables I Pour une variable qui n'est pas a sa borne superieure ou inferieure, le co^ut reduit est de zero I Pour une variable qui est a sa borne sup. ou inf., le co^ut reduit indique l'impact sur la valeur optimale de l'objectif d'une augmentation d'une unite de cette variable I Une variable dont la valeur optimale est a son minimum a un co^ut reduit relie au changement minimum du coecient de l'objectif qui rend une augmentation de cette variable protable

MTH8415: Optimisation lineaire: Applications21/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

BRHT : Sensibilite aux membres de droite des

contraintes

MTH8415: Optimisation lineaire: Applications22/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

BRHT : Sensibilite aux mdd des contraintes

I

Changer le membre de droite d'une contrainte :

I

Peut changer la valeur optimale de l'objectif

IPeut changer la solution optimale (un nouveau point extr^eme) I

Le rapport de sensibilite associe un

co ^utomb re ( shadow price) a chacune des contraintes. Celui-ci indique de combien l'objectif augmentera par unite d'augmentation du membre de droite, en supposant que tous les autres parametres restent constants I Le co^ut ombre n'est valable que si le mdd reste dans l'intervalle admissible, deni par les valeurs de \Augmentation admissible" et de \Reduction admissible" I Les co^uts ombre correspondent aux opposes des co^uts reduits des variables d'ecart et aux solutions duales

MTH8415: Optimisation lineaire: Applications23/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

BRHT : Sensibilite aux mdd des contraintes

I 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 mddco^ut ombre

I Le co^ut ombre des contraintes inactives est toujours zero : Changer la valeur du mdd d'une contrainte inactive n'aecte pas la solution optimale I Ces regles ne s'appliquent que si seulement un parametre (mdd) est modie I Le co^ut ombre indique seulement la variation de la valeur optimale de l'objectif. Si la contrainte est active, changer son mdd aecte l'ensemble des solution admissibles et mene a une nouvelle solution optimale. Pour trouver la nouvelle solution optimale, nous devons resoudre a nouveau le probleme

MTH8415: Optimisation lineaire: Applications24/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

BRHT : Autre usage des co^uts ombre

I Supposons qu'un nouveau bain (le Typhoon-Lagoon) peut ^etre produit par BRHT. Son prot unitaire serait de 320$ et requiert : 1 pompe (co^ut ombre = 200$), 8 heures de main d'uvre (co^ut ombre = 16.67$), 13 pieds de tuyaux (co^ut ombre = 0$) I

Est-il protable de produire ce bain?

I

320200116:678013 =13:33$: Non

I Un produit dont le prot marginal est au dessous du co^ut marginal de sa production (mesure avec les co^uts ombre des ressources) ne peut ^etre produit dans une solution optimale (a moins d'ajouter une contrainte de production minimale)

MTH8415: Optimisation lineaire: Applications25/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

BRHT : Solution degeneree

I La solution d'un POL est appelee degeneree si une des variables de base est a sa borne superieure ou a sa borne inferieure I On detecte une solution degeneree si l'augmentation ou la diminution admissible pour le mdd d'une contrainte est a zero I Dans ce cas, le rapport de sensibilite est dicilement interpretable

MTH8415: Optimisation lineaire: Applications26/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Exemple 3 : Eastern Steel

I ES achete du minerai provenant de 4 mines et melange ces minerais pour obtenir de l'acier. La qualite de l'acier se mesure en fonction de la teneur du melange, selon 3 types d'element A, 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 dierentes

dans le minerai des 4 mines exploitees et a des prix dierents :

Mine 1 Mine 2 Mine 3 Mine 4

A (kg/tonne) 10 3 8 2

B (kg/tonne) 90 150 75 175

C (kg/tonne) 45 25 20 37

$/tonne 800 400 600 500 I Il faut determiner le melange a co^ut minimalMTH8415: Optimisation lineaire: Applications27/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

ES : Modele

I Variables :M1;M2;M3;M4: Quantite de minerai des mines

1 a 4 dans une tonne d'acier

I

Modele :

min800M1 + 400M2 + 600M3 + 500M4 s.c.8 >>>:10M1 + 3M2 + 8M3 + 2M45(1)

90M1 + 150M2 + 75M3 + 175M4100(2)

45M1 + 25M2 + 20M3 + 37M430(3)

M1 +M2 +M3 +M4 = 1(4)

M1;M2;M3;M40MTH8415: Optimisation lineaire: Applications28/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

ES : Rapport de sensibilite

MTH8415: Optimisation lineaire: Applications29/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

ES : Questions

I De combien au maximum la mine 2 peut-elle augmenter son prix sans voir ses ventes aupres de ES baisser?

Reponse :66.85$

I De combien la mine 4 doit-elle baisser son prix pour reussir a vendre son minerai a ES?

Reponse :91.11$

I Sans renegocier le prix des minerais aupres des mines, comment ES peut-elle baisser son co^ut de minerai a 500$ par tonne? Possibilite 1 :Relaxer la contrainte (1) de 5 a 4.75 (511:110:2544:44 = 500) Possibilite 2 :Relaxer la contrainte (3) de 30 a 27.5 (511:112:54:444 = 500)MTH8415: Optimisation lineaire: Applications30/60 SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

1. Optimisation lineaire avec le solveur deExcel

2. Autres solveurs

3. Application : Approximations lineaires

4. Application : Jeux matriciels

References

MTH8415: Optimisation lineaire: Applications31/60

SolveurExcelAutres solveursApprox. lineairesJeux matricielsReferences

Optimisation lineaire avec Matlab

I

Pour resoudreminx2Rnf(x) =c>x

s.c.8 :Axb Dx=e `xu I

Executer la commande :

[x f flag output lambda] =linprog(c;A;b;D;e;l;u) I lambda.ineqlinetlambda.eqlinpermettent d'acceder auxquotesdbs_dbs44.pdfusesText_44

[PDF] solveur excel 2013

[PDF] solutions harcèlement scolaire

[PDF] résolution système d'équation non linéaire excel

[PDF] qu'est ce que le harcèlement scolaire ?

[PDF] prévention harcèlement scolaire

[PDF] agir contre le harcèlement ? l'école pdf

[PDF] harcèlement sévère définition

[PDF] le harcèlement entre élèves le reconnaître le prévenir le traiter

[PDF] introduction ? l'informatique cours pdf

[PDF] marché de la confiserie 2015

[PDF] harlan coben innocent pdf

[PDF] harlan coben pdf francais

[PDF] harlan coben livres pdf gratuit

[PDF] harlan coben une chance de trop pdf

[PDF] sans un adieu pdf