Programmation linéaire

Réduire les fonctions linéaires soumises aux contraintes

La programmation linéaire (LP) implique la réduction ou l'augmentation d'une fonction objective soumise aux limites, à l'égalité linéaire et aux contraintes d'inégalité. Les problèmes fournis en exemples comprennent l'optimisation du concept dans l'ingénierie, la maximisation des profits dans la fabrication, l'optimisation du portefeuille dans la finance et l'organisation dans l'énergie et les transports.

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

\[\underset{x}{min}\left\{f^Tx\right\}\]

Soumises aux contraintes linéaires :

\(Ax\leq b\)
(contrainte d'inégalité)
\(A_{eq}x=b_{eq}\)
(contrainte d'égalité)
\(lb\leq x\leq ub\)
(contrainte de limite)

Les algorithmes suivants sont couramment utilisés pour résoudre des problèmes de programmation linéaire :

  • Point intérieur : Utilise un algorithme prédicteur-correcteur primal-dual et est particulièrement utile pour les problèmes à grande échelle dotés d'une structure ou qui peuvent être définis en utilisant des matrices peu denses.
  • Ensemble actif : Minimise l'objectif à chaque itération de l'ensemble actif (un sous-ensemble de contraintes actives localement) jusqu'à ce qu'une solution soit atteinte.
  • Simplex : Utilise une procédure servant à générer et tester systématiquement les solutions applicables à un programme linéaire. L'algorithme simplex est l'algorithme le plus utilisé pour la programmation linéaire.

Pour plus d'informations sur les algorithmes et la programmation linéaire, consultez la description de la solution Optimization Toolbox.

Voir aussi: Optimization Toolbox, Global Optimization Toolbox, programmation quadratique, programmation non linéaire, optimisation multi-objectif, algorithme génétique, simulation de recuit