PROGRAMMATION LINÉAIRE: À QUOI ÇA SERT, MODÈLES, CONTRAINTES, APPLICATIONS - MATEMATIQUES - 2025

La programmation linéaire est une méthode mathématique qui permet d'optimiser (maximiser ou minimiser selon le cas) une fonction dont les variables sont restreintes, du moment que la fonction et les contraintes sont des variables linéairement dépendantes.

Généralement, la fonction à optimiser modélise une situation pratique, comme le profit d'un fabricant dont les intrants, la main-d'œuvre ou les machines sont limités.

Figure 1. La programmation linéaire est largement utilisée pour optimiser les profits. Source: Piqsels.

L'un des cas les plus simples est celui d'une fonction linéaire à maximiser, qui ne dépend que de deux variables, appelées variables de décision. Il peut être de la forme:

Z = k ₁ x + k ₂ y

Avec k ₁ et k ₂ constants. Cette fonction est connue sous le nom de fonction objectif. Bien sûr, il existe des situations qui méritent plus de deux variables à étudier, étant plus complexes:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

Et les contraintes sont également modélisées mathématiquement par un système d'équations ou d'inégalités, également linéaires en x et y.

L'ensemble des solutions de ce système est appelé solutions réalisables ou points réalisables. Et parmi les points réalisables, il y en a au moins un, qui optimise la fonction objectif.

La programmation linéaire a été développée indépendamment par le physicien et mathématicien américain George Dantzig (1914-2005) et le mathématicien et économiste russe Leonid Kantorovich (1912-1986) peu après la Seconde Guerre mondiale.

La méthode de résolution de problèmes connue sous le nom de méthode simplex est une idée originale de Dantzig, qui a travaillé pour l'US Air Force, l'Université de Berkeley et l'Université de Stanford.

Figure 2. Mathématiciens George Dantzig (à gauche) et Leonid Kantorovich (à droite). Source: F. Zapata.

Modèles de programmation linéaire

Les éléments nécessaires pour établir un modèle de programmation linéaire, adapté à une situation pratique, sont:

-Fonction objective

-Variables de décision

-Restrictions

Dans la fonction objectif, vous définissez ce que vous voulez réaliser. Par exemple, supposons que vous souhaitiez maximiser les bénéfices tirés de la fabrication de certains produits. Ensuite, la fonction «profit» est établie, en fonction du prix auquel les produits sont vendus.

En termes mathématiques, cette fonction peut être exprimée en abrégé en utilisant la notation de sommation:

Z = ∑k _i x _i

Dans cette équation, k _i sont des coefficients et x _i sont les variables de décision.

Les variables de décision sont les éléments du système dont on a le contrôle et leurs valeurs sont des nombres réels positifs. Dans l'exemple proposé, les variables de décision sont la quantité de chaque produit à fabriquer pour obtenir le profit maximum.

Enfin, nous avons les contraintes, qui sont des équations linéaires ou des inégalités en termes de variables de décision. Ils décrivent les limites du problème, qui sont connues et peuvent être, par exemple, les quantités de matière première disponible dans la fabrication.

Types de restrictions

Vous pouvez avoir un nombre M de limitations, à partir de j = 1 à j = M. Mathématiquement, les restrictions sont de trois types:

1. A _j = ∑ a _ij. x _i
2. B _j ≥ ∑ b _ij. x _i
3. C _j ≤ ∑ c _ij. x _i

La première restriction est de type équation linéaire et signifie que la valeur A _j, qui est connue, doit être respectée.

Les deux restrictions restantes sont des inégalités linéaires et cela signifie que les valeurs connues B _j et C _j peuvent être respectées ou dépassées, lorsque le symbole qui apparaît est ≥ (supérieur ou égal à) ou respecté ou non dépassé, si le symbole est ≤ (inférieur ou égal à).

Exemple de modèle

Les domaines d'application sont très variés, allant de l'administration des affaires à la nutrition, mais pour comprendre la méthode, un modèle simple de situation pratique à deux variables est proposé ci-dessous.

Une pâtisserie locale est connue pour deux spécialités: le gâteau de la forêt noire et le gâteau sacripantin.

Dans sa préparation, ils ont besoin d'œufs et de sucre. Pour la forêt noire, vous avez besoin de 9 œufs et 500 g de sucre, tandis que pour la sacripantine, vous avez besoin de 8 œufs et 800 g de sucre. Les prix de vente respectifs sont de 8 $ et 10 $.

Le problème est: combien de gâteaux de chaque type la boulangerie doit-elle fabriquer pour maximiser ses profits, sachant qu'elle a 10 kilos de sucre et 144 œufs?

Variables de décision

Les variables de décision sont "x" et "y", qui prennent des valeurs réelles:

-x: le nombre de gâteaux de la forêt noire

-y: gâteaux de type sacripantin.

Restrictions

Les restrictions sont données par le fait que le nombre de gâteaux est une quantité positive et qu'il y a des quantités limitées de matière première pour les préparer.

Par conséquent, sous forme mathématique, ces restrictions prennent la forme:

1. x ≥ 0
2. et ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Les contraintes 1 et 2 constituent la condition de non-négativité précédemment exposée, et toutes les inégalités soulevées sont linéaires. Dans les restrictions 3 et 4, les valeurs à ne pas dépasser: 144 œufs et 10 kg de sucre.

Objectif Fonction

Enfin, la fonction objectif est le profit obtenu lors de la fabrication de «x» quantité de gâteaux forêt noire plus «y» quantité de sacripantines. Il est construit en multipliant le prix par la quantité de gâteaux fabriqués et en ajoutant pour chaque type. C'est une fonction linéaire que nous appellerons G (x, y):

G = 8x + 10y

Méthodes de solution

Les diverses méthodologies de solution incluent les méthodes graphiques, l'algorithme du simplexe et la méthode du point intérieur, pour n'en nommer que quelques-unes.

- Méthode graphique ou géométrique

Lorsque vous rencontrez un problème à deux variables comme celui de la section précédente, les contraintes déterminent une région polygonale dans le plan xy, appelée région réalisable ou région de viabilité.

Figure 3. La région des possibles, où se trouve la solution du problème d'optimisation. Source: Wikimedia Commons.

Cette région est construite en utilisant les lignes de restriction, qui sont les lignes obtenues à partir des inégalités des restrictions, en travaillant uniquement avec le signe d'égalité.

Dans le cas de la boulangerie qui souhaite optimiser ses profits, les lignes de contrainte sont:

1. x = 0
2. y = 0
3. 9x + 8 ans = 144
4. 0,5 x + 0,8 y = 10

Tous les points de la région délimitée par ces lignes sont des solutions possibles, il y en a donc une infinité. Sauf dans le cas où la région des possibles s'avère vide, auquel cas le problème posé n'a pas de solution.

Heureusement, pour le problème de la pâtisserie, la région des possibles n'est pas vide, nous l'avons ci-dessous.

Figure 4. La région possible du problème de la pâtisserie. La ligne de gain 0 traverse l'origine. Source: F. Zapata avec Geogebra.

La solution optimale, si elle existe, est trouvée à l'aide de la fonction objectif. Par exemple, lorsque vous essayez de trouver le profit maximum G, nous avons la ligne suivante, qui s'appelle la ligne iso-profit:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Avec cette droite on obtient toutes les paires (x, y) qui fournissent un gain G donné, donc il y a une famille de droites selon la valeur de G, mais toutes avec la même pente -k ₁ / k ₂, donc elles sont lignes parallèles.

La solution optimale

Maintenant, on peut montrer que la solution optimale d'un problème linéaire est toujours un point ou sommet extrême de la région réalisable. Ensuite:

Si la droite la plus proche de l'origine a un segment entier en commun avec la région des possibles, on dit qu'il existe des solutions infinies. Ce cas se produit si la pente de la ligne iso-profit est égale à celle de l'une des autres lignes qui limitent la région.

Pour notre pâtisserie, les sommets candidats sont A, B et C.

- Méthode simplex de Dantzig

La méthode graphique ou géométrique est applicable pour deux variables. Cependant, il est plus compliqué lorsqu'il y a trois variables, et impossible à utiliser pour un plus grand nombre de variables.

Lorsqu'on traite des problèmes avec plus de deux variables, la méthode du simplexe est utilisée, qui consiste en une série d'algorithmes pour optimiser les fonctions objectives. Des matrices et une arithmétique simple sont souvent utilisées pour effectuer les calculs.

La méthode simplex commence par choisir une solution réalisable et vérifier si elle est optimale. Si c'est le cas, nous avons déjà résolu le problème, mais si ce n'est pas le cas, nous continuons vers une solution plus proche de l'optimisation. Si la solution existe, l'algorithme la trouve en quelques essais.

Applications

La programmation linéaire et non linéaire est appliquée dans de nombreux domaines pour prendre les meilleures décisions en termes de réduction des coûts et d'augmentation des profits, qui ne sont pas toujours monétaires, puisqu'ils peuvent être mesurés dans le temps, par exemple, si vous voulez minimiser le temps nécessaire. pour effectuer une série d'opérations.

Voici quelques champs:

-En marketing, il est utilisé pour trouver la meilleure combinaison de médias (réseaux sociaux, télévision, presse et autres) pour promouvoir un certain produit.

-Pour l'attribution de tâches adéquates au personnel d'une entreprise ou d'une usine ou des horaires à eux.

-Dans la sélection des aliments les plus nutritifs et au moindre coût dans les industries de l'élevage et de la volaille.

Exercices résolus

- Exercice 1

Résolvez graphiquement le modèle de programmation linéaire soulevé dans les sections précédentes.

Solution

Il est nécessaire de représenter graphiquement l'ensemble des valeurs déterminées par le système de restrictions spécifié dans le problème:

1. x ≥ 0
2. et ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

La région donnée par les inégalités 1 et 2 correspond au premier quadrant du plan cartésien. Concernant les inégalités 3 et 4, nous commençons par trouver les lignes de restriction:

9x + 8 ans = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

La région réalisable est un quadrilatère dont les sommets sont les points A, B, C et D.

Le profit minimum est 0, donc la ligne 8x + 10y = 0 est la limite inférieure et les lignes d'iso-profit ont une pente -8/10 = - 0,8.

Cette valeur est différente des pentes des autres lignes de restriction et comme la région réalisable est bornée, la solution unique existe.

Figure 5. Solution graphique de l'exercice 1, montrant la région réalisable et le point de solution C à l'un des sommets de ladite région. Source: F. Zapata.

Cette solution correspond à une ligne de pente -0,8 qui passe par l'un des points A, B ou C, dont les coordonnées sont:

A (11; 5,625)

B (0; 12,5)

C (16, 0)

Solution optimale

Nous calculons la valeur de G pour chacun de ces points:

- (11; 5,625): G _A = 8 x 11 + 10 x 5,625 = 144,25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Le profit le plus élevé est celui de la fabrication de 11 gâteaux de la forêt noire et de 5 625 gâteaux sacripantins. Cette solution est en accord avec celle trouvée via le logiciel.

- Exercice 2

Vérifiez le résultat de l'exercice précédent en utilisant la fonction Solveur disponible dans la plupart des feuilles de calcul comme Excel ou LibreOffice Calc, qui intègrent l'algorithme Simplex pour l'optimisation en programmation linéaire.

Solution

Figure 6. Détail de la solution de l'exercice 1 à travers la feuille de calcul Libre Office Calc. Source: F. Zapata.

Figure 7. Détail de la solution de l'exercice 1 à travers la feuille de calcul Libre Office Calc. Source: F. Zapata.

Références

1. Brillant. Programmation linéaire. Récupéré de: brilliant.org.
2. Eppen, G. 2000. Recherche opérationnelle en science administrative. 5ème. Édition. Prentice Hall.
3. Haeussler, E. 1992. Mathématiques pour la gestion et l'économie. 2ème. Édition. Grupo Editorial Iberoamericana.
4. Hiru.eus. Programmation linéaire. Récupéré de: hiru.eus.
5. Wikipédia. Programmation linéaire. Récupéré de: es. wikipedia.org.