La programmation linéaire

Le modèle linéaire

Un programme linéaire décrit une décision par trois choses. Des variables de décision, qui prennent des valeurs réelles. Un objectif, à maximiser ou à minimiser, qui est une somme de termes proportionnels aux variables : $c_1 x_1 + c_2 x_2 + \dots + c_n x_n$. Des contraintes, qui comparent chacune une somme du même type à une constante, par « ≤ », « ≥ » ou « = ». Les nombres $c_j$ et les coefficients des contraintes sont des données ; seules les variables sont à choisir.

Valdrome fabrique aussi deux références en lots, sans rapport avec les dix commandes de la semaine : des poulies, qui rapportent 520 € le lot, et des bielles, 240 € le lot. Un lot de poulies demande 5 heures de tournage et 3 heures de fraisage ; un lot de bielles, 2 heures de tournage et 2 heures de fraisage. Le tournage dispose de 15 heures, le fraisage de 12. Les variables $x$ et $y$ sont les nombres de lots de poulies et de bielles.

Ce modèle suppose trois choses, qu'il vaut mieux dire. La proportionnalité : deux lots consomment deux fois les heures d'un lot, et rapportent deux fois sa marge. L'additivité : les heures des poulies et des bielles s'ajoutent, sans gêne ni économie de l'une à l'autre. La divisibilité : un lot et demi a un sens. Quand l'une des trois tombe, le modèle n'est plus linéaire, ou plus continu.

Ce qui n'est pas linéaire

• Un produit de variables, ou une puissance. Une remise qui grandit avec la quantité vendue fait de la marge d'un lot une fonction de $x$, et la marge totale contient $x^2$.
• Un quotient. « Au moins un tiers des lots sont des poulies » s'écrit d'abord $\frac{x}{x + y} \ge \frac{1}{3}$. Le total $x + y$ est positif : multiplier les deux côtés par lui ne change pas le sens de l'inégalité, et la règle devient $3x \ge x + y$, soit $2x - y \ge 0$, qui est linéaire. Cette linéarisation se fait à la main, aucun solveur ne la fait.
• Un coût fixe. Un réglage de 300 € payé dès qu'au moins un lot de bielles est lancé ne dépend pas du nombre de lots : le coût saute de 0 à 300 quand $y$ quitte 0. Ni $300y$ ni aucune autre somme proportionnelle ne l'écrit.
• Un maximum, une valeur absolue, une condition. « Le plus long des deux temps », « l'écart à la cible, quel que soit son sens », « si l'on fait des poulies, alors on fait aussi des bielles ».

Exiger des valeurs entières n'est pas une non-linéarité, mais cela sort aussi du cadre : c'est la programmation linéaire en nombres entiers, bien plus dure, qui occupe le chapitre 4. Le chapitre 5 traite des modèles qui sortent du cadre linéaire.

Forme canonique, forme standard

Un même problème s'écrit de plusieurs façons, et chaque méthode de résolution en attend une précise. Deux formes reviennent partout.

Tout programme linéaire se ramène à l'une ou l'autre forme, par des conversions qui ne changent pas l'ensemble des plans possibles, seulement leur écriture.

Pourquoi un solveur n'accepte souvent qu'une forme. Son code ne travaille que sur l'écriture de son algorithme. Le simplexe, plus bas, raisonne sur la forme standard. La fonction linprog de scipy reçoit un problème à minimiser, des matrices de « ≤ » et d'« = », et des bornes : un problème à maximiser, ou une contrainte « ≥ », doit d'abord y être converti par celui qui l'écrit. Ces conversions sont faciles et propices aux erreurs de signe. Une bibliothèque de modélisation comme PuLP les fait elle-même, et c'est l'une de ses raisons d'être : la section Écrire un modèle avec PuLP montre les deux écritures du même modèle.

La résolution graphique

À deux variables, un programme linéaire se dessine. Le détail de la méthode graphique est traité dans le chapitre optimiser sous contraintes du parcours Mathématiques appliquées ; on ne le refait pas, on s'en sert.

Chaque contrainte est un demi-plan, et leur intersection est un polygone, le domaine réalisable. La marge $520x + 240y$ est constante sur une droite, et cette droite glisse parallèlement à elle-même quand la marge change. La figure dessine le polygone et cette droite. Les lots entiers réalisables sont les points pleins de la grille. Avant toute explication, chercher à la main le lot le plus rentable : glisser la droite vers les grandes marges, choisir un point plein, puis demander à la figure si c'est le meilleur.

L'optimum est atteint au dernier point du polygone que la droite touche en glissant vers les marges croissantes. C'est un cas d'une propriété générale, qui fonde tout ce chapitre.

Il suffit donc d'examiner les sommets. Le bloc suivant les trouve comme on le ferait à la main : il croise les bords deux à deux, contraintes et axes, garde les points qui respectent toutes les contraintes, et calcule la marge de chacun. Il énumère aussi les plans en lots entiers, peu nombreux ici.

Six paires de bords, quatre sommets : (0 ; 0), (3 ; 0), (1,5 ; 3,75) et (0 ; 6), de marges 0, 1 560, 1 680 et 1 440 €. Les deux autres croisements, où le tournage coupe l'axe des bielles et le fraisage celui des poulies, sortent du polygone. Cette méthode ne passe pas à l'échelle. À $n$ variables et $m$ contraintes, un sommet est le croisement de $n$ bords parmi $m + n$, et il y a $\binom{m+n}{n}$ choix à essayer : avec 20 variables et 20 contraintes, $\binom{40}{20} = 137\,846\,528\,820$, plus de cent milliards de systèmes à résoudre. Il faut une méthode qui n'essaie pas tout : c'est le simplexe, à la section suivante.

Le meilleur sommet est à $x = 1{,}5$ lot de poulies et $y = 3{,}75$ lots de bielles, pour 1 680 €. Un lot et demi, trois lots trois quarts : ce n'est pas une décision d'atelier. Si les lots sont indivisibles, l'optimum tombe à 1 560 €, avec 3 lots de poulies et aucun de bielles, le meilleur des 16 plans en lots entiers. Et le point entier obtenu en arrondissant le sommet continu vers le bas, 1 lot de poulies et 3 de bielles, ne rapporte que 1 240 € : arrondir n'est pas résoudre, l'optimum entier est ici dans un autre coin du polygone.

Deux leçons pour la suite. La première : le continu donne une borne (1 680 €), et le problème en nombres entiers est plus dur que son relâché continu. On sait résoudre le second pour des milliers de variables ; le premier reste difficile en général. La seconde : un solveur en nombres entiers traite directement le cas où l'on impose l'entier. PuLP le fait plus bas en un mot, et le chapitre 4 explique comment il s'y prend.

Le simplexe, de sommet en sommet

Le simplexe, mis au point par George Dantzig en 1947, part d'un sommet, ici l'origine, et passe à un sommet voisin, relié au premier par un côté du polygone, à condition que la marge y soit meilleure. Il recommence jusqu'à un sommet dont aucun voisin ne fait mieux. Ce sommet est l'optimum, parce que le polygone n'a pas de creux : il est convexe, le segment qui joint deux de ses points y reste tout entier, si bien qu'un sommet qu'aucun voisin n'améliore est le meilleur de tous. C'est ce qui sépare un programme linéaire des problèmes de la recherche locale, où un optimum local n'est que local.

La figure déroule le simplexe sur les lots. Chaque clic sur « Pivot suivant » fait un pas, et le tableau sous le dessin est celui que la suite de cette section apprend à lire.

Le tableau : variables de base et hors base

Le simplexe travaille sur la forme standard des lots, quatre variables et deux égalités :

Deux équations fixent deux inconnues : si deux des quatre variables sont mises à 0, les deux autres se calculent. À chaque sommet, les variables se partagent ainsi en deux groupes. Les variables hors base, autant que de variables de décision, valent 0. Les variables de base, une par contrainte, se calculent par les égalités. Choisir les variables hors base, c'est choisir les deux bords qui se croisent au sommet : $x = 0$ et $y = 0$ à l'origine ; $e_1 = 0$, le tournage épuisé, et $y = 0$ au sommet (3 ; 0).

À l'origine, $x$ et $y$ sont hors base, et chaque écart vaut toutes les heures de son atelier. Écrire chaque variable de base en fonction des variables hors base donne un dictionnaire, et la marge s'y écrit de même, notée $z$ :

Le tableau range les mêmes nombres : une ligne par égalité, une ligne pour la marge, une colonne par variable, et la valeur de chaque variable de base à droite.

La ligne de la marge porte, sous chaque variable, ce que rapporterait une unité de cette variable à partir du sommet courant. On l'appelle aussi la ligne des coûts réduits.

Un pivot, pas à pas

Premier pivot. À l'origine, $x$ entre, avec le plus grand coefficient, 520 € par lot. $y$ reste à 0, et les écarts valent $e_1 = 15 - 5x$ et $e_2 = 12 - 3x$. Le premier s'annule à $x = 15 / 5 = 3$, le second à $x = 12 / 3 = 4$ : les rapports sont 3 et 4, et $e_1$ sort, au plus petit. La ligne du tournage se résout en $x$, $x = 3 - \frac{2}{5}y - \frac{1}{5}e_1$, et remplace $x$ dans les deux autres :

Le plan est en (3 ; 0), pour 1 560 €. Le coefficient de $y$ n'est plus 240, mais 32 : au sommet (3 ; 0), le tournage est épuisé, et un lot de bielles de plus prend 2 heures de tournage qu'il faut retirer aux poulies, soit deux cinquièmes de lot. Il rapporte $240 - \frac{2}{5} \times 520 = 32$ €. C'est encore positif : un pivot de plus s'impose.

Second pivot. $y$ entre, seul candidat. $e_1$ reste à 0, si bien que $x = 3 - \frac{2}{5}y$ s'annulerait à $y = 7{,}5$, et $e_2 = 3 - \frac{4}{5}y$ à $y = 3{,}75$ : $e_2$ sort. Après réécriture :

Plus aucun coefficient positif : faire monter $e_1$ ou $e_2$, c'est laisser des heures inutilisées, et la marge ne peut que baisser. Le simplexe s'arrête en (1,5 ; 3,75), pour 1 680 €, après deux pivots et trois sommets visités ; le sommet (0 ; 6) ne l'a jamais été. Les deux nombres −80 et −40 resservent plus bas : ce sont, au signe près, ce que vaut une heure de plus de chaque atelier.

La règle d'entrée choisit le chemin, pas l'arrivée. Faire entrer $y$ d'abord, comme la figure le permet, mène par (0 ; 6), pour 1 440 €, puis au même sommet (1,5 ; 3,75). Quand trois bords ou plus passent par un même sommet, un rapport peut être nul : le pivot change la base sans déplacer le plan. Un tel sommet est dit dégénéré ; l'atelier en rencontre un dès son premier pivot. Les solveurs ajoutent des règles qui empêchent alors de tourner en rond.

Le bloc suivant fait les pivots en Python, sans bibliothèque, en fractions exactes : $\frac{2}{5}$ s'y affiche 2/5. Il prend le problème sous forme canonique, des marges c, une matrice A et des seconds membres b, et construit lui-même la forme standard. Il affiche chaque tableau, l'entrante, les rapports, la sortante, et le sommet atteint.

Le bloc retrouve les deux pivots et les trois tableaux de la section. Il ne dépend pas du nombre de variables. Lui donner un troisième produit, à 660 € le lot pour 5 heures de tournage et 8 de fraisage, demande une colonne de plus : c=[520, 240, 660], A=[[5, 2, 5], [3, 2, 8]] et noms=["x", "y", "w"]. Le simplexe le fait entrer d'abord, avec le plus grand coefficient, passe par deux sommets où il est fabriqué, puis l'abandonne au troisième pivot, et finit au même plan, pour la même marge. Le dernier tableau porte −60 sous lui : aux prix de 80 € l'heure de tournage et 40 € l'heure de fraisage, ses 5 et 8 heures valent $80 \times 5 + 40 \times 8 = 720$ €, plus que les 660 € qu'il rapporte.

Les points intérieurs

Le simplexe longe le bord du polygone. Une méthode de points intérieurs prend l'autre chemin : elle part d'un point à l'intérieur du domaine, et avance vers l'optimum à travers lui, en se tenant d'abord à distance des bords, puis en s'en approchant à mesure qu'elle relâche cette distance. Elle ne visite aucun sommet en route. Son nombre d'étapes croît au plus comme un polynôme de la taille du problème, depuis les travaux de Narendra Karmarkar, en 1984. Elle finit tout près du sommet optimal, et une dernière étape l'y amène exactement.

Dans la page, PuLP confie le calcul à HiGHS, un solveur libre, par la fonction linprog de scipy et sa méthode "highs". D'après la documentation de scipy, cette méthode choisit d'elle-même entre deux algorithmes de HiGHS : "highs-ds", un simplexe dual révisé, une variante du simplexe de cette section, et "highs-ipm", une méthode de points intérieurs, munie de cette étape finale qui la rend aussi précise qu'un simplexe. Le plus rapide des deux dépend du problème.

Le pire cas, et la pratique

Le simplexe est rapide sur les problèmes de la pratique, et pourtant son pire cas est exponentiel. En 1972, Victor Klee et George Minty ont construit des problèmes à $n$ variables, des cubes déformés, sur lesquels la règle du plus grand coefficient visite tous les sommets, $2^n$, en $2^n - 1$ pivots. Des exemples du même genre ont été construits depuis pour les autres règles d'entrée courantes, et l'on ne connaît aucune règle dont on ait prouvé qu'elle reste polynomiale dans tous les cas. Les problèmes de la pratique se résolvent pourtant en un nombre de pivots modeste, qui croît à peu près comme leur nombre de contraintes. Le bloc suivant compte les pivots sur les deux sortes de problèmes ; il ne démontre rien, il montre.

Sur le cube de Klee et Minty, chaque variable de plus double le nombre de pivots : 3 à deux variables, 1 023 à dix, 4 095 à douze. Sur vingt problèmes tirés au hasard à chaque taille (graine 1), le plus long n'en demande jamais plus de 7. Le pire cas existe, mais il ne se rencontre guère hors des exemples construits pour lui.

La programmation linéaire est pourtant un problème facile, au sens du chapitre 2 : sa version de décision est dans P, et l'on sait la résoudre en un temps polynomial depuis 1979, par la méthode de l'ellipsoïde de Leonid Khachiyan, lente en pratique, puis par les points intérieurs. Sa version en nombres entiers, elle, est NP-difficile. Le simplexe illustre la différence entre la complexité dans le pire cas et le comportement observé : un algorithme exponentiel dans le pire cas peut rester le plus employé.

Écrire un modèle avec PuLP

Un solveur résout ; une bibliothèque de modélisation écrit. PuLP, une bibliothèque Python, laisse écrire le modèle presque comme sur le papier, maximiser, « ≥ », une expression de chaque côté, et le traduit dans la forme que le solveur attend.

Le bloc suivant écrit les lots. Le premier bloc de la page qui importe pulp met environ deux secondes à le charger ; les suivants vont vite.

Le solveur rend le sommet (1,5 ; 3,75) et ses 1 680 €, le statut "Optimal", et pour chaque contrainte son écart et son prix, que la section suivante interprète. Avec ENTIERS = True, le même modèle exige des lots entiers, et rend (3 ; 0), pour 1 560 € : le meilleur point entier de la figure. Les prix, eux, n'ont plus de sens en nombres entiers, et se lisent sur le problème continu.

La forme brute. La fonction linprog de scipy reçoit le même problème sous la forme qu'attend le solveur : des matrices. Il faut alors faire soi-même les conversions de la forme canonique : linprog minimise, on lui passe la marge changée de signe, et l'on change le signe de ce qu'il rend.

linprog n'accepte qu'une forme : minimiser $c \cdot x$ sous $A_{ub}\,x \le b_{ub}$, $A_{eq}\,x = b_{eq}$, et des bornes. Une contrainte « ≥ » s'y écrit en changeant tous ses signes, et une égalité passe par A_eq et b_eq. C'est exactement ce que PuLP fabrique à partir du modèle écrit tel qu'on le dit : une colonne par variable, une ligne par contrainte, les signes remis dans le bon sens. Les deux écritures rendent le même plan, les mêmes écarts et les mêmes prix ; la seconde montre ce que voit le solveur, la première se relit et se modifie sans erreur de signe.

Interpréter une solution

Le plan, (1,5 ; 3,75) pour 1 680 €, n'est que la moitié de la réponse. La sortie d'un solveur dit aussi ce qui le fixe, ce qui reste, et ce que vaudrait une unité de plus de chaque ressource.

Contraintes saturées, et ce qui reste

Au plan (1,5 ; 3,75), le tournage consomme $5 \times 1{,}5 + 2 \times 3{,}75 = 15$ heures et le fraisage $3 \times 1{,}5 + 2 \times 3{,}75 = 12$ : les deux contraintes sont saturées, et leurs écarts, que PuLP donne par slack, sont nuls. Ce sont elles qui fixent le plan : un sommet, c'est un choix de contraintes saturées, celles dont l'écart a quitté la base au fil des pivots. Une contrainte non saturée laisse un reste, et ne limite rien. PuLP écrit l'écart comme le second membre moins la valeur de l'expression : il est positif pour une « ≤ » non saturée, et négatif pour une « ≥ » non saturée. Avec une commande d'au moins 5 lots en tout, $x + y \ge 5$, le plan (1,5 ; 3,75) en fait 5,25, et PuLP donne à cette contrainte un écart de −0,25.

Ce que vaut une unité de plus

Avec 16 heures de tournage, le tournage et le fraisage restent saturés, et le sommet glisse le long de la droite du fraisage, jusqu'en (2 ; 3), pour 1 760 € : 80 € de plus. C'est le −80 du dernier tableau, et le pi du tournage que PuLP affiche. Une heure de fraisage vaut de même 40 €. Si un sous-traitant propose une heure de tournage à 60 €, l'acheter laisse 20 € de gain ; à 100 €, elle coûte plus qu'elle ne rapporte. Le prix d'une ressource est le prix au-delà duquel une unité de plus ne vaut plus la peine d'être achetée.

Au signe près, le prix dit aussi ce que coûte une unité de moins. Le dernier dictionnaire le montre : $z = 1\,680 - 80\,e_1 - 40\,e_2$, et une heure de tournage laissée libre, $e_1 = 1$, coûte 80 €.

Jusqu'où le prix tient

Le prix ne vaut que tant que les mêmes contraintes restent saturées au sommet optimal. Avec $T$ heures de tournage, ce sommet est le croisement des droites du tournage et du fraisage : $x = \frac{T - 12}{2}$ et $y = \frac{60 - 3T}{4}$. Il reste dans le polygone tant que $x \ge 0$ et $y \ge 0$, c'est-à-dire pour $T$ entre 12 et 20 heures. Au-delà de 20 heures, plus aucune bielle n'est fabriquée : quatre lots de poulies épuisent le fraisage, il reste du tournage, et une heure de plus ne rapporte plus rien. C'est l'idée de l'analyse de sensibilité : chaque prix a sa plage de validité, et l'étudier dit jusqu'où une décision prise sur un prix reste bonne. Beaucoup de solveurs calculent ces plages ; à deux variables, elles se trouvent à la main, comme ici.

Les cas sans réponse

Un programme linéaire n'a pas toujours d'optimum, et le solveur le dit par son statut.

• Impossible. Aucun plan ne respecte toutes les contraintes : elles se contredisent. Un client qui exige au moins 7 lots en tout, $x + y \ge 7$, demande l'impossible : le polygone ne contient aucun plan de plus de 6 lots, au sommet (0 ; 6). PuLP répond "Infeasible", et varValue vaut None. C'est une réponse, pas une panne : la demande, telle qu'elle est écrite, ne peut pas être tenue, et c'est au métier de décider quelle contrainte desserrer.
• Non borné. L'objectif peut croître sans fin. Dans un problème réel, c'est presque toujours une contrainte oubliée, ou écrite à l'envers : les deux contraintes des lots écrites en « ≥ » laissent produire autant de lots qu'on veut. PuLP répond "Unbounded". Le simplexe le voit quand une entrante n'a aucun rapport : aucune ligne ne l'arrête, et le bloc du simplexe l'écrit.

Le statut se lit avant la solution : sur un problème impossible ou non borné, il n'y a pas de plan à lire, et un programme qui affiche x.varValue sans regarder le statut affiche None, ou plante sur un calcul qui en dépend.

Le problème de transport

Trois carrières, au nord, au centre et au sud d'un département, livrent du gravier à quatre chantiers : un pont, une gare, un lycée et un stade. Chaque carrière peut fournir au plus son tonnage de la semaine ; chaque chantier doit recevoir exactement le sien ; chaque tonne transportée coûte selon la route. Où prendre le gravier de chaque chantier pour payer le moins de transport ?

Une variable par route : $q_{ij}$, les tonnes livrées de la carrière $i$ au chantier $j$, douze variables positives. Le modèle s'écrit

où $c_{ij}$ est le coût d'une tonne sur la route, $o_i$ l'offre de la carrière et $d_j$ la demande du chantier. Les offres totalisent 320 tonnes pour 300 demandées : une carrière au moins gardera du gravier, et la contrainte d'offre est une « ≤ ». Si l'offre totale était inférieure à la demande, le problème serait impossible.

Le modèle a la même forme quelle que soit la taille : une contrainte par carrière, une par chantier, écrites en parcourant les dictionnaires, et lpSum pour les sommes. Le bloc le résout, puis le résout encore sur trente problèmes tirés au hasard (graine 1), et compte ceux dont le plan est entier.

Le plan coûte 1 160 € et emprunte six routes : le Nord livre le pont (70 t) et une partie du stade (30 t), le Centre la gare (90 t) et une partie du lycée (20 t), le Sud le reste du lycée (40 t) et du stade (50 t). Le Nord garde 20 tonnes : son offre n'est pas saturée, et son prix est nul. Les prix se lisent comme ceux des lots. Une tonne de plus livrée au stade coûterait 7 € : elle viendrait du Nord, la seule carrière qui ait du reste, par la route à 7 €. Une tonne de plus à la carrière du Centre ferait économiser 2 € : elle irait au lycée à la place d'une tonne du Sud, qui irait au stade à la place d'une tonne du Nord, soit $4 - 3 + 4 - 7 = -2$ €.

Une solution entière, sans l'avoir exigé. Les variables sont continues, et le plan est pourtant fait de tonnes entières ; sur les trente problèmes tirés au hasard, les trente plans le sont aussi. Ce n'est pas un hasard : quand les offres et les demandes sont entières, tous les sommets du polygone d'un problème de transport ont des coordonnées entières. La raison tient à la forme des contraintes, où chaque variable figure exactement deux fois, avec le coefficient 1, une fois dans l'offre de sa carrière et une fois dans la demande de son chantier ; la démonstration sort du cadre de ce chapitre. Le simplexe, qui va de sommet en sommet, rend donc un plan entier. Les lots de poulies et de bielles n'ont pas cette forme, et leur sommet optimal est (1,5 ; 3,75).

La propriété vaut aussi pour l'affectation, un transport où chaque offre et chaque demande vaut 1 : affecter des opérateurs à des postes se résout sans exiger l'entier, et le chapitre 4 le constate sur les opérateurs de Valdrome. Elle ne vaut plus dès qu'une contrainte d'une autre forme s'ajoute au modèle, une capacité de camion par exemple : il faut alors exiger l'entier.

Prendre en main le solveur

Six exercices courts, dans l'ordre : chacun ajoute une écriture de PuLP à la précédente. Les vérifications disent quel cas échoue, ce qui était attendu, et l'erreur probable quand elle est connue. Le premier exercice vérifié charge PuLP, en deux secondes environ ; les suivants vont vite.

Les erreurs d'un débutant

Exercices type

La méthode

1. Nommer les variables de décision, et dire ce que chacune compte, avec son unité.
2. Écrire l'objectif et chaque contrainte comme des sommes de termes proportionnels aux variables : une ressource limitée en « ≤ », un besoin en « ≥ », une quantité imposée en « = ». Linéariser un quotient en multipliant par le total, s'il est positif ; refuser un produit de variables.
3. Donner au solveur la forme qu'il attend : la forme standard, avec une variable d'écart par contrainte, pour le simplexe à la main ; des matrices à minimiser pour linprog ; le modèle tel qu'on le dit pour PuLP, qui fait les conversions.
4. À deux variables, chercher l'optimum parmi les sommets du polygone ; au-delà, confier le calcul au solveur, qui va de sommet en sommet ou traverse le polygone par l'intérieur.
5. Lire le statut avant la solution : « impossible » dit que la demande se contredit, « non borné » trahit presque toujours une contrainte oubliée ou écrite à l'envers.
6. Lire la solution : les contraintes saturées fixent le plan, une ressource non saturée a un prix nul, une unité de plus d'une ressource saturée vaut son prix, dans une plage qu'il faut connaître avant d'acheter.
7. Si les variables doivent être entières, ne pas arrondir : résoudre en nombres entiers, avec cat="Integer", et garder l'optimum continu comme borne. Un problème de transport aux données entières fait exception : son optimum continu est déjà entier.

Synthèse

• Un programme linéaire maximise ou minimise une somme de termes proportionnels aux variables, sous des contraintes du même type, avec des variables réelles. Un produit de variables, un quotient, un coût fixe ou une condition n'en sont pas ; un quotient d'un total positif se linéarise.
• La forme canonique maximise sous des « ≤ » ; la forme standard n'a que des égalités, avec une variable d'écart par contrainte, ce qui reste de la ressource. Une contrainte est saturée quand son écart est nul. Les conversions ne changent que l'écriture : linprog en exige une, PuLP les fait seul.
• Le domaine réalisable est un polygone, convexe, et l'optimum, s'il existe, est atteint en un sommet. Énumérer les sommets marche à deux variables, et devient impossible quand le nombre de variables grandit.
• Le simplexe va de sommet en sommet : l'entrante a un coefficient positif dans la ligne de la marge, la sortante le plus petit rapport, le pivot réécrit le tableau, et l'arrêt vient quand plus aucun coefficient n'est positif. Sur les lots : (0 ; 0), (3 ; 0), puis (1,5 ; 3,75), pour 1 680 €. La règle d'entrée change le chemin, pas l'arrivée.
• Les points intérieurs traversent le polygone et sont polynomiaux ; HiGHS choisit entre eux et un simplexe selon le problème. Le simplexe est exponentiel dans le pire cas, $2^n - 1$ pivots sur le cube de Klee et Minty, et rapide en pratique.
• Interpréter une solution, c'est lire le statut, les contraintes saturées, les écarts, et les prix duaux : 80 € l'heure de tournage, valable de 12 à 20 heures, 40 € l'heure de fraisage, de 9 à 15 heures. Un problème peut être impossible ou non borné, et le solveur le dit.
• Le problème de transport se modélise par une variable par route, une contrainte par offre et une par demande ; aux données entières, son optimum continu est entier : 1 160 € pour les carrières, en tonnes entières.
• L'optimum continu est une borne de l'optimum entier : 1 680 € pour les lots, contre 1 560 € en lots entiers. Arrondir le sommet continu ne donne pas l'optimum entier.

Et ensuite

Le chapitre suivant fait un outil de la borne que donne le continu : elle dit ce qu'une solution entière peut encore espérer, et un solveur en nombres entiers s'en sert pour résoudre exactement les petits cas, par séparation et évaluation. Le chapitre 5 sort du cadre linéaire, pour les contraintes et les coûts qui ne s'y écrivent pas.

L'atelier de programmation linéaire met ce chapitre en pratique chez Da Lambda, une pizzeria : un modèle à poser depuis une demande écrite, une proportion à linéariser, un simplexe qui commence par un sommet dégénéré, un mélange à composer, des commandes en tout ou rien. Le thème d'exercices La programmation linéaire reprend la lecture d'une solution, le calcul d'un prix, un pivot à la main, un transport et un modèle à corriger, sur d'autres situations. La méthode graphique est détaillée dans le chapitre optimiser sous contraintes du parcours Mathématiques appliquées.