Programmation linéaire multi-objectif (multicritère)

Résumé du document

La programmation linéaire est un outil simple et puissant de la Recherche Opérationnelle. Elle permet d'analyser plusieurs situations économiques dans lesquelles les variables de décisions ainsi que les paramètres constants relatifs à ses variables sont liés par des fonctions linéaires (...)

Extraits

[...] C : le vecteur coût de dimension n associé à l'objectif du problème. Pour résoudre un PL, se dernier est transformé en sa forme standard suivante : ( 1.3 ) Cette forme s'obtient on rajoutant des variables d'écarts au système des contraintes en cas de nécessité. Le vecteur x deviendra donc de dimension + α) ; n étant le nombre de variables de décision et α le nombre de variables d'écarts. Un PL peut admettre soit : 1. Une solution optimale unique Une infinité de solutions optimales Solution infinie Aucune solution réalisable Algorithme du simplexe Développé par Dantzig en 1947 cet algorithme résout n'importe quel programme linéaire. [...]

[...] La décision tel que est appelée décision idéale Fonctions Scalarisantes S'il apparaît naturel de limiter la considération des solutions à celle qui sont efficaces, l'ensemble de celles-ci est généralement très vaste et même infini dans le cas de variables continues. Aussi la sélection d'une solution efficace spécifique comme candidat de meilleur compromis exige une certaine connaissance de la structure de préférence. Cette information est obtenue directement ou indirectement et peut parfois se traduire en termes de paramètres de préférence. Les paramètres les plus courants sont : - les poids , qui reflètent l'importance relative de chaque critère. [...]

[...] Notons que ces paramètres peuvent également être des points cibles tels que : - Le point de référence qui est défini par des niveau d'aspiration sur chaque critère. En tenant compte d'un jeu de paramètre de préférence, donné ou évalué, il est possible de définir la fonction scalarisante. Il s'agit d'une fonction : Exemple1 : (à l'aide de poids) Exemple2 : (norme Lp pondérée) Bibliographie J.P.Ignizio , Linear programming in in single and multiple objective systems, Englewood Cliffs, NJ :Prentice-Hall, 1982a. C.Romero, A general structure of achievement function for a goal programming model. European Journal of Operational Research p. 675-686. [...]

[...] Comme le choix d'une décision se fait sur la base des évaluations des conséquences, l'intérêt sera porté sur l'ensemble des valeurs critères. Dans de nombreux problèmes, on constate que les vecteurs critères possèdent la priorité qu'on peut améliorer une composante d'un vecteur, sans augmenter la valeur d'une de ses autres composantes au moins. Cette caractéristique a donné lieu à la définition de l'optimum de Pareto. L'optimum n'a pas de réelle signification en optimisation des problèmes multicritère, on parle plus de solution de compromis, car les fonctions objectifs sont souvent conflictuelles. [...]

[...] La PL a connue un grand essor après la deuxième guerre mondiale, notamment après l'apparition de l'algorithme du simplexe par Dantzig (1947) qui permet de trouver la solution optimale si elle existe Définition : un programme linéaire est définit par ( 1.1 ) Où X : est l'ensemble des contraintes régissant le système c'est-à-dire : . : sont des fonctions linéaire. x : représente le n-vecteur des variables de décisions. C : le n-vecteur comprenant les coefficients relatifs aux variables du problème. est appelée la fonction objectif ou fonction économique. Le problème ( 1.1 ) peut aussi s'écrire sous la forme matricielle suivante : ( 1.2 ) Où : est la matrice composée des coefficients des variables x. [...]