Search-9 : Programmation Linéaire et Simplexe (C# / .NET)

Navigation : << Search-8 Dancing Links | Index | Search-10 SymbolicAutomata >>

Twin .NET du notebook Search-09-LinearProgramming (Python/PuLP). Ce notebook est le port fidèle en C#/.NET utilisant Google OrTools (Google.OrTools.LinearSolver) — le solveur SOTA de Google, natif sur NuGet.

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez : 1. Formuler un problème d’optimisation en programmation linéaire (variables, fonction objectif, contraintes) 2. Résoudre un LP continu avec le solveur GLOP (simplexe) d’OrTools 3. Distinguer PL continue (variables réelles) et PLNE (variables entières/binaires) et résoudre un sac à dos avec CBC 4. Lire une analyse de sensibilité (prix fictifs / shadow prices) et interpréter la dualité

Prérequis

  • Notions d’algèbre linéaire et de géométrie des polyèdres (sommets, région admissible)
  • Search-1 à Search-8 (modélisation de problèmes de recherche)

Durée estimée : 60 minutes

Note : OrTools fournit plusieurs solveurs. GLOP (Google) est un simplexe pour la PL continue ; CBC (COIN-OR) gère la PLNE (variables entières/binaires). Les deux sont embarqués dans le NuGet Google.OrTools.

// Setup : chargement du solveur SOTA Google OrTools via NuGet.
#r "nuget: Google.OrTools, 9.11.4210"

using Google.OrTools.LinearSolver;
using Microsoft.DotNet.Interactive;
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;

"Environnement prêt — Google.OrTools.LinearSolver chargé.".Display();
Installed Packages
  • Google.OrTools, 9.11.4210
Environnement prêt — Google.OrTools.LinearSolver chargé.

1. Introduction à la Programmation Linéaire

La programmation linéaire (PL) modélise un problème d’optimisation dont la fonction objectif et les contraintes sont des combinaisons linéaires des variables de décision :

\[\max / \min\ z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n\]

sous contraintes \(a_{i1}x_1 + a_{i2}x_2 + \dots + a_{in}x_n \le / = / \ge\ b_i\) et \(x_j \ge 0\).

Pourquoi le simplexe est SOTA

L’algorithme du simplexe (Dantzig, 1947) exploite une propriété géométrique fondamentale : l’optimum d’un LP est atteint en un sommet du polyèdre des solutions admissibles. Plutôt qu’énumérer les sommets (exponentiel), le simplexe pivote de sommet en sommet adjacent en améliaurant toujours l’objectif — convergent en pratique en O(n) itérations bien que O(2ⁿ) dans le pire cas théorique.

OrTools GLOP implémente le simplexe révisé avec règles de pivotage anti-cyclage : c’est le vrai outil SOTA, pas une réimplémentation pédagogique.

Exemple introductif — Problème de production

Un atelier fabrique deux produits P1 et P2. Chaque unité de P1 rapporte 3 € et consomme 1 h machine + 2 h main-d’œuvre. Chaque unité de P2 rapporte 2 € et consomme 2 h machine + 1 h main-d’œuvre. Disponibilités : 4 h machine, 5 h main-d’œuvre. Combien produire de chaque pour maximiser le profit ?

Ressource P1 (unité) P2 (unité) Disponible
Machine 1 h 2 h 4 h
Main-d’œuvre 2 h 1 h 5 h
Profit 3 € 2 € —

2. Premier exemple avec OrTools — Problème de production

Formulation :

\[\max\ z = 3x_1 + 2x_2 \quad \text{s.c.} \quad x_1 + 2x_2 \le 4,\ \ 2x_1 + x_2 \le 5,\ \ x_1, x_2 \ge 0\]

L’API OrTools est proche de PuLP : on crée un Solver, des variables (MakeNumVar), on ajoute des contraintes (solver.Add), on fixe l’objectif (Maximize/Minimize), puis on appelle Solve().

// Problème de production — PL continue (GLOP)
var solver = Solver.CreateSolver("GLOP");

var x1 = solver.MakeNumVar(0.0, double.PositiveInfinity, "x1");
var x2 = solver.MakeNumVar(0.0, double.PositiveInfinity, "x2");

solver.Add(x1 + 2 * x2 <= 4.0);
solver.Add(2 * x1 + x2 <= 5.0);
solver.Maximize(3 * x1 + 2 * x2);

var result = solver.Solve();
var sb = new System.Text.StringBuilder();
sb.AppendLine("=== Problème de Production (GLOP) ===");
sb.AppendLine($"Statut          : {result}");
sb.AppendLine($"x1 (P1)         : {x1.SolutionValue():F2} unités");
sb.AppendLine($"x2 (P2)         : {x2.SolutionValue():F2} unités");
sb.AppendLine($"Profit maximal z: {solver.Objective().Value():F2} €");
sb.AppendLine();
sb.AppendLine("--- Vérification des contraintes ---");
sb.AppendLine($"  Machine     : {x1.SolutionValue() + 2*x2.SolutionValue():F2} <= 4");
sb.AppendLine($"  Main-d'œuvre: {2*x1.SolutionValue() + x2.SolutionValue():F2} <= 5");
sb.ToString().Display();
=== Problème de Production (GLOP) ===
Statut          : OPTIMAL
x1 (P1)         : 2,00 unités
x2 (P2)         : 1,00 unités
Profit maximal z: 8,00 €

--- Vérification des contraintes ---
  Machine     : 4,00 <= 4
  Main-d'œuvre: 5,00 <= 5

Interprétation : Production — Solution optimale

La solution optimale est x1 = 2, x2 = 1 pour un profit de 8 € (3·2 + 2·1). Vérification : - Machine : 2 + 2·1 = 4 = 4 (contrainte saturée) - Main-d’œuvre : 2·2 + 1 = 5 = 5 (contrainte saturée)

Les deux contraintes sont saturées : le point optimal est le sommet du polyèdre à l’intersection des deux droites. C’est précisément ce que le simplexe exploite — il se déplace sur la frontière jusqu’au sommet qui maximise z.

Comparaison PuLP ↔︎ OrTools : LpProblem("Production", LpMaximize) ↔︎ Solver.CreateSolver("GLOP") + Maximize(...) ; LpVariable('x1', lowBound=0) ↔︎ MakeNumVar(0, inf, "x1") ; prob += 3*x1+2*x2 ↔︎ Maximize(3*x1+2*x2).

3. Méthodologie de formulation — Problème de diet

Le problème de diet (minimisation) illustre la formulation avec contraintes ≥ (couverture minimale) et objectif de minimisation. Deux aliments A et B ; A coûte 1 €/unité, B coûte 2 €/unité. Apports :

Nutriment Aliment A Aliment B Besoin minimal
Protéines 2 3 12
Calcium 10 5 30
Fer 5 10 20

\[\min\ z = x_A + 2x_B \quad \text{s.c.} \quad 2x_A+3x_B \ge 12,\ \ 10x_A+5x_B \ge 30,\ \ 5x_A+10x_B \ge 20,\ \ x_A,x_B \ge 0\]

// Problème de diet — minimisation (GLOP)
var solverDiet = Solver.CreateSolver("GLOP");
var xA = solverDiet.MakeNumVar(0.0, double.PositiveInfinity, "xA");
var xB = solverDiet.MakeNumVar(0.0, double.PositiveInfinity, "xB");

solverDiet.Add(2 * xA + 3 * xB >= 12.0);   // Protéines
solverDiet.Add(10 * xA + 5 * xB >= 30.0);  // Calcium
solverDiet.Add(5 * xA + 10 * xB >= 20.0);  // Fer
solverDiet.Minimize(xA + 2 * xB);

var statutDiet = solverDiet.Solve();
var sb = new System.Text.StringBuilder();
sb.AppendLine("=== Problème de Diet (minimisation) ===");
sb.AppendLine($"Statut     : {statutDiet}");
sb.AppendLine($"xA (aliment A): {xA.SolutionValue():F2} unités");
sb.AppendLine($"xB (aliment B): {xB.SolutionValue():F2} unités");
sb.AppendLine($"Coût minimal : {solverDiet.Objective().Value():F2} €");
sb.ToString().Display();
=== Problème de Diet (minimisation) ===
Statut     : OPTIMAL
xA (aliment A): 6,00 unités
xB (aliment B): 0,00 unités
Coût minimal : 6,00 €

Interprétation : Diet — Mélange optimal

Le simplexe trouve le mélange au coût minimal satisfaisant les apports : xA = 6, xB = 0 pour un coût de 6 €.

Vérifions quelles contraintes sont saturées à ce point : - Protéines : 2·6 + 3·0 = 12 = 12 (saturée) - Calcium : 10·6 + 5·0 = 60 ≫ 30 (largeur de 30 — surplus) - Fer : 5·6 + 10·0 = 30 > 20 (surplus)

Seule la contrainte de protéines est saturée : c’est elle qui « tire » la solution. L’aliment A étant le moins cher (1 € vs 2 €) et riche en calcium/fer, le solveur en remplit jusqu’à satisfaire la protéine — d’où le surplus sur les autres nutriments. C’est l’écart de relaxation typique d’un problème de minimisation.

Exercice : Problème de mélange industriel

À vous de modéliser un mélange industriel (par ex. alliage métallurgique : 3 métaux, puretés minimales, coût minimal). Formulez puis complétez le stub ci-dessous.

Exercice : Problème de mélange industriel

Énoncé : une raffinerie produit de l’essence en mélangeant 3 crudes (C1, C2, C3) aux caractéristiques différentes. L’objectif est de minimiser le coût tout en respectant les spécifications du produit final.

Données : - Coûts : C1 = 40 €/baril, C2 = 50 €/baril, C3 = 35 €/baril - Teneur en soufre : C1 = 2 %, C2 = 1 %, C3 = 4 % - Indice d’octane : C1 = 85, C2 = 95, C3 = 75 - Contraintes du mélange final (100 barils au total) : - Teneur en soufre ≤ 2,5 % - Octane moyen ≥ 85 - Au moins 20 barils de chaque crude

Consignes : 1. Formulez le PL : variables x1, x2, x3 (barils de chaque crude), objectif (minimiser le coût total), contraintes de qualité. 2. Résolvez avec OrTools (Solver.CreateSolver("GLOP")). 3. Vérifiez que le mélange final respecte les spécifications (soufre, octane).

Indice : la teneur en soufre du mélange est la moyenne pondérée — la contrainte s’écrit (soufre_C1·x1 + soufre_C2·x2 + soufre_C3·x3) / 100 ≤ 2,5. Le raisonnement est identique pour l’octane moyen (avec un sens ≥).

// Exercice : Problème de mélange industriel (étudiant à compléter)
// Objectif : modéliser un mélange à coût minimal sous contraintes de qualité.
// Indice 1 : créer un Solver.CreateSolver("GLOP") + MakeNumVar par ingrédient.
// Indice 2 : les contraintes de pureté sont des >= (couverture minimale).
// Étape 1 : définir les variables
// Étape 2 : ajouter l'objectif Minimize(cout_total)
// Étape 3 : ajouter les contraintes de qualité
// Étape 4 : solver.Solve() et afficher
var solverMelange = Solver.CreateSolver("GLOP");
// TODO étudiant : compléter la modélisation
"Exercice à compléter — voir l'énoncé ci-dessus.".Display();
Exercice à compléter — voir l'énoncé ci-dessus.

4. Analyse de sensibilité et dualité

L’analyse de sensibilité répond à : de combien l’objectif améliorerait-il si on relâchait une contrainte d’une unité ? La réponse = prix fictif (shadow price / valeur duale) de la contrainte.

OrTools expose ces valeurs via Constraint.DualValue(). Pour une maximisation sous contraintes ≤, la valeur duale est positive : c’est précisément le gain marginal de l’objectif si l’on relâche le second membre d’une unité. C’est la dualité forte du LP : le problème primal (max) et son dual (min) ont la même valeur optimale à l’optimum.

// Analyse de sensibilité — prix fictifs (problème de production)
var solverSens = Solver.CreateSolver("GLOP");
var s1 = solverSens.MakeNumVar(0.0, double.PositiveInfinity, "x1");
var s2 = solverSens.MakeNumVar(0.0, double.PositiveInfinity, "x2");

var cMachine = solverSens.MakeConstraint(double.NegativeInfinity, 4.0, "Machine");
cMachine.SetCoefficient(s1, 1.0); cMachine.SetCoefficient(s2, 2.0);
var cMO = solverSens.MakeConstraint(double.NegativeInfinity, 5.0, "MainOeuvre");
cMO.SetCoefficient(s1, 2.0); cMO.SetCoefficient(s2, 1.0);
solverSens.Maximize(3 * s1 + 2 * s2);
solverSens.Solve();

var sb = new System.Text.StringBuilder();
sb.AppendLine("=== Analyse de Sensibilité (shadow prices) ===");
sb.AppendLine($"Solution optimale : x1={s1.SolutionValue():F2}, x2={s2.SolutionValue():F2}, z={solverSens.Objective().Value():F2}");
sb.AppendLine();
sb.AppendLine("Prix fictifs (valeur marginale d'une unité supplémentaire de ressource) :");
sb.AppendLine($"  Machine     : dual = {cMachine.DualValue():F2} €/h");
sb.AppendLine($"  Main-d'œuvre: dual = {cMO.DualValue():F2} €/h");
sb.ToString().Display();
=== Analyse de Sensibilité (shadow prices) ===
Solution optimale : x1=2,00, x2=1,00, z=8,00

Prix fictifs (valeur marginale d'une unité supplémentaire de ressource) :
  Machine     : dual = 0,33 €/h
  Main-d'œuvre: dual = 1,33 €/h

Interprétation : Shadow Prices

Le prix fictif d’une ressource mesure sa valeur marginale : combien vaudrait une heure supplémentaire de cette ressource ? Ici la Main-d’œuvre vaut 1,33 €/h (contre 0,33 €/h pour la Machine) : c’est la ressource la plus tendue, celle dont une heure supplémentaire rapporterait le plus. La Machine, moins critique, n’a qu’une faible valeur marginale.

Règle de complémentarité : à l’optimum, soit une contrainte est saturée (dual > 0), soit son dual est nul (contrainte non saturée = ressource en surplus, sans valeur marginale). C’est le théorème de l’écart complémentaire.

5. Programmation Linéaire en Nombres Entiers (PLNE)

Quand les variables doivent être entières (on ne peut produire 2,3 unités) ou binaires (décision oui/non), on bascule en PLNE. Le solveur CBC (COIN-OR Branch-and-Cut) explore un arbre de branchement en résolvant des relaxations continues — c’est NP-difficile mais CBC le gère efficacement pour les tailles pédagogiques.

Problème du sac à dos

5 objets, capacité 7 kg, maximiser la valeur :

Objet 1 2 3 4 5
Poids (kg) 2 1 3 2 4
Valeur (€) 12 10 20 15 25

\[\max \sum_j v_j x_j \quad \text{s.c.} \quad \sum_j p_j x_j \le 7,\ \ x_j \in \{0,1\}\]

// Sac à dos — PLNE binaire (CBC)
var solverK = Solver.CreateSolver("CBC");
var poids  = new double[] { 2, 1, 3, 2, 4 };
var valeurs = new double[] { 12, 10, 20, 15, 25 };
double capacite = 7.0;

var xk = new Variable[poids.Length];
for (int j = 0; j < poids.Length; j++)
    xk[j] = solverK.MakeIntVar(0, 1, $"x{j+1}");

var cCap = solverK.MakeConstraint(double.NegativeInfinity, capacite, "Capacite");
for (int j = 0; j < poids.Length; j++)
    cCap.SetCoefficient(xk[j], poids[j]);

// Objectif : somme pondérée valeur·x. On accumule les termes (double * Variable -> LinearExpr)
// car LinearExpr n'admet ni la conversion depuis int ni Sum() statique dans OrTools 9.11.
LinearExpr obj = valeurs[0] * xk[0];
for (int j = 1; j < poids.Length; j++)
    obj += valeurs[j] * xk[j];
solverK.Maximize(obj);
var statutK = solverK.Solve();

var sb = new System.Text.StringBuilder();
sb.AppendLine("=== Sac à dos (PLNE, CBC) ===");
sb.AppendLine($"Capacité : {capacite} kg");
sb.AppendLine($"Statut   : {statutK}");
sb.AppendLine($"Valeur optimale : {solverK.Objective().Value():F0} €");
sb.AppendLine("Objets sélectionnés :");
double poidsTotal = 0;
for (int j = 0; j < poids.Length; j++)
{
    if (xk[j].SolutionValue() > 0.5)
    {
        sb.AppendLine($"  x{j+1} = 1  (poids {poids[j]} kg, valeur {valeurs[j]} €)");
        poidsTotal += poids[j];
    }
}
sb.AppendLine($"Poids total utilisé : {poidsTotal:F0} kg / {capacite} kg");
sb.ToString().Display();
=== Sac à dos (PLNE, CBC) ===
Capacité : 7 kg
Statut   : OPTIMAL
Valeur optimale : 50 €
Objets sélectionnés :
  x2 = 1  (poids 1 kg, valeur 10 €)
  x4 = 1  (poids 2 kg, valeur 15 €)
  x5 = 1  (poids 4 kg, valeur 25 €)
Poids total utilisé : 7 kg / 7 kg

Interprétation : Sac à dos — Sélection optimale

Le branch-and-cut de CBC trouve la combinaison binaire optimale. Notez qu’arrondir la solution de la relaxation continue ne donne PAS l’optimum entier — c’est toute la raison d’être du PLNE : la relaxation est une borne supérieure (pour un max), le PLNE donne la vraie solution faisable.

Exercice : Problème de couverture d’ensemble (Set Cover)

Énoncé : une ville doit placer des antennes relais sur un ensemble de sites candidats. Chaque site couvre un sous-ensemble de quartiers. L’objectif est de couvrir tous les quartiers à coût minimal.

Données : 6 quartiers à couvrir (Q1–Q6) et 4 sites candidats :

Site Coût (k€) Quartiers couverts
S1 10 Q1, Q2, Q3
S2 8 Q2, Q4
S3 12 Q3, Q5, Q6
S4 7 Q1, Q4, Q5

Consignes : 1. Modélisez comme un PLNE avec variables binaires y_j (1 si le site j est sélectionné). 2. Ajoutez une contrainte de couverture pour chaque quartier. 3. Minimisez le coût total. 4. Affichez les sites sélectionnés et le coût.

Indice : pour chaque quartier i, la contrainte est \(\sum_{j \text{ couvre } i} y_j \geq 1\).

// Exercice : Set Cover (étudiant à compléter)
// Indice 1 : Solver.CreateSolver("CBC") + MakeIntVar(0,1) par sous-ensemble.
// Indice 2 : pour chaque élément, la somme des x_S qui le couvrent doit être >= 1.
// Étape 1 : variables binaires par sous-ensemble
// Étape 2 : Minimize(coût total)
// Étape 3 : contraintes de couverture (>= 1 par élément)
// Étape 4 : Solve() + afficher les sous-ensembles choisis
var solverSC = Solver.CreateSolver("CBC");
// TODO étudiant : modéliser le set cover
"Exercice à compléter — voir l'énoncé ci-dessus.".Display();
Exercice à compléter — voir l'énoncé ci-dessus.

Exercice : Optimisation multi-objectif avec contraintes priorisées

Modélisez un problème à deux objectifs (par ex. maximiser profit ET minimiser émissions CO₂) via la méthode des poids ou les contraintes priorisées (un objectif principal, l’autre borné). Formulez puis complétez le stub.

// Exercice : Multi-objectif par contraintes priorisées (étudiant à compléter)
// Indice : max profit s.c. émissions <= seuil. Faire varier le seuil = front de Pareto.
// Étape 1 : variables + objectif profit (Maximize)
// Étape 2 : contrainte d'émission (<= seuil)
// Étape 3 : Solve() pour plusieurs valeurs de seuil
var solverMO = Solver.CreateSolver("GLOP");
// TODO étudiant : optimisation multi-objectif
"Exercice à compléter — voir l'énoncé ci-dessus.".Display();
Exercice à compléter — voir l'énoncé ci-dessus.

6. Problème de Transport

Le problème de transport achemine un bien de plusieurs sources (usines) vers plusieurs destinations (magasins) à coût minimal. C’est un LP à structure creuse : une variable x_ij par paire source→destination.

Modèle (m sources, n destinations, coûts unitaires c_ij, offres s_i, demandes d_j) :

\[\min z = \sum_{i=1}^m \sum_{j=1}^n c_{ij}\, x_{ij} \quad \text{s.c.} \quad \sum_{j=1}^n x_{ij} \le s_i\ \ (\text{offre}),\ \ \sum_{i=1}^m x_{ij} \ge d_j\ \ (\text{demande}),\ \ x_{ij} \ge 0\]

Données (twin fidèle du §4 Python/PuLP) — 3 usines × 4 magasins, problème équilibré (capacité totale = demande totale = 450) :

Usine  Magasin M1 M2 M3 M4 Capacité
U1 2 3 1 4 100
U2 5 2 3 2 150
U3 3 4 2 1 200
Demande 80 120 100 150 450

L’API OrTools traduit littéralement la formulation PuLP : MakeNumVar ↔︎ LpVariable, MakeConstraint(lb, ub, "name") + SetCoefficient ↔︎ prob += expr, "name", Minimize ↔︎ LpMinimize.

// Problème de Transport — PL continue (GLOP). Twin .NET de §4 (notebook Python/PuLP).
var solverT = Solver.CreateSolver("GLOP");

// 3 usines (sources) × 4 magasins (destinations)
string[] usines = { "U1", "U2", "U3" };
string[] magasins = { "M1", "M2", "M3", "M4" };
double[,] couts = {
    { 2, 3, 1, 4 },   // U1 -> M1..M4
    { 5, 2, 3, 2 },   // U2
    { 3, 4, 2, 1 },   // U3
};
double[] capacites = { 100, 150, 200 };     // offre par usine
double[] demandes  = { 80, 120, 100, 150 }; // demande par magasin
int m = usines.Length, n = magasins.Length;

// Variables x_ij >= 0 : quantité transportée de l'usine i vers le magasin j
var x = new Variable[m, n];
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        x[i, j] = solverT.MakeNumVar(0.0, double.PositiveInfinity, $"x_{usines[i]}_{magasins[j]}");

// Offre : Σ_j x_ij <= capacites[i]
for (int i = 0; i < m; i++)
{
    var c = solverT.MakeConstraint(double.NegativeInfinity, capacites[i], $"Offre_{usines[i]}");
    for (int j = 0; j < n; j++) c.SetCoefficient(x[i, j], 1.0);
}

// Demande : Σ_i x_ij >= demandes[j]
for (int j = 0; j < n; j++)
{
    var c = solverT.MakeConstraint(demandes[j], double.PositiveInfinity, $"Demande_{magasins[j]}");
    for (int i = 0; i < m; i++) c.SetCoefficient(x[i, j], 1.0);
}

// Objectif : min Σ c_ij x_ij. Accumulation depuis le 1er terme (OrTools 9.11 sans Sum() statique, cf. §5 sac à dos).
LinearExpr coutTotal = couts[0, 0] * x[0, 0];
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        if (!(i == 0 && j == 0))
            coutTotal += couts[i, j] * x[i, j];
solverT.Minimize(coutTotal);

var statutT = solverT.Solve();
var sb = new System.Text.StringBuilder();
sb.AppendLine("=== Problème de Transport (GLOP) ===");
sb.AppendLine($"Statut           : {statutT}");
sb.AppendLine($"Coût total min.  : {solverT.Objective().Value():F0} €");
sb.AppendLine();
sb.AppendLine("Matrice des flux optimaux (lignes = usines, colonnes = magasins) :");
sb.AppendLine("       M1   M2   M3   M4  | expédié / capacité");
for (int i = 0; i < m; i++)
{
    double expedie = 0;
    var ligne = $"  {usines[i]} | ";
    for (int j = 0; j < n; j++) { ligne += $"{x[i, j].SolutionValue(),4:F0} "; expedie += x[i, j].SolutionValue(); }
    ligne += $"| {expedie,3:F0} / {capacites[i]}";
    sb.AppendLine(ligne);
}
double totalCap = capacites.Sum();
double totalDem = demandes.Sum();
sb.AppendLine($"  Demande reçue  : {string.Join("  ", demandes.Select(d => $"{d,3:F0}"))}  (total {totalDem:F0})");
sb.AppendLine();
sb.AppendLine($"Total capacité = {totalCap:F0}, total demande = {totalDem:F0} → problème {(totalCap == totalDem ? "équilibré" : "déséquilibré")}.");
sb.ToString().Display();
=== Problème de Transport (GLOP) ===
Statut           : OPTIMAL
Coût total min.  : 760 €

Matrice des flux optimaux (lignes = usines, colonnes = magasins) :
       M1   M2   M3   M4  | expédié / capacité
  U1 |    0    0  100    0 | 100 / 100
  U2 |    0  120    0   30 | 150 / 150
  U3 |   80    0    0  120 | 200 / 200
  Demande reçue  :  80  120  100  150  (total 450)

Total capacité = 450, total demande = 450 → problème équilibré.

Interprétation : Transport — Plan optimal à 760 €

GLOP trouve un coût total minimal de 760 €, identique à celui du twin Python/PuLP — ce qui confirme la fidélité du portage. Toutes les capacités d’usine sont saturées (problème équilibré : 450 unités expédiées = 450 demandées) et chaque magasin reçoit exactement sa demande. Le flux optimal renvoyé par GLOP (5 routes) diffère de celui du twin Python (6 routes) : un LP de transport admet souvent plusieurs optima de même coût 760 €.

Points clés :

  1. Solution de base creuse : un sommet optimal d’un LP de transport active au plus m + n − 1 = 6 routes sur les 12 possibles. Ici GLOP en active 5 (sommet dégénéré : une variable de base vaut 0) — la matrice a m + n − 1 contraintes linéairement indépendantes.
  2. Unimodularité : la matrice des contraintes d’un problème de transport est totalement unimodulaire. Conséquence : si les offres et demandes sont entières, l’optimum du LP relaxé est automatiquement entier — aucun besoin de PLNE (CBC), GLOP suffit.
  3. Coûts marginaux : comme pour la production (§2) et le sac à dos (§5), Constraint.DualValue() expose le shadow price d’une contrainte — la valeur d’augmenter d’une unité la capacité d’une usine ou le niveau de demande d’un magasin.

Comparaison PuLP ↔︎ OrTools : pulp.lpSum(couts[(i,j)] * x[(i,j)]) ↔︎ accumulation LinearExpr (OrTools 9.11 n’expose pas de Sum() statique, cf. §5) ; prob += lpSum(x_ij) <= capacites[i] ↔︎ MakeConstraint(-inf, capacites[i], "Offre_U1") + SetCoefficient(x_ij, 1.0).

7. Problème de transport multi-dépôts

Le §6 traitait un transport équilibré (offre totale = demande totale). Le cas multi-dépôts généralise : plusieurs sources (dépôts) vers plusieurs puits (clients), et soulève la question de l’équilibrage quand l’offre ne correspond pas à la demande.

Énoncé (twin .NET de l’« Exemple guide 4 » du notebook Python/PuLP) : une entreprise livre depuis 2 dépôts (D1, D2) vers 3 clients (C1, C2, C3).

Dépôt  Client C1 C2 C3 Capacité
D1 4 6 3 50
D2 5 2 7 40
Demande 30 25 35 90

Capacité totale = 50 + 40 = 90 ; demande totale = 30 + 25 + 35 = 90 → équilibré. Le notebook Python laisse ce problème en exercice (stub PuLP) ; le twin C# en donne la solution OrTools ci-dessous (divergence positive documentée : le C# résout ce que le Python propose à l’étudiant).

// Transport multi-dépôts — PL continue (GLOP). Twin .NET de l'Exemple guide 4 (Python/PuLP).
var solverMD = Solver.CreateSolver("GLOP");

string[] depots = { "D1", "D2" };
string[] clients = { "C1", "C2", "C3" };
double[,] coutsMD = {
    { 4, 6, 3 },   // D1 -> C1,C2,C3
    { 5, 2, 7 },   // D2
};
double[] capacitesMD = { 50, 40 };     // offre par dépôt
double[] demandesMD  = { 30, 25, 35 }; // demande par client
int mMD = depots.Length, nMD = clients.Length;

// Variables x_ij >= 0 : quantité livrée du dépôt i au client j
var xMD = new Variable[mMD, nMD];
for (int i = 0; i < mMD; i++)
    for (int j = 0; j < nMD; j++)
        xMD[i, j] = solverMD.MakeNumVar(0.0, double.PositiveInfinity, $"x_{depots[i]}_{clients[j]}");

// Offre : Σ_j x_ij <= capacites[i]
for (int i = 0; i < mMD; i++)
{
    var c = solverMD.MakeConstraint(double.NegativeInfinity, capacitesMD[i], $"Offre_{depots[i]}");
    for (int j = 0; j < nMD; j++) c.SetCoefficient(xMD[i, j], 1.0);
}
// Demande : Σ_i x_ij >= demandes[j]
for (int j = 0; j < nMD; j++)
{
    var c = solverMD.MakeConstraint(demandesMD[j], double.PositiveInfinity, $"Demande_{clients[j]}");
    for (int i = 0; i < mMD; i++) c.SetCoefficient(xMD[i, j], 1.0);
}

// Objectif : min Σ c_ij x_ij (accumulation depuis le 1er terme, OrTools 9.11 sans Sum() statique).
LinearExpr coutMD = coutsMD[0, 0] * xMD[0, 0];
for (int i = 0; i < mMD; i++)
    for (int j = 0; j < nMD; j++)
        if (!(i == 0 && j == 0))
            coutMD += coutsMD[i, j] * xMD[i, j];
solverMD.Minimize(coutMD);

var statutMD = solverMD.Solve();
var sbMD = new System.Text.StringBuilder();
sbMD.AppendLine("=== Transport multi-dépôts équilibré (GLOP) ===");
sbMD.AppendLine($"Statut           : {statutMD}");
sbMD.AppendLine($"Coût total min.  : {solverMD.Objective().Value():F0} €");
sbMD.AppendLine();
sbMD.AppendLine("Flux optimaux (lignes = dépôts, colonnes = clients) :");
sbMD.AppendLine("       C1   C2   C3  | expédié / capacité");
for (int i = 0; i < mMD; i++)
{
    double expedie = 0;
    var ligne = $"  {depots[i]} | ";
    for (int j = 0; j < nMD; j++) { ligne += $"{xMD[i, j].SolutionValue(),4:F0} "; expedie += xMD[i, j].SolutionValue(); }
    ligne += $"| {expedie,3:F0} / {capacitesMD[i]}";
    sbMD.AppendLine(ligne);
}
sbMD.AppendLine($"  Demande reçue  : {string.Join("  ", demandesMD.Select(d => $"{d,3:F0}"))}  (total {demandesMD.Sum():F0})");
sbMD.ToString().Display();
=== Transport multi-dépôts équilibré (GLOP) ===
Statut           : OPTIMAL
Coût total min.  : 290 €

Flux optimaux (lignes = dépôts, colonnes = clients) :
       C1   C2   C3  | expédié / capacité
  D1 |   15    0   35 |  50 / 50
  D2 |   15   25    0 |  40 / 40
  Demande reçue  :  30   25   35  (total 90)

Interprétation : multi-dépôts — optimum à 290 €

GLOP livre un coût minimal de 290 €. Le plan optimal exploite les routes les moins chères : D1→C3 (3 €, 35 colis) et D2→C2 (2 €, 25 colis), puis répartit C1 entre D1 et D2 (15 colis chacun). Les routes coûteuses D1→C2 (6 €) et D2→C3 (7 €) restent inutilisées à l’optimum — signe que la solution est bien un sommet du polyèdre.

Cas déséquilibré — exercice de modélisation (Prong-B). Si la capacité totale devient inférieure à la demande (ex. D2 ramené à 30 → offre 80 < demande 90), le LP est infaisable tel quel : 10 unités de demande ne peuvent être satisfaites. La technique standard consiste à ajouter un dépôt fictif (dummy) de capacité 10 et de coût nul ; les flux vers le dummy représentent la demande non satisfaite. Le solveur résout alors le LP augmenté et quantifie le manque. On le démontre ci-dessous : c’est une étape de modélisation (dummy) que le cas équilibré du §6 ne nécessitait pas — d’où sa valeur pédagogique.

// Cas déséquilibré : D2 réduit à 30 (offre 80 < demande 90). Dépôt fictif DUMMY cap 10, coût 0.
var solverU = Solver.CreateSolver("GLOP");

string[] depotsU = { "D1", "D2", "DUMMY" };
string[] clientsU = { "C1", "C2", "C3" };
double[,] coutsU = {
    { 4, 6, 3 },   // D1
    { 5, 2, 7 },   // D2 (capacité réduite)
    { 0, 0, 0 },   // DUMMY = demande non satisfaite (coût 0)
};
double[] capacitesU = { 50, 30, 10 };    // offre réelle 80 + dummy 10 = 90
double[] demandesU  = { 30, 25, 35 };
int mU = depotsU.Length, nU = clientsU.Length;

var xU = new Variable[mU, nU];
for (int i = 0; i < mU; i++)
    for (int j = 0; j < nU; j++)
        xU[i, j] = solverU.MakeNumVar(0.0, double.PositiveInfinity, $"x_{depotsU[i]}_{clientsU[j]}");

for (int i = 0; i < mU; i++)
{
    var c = solverU.MakeConstraint(double.NegativeInfinity, capacitesU[i], $"Offre_{depotsU[i]}");
    for (int j = 0; j < nU; j++) c.SetCoefficient(xU[i, j], 1.0);
}
for (int j = 0; j < nU; j++)
{
    var c = solverU.MakeConstraint(demandesU[j], double.PositiveInfinity, $"Demande_{clientsU[j]}");
    for (int i = 0; i < mU; i++) c.SetCoefficient(xU[i, j], 1.0);
}

LinearExpr coutU = coutsU[0, 0] * xU[0, 0];
for (int i = 0; i < mU; i++)
    for (int j = 0; j < nU; j++)
        if (!(i == 0 && j == 0))
            coutU += coutsU[i, j] * xU[i, j];
solverU.Minimize(coutU);

var statutU = solverU.Solve();
var sbU = new System.Text.StringBuilder();
sbU.AppendLine("=== Transport déséquilibré + dépôt fictif (GLOP) ===");
sbU.AppendLine($"Statut           : {statutU}");
sbU.AppendLine($"Coût total min.  : {solverU.Objective().Value():F0} € (hors pénalité de demande non satisfaite)");
sbU.AppendLine();
for (int i = 0; i < mU; i++)
    for (int j = 0; j < nU; j++)
    {
        double v = xU[i, j].SolutionValue();
        if (v > 1e-6) sbU.AppendLine($"  {depotsU[i]} -> {clientsU[j]} = {v:F0}");
    }
double nonSatisfait = 0;
for (int j = 0; j < nU; j++) nonSatisfait += xU[mU - 1, j].SolutionValue();
sbU.AppendLine();
sbU.AppendLine($"Demande non satisfaite (via DUMMY) = {nonSatisfait:F0} colis sur {demandesU.Sum():F0} demandés.");
sbU.ToString().Display();
=== Transport déséquilibré + dépôt fictif (GLOP) ===
Statut           : OPTIMAL
Coût total min.  : 240 € (hors pénalité de demande non satisfaite)

  D1 -> C1 = 15
  D1 -> C3 = 35
  D2 -> C1 = 5
  D2 -> C2 = 25
  DUMMY -> C1 = 10

Demande non satisfaite (via DUMMY) = 10 colis sur 90 demandés.

Conclusion

Ce notebook a présenté la programmation linéaire en C#/.NET avec Google OrTools — le pendant du notebook Python/PuLP.

Récapitulatif

Concept API OrTools Solveur Équivalent PuLP
PL continue (max/min) MakeNumVar, solver.Add, Maximize/Minimize GLOP (simplexe) LpProblem, LpVariable('Continuous')
PLNE binaire/entière MakeIntVar(0,1) / MakeIntVar CBC (branch-and-cut) LpVariable('Binary') / ('Integer')
Analyse de sensibilité Constraint.DualValue() GLOP prob.constraints[i].pi
Contrainte nommée MakeConstraint(lb, ub, "name") + SetCoefficient — prob += expr, "name"

Points clés

  1. OrTools est le vrai solveur SOTA (GLOP = simplexe révisé Google, CBC = branch-and-cut COIN-OR) — ce n’est pas une réimplémentation pédagogique. Les solveurs sont embarqués nativement dans le NuGet.
  2. Géométrie du simplexe : l’optimum d’un LP est un sommet du polyèdre admissible ; le simplexe pivote de sommet en sommet.
  3. Dualité forte : les shadow prices (DualValue) mesurent la valeur marginale des ressources et satisfont l’écart complémentaire.
  4. PLNE ≠ PL arrondie : le branch-and-cut explore un arbre ; la relaxation continue n’est qu’une borne.

Pour aller plus loin

  • Problème de transport : traité en §6 ci-dessus (coût optimal 760 €). Pour aller plus loin, voir flot à coût minimal (Google.OrTools.Graph).
  • Méthode du simplexe à la main : voir Search-01-StateSpace pour les fondations géométriques.
  • OrTools avancé : Google.OrTools.Sat (CP-SAT) pour la programmation par contraintes, Google.OrTools.Graph pour le flot min-cost.

Références

  • Google OrTools — Linear Solver (GLOP, CBC, GLPK, SCIP).
  • Dantzig, G. (1947), origine du simplexe.
  • Vanderbei, R., Linear Programming: Foundations and Extensions.
  • Twin Python : Search-09-LinearProgramming (PuLP).

Troisième tranche du twin .NET⇄Python (#4956, marathon). Sections suivantes à venir : multi-objectif, comparaison PL vs PLNE approfondie. (Transport traité en §6.)

Retour au sommet