EPFL RECHERCHE OPÉRATIONNELLE
Institut de Mathématiques IN/MA
J.-F. Hêche HIVER 2002/2003
SÉRIE D’EXERCICES 3
Les énoncés des séries et leurs corrigés ainsi que les copies des présentations sont disponibles
sur le site du cours : [Link]/cours/ro/2002-2003.
Problème 1
Formuler un programme linéaire équivalent aux problèmes d’optimisation suivants.
a)
Min z = |2x3 − x1 | + x2
s.c. 4x1 − x2 + 2x3 = 6
2x2 − 4x3 ≥ 4
x1 , x2 , x3 ≥ 0
b)
Max z = x1 + min{2x2 − 4,4x3 + x1 }
s.c. x1 + 3x2 + 2x3 ≤ 9
5x2 − x3 = 4
x1 , x2 , x3 ≥ 0
c)
Max z = x1 + |x1 − x2 |
s.c. x 1 + x2 ≤ 5
x2 − x 3 ≤ 7
5x1 + 2x2 − 8x3 ≤ 5
x1 , x2 , x3 ≥ 0
Problème 2
Monsieur Fildefer possède m balances. Obsédé par son poids, il se pèse chaque matin sur chacune
de ses balances et relève les valeurs {p 1 , . . . ,pm }. Évidemment ses balances sont rarement d’ac-
cord et, afin d’estimer son poids p, Monsieur Fildefer calcule la valeur p̂ minimisant la somme
des erreurs de mesure de ses m balances.
Modéliser le problème de la recherche de p̂ sous forme d’un programme linéaire.
Problème 3
Soit le triangle
α β
1
sur lequel ont été effectuées les mesures suivantes :
α = 40◦
α + β = 70◦
β + γ = 120◦
γ = 100◦
Ces mesures sont entachées d’erreurs. On aimerait donc déterminer des valeurs pour les angles
α, β et γ minimisant l’erreur maximale de ces mesures.
Formuler ce problème sous la forme d’un programme linéaire.
Problème 4 (MA)
Une entreprise de produits électroniques doit honorer un contrat de livraison de 20’000 radios
dans les quatre prochaines semaines. Son client paiera 40.- pour chacune des radios livrées à la
fin de la première semaine, 36.- pour celles livrées à la fin de la deuxième semaine, 32.- à la fin
de la troisième et 28.- à la fin de la quatrième.
Comme un employé n’assemble que 50 radios par semaine, l’entreprise ne peut satisfaire la
demande avec ses 40 employés actuels et doit donc engager du personnel supplémentaire. Chacun
des employés actuels de l’entreprise peut être retiré des lignes de production pour entraı̂ner
un groupe d’au plus trois nouveaux employés. Après une semaine d’instruction, chacun des
nouveaux employés peut soit être intégré à une ligne de production, soit devenir instructeur
pour un groupe de nouveaux arrivants.
Pour l’instant, l’entreprise n’a aucun autre contrat à honorer, impliquant que certains des em-
ployés peuvent devenir improductifs une fois que les 20’000 radios auront été produites. Une
fois qu’un employé a été engagé, il doit être payé jusqu’à la fin de la quatrième semaine et son
salaire hebdomadaire est de 400.- qu’il soit instructeur, assembleur ou improductif et de 200.-
pour sa semaine d’instruction initiale. Le coût de production d’une radio, salaires exceptés, est
de 10.-.
L’entreprise désire maximiser le montant de son profit net. Formuler ce problème sous forme
d’un programme linéaire.
Problème 5 (MA)
Pour chacun des systèmes suivants, déterminer le nombre de solutions basiques admissibles qu’il
possède ainsi que le nombre de sommets du polytope qu’il définit.
a) {x ∈ Rn | 0 ≤ xi ≤ 1, i = 1, . . . ,n}.
P
b) {x ∈ Rn | ni=1 xi ≤ 1, xi ≥ 0, i = 1, . . . ,n}.
P
c) {x ∈ Rn | ni=1 xi ≤ 1, 0 ≤ xi ≤ 1, i = 1, . . . ,n}.
4 novembre 2002 – JFH/sn
