Correction examen ro juin 2016 exercice 1 -Programmation lin

Télécharger PDF

Correction d'Examen : Recherche Opérationnelle - Juin 2016

Exercice 1 : Résolution Graphique d'un Programme Linéaire

Représentation des Contraintes

La résolution graphique d'un programme linéaire commence par la délimitation de la région des solutions admissibles, aussi appelée domaine de faisabilité. Chaque contrainte du problème correspond à une droite ou à une demi-plan sur un graphique à deux dimensions.

Pour la première contrainte, nous déterminons les points d'intersection avec les axes. Si X1 = 0, on obtient X2 = 9, ce qui nous donne le point A(0, 9). Par contre, si X2 = 0, on obtient X1 = 6, ce qui nous donne le point B(6, 0). En reliant ces deux points, nous traçons la ligne correspondant à la première contrainte sur le graphique ci-dessous.

De la même manière, pour la deuxième contrainte : si X1 = 0, on obtient X2 = 3, ce qui nous donne le point C(0, 3). Par contre, si X2 = 0, on obtient X1 = 6, ce qui nous donne le point D(6, 0). Ces deux points permettent de tracer la ligne de la deuxième contrainte sur le graphique ci-dessous.

La troisième contrainte est représentée par une droite parallèle à l’axe des ordonnées. La quatrième contrainte est une droite parallèle à l’axe des abscisses. Les dernières contraintes, généralement X1 ≥ 0 et X2 ≥ 0, nous obligent à considérer seulement les valeurs positives des variables, c'est-à-dire le premier quadrant du plan cartésien.

La région admissible est constituée par l’aire hachurée OGEFH. Il s'agit de la zone où toutes les contraintes sont satisfaites simultanément, formant un polygone convexe dont les sommets sont des points d'intersection des droites de contrainte.

Représentation de la Fonction Objectif et Recherche de la Solution Optimale

Pour représenter la fonction objectif et trouver la solution optimale, nous utilisons la méthode de la droite d'iso-valeur (ou isoprofit). On choisit un point quelconque pour déterminer une valeur arbitraire de Z.

Par exemple, si on choisit le point de coordonnées I(1,0) sur l'axe des abscisses, la valeur de la fonction objectif est égale à 5 (Z = 5). Maintenant, on cherche un point sur l’axe des ordonnées (ce qui implique que X1 = 0) tel que la valeur de la fonction objectif reste inchangée (Z = 5). Ceci implique que X2 = 5/6. Alors le point J(0, 5/6) nous procure la même valeur de Z. La droite passant par I et J est une ligne d'iso-valeur.

En général, une droite d'iso-valeur représente l'équation de la fonction objectif pour une valeur Z donnée. Maximiser la fonction objectif consiste à translater cette droite vers le haut, parallèlement à elle-même, jusqu'à ce qu'elle touche le dernier point de la région admissible OGEFH. La solution est obtenue par l’intersection de la droite la plus éloignée de l'origine (dans le sens de la maximisation) et de la région admissible.

Graphiquement, la solution optimale est le point E(3, 3/2). Dans ce cas, la valeur maximale de Z est égale à 24.

Exercice 2 : Formulation d'un Programme Linéaire de Production

Soient X1, X2, X3 et X4 les nombres de sacs à produire des produits P1, P2, P3 et P4, respectivement. Ce problème de production vise à maximiser une fonction économique (profit, revenu, etc.) sous diverses contraintes de ressources, de production ou de demande. Il peut être représenté par le programme linéaire suivant :

Maximiser Z = 19X1 + 18X2 + 2X3 + 11X4

Sous contraintes :

X1 ≥ 2X3
X4 ≥ 10
X2 ≤ 100
2X1 + 3X2 + 4X3 + 2X4 ≤ 500
3X1 + 2X2 + X3 + 2X4 ≤ 380
7X1 + 3X2 + 2X3 + X4 ≤ 450
Xi ≥ 0 pour i = 1, 2, 3, 4 (Contraintes de non-négativité)
Xi sont des entiers pour i = 1, 2, 3, 4 (Contraintes d'intégrité)

La fonction objectif (Maximiser Z) représente le critère que l'on souhaite optimiser. Les inégalités sont les contraintes qui définissent les limitations du système. Les conditions Xi ≥ 0 garantissent que les quantités produites ne peuvent pas être négatives, et Xi sont des entiers signifie que les quantités doivent être des unités complètes (on ne peut pas produire une fraction de sac).

Exercice 3 : Identification des Programmes Linéaires

Critères d'un Programme Linéaire

1) Pour qu'un problème soit qualifié de programme linéaire (PL), il doit respecter plusieurs conditions strictes : une fonction objectif à optimiser (maximisation ou minimisation), toutes ses contraintes doivent être des fonctions linéaires des variables de décision, et les variables de décision sont généralement continues et non-négatives.

Seulement le problème C) représente un programme linéaire car il respecte toutes les conditions (présence d'une fonction objectif linéaire et de contraintes linéaires).
Par contre, le problème D) ne représente pas un programme linéaire car il ne contient pas de fonction objectif. Un programme linéaire doit toujours avoir un objectif clair à optimiser.
Le problème A) ne constitue pas un programme linéaire car au moins l’une de ses contraintes n’est pas linéaire (par exemple, elle pourrait contenir des produits de variables, des puissances, etc.).
De même, le problème B) n’est pas un programme linéaire car il contient une seule variable de décision. Généralement, pour un programme linéaire significatif, on considère au moins deux variables de décision pour explorer les interactions complexes.

Programme Linéaire en Nombres Entiers

2) Un programme linéaire en nombres entiers (PLNE) est une variante du programme linéaire où une ou plusieurs variables de décision sont contraintes de prendre des valeurs entières, en plus de toutes les autres conditions d'un PL. Cette caractéristique est essentielle lorsque les solutions fractionnaires n'ont pas de sens dans le contexte du problème (par exemple, le nombre d'unités indivisibles).

Dans les problèmes A, B, C, D analysés dans cet exercice, aucun ne représente un programme linéaire en nombres entiers, car les conditions d'intégrité pour l'ensemble des variables ne sont pas explicitement ou universellement appliquées pour tous les problèmes mentionnés.

Foire Aux Questions (FAQ) sur les Programmes Linéaires

Qu'est-ce qu'un programme linéaire (PL) ?

Un programme linéaire est une technique mathématique utilisée en recherche opérationnelle pour optimiser (maximiser ou minimiser) une fonction objectif linéaire, sous un ensemble de contraintes linéaires (inégalités ou égalités). Il aide à prendre des décisions optimales pour l'allocation de ressources limitées.

Comment identifie-t-on la région admissible dans un PL graphique ?

La région admissible (ou domaine de faisabilité) est l'ensemble de tous les points (combinaisons de valeurs des variables) qui satisfont simultanément toutes les contraintes du programme linéaire. Graphiquement, elle est représentée par la zone d'intersection de tous les demi-plans définis par les contraintes, formant un polygone convexe sur le plan cartésien.

Quelle est la différence entre un PL et un PL en nombres entiers (PLNE) ?

La principale distinction réside dans la nature des variables de décision. Dans un PL classique, les variables peuvent prendre n'importe quelle valeur réelle (décimales comprises). Dans un PLNE, au moins une, voire toutes, les variables de décision sont contraintes d'être des nombres entiers. Cette contrainte supplémentaire rend les PLNE généralement plus complexes à résoudre mais plus réalistes pour certains problèmes où les décisions doivent être des quantités discrètes.