Devoir de Maison de Programmation Linéaire

Ce devoir de maison porte sur la programmation linéaire et évalue les connaissances théoriques ainsi que la capacité à modéliser et résoudre des problèmes d’optimisation linéaire. Il teste la compréhension des définitions fondamentales, la formulation des problèmes, l’analyse des solutions de base, ainsi que la maîtrise de l’algorithme du simplexe et de la dualité.

Exercice 1 Questions de cours

Ce premier exercice demande de répondre à des questions théoriques sur la programmation linéaire, notamment les définitions, la formulation canonique et standard, la notion de base, les conditions d’optimalité, l’algorithme du simplexe et la dualité.

1. Donner la définition d'un Programme Linéaire (P.L.) écrit sous forme canonique :

Un Programme Linéaire (P.L.) sous forme canonique est un problème d’optimisation linéaire qui consiste à maximiser une fonction linéaire sous des contraintes d’égalité et de non-négativité des variables. Plus précisément :

maximiser z = c x sous contraintes Ax = b avec x ≥ 0

où :

• c est un vecteur de coefficients (c_j),
• x est le vecteur des variables (x_i),
• A est une matrice de coefficients des contraintes,
• b est un vecteur des termes constants.

Réponse : Un Programme Linéaire sous forme canonique est un problème de la forme max (z = c x) sous contraintes Ax = b et x ≥ 0.

2. Comment écrire un Programme Linéaire sous forme standard ?

La forme standard d’un Programme Linéaire consiste à exprimer le problème avec des contraintes d’inégalités (≤) et des variables non négatives. Typiquement, on écrit :

max z = c x sous contraintes Ax ≤ b avec x ≥ 0

Si le problème est initialement sous forme canonique (avec des égalités), on peut transformer les égalités en deux inégalités, ou introduire des variables d’écart (slack variables) pour passer des inégalités aux égalités.

Réponse : Un Programme Linéaire sous forme standard est écrit avec une fonction objectif linéaire à maximiser, des contraintes sous forme d’inégalités Ax ≤ b, et des variables x ≥ 0.

3. Soient n le nombre de variables, m le nombre de contraintes, c = (c_j)1≤j≤n et A une matrice de rang m. On considère le problème PL :

max (z = c x) sous contraintes Ax = b x ≥ 0

(a) Donner la définition d'une Base :

Une base est un sous-ensemble de colonnes de la matrice A, de taille m (le nombre de contraintes), telles que ces colonnes soient linéairement indépendantes. La matrice formée par ces colonnes est appelée matrice de base B.

Réponse : Une base est un ensemble de m colonnes de A formant une matrice B inversible (de rang m).

(b) Donner la définition d'une solution de Base réalisable :

Une solution de base réalisable est une solution x au problème PL où les variables hors base sont nulles, et les variables de base sont obtenues en résolvant B x_B = b, avec x_B ≥ 0. Cette solution satisfait donc toutes les contraintes et la non-négativité.

Réponse : Une solution de base réalisable est une solution x telle que x_HorsBase = 0, x_Base = B^-1 b ≥ 0.

(c) Soit B la matrice associée à une base réalisable, écrire le problème PL en fonction des variables hors base :

On partitionne le vecteur x en variables de base x_B et variables hors base x_N. Le problème s’écrit :

max z = c_B x_B + c_N x_N sous contraintes B x_B + N x_N = b x_B, x_N ≥ 0

En isolant x_B :

x_B = B^-1 b - B^-1 N x_N

La fonction objectif devient :

z = c_B x_B + c_N x_N = c_B (B^-1 b - B^-1 N x_N) + c_N x_N = c_B B^-1 b + (c_N - c_B B^-1 N) x_N

avec la contrainte x_N ≥ 0 et x_B ≥ 0, soit :

B^-1 b - B^-1 N x_N ≥ 0

Réponse : Le problème s’écrit :

max z = c_B B^-1 b + (c_N - c_B B^-1 N) x_N
sous contraintes
x_N ≥ 0
B^-1 b - B^-1 N x_N ≥ 0

4. Donner la condition nécessaire et suffisante pour qu'une solution de Base réalisable soit optimale :

La condition d’optimalité est que les coefficients réduits de la fonction objectif soient tous négatifs ou nuls :

c_N - c_B B^-1 N ≤ 0

Cette condition signifie qu’aucune variable hors base ne peut améliorer la valeur de la fonction objectif en entrant dans la base.

Réponse : Une solution de base réalisable est optimale si et seulement si les coefficients réduits c_N - c_B B^-1 N ≤ 0.

5. Donner l'organigramme de l'algorithme du simplexe :

L’algorithme du simplexe procède par itérations successives pour améliorer la solution :

• Initialiser avec une base réalisable B et solution x_B = B^-1 b ≥ 0.
• Calculer les coefficients réduits : r = c_N - c_B B^-1 N.
• Si tous les coefficients réduits r ≤ 0, la solution est optimale, arrêter.
• Sinon, choisir une variable hors base avec coefficient réduit positif pour entrer dans la base.
• Déterminer la variable de base à sortir en utilisant la règle du ratio pour maintenir la faisabilité.
• Mettre à jour la base, calculer la nouvelle solution de base réalisable.
• Retourner à l’étape 2.

Réponse : L’algorithme du simplexe est un processus itératif qui, à partir d’une base réalisable, améliore la solution en entrant une variable hors base avec coefficient réduit positif et en sortant une variable de base selon la règle du ratio, jusqu’à ce que tous les coefficients réduits soient négatifs ou nuls.

6. On considère les problèmes (P(b)) et (P(b0 = b + Δb)) pour Δb petit :

(P(b)) : max z = c x sous contraintes Ax = b x ≥ 0

(P(b0)) : max z = c x sous contraintes Ax = b + Δb x ≥ 0

(a) On note B la base optimale (B optimale) du dual de (P(b)) avec Δb > 0. Donner la solution :

La solution optimale de (P(b0)) s’exprime en fonction de la base B comme :

x_B = B^-1 (b + Δb) = B^-1 b + B^-1 Δb

et x_N = 0.

Réponse : La solution optimale de (P(b0)) est x_B = B^-1 b + B^-1 Δb, x_N = 0.

(b) Sous quelles conditions B reste la base optimale de (P(b0)) ?

Pour que B reste optimale, il faut que la solution de base reste réalisable :

x_B = B^-1 (b + Δb) ≥ 0

et que les coefficients réduits restent négatifs ou nuls :

c_N - c_B B^-1 N ≤ 0

La condition sur les coefficients réduits ne dépend pas de b, donc elle est automatiquement satisfaite si B était optimale pour (P(b)). La condition principale est donc la faisabilité :

Réponse : B reste optimale si B^-1 (b + Δb) ≥ 0.

(c) Donner le dual de (P(b0)) :

Le dual (D(b0)) du problème primal (P(b0)) est :

min y b + y Δb sous contraintes y A ≥ c

où y est le vecteur des multiplicateurs associés aux contraintes.

Réponse : Le dual est :

min y (b + Δb)
sous contraintes y A ≥ c

(d) Donner la signification de la solution optimale du dual de (P(b)) :

La solution optimale du dual y* correspond aux prix ombres ou valeurs marginales des ressources. Elle indique la variation de la valeur optimale du problème primal lorsque le second membre b est modifié. En particulier, y* Δb donne la variation de la valeur optimale lorsque b est remplacé par b + Δb.

Réponse : La solution optimale du dual représente les prix ombres, c’est-à-dire la sensibilité de la valeur optimale du primal aux variations de b.

Exercice 2 Modélisation d’un problème d’alimentation en électricité

Ce second exercice porte sur la modélisation d’un problème d’optimisation linéaire appliqué à la distribution d’électricité depuis plusieurs centrales vers plusieurs villes, avec des coûts de production et des demandes spécifiques.

1. Donner une représentation graphique :

Le problème peut être représenté par un graphe biparti où :

• Les sommets d’un côté représentent les centrales électriques (Centrale 1, Centrale 2, Centrale 3).
• Les sommets de l’autre côté représentent les villes (Cité 1, Cité 2, Cité 3, Cité 4).
• Les arcs relient chaque centrale à chaque ville, avec un coût de production associé à chaque arc.
• Les demandes des villes sont indiquées comme des contraintes de flux entrant.
• Les capacités de production des centrales sont indiquées comme des contraintes de flux sortant.

Réponse : Une représentation graphique est un graphe biparti avec les centrales d’un côté, les villes de l’autre, et des arcs pondérés par les coûts de production entre chaque centrale et chaque ville.

2. Formulation du problème :

(a) Donner la définition des variables de décision :

On définit les variables x_ij représentant la quantité d’électricité (en GW h) fournie par la centrale i à la ville j.

Par exemple :

• x_11 : quantité fournie par Centrale 1 à Cité 1
• x_12 : quantité fournie par Centrale 1 à Cité 2
• …
• x_34 : quantité fournie par Centrale 3 à Cité 4

Réponse : Les variables de décision sont x_ij ≥ 0, la quantité d’électricité fournie par la centrale i à la ville j.

(b) Écrire la fonction objectif :

La fonction objectif est de minimiser le coût total de production :

min Z = Σ_i Σ_j (coût_ij × x_ij)

où coût_ij est le coût de production pour 1 GW h de la centrale i vers la ville j.

Réponse : La fonction objectif est :

min Z = 9 x_11 + 7 x_12 + 5 x_13 + 30 x_14
      + 10 x_21 + 13 x_22 + 16 x_23 + 30 x_24
      + 6 x_31 + 9 x_32 + 9 x_33 + 20 x_34

(c) Écrire les contraintes :

Les contraintes se divisent en deux types :

• Contraintes de demande : pour chaque ville j, la somme des quantités reçues doit être égale à la demande D_j :

x_1j + x_2j + x_3j = Demande_j

• Contraintes de capacité : pour chaque centrale i, la somme des quantités fournies ne doit pas dépasser la puissance fournie maximale P_i :

Σ_j x_ij ≤ Puissance_i

De plus, toutes les variables doivent être positives :

x_ij ≥ 0

Réponse : Les contraintes sont :

Pour chaque ville j :
x_1j + x_2j + x_3j = Demande_j

Pour chaque centrale i :
Σ_j x_ij ≤ Puissance_i

x_ij ≥ 0

3. Montrer que (0; 10; 25; 0; 45; 0; 5; 0; 0; 10; 0; 30) est une solution optimale du problème :

La solution proposée correspond aux valeurs des variables x_ij dans l’ordre donné (probablement par lignes ou colonnes). Pour montrer qu’elle est optimale, il faut :

• Vérifier que la solution satisfait toutes les contraintes (demandes et capacités) et la non-négativité.
• Calculer la valeur de la fonction objectif pour cette solution.
• Vérifier que cette solution est réalisable et que les conditions d’optimalité (coefficients réduits négatifs) sont respectées, ce qui nécessite le calcul des multiplicateurs ou l’application de l’algorithme du simplexe.

Sans données supplémentaires sur la base ou les multiplicateurs, on peut au moins vérifier la faisabilité :

• Vérification des demandes :
• Cité 1 : x_11 + x_21 + x_31 = 0 + 45 + 5 = 50 (demande 35 selon tableau, donc il y a une incohérence)
• Cité 2 : 10 + 0 + 0 = 10 (demande 50)
• Cité 3 : 25 + 0 + 0 = 25 (demande 40)
• Cité 4 : 0 + 0 + 30 = 30 (demande 45)

Les demandes ne sont pas respectées selon ces calculs, ce qui suggère que soit l’ordre des variables n’est pas clair, soit la solution n’est pas faisable.

Réponse : Impossible de vérifier l’optimalité car les contraintes de demande ne sont pas respectées avec les données fournies. L’énoncé ne donne pas l’ordre exact des variables ni les bases associées.

Méthode

Ce devoir récompense la maîtrise des définitions fondamentales de la programmation linéaire, la capacité à formuler correctement un problème en variables et contraintes, ainsi que la compréhension des notions de base, solution de base réalisable, et conditions d’optimalité. La rigueur dans la manipulation des matrices et vecteurs, notamment dans l’écriture des coefficients réduits et la gestion des bases, est essentielle.

L’algorithme du simplexe doit être compris comme un processus itératif avec des règles précises pour l’entrée et la sortie des variables de base. La dualité est un concept clé pour interpréter les prix ombres et la sensibilité des solutions.

Les erreurs les plus pénalisées sont :

• Confusion entre formes canonique et standard.
• Omission des conditions de non-négativité.
• Mauvaise définition ou interprétation des bases et solutions de base réalisables.
• Manque de justification dans les conditions d’optimalité.
• Incapacité à relier la solution duale à la sensibilité du problème primal.
• Modélisation incorrecte des variables et contraintes dans le problème d’application.

Enfin, pour démontrer l’optimalité d’une solution, il faut toujours vérifier la faisabilité et les conditions d’optimalité, en montrant notamment que les coefficients réduits sont négatifs ou nuls.