Programmation linéaire

Résoudre des problèmes d'optimisation linéaire

La programmation linéaire (LP) est la minimisation ou la maximisation d'une fonction objectif soumise à des contraintes de limites, d'égalité linéaire et d'inégalité. Les exemples proposés adressent les problématiques de mélange de produits dans les industries de transformation, de la planification de la production dans le domaine manufacturier, d'appariement des flux de trésorerie dans le domaine financier et de la planification dans les domaines de l'énergie et des transports.

La programmation linéaire est le problème mathématique consistant à trouver un vecteur x qui minimise la fonction :

\[\min_{x} \left\{f^{\mathsf{T}}x\right\}\]

soumise aux contraintes :

\[\begin{eqnarray}Ax \leq b & \quad & \text{(contrainte d'inégalité)} \\A_{eq}x = b_{eq} & \quad & \text{(contrainte d'égalité)} \\lb \leq x \leq ub & \quad & \text{(contrainte de limites}\end{eqnarray}\]

Vous pouvez utiliser MATLAB® pour implémenter les algorithmes suivants, couramment utilisés pour résoudre des problèmes de programmation linéaire :

  • Algorithme de points intérieurs : utilise un algorithme prédicteur-correcteur primal-dual et est particulièrement utile pour les programmes linéaires à grande échelle qui ont une structure ou qui peuvent être définis en utilisant des matrices creuses.
  • Algorithme du simplexe : utilise une procédure systématique pour générer et tester les solutions sommets candidates d'un programme linéaire. L'algorithme du simplexe et l'algorithme du simplexe dual sont les algorithmes les plus utilisés pour la programmation linéaire.

Les algorithmes utilisés pour certains cas particuliers de programmes linéaires, où les contraintes possèdent une structure en réseau, sont généralement plus rapides que les algorithmes généralistes de points intérieurs et du simplexe. Parmi ces cas particuliers, on trouve :

Pour plus d'informations sur les algorithmes et la programmation linéaire, voir Optimization Toolbox™.




Voir aussi: Optimization Toolbox, Global Optimization Toolbox, programmation en nombres entiers, programmation quadratique, programmation non linéaire, optimisation multi-objectifs, analyse prédictive

Optimization Techniques Training Course

In this course you’ll learn applied optimization techniques in the MATLAB® environment, focusing on using Optimization Toolbox™ and Global Optimization Toolbox.