Chapitre 7 — Programmation Linéaire Entière

CHOIX MULTIPLES

1. Laquelle des contributions suivantes de la programmation entière est la plus utile ?

a. trouver des solutions entières où des solutions fractionnaires ne seraient pas appropriées
b. utiliser des variables 0-1 pour modéliser la flexibilité
c. facilité accrue de la solution
d. prévisions pour les procédures de solution des problèmes de transport et d'affectation
RÉPONSE : B PTS : 1 TOP : Introduction

2. Dans un modèle, x1≥0 et entier, x2≥0, et x3= 0, 1. Quelle solution ne serait pas réalisable?
a. x1= 5, x2= 3, x3= 0
b. x1= 4, x2= .389, x3= 1
c. x1= 2, x2= 3, x3= .578
d. x1= 0, x2= 8, x3= 0
RÉPONSE : C PTS: 1 Haut : Introduction

3. Les solutions arrondies aux programmes linéaires doivent être évaluées pour
a. faisabilité et optimalité.
b. sensibilité et dualité.
c. relaxation et bornitude.
d. chacun des éléments ci-dessus est vrai.

RÉPONSE : A PTS : 1 Relaxation en LP

4. Rounding the solution of an LP Relaxation to the nearest integer values provides

a. une solution entière réalisable mais pas nécessairement optimale.
b. une solution entière qui est optimale.
c. une solution entière qui pourrait ne pas être réalisable ni optimale.
d. une solution infaisable.
RÉPONSE : C PTS : 1 SOLUTION GRAPHIQUE

5. La solution à la relaxation LP d'un programme linéaire à entiers de maximisation fournit

a. une borne supérieure pour la valeur de la fonction objectif.
b. une borne inférieure pour la valeur de la fonction objectif.
c. une borne supérieure pour la valeur des variables de décision.
d. une borne inférieure pour la valeur des variables de décision.
RÉPONSE : A PTS : 1 SOLUTION GRAPHIQUE

6. Le graphique d'un problème qui nécessite x1et x2être entier a une région réalisable
a. le même que sa relaxation LP.
b. de points.
c. de rayures horizontales.
d. des rayures verticales.
RÉPONSE : B PTS : 1 SOLUTION GRAPHIQUE

7. Les variables 0-1 dans les modèles de coûts fixes correspondent à

 un processus pour lequel un coût fixe se produit.
b. le nombre de produits fabriqués.
c. le nombre d'unités produites.
d. la valeur réelle du coût fixe.
RÉPONSE : A PTS : 1 TOP: Fixed costs

8. Analyse de sensibilité pour la programmation linéaire entière

peut être fourni uniquement par un ordinateur.
b. a exactement la même interprétation que celle de la programmation linéaire.
c. n'a pas la même interprétation et doit être ignoré.
d. est le plus utile pour les modèles 0-1.

RÉPONSE : C PTS : 1 Analyse de sensibilité

9. Laissez x1et x2soient des variables 0-1 dont les valeurs indiquent si les projets 1 et 2 ne sont pas réalisés ou sont réalisés.
Quelle réponse ci-dessous indique que le projet 2 ne peut être réalisé que si le projet 1 est réalisé ?
a. x1+ x2= 1
b. x1+ x2= 2
c. x1−x2≤0
d. x1−x2≥0
Réponse : D PTS: 1 TOP : Contraintes conditionnelles et concomitantes

10. Laissez x1, x2, et x3soient des variables 0-1 dont les valeurs indiquent si les projets ne sont pas réalisés (0) ou le sont
Fait (1). Quelle réponse ci-dessous indique qu'au moins deux des projets doivent être réalisés ?
a. x1 + x2+ x3≥2
b. x1+ x2+ x3≤2
c. x1 + x2+ x3= 2
d. x1−x2= 0
RÉPONSE : A PTS : 1 TOP : contrainte k sur n alternatives

11. Si l'acceptation du projet A est conditionnelle à l'acceptation du projet B, et vice versa, le

la contrainte appropriée à utiliser est un
a. contrainte à choix multiples.
b. k parmi n alternatives contrainte.
c. contrainte d'exclusivité mutuelle.
d. contrainte de co-requis.
RÉPONSE : D PTS: 1
TOP : Modélisation de la flexibilité fournie par des variables entières 0-1

12. Dans un programme linéaire avec uniquement des entiers,

a. tous les coefficients de la fonction objective doivent être des entiers.
b. toutes les valeurs du côté droit doivent être des entiers.
c. toutes les variables doivent être des entiers.
d. tous les coefficients de la fonction objective et les valeurs du côté droit doivent être des entiers.

RÉPONSE : C PTS : 1 TOP : Types de modèles de programmation linéaire entière

13. Pour effectuer une analyse de sensibilité impliquant un programme linéaire entier, il est recommandé de
a. utilisez les prix duals avec beaucoup de prudence.
 b. effectuer plusieurs exécutions sur ordinateur.
c. utilisez la même approche que vous utiliseriez pour un programme linéaire.
d. utiliser la relaxation LP.

RÉPONSE: B PTS : 1 NOTE : Une remarque de prudence concernant l'analyse de sensibilité

14. Modéliser un problème de coût fixe comme un programme linéaire entier nécessite
a. ajouter les coûts fixes aux coûts variables correspondants dans la fonction objective.
b. utilisant des variables 0-1.
c. en utilisant des contraintes à choix multiples.
d. en utilisant la relaxation LP.

RÉPONSE : B PTS: 1 APPLICATIONS : Applications impliquant des variables 0-1

15. La plupart des applications pratiques de la programmation linéaire entière impliquent

a. uniquement des variables entières 0-1 et pas des variables entières ordinaires.
b. principalement des variables entières ordinaires et un petit nombre de variables entières 0-1.
c. seulement des variables entières ordinaires.
d. un nombre presque égal de variables entières ordinaires et de variables entières 0-1.
RÉPONSE : A PTS: 1 APPLICATIONS imiquant des variables 0-1

VRAI/FAUX

1. La relaxation LP contient la fonction objective et les contraintes du problème IP, mais abandonne tout
restrictions d'entiers.

R PTS : 1 TOP : relaxation PL

En général, arrondir les grandes valeurs des variables de décision à la valeur entière la plus proche entraîne moins de
des problèmes que d'arrondir de petites valeurs.

Réponse : T PTS: 1 RELAXATION LP

3. La solution à la relaxation LP d'un problème de minimisation sera toujours inférieure ou égale à la

valeur du problème de minimisation du programme entier.

RÉPONSE : F PTS : 1 SOLUTION GRAPHIQUE

4. Si la solution optimale au problème de relaxation PL est entière, elle est la solution optimale au problème entier.
programme linéaire.

Réponse : T PTS: 1 TOP : Relaxation LP

5. Les variables de slack et de surplus ne sont pas utiles dans les programmes linéaires entiers.

ANS : FPTS : 1TOP : Budgétisation des capitaux

6. Une contrainte à choix multiples implique de sélectionner k parmi n alternatives, où k ≥ 2.

Réponse : FPTS : 1SOMMET : Contrainte à choix multiples

7. Dans un modèle impliquant des coûts fixes, la variable 0-1 garantit que la capacité n'est pas disponible à moins que
le coût a été engagé.
 RÉPONSE : T PTS: 1 TOP: Fixed costs

8. Si x1+ x2≤500y1et y1est 0-1, alors si y1est 0, x1et x2sera 0.

RÉPONSE : TPTS: 1 Conception du système de distribution

9. La contrainte x1+ x2+ x3+ x4≤2 signifie que deux des quatre premiers projets doivent être sélectionnés.

R PTS : 1CONTRAINTE : k sur n alternatives

10. La contrainte x1-x2= 0 implique que si le projet 1 est sélectionné, le projet 2 ne peut pas l'être.

Réponse : FPTS : 1TOP : Contraintes conditionnelles et coréquis

11. Le problème de conception de produit et d'optimisation de la part de marché présenté dans le manuel est formulé comme
un modèle de programmation linéaire entière 0-1.

ANS : T PTS : 1
PROBLEME : Conception de produit et optimisation de la part de marché

12. L'objectif du problème de conception de produit et d'optimisation de la part de marché présenté dans le manuel
c'est de choisir les niveaux de chaque attribut de produit qui maximiseront le nombre de clients échantillonnés
préférant la marque en question.

RÉP: T PTS : 1
PROBLÈME : Conception de produit et optimisation de la part de marché

13. Si un problème n'a que des contraintes de type inférieure ou égale avec des coefficients positifs pour les variables,
L'arrondi vers le bas fournira toujours une solution entière faisable.

R É PTS: 1 Haut : Arrondir pour obtenir une solution entière

14. Les prix duals ne peuvent pas être utilisés pour l'analyse de sensibilité en programmation entière car ils sont conçus pour
programmes linéaires.

R PTS : 1 MESSAGE : Une note de prudence concernant l'analyse de sensibilité

15. Certains problèmes de programmation linéaire ont une structure spéciale qui garantit que les variables vont
ont des valeurs entières.

RÉPONSE : T PTS : 1 TOP: Introduction to integer linear programming

RÉPONSE COURTE

1. L'utilisation de variables entières crée des restrictions supplémentaires mais offre une flexibilité supplémentaire. Expliquez.

Réponse :
Réponse non fournie.

PTS : 1 Haut : Introduction

2. Pourquoi les variables 0-1 sont-elles parfois appelées variables logiques ?

RÉPONSE :
Réponse non fournie.

PTS : 1 TOP: Introduction

3. Donnez une interprétation verbale de chacune de ces contraintes dans le contexte d'un problème de budgétisation des capitaux.
a. x1−x2≥0
b. x1-x2= 0
c. x1+ x2+ x3≤2

RÉPONSE :
Réponse non fournie.

PTS : 1 TOP : Budgétisation des investissements

4. Expliquez comment les variables entières et les variables 0-1 peuvent être utilisées dans une fonction objectif pour minimiser la somme de
coûts fixes et variables de production sur deux machines.

RÉPONSE :
Réponse non fournie.

PTS : 1 Conception du système de distribution

5. Expliquez comment les variables entières et 0-1 peuvent être utilisées dans une contrainte pour permettre la production.

RÉPONSE :
Réponse non fournie.

PTS : 1 Conception du système de distribution

PROBLÈME

1. Résoudre le problème suivant graphiquement.

Max 5X + 6Y

s.t. 17X + 8Y ≤ 136

3X + 4Y ≤ 36
X, Y ≥0 et entier

a. Graphique les contraintes pour ce problème. Indiquez toutes les solutions réalisables.
b. Trouver la solution optimale à la relaxation LP. Arrondir vers le bas pour trouver un entier faisable
solution. Is this solution optimal?
c. Trouver la solution optimale.

RÉPONSE :

a. La région réalisable est constituée des valeurs entières dans l'espace étiqueté région réalisable.
 b. La solution optimale de la programmation linéaire relâchée se situe à X = 5,818, Y = 4,636, avec Z = 56,909. Arrondi à la baisse
la solution se produit à X = 5, Y = 4, Z = 49.

c. La solution optimale est à X = 4, Y = 6 et Z = 56.

PTS : 1 SOLUTION GRAPHIQUE

2. Résoudre le problème suivant graphiquement.

Max X + 2Y

s.t. 6X + 8Y≤48
7X + 5Y ≥ 35
X, Y ≥0
Y entier

a. Tracer les contraintes pour ce problème. Indiquez toutes les solutions réalisables.
b. Trouvez la solution optimale à la relaxation LP. Arrondissez vers le bas pour trouver un entier faisable
solution. Cette solution est-elle optimale ?
c. Trouver la solution optimale.

RÉPONSE :

a. La région faisable est constituée des portions des lignes horizontales qui se trouvent à l'intérieur de la zone.
étiqueté
F. R.
 b. La solution optimale relaxée est à X = 1,538, Y = 4,846 où Z = 11,231. Le arrondi
la solution est X = 1,538, Y = 4.

c. La solution optimale est à X = 2.667, Y = 4, Z = 10.667.

PTS : 1 SOLUTION GRAPHIQUE

3. Résoudre le problème suivant graphiquement.

Min 6X + 11Y

s.t. 9X + 3Y≥27
7X + 6Y ≥ 42
4X + 8Y ≥ 32
X, Y ≥0 et entier

a. Tracez les contraintes pour ce problème. Indiquez toutes les solutions réalisables.
b. Trouver la solution optimale à la relaxation LP. Arrondir pour trouver un entier faisable.
solution. Cette solution est-elle optimale ?
c. Trouvez la solution optimale.

RÉPONSE :

a. La région réalisable est l'ensemble des points entiers dans la zone étiquetée région réalisable.
 b. La solution optimale relâchée est à X = 4,5, Y = 1,75 et Z = 46,25.
The rounded solution is X = 5, Y = 2.

c. La solution optimale est à X = 6, Y = 1 et Z = 47.

PTS: 1 SOLUTION GRAPHIQUE

4. Considérez un exemple de budget d'investissement avec cinq projets parmi lesquels choisir. Soit xje= 1 si le projet i est
sélectionné, 0 si non, pour i = 1,...,5. Écrire les contraintes appropriées pour chaque condition. Les conditions sont
indépendant.

a. Choisissez pas moins de trois projets.

b. Si le projet 3 est choisi, le projet 4 doit être choisi.
c. Si le projet 1 est choisi, le projet 5 ne doit pas être choisi.
d. Les projets coûtent respectivement 100, 200, 150, 75 et 300. Le budget est de 450.
d. Pas plus de deux des projets 1, 2 et 3 ne peuvent être choisis.

ANS :

a. x1+ x2+ x3+ x4+ x5≥3

b. x3−x4≤0
c. x1+ x5≤1
d. 100x1+ 200x2+ 150x3+ 75x4+ 300x5≤450
e. x1+ x2 + x3≤2

PTS : 1 BUDGETISATION DU CAPITAL

5. Grush Consulting a cinq projets à considérer. Chacun nécessitera du temps au cours des deux prochains trimestres.
selon le tableau ci-dessous.

Projet Temps dans le premier trimestre Temps au deuxième trimestre Revenu

A 5 8 12000
B 3 12 10000
C 7 5 15000
 D 2 3 5000
E 15 1 20000

Le revenu de chaque projet est également indiqué. Développez un modèle dont la solution maximiserait le revenu.
respecter le budget horaire de 25 au premier trimestre et de 20 au deuxième trimestre, et ne pas réaliser les deux projets C
et D.

RÉPONSE :

Laissez A = 1 si le projet A est sélectionné, 0 sinon ; idem pour B, C, D et E

Max 12000A + 10000B + 15000C + 5000D + 20000E

s.t. 5A + 3B + 7C + 2D + 15E ≤ 25
8A + 12B + 5C + 3D + 1E ≤ 20
C + D ≤1

PTS: 1 BUDGÉTISATION CAPITALE

6. La société Westfall a un contrat pour produire 10 000 tuyaux de jardin pour une grande chaîne de magasins à prix réduits.
Westfall a quatre machines différentes qui peuvent produire ce type de tuyau. Parce que ces machines sont
de différents fabricants et utilisant des technologies différentes, leurs spécifications ne sont pas les mêmes.

Coût fixe à définir Coût variable

Machine Augmenter la production Par tuyau Capacité
1 750 1.25 6000
2 500 1,50 7500
3 1000 1,00 4000
4 300 2,00 5000

a. Ce problème nécessite deux types différents de variables de décision. Définissez clairement chaque type.
b. L'entreprise souhaite minimiser le coût total. Donner la fonction objectif.
c. Donnez les contraintes pour le problème.
d. Écrivez une contrainte pour garantir que si la machine 4 est utilisée, la machine 1 ne peut pas l'être.

RÉPONSE :

a. Laissez Pjele nombre de tuyaux produits sur la machine i

Uje= 1 si la machine i est utilisée, = 0 sinon

b. min 750U1+ 500U2+ 1000U3+ 300U4 + 1,25P1+ 1,5P2+ P3+ 2P4

c. P1≤6000U1
P2≤7500U2
P3≤4000U3
P4≤5000U4
P1+ P2+ P3+ P4≥10000

c. U1+ U4 ≤1

PTS : 1 TOP: Fixed costs

Hansen Controls a reçu un contrat pour un grand nombre de panneaux de contrôle. Pour répondre à cela
demande, elle utilisera ses usines existantes à San Diego et Houston, et envisagera de nouvelles usines à Tulsa, St.
Louis et Portland. Les panneaux de contrôle finis doivent être expédiés à Seattle, Denver et Kansas City.
Les informations pertinentes sont données dans le tableau.

Expédition
Construction Coût pour
Sources Coût Destination Capacité
n:
Kansas
Seattle Denver Ville
San Diego ---- 5 7 8 2 500
Houston ---- 10 8 6 2 500
Tulsa 350 000 9 4 3 10 000
Saint-Louis 200 000 12 6 2 10 000
Portland 480 000 4 10 11 10 000
Demande 3 000 8 000 9 000

Développez un modèle dont la solution révélerait quelles usines construire et l'acheminement optimal.
horaire.

RÉPONSE :

Laissez Pijle nombre de panneaux expédiés de la source i à la destination j

Bje= 1 si l'usine i est construite, = 0 sinon (i = 3, 4, 5)

Min 350000B3+ 200000B4+ 480000B5+ 5P11+ 7P12+ 8P13+ 10P21+ 8P22+ 6P23
+ 9P31+ 4P32+ 3P33+ 12P41+ 6P42+ 2P43+ 4P51+ 10P52+ 11P53

s.t. P11+P12+ P13 ≤2500

P21 + P22+ P23≤2500
P31 + P32+ P33≤10000B3
P41+ P42+ P43≤10000B4
P51+ P52+ P53≤10000B5
P11+ P21+ P31+ P41+ P51= 3000
P12+ P22+ P32 + P42+ P52= 8000
P13+ P23+ P33+ P43+P53= 9000

PTS: 1 TOP : Conception du système de distribution

8. Simplon Manufacturing doit décider des processus à utiliser pour produire 1650 unités. Si la machine 1 est
utilisé, sa production sera entre 300 et 1500 unités. La machine 2 et/ou la machine 3 peuvent être utilisées uniquement
si la production de la machine 1 est d'au moins 1000 unités. La machine 4 peut être utilisée sans restrictions.

Fixé Variable Minimum Maximum

Machine coût cost Production Production
1 500 2.00 300 1500
2 800 0.50 500 1200
3 200 3,00 100 800
4 50 5,00 n'importe quel n'importe quel
 (INDICE : Utilisez une variable additionnelle 0-1 pour indiquer quand les machines 2 et 3 peuvent être utilisées.)

RÉPONSE :

Laissez Ujele nombre d'unités fabriquées par la machine i

Sje= 1 si la machine i est utilisée (nécessitant un réglage), = 0 sinon
K = 1 si la machine 1 produit au moins 1000 unités, = 0 sinon

Min 500S1+ 2U1+ 800S2+ 5U2+ 200S3+ 3U3+ 50S4+ 5U4

s.t. Vous1≥300S1
U1≤1500S1
U1≥1000K
S2≤K
S3≤K
U2≥500S2
U2≤1200S2
U3≥100S3
U3≤800S3
U4≤1650S4
U1+ U2+ U3+ U4= 1650

PTS: 1 Conception du système de distribution

9. Votre entreprise de messagerie express élabore de nouvelles zones pour l'emplacement des boîtes de dépôt pour
clients. La ville a été divisée en sept zones montrées ci-dessous. Vous avez ciblé six
emplacements possibles pour les boîtes de dépôt. La liste des boîtes de dépôt accessibles facilement depuis chaque zone
est énuméré ci-dessous.

Zone Peut être servi par des emplacements :

Centre financier 1, 2, 5, 6
Centre-ville Juridique 2, 4, 5
Détail Sud 1, 2, 4, 6
Commerce de détail Est 3, 4, 5
Fabrication Nord 1, 2, 5
Fabrication Est 3, 4
Ouest corporatif 1, 2, 6

Laissez xje= 1 si l'emplacement de la boîte de dépôt i est utilisé, 0 sinon. Développez un modèle pour fournir le plus petit nombre

des emplacements mais assurez-vous que chaque zone soit couverte par au moins deux boîtes.

RÉPONSE :

Min Σxje

s.t. x1+ x2+ x5+ x6≥2

x2+ x4+ x5≥2
x1+ x2+ x4+ x6≥2
 x3 + x4+ x5≥2
x1+x2+ x5≥2
x3+ x4≥2
x1+ x2+ x6≥2

PTS: 1 APPLICATIONS DE LA PROGRAMMATION LINÉAIRE ENTIÈRE

10. Considérez le problème auquel est confronté un directeur de loisirs de camp d'été qui essaie de choisir des activités.
pour un jour de pluie. Des informations sur les choix possibles sont données dans le tableau ci-dessous.

Popularité Popularité avec

Catégorie Activité Temps avec des campeurs Conseillers
(minutes)
Art 1−Peinture 30 4 2
2−Dessiner 20 5 2
3−Artisanat de la nature 30 3 1
Musique Groupe de 4 rythmes 20 5 5
Sports 5−Courses de relais 45 2 1
6−Basket-ball 60 1 3
Ordinateur 7−Internet 45 1 1
8−Écriture créative 30 4 3
9−Jeux 40 1 2

a. Donnez une définition générale des variables nécessaires dans ce problème afin que chaque activité
peut être considéré pour inclusion dans le programme du jour.
b. Les classements de popularité sont définis de sorte que 1 soit le plus populaire. Si l'objectif est de maintenir
les campeurs heureux, quel devrait être la fonction objectif ?

Écrivez des contraintes pour ces restrictions :

c. Au maximum une activité artistique peut être réalisée.
d. Pas plus de deux activités informatiques peuvent être effectuées.
e. Si le basket-ball est choisi, alors la musique doit être choisie.
Au moins 120 minutes d'activités doivent être sélectionnées.
Pas plus de 165 minutes d'activités peuvent être sélectionnées.
h. Pour garder le personnel heureux, la note du conseiller ne devrait pas être supérieure à 10.

RÉPONSE :

a. Laissez xje= 1 si l'activité i est choisie, 0 si ce n'est pas le cas, pour i = 1, ... , 9

b. Max 4x1+ 5x2+ 3x3+ 5x4+ 2x5+ 1x6+ 1x7+ 4x8+ 1x9
c. x1+ x2+ x3≤1
d. x7+ x8+ x9≤2
e. x6≤x4
f. 30x1+ 20x2+ 30x3+ 20x4+ 45x5 + 60x6+ 45x7+ 30x8+ 40x9 ≥120
g. 30x1+ 20x2+ 30x3+ 20x4+ 45x5+ 60x6+ 45x7+ 30x8+ 40x9≤165
h. 2x1+ 2x2+ 1x3+ 5x4+ 1x5 + 3x6+ 1x7+ 3x8+ 2x9≤10

PTS: 1 APPLICATIONS DE LA PROGRAMMATION ENTIER

11. La Tower Engineering Corporation envisage de réaliser plusieurs projets proposés pour le prochain
exercice fiscal. Les projets, le nombre d'ingénieurs et le nombre de personnel de soutien requis pour
Chaque projet et les bénéfices attendus pour chaque projet sont résumés dans le tableau suivant :

Projet
1 2 3 4 5 6
Ingénieurs requis 20 55 47 38 90 63
Personnel de soutien requis 15 45 50 40 70 70
Profit ($1,000,000s) 1.0 1.8 2.0 1,5 3.6 2.2

Formulate an integer program that maximizes Tower's profit subject to the following management
contraintes :

Utilisez pas plus de 175 ingénieurs

Utilisez pas plus de 150 personnels de soutien
3) Si l'un des projets 6 ou 4 est réalisé, les deux doivent être réalisés.
Le projet 2 ne peut être réalisé que si le projet 1 est terminé.
5) Si le projet 5 est réalisé, le projet 3 ne doit pas être réalisé et vice versa.
Pas plus de trois projets ne doivent être réalisés.

REP:

Max P1+ 1,8 P2+ 2P3+ 1.5P4+ 3.6P5+ 2,2P6

s.t. 20P1+ 55P2+ 47P3+ 38P4+ 90P5+ 63P6≤175

15P1+ 45P2+ 50P3+ 40P4+ 70P5+ 70P6≤150
P4−P6= 0
P1−P2≥0
P3+ P5≤1
P1+ P2+ P3+ P4+ P5+ P6≤3
Pje= 0 ou 1

PTS : 1 APPLICATIONS DE LA PROGRAMMATION EN NOMBRE ENTIER