Modélisation d'un problème linéaire

$$\text{Probleˋme d’optimisation}=\{\begin{array}{l}\text{Vecteur des variables }x\text{(Permet des choix)}\\ \text{Fonction objectif}\\ \text{Contraintes}\end{array}$$

Exemple de modélisation de problème linéaire

Note : la formulation que l’on fait ici est de forme générale. Il est cependant possible de reformuler ces problèmes sous la forme géométrique ou la forme standard.

Exemple 1

Énoncé

Trois ressources A (bois), B (clous) et C (tissu) sont utilisées pour obtenir deux produits T (table) et L (lits). On a besoin de: deux unités de bois pour construire une table et trois pour un lit, deux unités de clou pour une table et une pour un lit, et une unité de tissu pour une table et trois pour un lit. On dispose de 13 unités de A, 11 de B et 9 de C. Les produits T et L rapportent, respectivement, 300 et 400 euros par unités produites. Combien d’unités de L et T faut-il produire pour maximiser le profit?

Au propre

Trois ressources :

• A → Bois
• B → Clous
• C → Tissus Sont utilisés afin de confectionner des
• Tables → 2A + 2B + 1C
• Lits → 3A + 1B + 3C

On a 13A, 11B et 9C

Les tables rapportent 300€ Les lits rapportent 400€

Comment maximiser nos gains ?

Formulation du problème

Choix des variables

Tout d’abord on va attribuer des variables $x$, pour tous les éléments sur lesquels on peut jouer dans le problème. (Dans notre cas le nombre d’unité de tables et de lits). Ici : $x_1\to \text{Nombre de tables}$ $x_2\to \text{Nombre de lits}$

Contraintes

• On a 13 unités de A et ça nous en consomme 2 par $x_1$ et 3 par $x_2$ Ce qui nous donne : $2x_1+3x_2\le 13$
• On a 11 unités de B et ça nousx_{1},x_{2} \geq 0 en consomme 2 par $x_1$ et 1 par $x_2$ Ce qui nous donne : $2x_1+x_2\le 13$
• On a 9 unités de C et ça nous en consomme 1 par $x_1$ et 3 par $x_2$ Ce qui nous donne : $x_1+3x_2\le 9$
• On ne peut pas produire un nombre négatif Donc : $x_1,x_2\ge 0$ Au final on a les contraintes :

$$\{\begin{array}{l}2x_1+3x_2\le 13\\ 2x_1+x_2\le 13\\ x_1+3x_2\le 9\\ x_1,x_2\ge 0\end{array}$$

Fonction objectif

Il s’agit du point principal de notre problème c’est la fonction qui nous permet d’évaluer à quel point notre solution est optimale. Ici ça va être une maximisation de notre profit : ${\max }_{x_1,x_2}=300x_1+400x_2$ On dit que la table nous rapporte 300 et que le lit nous rapporte 400.

Exemple 2

Un produit est transportée de m origines vers n destinations. Le produit est disponible en quantités a1 , a2 , … , am aux origines et les demandes aux destinations sont de b1 , b2 , … , bn . Le coût de transport d’une unité du produit de l’origine i à la destination j est de cij (par exemple, la distance entre i et j). On désire déterminer les quantités du produit à transporter de i à j de manière à satisfaire les demandes tout en minimisant le coût total des transports.

Variables

Nos variables seront dans une matrice $X$ Une variable $x_{ij}$ correspond à la quantité de produits transporté de i à j

Contraintes

On doit s’assurer que ce qui sort de chaque entrepôt n’est pas supérieure à la quantité disponible en stock. Nos produits sont envoyés vers n destinations depuis chaque entrepôt. C’est pourquoi on boucle sur les j ici. ${\sum }_{j=1}^n{x}_{ij}\le a_i\forall i$ On doit s’assurer que les destinations reçoivent suffisamment de produits de chaque entrepôts. Il y a m origines donc on va boucler sur toutes les origines pour voir si les origines toutes ensembles nous envoient suffisamment de produits ensemble : ${\sum }_{i=1}^m{x}_{ij}\ge b_j\forall j$

Également on ne peut pas transférer une quantité négative de produits $x_{ij}\ge 0$ (logiquement on devrait dire $\forall i\forall j$ mais c’est souvent omis pour des raisons pratiques )

Fonction objectif

Ici on cherche une minimisation de coût. On a une matrice C qui nous donne le coût pour un transport de i à j. Donc on a : ${\min }_x{\sum }_{i=1}^m{\sum }_{j=1}^n{x}_{ij}.c_{ij}={\min }_x{\sum }_{i,j}{x}_{ij}.c_{ij}$ (La forme de droite de la formule est la formule des slides, c’est un forme abrégée de ce qui est à gauche)