Modélisation d'un problème de programmation linéaire

Processus de modélisation d'un problème linéaire

Processus de modélisation d'un problème de programmation linéaire.

• Déterminer et définir la cible (maximiser ou minimiser).
• Dresser une liste de choix.
• Définir les variables de décision (x1, x2, ..., xn).
• Développer une liste de restrictions qui les affectent.
• Définir la fonction objectif, par exemple : max Z = 40 x1 + 50 x2.

Types de relations : ≤, ≥, =

Limitation (≤), exigence (≥) et égalité (=).

Restrictions

Les restrictions devraient établir des limites à la disponibilité des ressources et à la nécessité de respecter les engagements pour la période.

• Contraintes de capacité et/ou disponibilité des ressources. Ce sont des limites dues au système en termes de quantité de matériel, d'espace, de financement, de matières premières et de main-d'œuvre disponible. Un exemple serait la contrainte liée à la surface de terre disponible pour les cultures. Ces contraintes sont généralement exprimées par des inégalités de type (≤) : la quantité utilisée d'une ressource ne peut pas être supérieure à la quantité disponible.
• Restrictions sur le marché. Il existe des limites (inférieure, supérieure ou les deux) du montant d'un produit qui peut être vendu ou utilisé. Par exemple : un maximum de ventes historique ou un minimum historique requis pour un produit. Le minimum correspond à une exigence (≥) : si un certain niveau de ventes est contractuellement engagé, on ne peut pas produire moins. Le maximum est une contrainte (≤) car on ne peut pas vendre plus que la demande historique.
• Contraintes de qualité ou composition d'un mélange. Ces restrictions limitent le mélange d'ingrédients qui définissent généralement la qualité du produit final. Elles peuvent être exprimées par des inégalités (≤, ≥) ou par des égalités (=), selon la spécification de qualité.
• Contraintes liées à la technologie de production ou bilan matières. Ce sont des contraintes qui définissent le résultat d'un processus en fonction des intrants, souvent incluant des pertes ou des rendements. Comme ci-dessus, elles peuvent être des limitations (≤), des exigences (≥) ou des égalités (=), selon le processus modélisé.
• Contraintes de définition. Ces contraintes définissent une variable en fonction d'autres variables. Elles proviennent souvent de relations comptables ou d'équilibres de matières, par exemple la relation entre la quantité produite, la quantité vendue et le stock restant. Ces contraintes sont généralement des égalités (=).

Caractérisation de la solution optimale

Types de contraintes

• Contraintes actives : elles déterminent directement la localisation de l'optimum.
• Contraintes non actives : elles ne sont pas directement impliquées dans la détermination de l'emplacement optimal.
• Contraintes redondantes : ce sont des contraintes non actives qui ne participent pas directement, voire qui n'influencent pas, les limites de la zone des solutions réalisables.

Prix d'ombre des contraintes

Le prix d'ombre d'une contrainte est une mesure quantitative de l'influence d'une modification du terme libre (second membre) de la contrainte sur la valeur optimale de la fonction objectif. Il existe deux définitions équivalentes :

• Définition n°1 : le taux d'amélioration de la valeur optimale de la fonction objectif pour chaque unité que l'on augmente le terme libre d'une contrainte.
• Définition n°2 : le taux de détérioration de la valeur optimale de la fonction objectif pour chaque unité que l'on diminue le terme libre d'une contrainte.

Ces définitions s'appliquent habituellement lorsque le prix d'ombre est positif. En pratique, le signe du prix d'ombre dépend du type de contrainte :

• Le prix d'ombre d'une contrainte de type (≤) active est normalement positif (≥ 0).
• Le prix d'ombre d'une contrainte de type (≥) active est normalement non positif (≤ 0).
• Pour une contrainte de type (=), le prix d'ombre peut être positif, négatif ou nul, selon le modèle.
• Le prix d'ombre d'une contrainte non active est toujours égal à zéro.

Plage de validité du prix d'ombre

La valeur du prix d'ombre d'une contrainte n'est valable que pour des variations du terme libre qui ne font pas changer l'ensemble des contraintes actives de la solution optimale initiale (c'est-à-dire tant que les contraintes actives restent les mêmes).

• Le prix d'ombre permettra d'améliorer la valeur de la fonction objectif (si l'on maximise : augmenter ; si l'on minimise : diminuer) lorsque l'on augmente le terme libre d'une contrainte active de type ≤.
• La valeur empirique pour le pire cas (si l'on maximise : diminution ; si l'on minimise : augmentation) apparaît lorsque le terme libre diminue pour une contrainte active de type ≤.
• Le prix d'ombre permettra d'améliorer la valeur de la fonction objectif (si l'on maximise : augmenter ; si l'on minimise : diminuer) lorsque le terme libre diminue pour une contrainte active de type ≥.
• La valeur empirique pour le pire cas (si l'on maximise : diminution ; si l'on minimise : augmentation) survient lorsque l'on augmente le terme libre d'une contrainte active de type ≥.
• La valeur de la fonction objectif restera inchangée (pas de changement) lorsqu'on augmente ou diminue la valeur du terme libre à condition qu'aucune contrainte active ne change de statut.