MODEL2

La Modélisation

Nizar El Hachemi

11 mars 2011

Nizar El Hachemi La Modélisation

Introduction

On peut résumer la modélisation à l’habileté à traduire diversproblèmes par des relations mathématiques. Les relationsmathématiques obtenues ne constituent que des modèles desproblèmes considérés. Connaître une solution optimale d’un modèlepermet souvent au gestionnaire d’obtenir de précieuses indicationssur la façon de se comporter pour tirer au mieux son épingle du jeu.


Quelques exemples de base

Les chaises de M. EugèneM. Eugène a adapté pour la production en courtes séries, deuxmodèles de chaises : la chaise en porte-à-faux et la chaiseBarcelone. M. Eugène les a pourvus d’une armature métallique dontles pièces sont assemblées par brasage puis enduites de laquesisolantes, ce qui confère au métal un toucher chaud. Dossiers etsièges sont ensuite recouverts de cuirs de Cordoue capitonnés. M.Eugène s’est engagé à livrer d’ici 3 semaines 42 chaises enporte-à-faux et 53 chaises Barcelone. Il estime à 100 unités lemarché potentiel pour chaque type.



Les chaises de M. EugèneM. Eugène se propose de consacrer à la fabrication de ces chaisestoutes les heures de main d’oeuvre dont il disposera dans son atelierpendant les prochaines 3 semaines.



Les chaises de M. Eugène

Opération Porte-à-faux Barcelone Heures disponiblesBrasage 1,5 (h) 2 (h) 250 (h)Laquage 30 min 45 min 100 (h)

Capitonnage 2 (h) 3 (h) 327 (h)Profit par chaise 450 $ 800 $



Construction d’un modèle linéaireL’information importante est le nombre de chaises porte-à-faux xAet le nombre de chaises Barcelone xB à fabriquer d’ici 3 semaines.xA et xB sont dites variables de décisions.Quel profit M. Eugène retirera-t-il de la vente de ces chaises ? Ils’agit d’additionner les bénéfices à tirer de chacun des 2 types dechaises. Le profit total à tirer des chaises fabriquées s’élève donc à :z = 450xA + 800xB



Construction d’un modèle linéaireIl y a bien sûr des empêchements naturels, appelés contraintes, quifreinent le rêve d’un profit infini. Prenons en considération chacunedes contraintes.Contraintes de demande, il faut exiger que le plan de productionsatisfasse les commandes fermes : xA ≥ 42 et xB ≥ 53.Ne pas excéder le marché potentiel : xA ≤ 100 et xB ≤ 100.Contrainte de brasage, le temps utilisé pour braser les chaises nepeut excéder les 250 heures disponibles : 1, 5xA + 2xB ≤ 250.



Construction d’un modèle linéaireContrainte de laquage s’écrit comme suit : 30xA + 45xB ≤ 100,cependant il faudrait faire très attention aux unités. La contraintedevient donc 0, 5xA + 0, 75xB ≤ 100.La contrainte de capitonnage s’écrit tout naturellement :2xA + 3xB ≤ 327.Contraintes de non-négativité et d’intégrité : xA, xB ≥ 0 et entiers.



Modèle final

Max 450xA + 800xB (1)subject to : (2)

42 ≤ xA ≤ 100 (3)53 ≤ xB ≤ 100 (4)

1, 5xA + 2xB ≤ 250 (5)0, 5xA + 0, 75xB ≤ 100 (6)

2xA + 3xB ≤ 327 (7)xA, xB ≥ 0 (8)

xA, xB entiers (9)


Les hypothèses de la programmation linéaire

la programmation linéaireLe problème utilisé pour traduire le problème de M. Eugène enlangage mathématique est qualifié de linéaire. Mais à quellesconditions doit obéir un modèle pour être déclaré linéaire ? Etpourquoi les modèles linéaires sont-ils tant recherchés ?Les modèles linéaires se présentent dans la modélisation deplusieurs situations. Il existe toute une gamme d’algorithmesefficaces pour résoudre ces modèles.


Forme générale d’un modèle linéaire

modèle linéaire

Max (Min)z =∑

i

cixi (10)

subject to : (11)

∀i ,∑

aijxj

≤=≥

bi (12)

∀i , xi ≥ 0 (13)


Les conditions de linéarité

Conditions1 Le modèle comporte une fonction-objectif qu’il s’agit soit de

maximiser, soit de minimiser.2 La fonction-objectif de même que les membres gauches des

contraintes s’écrivent comme des sommes dont chaque termeest un produit d’une constant et une variable.

3 Chaque variable est soumise à une contrainte denon-négativité.

4 Le modèle ne comporte pas de contraintes écrites sous formed’inéquations strictes.

5 On suppose que tous les paramètres qui apparaissent dans lemodèle sont déterministes et sont connus avec précision.


Un problème de comptabilité de gestion

Définition du problèmeVincent pratique le métier ébéniste, sa spécialité est la fabricationde tables à langer et les berceaux en bois précieux. Aujourd’hui, le1er Juin, Vincent dispose d’assez de bois et de fournitures pourfabriquer 100 tables à langer et 100 berceaux. Une table se vend500$ et un berceau, 800$. Les coûts de main-d’oeuvre sont de 250$pour une table et de 350$ pour un berceau. Le bois et lesfournitures lui coûtent 75$ pour une table et 160$ pour un berceau.



Définition du problèmeUne grande part de la main-d’oeuvre est occasionnelle, elle vientprincipalement d’une école d’ébinisterie. Le nombre d’apprentisdisponible sera réduit au cours de la période estivale qui débute, cequi limite sa production de juin à un maximum de 50 tables et de30 berceaux.


Données

Résumé de la situation financière au 1er juin

Actif PassifEncaisse 20.000$

Comptes clients 37.000$Stocks* 23.500$

Emprunt bancaire 30.000$* 23500 = (100*75)+(100*160)



Définition du problèmeVincent doit établir combien de tables et de berceaux il lui fautfabriquer au cours du mois de juin. Sa clientèle ne paie toutefoisjamais comptant : les meubles vendus en juin ne seront payés qu’audébut du mois d’août. En juin, Vincent doit recevoir 13.850$ decomptes clients et il devra payer 1.600$ pour le loyer de son atelier.Il aura à rembourser une partie de l’emprunt bancaire, soit 4.350$.La dernière semaine de juin, il recevra une livraison de bois précieuxvalant 26.500$, qu’il lui faudra payer en août. Vincent veutdisposer, au début de juillet, d’au moins 15.900$ pour acheter enpayant comptant. Le banquier de Vincent exige que le ratioactif/passif soit, au début de juillet égal au moins 2.


Modèle

Variables de décisionsx1 = nombre de tables à langer à fabriquer et à vendre en juin.x2 = nombre de berceaux à fabriquer et à vendre en juin.L’objectif de Vincent consiste à maximiser le profit qu’il retirera dela production de juin.

Pour une table à langer le profit est :500− 250− 75 = 175(dollars)Pour un berceau : 800− 350− 160 = 290(dollars)


Modèle

Objectif et contraintesL’objectif est : Max z = 175x1 + 290x2

Contraintes de main-d’oeuvre ou disponibilité des apprentisx1 ≤ 50x2 ≤ 30Contraintes de fournitures (Le bois et les fournituresdisponibles)x1 ≤ 100x2 ≤ 100


Modèle

ContraintesContrainte d’encaisse : il faut au moins 15.900$ en banque audébut de juillet.20.000 + 13.850− 4.350− 1.600− 250x1 − 350x2 ≥ 15.90027.900− 250x1 − 350x2 ≥ 15.900250x1 + 350x2 ≤ 12.000Contrainte de ration actif/passif : Au début de juillet, ce ratiodoit être ≥ 2.Encaisse = 27.900− 250x1 − 350x2Comptes clients = 37.000 + 500x1 + 800x2 − 13.850Stocks = 23.500− (75x1 + 100x2) + 26.500


Modèle

ContraintesActif = Encaisse + comptes clients + StocksActif = 101.050 + 175x1 + 290x2

Passif = 30.000− 4.350 + 26.500 = 52.150La contrainte s’écrit donc 101.050+175x1+290x2

52.150 ≥ 2Ce qui se traduit par 175x1 + 290x2 ≥ 3.250


Modèle

Formulation complète

Max 175x1 + 290x2 (14)subject to : (15)

x1 ≤ 50 (16)x2 ≤ 30 (17)

250x1 + 350x2 ≤ 12.000 (18)175x1 + 350x2 ≤ 3.250 (19)

x1, x2 ≥ 0 (20)x1, x2 entiers (21)


Un problème du chocolatier-confiseur

Définition du problèmeUn chocolatier-confiseur reçoit une commande de 3.000assortiments de chocolats. Pour les confectionner, il a convenu d’yplacer 3 sortes de chocolats, dénotés chocolats 1,2 et 3, dontchaque kg lui coûte 4$, 1,45$ et 2,40$ respectivement. Chaqueassortiment doit peser un kg et se vendra 8$.Les chocolats 1 doivent représenter entre 10% et 20% du poidsd’un assortiment. Les chocolats 1 et 2 présents dans un assortimentne doivent pas peser plus de 800 g. Au moins la moitié du poidsd’un assortiment doit provenir des chocolats 1 et 3.



Définition du problèmeOn cherche une recette qui est optimale pour tous les assortiments(les 3.000 assortiments seront confectionnés de la même manière).Les quantités achetés, s’obtiennent en multipliant par 3.000 cetterecette optimale. Et réciproquement, pour résoudre le problème, ilsuffit de connaître le nombre de kg à acheter de chaque sorte. Deces remarques découle immédiatement la définition des 3 variablesde décision suivantes :

xj = nombre de kg de chocolats j que se procurera le confiseur



ObjectifLe chocolatier-confiseur veut maximiser ses profits. Un kg dechocolats se vend toujours 8$, le profit de chaque kg de chocolats 1s’établit à 8$ - 4$ = 4$, le profit de chaque kg de chocolats 2s’établit à 8$ - 1,45$ = 6,55$ et finalement le profit associé auchocolat 3 est 8$ - 2,40$ = 5,60$. La fonction-objectif quireprésente les représente les profits s’écrit donc :

Max z = 4x1 + 6, 55x2 + 5, 60x3



ContraintesContrainte de la demande : x1 + x2 + x3 = 3000Contrainte du poids de chocolats 1 du poids total del’assortiment (au moins 10%) : x1

x1+x2+x3≥ 0, 1

Simplification 0, 9x1 − 0, 1x2 − 0, 1x3 ≥ 0Contrainte du poids de chocolats (au plus 20%) :0, 8x1 − 0, 2x2 − 0, 2x3 ≤ 0Contrainte du poids du chocolats 1 et 2 dans un assortimentne doivent pas peser plus que 800 grammes.

x1+x2x1+x2+x3

≤ 0, 8ce qui s’écrit comme : 0, 2x1 + 0, 2x2 − 0, 8x3 ≤ 0



ContraintesContrainte du poids du chocolats 1 et 3 (au moins 50%).

x1+x3x1+x2+x3

≥ 0, 5, ce qui s’écrit comme :0, 5x1 − 0, 5x2 + 0, 5x3 ≥ 0Contraintes de non-négativité : x1, x2, x3 ≥ 0


Modèle

Formulation complète

Max 4x1 + 6, 55x2 + 5, 60x3 (22)subject to : (23)

x1 + x2 + x3 = 3.000 (24)x1 ≥ 300 (25)x1 ≤ 600 (26)

x1 + x2 ≤ 2.400 (27)x1 + x3 ≥ 1.500 (28)

x1, x2, x3 ≥ 0 (29)


Problème de la coupe de bobines-mères

Description du problèmeLes papetiers fabriquent des rouleaux de papier dont la largeur estfixée par les caractéristiques des machines qu’ils utilisent. Ils lesdésignent sous le vocable de bobines-mères. Par contre, leurs clientsréclament des rouleaux de divers largeurs et parfois de diverseslongueurs. Comme il est fréquent que ni la largeur ni la longueurdes bobines-mères ne soient des multiples de celles des rouleauxcommandés, les papetiers encourent souvent, pour satisfaire lescommandes de leur clientèle, des pertes de papier qu’ils désignentsous le nom de chutes.



Description du problème et donnéesSupposons que toutes les bobines-mères dont dispose un papetieront une largeur de 215 cm et une longueur de 250 m, et qu’il aaccepté les commandes données au tableau suivant :



Largeur (en cm) Longueur (en m) Nombre de rouleaux64 250 36060 250 18035 250 180



Description du problème et donnéesComme la longueur des rouleaux commandés est identique à celledes bobines-mères, il suffit d’assurer la coupe transversale d’uncertain nombre de bobines-mères.



Description du problème et donnéesQuel est l’objectif poursuivi par le papetier ? s’agit-il pour lui desatisfaire les commandes acceptées ? Si tel était le cas, il lui suffiraitde tailler tout bonnement un seul rouleau par bobine-mère : lescommandes des clients seraient évidemment satisfaites, maisexigeraient 720 bobines-mères, ce qui constituerait un gaspillage depapier. Il faut se rendre à l’évidence : l’objectif poursuivi n’est pasuniquement de remplir les commandes. Si le papetier se proposed’utiliser le moins possible de bobines-mères pour s’acquitter descommandes, comment peut-il atteindre cet objectif ? Et s’il chercheplutôt à minimiser les chutes tout en remplissant les commandes,



Description du problème et donnéess’agit-il du même objectif, formulé différemment, ou d’un secondobjectif totalement distinct du premier ? Et si ces objectifs s’avèrentdistincts, lequel faut-il privilégier ? Voilà des questions auxquellesnous nous proposons d’apporter réponses.



Plan de coupeDéterminons tous les plans de coupe :

Largeur (en cm) Plans de coupe1 2 3 4 5 6 7 8 9 10

64 3 2 2 1 1 1 0 0 0 060 0 1 0 2 1 0 3 2 1 035 0 0 2 0 2 4 1 2 4 6

Chutes 23 27 17 31 21 11 0 25 15 5



ObjectifL’objectif du papetier est de remplir les commandes soit enminimisant les chutes (pertes), soit en minimisant le nombre debobines-mères utilisées. Le papetier doit déterminer quels plans decoupe retenir et combien de fois mettre chacun en oeuvre de façonà atteindre l’un ou l’autre objectifs.



Variables de décision

Énonçons tout d’abord le premier objectif visé : minimiser lenombre de bobines-mères à découper pour satisfaire lescommandes. Nous nous préoccuperons plus loin de l’autre objectif.Comme il s’agit de déterminer les plans de coupes à retenir et lenombre de mises en oeuvre pour chacun, posons :xj = nombre de mises en oeuvre du plan numéro j . Dire que le plande coupe numéro j n’est retenu revient à exiger que la variable dedécision xj est nulle.



Puisque chaque mise en oeuvre d’un plan de coupe implique ladécoupe transversale d’une bobine-mère, l’objectif visé consiste àminimiser la somme des mises en oeuvre des diverses coupes :

Minz =∑i≤10

xi (30)

subject to : (31)3x1 + 2x2 + 2x31x4 + 1x5 + 1x6 ≥ 360 (32)

1x2 + 2x4 + 1x5 + 3x7 + 2x8 + 1x9 ≥ 180 (33)2x3 + 2x5 + 4x6 + 1x7 + 2x8 + 4x9 + 6x10 ≥ 180 (34)

∀i , xiest entier (35)



Solutions optimalesCe modèle admet plusieurs solutions optimales. En voici 3, quiproposent chacune d’utiliser 200 bobines-mères et qui, sans qu’onl’ait exigé, occasionnent toutes la même longueur totale de chutes,soit 2860 cm :

Largeur (en cm) Longueur (en m) Nombre de rouleauxSolution A Solution B Solution Cx1 = 120 x1 = 80 x1 = 110x7 = 60 x3 = 60 x6 = 30x10 = 20 x7 = 60 x7 = 60z = 200 z = 200 z = 200

Chutes = 2860 cm Chutes = 2860 cm Chutes = 2860 cm



Un modèle pour minimiser les chutesRetournons maintenant au second objectif proposé, soit laminimisation des chutes obtenues en satisfaisant les commandes. Lemodèles s’écrit :

Minw = 23x1 + 27x2 + ... + 5x10 (36)subject to : (37)

3x1 + 2x2 + 2x3 + 1x4 + 1x5 + 1x6 ≥ 360 (38)1x2 + 2x4 + 1x5 + 3x7 + 2x8 + 1x9 ≥ 180 (39)

2x3 + 2x5 + 4x6 + 1x7 + 2x8 + 4x9 + 6x10 ≥ 180 (40)∀i , xiest entier (41)



Solution optimaleL’unique solution optimale de ce modèle est :

x1 = 120x7 = 180w = 2760



Troisième modèleSi on s’appuie sur la solution optimale du dernier modèle, lepapetier découpe plus de bobines-mères, produit davantage derouleaux 60 cm, mais engendre des chutes totales moins élevéesque s’il applique l’une ou l’autre des solutions optimales du premiermodèle. Comment expliquer ce paradoxe ? Tout simplement par lefait qu’aucune pénalité ne s’applique à la production de rouleauxqui ne sont pas essentiels à l’exécution des commandes. Le bonmodèle est donc :



Un modèle pour minimiser les chutesLe bon modèle s’écrit :

Mint = w + Exc64 + Exc60 + Exc35 (42)subject to : (43)

3x1 + 2x2 + 2x31x4 + 1x5 + 1x6 ≥ 360 (44)1x2 + 2x4 + 1x5 + 3x7 + 2x8 + 1x9 ≥ 180 (45)

2x3 + 2x5 + 4x6 + 1x7 + 2x8 + 4x9 + 6x10 ≥ 180 (46)∀i , xiest entier (47)



Un modèle pour minimiser les chutesOù :

w = 23x1 + 27x2 + ... + 5x10

Exc64 = 64(3x1 + 2x2 + 2x31x4 + 1x5 + 1x6 − 360)Exc60 = 60(1x2 + 2x4 + 1x5 + 3x7 + 2x8 + 1x9 − 180)Exc35 = 35(2x3 + 2x5 + 4x6 + 1x7 + 2x8 + 4x9 + 6x10 − 180)


Problème d’affectation : la rotation du personnel

Description du problème

À intervalles réguliers, l’armée organise la rotation d’une partie deson personnel technique entre les différentes bases militaires. Elle aplusieurs raisons d’agir ainsi : permettre l’acquisition d’uneexpérience de travail diversifiée, donner l’occasion de suivre descours, accéder aux demandes de mutation vers des postes où leclimat est plus favorable, récompenser ou punir certainscomportements.



Description du problèmeSupposons, à titre d’exemple, que l’armée dispose d’une liste de 10sergents d’état-major, spécialistes de la mécanique des charsd’assaut, et qu’elle souhaite réaffecter chacun au poste de l’un deses 9 collègues. Certains de ces militaires sont célibataires, d’autressont mariés mais n’ont pas d’enfants, d’autres encore sont mariés etont des enfants... L’armée a évalué pour chacun les coûts demutation à chaque poste. L’objectif est d’assurer au moindre coûtque chaque sergent occupe un nouveau poste et que tous les postessoient comblés.



Description du problèmeDénotons les sergents par les lettres A, B, ..., H, M et N. Etdésignons par i le poste occupé présentement par le sergentd’état-major I : le sergent A occupe présentement le poste a, etainsi de suite. Le tableau suivant présente la matrice des coûts demutation de chaque sergent à chacun des postes.



Matrice des coûts

PosteSergent a b c d e f g h m n

A * 12 15 11 17 15 11 12 10 10B 6 * 14 12 16 11 17 18 18 16C 8 17 * 21 17 16 14 12 10 15D 7 16 9 * 12 18 18 14 11 14E 7 13 8 12 * 22 19 12 13 12F 8 8 11 14 12 * 12 17 9 18G 6 9 13 9 11 16 * 14 13 16H 7 14 16 11 16 22 15 * 14 18M 11 16 17 15 17 18 21 22 * 11N 8 9 8 13 9 7 8 9 8 *



Description du problème et modélisationComme il n’est pas permis qu’un sergent conserve le poste qu’iloccupe présentement, on remplace chaque astérisque de ladiagonale par un montant M, largement supérieur à ceux qui sonten jeu pour les mutations envisagées, en marquant ainsil’impossibilité de maintenir un sergent dans son poste actuel.Posons, par exemple : M = 500.



Variables de décisionDéfinissons les variables de décision binaires suivantes :vIj = 1 si le sergent I est muté du poste i au poste j.La fonction-objectif s’écrit comme suit :Minz = 500vAa + 12vAb + 15vAc + ... + 9vNh + 8vNm + 500vNnLes contraintes indiquent :

qu’à chaque sergent on doit attribuer un poste ;que chaque poste doit être combler.



modèle

À titre d’exemple, la contrainte associée au sergent A est :vAa + vAb + vAc + ... + vAn = 1et celle associée au poste a :vAa + vBa + vCa + ... + vNa = 1une solution optimale de ce problème est :

Sergent A B C D E F G H M NPoste m f h e c b d a n g


Problème : Les conditions logiques, l’équiped’arpenteurs-géomètres

Description du problèmeUne firme d’exploration minière veut recruter 6 personnes pourcombler les postes vacants dans une équipe d’arpenteurs-géomètresqui doit se rendre pour de longues périodes dans le Grand Nord. Ona retenu, parmi les dossiers reçus, 12 candidatures valables. Lesémoluments annuels exigés par ces personnes apparaissent autableau suivant.



Description du problème

Candidat Émoluments1 56.000$2 55.000$3 54.000$4 57.000$5 49.000$6 51.000$7 54.000$8 56.000$9 52.000$10 55.000$11 53.000$12 50.000$



Description du problèmeLa cohésion de l’équipe est de prime importance. Des tests depersonnalité et des séances d’interaction entre les 12 candidatsmenés par des psychologues ont révélé que certaines combinaisonsde candidats n’étaient pas souhaitables. En particulier, on désirerespecter les contraintes de cohésion suivantes :



Description du problèmeSi les candidats 3 et 8 sont embauchés, le candidat 9 ne peutl’être.Si on embauche le candidat 2, il convient d’embaucher lecandidat 11, et réciproquement, puisqu’ils sont mari et femme.Le candidat 7 est en conflit avec les candidats 4 et 5, et on neveut pas retenir ses services si l’un des candidats 4 ou 5, ou lesdeux, sont embauchés.



Description du problèmeDe plus, compte tenu des travaux à effectuer par l’équipe, on tientégalement à respecter les contraintes de qualifications suivantes :

On ne peut embaucher plus de trois des cinq candidatssuivants : 1, 3, 6, 10, 12.On doit embaucher un et un seul des trois candidats 3, 5 et 12.



Modèle : objectifQuels candidats faut-il embaucher si l’objectif est de minimiser letotal des émoluments annuels à verser aux nouveaux employés ? Lesvariables de décision sont les variables binaires vj (1 ≤ j ≤ 12), oùvj = 1 si le candidat j est embauché.La fonction objectif s’écrit :Min z = 56v1 + 55v2 + 54v3 + ... + 50v12 où z représente lesémoluments totaux (en milliers de dollars) de l’équipe.



Modèle : contraintes

Écrivons les contraintes.Tout d’abord, il s’agit d’embaucher 6 candidats :∑

1≤j≤12 vj = 6.La contrainte 1 se traduit par v3 + v8 + v9 ≤ 2.La contrainte 2 s’écrit comme : −v2 + v11 = 0.Quant à la contrainte 3, on la traduit par les 2 inéquationssuivantes :v4 + v7 ≤ 1 et v5 + v7 ≤ 1.



Modèle : contraintes et solution optimaleOn peut remplacer les deux inéquations par une seule, quiéquivaut aux 2 précédents :v4 + v5 + 2v7 ≤ 2Les dernières contraintes de qualification donnent lieu à :v1 + v3 + v6 + v10 + v12 ≤ 3v3 + v5 + v12 = 1

Une solution optimale consiste à embaucher les candidats 2, 6, 7, 9,11 et 12, pour un coût total de 315 milliers de dollars.


La verrerie Grand Siècle

Description du problèmeLa verrerie Grand Siècle exploite une usine de verre dépoli danschacune des 5 villes suivantes : A, B, C, D et E. Le procédé defabrication exige de l’acide fluorhydrique que, jusqu’à maintenant,Grand Siècle entreposait sur l’emplacement même de ses usines. Leministère de l’Environnement exige qu’à compter de l’an prochainles fûts l’acide soient entreposés à la campagne en des endroits oùd’éventuelles émanations accidentelles se diffuseraient dansl’atmosphère.



Description du problèmeGrand Siècle a repéré 4 emplacements, qui ont reçu l’agrément duMinistère, où il serait possible de stocker les fûts en attendant deles acheminer un à un, au fur et à mesure des besoins, vers lesdifférents usines. Les coûts reliés à l’acquisition des terrains et à laconstruction des installations de stockage varient très peu d’unemplacement à l’autre ; une fois répartis sur la vie utile desinstallations, ils correspondent, selon les comptables de GrandSiècle, à une dépense annuelle de 85.000 $ par emplacement. Parcontre, les coûts d’entretien des chemins d’accés différeraient defaçon notable. Le tableau suivant donne, pour les 4 emplacementsenvisagés, les coûts annuels d’entretien de ces chemins d’accés.



Données : coûts annuels d’entretien des chemins d’accés

Emplacement Coût1 12.000$2 4.000$3 4.000$4 10.000$



Données : coûts annuels d’acheminement des fûts (en 1000 $)

Le tableau suivant donne les coûts annuels, en milliers de dollars,d’acheminement des fûts de chacun de ces emplacements.

Emplacement A B C D E1 7 13 11 6 112 9 18 5 10 233 16 8 5 17 154 12 8 7 12 8



ObjectifL’objectif de Grand Siècle est de minimiser les coûts des opérations( approvisionnement annuel des usines en fûts d’acidefluorhydrique). Il est convenu que chaque usine sera approvisionnéeà partir d’un seul emplacement. La dirction se pose deux questions :

Sur quel(s) emplacement(s) faut-il construire des installationsde stockage ?Quelles sont les usines qui seront approvisionnées en acide àpartir de chaque emplacement où des installations de stockageauront été construites ?



Réponses et variables de décisionRépondre à la première question revient à déterminer, pour chaqueemplacement, si oui ou non on y construira des installations destockage. De plus, De plus, pour qu’une usine puisse êtreapprovisionnée à partir d’un emplacement, il faut que lesinstallations de stockage y aient été aménagées et que le chemind’accés soit entretenu. On est donc amené à introduire les variablesde décision binaires suivantes :

vi = 1 si Grand Siècle construit un entrepôt sur l’emplacementi .wiJ = 1 si l’entrepôt de l’emplacement i alimente en fûtsl’usine de la ville J.



ObjectifIl s’agit de minimiser la fonction-objectif z obtenue en additionnantl’amortissement annuel (en 1000 $) des investissements réalisés surles emplacements retenus 85(v1 + v2 + v3 + v4 + v5),Les coûts annuels (en 1000$) d’entretien des chemins d’accés12v1 + 4v2 + 4v3 + 10v4et finalement les coûts d’acheminement des fûts7w1A + 13w1B + ... + 8w4E



ContraintesLes contraintes technologiques se regroupent en deux groupes. Lepremier, traduit la contrainte qu’une usine J peut êtreapprovisionnée à partir d’un emplacement i seulement lorsque desinstallations de stockage existent sur cet emplacement. Lescontraintes du deuxième bloc traduisent le fait que chaque usine estapprovisionnée à partir d’un seul emplacement.

wiJ ≤ vi , ∀i , ∀Jw1J + w2J + w3J + w4J = 1, ∀J


L’utilisation de variables binaires pour linéariser

DéscriptionLes variables binaires sont souvent utilisées conjointement avec desvariables réelles non négatives pour traduire en modèles linéairesdes problèmes qui, a priori, semblent non linéaires. Nous allons voirquelques exemples simples qui illustrent comment le recoursastucieux à des varoables binaires permet d’agrandirconsidérablement le champ d’application des modèles linéaires.


Électro

DéscriptionEn périodes de basses eaux, ou durant l’hiver pour faire face à unedemande accrue, Électro, un fournisseur d’énergie électrique, faitappel à des centrales thermiques alimentées au mazout etregroupées sur un emplacement situé prés d’une grande ville où unebonne part de sa clientèle. Dans chacune des 4 centralesthermiques d’Électro, des brûleurs génèrent dans une chaudière lavapeur nécessaire à l’entraînement du groupe turboalternateur


Électro

Déscriptionqui produit l’électricité convoyée par les lignes de transport vers lesconsommateurs. Chez Électro, la vapeur produite par l’une oul’autre des 4 chaudières peut être acheminée sans perteconséquente vers l’un ou l’autre des 4 groupes turboalternateurs,cette configuration a été adoptée pour faire face aux nombreusespannes et aux fréquents arrêts nécessités par entretiens.


Électro

Déscription

Électro a construit ces centrales au fur et à mesure que son réseaugrandissait, de sorte que certaines centrales sont plus modernes et,partant, plus rentables que d’autres. Chaudières et groupesalternateurs ont des plages d’exploitation en dehors desquelles leurfonctionnement n’est ni économique ni sécuritaire. Le respect deces plages assure de plus une vie utile prolongée à l’équipement.Les tableaux suivants contient, pour les 4 chaudières et les 4groupes alternateurs, les données pertinentes au problème.


Électro

Données

Chaudière tonnage minimal tonnage maximale coûtde vapeur produite de vapeur produite par tonne

A 800 1200 9,00B 650 900 8,50C 425 675 7,75D 360 600 7,25


Électro

Données

Groupe tonnage tonnage kWh par tonne coût parminimal maximale de vapeur tonne

1 500 800 4 3,002 900 1300 3 3,403 600 900 4 3,254 500 800 4 4,00


Électro

DéscriptionLe problème d’aujourd’hui consiste à produire 8312 kWh en périodede pointe tout en minimisant les coûts. Combien de vapeurproduira chacune des chaudières et de quelle façon sera répartie lavapeur entre les groupes, sachant qu’il possible que certaineschaudières ou que certains groupes soient inutilisés ?


Électro

Variables de décisionLes variables de décision sont :

vI = 1 si la chaudière I est activewj = 1 si le groupe j est mis à contributionxI = nombre de tonnes de vapeur produites par la chaudière Iyj = nombre de tonnes de vapeur utilisées par le groupe j


Électro

ContraintesPour indiquer qu’il faut produire au moins 8312 kWh, on pose :

4y1 + 3y2 + 4y3 + 3y4 ≥ 8312Pour indiquer que les 4 chaudières doivent produire ensemble aumoins autant de tonnes de vapeur qu’en utiliseront les 4 groupes,on pose :

xA + xB + xC + xD ≥ y1 + y2 + y3 + y4

Pour chaque chaudière I, il faut forcer la variable xI , à être nulle,soit dans l’intervalle admissible. Par exemple, pour la chaudière A,on pose :

800vA ≤ xA ≤ 1200vA


Électro

Minz = 9xA + ... + 7, 25xD + 3y1 + ... + 4y4 (48)subject to : (49)

4y1 + 3y2 + 4y3 + 3y4 ≥ 8312 (50)xA + xB + xC + xD − y1 − y2 − y3 − y4 ≥ 0 (51)

800vA ≤ xA ≤ 1200vA (52)650vB ≤ xB ≤ 900vB (53)425vC ≤ xC ≤ 675vC (54)360vD ≤ xD ≤ 600vD (55)500w1 ≤ y1 ≤ 800w1 (56)

900w2 ≤ y2 ≤ 1300w2 (57)600w3 ≤ y3 ≤ 900w3 (58)500w4 ≤ y4 ≤ 800w4 (59)


Électro

Solution optimalexA = 929, xC = 675, xD = 600y1 = 800, y3 = 900, y4 = 504vA = vC = vD = w1 = w3 = w4 = 1z = 25283, 25 dollars


Électro

Remarques

Électro présente un cas particulier d’une situation fréquente. Dansle présent exemple, les variables xI et yj doivent soit être nulles, soitappartenir aux plages d’exploitation économique et sécuritaire.Autrement dit, les domaines admissibles de ces variables sontcomposés de deux intervalles fermés disjoints : par exemple, ledomaine de xA est la réunion des intervalles [0 ;0] et [800 ;1200].


Électro

RemarquesDans certains contextes, le domaine d’une variable est formé deplus de deux intervalles fermés disjoints. L’approche utilisée dans leproblème d’Électro s’adapte aisément à ces situations. À titred’exemple, considérons une variable x dont la valeur doitimpérativement appartenir à l’un des intervalles [0 ;20], [50 ;64] et[75 ;81]. Il suffit d’introduire des variables binaires u, v et w ainsidéfinies :


Électro

Exemple

u = 1 si x appartient à l’intervalle [0 ;20]v = 1 si x appartient à l’intervalle [50 ;64]w = 1 si x appartient à l’intervalle [75 ;81]

Il reste à ajouter au modèle :u + v + w = 10u + 50v + 75w ≤ x ≤ 20u + 64v + 81w


Comment tenir compte des coûts fixes : la coupe debobines-mères

DéscriptionReprenons le problème de la coupe de bobines-mères considéréavant. Convenons cette fois de tenir compte non seulement descoûts reliés aux chutes, mais également des coûts engendrés par lepassage d’un plan de coupe à un autre. Convenons de plus de nousconformer à une pratique du monde manufacturier où l’on tolère,souvent tacitement, des variations de faible amplitude dans lafourniture des commandes.



Déscription

À ce propos, imaginons qu’aient été conclus, entre le papetier etses clients, des accords dont il s’autorise pour se contenter desatisfaire, à quelques rouleaux près, l’ensemble des commandes derouleaux d’une largeur donnée. Pour fixer les idées, disons qu’il sedonne une marge de 10 rouleaux de 64 cm, en plus ou en moins, secontraignant à produire non pas exactement 360 rouleaux, commel’indique le carnet de commandes, mais de 350 à 370 rouleaux decette largeur ; et fixons à 5 rouleaux la marge de manoeuvre qu’ils’accorde pour les commandes de 180 rouleaux de chacune des 2autres largeurs.



ModèleComme dans les modèles précédents, les variables xj dénotent lenombre de mises en oeuvre du plan de coupe numéro j . On leuradjoint des variables binaires vj telles que :

vj = 1 si le plan de coupe j est mis en oeuvre au moins unefois.

La fonction objectif prend alors l’allure suivante :Min z = (c1*Chutes) + (c2*Passages)où c1 est le coût correspondant à chaque cm de chuteChutes = total des chutes (en cm)Chutes = 23x1 + 27x2 + 17x3 + ... + 5x10



Modèlec2 est le coût de passage d’un plan de coupe au suivantPassages = nombre de passages d’un plan de coupe à unautrePassages = v1 + v2 + v3 + ... + v10 − 1

Les contraintes se regroupent en 3 catégories.Celles qui visent à satisfaire la demande à quelques rouleaux près :

350 ≤ 3x1 + 2x2 + ... + 1x6 ≤ 370175 ≤ 1x2 + 2x4 + ... + 1x9 ≤ 185175 ≤ 2x3 + 2x5 + ... + 6x10 ≤ 185



ModèleCelles qui lient chaque variable xj à la variable vj correspondante defaçon à traduire l’obligation pour vj de prendre la valeur 1 si etseulement si la variable xj est positive :

vj ≤ xj ≤ Mvj où M est une constante suffisamment élevéeCelles qui exigent que les variables xj sont non négatives etentières, que les variables vj soient binaires.


La modification par à-coups du membre droit d’unecontrainte

DéscriptionUn manufacturier dispose de l’équipement nécessaire pour mettreen marché 4 produits alimentaires : P1, P2, P3 et P4. Ces produitsrequirent l’intervention de 3 ateliers distincts : A1, A2 et A3. Letableau suivant présente les données relatives aux durées deproduction et aux disponibilités de ces ateliers au cours du prochainmois.



Données de fabrication

Atelier P1 P2 P3 P4 Heuresdisponibles

A1 0,12 0,15 0,10 0,09 2760A2 0,10 0,09 0,15 0,10 2500A3 0,05 0,04 0,04 0,05 1200

Profit par caisse 2,20 $ 1,90 $ 2,25 $ 1,71 $

Table: Données en heure



DéscriptionCe qui es fabriqué au cours d’un mois n’est livré qu’à la fin du moissuivant : en effet, une période minimale d’un mois de mûrissementet d’affinage est requise pour que les produits atteignent leur pleinesaveur. L’espace d’entreposage requis pour une caisse de chaqueproduit est donné au tableau qui suit. Le manufacturier dispose de4000 m3 d’espace d’entreposage, qui lui coûtent 1200$ par mois. Ilpeut louer de l’espace supplémentaire par tranche de 2000 m3, autarifs mensuels donnés au tableau.



Données de fabrication

Produits P1 P2 P3 P4

Espace requis en m3 0,27 0,28 0,29 0,24

Table: Espace requis

Espace (103 m3) 2 4 6 8 10 12 14 16Coût 103 $ 3 4,8 6,4 7,8 9 10 10,8 11,5

Table: Coût de location mensuel



DéscriptionLe carnet de commandes et le maintien de ses parts de marchéimposent au manufacturier de fabriquer un total d’au moins 5000caisses de P1 et de P2 confondus, au plus 4000 caisses de P2, aumoins 2000 caisses de P4 et un total d’au plus 30000 caisses desproduits P1 et P3 confondus.



ModélisationLes coûts d’entreposage ne sont pas linéaires et il sera nécessaired’introduire des variables binaires. Les variables de décision sontdonc xj (1 ≤ j ≤ 4), C et vh (0 ≤ h ≤ 8), où

xj = nombre de caisses du produit j que fabriquera lemanufacturierC n’apparaît que pour représenter le coût des 4000 m3

disponiblev0 = 1 si le manufacturier n’utilise que les 4000 m3 dont ildispose et où, pour h = 1, ..., 8vh = 1 si le manufacturier loue exactement (2h) milliers de m3



ModélisationLe modèle suivant constitue une façon de traduiremathématiquement le problème du manufacturier :

Max 2, 2x1 + ... + 1, 71x4− 103 (3v1 − ...− 11, 5v8)− Csubject to : (60)

0, 12x1 + 0, 15x2 + 0, 10x3 + 0, 09x4 ≤ 2760 (61)0, 10x1 + 0, 09x2 + 0, 15x3 + 0, 10x4 ≤ 2500 (62)0, 05x1 + 0, 04x2 + 0, 04x3 + 0, 05x4 ≤ 1200 (63)0, 27x1 + 0, 28x2 + 0, 29x3 + 0, 24x4 ≤ 103(4v0 + ... + 20v8)(64)



ModélisationSuite du modèle :

v0 + v1 + v2 + ... + v8 = 1 (65)x1 + x2 ≥ 5000 (66)

x2 ≤ 4000 (67)x4 ≥ 2000 (68)

x1 + x3 ≤ 30000 (69)C = 1200 (70)



DiscussionL’approche retenue pour modifier par à-coups le membre de droitde la contrainte d’entreposage mérite une présentation plusgénérale. L’objectif du manufacturier est de maximiser ses profitsen utilisant à bon escient diverses ressources. L’une d’elles estl’espace d’entreposage, et le manufacturier dispose pour le momentde b0 = 4000m3. Il doit donc respecter une contrainte du genre∑

aixi ≤ b0.



DiscussionIl songe à augmenter l’espace d’entreposage et cherche le niveau decette ressource qui lui permettrait de maximiser ses profits enrelaxant le membre droit de la contrainte associé. Comme lescontrats de location offrent l’espace supplémentaire en blocs, ils’agit de permettre à b0 de varier pat à-coups, disons de b0 à b1, deb1 à b2, de b2 à b3, etc. Les écarts entre deux bh consécutifs n’ontpas à être égaux, bien qu’ils le soient dans l’exemple.



DiscussionPour modéliser une telle situation, il suffit de relier comme suit lescoûts afférents à chacun des accroissements prèvus de la ressource,à partir du seuil minimal b0 :

Pour le passage de b0 à bh : coûts de ch h = 1, ..., p0 < c1 < c2 < ... < cp.vh = 1 si le membre de droit de la contrainte est égale à bh


Comment satisfaire à un nombre fixé de contraintes

PrésentationIl arrive que les contraintes technologiques, dans leur ensemble,excluent toute solution admissible, ou encore limitent lafonction-objectif à une valeur jugée inacceptable par lesgestionnaires. On cherche alors à agrandir l’ensemble des solutionsadmissibles. Une façon de procéder est de faire jouer à certainescontraintes technologiques un rôle de critères et d’accepter queseulement un certain nombre de ses critères puissent être satisfaits.



Les contraintes de signe ≥Nous illustrons notre propos à l’aide d’un problème classique dediète, dont toutes les contraintes en un premier temps doivent êtresatisfaits.Les normes d’une diète idéale imposent des quantités minimales deglucides, de lipides et de protides. Une diètéticienne, qui cherche àminimiser le coût de rations composées à partir des aliments A etB, se voit confrontée au problème linéaire suivant :



Modéle

Min z = 5xA + 6xB

subject to : (71)120xA + 200xB ≥ 1200 (72)300xA + 250xB ≥ 2200 (73)200xA + 200xB ≥ 1375 (74)

xA, xB ≥ 0 (75)



DiscussionLa valeur minimale de la fonction-objectif dans le modèle ci-dessusest z = 42, 53. Si le coût 42,53 de la diète optimale est jugé tropélevé, il est possible d’améliorer la situation en exigeant seulementque 2 des 3 contraintes technologiques soient satisfaites. Voicicomment traduire algébriquement cette exigence. On commencepar définir des variables binaires vi (1 ≤ j ≤ 3) :

vi = 1 si la contrainte-critère numéro i doit être satisfaite.



Modéle

Min z = 5xA + 6xB

subject to : (76)120xA + 200xB ≥ 1200− (1− v1)M (77)300xA + 250xB ≥ 2200− (1− v2)M (78)200xA + 200xB ≥ 1375− (1− v3)M (79)

v1 + v2 + v3 ≥ 2 (80)xA, xB ≥ 0 (81)

v1, v2, v3 ∈ {0, 1} (82)


Documents

MODEL2