[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 desquotesdbs_dbs44.pdfusesText_44

[PDF] cours java netbeans pdf

[PDF] résoudre équation produit nul second degré

[PDF] équation algébrique définition

[PDF] passer de l'autre côté expression

[PDF] résoudre équation algébrique en ligne

[PDF] passer de l'autre côté du miroir expression

[PDF] passer de l autre côté du miroir synonyme

[PDF] comment résoudre une équation algébrique avec des fractions

[PDF] quand l'amitié devient amour

[PDF] passer de l'autre côté de la barrière

[PDF] comment transformer l'amitié en amour

[PDF] passer de l'amitié ? l'amour comment

[PDF] séquence passer de l'écriture fractionnaire aux nombres décimaux cm1

[PDF] resoudre identité remarquable en ligne

[PDF] log a log b