Navigation : Index | >> Z3.Linq

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.IO;
using System.Linq;
using System.Text;

#r "nuget: XPlot.Plotly.Interactive"
Installing Packages
  • XPlot.Plotly.Interactive
Loading extensions from `~\.nuget\packages\xplot.plotly.interactive\4.1.0\lib\net7.0\XPlot.Plotly.Interactive.dll`

Configuration de l’environnement C

Nous commençons par importer les bibliothèques .NET nécessaires pour manipuler les données et créer des visualisations. Ces bibliothèques nous permettront de :

  • Gérer les collections de données (System.Collections.Generic)
  • Lire et écrire des fichiers (System.IO)
  • Manipuler des chaînes de caractères (System.Linq, System.Text)
  • Créer des graphiques avec XPlot.Plotly

Cette étape prépare l’environnement avant l’installation d’OR-Tools.

Installation de OR-Tools

Pour utiliser OR-Tools avec C#, nous devons d’abord installer la bibliothèque. Vous pouvez suivre les instructions sur le site officiel de Google OR-Tools.

Installation de OR-Tools

On appelle le package Nuget correspondant.

Installation de la bibliothèque OR-Tools

Google OR-Tools est disponible via NuGet, le gestionnaire de packages .NET. L’installation charge automatiquement :

  • Le solveur GLOP (Google Linear Optimization Package) pour la programmation linéaire
  • Les wrappers C# pour interagir avec les solveurs natifs
  • Les dépendances nécessaires

Note technique : OR-Tools utilise des solveurs natifs optimisés (écrit en C++) avec des bindings pour C#. Le package NuGet contient les bibliothèques natives pour Windows, Linux et macOS.

Comprendre les données du problème

Avant de modéliser le problème, il est essentiel de comprendre la structure des données.

Structure du problème de Stigler

Le problème comporte deux types de données principales :

  1. Les besoins nutritionnels minimaux : 9 nutriments avec leurs apports quotidiens recommandés
  2. Les aliments disponibles : 77 aliments avec leurs prix et contenus nutritionnels

Analyse des contraintes nutritionnelles

Les apports minimaux recommandés en 1939 reflètent les connaissances nutritionnelles de l’époque :

Nutriment Apport minimal Remarque
Calories 3000 kcal Besoin énergétique moyen d’un adulte actif
Protéines 70 g Essentiel pour la construction musculaire
Calcium 0,8 g Important pour les os
Fer 12 mg Transport de l’oxygène dans le sang
Vitamines A, B1, B2, C, Niacine Variables Prévention des carences

Contexte historique : En 1939, Stigler a résolu ce problème manuellement en 120 jours de calculs. La solution optimale trouvée était de 39,93 $ par an. Aujourd’hui, un ordinateur résout ce problème en quelques millisecondes.

Analyse de la base de données alimentaire

La base contient 77 aliments répartis en catégories :

  • Céréales et farines (8 produits) : base énergétique peu coûteuse
  • Produits laitiers (6 produits) : sources de calcium et protéines
  • Viandes et poissons (15 produits) : sources de protéines et fer
  • Fruits et légumes (23 produits) : sources de vitamines
  • Conserves (13 produits) : alternatives aux produits frais
  • Produits secs (5 produits) : légumineuses riches en protéines
  • Autres (7 produits) : café, thé, sucre, chocolat

Chaque aliment est caractérisé par : - Son prix unitaire (en cents de 1939) - Son contenu nutritionnel pour 9 nutriments

Les tableaux ci-dessous présentent ces données en détail.

#r "nuget: Google.OrTools"
Installing Packages
  • Google.OrTools

Importer le solveur de programmation linéaire

Nous importons maintenant le namespace Google.OrTools.LinearSolver qui contient les classes nécessaires pour :

  • Solver : le solveur de programmation linéaire
  • Variable : représenter les variables de décision
  • Constraint : définir les contraintes du problème
  • Objective : définir la fonction objectif à optimiser

Ces classes nous permettront de formuler mathématiquement le problème de Stigler.

Liste des nutriments

Nutriments Apport quotidien recommandé
Calories 3 000 calories
Protéines 70 g
Calcium 0,8 g
Fer 12 milligrammes
Vitamine A 5 000 UI
Thiamine (vitamine B1) 1,8 milligramme
Riboflavine (vitamine B2) 2,7 milligrammes
Niacine 18 milligrammes
Acide ascorbique (vitamine C) 75 milligrammes

Liste des marchandises (corpus de Stigler 1939)

Marchandises Unité Prix 1939 (cents) Calories (kcal) Protéines (g) Calcium (g) Fer (mg) Vitamine A (KIU) Thiamine (mg) Riboflavine (mg) Niacine (mg) Acide ascorbique (mg)
Farine de blé (enrichi) 4,5 kg 36 44,7 1411 2 365 0 55.4 33.3 441 0
Moutarde 1 kg 14.1 11.6 418 0.7 54 0 3.2 1.9 68 0
Céréales de blé (enrichies) 800 g 24.2 11.8 377 14.4 175 0 14.4 8.8 114 0
Flocons de maïs 225 g 7.1 11.4 252 0.1 56 0 13.5 2.3 68 0
Farine de maïs 1 kg 4.6 36.0 897 1.7 99 30.9 17.4 7.9 106 0
Hominy Grits 24 oz 8.5 28.6 680 0,8 80 0 10.6 1.6 110 0
Riz 1 kg 7.5 21.2 460 0.6 41 0 2 4.8 60 0
Avoine roulée 1 kg 7.1 25,3 907 5.1 341 0 37.1 8.9 64 0
Pain blanc (enrichi) 1 kg 7.9 15.0 488 2.5 115 0 13.8 8.5 126 0
Pain au blé complet 1 kg 9.1 12.2 484 2.7 125 0 13.9 6.4 160 0
Pain de seigle 1 kg 9.1 12.4 439 1.1 82 0 9.9 3 66 0
Cake 1 kg 24.8 8.0 130 0.4 31 18,9 2.8 3 17 0
Crackers à soda 1 kg 15.1 12.5 288 0.5 50 0 0 0 0 0
Lait 1 qt 11 6.1 310 10.5 18 16,8 4 16 7 177
Lait évaporé (boîte) 14,5 oz 6.7 8.4 422 15.1 9 26 3 23.5 11 60
Beurre 1 kg 30.8 10.8 9 0,2 3 44.2 0 0,2 2 0
Oléomargarine 1 kg 16.1 20,6 17 0.6 6 55.8 0,2 0 0 0
Œufs 1 douz. 32.6 2.9 238 1 52 18,6 2.8 6.5 1 0
Fromage (Cheddar) 1 kg 24.2 7.4 448 16.4 19 28,1 0,8 10.3 4 0
Crème 1/2 pt 14.1 3.5 49 1.7 3 16,9 0,6 2.5 0 17
Beurre de cacahuète 1 kg 17.9 15.7 661 1 48 0 9.6 8.1 471 0
Mayonnaise 1/2 pt 16.7 8.6 18 0,2 8 2,7 0,4 0.5 0 0
Crisco 1 kg 20.3 20.1 0 0 0 0 0 0 0 0
Lard 1 kg 9.8 41.7 0 0 0,2 0 0 0.5 5 0
Faux-filet 1 kg 39.6 2.9 166 0,1 34 0,2 2.1 2.9 69 0
Viande ronde 1 kg 36.4 2.2 214 0,1 32 0,4 2.5 2.4 87 0
Rôti de côtelette 1 kg 29.2 3.4 213 0,1 33 0 0 2 0 0
Chuck roast 1 kg 22.6 3.6 309 0,2 46 0,4 1 4 120 0
Assiette 1 kg 14.6 8.5 404 0,2 62 0 0.9 0 0 0
Foie (bœuf) 1 kg 26.8 2.2 333 0,2 139 169,2 6.4 50,8 316 525
Cuisse d’agneau 1 kg 27.6 3.1 245 0,1 20 0 2.8 3.9 86 0
Côtes d’agneau 1 kg 36.6 3.3 140 0,1 15 0 1.7 2.7 54 0
Côtes de porc 1 kg 30.7 3.5 196 0,2 30 0 17.4 2.7 60 0
Filet de porc rôti 1 kg 24.2 4.4 249 0.3 37 0 18.2 3.6 79 0
Bacon 1 kg 25.6 10.4 152 0,2 23 0 1.8 1.8 71 0
Jambon fumé 1 kg 27.4 6.7 212 0,2 31 0 9.9 3.3 50 0
Porc salé 1 kg 16 18,8 164 0,1 26 0 1.4 1.8 0 0
Poulet rôti 1 kg 30.3 1.8 184 0,1 30 0,1 0.9 1.8 68 46
Escalopes de veau 1 kg 42.3 1.7 156 0,1 24 0 1.4 2.4 57 0
Saumon, rose (boîte) 500 g 13 5.8 705 6.8 45 3.5 1 4.9 209 0
Pommes 1 kg 4.4 5.8 27 0.5 36 7.3 3.6 2.7 5 544
Bananes 1 kg 6.1 4.9 60 0.4 30 17.4 2.5 3.5 28 498
Citrons 1 douz. 26 1 21 0.5 14 0 0.5 0 4 952
Oranges 1 douz. 30.9 2.2 40 1.1 18 11.1 3.6 1.3 10 1998
Haricots verts 1 kg 7.1 2.4 138 3.7 80 69 4.3 5.8 37 862
Chou 1 kg 3.7 2.6 125 4.0 36 7.2 9 4.5 26 5369
Carottes 1 groupe 4.7 2.7 73 2.8 43 188.5 6.1 4.3 89 608
Le céleri 1 tige 7.3 0.9 51 3.0 23 0.9 1.4 1.4 9 313
Laitue 1 tête 8.2 0.4 27 1.1 22 112.4 1.8 3.4 11 449
Oignons 1 kg 3.6 5.8 166 3.8 59 16.6 4.7 5.9 21 1184
Des pommes de terre 6 kg 34 14.3 336 1.8 118 6.7 29.4 7.1 198 2522
Épinards 1 kg 8.1 1.1 106 0 138 918.4 5.7 13.8 33 2755
Patates douces 1 kg 5.1 9.6 138 2.7 54 290.7 8.4 5.4 83 1912
Pêches (boîte de conserve) N° 2 1/2 16.8 3.7 20 0.4 10 21.5 0.5 1 31 196
Poires (boîte) N° 2 1/2 20.4 3.0 8 0.3 8 0,8 0,8 0,8 5 81
Ananas (boîte) N° 2 1/2 21.3 2.4 16 0.4 8 2 2.8 0,8 7 399
Asperges (boîte) N° 2 27,7 0.4 33 0.3 12 16.3 1.4 2.1 17 272
Haricots verts (boîte) N° 2 10 1 54 2 65 53.9 1.6 4.3 32 431
Porc et haricots (boîte) 500 g 7.1 7.5 364 4 134 3.5 8.3 7.7 56 0
Maïs (boîte) N° 2 10.4 5.2 136 0,2 16 12 1.6 2.7 42 218
Pois (boîte) N° 2 13.8 2.3 136 0.6 45 34.9 4.9 2.5 37 370
Tomates (boîte) N° 2 8.6 1.3 63 0.7 38 53.2 3.4 2.5 36 1253
Tomates (boîte) N° 2 8.6 1.3 63 0.7 38 53.2 3.4 2.5 36 1253
Soupe à la tomate (boîte de conserve) 300 g 7.6 1.6 71 0.6 43 57.9 3.5 2.4 67 862
Pêches, séchées 1 kg 15.7 8.5 87 1.7 173 86.8 1.2 4.3 55 57
Pruneaux séchés 1 kg 9 12.8 99 2.5 154 85.7 3.9 4.3 65 257
Raisins secs et séchés 500 g 9.4 13.5 104 2.5 136 4.5 6.3 1.4 24 136
Pois séchés 1 kg 7.9 20.0 1 367 4.2 345 2.9 28.7 18.4 162 0
Haricots Lima secs 1 kg 8.9 17.4 1055 3.7 459 5.1 26.9 38.2 93 0
Haricots de marine secs 1 kg 5.9 26.9 1691 11.4 792 0 38.4 24.6 217 0
Café 1 kg 22.4 0 0 0 0 0 4 5.1 50 0
Thé 1/4 lb 17.4 0 0 0 0 0 0 2.3 42 0
Cacao 225 g 8.6 8.7 237 3 72 0 2 11.9 40 0
Chocolat 225 g 16.2 8.0 77 1.3 39 0 0.9 3.4 14 0
Sucre 4,5 kg 51.7 34.9 0 0 0 0 0 0 0 0
Sirop de maïs 24 oz 13.7 14.7 0 0.5 74 0 0 0 5 0
Mélasse 500 g 13.6 9.0 0 10.3 244 0 1.9 7.5 146 0
Conserves de fraises 1 kg 20.5 6.4 11 0.4 7 0.2 0.2 0.4 3 0

Chargement des données en mémoire

Nous définissons maintenant deux structures de données :

  1. nutrients : tableau des 9 nutriments avec leurs apports minimaux quotidiens
  2. data : tableau des 77 aliments avec leur nom, unité, prix et contenu nutritionnel

Structure des données

Chaque aliment est représenté par un tuple contenant : - Name : nom de l’aliment (ex: “Wheat Flour (Enriched)”) - Unit : unité de mesure (ex: “10 lb.”, “1 qt.”) - Price : prix en cents (année 1939) - Nutrients : tableau de 9 valeurs représentant le contenu en chaque nutriment

Note : Les unités varient selon les aliments (livres, onces, douzaines, etc.). Le solveur gère automatiquement ces différences en calculant le coût et les apports par unité.

Importer le wrapper de solution linéaire

Création du solveur de programmation linéaire

Nous créons maintenant une instance du solveur GLOP (Google Linear Optimization Package).

Qu’est-ce que GLOP ?

GLOP est un solveur de programmation linéaire développé par Google qui implémente l’algorithme du simplexe révisé. Il est optimisé pour :

  • Les problèmes de grande taille (milliers de variables et contraintes)
  • La précision numérique
  • La rapidité d’exécution

Formulation mathématique du problème

Le problème de Stigler peut être formulé comme un problème de programmation linéaire :

Variables de décision : \(x_i\) = quantité de l’aliment \(i\) à acheter (en unités)

Fonction objectif : Minimiser le coût total \[\min \sum_{i=1}^{77} p_i \cdot x_i\]

où \(p_i\) est le prix de l’aliment \(i\)

Contraintes nutritionnelles : Pour chaque nutriment \(j\) (j = 1 à 9) \[\sum_{i=1}^{77} n_{ij} \cdot x_i \geq N_j\]

où : - \(n_{ij}\) = contenu en nutriment \(j\) de l’aliment \(i\) - \(N_j\) = apport minimal requis pour le nutriment \(j\)

Contraintes de non-négativité : \[x_i \geq 0 \quad \forall i\]

Le solveur trouvera les valeurs optimales des \(x_i\) qui minimisent le coût tout en respectant toutes les contraintes.

using System;
using System.Collections.Generic;
using Google.OrTools.LinearSolver;
Console.WriteLine("Modele de programmation lineaire defini.");
Modele de programmation lineaire defini.

Définition des variables de décision

Nous créons maintenant une variable de décision pour chaque aliment. Chaque variable \(x_i\) représente la quantité à acheter de l’aliment \(i\) par jour.

Caractéristiques des variables

  • Borne inférieure : 0 (on ne peut pas acheter une quantité négative)
  • Borne supérieure : +∞ (pas de limite sur la quantité à acheter)
  • Type : continue (on peut acheter des fractions d’unités)

Le solveur ajustera ces variables pour trouver la combinaison optimale.

Définition des contraintes et de la fonction objectif

Cette étape cruciale consiste à traduire le problème en équations mathématiques.

Création des contraintes nutritionnelles

Pour chaque nutriment (9 au total), nous créons une contrainte qui garantit que l’apport total respecte le minimum requis.

Formule mathématique : Pour le nutriment \(j\) \[\sum_{i=1}^{77} n_{ij} \cdot x_i \geq N_j\]

où : - \(n_{ij}\) = coefficient : contenu en nutriment \(j\) de l’aliment \(i\) - \(x_i\) = variable : quantité de l’aliment \(i\) - \(N_j\) = borne inférieure : apport minimal requis pour le nutriment \(j\)

Exemple concret : Pour les calories (nutriment 1) \[44.7 \cdot x_{\text{wheat flour}} + 11.6 \cdot x_{\text{macaroni}} + ... + 6.4 \cdot x_{\text{strawberry}} \geq 3.0\]

Définition de la fonction objectif

La fonction objectif représente le coût total quotidien à minimiser :

\[\text{Minimiser : } \sum_{i=1}^{77} p_i \cdot x_i\]

Chaque aliment \(i\) contribue au coût total proportionnellement à : - Son prix unitaire \(p_i\) - La quantité achetée \(x_i\)

Conclusion et perspectives

Résumé des apprentissages

Ce notebook a démontré comment résoudre un problème classique d’optimisation linéaire avec Google OR-Tools. Les points clés à retenir :

  1. Modélisation mathématique : Un problème du monde réel (nutrition à coût minimal) a été formulé comme un problème de programmation linéaire avec :

    • Variables de décision (quantités d’aliments)
    • Fonction objectif (coût total à minimiser)
    • Contraintes linéaires (besoins nutritionnels minimaux)

  2. Résolution efficace : Le solveur GLOP a trouvé la solution optimale en moins d’une seconde, alors que Stigler a pris 120 jours en 1939.

  3. Interprétation des résultats : La solution mathématiquement optimale ne contient qu’une dizaine d’aliments économiques, démontrant que l’optimisation pure ne tient pas compte de la variété ou du plaisir alimentaire.

Limites du modèle

Ce modèle simple ne prend pas en compte :

  • Variété alimentaire : pas de contrainte sur la diversité
  • Préférences personnelles : goûts, allergies, restrictions culturelles
  • Contraintes pratiques : disponibilité saisonnière, stockage, préparation
  • Santé à long terme : effets d’un régime monotone, micronutriments non modélisés

Extensions possibles

Le modèle peut être enrichi avec :

Extension Description Impact
Contraintes de variété Limiter la quantité max par aliment Régime plus équilibré mais plus cher
Groupes alimentaires Forcer la présence de fruits, légumes, etc. Meilleure qualité nutritionnelle
Coûts actuels Mettre à jour avec des prix 2026 Solution réaliste pour aujourd’hui
Multi-objectif Minimiser coût ET maximiser variété Compromis coût/plaisir
Données nutritionnelles modernes Inclure vitamines D, E, K, oméga-3, fibres Nutrition plus complète

Applications modernes

La programmation linéaire résout de nombreux problèmes industriels :

  • Logistique : optimisation de tournées de livraison
  • Production : planification de chaînes de fabrication
  • Finance : optimisation de portefeuille (Markowitz)
  • Énergie : gestion de réseaux électriques
  • Ressources humaines : planification d’horaires

OR-Tools offre également d’autres solveurs pour : - Problèmes combinatoires (satisfaction de contraintes) - Problèmes d’affectation (flow networks) - Problèmes de tournées (vehicle routing) - Ordonnancement (job shop scheduling)

Références

  • Article original : Stigler, G.J. (1945). “The Cost of Subsistence”. Journal of Farm Economics, 27(2), 303-314.
  • Documentation OR-Tools : https://developers.google.com/optimization
  • GLOP : https://developers.google.com/optimization/lp/glop

Pour aller plus loin : Consultez les autres notebooks de ce repository pour découvrir Z3 (SMT solving), OR-Tools CP-SAT (contraintes), et Tweety (logique formelle).

Exemple guide : Optimisation de Portefeuille Simplifiee

Creez un solveur de programmation lineaire pour un probleme de portefeuille d’investissement.

Objectifs

Modeliser un probleme d’allocation d’actifs avec contraintes de risque et rendement.

Instructions

Questions d’analyse

  1. Quelle est l’allocation optimale ?
  2. Comment le risque affecte-t-il la solution ?
  3. Que se passe-t-il si on ajoute une contrainte “minimum 20% en obligations” ?

Extensions (bonus)

  • Ajoutez une contrainte de diversification minimum par categorie
  • Comparez avec le solveur SCIP (programmation lineaire mixte)
  • Visualisez la frontiere efficiente avec XPlot

Checklist de completion

// TODO: Définissez le problème de portefeuille
// - 4 actifs disponibles avec rendements attendus
// - Contrainte : budget total de 100 000€
// - Contrainte : risque maximum par catégorie
// - Objectif : maximiser le rendement

(String Name, double ExpectedReturn, double Risk, string Category)[] assets = new[] {
    ("Actions US", 8.5, 0.15, "Actions"),
    ("Actions EU", 7.2, 0.12, "Actions"),
    ("Obligations", 4.0, 0.05, "Obligations"),
    ("Immobilier", 6.0, 0.08, "Immobilier")
};

// TODO: Créez le solveur
// Solver solver = Solver.CreateSolver("GLOP");

// TODO: Créez les variables de décision (montant dans chaque actif)
// List<Variable> allocations = ...

// TODO: Définissez la contrainte de budget
// Constraint budgetConstraint = ...

// TODO: Définissez les contraintes de risque par catégorie
// Constraint riskConstraint = ...

// TODO: Définissez l'objectif (maximiser rendement)
// Objective objective = ...

// TODO: Résolvez et affichez la solution
// Solver.ResultStatus result = solver.Solve();
Console.WriteLine("Probleme de portefeuille defini.");
Probleme de portefeuille defini.

Résolution du problème et analyse des résultats

Nous lançons maintenant le solveur pour trouver la solution optimale. Le code effectue trois opérations :

  1. Résolution : appel à solver.Solve()
  2. Vérification : le statut de la solution (optimale, réalisable, ou impossible)
  3. Affichage : les quantités à acheter et les apports nutritionnels obtenus

Données concernant le problème

// Nutrient minimums.
(String Name, double Value)[] nutrients =
  new[] { ("Calories (kcal)", 3.0), ("Protéines (g)", 70.0),    ("Calcium (g)", 0.8),
            ("Fer (mg)", 12.0),         ("Vitamine A (kIU)", 5.0), ("Vitamine B1 (mg)", 1.8),
            ("Vitamine B2 (mg)", 2.7),  ("Niacine (mg)", 18.0),       ("Vitamine C (mg)", 75.0) };

(String Name, String Unit, double Price, double[] Nutrients)[] data = new[] {
    ("Wheat Flour (Enriched)", "10 lb.", 36, new double[] { 44.7, 1411, 2, 365, 0, 55.4, 33.3, 441, 0 }),
    ("Macaroni", "1 lb.", 14.1, new double[] { 11.6, 418, 0.7, 54, 0, 3.2, 1.9, 68, 0 }),
    ("Wheat Cereal (Enriched)", "28 oz.", 24.2, new double[] { 11.8, 377, 14.4, 175, 0, 14.4, 8.8, 114, 0 }),
    ("Corn Flakes", "8 oz.", 7.1, new double[] { 11.4, 252, 0.1, 56, 0, 13.5, 2.3, 68, 0 }),
    ("Corn Meal", "1 lb.", 4.6, new double[] { 36.0, 897, 1.7, 99, 30.9, 17.4, 7.9, 106, 0 }),
    ("Hominy Grits", "24 oz.", 8.5, new double[] { 28.6, 680, 0.8, 80, 0, 10.6, 1.6, 110, 0 }),
    ("Rice", "1 lb.", 7.5, new double[] { 21.2, 460, 0.6, 41, 0, 2, 4.8, 60, 0 }),
    ("Rolled Oats", "1 lb.", 7.1, new double[] { 25.3, 907, 5.1, 341, 0, 37.1, 8.9, 64, 0 }),
    ("White Bread (Enriched)", "1 lb.", 7.9, new double[] { 15.0, 488, 2.5, 115, 0, 13.8, 8.5, 126, 0 }),
    ("Whole Wheat Bread", "1 lb.", 9.1, new double[] { 12.2, 484, 2.7, 125, 0, 13.9, 6.4, 160, 0 }),
    ("Rye Bread", "1 lb.", 9.1, new double[] { 12.4, 439, 1.1, 82, 0, 9.9, 3, 66, 0 }),
    ("Pound Cake", "1 lb.", 24.8, new double[] { 8.0, 130, 0.4, 31, 18.9, 2.8, 3, 17, 0 }),
    ("Soda Crackers", "1 lb.", 15.1, new double[] { 12.5, 288, 0.5, 50, 0, 0, 0, 0, 0 }),
    ("Milk", "1 qt.", 11, new double[] { 6.1, 310, 10.5, 18, 16.8, 4, 16, 7, 177 }),
    ("Evaporated Milk (can)", "14.5 oz.", 6.7, new double[] { 8.4, 422, 15.1, 9, 26, 3, 23.5, 11, 60 }),
    ("Butter", "1 lb.", 30.8, new double[] { 10.8, 9, 0.2, 3, 44.2, 0, 0.2, 2, 0 }),
    ("Oleomargarine", "1 lb.", 16.1, new double[] { 20.6, 17, 0.6, 6, 55.8, 0.2, 0, 0, 0 }),
    ("Eggs", "1 doz.", 32.6, new double[] { 2.9, 238, 1.0, 52, 18.6, 2.8, 6.5, 1, 0 }),
    ("Cheese (Cheddar)", "1 lb.", 24.2, new double[] { 7.4, 448, 16.4, 19, 28.1, 0.8, 10.3, 4, 0 }),
    ("Cream", "1/2 pt.", 14.1, new double[] { 3.5, 49, 1.7, 3, 16.9, 0.6, 2.5, 0, 17 }),
    ("Peanut Butter", "1 lb.", 17.9, new double[] { 15.7, 661, 1.0, 48, 0, 9.6, 8.1, 471, 0 }),
    ("Mayonnaise", "1/2 pt.", 16.7, new double[] { 8.6, 18, 0.2, 8, 2.7, 0.4, 0.5, 0, 0 }),
    ("Crisco", "1 lb.", 20.3, new double[] { 20.1, 0, 0, 0, 0, 0, 0, 0, 0 }),
    ("Lard", "1 lb.", 9.8, new double[] { 41.7, 0, 0, 0, 0.2, 0, 0.5, 5, 0 }),
    ("Sirloin Steak", "1 lb.", 39.6, new double[] { 2.9, 166, 0.1, 34, 0.2, 2.1, 2.9, 69, 0 }),
    ("Round Steak", "1 lb.", 36.4, new double[] { 2.2, 214, 0.1, 32, 0.4, 2.5, 2.4, 87, 0 }),
    ("Rib Roast", "1 lb.", 29.2, new double[] { 3.4, 213, 0.1, 33, 0, 0, 2, 0, 0 }),
    ("Chuck Roast", "1 lb.", 22.6, new double[] { 3.6, 309, 0.2, 46, 0.4, 1, 4, 120, 0 }),
    ("Plate", "1 lb.", 14.6, new double[] { 8.5, 404, 0.2, 62, 0, 0.9, 0, 0, 0 }),
    ("Liver (Beef)", "1 lb.", 26.8, new double[] { 2.2, 333, 0.2, 139, 169.2, 6.4, 50.8, 316, 525 }),
    ("Leg of Lamb", "1 lb.", 27.6, new double[] { 3.1, 245, 0.1, 20, 0, 2.8, 3.9, 86, 0 }),
    ("Lamb Chops (Rib)", "1 lb.", 36.6, new double[] { 3.3, 140, 0.1, 15, 0, 1.7, 2.7, 54, 0 }),
    ("Pork Chops", "1 lb.", 30.7, new double[] { 3.5, 196, 0.2, 30, 0, 17.4, 2.7, 60, 0 }),
    ("Pork Loin Roast", "1 lb.", 24.2, new double[] { 4.4, 249, 0.3, 37, 0, 18.2, 3.6, 79, 0 }),
    ("Bacon", "1 lb.", 25.6, new double[] { 10.4, 152, 0.2, 23, 0, 1.8, 1.8, 71, 0 }),
    ("Ham, smoked", "1 lb.", 27.4, new double[] { 6.7, 212, 0.2, 31, 0, 9.9, 3.3, 50, 0 }),
    ("Salt Pork", "1 lb.", 16, new double[] { 18.8, 164, 0.1, 26, 0, 1.4, 1.8, 0, 0 }),
    ("Roasting Chicken", "1 lb.", 30.3, new double[] { 1.8, 184, 0.1, 30, 0.1, 0.9, 1.8, 68, 46 }),
    ("Veal Cutlets", "1 lb.", 42.3, new double[] { 1.7, 156, 0.1, 24, 0, 1.4, 2.4, 57, 0 }),
    ("Salmon, Pink (can)", "16 oz.", 13, new double[] { 5.8, 705, 6.8, 45, 3.5, 1, 4.9, 209, 0 }),
    ("Apples", "1 lb.", 4.4, new double[] { 5.8, 27, 0.5, 36, 7.3, 3.6, 2.7, 5, 544 }),
    ("Bananas", "1 lb.", 6.1, new double[] { 4.9, 60, 0.4, 30, 17.4, 2.5, 3.5, 28, 498 }),
    ("Lemons", "1 doz.", 26, new double[] { 1.0, 21, 0.5, 14, 0, 0.5, 0, 4, 952 }),
    ("Oranges", "1 doz.", 30.9, new double[] { 2.2, 40, 1.1, 18, 11.1, 3.6, 1.3, 10, 1998 }),
    ("Green Beans", "1 lb.", 7.1, new double[] { 2.4, 138, 3.7, 80, 69, 4.3, 5.8, 37, 862 }),
    ("Cabbage", "1 lb.", 3.7, new double[] { 2.6, 125, 4.0, 36, 7.2, 9, 4.5, 26, 5369 }),
    ("Carrots", "1 bunch", 4.7, new double[] { 2.7, 73, 2.8, 43, 188.5, 6.1, 4.3, 89, 608 }),
    ("Celery", "1 stalk", 7.3, new double[] { 0.9, 51, 3.0, 23, 0.9, 1.4, 1.4, 9, 313 }),
    ("Lettuce", "1 head", 8.2, new double[] { 0.4, 27, 1.1, 22, 112.4, 1.8, 3.4, 11, 449 }),
    ("Onions", "1 lb.", 3.6, new double[] { 5.8, 166, 3.8, 59, 16.6, 4.7, 5.9, 21, 1184 }),
    ("Potatoes", "15 lb.", 34, new double[] { 14.3, 336, 1.8, 118, 6.7, 29.4, 7.1, 198, 2522 }),
    ("Spinach", "1 lb.", 8.1, new double[] { 1.1, 106, 0, 138, 918.4, 5.7, 13.8, 33, 2755 }),
    ("Sweet Potatoes", "1 lb.", 5.1, new double[] { 9.6, 138, 2.7, 54, 290.7, 8.4, 5.4, 83, 1912 }),
    ("Peaches (can)", "No. 2 1/2", 16.8, new double[] { 3.7, 20, 0.4, 10, 21.5, 0.5, 1, 31, 196 }),
    ("Pears (can)", "No. 2 1/2", 20.4, new double[] { 3.0, 8, 0.3, 8, 0.8, 0.8, 0.8, 5, 81 }),
    ("Pineapple (can)", "No. 2 1/2", 21.3, new double[] { 2.4, 16, 0.4, 8, 2, 2.8, 0.8, 7, 399 }),
    ("Asparagus (can)", "No. 2", 27.7, new double[] { 0.4, 33, 0.3, 12, 16.3, 1.4, 2.1, 17, 272 }),
    ("Green Beans (can)", "No. 2", 10, new double[] { 1.0, 54, 2, 65, 53.9, 1.6, 4.3, 32, 431 }),
    ("Pork and Beans (can)", "16 oz.", 7.1, new double[] { 7.5, 364, 4, 134, 3.5, 8.3, 7.7, 56, 0 }),
    ("Corn (can)", "No. 2", 10.4, new double[] { 5.2, 136, 0.2, 16, 12, 1.6, 2.7, 42, 218 }),
    ("Peas (can)", "No. 2", 13.8, new double[] { 2.3, 136, 0.6, 45, 34.9, 4.9, 2.5, 37, 370 }),
    ("Tomatoes (can)", "No. 2", 8.6, new double[] { 1.3, 63, 0.7, 38, 53.2, 3.4, 2.5, 36, 1253 }),
    ("Tomato Soup (can)", "10 1/2 oz.", 7.6, new double[] { 1.6, 71, 0.6, 43, 57.9, 3.5, 2.4, 67, 862 }),
    ("Peaches, Dried", "1 lb.", 15.7, new double[] { 8.5, 87, 1.7, 173, 86.8, 1.2, 4.3, 55, 57 }),
    ("Prunes, Dried", "1 lb.", 9, new double[] { 12.8, 99, 2.5, 154, 85.7, 3.9, 4.3, 65, 257 }),
    ("Raisins, Dried", "15 oz.", 9.4, new double[] { 13.5, 104, 2.5, 136, 4.5, 6.3, 1.4, 24, 136 }),
    ("Peas, Dried", "1 lb.", 7.9, new double[] { 20.0, 1367, 4.2, 345, 2.9, 28.7, 18.4, 162, 0 }),
    ("Lima Beans, Dried", "1 lb.", 8.9, new double[] { 17.4, 1055, 3.7, 459, 5.1, 26.9, 38.2, 93, 0 }),
    ("Navy Beans, Dried", "1 lb.", 5.9, new double[] { 26.9, 1691, 11.4, 792, 0, 38.4, 24.6, 217, 0 }),
    ("Coffee", "1 lb.", 22.4, new double[] { 0, 0, 0, 0, 0, 4, 5.1, 50, 0 }),
    ("Tea", "1/4 lb.", 17.4, new double[] { 0, 0, 0, 0, 0, 0, 2.3, 42, 0 }),
    ("Cocoa", "8 oz.", 8.6, new double[] { 8.7, 237, 3, 72, 0, 2, 11.9, 40, 0 }),
    ("Chocolate", "8 oz.", 16.2, new double[] { 8.0, 77, 1.3, 39, 0, 0.9, 3.4, 14, 0 }),
    ("Sugar", "10 lb.", 51.7, new double[] { 34.9, 0, 0, 0, 0, 0, 0, 0, 0 }),
    ("Corn Syrup", "24 oz.", 13.7, new double[] { 14.7, 0, 0.5, 74, 0, 0, 0, 5, 0 }),
    ("Molasses", "18 oz.", 13.6, new double[] { 9.0, 0, 10.3, 244, 0, 1.9, 7.5, 146, 0 }),
    ("Strawberry Preserves", "1 lb.", 20.5, new double[] { 6.4, 11, 0.4, 7, 0.2, 0.2, 0.4, 3, 0 })
};
Console.WriteLine("Donnees nutrition Stiegler chargees.");
Donnees nutrition Stiegler chargees.

Déclarer le résolveur LP

// Créer le solveur linéaire avec le backend GLOP.
Solver solver = Solver.CreateSolver("GLOP");
if (solver is null)
{
    return;
}
<null>

Créer les variables

// Créer les variables 

List<Variable> foods = new List<Variable>();
for (int i = 0; i < data.Length; ++i)
{
    foods.Add(solver.MakeNumVar(0.0, double.PositiveInfinity, data[i].Name));
}
Console.WriteLine($"Nombre de variables = {solver.NumVariables()}");
Nombre de variables = 77

Interprétation du nombre de variables

Résultat : Le solveur a créé 77 variables, une pour chaque aliment disponible.

Dimension Valeur Signification
Variables 77 Nombre d’aliments dans la base de données
Type Continue Les quantités peuvent être fractionnaires
Bornes [0, +∞) Quantités non-négatives sans limite supérieure

Chaque variable représente une décision d’achat : quelle quantité acheter de cet aliment pour minimiser le coût tout en respectant les besoins nutritionnels.

Exemple : Si la solution optimale contient x_1 = 0.5, cela signifie acheter 0.5 unité de “Wheat Flour (Enriched)” par jour (soit 5 lb par jour puisque l’unité est “10 lb.”).

Définir les contraintes & Créer l’objectif

// définir les contraintes
List<Constraint> constraints = new List<Constraint>();
for (int i = 0; i < nutrients.Length; ++i)
{
    Constraint constraint =
        solver.MakeConstraint(nutrients[i].Value, double.PositiveInfinity, nutrients[i].Name);
    for (int j = 0; j < data.Length; ++j)
    {
        constraint.SetCoefficient(foods[j], data[j].Nutrients[i]);
    }
    constraints.Add(constraint);
}
Console.WriteLine($"Nombre de contraintes = {solver.NumConstraints()}");


// déclaration des objectifs 
Objective objective = solver.Objective();
for (int i = 0; i < data.Length; ++i)
{
    objective.SetCoefficient(foods[i], 1);
}
objective.SetMinimization();
Nombre de contraintes = 9

Interprétation de la structure du problème

Résultat : Le solveur a configuré 9 contraintes, une pour chaque nutriment.

Dimension Valeur Signification
Contraintes 9 Nombre de nutriments à respecter
Variables 77 Nombre d’aliments disponibles
Coefficients 9 × 77 = 693 Chaque contrainte implique tous les aliments

Taille du problème

Ce problème est de taille moyenne pour un solveur de programmation linéaire moderne :

  • Variables : 77 (les solveurs modernes gèrent facilement des millions de variables)
  • Contraintes : 9 (très peu, typiquement des milliers dans les problèmes industriels)
  • Matrice des contraintes : 9 × 77 = 693 coefficients (matrice creuse dans des cas réels)

Performance attendue : Un problème de cette taille se résout en quelques millisecondes avec GLOP. La solution de Stigler a pris 120 jours de calculs manuels en 1939 !

Appeler le résolveur & Afficher la solution

Solver.ResultStatus resultStatus = solver.Solve();

// Vérifie que le problème possède une solution optimale.
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
    Console.WriteLine("Le problème n'a pas de solution optimale !");
    if (resultStatus == Solver.ResultStatus.FEASIBLE)
    {
        Console.WriteLine("Une solution potentiellement sous-optimale a été trouvée.");
    }
    else
    {
        Console.WriteLine("Le solveur n'a pas pu résoudre le problème.");
        return;
    }
}

// Affiche les montants (en dollars) à acheter de chaque aliment.
double[] nutrientsResult = new double[nutrients.Length];
Console.WriteLine("\nAliments annuels:");
for (int i = 0; i < foods.Count; ++i)
{
    if (foods[i].SolutionValue() > 0.0)
    {
        Console.WriteLine($"{data[i].Name}: ${365 * foods[i].SolutionValue():N2}");
        for (int j = 0; j < nutrients.Length; ++j)
        {
            nutrientsResult[j] += data[i].Nutrients[j] * foods[i].SolutionValue();
        }
    }
}
Console.WriteLine($"\nPrix annuel optimal : ${365 * objective.Value():N2}");

Console.WriteLine("\nNutriments par jour :");
for (int i = 0; i < nutrients.Length; ++i)
{
    Console.WriteLine($"{nutrients[i].Name}: {nutrientsResult[i]:N2} (min {nutrients[i].Value})");
}

Aliments annuels:
Wheat Flour (Enriched): $10,77
Liver (Beef): $0,69
Cabbage: $4,09
Spinach: $1,83
Navy Beans, Dried: $22,28

Prix annuel optimal : $39,66

Nutriments par jour :
Calories (kcal): 3,00 (min 3)
Protéines (g): 147,41 (min 70)
Calcium (g): 0,80 (min 0,8)
Fer (mg): 60,47 (min 12)
Vitamine A (kIU): 5,00 (min 5)
Vitamine B1 (mg): 4,12 (min 1,8)
Vitamine B2 (mg): 2,70 (min 2,7)
Niacine (mg): 27,32 (min 18)
Vitamine C (mg): 75,00 (min 75)

Exercice 3 : Analyse de sensibilite du regime optimal

La solution optimale indique 5 aliments pour un cout de 39,66 $/an. Mais que se passe-t-il si un de ces aliments n’est plus disponible ?

Objectif : Supprimez successivement chacun des 5 aliments de la solution optimale (Wheat Flour, Liver, Cabbage, Spinach, Navy Beans) et re-solvez le probleme. Identifiez quel aliment, une fois retire, provoque la plus forte hausse du cout annuel.

Indices : - Pour “supprimer” un aliment, fixez sa borne superieure a 0 : solver.MakeNumVar(0.0, 0.0, data[i].Name) - Utilisez une boucle sur les 5 aliments de la solution optimale - Stockez le cout optimal de chaque sous-probleme dans un dictionnaire - L’aliment avec le plus fort impact est le plus “critique” du regime optimal

// Exercice 3 : Analyse de sensibilite du regime optimal
// TODO etudiant : supprimez chaque aliment de la solution et re-solvez
// Etape 1 : identifiez les 5 aliments avec SolutionValue() > 0 dans la solution initiale
// Etape 2 : pour chaque aliment, reconstruisez le LP en fixant sa borne sup a 0
// Etape 3 : resolvez et enregistrez le cout optimal dans un dictionnaire
// Etape 4 : affichez les couts tries par impact decroissant
// Indice : bouclez sur les indices des aliments non-nuls de la premiere solution

// var criticalFoods = new List<(string Name, double Cost)>();
// foreach (var removedFood in optimalFoods) {
//     var solver_sens = Solver.CreateSolver("GLOP");
//     // ... reconstruction du LP avec l'aliment exclu
//     // criticalFoods.Add((removedFood, 365 * solver_sens.Objective().Value()));
// }
// foreach (var cf in criticalFoods.OrderByDescending(c => c.Cost))
//     Console.WriteLine($"{cf.Name}: ${cf.Cost:F2}/an");

Console.WriteLine("Exercice a completer : analyse de sensibilite du regime de Stigler");
Exercice a completer : analyse de sensibilite du regime de Stigler

Exercice : etendre le modele du regime de Stigler

Le modele resolu ci-dessus minimise le cout annuel sans plafonner la quantite d’un aliment. En pratique, on ne peut pas raisonnablement consommer une quantite illimitee d’un seul produit.

Objectif : ajoutez une borne superieure sur chaque variable d’aliment (par exemple 20 unites maximum), puis re-resolvez le probleme et comparez le cout optimal obtenu avec celui du modele initial.

Completez la cellule ci-dessous : decommentez les etapes suggerees et implementez-les.

// Exercice : limiter la quantite de chaque aliment et re-resoudre
// Etapes suggerees (decommentez et completez) :
//   // 1. Reconstruire un solveur et des variables avec une borne superieure (ex: 20)
//   var solver2 = Solver.CreateSolver("GLOP");
//   var foods2 = new List<Variable>();
//   for (int i = 0; i < data.Length; ++i)
//       foods2.Add(solver2.MakeNumVar(0.0, 20.0, data[i].Name)); // borne sup = 20
//   // 2. Re-creer les contraintes nutritionnelles (cf cellule precedente)
//   // 3. Re-definir l'objectif (minimiser le cout) puis appeler solver2.Solve()
//   // 4. Comparer solver2.Objective().Value() au cout du modele initial

Console.WriteLine("Exercice a completer");
Exercice a completer

Exercice : Analyse des prix fictifs (shadow prices) des contraintes nutritionnelles

Le solveur GLOP fournit les valeurs duales (shadow prices) de chaque contrainte. Un shadow price indique de combien la fonction objectif augmenterait si le seuil minimum du nutriment etait augmente d’une unite.

Objectif : Pour chaque nutriment, extraire le shadow price de la contrainte associee, puis identifier les nutriments “critiques” (ceux dont le relachement reduirait le plus le cout).

Etapes : 1. Accedez aux contraintes du solveur via constraints[i].DualValue() 2. Stockez les valeurs duales dans un dictionnaire associe a chaque nutriment 3. Triez par impact decroissant et affichez le classement 4. Identifiez les nutriments actifs (dual > 0) vs inactifs (dual = 0)

Indices : - La dual value d’une contrainte >= indique le cout marginal d’une unite supplementaire de ce nutriment - Un nutriment avec dual = 0 n’est pas contraignant (l’apport depasse deja le minimum) - Les nutriments actifs sont ceux pour lesquels la contrainte est “saturee” (apport = minimum) - Utilisez constraints[i].DualValue() pour obtenir la valeur duale du solveur GLOP

// Exercice : Analyse des prix fictifs (shadow prices)
// TODO etudiant : extraire et analyser les valeurs duales des contraintes

// Etape 1 : Extraire les shadow prices de chaque contrainte nutritionnelle
// Indice : var shadowPrices = new List<(string Name, double Dual)>();
// Indice : for (int i = 0; i < constraints.Count; ++i)
//              shadowPrices.Add((nutrients[i].Name, constraints[i].DualValue()));
var shadowPrices = new List<(string Name, double Dual)>();

// Etape 2 : Trier par impact decroissant
// Indice : foreach (var sp in shadowPrices.OrderByDescending(s => s.Dual))

// Etape 3 : Separer nutriments actifs (dual > 0) et inactifs (dual = 0)
// Indice : Les nutriments actifs sont ceux ou la contrainte est saturee
// Indice :Comparer avec les resultats "Nutriments par jour" de la cellule precedente

// Etape 4 : Afficher le classement
// Indice : Console.WriteLine($"  {sp.Name,25}: dual = {sp.Dual:F4}");

Console.WriteLine("Exercice a completer : analyse des shadow prices");
Exercice a completer : analyse des shadow prices

Conclusion

Ce notebook a illustre la resolution d’un probleme classique de programmation lineaire avec Google OR-Tools et le solveur GLOP. Vous avez appris a formuler un probleme d’optimisation reel (le regime de Stigler) en variables de decision, contraintes lineaires et fonction objectif, puis a interpreter la solution optimale obtenue en quelques millisecondes.

Les points cles a retenir sont la traduction d’un probleme metier en modele mathematique (77 variables, 9 contraintes), la difference entre solution optimale mathematiquement et solution praticable (absence de variante alimentaire), et les extensions possibles vers des modeles multi-objectifs ou avec contraintes de diversite. Ces competences sont transposables a de nombreux domaines industriels : logistique, finance, planification energetique et ordonnancement.

Retour au sommet