Article de reference

Programmation linéaire

Voici les composants de x {\displaystyle \mathbf {x} } sont les variables à déterminer, c {\displaystyle \mathbf {c} } et b {\displaystyle \mathbf {b} } sont donnés des vecteurs...

Worldlex WikiFrancaisLecture gratuite

Voici les composants de ${\displaystyle \mathbf {x} <semantics><mrow><mstyle><mrow><mi>x</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {x} }</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {c} <semantics><mrow><mstyle><mrow><mi>c</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {c} }</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {b} <semantics><mrow><mstyle><mrow><mi>b</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {b} }</annotation></semantics></math><img src=$ ${\displaystyle A <semantics><mrow><mstyle><mi>UN</mi></mstyle></mrow><annotation>{\displaystyle A}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x} <semantics><mrow><mstyle><mrow><mi>x</mi></mrow><mo>↦</mo><msup><mrow><mi>c</mi></mrow><mrow><mrow><mi>T</mi></mrow></mrow></msup><mrow><mi>x</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x} }</annotation></semantics></math><img src=$ ${\displaystyle A\mathbf {x} \leq \mathbf {b} <semantics><mrow><mstyle><mi>UN</mi><mrow><mi>x</mi></mrow><mo>≤</mo><mrow><mi>b</mi></mrow></mstyle></mrow><annotation>{ displaystyle A mathbf {x} leq mathbf {b}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {x} \geq \mathbf {0} <semantics><mrow><mstyle><mrow><mi>x</mi></mrow><mo>≥</mo><mrow><mn>0</mn></mrow></mstyle></mrow><annotation>{ displaystyle mathbf {x} geq mathbf {0}}</annotation></semantics></math><img src=$

La programmation linéaire trouve des applications dans divers domaines d'études. Elle est largement utilisée en mathématiques et, dans une moindre mesure, en gestion, en économie et dans certains domaines de l'ingénierie. Il existe un lien étroit entre les programmes linéaires, les équations aux valeurs propres, le modèle d'équilibre général de John von Neumann et les modèles d'équilibre structurel (voir la programmation linéaire dual pour plus de détails). Parmi les secteurs qui utilisent des modèles de programmation linéaire, on peut citer les transports, l'énergie, les télécommunications et l'industrie manufacturière. Elle s'est avérée utile pour modéliser différents types de problèmes de planification , d'acheminement , d'ordonnancement , d'affectation et de conception.

Histoire

Le problème de la résolution d'un système d'inégalités linéaires remonte au moins à Fourier , qui publia en 1827 une méthode pour les résoudre, et dont la méthode d' élimination de Fourier-Motzkin tire son nom.

À la fin des années 1930, le mathématicien soviétique Leonid Kantorovich et l'économiste américain Wassily Leontief ont exploré indépendamment les applications pratiques de la programmation linéaire. Kantorovich s'est concentré sur les plannings de production, tandis que Leontief a étudié ses applications économiques. Leurs travaux novateurs sont restés largement méconnus pendant des décennies.

Le tournant décisif s'est produit pendant la Seconde Guerre mondiale, lorsque la programmation linéaire s'est imposée comme un outil essentiel. Elle a été largement utilisée pour relever les défis complexes du temps de guerre, notamment en matière de logistique des transports, de planification et d'allocation des ressources. La programmation linéaire s'est révélée inestimable pour optimiser ces processus tout en tenant compte de contraintes critiques telles que les coûts et la disponibilité des ressources.

Malgré son caractère initialement confidentiel, les succès obtenus pendant la guerre ont propulsé la programmation linéaire sur le devant de la scène. Après la Seconde Guerre mondiale, la méthode a acquis une large reconnaissance et est devenue une pierre angulaire dans divers domaines, de la recherche opérationnelle à l'économie. Les contributions méconnues de Kantorovich et Leontief à la fin des années 1930 ont finalement joué un rôle fondamental dans l'acceptation et l'utilisation plus larges de la programmation linéaire pour l'optimisation des processus de décision.

Les travaux de Kantorovich furent initialement négligés en URSS . À peu près à la même époque, l'économiste néerlando-américain T.C. Koopmans formula les problèmes économiques classiques sous forme de programmes linéaires. Kantorovich et Koopmans partagèrent plus tard le prix Nobel d'économie en 1975. En 1941, Frank Lauren Hitchcock formula également les problèmes de transport sous forme de programmes linéaires et proposa une solution très proche de la méthode du simplexe ultérieure . Hitchcock étant décédé en 1957, le prix Nobel d'économie n'est pas décerné à titre posthume.

De 1946 à 1947, George B. Dantzig développa indépendamment une formulation générale de programmation linéaire destinée à la résolution de problèmes de planification au sein de l'US Air Force. En 1947, il inventa également la méthode du simplexe qui, pour la première fois, permettait de résoudre efficacement le problème de la programmation linéaire dans la plupart des cas. Lors d'une rencontre entre Dantzig et John von Neumann pour discuter de sa méthode du simplexe, von Neumann conjectura immédiatement la théorie de la dualité en réalisant l' équivalence du problème sur lequel il travaillait en théorie des jeux . Dantzig en apporta la preuve formelle dans un rapport inédit intitulé « Un théorème sur les inégalités linéaires », daté du 5 janvier 1948. Ses travaux furent rendus publics en 1951. Après la guerre, de nombreuses industries les appliquèrent à leur planification quotidienne.

L'exemple initial de Dantzig consistait à trouver la meilleure affectation de 70 personnes à 70 postes. La puissance de calcul nécessaire pour tester toutes les permutations et sélectionner la meilleure affectation est immense ; le nombre de configurations possibles dépasse le nombre de particules dans l' univers observable . Cependant, il suffit d'un instant pour trouver la solution optimale en formulant le problème comme un programme linéaire et en appliquant l' algorithme du simplexe . La théorie sous-jacente à la programmation linéaire réduit considérablement le nombre de solutions possibles à vérifier.

Le problème de programmation linéaire a été démontré pour la première fois comme étant résoluble en temps polynomial par Leonid Khachiyan en 1979, mais une percée théorique et pratique plus importante dans le domaine est survenue en 1984 lorsque Narendra Karmarkar a introduit une nouvelle méthode de points intérieurs pour résoudre les problèmes de programmation linéaire.

Utilisations

La programmation linéaire est un domaine d'optimisation largement utilisé pour plusieurs raisons. De nombreux problèmes pratiques en recherche opérationnelle peuvent être formulés comme des problèmes de programmation linéaire. Certains cas particuliers de programmation linéaire, tels que les problèmes de flot de réseaux et les problèmes de flot de produits multiples , sont considérés comme suffisamment importants pour justifier de nombreuses recherches sur des algorithmes spécialisés. Un certain nombre d'algorithmes pour d'autres types de problèmes d'optimisation fonctionnent en résolvant des problèmes de programmation linéaire comme sous-problèmes. Historiquement, les idées issues de la programmation linéaire ont inspiré de nombreux concepts centraux de la théorie de l'optimisation, tels que la dualité, la décomposition et l'importance de la convexité et de ses généralisations. De même, la programmation linéaire a été largement utilisée lors des débuts de la microéconomie et elle est actuellement employée dans la gestion d'entreprise, notamment pour la planification, la production, le transport et la technologie. Bien que les problématiques de gestion modernes soient en constante évolution, la plupart des entreprises cherchent à maximiser leurs profits et à minimiser leurs coûts avec des ressources limitées. Google utilise également la programmation linéaire pour stabiliser les vidéos YouTube.

Forme standard

La forme standard est la forme habituelle et la plus intuitive pour décrire un problème de programmation linéaire. Elle se compose des trois parties suivantes :

Une fonction linéaire (ou affine) à maximiser

par exemple

{\displaystyle f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2 <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub><mo>)</mo><mo>=</mo><msub><mi>c</mi><mrow><mn>1</mn></mrow></msub><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>c</mi><mrow><mn>2</mn></mrow></msub><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}}</annotation></semantics></math></span><img src=

Les contraintes du problème sont de la forme suivante

par exemple

{\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msub><mi>un</mi><mrow><mn>11</mn></mrow></msub><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>un</mi><mrow><mn>12</mn></mrow></msub><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub></mtd><mtd><mo>≤</mo><msub><mi>b</mi><mrow><mn>1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>un</mi><mrow><mn>21</mn></mrow></msub><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>un</mi><mrow><mn>22</mn></mrow></msub><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub></mtd><mtd><mo>≤</mo><msub><mi>b</mi><mrow><mn>2</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>un</mi><mrow><mn>31</mn></mrow></msub><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>un</mi><mrow><mn>32</mn></mrow></msub><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub></mtd><mtd><mo>≤</mo><msub><mi>b</mi><mrow><mn>3</mn></mrow></msub></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}}</annotation></semantics></math></span><img src=

Variables non négatives

par exemple

{\displaystyle {\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><mo>≥</mo><mn>0</mn></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub><mo>≥</mo><mn>0</mn></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}}</annotation></semantics></math></span><img src=

Le problème est généralement exprimé sous forme matricielle , et devient alors :

{\displaystyle \max\{\,\mathbf {c} ^{\mathsf {T}}\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\ <semantics><mrow><mstyle><mo>max</mo><mo>{</mo><mspace></mspace><msup><mrow><mi>c</mi></mrow><mrow><mrow><mi>T</mi></mrow></mrow></msup><mrow><mi>x</mi></mrow><mo>∣</mo><mrow><mi>x</mi></mrow><mo>∈</mo><msup><mrow><mi>R</mi></mrow><mrow><mi>n</mi></mrow></msup><mo>∧</mo><mi>UN</mi><mrow><mi>x</mi></mrow><mo>≤</mo><mrow><mi>b</mi></mrow><mo>∧</mo><mrow><mi>x</mi></mrow><mo>≥</mo><mn>0</mn><mspace></mspace><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \max\{\,\mathbf {c} ^{\mathsf {T}}\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}}</annotation></semantics></math></span><img src=

D'autres formes, telles que les problèmes de minimisation, les problèmes avec contraintes sur des formes alternatives et les problèmes impliquant des variables négatives , peuvent toujours être réécrites sous la forme d'un problème équivalent sous forme standard.

Exemple

Supposons qu'un agriculteur possède une parcelle de terre, disons L hectares , qu'il doit cultiver en blé, en orge ou en une combinaison des deux. Il dispose de _Fkilogrammes d'engrais et _deP kilogrammes de pesticide. Chaque hectare de blé nécessite F₁ _kilogrammes d'engrais et P₁ kilogrammes de pesticide, tandis que chaque hectare d'orge nécessite F₂ _kilogrammes d'engrais et P₂ kilogrammes de pesticide. Soient S₁ _et_S₂ les prix de vente du blé et de l'orge par hectare. Si l'on note x₁ et x₂ respectivement les surfaces cultivées en blé et en orge _, le profit peut être maximisé en choisissant les valeurs optimales de x₁ et _x₂_. Ce problème peut être formulé comme le problème de programmation linéaire suivant, sous sa forme standard_:

Sous forme matricielle, cela devient :

maximiser

{\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix <semantics><mrow><mstyle><mrow><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>S</mi><mrow><mn>1</mn></mrow></msub></mtd><mtd><msub><mi>S</mi><mrow><mn>2</mn></mrow></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mrow><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}</annotation></semantics></math></span><img src=

sous réserve de

{\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}. <semantics><mrow><mstyle><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><msub><mi>F</mi><mrow><mn>1</mn></mrow></msub></mtd><mtd><msub><mi>F</mi><mrow><mn>2</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub></mtd><mtd><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mrow><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>≤</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>L</mi></mtd></mtr><mtr><mtd><mi>F</mi></mtd></mtr><mtr><mtd><mi>P</mi></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>,</mo><mspace></mspace><mrow><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>≥</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.}</annotation></semantics></math></span><img src=

Forme augmentée (forme relâchée)

Les problèmes de programmation linéaire peuvent être convertis en une forme augmentée afin d'appliquer la forme classique de l' algorithme du simplexe . Cette forme introduit des variables d'écart non négatives pour remplacer les inégalités par des égalités dans les contraintes. Les problèmes peuvent alors s'écrire sous la forme matricielle par blocs suivante :

Maximiser

{\displaystyle z <semantics><mrow><mstyle><mi>z</mi></mstyle></mrow><annotation>{\displaystyle z}</annotation></semantics></math></span><img src=

{\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{\mathsf {T}}&\mathbf {0} ^{\mathsf {T}}\\\mathbf {0} &\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix <semantics><mrow><mstyle><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mo>−</mo><msup><mrow><mi>c</mi></mrow><mrow><mrow><mi>T</mi></mrow></mrow></msup></mtd><mtd><msup><mrow><mn>0</mn></mrow><mrow><mrow><mi>T</mi></mrow></mrow></msup></mtd></mtr><mtr><mtd><mrow><mn>0</mn></mrow></mtd><mtd><mrow><mi>UN</mi></mrow></mtd><mtd><mrow><mi>je</mi></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>z</mi></mtd></mtr><mtr><mtd><mrow><mi>x</mi></mrow></mtd></mtr><mtr><mtd><mrow><mi>s</mi></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>=</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mrow><mi>b</mi></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{\mathsf {T}}&\mathbf {0} ^{\mathsf {T}}\\\mathbf {0} &\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}}</annotation></semantics></math></span><img src=

{\displaystyle \mathbf {x} \geq \mathbf {0} ,\mathbf {s} \geq \mathbf {0} <semantics><mrow><mstyle><mrow><mi>x</mi></mrow><mo>≥</mo><mrow><mn>0</mn></mrow><mo>,</mo><mrow><mi>s</mi></mrow><mo>≥</mo><mrow><mn>0</mn></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {x} \geq \mathbf {0} ,\mathbf {s} \geq \mathbf {0} }</annotation></semantics></math></span><img src=

où ${\displaystyle \mathbf {s} <semantics><mrow><mstyle><mrow><mi>s</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {s} }</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {x} <semantics><mrow><mstyle><mrow><mi>x</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {x} }</annotation></semantics></math><img src=$ ${\displaystyle z <semantics><mrow><mstyle><mi>z</mi></mstyle></mrow><annotation>{\displaystyle z}</annotation></semantics></math><img src=$

Exemple

L'exemple ci-dessus est converti en la forme augmentée suivante :

où ${\displaystyle x_{3},x_{4},x_{5 <semantics><mrow><mstyle><msub><mi>x</mi><mrow><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>x</mi><mrow><mn>4</mn></mrow></msub><mo>,</mo><msub><mi>x</mi><mrow><mn>5</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle x_{3},x_{4},x_{5}}</annotation></semantics></math><img src=$

Sous forme matricielle, cela devient :

Maximiser

{\displaystyle z <semantics><mrow><mstyle><mi>z</mi></mstyle></mrow><annotation>{\displaystyle z}</annotation></semantics></math></span><img src=

{\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0. <semantics><mrow><mstyle><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mo>−</mo><msub><mi>S</mi><mrow><mn>1</mn></mrow></msub></mtd><mtd><mo>−</mo><msub><mi>S</mi><mrow><mn>2</mn></mrow></msub></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><msub><mi>F</mi><mrow><mn>1</mn></mrow></msub></mtd><mtd><msub><mi>F</mi><mrow><mn>2</mn></mrow></msub></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub></mtd><mtd><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>z</mi></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>3</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>4</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>5</mn></mrow></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>=</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mi>L</mi></mtd></mtr><mtr><mtd><mi>F</mi></mtd></mtr><mtr><mtd><mi>P</mi></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>,</mo><mspace></mspace><mrow><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>3</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>4</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>x</mi><mrow><mn>5</mn></mrow></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>≥</mo><mn>0.</mn></mstyle></mrow><annotation>{\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0.}</annotation></semantics></math></span><img src=

Dualité

{\displaystyle \mathbf {y} </span referrerpolicy=

Ces coefficients peuvent être interprétés comme des coefficients dans une combinaison linéaire d'inégalités issues du problème primal, construite dans l'espoir d'obtenir une borne pour la fonction objectif. Ces coefficients doivent être non négatifs, car sinon les inégalités seraient inversées, d'où l'exigence de…

{\displaystyle \mathbf {y} \geq \mathbf {0} <semantics><mrow><mstyle><mrow><mi>y</mi></mrow><mo>≥</mo><mrow><mn>0</mn></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {y} \geq \mathbf {0} }</annotation></semantics></math></span><img src=

{\displaystyle \mathbf {c} ^{ op }\leq \mathbf {y} ^{ op }\!A <semantics><mrow><mstyle><msup><mrow><mi>c</mi></mrow><mrow><mi>⊤</mi></mrow></msup><mo>≤</mo><msup><mrow><mi>y</mi></mrow><mrow><mi>⊤</mi></mrow></msup><mspace></mspace><mi>UN</mi></mstyle></mrow><annotation>{\displaystyle \mathbf {c} ^{ op }\leq \mathbf {y} ^{ op }\!A}</annotation></semantics></math></span><img src=

{\displaystyle \mathbf {c} ^{ op }\mathbf {x} \leq \mathbf {y} ^{ op }\!A\mathbf {x} \leq \mathbf {y} ^{ op }\mathbf {b} =\mathbf {b} ^{ op }\mathbf {y} { ext{, <semantics><mrow><mstyle><msup><mrow><mi>c</mi></mrow><mrow><mi>⊤</mi></mrow></msup><mrow><mi>x</mi></mrow><mo>≤</mo><msup><mrow><mi>y</mi></mrow><mrow><mi>⊤</mi></mrow></msup><mspace></mspace><mi>UN</mi><mrow><mi>x</mi></mrow><mo>≤</mo><msup><mrow><mi>y</mi></mrow><mrow><mi>⊤</mi></mrow></msup><mrow><mi>b</mi></mrow><mo>=</mo><msup><mrow><mi>b</mi></mrow><mrow><mi>⊤</mi></mrow></msup><mrow><mi>y</mi></mrow><mrow><mtext>,</mtext></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {c} ^{ op }\mathbf {x} \leq \mathbf {y} ^{ op }\!A\mathbf {x} \leq \mathbf {y} ^{ op }\mathbf {b} =\mathbf {b} ^{ op }\mathbf {y} { ext{,}}}</annotation></semantics></math></span><img src=

{\displaystyle \mathbf {b} ^{ op }\mathbf {y} <semantics><mrow><mstyle><msup><mrow><mi>b</mi></mrow><mrow><mi>⊤</mi></mrow></msup><mrow><mi>y</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {b} ^{ op }\mathbf {y} }</annotation></semantics></math></span><img src=

{\displaystyle \mathbf {y} <semantics><mrow><mstyle><mrow><mi>y</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {y} }</annotation></semantics></math></span><img src=

{\displaystyle \mathbf {c} ^{ op }\mathbf {x} <semantics><mrow><mstyle><msup><mrow><mi>c</mi></mrow><mrow><mi>⊤</mi></mrow></msup><mrow><mi>x</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {c} ^{ op }\mathbf {x} }</annotation></semantics></math></span><img src=

{\displaystyle \mathbf {x} <semantics><mrow><mstyle><mrow><mi>x</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {x} }</annotation></semantics></math></span><img src=

x ^* , alors le dual a également une solution optimale, y ^* , et c ^Tx ^* = b ^Ty ^* .

Un programme linéaire peut être non borné ou irréalisable. La théorie de la dualité nous apprend que si le programme primal est non borné, alors le programme dual est irréalisable, d'après le théorème de dualité faible. De même, si le programme dual est non borné, alors le programme primal est nécessairement irréalisable. Cependant, il est possible que le programme dual et le programme primal soient tous deux irréalisables. Voir la section sur les programmes linéaires duaux pour plus de détails et d'exemples supplémentaires.

Dualités de couverture/emballage

= ( x₁ _,x₂ _, ... , xₙ ) soit primal réalisable et que y = ( y₁ , y₂ _, ... _,yₘ ) soit duallement réalisable. Soient ( w₁ , _w₂, _... , wₘ ) les variables d' _écart primales correspondantes et ( z₁ , z₂ _, ... _, zₙ ₎_les variables d'écart duales correspondantes. Alors x et y sont optimaux pour leurs problèmes respectifs si et seulement _si

x _j z _j = 0, pour j = 1, 2, ... , n , et
w _i y _i = 0, pour i = 1, 2, ... , m .

Ainsi, si la i -ème variable d'écart du problème primal est non nulle, alors la i -ème variable du problème dual est nulle. De même, si la j -ème variable d'écart du problème dual est non nulle, alors la j -ème variable du problème primal est nulle.

Cette condition nécessaire d'optimalité repose sur un principe économique relativement simple. Sous sa forme standard (en cas de maximisation), s'il existe une marge de manœuvre concernant une ressource primaire contrainte (c'est-à-dire des « excédents »), alors des quantités supplémentaires de cette ressource sont inutiles. De même, s'il existe une marge de manœuvre concernant la contrainte de non-négativité du prix (ou contrainte implicite), c'est-à-dire si le prix n'est pas nul, alors l'offre est nécessairement limitée (absence d'« excédents »).

Théorie

Existence de solutions optimales

Géométriquement, les contraintes linéaires définissent la région admissible , qui est un polytope convexe . Une fonction linéaire est une fonction convexe , ce qui implique que tout minimum local est un minimum global ; de même, une fonction linéaire est une fonction concave , ce qui implique que tout maximum local est un maximum global .

Il n'existe pas nécessairement de solution optimale, et ce pour deux raisons. Premièrement, si les contraintes sont incompatibles, aucune solution réalisable n'est possible : par exemple, les contraintes x ≥ 2 et x ≤ 1 ne peuvent être satisfaites simultanément ; dans ce cas, on dit que le programme linéaire est infaisable . Deuxièmement, lorsque le polytope est non borné dans la direction du gradient de la fonction objectif (où le gradient de la fonction objectif est le vecteur des coefficients de cette fonction), aucune valeur optimale n'est atteinte, car il est toujours possible de faire mieux que toute valeur finie de la fonction objectif.

Sommets (et rayons) optimaux des polyèdres

Autrement, si une solution réalisable existe et si l'ensemble des contraintes est borné, la valeur optimale est toujours atteinte sur la frontière de cet ensemble, d'après le principe du maximum pour les fonctions convexes (ou, alternativement, d'après le principe du minimum pour les fonctions concaves ), puisque les fonctions linéaires sont à la fois convexes et concaves. Cependant, certains problèmes admettent des solutions optimales distinctes ; par exemple, le problème de la recherche d'une solution réalisable à un système d'inégalités linéaires est un problème de programmation linéaire dont la fonction objectif est la fonction nulle (c'est-à-dire la fonction constante qui prend la valeur zéro partout). Pour ce problème de faisabilité avec la fonction nulle comme fonction objectif, s'il existe deux solutions distinctes, alors toute combinaison convexe de ces solutions est une solution.

The vertices of the polytope are also called basic feasible solutions. The reason for this choice of name is as follows. Let d denote the number of variables. Then the fundamental theorem of linear inequalities implies (for feasible problems) that for every vertex x^* of the LP feasible region, there exists a set of d (or fewer) inequality constraints from the LP such that, when we treat those d constraints as equalities, the unique solution is x^*. Thereby we can study these vertices by means of looking at certain subsets of the set of all constraints (a discrete set), rather than the continuum of LP solutions. This principle underlies the simplex algorithm for solving linear programs.

Algorithms

2^D corners of a (perturbed) cube in dimensionD, the Klee–Minty cube, in the worst case.

Ellipsoid algorithm, following Khachiyan

{\displaystyle O(n^{6}L) </span referrerpolicy=

time.Leonid Khachiyan solved this long-standing complexity issue in 1979 with the introduction of the ellipsoid method. The convergence analysis has (real-number) predecessors, notably the iterative methods developed by Naum Z. Shor and the approximation algorithms by Arkadi Nemirovski and D. Yudin.

The problem natively solved by the ellipsoid method is not a linear program ‘maximize ${\displaystyle \mathbf {c} ^{ op }\mathbf {x} <semantics><mrow><mstyle><msup><mrow><mi>c</mi></mrow><mrow><mi>⊤</mi></mrow></msup><mrow><mi>x</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {c} ^{ op }\mathbf {x} }</annotation></semantics></math><img src=$ ${\displaystyle A\mathbf {x} \leq \mathbf {b} ,\mathbf {x} \geq \mathbf {0} <semantics><mrow><mstyle><mi>A</mi><mrow><mi>x</mi></mrow><mo>≤</mo><mrow><mi>b</mi></mrow><mo>,</mo><mrow><mi>x</mi></mrow><mo>≥</mo><mrow><mn>0</mn></mrow></mstyle></mrow><annotation>{\displaystyle A\mathbf {x} \leq \mathbf {b} ,\mathbf {x} \geq \mathbf {0} }</annotation></semantics></math><img src=$ ${\displaystyle A\mathbf {x} \leq \mathbf {b} <semantics><mrow><mstyle><mi>A</mi><mrow><mi>x</mi></mrow><mo>≤</mo><mrow><mi>b</mi></mrow></mstyle></mrow><annotation>{\displaystyle A\mathbf {x} \leq \mathbf {b} }</annotation></semantics></math><img src=$ ${\displaystyle A\mathbf {x} \leq \mathbf {b} ,\mathbf {x} \geq \mathbf {0} <semantics><mrow><mstyle><mi>A</mi><mrow><mi>x</mi></mrow><mo>≤</mo><mrow><mi>b</mi></mrow><mo>,</mo><mrow><mi>x</mi></mrow><mo>≥</mo><mrow><mn>0</mn></mrow></mstyle></mrow><annotation>{\displaystyle A\mathbf {x} \leq \mathbf {b} ,\mathbf {x} \geq \mathbf {0} }</annotation></semantics></math><img src=$ ${\displaystyle A^{ op }\mathbf {y} \geq \mathbf {c} ,\mathbf {y} \geq \mathbf {0} <semantics><mrow><mstyle><msup><mi>A</mi><mrow><mi>⊤</mi></mrow></msup><mrow><mi>y</mi></mrow><mo>≥</mo><mrow><mi>c</mi></mrow><mo>,</mo><mrow><mi>y</mi></mrow><mo>≥</mo><mrow><mn>0</mn></mrow></mstyle></mrow><annotation>{\displaystyle A^{ op }\mathbf {y} \geq \mathbf {c} ,\mathbf {y} \geq \mathbf {0} }</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {x} \geq \mathbf {0} ,\mathbf {y} \geq \mathbf {0} ,A\mathbf {x} \leq \mathbf {b} ,A^{ op }\mathbf {y} \geq \mathbf {c} ,\mathbf {c} ^{ op }\mathbf {x} =\mathbf {b} ^{ op }\mathbf {y} <semantics><mrow><mstyle><mrow><mi>x</mi></mrow><mo>≥</mo><mrow><mn>0</mn></mrow><mo>,</mo><mrow><mi>y</mi></mrow><mo>≥</mo><mrow><mn>0</mn></mrow><mo>,</mo><mi>A</mi><mrow><mi>x</mi></mrow><mo>≤</mo><mrow><mi>b</mi></mrow><mo>,</mo><msup><mi>A</mi><mrow><mi>⊤</mi></mrow></msup><mrow><mi>y</mi></mrow><mo>≥</mo><mrow><mi>c</mi></mrow><mo>,</mo><msup><mrow><mi>c</mi></mrow><mrow><mi>⊤</mi></mrow></msup><mrow><mi>x</mi></mrow><mo>=</mo><msup><mrow><mi>b</mi></mrow><mrow><mi>⊤</mi></mrow></msup><mrow><mi>y</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {x} \geq \mathbf {0} ,\mathbf {y} \geq \mathbf {0} ,A\mathbf {x} \leq \mathbf {b} ,A^{ op }\mathbf {y} \geq \mathbf {c} ,\mathbf {c} ^{ op }\mathbf {x} =\mathbf {b} ^{ op }\mathbf {y} }</annotation></semantics></math><img src=$

L'idée de la méthode des ellipsoïdes est d'encadrer la région admissible par une séquence d' ellipsoïdes de volume décroissant. À chaque itération, on vérifie si le milieu de chaque ellipsoïde est admissible ; si c'est le cas, la réponse est « oui ». Sinon, on constate que la région admissible est contenue dans une moitié spécifique de l'ellipsoïde, on trouve alors un ellipsoïde plus petit qui ne contient que cette moitié, et on répète l'opération. Dans l'algorithme de Khachiyan, on connaît une borne inférieure du volume d'une région admissible non vide , ce qui se traduit par une borne supérieure polynomiale du nombre d'itérations nécessaires avant de conclure à une incapacité. Les ellipsoïdes ne sont pas inclus les uns dans les autres ; seul leur volume diminue.

Point intérieur

L'algorithme de Khachiyan a joué un rôle déterminant dans l'établissement de la résolution en temps polynomial des programmes linéaires. Bien qu'il ne constitue pas une avancée majeure en termes de calcul, la méthode du simplexe étant plus efficace pour tous les programmes linéaires, à l'exception de familles spécialement conçues, l'algorithme de Khachiyan a néanmoins ouvert de nouvelles perspectives de recherche en programmation linéaire.

Contrairement à l'algorithme du simplexe, qui trouve une solution optimale en parcourant les arêtes entre les sommets d'un ensemble polyédrique, les méthodes de points intérieurs se déplacent à l'intérieur de la région admissible.

Algorithme projectif de Karmarkar

{\displaystyle O(n^{3,5}L) </span referrerpolicy=

Karmarkar affirmait que son algorithme était beaucoup plus rapide que la méthode du simplexe pour la programmation linéaire pratique, une affirmation qui a suscité un grand intérêt pour les méthodes de points intérieurs. Depuis la découverte de Karmarkar, de nombreuses méthodes de points intérieurs ont été proposées et analysées.

L'algorithme 87 de Vaidya

En 1987, Vaidya a proposé un algorithme qui s'exécute dans ${\displaystyle O(n^{3}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>3</mn></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{3})}</annotation></semantics></math><img src=$

L'algorithme 89 de Vaidya

En 1989, Vaidya a développé un algorithme qui fonctionne en ${\displaystyle O(n^{2.5}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>2.5</mn></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{2.5})}</annotation></semantics></math><img src=$ ${\displaystyle O((n+d)^{1.5}nL) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mo>(</mo><mi>n</mi><mo>+</mo><mi>d</mi><msup><mo>)</mo><mrow><mn>1.5</mn></mrow></msup><mi>n</mi><mi>L</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O((n+d)^{1.5}nL)}</annotation></semantics></math><img src=$ ${\displaystyle d <semantics><mrow><mstyle><mi>d</mi></mstyle></mrow><annotation>{\displaystyle d}</annotation></semantics></math><img src=$ ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle L <semantics><mrow><mstyle><mi>L</mi></mstyle></mrow><annotation>{\displaystyle L}</annotation></semantics></math><img src=$

algorithmes de temps de parcimonie des entrées

En 2015, Lee et Sidford ont montré que la programmation linéaire peut être résolue dans ${\displaystyle { ilde {O}}{\bigl (}(\mathrm {nnz} (A)+d^{2}){\sqrt {d}}L{\bigr ) <semantics><mrow><mstyle><mrow><mrow><mover><mi>O</mi><mo>~</mo></mover></mrow></mrow><mrow><mrow><mo>(</mo></mrow></mrow><mo>(</mo><mrow><mi>n</mi><mi>n</mi><mi>z</mi></mrow><mo>(</mo><mi>UN</mi><mo>)</mo><mo>+</mo><msup><mi>d</mi><mrow><mn>2</mn></mrow></msup><mo>)</mo><mrow><msqrt><mi>d</mi></msqrt></mrow><mi>L</mi><mrow><mrow><mo>)</mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle { ilde {O}}{\bigl (}(\mathrm {nnz} (A)+d^{2}){\sqrt {d}}L{\bigr )}}</annotation></semantics></math><img src=$ ${\displaystyle { ilde {O <semantics><mrow><mstyle><mrow><mrow><mover><mi>O</mi><mo>~</mo></mover></mrow></mrow></mstyle></mrow><annotation>{\displaystyle { ilde {O}}}</annotation></semantics></math><img src=$ ${\displaystyle \mathrm {nnz} (A) <semantics><mrow><mstyle><mrow><mi>n</mi><mi>n</mi><mi>z</mi></mrow><mo>(</mo><mi>UN</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \mathrm {nnz} (A)}</annotation></semantics></math><img src=$ ${\displaystyle O(n^{2.5}L) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>2.5</mn></mrow></msup><mi>L</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{2.5}L)}</annotation></semantics></math><img src=$

Algorithme actuel de multiplication matricielle

En 2019, Cohen, Lee et Song ont amélioré le temps d'exécution à ${\displaystyle { ilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L) <semantics><mrow><mstyle><mrow><mrow><mover><mi>O</mi><mo>~</mo></mover></mrow></mrow><mo>(</mo><mo>(</mo><msup><mi>n</mi><mrow><mi>ω</mi></mrow></msup><mo>+</mo><msup><mi>n</mi><mrow><mn>2.5</mn><mo>−</mo><mi>α</mi><mrow><mo>/</mo></mrow><mn>2</mn></mrow></msup><mo>+</mo><msup><mi>n</mi><mrow><mn>2</mn><mo>+</mo><mn>1</mn><mrow><mo>/</mo></mrow><mn>6</mn></mrow></msup><mo>)</mo><mi>L</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle { ilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)}</annotation></semantics></math><img src=$ ${\displaystyle \omega <semantics><mrow><mstyle><mi>ω</mi></mstyle></mrow><annotation>{\displaystyle \omega }</annotation></semantics></math><img src=$ ${\displaystyle \alpha <semantics><mrow><mstyle><mi>α</mi></mstyle></mrow><annotation>{\displaystyle \alpha }</annotation></semantics></math><img src=$ ${\displaystyle \alpha <semantics><mrow><mstyle><mi>α</mi></mstyle></mrow><annotation>{\displaystyle \alpha }</annotation></semantics></math><img src=$ ${\displaystyle n imes n <semantics><mrow><mstyle><mi>n</mi><mo>×</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n imes n}</annotation></semantics></math><img src=$ ${\displaystyle n imes n^{\alpha <semantics><mrow><mstyle><mi>n</mi><mo>×</mo><msup><mi>n</mi><mrow><mi>α</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle n imes n^{\alpha }}</annotation></semantics></math><img src=$ ${\displaystyle O(n^{2}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{2})}</annotation></semantics></math><img src=$ ${\displaystyle { ilde {O}}(n^{2+1/6}L) <semantics><mrow><mstyle><mrow><mrow><mover><mi>O</mi><mo>~</mo></mover></mrow></mrow><mo>(</mo><msup><mi>n</mi><mrow><mn>2</mn><mo>+</mo><mn>1</mn><mrow><mo>/</mo></mrow><mn>6</mn></mrow></msup><mi>L</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle { ilde {O}}(n^{2+1/6}L)}</annotation></semantics></math><img src=$ ${\displaystyle \omega =2 <semantics><mrow><mstyle><mi>ω</mi><mo>=</mo><mn>2</mn></mstyle></mrow><annotation>{\displaystyle \omega =2}</annotation></semantics></math><img src=$ ${\displaystyle \alpha =1 <semantics><mrow><mstyle><mi>α</mi><mo>=</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle \alpha =1}</annotation></semantics></math><img src=$ ${\displaystyle { ilde {O}}(n^{2+1/6}L) <semantics><mrow><mstyle><mrow><mrow><mover><mi>O</mi><mo>~</mo></mover></mrow></mrow><mo>(</mo><msup><mi>n</mi><mrow><mn>2</mn><mo>+</mo><mn>1</mn><mrow><mo>/</mo></mrow><mn>6</mn></mrow></msup><mi>L</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle { ilde {O}}(n^{2+1/6}L)}</annotation></semantics></math><img src=$ ${\displaystyle { ilde {O}}(n^{2+1/18}L) <semantics><mrow><mstyle><mrow><mrow><mover><mi>O</mi><mo>~</mo></mover></mrow></mrow><mo>(</mo><msup><mi>n</mi><mrow><mn>2</mn><mo>+</mo><mn>1</mn><mrow><mo>/</mo></mrow><mn>18</mn></mrow></msup><mi>L</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle { ilde {O}}(n^{2+1/18}L)}</annotation></semantics></math><img src=$

Comparaison des méthodes de points intérieurs et des algorithmes du simplexe

L'opinion actuelle est que l'efficacité des bonnes implémentations des méthodes basées sur le simplexe et des méthodes de points intérieurs est similaire pour les applications courantes de la programmation linéaire. Cependant, pour certains types de problèmes de PL, il se peut qu'un type de solveur soit meilleur qu'un autre (parfois beaucoup meilleur), et que la structure des solutions générées par les méthodes de points intérieurs diffère significativement de celle des méthodes basées sur le simplexe, l'ensemble de support des variables actives étant généralement plus petit pour ces dernières.

Problèmes ouverts et travaux récents

La programmation linéaire admet-elle un algorithme à complexité polynomiale forte ?

De nouveaux problèmes non résolus en informatique

Il existe plusieurs problèmes ouverts dans la théorie de la programmation linéaire, dont la résolution représenterait des percées fondamentales en mathématiques et potentiellement des avancées majeures dans notre capacité à résoudre des programmes linéaires à grande échelle.

La programmation linéaire admet-elle un algorithme en temps fortement polynomial ?
La programmation linéaire admet-elle un algorithme en temps polynomial fort pour trouver une solution strictement complémentaire ?
La programmation linéaire admet-elle un algorithme en temps polynomial dans le modèle de calcul en nombres réels (coût unitaire) ?

Cet ensemble de problèmes étroitement liés a été cité par Stephen Smale parmi les 18 plus grands problèmes non résolus du XXIe siècle. Selon Smale, la troisième version du problème « constitue le principal problème non résolu de la théorie de la programmation linéaire ». Bien qu'il existe des algorithmes permettant de résoudre la programmation linéaire en temps faiblement polynomial , tels que les méthodes de l'ellipsoïde et les techniques de points intérieurs , aucun algorithme n'a encore permis d'obtenir une complexité fortement polynomiale en fonction du nombre de contraintes et du nombre de variables. Le développement de tels algorithmes présenterait un grand intérêt théorique et pourrait également permettre des gains pratiques dans la résolution de grands programmes linéaires.

Bien que la conjecture de Hirsch ait été récemment réfutée pour les dimensions supérieures, elle laisse encore les questions suivantes ouvertes.

Existe-t-il des règles de pivot qui mènent à des variantes du simplexe en temps polynomial ?
Tous les graphes polytopaux ont-ils un diamètre borné polynomialement ?

Ces questions portent sur l'analyse des performances et le développement de méthodes de type simplexe. L'immense efficacité de l'algorithme du simplexe en pratique, malgré sa complexité théorique exponentielle, laisse supposer l'existence de variantes s'exécutant en temps polynomial, voire fortement polynomial. Il serait d'une grande importance pratique et théorique de savoir si de telles variantes existent, notamment pour déterminer si la programmation linéaire peut être résolue en temps fortement polynomial.

L'algorithme du simplexe et ses variantes appartiennent à la famille des algorithmes de suivi d'arêtes, ainsi nommés car ils résolvent les problèmes de programmation linéaire en se déplaçant de sommet en sommet le long des arêtes d'un polytope. Leurs performances théoriques sont donc limitées par le nombre maximal d'arêtes entre deux sommets quelconques du polytope. Par conséquent, nous cherchons à déterminer le diamètre maximal, au sens de la théorie des graphes, des graphes polytopiques . Il a été démontré que tous les polytopes ont un diamètre sous-exponentiel. La réfutation récente de la conjecture de Hirsch constitue une première étape vers la démonstration de l'existence éventuelle d'un diamètre superpolynomial pour un polytope. Si de tels polytopes existent, aucune variante d'algorithme de suivi d'arêtes ne peut s'exécuter en temps polynomial. Les questions relatives au diamètre des polytopes présentent un intérêt mathématique intrinsèque.

Les méthodes de pivot simplex préservent la faisabilité primale (ou duale). En revanche, les méthodes de pivot croisées ne préservent pas la faisabilité (primale ou duale) ; elles peuvent explorer les bases primales réalisables, duales réalisables ou primales et duales irréalisables dans n’importe quel ordre. Les méthodes de pivot de ce type sont étudiées depuis les années 1970 . Essentiellement, ces méthodes cherchent à trouver le chemin de pivot le plus court sur le polytope d’arrangement dans le cadre du problème de programmation linéaire. Contrairement aux graphes polytopaux, les graphes des polytopes d’arrangement ont un diamètre réduit, ce qui permet d’envisager un algorithme de pivot croisée fortement polynomial sans avoir à résoudre la question du diamètre des polytopes généraux

Inconnues entières

Si toutes les variables inconnues doivent être des entiers, le problème est appelé programmation linéaire en nombres entiers (PLNE ). Contrairement à la programmation linéaire, qui peut être résolue efficacement dans le pire des cas, les problèmes de programmation en nombres entiers sont NP-difficiles dans de nombreuses situations pratiques (celles avec des variables bornées) . La programmation en nombres entiers binaire (PNB) est un cas particulier de programmation en nombres entiers où les variables doivent prendre les valeurs 0 ou 1 (et non des entiers quelconques). Ce problème est également classé comme NP-difficile, et sa version décisionnelle figurait parmi les 21 problèmes NP-complets de Karp .

Si seules certaines des variables inconnues doivent être des entiers, le problème est appelé programme linéaire en nombres entiers mixtes (PLNE). Ces problèmes sont généralement NP-difficiles car ils sont encore plus généraux que les programmes linéaires en nombres entiers (PNI).

Il existe cependant d'importantes sous-classes de problèmes IP et MIP qui sont résolubles efficacement, notamment les problèmes où la matrice de contraintes est totalement unimodulaire et où les seconds membres des contraintes sont des entiers ou – plus généralement – où le système possède la propriété d' intégralité duale totale (TDI).

Les algorithmes avancés pour la résolution des programmes linéaires en nombres entiers comprennent :

méthode du plan de coupe
Branche et limites
Brancher et couper
Succursale et prix
si le problème présente une structure supplémentaire, il est possible d'appliquer une génération de colonnes différée .

De tels algorithmes de programmation en nombres entiers sont abordés par Padberg et dans Beasley.

Programmes linéaires intégraux

Un programme linéaire à variables réelles est dit intégral s'il admet au moins une solution optimale qui est intégrale, c'est-à-dire composée uniquement de valeurs entières ( à ne pas confondre avec les intégrales ). De même, un polyèdre ${\displaystyle P=\{x\mid Ax\geq 0\ <semantics><mrow><mstyle><mi>P</mi><mo>=</mo><mo>{</mo><mi>x</mi><mo>∣</mo><mi>UN</mi><mi>x</mi><mo>≥</mo><mn>0</mn><mo>}</mo></mstyle></mrow><annotation>{\displaystyle P=\{x\mid Ax\geq 0\}}</annotation></semantics></math><img src=$ intégral si, pour toutes les fonctions objectives réalisables bornées c , le programme linéaire ${\displaystyle \{\max cx\mid x\in P\ <semantics><mrow><mstyle><mo>{</mo><mo>max</mo><mi>c</mi><mi>x</mi><mo>∣</mo><mi>x</mi><mo>∈</mo><mi>P</mi><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \{\max cx\mid x\in P\}}</annotation></semantics></math><img src=$ ${\displaystyle x^{* <semantics><mrow><mstyle><msup><mi>x</mi><mrow><mo>∗</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle x^{*}}</annotation></semantics></math><img src=$ ${\displaystyle P <semantics><mrow><mstyle><mi>P</mi></mstyle></mrow><annotation>{\displaystyle P}</annotation></semantics></math><img src=$ c , la valeur optimale du programme linéaire ${\displaystyle \{\max cx\mid x\in P\ <semantics><mrow><mstyle><mo>{</mo><mo>max</mo><mi>c</mi><mi>x</mi><mo>∣</mo><mi>x</mi><mo>∈</mo><mi>P</mi><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \{\max cx\mid x\in P\}}</annotation></semantics></math><img src=$

Les programmes linéaires intégraux sont essentiels à l'approche polyédrique de l'optimisation combinatoire , car ils offrent une caractérisation alternative du problème. Plus précisément, pour tout problème, l'enveloppe convexe des solutions est un polyèdre intégral ; si ce polyèdre admet une description élégante et compacte, on peut trouver efficacement la solution optimale réalisable pour toute fonction objectif linéaire. Réciproquement, si l'on peut démontrer qu'une relaxation de programme linéaire est intégrale, alors elle constitue la description recherchée de l'enveloppe convexe des solutions réalisables (intégrales).

La terminologie n'est pas uniforme dans toute la littérature, il convient donc de faire attention à distinguer les deux concepts suivants :

Dans un programme linéaire en nombres entiers, décrit dans la section précédente, les variables sont contraintes d'être des entiers, et ce problème est NP-difficile en général.
Dans un programme linéaire intégral, décrit dans cette section, les variables ne sont pas contraintes d'être des entiers, mais on a plutôt prouvé d'une manière ou d'une autre que le problème continu a toujours une valeur optimale entière (en supposant que c est entier), et cette valeur optimale peut être trouvée efficacement puisque tous les programmes linéaires de taille polynomiale peuvent être résolus en temps polynomial.

Une méthode courante pour démontrer qu'un polyèdre est entier consiste à montrer qu'il est totalement unimodulaire . Il existe d'autres méthodes générales, notamment la propriété de décomposition en entiers et l'intégralité duale totale . Parmi les autres programmes linéaires entiers bien connus, on peut citer le polytope de couplage, les polyèdres réticulaires, les polyèdres de flot sous-modulaires et l'intersection de deux polymatroïdes généralisés (ou g - polymatroïdes) – voir par exemple Schrijver 2003.

Solveurs et langages de script (programmation)

Licences permissives :

Licences copyleft (réciproques) :

MINTO (Mixed Integer Optimizer, un solveur de programmation entière qui utilise l'algorithme de branchement et d'évaluation) a un code source disponible publiquement mais n'est pas open source.

Licences propriétaires :