Modélisation linéaire
Reprenons les bases de la modélisation linéaire dans le cadre de problème linéaire. Les étapes à suivre sont les suivantes :
- Quelles sont les variables ? leur type peut être entier, flottant ou binaire.
- Quelles sont les contraintes ? puisque nous sommes en modélisation linéaire, les variables sont isolés(c’est à dire que seul un coefficient peut modifier les variables, des opérations de premier ordre tel que l’addition et la soustraction mettent en relation les variables).
- Quel est la fonction objectif ? il peut s’agir d’une minimisation ou d’une maximisation; puisque nous sommes en modélisation linéaire, les variables sont isolés.
- Le problème de complexité et de méthode de résolution ne seront pas abordés dans ce chapitre.
Exemple 1
Un industriel possède trois usine adapté dans la fabrication de deux produits. Chaque lot de produit lui rapporte une certaine somme, et il connait le nombre d’heure nécessaire pour la fabrication de chaque type de lot dans ses usines.
L’industriel voulant maximiser son profit, il faut donc trouver la meilleure production possible.
Posons des variables de décision :
- x1 = le nombre de lots du produit 1
- x2 = le nombre de lots du produit 2
Posons les contraintes :
- x1 ≤ 4 (deuxième ligne du tableau)
- 2 x2 ≤ 12 (troisième ligne du tableau)
- 3 x1 + 2 x_2 ≤ 18 (quatrième ligne du tableau)
- x1 ≥ 0 et x2 ≥ 0 (le nombre de lot est toujours positif ou nul)
Posons la fonction objectif:
- z = le profit total (en milliers d’euros)
- z = 3 x1 + 5 x2 (d’après la dernière ligne du tableau)
- max z, c’est à dire que nous cherchons la valeur maximale que peut prendre z
Ce qui donne le modèle mathématique suivant :
Ce qui peut se représenter d’un point de vue graphique par (l’espace des choix est en gris) :
Exemple 2
Maintenant que l’industriel sait comment optimiser son bénéfice, il cherche à minimiser ses dépenses. Ces dernières se constituent uniquement du salaire des employés et des horaires de travail. L’industriel à estimer le nombre minimum d’employés (MinEmp) devant être affectés durant chaque période de la journée. Chaque employé doit effectué des quarts afin de maximiser son temps de présence, une journée possède quatre quarts de travail et ces derniers demandent une rémunération particulière. L’ensemble des données est décrit dans le tableau suivant :
Posons des variables de décision :
- x1= le nombre d’employés sur le premier quart
- x2= le nombre d’employés sur le deuxième quart
- x3= le nombre d’employés sur le troisième quart
- x4= le nombre d’employés sur le quatrième quart
- x5= le nombre d’employés sur le cinquième quart
Posons les contraintes :
- x1 ≥ 48 (deuxième ligne du tableau)
- x1 + x2 ≥ 79 (troisième ligne du tableau)
- etc.
Posons la fonction objectif:
- Z = le coût total
- Z = 170 x1 + 160 x2 + 175 x3+ 180 x4+ 195 x5 (d’après la dernière ligne du tableau)
- min Z, c’est à dire que nous cherchons la valeur minimale que peut prendre Z
Ce qui donne le modèle mathématique suivant :
