Atelier : la programmation linéaire, chez Da Lambda

Quatre décisions dans la semaine d'une pizzeria.

Da Lambda, la pizzeria qui a réécrit son logiciel de caisse dans l'atelier sur les fonctions, se pose des questions que le patron tranchait jusqu'ici au jugé. Combien de mètres de chaque pizza préparer pour le vendredi midi ? Quel mélange de fromages coûte le moins sans détremper la pâte ? Quelles commandes de groupe accepter pour le samedi soir, quand la pâte est comptée ? Et un solveur suffira-t-il quand la cuisine servira toute une ville ?

Chaque phase part d'une demande écrite en français, avec ses données brutes, et finit sur une décision chiffrée qu'il faut savoir défendre. Le modèle s'écrit en entier : variables, contraintes, objectif. Le solveur ne fait que le calcul.

L'atelier suppose acquis le chapitre 3 de ce parcours, pour la relaxation, la borne et l'usage de linprog et milp, ainsi que la méthode graphique, l'idée qu'un programme linéaire atteint son optimum en un sommet, et le calcul à la main de ce qui reste sous une contrainte et de son prix, posés dans optimiser sous contraintes.

Atelier à trous. Chaque bloc contient des TODO : on remplace les ... et les pass, puis on exécute. Ici, les trous sont grands : un bloc ne fournit que les données et la signature de la fonction, et le modèle s'écrit en entier. Un bloc s'exécute seul, sans voir les précédents : ce dont il a besoin est recopié en tête. Les lignes assert du bas servent de juge, sur de petits cas qu'on vérifie de tête, jamais sur les données de la demande : la réponse à la demande reste à établir et à défendre. Des coups de pouce, à ouvrir dans l'ordre, débloquent sans donner la solution ; une correction est dépliable sous chaque bloc. L'ouvrir avant d'avoir essayé ne coûte rien à personne d'autre qu'à soi.

Déroulé

Durée	Étape	Notion
10 min	Lancement	Lire l'introduction et l'outil, former des binômes
40 min	1. La pizza au mètre	Deux variables, une proportion à linéariser, lecture d'un sommet
40 min	2. La mozzarella qui détrempe	Problème de mélange, matrices, infaisabilité
10 min	Pause
40 min	3. Les commandes de groupe	Variables entières, relaxation, borne
30 min	4. Jusqu'où le solveur suit	Expérience, limite de temps, écart garanti
10 min	Synthèse	La recommandation de chaque binôme

Prévoir trois heures en tout, pause comprise. Chaque phase se termine par des questions d'interprétation, auxquelles on répond par écrit, en une ou deux phrases chiffrées.

L'outil : `linprog` et `milp`

Les deux solveurs viennent de scipy.optimize. Le premier bloc qui importe scipy met quelques secondes à démarrer ; la suite va vite. Un bloc qui importe scipy est interrompu au bout de vingt-cinq secondes.

Besoin	Écriture
Minimiser $c \cdot x$ sous $A x \le b$	`res = linprog(c, A_ub=A, b_ub=b)`
Ajouter des égalités $A' x = b'$	`linprog(..., A_eq=A2, b_eq=b2)`
Borner chaque variable (par défaut : de 0 à l'infini)	`linprog(..., bounds=[(0, 1)] * n)`
Savoir si un optimum existe	`res.status` : 0 si oui, 2 si aucun point ne respecte les contraintes
Lire la solution et sa valeur	`res.x`, `res.fun`
Ce qui reste sous chaque contrainte « ≤ »	`res.slack`
Ce que change `res.fun` quand le second membre d'une contrainte « ≤ » augmente d'une unité	`res.ineqlin.marginals`
Imposer des variables entières	`milp(c, constraints=LinearConstraint(A, ub=b), integrality=np.ones(n), bounds=Bounds(0, 1))`
Limiter le temps de calcul	`milp(..., options={"time_limit": 3})`, puis `res.mip_gap`

La documentation complète tient en deux pages : linprog et milp.

Phase 1 : La pizza au mètre

Le vendredi midi, Da Lambda vend la pizza au mètre aux bureaux du quartier, en deux recettes. La pâte se pétrit la veille, et le pétrin n'en donne que 12 mètres. Le vendredi matin, la chambre froide contient 14 kg de mozzarella et 6 kg de jambon ; la sauce et les champignons ne manquent jamais.

Recette, pour un mètre	Prix de vente	Pâte	Sauce	Mozzarella	Jambon	Champignons
Margherita	90 €	1 m	1 portion	1,2 kg
Regina	115 €	1 m	1 portion	1,0 kg	0,6 kg	0,5 kg

Les ingrédients coûtent : la pâte 4 € le mètre, la sauce 3 € la portion, la mozzarella 9 € le kilo, le jambon 14 € le kilo, les champignons 6 € le kilo. Tout ce qui est préparé se vend.

Une règle de la maison s'ajoute : la Margherita est la vitrine de Da Lambda, et au moins un tiers des mètres vendus doivent en être.

La demande. Combien de mètres de chaque recette préparer pour gagner le plus, et combien rapporte le vendredi ?

Écrire MARGES, la marge d'un mètre de chaque recette, puis plan_du_vendredi, qui renvoie le couple (mètres de Margherita, mètres de Regina) pour n'importe quelles marges, recettes, stocks et part minimale de Margherita.

main.py

Sortie

>_ Prêt à exécuter…

Coup de pouce 1 : la règle du tiers

Écrite telle qu'on la dit, « la Margherita fait au moins un tiers du total », la règle est un quotient : $\frac{x}{x + y} \ge \frac{1}{3}$ . Un programme linéaire n'accepte pas de quotient. Le total $x + y$ est positif : multiplier les deux côtés par lui ne change pas le sens de l'inégalité. Il reste à tout passer du même côté.

Coup de pouce 2 : maximiser avec un solveur qui minimise

linprog cherche toujours le minimum de $c \cdot x$ . Pour maximiser une marge, on minimise son opposé, puis on change le signe de res.fun pour lire la marge. Un plan rendu à (0 ; 0) est le symptôme de cet oubli.

Coup de pouce 3 : une ligne par stock

Chaque stock donne une contrainte : ce que consomment $x$ mètres de Margherita et $y$ mètres de Regina ne dépasse pas ce qu'il y a. Une recette qui n'emploie pas un ingrédient en consomme 0 : recettes["margherita"].get("jambon", 0) le dit sans lever d'erreur. La règle du tiers s'ajoute comme une ligne de plus, de second membre 0.

Correction

main.py

Sortie

>_ Prêt à exécuter…

La marge, pas le prix : une Regina se vend 25 € de plus qu'une Margherita, mais ne rapporte que 15,40 € de plus, parce que son jambon et ses champignons coûtent. Maximiser le chiffre d'affaires donnerait ici le même plan, par chance, et une valeur fausse.

La règle du tiers devient $x \ge \frac{1}{3}(x + y)$ , soit $-\frac{2}{3}x + \frac{1}{3}y \le 0$ , ou, multipliée par 3, $-2x + y \le 0$  : au plus deux mètres de Regina par mètre de Margherita. Le plan est de 4 m de Margherita et 8 m de Regina, pour 989,60 €.

À interpréter

Quels stocks le plan épuise-t-il, et lesquels laisse-t-il ? Qu'est-ce qui fixe donc le plan ?

La pâte est épuisée : 4 + 8 = 12 m. Il reste 1,2 kg de mozzarella (4 × 1,2 + 8 × 1,0 = 12,8 kg sur 14) et 1,2 kg de jambon (8 × 0,6 = 4,8 kg sur 6). La règle du tiers est atteinte tout juste : 4 m sur 12. Le plan est fixé par la pâte et la règle, et par rien d'autre. res.slack donne ces restes d'un coup : 0 ; 1,2 ; 1,2 ; 0.

Que rapporterait un mètre de pâte de plus ? Un kilo de mozzarella de plus ?

Relancer avec 13 m de pâte donne 1 072,07 €, soit 82,47 € de plus : le mètre supplémentaire se partage en un tiers de Margherita et deux tiers de Regina, pour garder la proportion, et $\frac{72{,}20}{3} + \frac{2 \times 87{,}60}{3} = 82{,}47$ . Un kilo de mozzarella de plus ne rapporte rien : il en reste déjà.

res.ineqlin.marginals donne ces nombres sans relancer, au signe près, puisque le solveur a minimisé l'opposé de la marge. C'est le prix au-delà duquel il ne vaut plus la peine d'acheter une unité de plus : payer jusqu'à 82 € un mètre de pâte supplémentaire reste rentable, un kilo de mozzarella supplémentaire ne vaut rien. Ce prix ne vaut que dans un intervalle : au-delà de 13,125 m de pâte, la mozzarella s'épuise à son tour, et un mètre de plus ne rapporte plus rien.

Combien coûte la règle du tiers ?

Sans elle (part_min à 0), le plan devient 2 m de Margherita et 10 m de Regina, pour 1 020,40 € : c'est le jambon qui arrête alors la Regina, 10 × 0,6 = 6 kg. La règle coûte 30,80 € par vendredi. Le modèle ne dit pas si la vitrine les vaut ; il dit combien elle coûte, et c'est au patron de trancher.

Vérifier sur la figure, une fois le plan trouvé

La figure dessine le même problème : le polygone des plans possibles, une droite le long de laquelle la marge est constante, et les points à coordonnées entières. Les marges se règlent aux curseurs.

Polygone des contraintesmaximiser 72 x + 88 y

Droite: 72 x + 88 y = 600 €
Point retenu: aucun

Glisser la droite orange, ou la régler au curseur. Zone grisée : interdite par une contrainte. Points pleins : points entiers réalisables. Au clavier : Tab jusqu'au tracé, flèches pour parcourir la grille, Entrée pour retenir un point, Page haut ou bas pour avancer la droite.

Marge de la droite600 €Marge par unité de x72 €Marge par unité de y88 €

Chercher le point entier le plus rentable : faire glisser la droite vers les grandes marges, puis retenir un point.

Le vendredi de Da Lambda. Zone grisée : interdite par une contrainte. Losanges : sommets du polygone.

À manipuler

Glisser la droite vers les grandes marges et noter le dernier sommet qu'elle touche. Repérer la droite du jambon : elle ne touche pas le polygone, et c'est ce que voulait dire « il en reste ». Monter ensuite la marge de la Margherita, par paliers, et noter pour quelles valeurs le sommet touché en dernier change : il y a deux seuils. Au-delà du second, demander la suite à la figure, sommet continu, arrondi, meilleur point entier, et comparer l'arrondi au meilleur point entier.

Les deux seuils sont 87,60 € et 105,12 €. Jusqu'au premier, le plan reste (4 ; 8). Quand la Margherita rapporte plus que la Regina, il passe à (10 ; 2), où la pâte et la mozzarella sont épuisées. Au-delà de 105,12 €, soit 1,2 fois la marge de la Regina, la pente de la mozzarella, le sommet continu devient (11,67 ; 0) : 11 mètres deux tiers, ce qui ne se prépare pas. L'arrondi (11 ; 0) est réalisable, mais le meilleur point entier reste (10 ; 2) tant que la Margherita rapporte moins de 175,20 €. Arrondir un sommet n'est pas résoudre en nombres entiers : la phase 3 y revient.

Phase 2 : La mozzarella qui détrempe

Les clients s'en plaignent : la pizza détrempe. Le fior di latte de Da Lambda contient 60 % d'eau, qui sort à la cuisson. Le pizzaiolo veut un mélange de fromages râpés, préparé chaque matin, et l'a décrit dans une fiche :

au plus 52 % d'eau, sinon la pâte détrempe ;
au plus 24 % de matière grasse, sinon la pizza rend de l'huile ;
au plus 24 % d'extrait sec dégraissé (les protéines, le lactose et les minéraux), sinon le fromage durcit et brunit avant que la pâte soit cuite ;
au moins 40 % de mozzarella fraîche, fior di latte ou bufala, parce que c'est le goût que les clients viennent chercher.

Six fromages sont au catalogue du fournisseur. Pour chacun, l'eau, la matière grasse et l'extrait sec dégraissé font 100 % :

Fromage	Eau	Matière grasse	Extrait sec dégraissé	Prix	Fraîche
Fior di latte	60 %	19 %	21 %	9,50 €/kg	oui
Bufala	62 %	24 %	14 %	17,00 €/kg	oui
Mozzarella sèche	48 %	22 %	30 %	7,00 €/kg	non
Provola	44 %	27 %	29 %	12,00 €/kg	non
Emmental	36 %	29 %	35 %	11,00 €/kg	non
Parmesan	30 %	28 %	42 %	22,00 €/kg	non

La composition d'un mélange est la moyenne des compositions, pondérée par les proportions : 30 % de fior di latte et 70 % de mozzarella sèche contiennent $0{,}3 \times 60 + 0{,}7 \times 48 = 51{,}6$ % d'eau.

La demande. Quel mélange respecte la fiche au moindre coût, et combien coûte le kilo ?

Écrire recette, qui renvoie un dictionnaire {fromage : proportion} pour n'importe quel catalogue, n'importe quels maxima et n'importe quelle part minimale de fraîche, et None quand aucun mélange ne tient la fiche. Les six fromages s'écrivent en une ligne de matrice chacun ou en une colonne, pas en six variables tapées à la main : le catalogue réel en compte cent.

main.py

Sortie

>_ Prêt à exécuter…

Coup de pouce 1 : ce qui manque à la fiche

Les proportions d'un mélange font 100 %. La fiche ne le dit pas, parce que c'est évident pour le pizzaiolo ; le solveur, lui, ne le sait pas. Sans cette égalité, le mélange le moins cher est le mélange vide, à 0 € le kilo.

Coup de pouce 2 : les matrices depuis le catalogue

Une ligne de A_ub par caractéristique de la fiche, une colonne par fromage : la ligne de l'eau est [fromages[f]["eau"] for f in noms], et son second membre est le maximum de l'eau. Une ligne de A_eq pour la somme des proportions. Un minimum, « au moins 40 % de fraîche », se retourne en maximum en changeant tous les signes : $-\sum \text{fraîche} \le -0{,}4$ .

Coup de pouce 3 : reconnaître une fiche impossible

Quand aucun mélange ne respecte les contraintes, linprog ne lève pas d'erreur : il renvoie un résultat dont res.status vaut 2 et dont res.x vaut None. C'est là qu'il faut rendre None.

Correction

main.py

Sortie

>_ Prêt à exécuter…

Le mélange le moins cher contient 40 % de bufala, 40 % de mozzarella sèche, 10 % de provola et 10 % d'emmental, pour 11,90 € le kilo. Ajouter un fromage au catalogue ajoute une colonne, et rien d'autre : le code ne change pas.

À interpréter

Le mélange prend la bufala, le fromage frais le plus cher, et laisse le fior di latte. Pourquoi ?

Parce que sans elle, la fiche est impossible : retirer la bufala du catalogue et relancer donne None. Tous les fromages bon marché ont trop d'extrait sec dégraissé (30 % pour la mozzarella sèche, 29 % et plus pour les autres), quand la fiche en tolère 24. Il faut les diluer, et la bufala est de loin la plus pauvre en extrait sec (14 %). Le fior di latte, à 21 %, dilue trop peu, et en le forçant à plus de 40 % on dépasse l'eau. Un ingrédient ne se juge pas à son prix, mais à ce qu'il rend possible chez les autres.

Les trois maxima de la fiche sont atteints exactement, 52, 24 et 24 %. Est-ce une coïncidence ?

Non. Pour chaque fromage, eau, matière grasse et extrait sec dégraissé font 100 % ; le mélange, moyenne pondérée, aussi. Or 52 + 24 + 24 = 100. Si l'une des trois quantités restait sous son maximum, les deux autres devraient le dépasser pour faire 100. Les trois « au plus » de la fiche sont donc trois égalités déguisées. C'est une propriété des données, pas du solveur, et elle annonce la question suivante.

Le pizzaiolo veut une pizza encore moins humide : 50 % d'eau au plus. Que répond le solveur, et que faudrait-il changer sur la fiche ?

Le solveur répond que c'est impossible (res.status vaut 2) : 50 + 24 + 24 = 98, et aucun mélange ne peut faire 100 % avec ces trois plafonds. « Impossible » est une réponse, pas une panne : elle dit que la demande se contredit. Pour baisser l'eau, il faut rendre deux points ailleurs. Avec 26 % d'extrait sec dégraissé, le mélange redevient possible, et il coûte même moins cher : 11,01 € le kilo, avec 14,6 % de fior di latte, 25,4 % de bufala, 32,4 % de mozzarella sèche et 27,6 % d'emmental.

Le fournisseur annonce 20 % de hausse sur la mozzarella sèche. Que devient le mélange ?

Elle disparaît du mélange, alors qu'elle en faisait 40 % : le nouveau mélange contient 31,3 % de fior di latte, 16,7 % de bufala et 52,1 % de provola, pour 12,05 € le kilo. Une hausse de 20 % sur un fromage ne retouche pas un peu les proportions : la solution d'un programme linéaire est un sommet, et quand les prix changent elle ne glisse pas, elle saute d'un sommet à un autre. Un fournisseur qui le sait n'augmente pas ses prix de la même façon.

Phase 3 : Les commandes de groupe

Pour le samedi soir, douze groupes ont demandé une commande : anniversaires, associations, un mariage. La pâte se pétrit le jeudi, pour quarante-huit heures de maturation, et le pétrin en donne 150 pâtons de plus que ce qu'il faut au service normal. Une commande s'honore en entier ou pas du tout : on ne livre pas la moitié d'un anniversaire.

Commande	Pizzas	Marge
Comité d'entreprise	54	500 €
Anniversaire de Léa	18	120 €
Tournoi de futsal	46	350 €
Kermesse de l'école	40	280 €
Club de rugby	51	380 €
Mariage	55	510 €
Association des commerçants	39	270 €
Anniversaire de Tom	11	80 €
Fête de quartier	44	390 €
Soirée étudiante	38	330 €
Pot de départ	14	130 €
Conseil municipal	42	290 €

Le patron a trouvé dans son tableur un module de programmation linéaire. Il y a saisi les commandes, a laissé chaque variable entre 0 et 1, et compte arrondir ce que le tableur répondra.

La demande. Le patron peut-il se fier à l'arrondi de son tableur ? Quelles commandes accepter ?

Écrire tableur, qui fait ce que fait le tableur du patron et renvoie la fraction acceptée de chaque commande, et accepter, qui renvoie l'ensemble des commandes à accepter en tout ou rien. Puis, sur les commandes du samedi, chiffrer : la marge annoncée par le tableur, celle de son arrondi par défaut, et celle de l'optimum.

main.py

Sortie

>_ Prêt à exécuter…

Coup de pouce 1 : le tableur

Une variable par commande, la fraction acceptée, bornée entre 0 et 1 par bounds. Une seule contrainte : les pizzas des commandes acceptées ne dépassent pas les pâtons. Comme toujours, on minimise l'opposé de la marge.

Coup de pouce 2 : le tout ou rien

milp prend le même vecteur de coût, la contrainte sous la forme LinearConstraint(matrice, ub=...), avec une matrice d'une seule ligne, Bounds(0, 1) pour les bornes, et integrality : un tableau qui vaut 1 pour chaque variable qui doit être entière. Une variable entière entre 0 et 1 vaut 0 ou 1.

Coup de pouce 3 : l'arrondi par défaut

L'arrondi par défaut garde les commandes que le tableur accepte en entier, à une petite tolérance près (f > 1 - 1e-6), et abandonne celle qu'il coupe.

Correction

main.py

Sortie

>_ Prêt à exécuter…

Le tableur annonce 1 379,32 €, en acceptant le comité d'entreprise, le mariage et le pot de départ, plus 61,4 % de la fête de quartier. L'arrondi par défaut abandonne la fête de quartier et tombe à 1 140 €. L'optimum vaut 1 350 € : comité d'entreprise, fête de quartier, soirée étudiante et pot de départ.

Le juge écarte les deux fausses bonnes idées. Sur ses trois commandes, l'arrondi du tableur et la règle « la meilleure marge par pizza d'abord » prennent toutes deux C seule, pour 70 €, quand A et B remplissent les dix pâtons pour 90 €.

À interpréter

Le patron peut-il se fier à l'arrondi ? Et s'il complète l'arrondi avec ce qui tient encore ?

Non. L'arrondi par défaut, 1 140 €, laisse 27 pâtons inutilisés et rapporte 15,6 % de moins que l'optimum. Le compléter, en ajoutant par meilleure marge par pizza ce qui tient encore, ajoute l'anniversaire de Tom et monte à 1 220 € : 9,6 % de moins que l'optimum, toujours. Rafistoler l'arrondi améliore le plan sans le rendre optimal, et rien, dans le résultat, ne dit combien il en reste loin.

Que vaut alors le 1 379,32 € du tableur ?

C'est une borne. Une sélection en tout ou rien est une sélection fractionnaire particulière, avec des fractions qui valent 0 ou 1 : aucune ne peut donc dépasser le meilleur des fractionnaires. L'optimum, 1 350 €, est à 2,1 % de ce plafond, et c'est la borne qui permet de l'affirmer sans avoir tout énuméré. Elle dit combien on peut espérer, pas quelles commandes prendre.

L'optimum refuse le mariage, la commande qui rapporte le plus, que le tableur prenait en entier. Pourquoi ?

Parce que la question n'est pas de prendre les meilleures commandes, mais de remplir le pétrin. 54 + 44 + 38 + 14 = 150 : l'optimum utilise les 150 pâtons, au pâton près. Avec les 55 pizzas du mariage, les combinaisons qui restent laissent des trous. La commande que le tableur coupait, la fête de quartier, est dans l'optimum ; celles qu'il prenait en entier n'y sont pas toutes. La relaxation borne l'optimum, elle ne le localise pas.

Et l'arrondi au plus proche ?

61,4 % s'arrondit à 1 : le plan prend alors la fête de quartier en plus des trois commandes entières, soit 167 pizzas pour 150 pâtons. Il n'est pas réalisable. Un arrondi ne sait pas s'il respecte les contraintes : il faut le vérifier, et il ne dit rien de l'optimum.

Phase 4 : Jusqu'où le solveur suit

Da Lambda ouvre une cuisine centrale, qui prépare les commandes de groupe de plusieurs restaurants. Chaque semaine arrivent des centaines de commandes, et chacune consomme cinq ingrédients comptés : pâtons, mozzarella, jambon, sauce et heures de four. Le patron veut une réponse en trois secondes et demande si le solveur de la phase 3 tiendra, ou s'il faut autre chose.

Le problème des commandes est NP-difficile : on ne connaît aucun algorithme qui le résolve en un temps polynomial dans tous les cas. Cela ne dit pas à partir de quand un solveur cale sur ces données-là. Pour le savoir, on mesure.

Le générateur instance(n, m, graine) fabrique une semaine de $n$ commandes et $m$ ingrédients, dont les stocks couvrent la moitié de la demande. Écrire chronometrer, qui résout une instance avec une limite de temps et renvoie trois choses : la durée en secondes, si l'optimum a été prouvé, et l'écart que garantit le solveur entre sa meilleure sélection et l'optimum, en fraction.

main.py

Sortie

>_ Prêt à exécuter…

Coup de pouce 1 : mesurer une durée

time.perf_counter() avant l'appel, puis après : la différence est la durée en secondes.

Coup de pouce 2 : prouvé ou arrêté

res.status vaut 0 quand l'optimum est prouvé, et 1 quand la limite de temps a arrêté le calcul. Dans ce second cas, res.x contient quand même la meilleure sélection trouvée, et res.mip_gap l'écart relatif entre sa marge et la meilleure borne connue. res.mip_gap peut valoir None sur un problème résolu sans recherche : l'écart est alors nul.

Correction

main.py

Sortie

>_ Prêt à exécuter…

La matrice des consommations est déjà au bon format : une ligne par ingrédient, une colonne par commande. C'est la contrainte de la phase 3, avec cinq lignes au lieu d'une.

L'expérience

Le patron veut une réponse, pas un chronométrage. Il reste à concevoir l'expérience qui la donne : quelles tailles essayer, avec combien d'ingrédients, combien de graines par taille, et quelle limite de temps. Une exécution ne dure pas plus de vingt-cinq secondes : avec trois secondes par instance, cela fait six instances par exécution au plus, et l'expérience se mène en plusieurs fois. Noter les résultats dans un tableau, au fur et à mesure.

main.py

Sortie

>_ Prêt à exécuter…

Une expérience possible, et ce qu'elle montre

main.py

Sortie

>_ Prêt à exécuter…

Sur le moteur de cette page, une exécution donne à peu près ceci. Les durées et les écarts changent d'une machine à l'autre, et même d'une exécution à l'autre, puisqu'un solveur arrêté par le temps s'arrête là où il en est ; l'allure, elle, ne change pas.

Commandes	Ingrédients	Graine	Durée	Résultat	Écart garanti
500	1	0	0,2 s	prouvé	0 %
20	5	0	moins de 1 s	prouvé	0 %
50	5	0	environ 1 s	prouvé	0 %
50	5	1	3 s	arrêté	environ 0,7 %
100	5	0	3 s	arrêté	environ 0,5 %
300	5	0	3 s	arrêté	environ 0,1 %

Avec un seul ingrédient, 500 commandes se résolvent en un instant. Avec cinq, le solveur ne prouve plus l'optimum dès 50 à 100 commandes, et deux graines de même taille ne se comportent pas pareil : à 50 commandes, l'une se prouve en une seconde, l'autre pas en trois. Mais à la limite de temps, il rend une sélection dont l'écart garanti reste sous 1 % dans ces mesures, et qui diminue quand les commandes sont plus nombreuses.

À interpréter

Qu'est-ce qui rend le problème difficile pour le solveur : le nombre de commandes, ou autre chose ?

Pas le nombre de commandes seul : avec un ingrédient, 500 commandes passent en un instant, alors qu'avec cinq ingrédients, 100 commandes ne se prouvent plus en trois secondes. La difficulté dépend de la structure de l'instance, et même de l'instance : deux graines de même taille ne demandent pas le même temps. NP-difficile ne veut pas dire lent sur toutes les instances ; cela veut dire qu'on ne connaît aucune méthode garantie rapide sur toutes.

À la limite de temps, le solveur rend une sélection et un écart de 0,5 %. Que garantit exactement ce nombre ?

Le solveur connaît deux nombres : la marge de la meilleure sélection trouvée, et une borne que l'optimum ne peut pas dépasser, obtenue par relaxation comme à la phase 3. L'écart est leur distance relative. Il garantit que l'optimum rapporte au plus 0,5 % de plus que la sélection rendue : ce n'est pas une estimation, c'est une preuve. Ce qui coûte du temps au-delà, c'est de prouver l'optimum, plus que de le trouver.

Que recommander au patron ?

Pour ce problème, le solveur exact avec une limite de trois secondes suffit : il rend une sélection à moins de 1 % garanti de l'optimum, et un écart de cet ordre ne change aucune décision de cuisine. Les méthodes approchées des chapitres suivants deviennent nécessaires quand le problème n'entre plus dans un programme linéaire de taille raisonnable, comme l'ordre de passage d'une perceuse sur des centaines de trous, ou quand il faut une réponse en quelques millisecondes. La décision ne se prend pas sur le nom du problème, mais sur une mesure, sur des données qui ressemblent aux vraies.

La méthode

Souligner la décision dans la demande. Ce que le patron choisit devient une variable, avec son unité : des mètres, une proportion, une commande prise ou non.
Écrire l'objectif en marge, pas en prix. Une recette chère à vendre peut coûter cher à faire.
Une phrase, une contrainte. Chaque stock, chaque règle de la fiche ; une proportion se multiplie par le total ; et ce qui va de soi pour le métier, comme des proportions qui font 100 %, s'écrit aussi.
Construire les matrices depuis les données. Une ligne par ressource ou caractéristique, une colonne par décision ; un minimum se retourne en changeant tous les signes ; le solveur minimise, on lui passe l'opposé d'une marge.
Vérifier le modèle sur un petit cas calculable de tête avant de le lancer sur les vraies données.
Lire la solution avant de la recopier. Le statut d'abord : « impossible » se diagnostique, il ne se contourne pas. Puis les contraintes saturées, ce qui reste, et ce que rapporterait une unité de plus.
Résoudre en entiers quand les décisions le sont. L'arrondi d'une relaxation n'est ni sûr ni optimal ; la relaxation sert de borne.
Limiter le temps quand il compte, et lire l'écart garanti : il dit à quelle distance de l'optimum on s'arrête.

Synthèse

Modéliser, c'est traduire chaque phrase de la demande en variable, en contrainte ou en objectif ; une proportion se linéarise en multipliant par le total, et l'objectif est une marge, pas un prix.
Les contraintes s'écrivent en matrices depuis les données, une ligne par ressource ou caractéristique, une colonne par décision : le code ne change pas quand le catalogue grandit.
Une solution se lit : les contraintes saturées fixent le plan, une ressource en trop ne vaut rien de plus, et une unité supplémentaire vaut son prix dual.
« Impossible » est une réponse : elle dit que la demande se contredit, et indique quoi desserrer.
Arrondir une relaxation n'est pas résoudre : l'arrondi peut perdre beaucoup ou violer une contrainte, et la relaxation sert de borne.
Un solveur exact rend, à la limite de temps, une solution et un écart garanti ; sa difficulté dépend de la structure de l'instance, et se mesure.

Et ensuite

La phase 4 a trouvé la frontière : un problème qui entre dans un programme linéaire de taille raisonnable se confie à un solveur, avec une limite de temps et un écart garanti. Au-delà, il faut construire une bonne solution sans preuve, puis l'améliorer : c'est l'objet des heuristiques constructives, et des chapitres qui les suivent. La borne de la phase 3 y garde son rôle : c'est elle qui dira à quelle distance de l'optimum une heuristique s'arrête.

Déroulé

L'outil : linprog et milp

Phase 1 : La pizza au mètre

À interpréter

Phase 2 : La mozzarella qui détrempe

À interpréter

Phase 3 : Les commandes de groupe

À interpréter

Phase 4 : Jusqu'où le solveur suit

L'expérience

À interpréter

La méthode

Synthèse

Et ensuite

L'outil : `linprog` et `milp`

Phase 1 : La pizza au mètre

Phase 2 : La mozzarella qui détrempe

Phase 3 : Les commandes de groupe

Phase 4 : Jusqu'où le solveur suit