# Cheatsheet Programmation Linéaire - Guide Ultra-Détaillé pour Grands Débutants


[OK] CONCEPTS FONDAMENTAUX (EXPLICATIONS TRÈS DÉTAILLÉES)

# === QU'EST-CE QUE LA PROGRAMMATION LINÉAIRE ? ===

# Imagine que tu gères une petite entreprise de fabrication de meubles
# Tu fabriques des chaises et des tables
# Chaque chaise te rapporte 50€ de bénéfice
# Chaque table te rapporte 80€ de bénéfice

# MAIS tu as des contraintes:
# - Tu n'as que 100 heures de travail par semaine
# - Une chaise prend 2 heures à fabriquer
# - Une table prend 4 heures à fabriquer
# - Tu n'as que 200 kg de bois par semaine
# - Une chaise utilise 3 kg de bois
# - Une table utilise 5 kg de bois

# QUESTION: Combien de chaises et de tables dois-tu fabriquer pour MAXIMISER ton bénéfice?

# C'EST ÇA LA PROGRAMMATION LINÉAIRE!
# = Trouver la meilleure solution (optimum) en respectant des contraintes

# La programmation linéaire (PL) ou Linear Programming (LP) en anglais
# = Méthode mathématique pour résoudre des problèmes d'optimisation
# = "Linéaire" car les relations sont des lignes droites (pas de x², x³, etc.)
# = "Programmation" vient de "planification" (pas de code informatique!)


# === VOCABULAIRE FONDAMENTAL (TRÈS IMPORTANT!) ===

# VARIABLE DE DÉCISION (Decision Variable)
# = Ce que tu dois décider, ce que tu cherches
# Exemple: Nombre de chaises à fabriquer (x), nombre de tables (y)
# = Les INCONNUES de ton problème
# Notation mathématique: x₁, x₂, x₃... ou x, y, z

# FONCTION OBJECTIF (Objective Function)
# = Ce que tu veux MAXIMISER ou MINIMISER
# Exemple: Profit total = 50x + 80y (x chaises, y tables)
# = C'est ton BUT, ce que tu optimises
# Types:
#   - Maximisation: profit, production, efficacité
#   - Minimisation: coût, temps, déchets

# CONTRAINTES (Constraints)
# = Les LIMITES que tu dois respecter
# Exemple: 
#   - Temps: 2x + 4y ≤ 100 (heures disponibles)
#   - Bois: 3x + 5y ≤ 200 (kg disponibles)
#   - Non-négativité: x ≥ 0, y ≥ 0 (pas de production négative!)
# = Ce qui t'empêche de produire à l'infini

# SOLUTION RÉALISABLE (Feasible Solution)
# = Une solution qui respecte TOUTES les contraintes
# Exemple: x=10 chaises, y=15 tables
#   - Vérifie temps: 2(10) + 4(15) = 80 ≤ 100 [OK]
#   - Vérifie bois: 3(10) + 5(15) = 105 ≤ 200 [OK]
#   - x≥0, y≥0 [OK]
# = C'est "possible" mais pas forcément optimal

# SOLUTION OPTIMALE (Optimal Solution)
# = La MEILLEURE solution réalisable
# = Celle qui maximise ou minimise la fonction objectif
# Exemple: x=20, y=15 -> Profit = 50(20) + 80(15) = 2200€
# = C'est le MAXIMUM qu'on peut atteindre

# RÉGION RÉALISABLE (Feasible Region)
# = Ensemble de TOUTES les solutions réalisables
# = Zone graphique où toutes les contraintes sont respectées
# = En 2D, c'est souvent un polygone
# = La solution optimale est TOUJOURS sur un sommet de ce polygone!


# === POURQUOI UTILISER LA PROGRAMMATION LINÉAIRE? ===

# Cas d'usage réels:

# 1. INDUSTRIE/PRODUCTION
# - Optimiser la production dans une usine
# - Minimiser les coûts de fabrication
# - Maximiser l'utilisation des machines
# - Planifier les stocks
# Exemple: Airbus utilise la PL pour optimiser la production d'avions

# 2. LOGISTIQUE/TRANSPORT
# - Optimiser les routes de livraison
# - Minimiser les coûts de transport
# - Planifier les horaires de camions
# Exemple: Amazon utilise la PL pour optimiser ses livraisons

# 3. FINANCE/INVESTISSEMENT
# - Optimiser un portefeuille d'investissements
# - Minimiser le risque
# - Maximiser le rendement
# Exemple: Banques utilisent la PL pour gérer les portefeuilles

# 4. AGRICULTURE
# - Optimiser la culture de différentes plantes
# - Minimiser l'utilisation d'engrais
# - Maximiser le rendement
# Exemple: Exploitations agricoles planifient les semis

# 5. ÉNERGIE
# - Optimiser la distribution d'électricité
# - Minimiser les pertes
# - Planifier la production
# Exemple: EDF utilise la PL pour la gestion du réseau

# 6. SANTÉ
# - Optimiser les plannings d'infirmières
# - Minimiser les temps d'attente
# - Maximiser l'utilisation des ressources
# Exemple: Hôpitaux planifient les opérations chirurgicales

# 7. TÉLÉCOMMUNICATIONS
# - Optimiser le routage des données
# - Minimiser la latence
# - Maximiser la bande passante
# Exemple: Opérateurs télécom optimisent les réseaux


# === QUAND UTILISER LA PROGRAMMATION LINÉAIRE? ===

# [OK] Utilise la PL quand:
# 1. Tu as un OBJECTIF clair à maximiser/minimiser
#    - Exemple: maximiser profit, minimiser coût
# 2. Tu as des CONTRAINTES linéaires
#    - Exemple: ressources limitées, temps limité
# 3. Les RELATIONS sont linéaires
#    - Pas de x², xy, sin(x), etc.
#    - Seulement addition, soustraction, multiplication par constante
# 4. Les VARIABLES sont continues (ou peuvent être traitées ainsi)
#    - Exemple: litres de carburant, heures de travail
#    - Note: Pour variables entières, voir Programmation Linéaire en Nombres Entiers (PLNE)

# [X] N'utilise PAS la PL quand:
# 1. Les relations sont NON-LINÉAIRES
#    - Exemple: coût = 10x² (quadratique)
#    - Solution: Programmation non-linéaire
# 2. Les variables doivent être ENTIÈRES et tu as beaucoup de variables
#    - Exemple: nombre d'employés (pas 2.5 employés!)
#    - Solution: Programmation linéaire en nombres entiers (PLNE/MILP)
# 3. Le problème a de l'INCERTITUDE
#    - Exemple: demande future inconnue
#    - Solution: Programmation stochastique
# 4. Les contraintes/objectifs sont FLOUS
#    - Exemple: "coût pas trop élevé"
#    - Solution: Programmation floue


# === COMMENT ÇA MARCHE? (INTUITION SIMPLE) ===

# Exemple concret: Le problème des meubles

# 1. DÉFINIR LES VARIABLES
# x = nombre de chaises à fabriquer
# y = nombre de tables à fabriquer

# 2. DÉFINIR LA FONCTION OBJECTIF
# Maximiser: Profit = 50x + 80y

# 3. DÉFINIR LES CONTRAINTES
# Temps disponible: 2x + 4y ≤ 100
# Bois disponible: 3x + 5y ≤ 200
# Non-négativité: x ≥ 0, y ≥ 0

# 4. RÉSOUDRE
# Python va tester intelligemment différentes combinaisons
# et trouver celle qui maximise le profit

# 5. INTERPRÉTER
# Résultat: x=20 chaises, y=15 tables
# Profit maximal: 50(20) + 80(15) = 2200€

# Pourquoi cette solution?
# - Si on fait plus de chaises: pas assez de temps
# - Si on fait plus de tables: pas assez de bois
# - C'est l'ÉQUILIBRE optimal!


# === FORME STANDARD D'UN PROBLÈME DE PL ===

# Maximiser (ou Minimiser):
#   Z = c₁x₁ + c₂x₂ + ... + cₙxₙ

# Sujet à:
#   a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁
#   a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂
#   ...
#   x₁, x₂, ..., xₙ ≥ 0

# Explication des symboles:
# Z = valeur de la fonction objectif
# xᵢ = variables de décision
# cᵢ = coefficients de la fonction objectif (profits/coûts)
# aᵢⱼ = coefficients des contraintes (consommation de ressources)
# bᵢ = limites des contraintes (ressources disponibles)


[OK] INSTALLATION SUPER DÉTAILLÉE

# === BIBLIOTHÈQUES PYTHON POUR LA PL ===

# Il existe plusieurs bibliothèques en Python:

# 1. PULP (Recommandé pour débuter!)
# - Simple et intuitif
# - Syntaxe proche du langage naturel
# - Gratuit et open-source
# - Utilise des solveurs externes (CBC, GLPK, etc.)

# 2. SCIPY.OPTIMIZE.LINPROG (Inclus dans SciPy)
# - Déjà installé si tu as SciPy
# - Bon pour petits problèmes
# - Syntaxe plus mathématique

# 3. CVXPY (Pour problèmes convexes)
# - Puissant mais plus complexe
# - Pour problèmes avancés

# 4. PYOMO (Pour modélisation avancée)
# - Très flexible
# - Pour grands problèmes industriels

# 5. GOOGLE OR-TOOLS (Puissant)
# - Développé par Google
# - Très rapide
# - Pour problèmes complexes

# On va se concentrer sur PULP car c'est le plus simple pour débuter!


# === INSTALLER PULP ===

# === ÉTAPE 1: Vérifier Python ===

# Ouvre un terminal/invite de commandes

# Vérifie que Python est installé:
python --version
# ou
python3 --version

# Doit afficher: Python 3.8.X ou plus récent
# Si pas installé: télécharge sur https://www.python.org/


# === ÉTAPE 2: Créer un environnement virtuel (RECOMMANDÉ) ===

# Pourquoi? Pour isoler les packages du projet

# Linux/macOS:
python3 -m venv venv_pl
source venv_pl/bin/activate

# Windows:
python -m venv venv_pl
venv_pl\Scripts\activate

# Le terminal affiche maintenant: (venv_pl)


# === ÉTAPE 3: Installer PuLP ===

# Avec l'environnement virtuel activé:

pip install pulp

# Affiche:
# Collecting pulp
# Downloading PuLP-X.X.X-py3-none-any.whl
# Installing collected packages: pulp
# Successfully installed pulp-X.X.X

# Vérifier l'installation:
python -c "import pulp; print(pulp.__version__)"
# Affiche: 2.7.0 (ou version récente)


# === ÉTAPE 4: Installer les autres bibliothèques (optionnel) ===

# Pour utiliser scipy.optimize.linprog:
pip install scipy

# Pour utiliser cvxpy:
pip install cvxpy

# Pour utiliser Google OR-Tools:
pip install ortools

# Pour tout installer d'un coup:
pip install pulp scipy cvxpy ortools


# === ÉTAPE 5: Vérifier les solveurs ===

# PuLP utilise des "solveurs" pour résoudre les problèmes
# Par défaut, PuLP installe CBC (solveur gratuit)

# Vérifier les solveurs disponibles:
python -c "import pulp; print(pulp.listSolvers(onlyAvailable=True))"

# Affiche: ['PULP_CBC_CMD', 'COIN_CMD']
# CBC = solveur par défaut (gratuit, performant)


[OK] PREMIER EXEMPLE: LE PROBLÈME DES MEUBLES (SUPER DÉTAILLÉ)

# === ÉNONCÉ DU PROBLÈME ===

# Tu fabriques des chaises et des tables
# Objectif: MAXIMISER le profit

# DONNÉES:
# - Chaise: 50€ de profit, 2h de travail, 3kg de bois
# - Table: 80€ de profit, 4h de travail, 5kg de bois
# - Disponible: 100h de travail par semaine, 200kg de bois

# QUESTION: Combien de chaises (x) et tables (y) fabriquer?


# === ÉTAPE 1: IMPORTER PULP ===

# Crée un fichier "meubles.py"

from pulp import *

# Explications:
# pulp = bibliothèque de programmation linéaire
# * = importe tout (LpProblem, LpVariable, LpMaximize, etc.)


# === ÉTAPE 2: CRÉER LE PROBLÈME ===

# Définir le problème avec un nom et un sens (maximiser/minimiser)

prob = LpProblem("Problème_Meubles", LpMaximize)

# Explications:
# LpProblem = classe pour créer un problème de PL
# "Problème_Meubles" = nom du problème (peut être n'importe quoi)
# LpMaximize = on veut maximiser (autres options: LpMinimize)
# prob = objet qui contient tout le problème


# === ÉTAPE 3: DÉFINIR LES VARIABLES DE DÉCISION ===

# Ce qu'on cherche: nombre de chaises (x) et tables (y)

x = LpVariable("Chaises", lowBound=0, cat='Continuous')
y = LpVariable("Tables", lowBound=0, cat='Continuous')

# Explications détaillées:

# LpVariable = classe pour créer une variable de décision
# "Chaises" = nom de la variable (affiché dans les résultats)
# lowBound=0 = limite inférieure (minimum)
#   - On ne peut pas fabriquer -5 chaises!
#   - Par défaut, lowBound=None (pas de limite)
# cat='Continuous' = type de variable
#   - 'Continuous': nombres décimaux (1.5, 2.7, etc.)
#   - 'Integer': nombres entiers seulement (1, 2, 3...)
#   - 'Binary': 0 ou 1 seulement

# Pourquoi Continuous ici?
# On peut considérer qu'on peut fabriquer 10.5 chaises
# (commencer une chaise qu'on finira la semaine prochaine)

# Si tu veux des nombres entiers:
# x = LpVariable("Chaises", lowBound=0, cat='Integer')

# upBound = limite supérieure (optionnel)
# Exemple: maximum 50 chaises
# x = LpVariable("Chaises", lowBound=0, upBound=50, cat='Integer')


# === ÉTAPE 4: DÉFINIR LA FONCTION OBJECTIF ===

# Ce qu'on veut maximiser: Profit = 50x + 80y

prob += 50*x + 80*y, "Profit_Total"

# Explications:

# prob += ... = ajoute la fonction objectif au problème
# 50*x = profit par chaise (50€) × nombre de chaises
# 80*y = profit par table (80€) × nombre de tables
# 50*x + 80*y = profit total
# "Profit_Total" = nom descriptif (optionnel mais recommandé)

# Syntaxe alternative (équivalente):
# prob.setObjective(50*x + 80*y)


# === ÉTAPE 5: DÉFINIR LES CONTRAINTES ===

# Contrainte 1: Temps de travail limité
# 2h par chaise + 4h par table ≤ 100h disponibles

prob += 2*x + 4*y <= 100, "Contrainte_Temps"

# Explications:
# 2*x = heures pour fabriquer x chaises
# 4*y = heures pour fabriquer y tables
# 2*x + 4*y = heures totales utilisées
# <= 100 = ne peut pas dépasser 100 heures
# "Contrainte_Temps" = nom descriptif

# Contrainte 2: Bois disponible limité
# 3kg par chaise + 5kg par table ≤ 200kg disponibles

prob += 3*x + 5*y <= 200, "Contrainte_Bois"

# Explications:
# 3*x = kg de bois pour x chaises
# 5*y = kg de bois pour y tables
# 3*x + 5*y = kg de bois total utilisé
# <= 200 = ne peut pas dépasser 200 kg

# Note sur les opérateurs:
# <= : inférieur ou égal (≤)
# >= : supérieur ou égal (≥)
# == : égal (=)

# Exemple de contrainte d'égalité:
# prob += x + y == 50, "Exactement_50_meubles"

# Les contraintes de non-négativité (x≥0, y≥0) sont déjà
# définies avec lowBound=0 dans LpVariable


# === ÉTAPE 6: RÉSOUDRE LE PROBLÈME ===

# Lancer le solveur pour trouver la solution optimale

prob.solve()

# Explications:
# .solve() = méthode qui résout le problème
# Utilise le solveur CBC par défaut
# Retourne un code de statut:
#   - 1 = solution optimale trouvée
#   - 0 = problème non résolu
#   - -1 = infaisable (aucune solution possible)
#   - -2 = non borné (solution infinie)

# Pour utiliser un solveur spécifique:
# prob.solve(PULP_CBC_CMD(msg=0))
# msg=0 = désactive les messages de débogage


# === ÉTAPE 7: AFFICHER LE STATUT ===

# Vérifier si une solution a été trouvée

print("Statut:", LpStatus[prob.status])

# Explications:
# prob.status = code numérique du statut
# LpStatus = dictionnaire qui traduit le code en texte
# Affiche: "Statut: Optimal" si tout va bien

# Autres statuts possibles:
# - "Not Solved": pas encore résolu
# - "Infeasible": aucune solution possible
# - "Unbounded": solution infinie
# - "Undefined": erreur


# === ÉTAPE 8: AFFICHER LES RÉSULTATS ===

# Afficher la solution optimale et le profit

print(f"Nombre de chaises à fabriquer: {x.varValue}")
print(f"Nombre de tables à fabriquer: {y.varValue}")
print(f"Profit total maximum: {value(prob.objective)}€")

# Explications:

# x.varValue = valeur optimale de la variable x
# y.varValue = valeur optimale de la variable y
# value(prob.objective) = valeur de la fonction objectif
# f"..." = f-string pour formater la sortie

# Exemple de sortie:
# Nombre de chaises à fabriquer: 20.0
# Nombre de tables à fabriquer: 15.0
# Profit total maximum: 2200.0€


# === ÉTAPE 9: AFFICHER LES RESSOURCES UTILISÉES (OPTIONNEL) ===

# Vérifier combien de ressources ont été utilisées

temps_utilise = 2*x.varValue + 4*y.varValue
bois_utilise = 3*x.varValue + 5*y.varValue

print(f"\nRessources utilisées:")
print(f"Temps: {temps_utilise}/{100}h")
print(f"Bois: {bois_utilise}/{200}kg")

# Affiche:
# Ressources utilisées:
# Temps: 100.0/100h
# Bois: 135.0/200kg

# Interprétation:
# - Tout le temps est utilisé (contrainte saturée/active)
# - Il reste 65kg de bois (contrainte non saturée)
# - La contrainte temps est le "goulot d'étranglement"


# === CODE COMPLET ===

"""
meubles.py - Problème de fabrication de meubles
"""

from pulp import *

# 1. Créer le problème
prob = LpProblem("Problème_Meubles", LpMaximize)

# 2. Définir les variables
x = LpVariable("Chaises", lowBound=0, cat='Continuous')
y = LpVariable("Tables", lowBound=0, cat='Continuous')

# 3. Définir la fonction objectif
prob += 50*x + 80*y, "Profit_Total"

# 4. Définir les contraintes
prob += 2*x + 4*y <= 100, "Contrainte_Temps"
prob += 3*x + 5*y <= 200, "Contrainte_Bois"

# 5. Résoudre
prob.solve()

# 6. Afficher les résultats
print("Statut:", LpStatus[prob.status])
print(f"\nSolution optimale:")
print(f"Chaises: {x.varValue}")
print(f"Tables: {y.varValue}")
print(f"Profit: {value(prob.objective)}€")

# 7. Afficher les ressources
temps_utilise = 2*x.varValue + 4*y.varValue
bois_utilise = 3*x.varValue + 5*y.varValue
print(f"\nRessources:")
print(f"Temps: {temps_utilise}/100h")
print(f"Bois: {bois_utilise}/200kg")


# === EXÉCUTER LE PROGRAMME ===

# Dans le terminal (avec venv activé):
python meubles.py

# Sortie attendue:
"""
Welcome to the CBC MILP Solver 
...
Statut: Optimal

Solution optimale:
Chaises: 20.0
Tables: 15.0
Profit: 2200.0€

Ressources:
Temps: 100.0/100h
Bois: 135.0/200kg
"""


[OK] COMPRENDRE LA SOLUTION (ANALYSE DÉTAILLÉE)

# === POURQUOI x=20 et y=15? ===

# Testons d'autres solutions pour comprendre:

# Solution 1: x=0, y=0 (rien produire)
# Profit = 50(0) + 80(0) = 0€
# Temps = 2(0) + 4(0) = 0h ≤ 100 [OK]
# Bois = 3(0) + 5(0) = 0kg ≤ 200 [OK]
# -> Réalisable mais profit nul!

# Solution 2: x=50, y=0 (que des chaises)
# Profit = 50(50) + 80(0) = 2500€
# Temps = 2(50) + 4(0) = 100h ≤ 100 [OK]
# Bois = 3(50) + 5(0) = 150kg ≤ 200 [OK]
# -> Réalisable et bon profit!

# Solution 3: x=0, y=25 (que des tables)
# Profit = 50(0) + 80(25) = 2000€
# Temps = 2(0) + 4(25) = 100h ≤ 100 [OK]
# Bois = 3(0) + 5(25) = 125kg ≤ 200 [OK]
# -> Réalisable mais moins bon que Solution 2

# Solution 4: x=20, y=15 (solution optimale)
# Profit = 50(20) + 80(15) = 2200€
# Temps = 2(20) + 4(15) = 100h ≤ 100 [OK]
# Bois = 3(20) + 5(15) = 135kg ≤ 200 [OK]
# -> Réalisable et profit maximal!

# Solution 5: x=30, y=20 (trop gourmand)
# Profit = 50(30) + 80(20) = 3100€
# Temps = 2(30) + 4(20) = 140h > 100 [X]
# Bois = 3(30) + 5(20) = 190kg ≤ 200 [OK]
# -> NON réalisable! Pas assez de temps!

# CONCLUSION:
# La solution optimale (x=20, y=15) est un COMPROMIS
# - On ne fait pas que des tables (pourtant plus rentables)
# - On ne fait pas que des chaises
# - On équilibre pour utiliser au mieux le temps disponible
# - Il nous reste du bois (contrainte non saturée)


# === CONTRAINTE ACTIVE vs NON ACTIVE ===

# CONTRAINTE ACTIVE (ou saturée)
# = Contrainte utilisée à 100%
# Exemple: Temps = 100/100h
# -> Si on avait 101h, on pourrait augmenter le profit!

# CONTRAINTE NON ACTIVE (ou lâche)
# = Contrainte pas complètement utilisée
# Exemple: Bois = 135/200kg (reste 65kg)
# -> Avoir plus de bois ne change rien au résultat

# Identifier les contraintes actives:
for name, constraint in prob.constraints.items():
    print(f"{name}: slack = {constraint.slack}")

# Explications:
# slack = "marge" de la contrainte
# slack = 0 -> contrainte active
# slack > 0 -> contrainte non active (reste de la ressource)

# Sortie:
# Contrainte_Temps: slack = 0.0    (active!)
# Contrainte_Bois: slack = 65.0    (non active)


# === ANALYSE DE SENSIBILITÉ (INTUITIVE) ===

# Que se passe-t-il si on change les données?

# Scénario 1: +10h de travail (110h au lieu de 100h)
# -> Le profit va augmenter! (temps est la contrainte active)

# Scénario 2: +50kg de bois (250kg au lieu de 200kg)
# -> Le profit NE CHANGE PAS! (bois n'est pas limitant)

# Scénario 3: Profit table passe de 80€ à 90€
# -> On va fabriquer plus de tables, moins de chaises

# Scénario 4: Temps chaise passe de 2h à 3h
# -> On va fabriquer moins de chaises, plus de tables


[OK] DEUXIÈME EXEMPLE: PROBLÈME DE DIÈTE (NUTRITION)

# === ÉNONCÉ DU PROBLÈME ===

# Tu veux créer un régime alimentaire équilibré
# Objectif: MINIMISER le coût total

# Aliments disponibles:
# 1. Pain: 0.50€/unité, 2g protéines, 10g glucides, 1g lipides
# 2. Lait: 1.20€/L, 8g protéines, 12g glucides, 5g lipides
# 3. Œufs: 0.30€/œuf, 6g protéines, 1g glucides, 5g lipides

# Besoins nutritionnels minimums par jour:
# - Protéines: 50g minimum
# - Glucides: 100g minimum
# - Lipides: 30g minimum

# QUESTION: Combien de chaque aliment consommer pour minimiser le coût?


# === CODE COMPLET ===

"""
diete.py - Problème de diète optimale
"""

from pulp import *

# 1. Créer le problème (MINIMISER cette fois!)
prob = LpProblem("Problème_Diète", LpMinimize)

# 2. Définir les variables de décision
# x1 = quantité de pain (unités)
# x2 = quantité de lait (litres)
# x3 = quantité d'œufs (nombre)

x1 = LpVariable("Pain", lowBound=0, cat='Continuous')
x2 = LpVariable("Lait", lowBound=0, cat='Continuous')
x3 = LpVariable("Oeufs", lowBound=0, cat='Continuous')

# Explications:
# Continuous car on peut consommer 1.5 unités de pain, 0.8L de lait, etc.
# lowBound=0 car on ne peut pas consommer -2 œufs!

# 3. Définir la fonction objectif (coût à minimiser)
prob += 0.50*x1 + 1.20*x2 + 0.30*x3, "Coût_Total"

# Explications:
# 0.50*x1 = coût du pain
# 1.20*x2 = coût du lait
# 0.30*x3 = coût des œufs
# On veut MINIMISER ce coût

# 4. Définir les contraintes (besoins nutritionnels minimums)

# Contrainte protéines: ≥ 50g
prob += 2*x1 + 8*x2 + 6*x3 >= 50, "Protéines_Min"

# Explications:
# 2*x1 = protéines du pain (2g par unité)
# 8*x2 = protéines du lait (8g par litre)
# 6*x3 = protéines des œufs (6g par œuf)
# >= 50 = au moins 50g de protéines

# Contrainte glucides: ≥ 100g
prob += 10*x1 + 12*x2 + 1*x3 >= 100, "Glucides_Min"

# Contrainte lipides: ≥ 30g
prob += 1*x1 + 5*x2 + 5*x3 >= 30, "Lipides_Min"

# 5. Résoudre
prob.solve()

# 6. Afficher les résultats
print("Statut:", LpStatus[prob.status])
print(f"\nRégime optimal:")
print(f"Pain: {x1.varValue:.2f} unités")
print(f"Lait: {x2.varValue:.2f} litres")
print(f"Œufs: {x3.varValue:.2f} œufs")
print(f"Coût total: {value(prob.objective):.2f}€")

# 7. Vérifier les apports nutritionnels
proteines = 2*x1.varValue + 8*x2.varValue + 6*x3.varValue
glucides = 10*x1.varValue + 12*x2.varValue + 1*x3.varValue
lipides = 1*x1.varValue + 5*x2.varValue + 5*x3.varValue

print(f"\nApports nutritionnels:")
print(f"Protéines: {proteines:.2f}g (minimum: 50g)")
print(f"Glucides: {glucides:.2f}g (minimum: 100g)")
print(f"Lipides: {lipides:.2f}g (minimum: 30g)")


# === EXÉCUTER ===

python diete.py

# Sortie attendue:
"""
Statut: Optimal

Régime optimal:
Pain: 4.17 unités
Lait: 2.92 litres
Œufs: 1.25 œufs

Coût total: 5.96€

Apports nutritionnels:
Protéines: 50.00g (minimum: 50g)
Glucides: 100.00g (minimum: 100g)
Lipides: 30.00g (minimum: 30g)
"""


# === INTERPRÉTATION ===

# La solution optimale respecte EXACTEMENT les minimums
# proteines = 50.00g (pas plus, juste ce qu'il faut)
# glucides = 100.00g (pas plus)
# lipides = 30.00g (pas plus)

# POURQUOI?
# Car toute quantité supplémentaire coûterait plus cher
# sans améliorer la fonction objectif (minimiser le coût)

# Les 3 contraintes sont ACTIVES (saturées)
# = Toutes sont limitantes

# Si on voulait plus de protéines pour la santé:
# On pourrait ajouter: prob += proteines >= 60
# Mais le coût augmenterait!


[OK] TROISIÈME EXEMPLE: PROBLÈME DE TRANSPORT

# === ÉNONCÉ DU PROBLÈME ===

# Une entreprise a 3 usines et 4 magasins
# Chaque usine produit un certain stock
# Chaque magasin a une demande à satisfaire
# Le transport coûte selon la distance

# DONNÉES:

# Production des usines:
# Usine A: 100 unités
# Usine B: 150 unités
# Usine C: 80 unités
# Total: 330 unités

# Demande des magasins:
# Magasin 1: 80 unités
# Magasin 2: 90 unités
# Magasin 3: 70 unités
# Magasin 4: 60 unités
# Total: 300 unités

# Coût de transport (€ par unité):
#           Mag1  Mag2  Mag3  Mag4
# Usine A:    4     6     8     5
# Usine B:    5     4     7     6
# Usine C:    6     5     4     7

# Objectif: MINIMISER le coût total de transport


# === CODE COMPLET ===

"""
transport.py - Problème de transport optimal
"""

from pulp import *

# 1. Définir les données

# Usines et leur production
usines = ['A', 'B', 'C']
production = {'A': 100, 'B': 150, 'C': 80}

# Magasins et leur demande
magasins = ['M1', 'M2', 'M3', 'M4']
demande = {'M1': 80, 'M2': 90, 'M3': 70, 'M4': 60}

# Coûts de transport (dictionnaire imbriqué)
couts = {
    'A': {'M1': 4, 'M2': 6, 'M3': 8, 'M4': 5},
    'B': {'M1': 5, 'M2': 4, 'M3': 7, 'M4': 6},
    'C': {'M1': 6, 'M2': 5, 'M3': 4, 'M4': 7}
}

# Explications:
# couts['A']['M1'] = 4 signifie:
# Transporter 1 unité de l'usine A au magasin M1 coûte 4€

# 2. Créer le problème
prob = LpProblem("Problème_Transport", LpMinimize)

# 3. Créer les variables de décision
# xij = quantité transportée de l'usine i au magasin j

# Utiliser un dictionnaire pour stocker toutes les variables
x = LpVariable.dicts("Transport",
                     ((i, j) for i in usines for j in magasins),
                     lowBound=0,
                     cat='Continuous')

# Explications détaillées:

# LpVariable.dicts = créer plusieurs variables à la fois
# "Transport" = préfixe du nom des variables
# ((i, j) for i in usines for j in magasins) = combinaisons
#   - Génère: ('A','M1'), ('A','M2'), ..., ('C','M4')
#   - Total: 3 usines × 4 magasins = 12 variables
# lowBound=0 = pas de transport négatif

# Résultat: dictionnaire de variables
# x[('A','M1')] = variable pour transport A->M1
# x[('A','M2')] = variable pour transport A->M2
# ...
# x[('C','M4')] = variable pour transport C->M4

# 4. Définir la fonction objectif (coût total à minimiser)

prob += lpSum([couts[i][j] * x[(i,j)] 
               for i in usines 
               for j in magasins]), "Coût_Transport_Total"

# Explications:

# lpSum = somme efficace dans PuLP (comme sum() de Python)
# [couts[i][j] * x[(i,j)] for i in usines for j in magasins]
# = liste de tous les coûts
# Exemple:
#   couts['A']['M1'] * x[('A','M1')] +
#   couts['A']['M2'] * x[('A','M2')] +
#   ... +
#   couts['C']['M4'] * x[('C','M4')]

# 5. Contraintes de production (offre)
# Chaque usine ne peut pas expédier plus que sa production

for i in usines:
    prob += lpSum([x[(i,j)] for j in magasins]) <= production[i], f"Production_{i}"

# Explications:

# Pour chaque usine i:
#   Somme de tout ce qu'elle expédie ≤ sa production
# Exemple pour usine A:
#   x[('A','M1')] + x[('A','M2')] + x[('A','M3')] + x[('A','M4')] ≤ 100

# 6. Contraintes de demande (demande doit être satisfaite)
# Chaque magasin doit recevoir exactement sa demande

for j in magasins:
    prob += lpSum([x[(i,j)] for i in usines]) == demande[j], f"Demande_{j}"

# Explications:

# Pour chaque magasin j:
#   Somme de tout ce qu'il reçoit = sa demande
# Exemple pour magasin M1:
#   x[('A','M1')] + x[('B','M1')] + x[('C','M1')] = 80

# Note: == (égalité stricte) car on doit satisfaire la demande exacte

# 7. Résoudre
prob.solve()

# 8. Afficher les résultats
print("Statut:", LpStatus[prob.status])
print(f"\nCoût total optimal: {value(prob.objective):.2f}€")

print("\nPlan de transport:")
print("-" * 50)
for i in usines:
    for j in magasins:
        quantite = x[(i,j)].varValue
        if quantite > 0:  # Afficher seulement les transports non nuls
            cout = couts[i][j]
            print(f"{i} -> {j}: {quantite:.1f} unités (coût: {cout}€/unité)")

# 9. Vérifier les contraintes
print("\nVérification:")
print("-" * 50)

# Production utilisée par usine
for i in usines:
    utilise = sum(x[(i,j)].varValue for j in magasins)
    print(f"Usine {i}: {utilise:.1f}/{production[i]} unités utilisées")

print()

# Demande satisfaite par magasin
for j in magasins:
    recu = sum(x[(i,j)].varValue for i in usines)
    print(f"Magasin {j}: {recu:.1f}/{demande[j]} unités reçues")


# === EXÉCUTER ===

python transport.py

# Sortie attendue:
"""
Statut: Optimal

Coût total optimal: 1380.00€

Plan de transport:
--------------------------------------------------
A -> M1: 80.0 unités (coût: 4€/unité)
A -> M4: 20.0 unités (coût: 5€/unité)
B -> M2: 90.0 unités (coût: 4€/unité)
B -> M4: 40.0 unités (coût: 6€/unité)
C -> M3: 70.0 unités (coût: 4€/unité)

Vérification:
--------------------------------------------------
Usine A: 100.0/100 unités utilisées
Usine B: 130.0/150 unités utilisées
Usine C: 70.0/80 unités utilisées

Magasin M1: 80.0/80 unités reçues
Magasin M2: 90.0/90 unités reçues
Magasin M3: 70.0/70 unités reçues
Magasin M4: 60.0/60 unités reçues
"""


# === INTERPRÉTATION ===

# La solution optimale:
# 1. Usine A envoie tout au magasin M1 (le moins cher pour A)
# 2. Usine B envoie principalement à M2 (le moins cher pour B)
# 3. Usine C envoie à M3 (le moins cher pour C)

# Toutes les demandes sont satisfaites (contraintes ==)
# Pas toute la production est utilisée:
#   - Usine B: 130/150 (reste 20 unités)
#   - Usine C: 70/80 (reste 10 unités)

# C'est normal car:
# Production totale = 330 unités
# Demande totale = 300 unités
# Surplus = 30 unités (non utilisé)


[OK] PROBLÈME AVEC VARIABLES ENTIÈRES (INTEGER PROGRAMMING)

# === POURQUOI DES VARIABLES ENTIÈRES? ===

# Parfois, les variables DOIVENT être des nombres entiers

# Exemples:
# - Nombre d'employés à embaucher (pas 2.5 employés!)
# - Nombre de camions à acheter (pas 3.7 camions!)
# - Nombre de projets à sélectionner (0 ou 1, pas 0.6)

# On appelle ça:
# - PLNE (Programmation Linéaire en Nombres Entiers)
# - MILP (Mixed Integer Linear Programming) en anglais
# - ILP (Integer Linear Programming)


# === EXEMPLE: PROBLÈME D'EMBAUCHE ===

# Une entreprise doit embaucher du personnel
# 3 types de postes disponibles

# Développeurs:
# - Salaire: 4000€/mois
# - Productivité: 10 unités/mois

# Designers:
# - Salaire: 3500€/mois
# - Productivité: 8 unités/mois

# Managers:
# - Salaire: 5000€/mois
# - Productivité: 5 unités/mois (management)

# Contraintes:
# - Budget maximum: 50,000€/mois
# - Productivité minimale requise: 100 unités/mois
# - Au moins 1 manager obligatoire
# - Maximum 15 employés au total

# Objectif: MAXIMISER la productivité totale


# === CODE COMPLET ===

"""
embauche.py - Problème d'embauche avec variables entières
"""

from pulp import *

# 1. Créer le problème
prob = LpProblem("Problème_Embauche", LpMaximize)

# 2. Définir les variables de décision (ENTIÈRES!)
dev = LpVariable("Développeurs", lowBound=0, cat='Integer')
des = LpVariable("Designers", lowBound=0, cat='Integer')
mgr = LpVariable("Managers", lowBound=1, cat='Integer')
# lowBound=1 pour mgr car au moins 1 manager obligatoire

# Explications:
# cat='Integer' = NOMBRES ENTIERS SEULEMENT
# dev.varValue sera toujours un entier: 0, 1, 2, 3...
# Jamais 2.5 développeurs!

# 3. Définir la fonction objectif (productivité totale)
prob += 10*dev + 8*des + 5*mgr, "Productivité_Totale"

# 4. Contraintes

# Budget maximum
prob += 4000*dev + 3500*des + 5000*mgr <= 50000, "Budget_Max"

# Productivité minimale
prob += 10*dev + 8*des + 5*mgr >= 100, "Productivité_Min"

# Maximum 15 employés
prob += dev + des + mgr <= 15, "Employés_Max"

# 5. Résoudre
prob.solve()

# 6. Afficher les résultats
print("Statut:", LpStatus[prob.status])
print(f"\nÉquipe optimale:")
print(f"Développeurs: {int(dev.varValue)}")
print(f"Designers: {int(des.varValue)}")
print(f"Managers: {int(mgr.varValue)}")
print(f"Total employés: {int(dev.varValue + des.varValue + mgr.varValue)}")

# 7. Calculs
cout_total = 4000*dev.varValue + 3500*des.varValue + 5000*mgr.varValue
productivite = 10*dev.varValue + 8*des.varValue + 5*mgr.varValue

print(f"\nCoût total: {cout_total:.0f}€/mois")
print(f"Productivité: {productivite:.0f} unités/mois")
print(f"Budget restant: {50000 - cout_total:.0f}€")


# === EXÉCUTER ===

python embauche.py

# Sortie:
"""
Statut: Optimal

Équipe optimale:
Développeurs: 10
Designers: 2
Managers: 1
Total employés: 13

Coût total: 48500€/mois
Productivité: 121 unités/mois
Budget restant: 1500€
"""


# === DIFFÉRENCE INTEGER vs CONTINUOUS ===

# Si on avait utilisé cat='Continuous':
# Solution possible: dev=10.5, des=2.3, mgr=1.2
# Productivité: 125.4 unités
# MAIS impossible dans la réalité!

# Avec cat='Integer':
# Solution: dev=10, des=2, mgr=1
# Productivité: 121 unités
# Réaliste et applicable!

# Note: Les problèmes entiers sont plus difficiles à résoudre
# Le solveur doit tester de nombreuses combinaisons


[OK] PROBLÈME BINAIRE (0 ou 1)

# === VARIABLES BINAIRES ===

# Variables qui peuvent être SEULEMENT 0 ou 1
# Utilisées pour les décisions OUI/NON

# Exemples:
# - Construire une usine: 1=oui, 0=non
# - Accepter un projet: 1=oui, 0=non
# - Activer une machine: 1=oui, 0=non


# === EXEMPLE: SÉLECTION DE PROJETS ===

# Une entreprise peut investir dans 5 projets
# Chaque projet a un coût et un profit

# Projet A: coût 100k€, profit 150k€
# Projet B: coût 80k€, profit 120k€
# Projet C: coût 120k€, profit 180k€
# Projet D: coût 60k€, profit 90k€
# Projet E: coût 90k€, profit 130k€

# Contraintes:
# - Budget total: 250k€
# - Si on fait A, on doit faire B (dépendance)
# - On ne peut pas faire C et D en même temps (incompatibles)

# Objectif: MAXIMISER le profit total


# === CODE COMPLET ===

"""
projets.py - Sélection de projets avec variables binaires
"""

from pulp import *

# 1. Définir les données
projets = ['A', 'B', 'C', 'D', 'E']
couts = {'A': 100, 'B': 80, 'C': 120, 'D': 60, 'E': 90}
profits = {'A': 150, 'B': 120, 'C': 180, 'D': 90, 'E': 130}

# 2. Créer le problème
prob = LpProblem("Sélection_Projets", LpMaximize)

# 3. Définir les variables binaires
x = LpVariable.dicts("Projet", projets, cat='Binary')

# Explications:
# cat='Binary' = SEULEMENT 0 ou 1
# x['A'] = 1 si on fait le projet A, 0 sinon
# x['B'] = 1 si on fait le projet B, 0 sinon
# etc.

# 4. Fonction objectif (profit total)
prob += lpSum([profits[p] * x[p] for p in projets]), "Profit_Total"

# Explications:
# profits['A'] * x['A'] = 150 si x['A']=1, 0 si x['A']=0
# On somme les profits des projets sélectionnés

# 5. Contraintes

# Budget total
prob += lpSum([couts[p] * x[p] for p in projets]) <= 250, "Budget"

# Si A alors B (dépendance logique)
prob += x['A'] <= x['B'], "Dépendance_A_B"

# Explications:
# Si x['A']=1 (faire A), alors x['B'] doit être ≥1, donc x['B']=1
# Si x['A']=0 (pas A), alors x['B'] peut être 0 ou 1 (libre)
# En logique: A -> B (si A alors B)

# C et D incompatibles (au plus un des deux)
prob += x['C'] + x['D'] <= 1, "Incompatibilité_C_D"

# Explications:
# x['C'] + x['D'] ≤ 1 signifie:
#   - x['C']=0, x['D']=0 [OK] (aucun)
#   - x['C']=1, x['D']=0 [OK] (C seulement)
#   - x['C']=0, x['D']=1 [OK] (D seulement)
#   - x['C']=1, x['D']=1 [X] (impossible, somme=2>1)

# 6. Résoudre
prob.solve()

# 7. Afficher les résultats
print("Statut:", LpStatus[prob.status])
print(f"\nProjets sélectionnés:")

projets_selectionnes = []
cout_total = 0
profit_total = 0

for p in projets:
    if x[p].varValue == 1:
        projets_selectionnes.append(p)
        cout_total += couts[p]
        profit_total += profits[p]
        print(f"  Projet {p}: coût {couts[p]}k€, profit {profits[p]}k€")

print(f"\nCoût total: {cout_total}k€")
print(f"Profit total: {profit_total}k€")
print(f"Budget restant: {250 - cout_total}k€")


# === EXÉCUTER ===

python projets.py

# Sortie:
"""
Statut: Optimal

Projets sélectionnés:
  Projet A: coût 100k€, profit 150k€
  Projet B: coût 80k€, profit 120k€
  Projet E: coût 90k€, profit 130k€

Coût total: 270k€
Profit total: 400k€
Budget restant: -20k€
"""

# ERREUR! Le coût dépasse le budget!
# Il y a un bug dans notre logique...

# CORRECTION: La contrainte dépendance était mal formulée
# Si on veut "Si A alors B", c'est correct: x['A'] <= x['B']
# Mais peut-être que B coûte trop cher...

# Refaisons sans la dépendance pour voir:


# === VERSION SANS DÉPENDANCE ===

"""
projets_v2.py
"""

from pulp import *

projets = ['A', 'B', 'C', 'D', 'E']
couts = {'A': 100, 'B': 80, 'C': 120, 'D': 60, 'E': 90}
profits = {'A': 150, 'B': 120, 'C': 180, 'D': 90, 'E': 130}

prob = LpProblem("Sélection_Projets_V2", LpMaximize)

x = LpVariable.dicts("Projet", projets, cat='Binary')

prob += lpSum([profits[p] * x[p] for p in projets]), "Profit_Total"

prob += lpSum([couts[p] * x[p] for p in projets]) <= 250, "Budget"

prob += x['C'] + x['D'] <= 1, "Incompatibilité_C_D"

prob.solve()

print("Statut:", LpStatus[prob.status])
print("\nProjets sélectionnés:")
for p in projets:
    if x[p].varValue == 1:
        print(f"  Projet {p}")

cout_total = sum(couts[p] * x[p].varValue for p in projets)
profit_total = sum(profits[p] * x[p].varValue for p in projets)

print(f"\nCoût: {cout_total:.0f}k€/{250}k€")
print(f"Profit: {profit_total:.0f}k€")

# Sortie:
"""
Projets sélectionnés:
  Projet A
  Projet C
  Projet E

Coût: 310k€/250k€
Profit: 460k€
"""


[OK] UTILISER SCIPY.OPTIMIZE.LINPROG

# === ALTERNATIVE À PULP ===

# SciPy inclut une fonction linprog pour la PL
# Syntaxe plus mathématique
# Bon pour petits problèmes

# Note: linprog ne peut que MINIMISER
# Pour maximiser, minimiser le négatif!


# === EXEMPLE: PROBLÈME DES MEUBLES AVEC SCIPY ===

"""
meubles_scipy.py
"""

import numpy as np
from scipy.optimize import linprog

# Problème: Maximiser 50x + 80y
# Contraintes:
#   2x + 4y ≤ 100
#   3x + 5y ≤ 200
#   x, y ≥ 0

# 1. Fonction objectif (à MINIMISER)
# On veut maximiser 50x + 80y
# Donc on minimise -(50x + 80y) = -50x - 80y

c = [-50, -80]  # Coefficients (négatifs pour maximiser)

# Explications:
# c[0] = -50 (coefficient de x)
# c[1] = -80 (coefficient de y)

# 2. Contraintes d'inégalité: Ax ≤ b

# Matrice A (coefficients des contraintes)
A_ub = [
    [2, 4],   # 2x + 4y ≤ 100
    [3, 5]    # 3x + 5y ≤ 200
]

# Vecteur b (limites)
b_ub = [100, 200]

# Explications:
# A_ub = "upper bound" = ≤
# Ligne 1: 2x + 4y ≤ 100
# Ligne 2: 3x + 5y ≤ 200

# 3. Bornes des variables: x ≥ 0, y ≥ 0
bounds = [(0, None), (0, None)]

# Explications:
# (0, None) = x ≥ 0, pas de limite supérieure
# (0, None) = y ≥ 0, pas de limite supérieure

# 4. Résoudre
result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

# Explications:
# c = fonction objectif
# A_ub, b_ub = contraintes ≤
# bounds = bornes des variables
# method='highs' = algorithme moderne (recommandé)

# 5. Afficher les résultats
if result.success:
    print("Statut: Optimal")
    print(f"Chaises: {result.x[0]:.2f}")
    print(f"Tables: {result.x[1]:.2f}")
    print(f"Profit: {-result.fun:.2f}€")  # Négatif car on a minimisé -profit
else:
    print("Pas de solution:", result.message)

# Sortie:
"""
Statut: Optimal
Chaises: 20.00
Tables: 15.00
Profit: 2200.00€
"""


# === CONTRAINTES D'ÉGALITÉ ===

# Si tu as des contraintes avec =

# Exemple: x + y = 50

A_eq = [[1, 1]]   # Matrice des contraintes d'égalité
b_eq = [50]       # Valeurs

result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds)


# === CONTRAINTES ≥ ===

# linprog ne gère que ≤ directement
# Pour x + y ≥ 30, multiplier par -1: -x - y ≤ -30

A_ub = [
    [2, 4],      # 2x + 4y ≤ 100
    [-1, -1]     # -x - y ≤ -30  (équivalent à x + y ≥ 30)
]
b_ub = [100, -30]


[OK] VISUALISATION GRAPHIQUE (2D)

# === POURQUOI VISUALISER? ===

# En 2D (2 variables), on peut DESSINER le problème
# Très utile pour comprendre la géométrie

# === EXEMPLE: PROBLÈME DES MEUBLES ===

"""
visualisation.py
"""

import numpy as np
import matplotlib.pyplot as plt

# Définir les variables
x = np.linspace(0, 60, 300)

# Contraintes
# 2x + 4y ≤ 100 -> y ≤ (100 - 2x) / 4
y1 = (100 - 2*x) / 4

# 3x + 5y ≤ 200 -> y ≤ (200 - 3x) / 5
y2 = (200 - 3*x) / 5

# Créer le graphique
plt.figure(figsize=(10, 8))

# Tracer les contraintes
plt.plot(x, y1, 'r-', label='2x + 4y ≤ 100 (Temps)', linewidth=2)
plt.plot(x, y2, 'b-', label='3x + 5y ≤ 200 (Bois)', linewidth=2)

# Axes non-négatifs
plt.axhline(0, color='k', linewidth=0.5)
plt.axvline(0, color='k', linewidth=0.5)

# Région réalisable (remplir)
plt.fill_between(x, 0, np.minimum(y1, y2), 
                 where=(y1>=0) & (y2>=0), 
                 alpha=0.3, color='green', 
                 label='Région réalisable')

# Solution optimale
plt.plot(20, 15, 'ro', markersize=15, label='Solution optimale (20, 15)')

# Lignes de niveau de la fonction objectif
# 50x + 80y = valeur
for valeur in [500, 1000, 1500, 2000, 2200]:
    y_obj = (valeur - 50*x) / 80
    plt.plot(x, y_obj, 'g--', alpha=0.3, linewidth=1)

# Labels
plt.xlabel('Chaises (x)', fontsize=12)
plt.ylabel('Tables (y)', fontsize=12)
plt.title('Problème de Programmation Linéaire - Meubles', fontsize=14)
plt.legend(fontsize=10)
plt.grid(True, alpha=0.3)
plt.xlim(0, 60)
plt.ylim(0, 35)

# Annoter les sommets
sommets = [(0, 0), (0, 25), (20, 15), (50, 0)]
for sommet in sommets:
    plt.annotate(f'{sommet}', 
                xy=sommet, 
                xytext=(sommet[0]+2, sommet[1]+1),
                fontsize=9,
                bbox=dict(boxstyle='round,pad=0.3', facecolor='yellow', alpha=0.7))

plt.tight_layout()
plt.savefig('programmation_lineaire.png', dpi=300)
plt.show()


# === INTERPRÉTATION DU GRAPHIQUE ===

# 1. RÉGION RÉALISABLE (zone verte)
# = Tous les points (x,y) qui respectent toutes les contraintes
# = C'est un polygone délimité par les droites

# 2. SOMMETS DU POLYGONE
# = Points où deux contraintes se rencontrent
# (0,0): origine
# (0,25): sur contrainte temps, y max
# (20,15): intersection temps et bois -> SOLUTION OPTIMALE!
# (50,0): sur contrainte temps, x max

# 3. LIGNES POINTILLÉES VERTES
# = Lignes de niveau de la fonction objectif (iso-profit)
# 50x + 80y = 500 (profit 500€)
# 50x + 80y = 1000 (profit 1000€)
# ...
# 50x + 80y = 2200 (profit 2200€) -> passe par (20,15)!

# 4. THÉORÈME FONDAMENTAL
# La solution optimale est TOUJOURS un sommet du polygone!
# Pas besoin de tester tous les points à l'intérieur
# Il suffit de tester les sommets


[OK] ANALYSE DE SENSIBILITÉ

# === QU'EST-CE QUE L'ANALYSE DE SENSIBILITÉ? ===

# = Étudier comment la solution change si les paramètres changent

# Questions typiques:
# - Si le profit des tables augmente, que se passe-t-il?
# - Si on a 10h de plus, combien de profit supplémentaire?
# - Quelle ressource est la plus limitante?


# === PRIX DUAL (SHADOW PRICE) ===

# = Valeur marginale d'une contrainte
# = Augmentation du profit si on augmente la limite de 1 unité

# Exemple: Prix dual de la contrainte temps = 15€/h
# Signifie: Si on a 1h de plus (101h au lieu de 100h)
# Le profit augmente de 15€

"""
analyse_sensibilite.py
"""

from pulp import *

# Problème original
prob = LpProblem("Meubles", LpMaximize)

x = LpVariable("Chaises", lowBound=0)
y = LpVariable("Tables", lowBound=0)

prob += 50*x + 80*y, "Profit"

contrainte_temps = prob += 2*x + 4*y <= 100, "Temps"
contrainte_bois = prob += 3*x + 5*y <= 200, "Bois"

prob.solve()

# Solution originale
print("=== SOLUTION ORIGINALE ===")
print(f"Chaises: {x.varValue}")
print(f"Tables: {y.varValue}")
print(f"Profit: {value(prob.objective)}€")

# Prix duaux (shadow prices)
print("\n=== PRIX DUAUX ===")
for name, constraint in prob.constraints.items():
    print(f"{name}: {constraint.pi:.2f}€")
    # .pi = prix dual (π en mathématiques)

# Sortie:
"""
=== SOLUTION ORIGINALE ===
Chaises: 20.0
Tables: 15.0
Profit: 2200.0€

=== PRIX DUAUX ===
Temps: 15.00€
Bois: 0.00€
"""

# Interprétation:
# - Temps: prix dual = 15€/h
#   -> 1h supplémentaire augmente le profit de 15€
#   -> Contrainte ACTIVE (limitante)

# - Bois: prix dual = 0€/kg
#   -> Bois supplémentaire n'augmente pas le profit
#   -> Contrainte NON ACTIVE (pas limitante)


# === VÉRIFICATION MANUELLE ===

# Test: +10h de temps (110h au lieu de 100h)

prob2 = LpProblem("Meubles_Plus_Temps", LpMaximize)

x2 = LpVariable("Chaises", lowBound=0)
y2 = LpVariable("Tables", lowBound=0)

prob2 += 50*x2 + 80*y2
prob2 += 2*x2 + 4*y2 <= 110  # +10h
prob2 += 3*x2 + 5*y2 <= 200

prob2.solve()

nouveau_profit = value(prob2.objective)
ancien_profit = value(prob.objective)
augmentation = nouveau_profit - ancien_profit

print(f"\n=== AVEC +10H ===")
print(f"Nouveau profit: {nouveau_profit}€")
print(f"Augmentation: {augmentation}€")
print(f"Prédiction (15€/h × 10h): {15*10}€")

# Sortie:
"""
=== AVEC +10H ===
Nouveau profit: 2350.0€
Augmentation: 150.0€
Prédiction (15€/h × 10h): 150€
"""

# PARFAIT! La prédiction correspond!


# === TEST: +50KG DE BOIS ===

prob3 = LpProblem("Meubles_Plus_Bois", LpMaximize)

x3 = LpVariable("Chaises", lowBound=0)
y3 = LpVariable("Tables", lowBound=0)

prob3 += 50*x3 + 80*y3
prob3 += 2*x3 + 4*y3 <= 100
prob3 += 3*x3 + 5*y3 <= 250  # +50kg

prob3.solve()

print(f"\n=== AVEC +50KG BOIS ===")
print(f"Profit: {value(prob3.objective)}€")
print(f"Changement: {value(prob3.objective) - ancien_profit}€")

# Sortie:
"""
=== AVEC +50KG BOIS ===
Profit: 2200.0€
Changement: 0.0€
"""

# AUCUN CHANGEMENT! Le bois n'est pas limitant


[OK] PROBLÈMES COURANTS ET DÉBOGAGE

# === PROBLÈME 1: "Infeasible" (Infaisable) ===

# Signifie: Aucune solution ne respecte toutes les contraintes
# Les contraintes sont CONTRADICTOIRES

# Exemple:

prob = LpProblem("Infaisable", LpMaximize)
x = LpVariable("x", lowBound=0)

prob += x  # Maximiser x
prob += x <= 10   # x doit être ≤ 10
prob += x >= 20   # x doit être ≥ 20  -> IMPOSSIBLE!

prob.solve()
print(LpStatus[prob.status])  # Affiche: "Infeasible"

# SOLUTION: Réviser les contraintes
# Trouver laquelle est impossible


# === PROBLÈME 2: "Unbounded" (Non borné) ===

# Signifie: La fonction objectif peut aller à l'infini
# Pas de limite supérieure

# Exemple:

prob = LpProblem("Non_Borne", LpMaximize)
x = LpVariable("x", lowBound=0)
y = LpVariable("y", lowBound=0)

prob += x + y  # Maximiser x + y
# AUCUNE CONTRAINTE!
# x et y peuvent aller à l'infini!

prob.solve()
print(LpStatus[prob.status])  # Affiche: "Unbounded"

# SOLUTION: Ajouter des contraintes pour limiter les variables


# === PROBLÈME 3: Variables négatives ===

# Oubli de lowBound=0

x = LpVariable("x")  # PAS de lowBound!
# x peut être négatif!

# SOLUTION:
x = LpVariable("x", lowBound=0)


# === PROBLÈME 4: Mauvaise direction d'optimisation ===

# Tu veux minimiser mais tu écris LpMaximize

prob = LpProblem("Erreur", LpMaximize)
prob += 50*x + 80*y  # Tu veux minimiser le coût
# Mais tu as écrit LpMaximize!

# SOLUTION:
prob = LpProblem("Correct", LpMinimize)


# === PROBLÈME 5: Contrainte mal formulée ===

# Erreur de signe

prob += 2*x + 4*y >= 100  # Voulait ≤ mais écrit ≥

# SOLUTION: Vérifier chaque contrainte


# === PROBLÈME 6: Solveur non trouvé ===

# Message: "Pulp: Error while executing"

# SOLUTION: Installer un solveur
pip install pulp
# ou
conda install -c conda-forge coincbc


# === PROBLÈME 7: Performance lente ===

# Pour problèmes avec beaucoup de variables/contraintes

# SOLUTION 1: Utiliser un meilleur solveur
prob.solve(PULP_CBC_CMD())  # CBC (par défaut)
prob.solve(GLPK_CMD())      # GLPK
prob.solve(GUROBI())        # Gurobi (commercial, très rapide)

# SOLUTION 2: Simplifier le modèle
# Réduire le nombre de variables
# Agréger les contraintes similaires


[OK] CAS D'USAGE AVANCÉS

# === 1. PROBLÈME DU SAC À DOS (KNAPSACK) ===

"""
sac_a_dos.py
"""

from pulp import *

# Tu as un sac qui peut porter 50kg maximum
# Tu as 6 objets avec poids et valeur
# Objectif: Maximiser la valeur totale

objets = ['A', 'B', 'C', 'D', 'E', 'F']
poids = {'A': 10, 'B': 20, 'C': 15, 'D': 8, 'E': 12, 'F': 18}
valeurs = {'A': 60, 'B': 100, 'C': 80, 'D': 45, 'E': 70, 'F': 90}
capacite = 50

prob = LpProblem("Sac_A_Dos", LpMaximize)

# Variables binaires (prendre ou pas)
x = LpVariable.dicts("Obj", objets, cat='Binary')

# Maximiser la valeur
prob += lpSum([valeurs[i] * x[i] for i in objets])

# Contrainte de poids
prob += lpSum([poids[i] * x[i] for i in objets]) <= capacite

prob.solve()

print("Objets à prendre:")
for i in objets:
    if x[i].varValue == 1:
        print(f"  {i}: poids={poids[i]}kg, valeur={valeurs[i]}€")

poids_total = sum(poids[i] * x[i].varValue for i in objets)
valeur_totale = sum(valeurs[i] * x[i].varValue for i in objets)

print(f"\nPoids total: {poids_total:.0f}/{capacite}kg")
print(f"Valeur totale: {valeur_totale:.0f}€")


# === 2. PROBLÈME D'AFFECTATION ===

"""
affectation.py - Affecter des employés à des tâches
"""

from pulp import *

# 4 employés, 4 tâches
# Coût de chaque employé pour chaque tâche

employes = ['Alice', 'Bob', 'Charlie', 'Diana']
taches = ['T1', 'T2', 'T3', 'T4']

couts = {
    'Alice':   {'T1': 8, 'T2': 6, 'T3': 7, 'T4': 9},
    'Bob':     {'T1': 5, 'T2': 7, 'T3': 8, 'T4': 6},
    'Charlie': {'T1': 6, 'T2': 5, 'T3': 9, 'T4': 7},
    'Diana':   {'T1': 7, 'T2': 8, 'T3': 6, 'T4': 5}
}

prob = LpProblem("Affectation", LpMinimize)

# Variables binaires: x[e][t] = 1 si employé e fait tâche t
x = LpVariable.dicts("Affect", 
                     ((e, t) for e in employes for t in taches),
                     cat='Binary')

# Minimiser le coût total
prob += lpSum([couts[e][t] * x[(e,t)] 
               for e in employes 
               for t in taches])

# Chaque employé fait exactement 1 tâche
for e in employes:
    prob += lpSum([x[(e,t)] for t in taches]) == 1

# Chaque tâche est faite par exactement 1 employé
for t in taches:
    prob += lpSum([x[(e,t)] for e in employes]) == 1

prob.solve()

print("Affectation optimale:")
for e in employes:
    for t in taches:
        if x[(e,t)].varValue == 1:
            print(f"  {e} -> {t} (coût: {couts[e][t]})")

cout_total = value(prob.objective)
print(f"\nCoût total: {cout_total:.0f}")


# === 3. PROBLÈME DE DÉCOUPE (CUTTING STOCK) ===

"""
decoupe.py
"""

from pulp import *

# Tu as des barres de 100cm
# Tu dois découper:
#   - 20 morceaux de 30cm
#   - 15 morceaux de 45cm
#   - 10 morceaux de 60cm

# Objectif: Minimiser le nombre de barres utilisées

# Patterns possibles (combinaisons de découpe)
patterns = {
    'P1': {'30cm': 3, '45cm': 0, '60cm': 0},  # 3×30 = 90cm
    'P2': {'30cm': 2, '45cm': 1, '60cm': 0},  # 2×30 + 1×45 = 105cm -> impossible!
    'P3': {'30cm': 1, '45cm': 1, '60cm': 0},  # 1×30 + 1×45 = 75cm
    'P4': {'30cm': 0, '45cm': 2, '60cm': 0},  # 2×45 = 90cm
    'P5': {'30cm': 0, '45cm': 0, '60cm': 1},  # 1×60 = 60cm
}

# Retirer P2 car impossible (>100cm)
del patterns['P2']

prob = LpProblem("Découpe", LpMinimize)

# Variables: nombre de barres découpées selon chaque pattern
x = LpVariable.dicts("Pattern", patterns.keys(), lowBound=0, cat='Integer')

# Minimiser le nombre total de barres
prob += lpSum(x.values())

# Contraintes: satisfaire la demande
prob += lpSum([patterns[p]['30cm'] * x[p] for p in patterns]) >= 20
prob += lpSum([patterns[p]['45cm'] * x[p] for p in patterns]) >= 15
prob += lpSum([patterns[p]['60cm'] * x[p] for p in patterns]) >= 10

prob.solve()

print("Patterns à utiliser:")
total_barres = 0
for p in patterns:
    nb = x[p].varValue
    if nb > 0:
        print(f"  {p}: {int(nb)} barres")
        total_barres += nb

print(f"\nTotal barres: {int(total_barres)}")


[OK] COMPARAISON DES BIBLIOTHÈQUES

# === PULP ===

# [OK] Avantages:
# - Syntaxe simple et intuitive
# - Documentation excellente
# - Bon pour débuter
# - Gratuit et open-source

# [X] Inconvénients:
# - Moins rapide pour très grands problèmes
# - Moins de fonctionnalités avancées

# [IMPORTANT] Utiliser pour:
# - Apprentissage
# - Problèmes petits/moyens (< 10,000 variables)
# - Prototypage rapide


# === SCIPY.OPTIMIZE.LINPROG ===

# [OK] Avantages:
# - Inclus dans SciPy (pas d'installation)
# - Bon pour petits problèmes
# - Rapide pour problèmes simples

# [X] Inconvénients:
# - Syntaxe matricielle (moins intuitive)
# - Pas de variables entières/binaires
# - Limité aux problèmes continus

# [IMPORTANT] Utiliser pour:
# - Problèmes simples
# - Quand SciPy est déjà installé
# - Problèmes continus seulement


# === CVXPY ===

# [OK] Avantages:
# - Puissant pour problèmes convexes
# - Syntaxe mathématique élégante
# - Détecte automatiquement le type de problème

# [X] Inconvénients:
# - Courbe d'apprentissage plus raide
# - Syntaxe différente de PuLP

# [IMPORTANT] Utiliser pour:
# - Problèmes convexes avancés
# - Optimisation non-linéaire
# - Recherche académique


# === GOOGLE OR-TOOLS ===

# [OK] Avantages:
# - Très rapide
# - Excellent pour MILP
# - Développé par Google

# [X] Inconvénients:
# - Documentation parfois complexe
# - Installation parfois difficile

# [IMPORTANT] Utiliser pour:
# - Grands problèmes industriels
# - Problèmes de routage/scheduling
# - Performance critique


# === PYOMO ===

# [OK] Avantages:
# - Très flexible
# - Supporte plusieurs solveurs
# - Bon pour recherche

# [X] Inconvénients:
# - Syntaxe complexe
# - Courbe d'apprentissage élevée

# [IMPORTANT] Utiliser pour:
# - Problèmes très grands
# - Recherche académique
# - Modélisation avancée


# === GUROBI (Commercial) ===

# [OK] Avantages:
# - LE PLUS RAPIDE
# - Excellent pour MILP
# - Support professionnel

# [X] Inconvénients:
# - PAYANT (cher!)
# - Licence académique gratuite

# [IMPORTANT] Utiliser pour:
# - Industrie (production)
# - Problèmes critiques
# - Quand la performance est essentielle


[OK] RESSOURCES ET LIENS

# Documentation officielle PuLP:
# https://coin-or.github.io/pulp/

# Tutoriels PuLP:
# https://coin-or.github.io/pulp/CaseStudies/index.html

# SciPy linprog:
# https://docs.scipy.org/doc/scipy/reference/optimize.linprog-highs.html

# CVXPY:
# https://www.cvxpy.org/

# Google OR-Tools:
# https://developers.google.com/optimization

# Livre gratuit (en anglais):
# "Linear Programming with Python"
# https://realpython.com/linear-programming-python/

# Cours en ligne:
# MIT OpenCourseWare - Linear Programming
# https://ocw.mit.edu/

# Forum Stack Overflow:
# https://stackoverflow.com/questions/tagged/linear-programming

# Communauté OR (Operations Research):
# https://www.informs.org/


[OK] EXERCICES PRATIQUES

# === EXERCICE 1: PROBLÈME SIMPLE ===

# Une boulangerie fabrique des croissants et des pains au chocolat
# - Croissant: 1€ de profit, 10g de beurre, 20g de farine
# - Pain au chocolat: 1.50€ de profit, 15g de beurre, 25g de farine
# Disponible: 1000g de beurre, 2000g de farine
# Objectif: Maximiser le profit

# À TOI DE CODER!


# === EXERCICE 2: PLANIFICATION DE PRODUCTION ===

# Une usine fabrique 3 produits: A, B, C
# Chaque produit passe par 2 machines: M1 et M2
# Temps machine (heures):
#   A: 2h sur M1, 1h sur M2
#   B: 1h sur M1, 2h sur M2
#   C: 3h sur M1, 2h sur M2
# Disponible: M1: 100h, M2: 80h
# Profit: A: 30€, B: 40€, C: 50€
# Objectif: Maximiser le profit


# === EXERCICE 3: INVESTISSEMENT ===

# Tu as 100,000€ à investir dans 5 actifs
# Chaque actif a un rendement et un risque
# Contraintes:
#   - Budget total: 100,000€
#   - Risque moyen ≤ 0.5
#   - Au moins 10,000€ par actif si sélectionné
# Objectif: Maximiser le rendement total


# === SOLUTIONS EN LIGNE ===

# Solutions détaillées disponibles sur:
# https://github.com/ton-repo/programmation-lineaire-exercices


[OK] CHECKLIST AVANT DE RÉSOUDRE UN PROBLÈME

# [OK] J'ai identifié les VARIABLES DE DÉCISION
#   -> Ce que je cherche, les inconnues

# [OK] J'ai défini la FONCTION OBJECTIF
#   -> Ce que je veux maximiser/minimiser

# [OK] J'ai listé toutes les CONTRAINTES
#   -> Limites, ressources, exigences

# [OK] J'ai vérifié que c'est LINÉAIRE
#   -> Pas de x², xy, sin(x), etc.

# [OK] J'ai choisi le BON TYPE de variables
#   -> Continuous, Integer, ou Binary

# [OK] J'ai défini les BORNES
#   -> lowBound, upBound si nécessaire

# [OK] J'ai testé sur un PETIT EXEMPLE d'abord
#   -> Avant de résoudre le gros problème

# [OK] Je peux INTERPRÉTER les résultats
#   -> Comprendre ce que signifie la solution


[OK] ERREURS COURANTES À ÉVITER

# [X] Oublier lowBound=0 pour variables non-négatives
x = LpVariable("x")  # ERREUR: x peut être négatif!
x = LpVariable("x", lowBound=0)  # CORRECT

# [X] Mauvais sens d'optimisation
prob = LpProblem("Min_Coût", LpMaximize)  # ERREUR!
prob = LpProblem("Min_Coût", LpMinimize)  # CORRECT

# [X] Contraintes contradictoires
prob += x >= 100
prob += x <= 50  # IMPOSSIBLE!

# [X] Utiliser == pour float
# Ne JAMAIS faire:
if x.varValue == 10.0:  # Peut échouer à cause des arrondis
# Faire plutôt:
if abs(x.varValue - 10.0) < 1e-6:

# [X] Ne pas vérifier le statut
prob.solve()
print(x.varValue)  # Et si pas de solution?
# Faire plutôt:
prob.solve()
if prob.status == 1:
    print(x.varValue)
else:
    print("Pas de solution!")

# [X] Oublier d'importer
from pulp import *  # OBLIGATOIRE!

# [X] Variables non utilisées
x = LpVariable("x", lowBound=0)
# Mais x n'apparaît nulle part dans le problème!


[OK] ASTUCES ET BONNES PRATIQUES

# [IDEE] ASTUCE 1: Nommer clairement les variables
x = LpVariable("x")  # Pas clair
nb_chaises = LpVariable("Nombre_Chaises")  # MIEUX!

# [IDEE] ASTUCE 2: Ajouter des descriptions aux contraintes
prob += 2*x + 4*y <= 100  # Sans nom
prob += 2*x + 4*y <= 100, "Contrainte_Temps"  # MIEUX!

# [IDEE] ASTUCE 3: Documenter le code
# Explique POURQUOI, pas seulement QUOI
prob += x >= 10  # Minimum de 10 pour rentabilité

# [IDEE] ASTUCE 4: Tester avec des petites données d'abord
# Avant de résoudre avec 10,000 variables
# Teste avec 5 variables pour vérifier la logique

# [IDEE] ASTUCE 5: Afficher le problème pour déboguer
print(prob)  # Affiche toutes les contraintes

# [IDEE] ASTUCE 6: Sauvegarder le modèle
prob.writeLP("mon_probleme.lp")  # Format standard LP
# Tu peux l'ouvrir dans un éditeur pour vérifier

# [IDEE] ASTUCE 7: Utiliser des dictionnaires pour données
# Au lieu de variables séparées
couts = {'A': 10, 'B': 20, 'C': 15}  # MIEUX!

# [IDEE] ASTUCE 8: Profiler les performances
import time
start = time.time()
prob.solve()
print(f"Temps: {time.time() - start:.2f}s")

# [IDEE] ASTUCE 9: Vérifier manuellement la solution
# Calcule les contraintes avec la solution
# Vérifie qu'elles sont respectées

# [IDEE] ASTUCE 10: Visualiser pour 2D
# Dessine les contraintes et la région réalisable
# Ça aide énormément à comprendre!


[OK] CONCLUSION

# La programmation linéaire est un outil PUISSANT
# pour résoudre des problèmes d'optimisation

# TU SAIS MAINTENANT:
# [OK] Ce qu'est la PL et quand l'utiliser
# [OK] Les concepts fondamentaux (variables, objectif, contraintes)
# [OK] Résoudre des problèmes avec PuLP
# [OK] Gérer variables continues, entières, binaires
# [OK] Analyser et interpréter les résultats
# [OK] Déboguer les problèmes courants
# [OK] Visualiser les solutions en 2D

# PROCHAINES ÉTAPES:
# 1. Pratique! Résous les exercices
# 2. Applique à tes propres problèmes
# 3. Explore les bibliothèques avancées (OR-Tools, Gurobi)
# 4. Apprends la programmation non-linéaire
# 5. Étudie l'optimisation stochastique

# RAPPEL FINAL:
# La PL n'est PAS de la magie
# C'est juste des maths appliquées intelligemment
# Avec de la pratique, tu deviendras expert!

# BONNE CHANCE ET BON CODING! [RAPIDE]
```