Modélisation linéaire

Reprenons les bases de la modélisation dans le cadre de problème linéaire. Les étapes à suivre sont les suivantes :

  1. Quelles sont les variables ? leur type peut être entier, flottant ou binaire.
  2. 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).
  3. 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.
  4. 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.

decision1

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 :

decision2

Ce qui peut se représenter d’un point de vue graphique par (l’espace des choix est en gris) :

decision3

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 :

decision4

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 :

  • x≥ 48 (deuxième ligne du tableau)
  • x+ x≥ 79 (troisième ligne du tableau)
  • etc.

Posons la fonction objectif:

  • Z = le coût total
  • Z = 170 x+ 160 x+ 175 x3+ 180 x4+ 195 x(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 :

decision5
Publicités