QCM : Recherche opérationnelle et programmation linéaire (18 questions)

Questions et réponses du QCM

1. Comment caractérise-t-on un programme linéaire ?

Il optimise une fonction linéaire de plusieurs contraintes soumises à des variables linéaires.
Il optimise une fonction linéaire de plusieurs variables soumises à des contraintes non linéaires.
Il optimise une fonction non linéaire de plusieurs variables soumises à des contraintes linéaires.
Il optimise une fonction linéaire de plusieurs variables soumises à des contraintes linéaires.

Il optimise une fonction linéaire de plusieurs variables soumises à des contraintes linéaires.

Explication

Un programme linéaire cherche à maximiser ou minimiser une fonction linéaire sous des contraintes linéaires. Une fonction non linéaire, l’inversion des rôles entre variables et contraintes ou des contraintes non linéaires ne correspondent pas à cette définition.

2. Une entreprise produit xx tonnes de A et yy tonnes de B. A consomme une tonne de M1 et deux tonnes de M2 par tonne produite; B consomme une tonne de chacune des trois matières. Les stocks sont de 300 tonnes de M1, 400 de M2 et 250 de M3, et les profits unitaires sont de 50 et 100. Quelle formulation maximise le profit ?

Maximiser 50x+100y50x+100y sous x+y≤300x+y\leq300, y≤250y\leq250, x,y≥0x,y\geq0.
Maximiser 50x+100y50x+100y sous x+y≤300x+y\leq300, 2x+y≤4002x+y\leq400, x+y≤250x+y\leq250, x,y≥0x,y\geq0.
Maximiser 50x+100y50x+100y sous x+y≤300x+y\leq300, 2x+y≤4002x+y\leq400, y≤250y\leq250, x,y≥0x,y\geq0.
Maximiser 100x+50y100x+50y sous x+y≤300x+y\leq300, 2x+y≤4002x+y\leq400, y≤250y\leq250, x,y≥0x,y\geq0.

Maximiser $$50x+100y$$ sous $$x+y\leq300$$, $$2x+y\leq400$$, $$y\leq250$$, $$x,y\geq0$$.

Explication

Les profits unitaires donnent 50x+100y50x+100y, tandis que les consommations de M1, M2 et M3 imposent respectivement x+y≤300x+y\leq300, 2x+y≤4002x+y\leq400 et y≤250y\leq250, avec des quantités non négatives. Inverser les profits, omettre M2 ou faire consommer M3 par A déforme les données du problème.

3. Dans le problème de production décrit, l’entreprise choisit le point B(50,250)B(50,250). Quel profit maximal ce point procure-t-il ?

15 000 Dh
27 500 Dh
300 Dh
25 000 Dh

27 500 Dh

Explication

Le profit vaut 50×50+100×250=2 500+25 000=27 50050\times50+100\times250=2\,500+25\,000=27\,500 Dh. Omettre la production de A ou permuter les profits unitaires réduit le calcul, tandis qu’additionner les quantités ne mesure pas le profit.

4. Un problème de programmation linéaire possède un domaine admissible et une valeur optimale finie. Où faut-il chercher une solution optimale ?

À un point extérieur au domaine admissible.
À un point intérieur du domaine admissible.
À un sommet du domaine admissible.
Sur une droite de niveau arbitraire de la fonction objectif.

À un sommet du domaine admissible.

Explication

Lorsqu’une solution finie existe, elle se trouve à un sommet du domaine des solutions admissibles. Un point intérieur ou extérieur n’est pas la propriété garantie, et une droite de niveau arbitraire ne détermine pas à elle seule une solution optimale.

5. Après les transformations nécessaires, quelle structure caractérise la forme standard d’un programme linéaire ?

Maximiser une fonction linéaire sous Ax=bAx=b et x≥0x\geq0
Minimiser une fonction linéaire sous des contraintes Ax≤bAx\leq b et x≥0x\geq0
Minimiser une fonction linéaire sous Ax=bAx=b et x≥0x\geq0, avec des seconds membres non négatifs
Minimiser une fonction linéaire sous Ax=bAx=b en autorisant des variables de signe libre

Minimiser une fonction linéaire sous $$Ax=b$$ et $$x\geq0$$, avec des seconds membres non négatifs

Explication

La forme standard combine une minimisation, des contraintes d’égalité et des variables non négatives; les seconds membres sont rendus non négatifs au besoin. Les inégalités conservées, les variables libres et la maximisation non transformée ne respectent pas cette structure.

6. Pour mettre en forme standard un problème qui maximise 3u−v3u-v, avec uu libre, v≤0v\leq0 et une contrainte 2u+v≤52u+v\leq5, quelle transformation convient à la fois à l’objectif, aux variables et à cette contrainte ?

Minimiser −3u+v-3u+v, poser u=u+−u−u=u^+-u^- et v=−v−v=-v^-, puis écrire 2u+v−s=52u+v-s=5 avec des variables non négatives
Minimiser −3u+v-3u+v, poser u=u+−u−u=u^+-u^- et v=−v−v=-v^-, puis écrire 2u+v+s=52u+v+s=5 avec des variables non négatives
Minimiser 3u−v3u-v, poser u=u+−u−u=u^+-u^- et v=−v−v=-v^-, puis écrire 2u+v+s=52u+v+s=5 avec des variables non négatives
Minimiser −3u+v-3u+v, poser u=u+u=u^+ et v=−v−v=-v^-, puis écrire 2u+v+s=52u+v+s=5 avec des variables non négatives

Minimiser $$-3u+v$$, poser $$u=u^+-u^-$$ et $$v=-v^-$$, puis écrire $$2u+v+s=5$$ avec des variables non négatives

Explication

Une maximisation devient la minimisation de son opposé, une variable libre est la différence de deux variables non négatives, et une variable non positive est l’opposé d’une variable non négative. Une contrainte de type inférieur reçoit une variable d’écart ajoutée; garder l’objectif initial, réduire la variable libre à une seule variable ou soustraire l’écart correspond aux erreurs signalées.

7. Pour le système Ax=b, x≥0Ax=b,\ x\geq0, un vecteur zz satisfait Az=bAz=b mais possède une composante négative; comment le classer ?

Il n’est pas admissible, car toutes ses composantes doivent être non négatives
Il est admissible, car les égalités suffisent à satisfaire le système
Il est optimal, car il vérifie les contraintes d’égalité
Il n’est admissible que si toutes ses composantes sont strictement positives

Il n’est pas admissible, car toutes ses composantes doivent être non négatives

Explication

Une solution admissible doit vérifier simultanément Az=bAz=b et z≥0z\geq0; la composante négative exclut donc ce vecteur. Les égalités seules ne suffisent pas, l’admissibilité ne signifie pas optimalité, et la condition porte sur la non-négativité plutôt que sur la positivité stricte.

8. Dans un ensemble admissible défini par Ax=b, x≥0Ax=b,\ x\geq0, un point est vérifié comme point extrémal; quelle propriété équivalente peut-on alors lui attribuer ?

Il est un point quelconque satisfaisant les égalités
Il est nécessairement une solution optimale
Il est une solution de base même si elle n’est pas admissible
Il est une solution de base admissible

Il est une solution de base admissible

Explication

Pour l’ensemble défini par Ax=b, x≥0Ax=b,\ x\geq0, être un point extrémal équivaut à être une solution de base admissible. Le caractère extrémal n’implique pas l’optimalité, et une solution de base non admissible ou un point satisfaisant les seules égalités ne suffit pas.

9. Au cours d’une itération du simplexe, quelle démarche respecte le principe de la méthode ?

Passer d’une solution de base admissible à une autre en améliorant la fonction objectif
Passer d’une solution de base admissible à une autre sans chercher à améliorer l’objectif
Passer à une solution non admissible dès qu’elle améliore la fonction objectif
Passer d’une solution admissible quelconque à une autre sans condition de base

Passer d’une solution de base admissible à une autre en améliorant la fonction objectif

Explication

Le simplexe progresse d’une solution de base admissible vers une autre solution de base admissible en améliorant la fonction objectif. Une solution quelconque n’est pas forcément de base, une transition sans amélioration omet le critère de progression, et une solution non admissible sort du domaine recherché.

10. Dans un problème de minimisation, une solution de base admissible présente des coûts réduits tous supérieurs ou égaux à zéro. Quelle conclusion faut-il en tirer ?

La solution est nécessairement dégénérée.
Le problème est irréalisable.
La solution est optimale.
Une variable doit entrer dans la base.

La solution est optimale.

Explication

Pour une solution de base admissible, des coûts réduits tous supérieurs ou égaux à zéro satisfont la condition d’optimalité. Un coût réduit négatif indique plutôt une variable susceptible d’entrer dans la base, tandis que l’admissibilité seule ne prouve pas l’irréalisabilité ni la dégénérescence.

11. Dans un problème de minimisation, une variable hors base a un coût réduit négatif et peut entrer dans la base. Quel effet son entrée peut-elle avoir sur la valeur de l’objectif ?

Elle peut augmenter la valeur de l’objectif.
Elle laisse nécessairement la valeur inchangée.
Elle prouve que la solution actuelle est optimale.
Elle peut diminuer la valeur de l’objectif.

Elle peut diminuer la valeur de l’objectif.

Explication

Un coût réduit négatif signifie que l’augmentation admissible de cette variable peut diminuer l’objectif à minimiser. Une hausse correspondrait à une mauvaise interprétation du signe, et ce critère ne prouve pas que la solution actuelle est optimale.

12. Lors d’une itération du simplexe, une variable entrante est choisie, mais tous les coefficients de sa colonne dans les lignes des variables de base sont non positifs. Que conclut-on ?

La variable entrante doit être remplacée par une variable artificielle.
Le problème initial est irréalisable.
Le problème possède une solution infinie.
La solution de base actuelle est optimale.

Le problème possède une solution infinie.

Explication

Si tous les coefficients de la colonne entrante sont non positifs, aucune borne supérieure n’est imposée à cette variable par le test de faisabilité : le problème possède une solution infinie. L’absence de coefficient positif ne signifie ni que le problème est irréalisable ni que l’optimum est atteint.

13. Une équipe dispose d’une base admissible initiale et veut appliquer le simplexe pour minimiser un objectif. Quelle suite d’opérations décrit correctement l’algorithme ?

Tester les coûts réduits, choisir une variable entrante de coût négatif, choisir une ligne arbitraire, pivoter et recommencer.
Choisir une variable entrante, pivoter, tester les coûts réduits, appliquer le rapport minimal et recommencer.
Tester les coûts réduits, choisir une variable entrante de coût négatif, appliquer le rapport minimal, pivoter et recommencer.
Tester les coûts réduits, choisir une variable de coût positif, appliquer le rapport minimal, pivoter et recommencer.

Tester les coûts réduits, choisir une variable entrante de coût négatif, appliquer le rapport minimal, pivoter et recommencer.

Explication

Après avoir trouvé une base admissible, l’algorithme teste les coûts réduits, choisit une variable entrante de coût réduit négatif, détermine la ligne pivot par le rapport minimal, puis pivote et recommence. Pivoter avant les tests ou choisir une ligne arbitraire omet une étape essentielle.

14. Un problème linéaire sous forme standard ne possède pas de base admissible évidente. Quelle démarche permet de l’initialiser par la phase I ?

Ajouter des colonnes unités nécessaires, puis minimiser directement l’objectif initial.
Ajouter les colonnes unités nécessaires et les variables artificielles associées, puis minimiser leur somme.
Conserver la matrice inchangée et choisir directement une base admissible.
Ajouter des variables artificielles, puis maximiser leur somme.

Ajouter les colonnes unités nécessaires et les variables artificielles associées, puis minimiser leur somme.

Explication

La phase I ajoute les colonnes unités nécessaires, associe à celles-ci des variables artificielles positives, puis minimise leur somme afin de construire une base admissible. Minimiser l’objectif initial ne réalise pas cette procédure de faisabilité.

15. À l’optimum de la phase I, la somme des variables artificielles vaut 3. Que révèle ce résultat sur le problème initial ?

Il est irréalisable.
Son objectif initial vaut 3.
Il possède une solution optimale dégénérée.
Il admet une solution de base admissible.

Il est irréalisable.

Explication

À l’optimum de la phase I, une somme artificielle non nulle signifie que le problème initial n’a pas de solution admissible. Une somme nulle, au contraire, indique l’existence d’une solution de base admissible; la valeur obtenue ne donne pas l’objectif initial.

16. Une entreprise modélise son problème primal par min⁡cTx\min c^T x sous Ax≥bAx\geq b et x≥0x\geq0. Quelle formulation doit-elle associer au problème dual ?

min⁡yTb\min y^T b sous yTA≤cTy^T A\leq c^T et y≥0y\geq0
max⁡yTb\max y^T b sous yTA≥cTy^T A\geq c^T et y≥0y\geq0
max⁡yTb\max y^T b sous yTA≤cTy^T A\leq c^T et y≥0y\geq0
max⁡yTb\max y^T b sous yTA≤cTy^T A\leq c^T et yy libre

$$\max y^T b$$ sous $$y^T A\leq c^T$$ et $$y\geq0$$

Explication

Le dual de cette forme primale maximise yTby^T b, impose yTA≤cTy^T A\leq c^T et conserve la non-négativité des variables duales. La minimisation est une inversion du sens de l’objectif, le signe ≥\geq inverse la contrainte duale, et des variables libres ne respectent pas la condition y≥0y\geq0.

17. Pour un problème primal et son dual, une équipe trouve deux solutions admissibles dont les valeurs d’objectif sont respectivement cTx=18c^T x=18 et yTb=18y^T b=18. Que peut-elle conclure ?

Les deux solutions sont optimales
Seule la solution duale est optimale
Les solutions ne peuvent être admissibles ensemble
Seule la solution primale est optimale

Les deux solutions sont optimales

Explication

La dualité faible donne yTb≤cTxy^T b\leq c^T x pour des solutions admissibles; lorsque les valeurs sont égales, les deux solutions sont optimales. L’inadmissibilité ne découle pas de cette égalité, l’inégalité n’est pas inversée, et l’optimalité concerne les deux solutions.

18. Un problème de maximisation et son problème dual sont en dualité; le premier admet une solution optimale. Quelle conséquence s’applique à l’autre problème ?

Il admet une solution optimale, mais de valeur distincte
Il admet aussi une solution optimale de même valeur
Il est nécessairement non admissible, avec une valeur distincte
Il peut rester sans solution optimale malgré cette optimalité

Il admet aussi une solution optimale de même valeur

Explication

Le théorème de dualité affirme que si l’un des problèmes admet une solution optimale, l’autre en admet également une, et que leurs valeurs optimales sont égales. Une valeur distincte contredit l’égalité des valeurs, tandis que l’absence de solution optimale dans le dual contredit l’existence garantie par le théorème.

Révisez avec les flashcards

Mémorisez les réponses avec 46 flashcards sur Recherche opérationnelle et programmation linéaire.

Qu’est-ce qu’un programme linéaire ?

L’optimisation d’une fonction linéaire de plusieurs variables soumises à des contraintes linéaires.

Dans le modèle de production de A et B, quelle fonction représente le profit à maximiser ?

P=50x+100yP=50x+100y

Dans le modèle de production de A et B, quelle contrainte exprime le stock de M1 ?

x+y≤300x+y\leq300

Voir les flashcards →

Approfondir avec la fiche

Consultez la fiche de révision complète sur Recherche opérationnelle et programmation linéaire.

Voir la fiche →

Cours similaires

Acides et bases en solution

Chimie

Suites numériques

Mathématiques

Transformations acido-basiques et pH

Chimie

Réplication et mutations de l’ADN

SVT

Organisation cellulaire du vivant

SVT

Organisation fonctionnelle du vivant

SVT

Crée tes propres QCM

Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.

Générateur de QCM