Chap 00 Exercices

MATH-F-306 – Optimisation
chapitre 0

Modélisation

20 avril 2007
Optimisation – MATH-F-306
MATH-F-306 0. Modélisation
RAPPEL :
• Programme linéaire (PL) :
max cT x min cT x
scq : A1 x = b1 scq : A1 x = b1
A2 x 6 b2 A2 x > b2
où c ∈ Rn , x ∈ Rn , A1 ∈ Rm1 n , A2 ∈ Rm2 n , b1 ∈ Rm1 , b2 ∈ Rm2
RAPPEL :
• Programme linéaire en variables entières (PLE) :
max cT x min cT x
scq : A1 x = b1 scq : A1 x = b1
A2 x 6 b2 A2 x > b2
n
x∈Z x ∈ Zn
où c ∈ Rn , x ∈ Rn , A1 ∈ Rm1 n , A2 ∈ Rm2 n , b1 ∈ Rm1 , b2 ∈ Rm2
• Programme linéaire en variables mixtes (PLM) :
max cT1 x + cT2 y min cT1 x + cT2 y

scq : A11 x + A12 y = b1 scq : A11 x + A12 y = b1
A21 x + A22 y 6 b2 A21 x + A22 y > b2
n1
x∈R x ∈ Rn1
y ∈ Zn2 y ∈ Zn2
1
0. Modélisation MATH-F-306
2
MATH-F-306 – 0. Modélisation Exercice 0. 1
Exercice 0. 1
cf : Recherche opérationnelle pour ingénieurs I (de Werra, Liebling, Hêche) ; page 33
Un fabricant doit produire 120 kg d’un alliage comportant 30 % de plomb, 30 % de zinc et 40 % d’étain.
Sur le marché, on trouve les alliages suivants :
alliage 1 2 3 4 5 6 7 8 9
% plomb 10 10 40 60 30 30 30 50 20
% zinc 10 30 50 30 30 40 20 40 30
% étain 80 60 10 10 40 30 50 10 50
coût/kg 4.1 4.3 5.8 6.0 7.6 7.5 7.3 6.9 7.3
Comment obtenir un alliage de la composition voulue dont le coût est minimum ? Formuler ce problème
sous forme de programme linéaire.
Solution :
Notons pi le pourcentage de plomb dans l’alliage i.

zi le pourcentage de zinc dans l’alliage i.
ei le pourcentage d’étain dans l’alliage i.
ci le coût unitaire de production de l’alliage i.
Introduisons les variables suivantes : xi = le nombre de kg de l’alliage i utilisés.

Alors on obtient le programme linéaire suivant :
9
X
min ci · xi
i=1
X9
s.t. : pi · xi = 0.30 · 120
i=1
X9
zi · xi = 0.30 · 120
i=1
X9
ei · xi = 0.40 · 120
i=1
xi > 0 ∀ i = 1, . . . , 9
9
P
Question : Pourquoi peut-on laisser de côté la contrainte xi = 120 ?
i=1
3
Exercice 0. 1 0. Modélisation – MATH-F-306
4
Exercice 0. 2
cf : Syllabus (Geir Dahl) ex 0.1 page 8
Un étudiant veut décider quel type d’aliments manger de manière à minimiser ses dépenses, tout en conser-
vant une nourriture équilibrée. 5 types d’aliments F1 , . . . , F5 sont disponibles, chacun contenant une quantité
donnée d’énergie (kcal), de protéines (g) et de calcium (mg). L’étudiant veut que le menu à établir contienne
une quantité minimum (donnée) d’énergie, une quantité minimum de protéines et une quantité minimum de
calcium. Le prix par gramme de chaque type d’aliment est donné. De plus, on impose une borne supérieure
sur la quantité qu’on mange de chaque aliment. Formuler le problème comme un programme linéaire.
Solution :
Notons :
• ei = l’énergie contenue dans l’aliment Fi

pi = les protéines contenues dans l’aliment Fi
ci = le calcium contenu dans l’aliment Fi
• E = quantité minimale d’énergie nécessaire
P = quantité minimale de protéines nécessaire
C = quantité minimale de calcium nécessaire
• Ui est la borne supérieure sur la quantité de l’aliment Fi
• wi est le prix par gramme de l’aliment Fi
Nous utilisons les variables suivantes :

xi = quantité de l’aliment Fi à manger
Le programme linéaire résultant est :
5
X
min wi xi
i=1
5
X
s.t. : ei xi > E (besoin en énergie couvert)
i=1
X5
pi xi > P (besoin en protéines couvert)
i=1
X5
ci xi > C (besoin en calcium couvert)
i=1
0 6 xi 6 Ui ∀ i = 1, . . . , 5 (bornes pour chaque aliment)
5
6
Exercice 0. 3
On veut investir un capital K sur 4 périodes d’un an. Sur le marché il y a 3 projets d’investissements avec
les taux d’intérêts suivants :
projet
période A B C
1 0.03 0.02 0.025

2 0.01 0.04 0.03
3 0.02 0.015 0.02
4 0.025 0.01 0.01
Mais attention, chaque investissement doit se faire sur deux périodes consécutives, c’est-à-dire que si on
investit 1 000 e au projet B pour la 2e période, alors ces 1 000 e restent bloqués au projet B pour la 3e
période. Par contre les intérêts obtenus à la fin de la 2e période peuvent être réinvestis dans n’importe quel
projet lors de la 3e période.
Donner le programme linéaire qui maximise le profit à la fin de la 4e période.
Solution :
Utilisons les variables suivantes :
x(i i+1)j = argent investi dans le projet j lors de la période i (et qui reste donc au projet j
durant la période i + 1)
Notons tij le taux d’intérêt du projet j pour la période i. Alors on peut écrire le programme linéaire de la
manière suivante :
C
X C
X C
X C
X
max K + t1j x(12)j + t2j (x(12)j + x(23)j ) + t3j (x(23)j + x(34)j ) + t4j (x(34)j + x(4)j )
j=A j=A j=A j=A
C
X
s.t : x(12)j 6 K
j=A
XC C
X C
X
x(23)j 6 K − x(12)j + t1j x(12)j
j=A j=A j=A
XC XC XC C
X
x(34)j 6 K − x(23)j + t1j x(12)j + t2j (x(12)j + x(23)j )
j=A j=A j=A j=A
XC XC XC XC C
X
x(4)j 6 K − x(34)j + t1j x(12)j + t2j (x(12)j + x(23)j ) + t3j (x(23)j + x(34)j )
j=A j=A j=A j=A j=A
xij > 0 ∀ i, j
Pendant chaque période i, on peut donc investir le capital initial, moins ce qu’on a investi à la période i − 1,
plus les intérêts déjà obtenus.
7
ou bien :
en utilisant les variables :
xij = montant total dans le projet j lors de la période i
Alors le programme linéaire devient :

4 X
X C
max K + tij xij
i=1 j=A
C
X i−1 X
X C
s.t : xij 6 K + tkj xkj ∀ i = 1, . . . , 4 (argent disponible)
j=A k=0 j=A
x2j > x1j ∀ j = A, . . . , C (argent de la période 1 bloqué)

x3j > x2j − x1j ∀ j = A, . . . , C (argent de la période 2 bloqué)

x4j > x3j − x2j − x1j ∀ j = A, . . . , C (argent de la période 3 bloqué)
xij > 0 ∀ i, ∀j
8
Exercice 0. 4
Considérons le problème suivant :
min 2 · x1 + 3 · |x2 − 10|

s.t. : |x1 + 2| + |x2 | 6 15
Reformuler ce problème sous forme de programme linéaire.
Solution :
On introduit une variable auxiliaire z1 pour remplacer la valeur absolue dans la fonction objective.
min 2 x1 + 3 z1
s.t. : z1 > x2 − 10
z1 > − x2 + 10
x1 + 2 + x2 6 15
x1 + 2 − x2 6 15
− x1 − 2 + x2 6 15
− x1 − 2 − x2 6 15
9
10
Exercice 0. 5
Une raffinerie mélange 5 types d’essence brute pour obtenir deux qualités de carburant : normal et super.
Le nombre de barils disponibles par jour, le taux de performance ainsi que le prix par baril est donné pour
chaque type d’essence brute dans le tableau suivant :
Type d’essence Performance Barils disponibles Prix / baril ($)
1 70 2000 0.80
2 80 4000 0.90
3 85 4000 0.95
4 90 5000 1.15
5 99 5000 2.00
Le carburant normal doit avoir un taux de performance d’au moins 85 et le super d’au moins 95. Des contrats
obligent la raffinerie à produire au moins 8000 barils de super par jour. Mais ils peuvent vendre toute leur
production aux prix suivants : 2.85 $ par baril de carburant normal et 3.75 $ par baril de super. Supposons
que le taux de performance est proportionnel au mélange (p.ex. un mélange 12 – 12 d’essences brutes de type
1 et 2 donne un taux de performance de 75).
Donner une formulation sous forme de programme linéaire qui maximise le profit de la raffinerie.
Solution :
Introduisons les notations suivantes :
pi est la performance du type i
ci est le cout d’achat d’un baril de type i
di est le nombre de barils disponibles du type i
xij = nombre de barils de type i utilisés pour la production du carburant j

1 pour le normal
où j =
2 pour le super
Alors on obtient le programme linéaire suivant :
5
X 5
X 5 X
X 2
max 2.85 · xi1 + 3.75 · xi2 − ci · xij
i=1 i=1 i=1 j=1
5
X
s.t. : xi2 > 8 000 ( production minimale de super )
i=1
5
X 5
X
pi xi1 > 85 · xi1 ( performance de normal )
i=1 i=1
X5 X5
pi xi2 > 95 · xi2 ( performance de super )
i=1 i=1
2
X
xij 6 di ∀i ( disponibilités )
j=1
xij > 0 ∀ i, ∀ j
11
12
Exercice 0. 6
Considérons le problème de transport suivant : une firme dispose de m entrepôts et de n clients. Il faut livrer
un certain produit des entrepôts vers les clients. Notons oi la quantité du produit stockée dans l’entrepôt
i, ∀ i = 1, . . . , m et dj la quantité du produit demandée par le client j, ∀ j = 1, . . . , n. Le coût unitaire de
transport de l’entrepôt i vers le client j est noté cij . La firme veut minimiser le coût de transport total, en
satisfaisant tous les clients.
Donner une formulation de ce problème sous forme de programme linéaire.
Solution :
On utilise les variables suivantes :
xij = quantité livrée au client j à partir de l’entrepôt i
Alors on peut modéliser le problème de la manière suivante :

m X
X n
min cij xij
i=1 j=1
n
X
s.t. : xij 6 oi ∀ i = 1, . . . , m
j=1
m
X
xij = dj ∀ j = 1, . . . , n
i=1
xij > 0 ∀ i = 1, . . . , m ∀ j = 1, . . . , n
13
14
Exercice 0. 7 (Cutting Stock Problem)
On dispose d’un nombre illimité de barres de longueur 10. On veut découper ces barres pour obtenir des
petites barres. Ainsi on veut obtenir :
32 petites barres de longueur 7

15 5
46 4
52 3
Formuler ce problème sous forme de programme linéaire en variables entières de façon à minimiser les chutes.
(Les petites barres produites en trop sont comptées comme chutes.)
Solution :
Introduisons les notations suivantes :
• L = 10 (Longueur d’une barre)

• di = demande pour le type i de petites barres
• li = longueur d’une petite barre de type i.
On introduit la notion de pattern, c’est-à-dire les différentes possibilités de découper une longue barre. Ainsi
on énumère tous les patterns :
pattern 7 cm 5 cm 4 cm 3cm chute

1 1 0 0 1 0 cm
2 1 0 0 0 3 cm
3 0 2 0 0 0 cm
4 0 1 1 0 1 cm
5 0 1 0 1 2 cm
6 0 1 0 0 5 cm
7 0 0 2 0 2 cm
8 0 0 1 2 0 cm
9 0 0 1 1 3 cm
10 0 0 1 0 6 cm
11 0 0 0 3 1 cm
12 0 0 0 2 4 cm
13 0 0 0 1 7 cm
Notons :
cj = chute pour le pattern j

aij = nombre de barres de type i qu’on obtient si on découpe selon le pattern j
Alors on peut utiliser les variables suivantes :
xj = nombre de barres que l’on découpe selon le pattern j
15
Et on obtient le programme linéaire le suivant :

13
X
min cj xj
j=1
13
X
s.t. : aij xj = di ∀ i = 1, . . . , 4
j=1
xj ∈ Z+ ∀ j = 1, . . . , 13
ou bien :
On n’utilise que les patterns qui ne sont contenus dans aucun autre pattern, c’est-à-dire les patterns 1, 3, 4,
5, 7, 8 et 11
Et alors le programme linéaire devient :
7
X 4
X
min 10 xj − li di
j=1 i=1
7
X
s.t. : aij xj > di ∀ i = 1, . . . , 4
j=1
xj ∈ Z+ ∀ j = 1, . . . , 7
16
Exercice 0. 8
Soit un ensemble d’inégalités linéaires aTi x 6 bi , où i = 1, . . . , m (avec ai ∈ Rn , bi ∈ R).

Formuler un modèle (uniquement des contraintes – sans fonction objective) pour lequel un point x ∈ Rn
satisfait au moins k des m contraintes (k 6 m) et, de plus, satisfait 0 6 xj 6 M , pour tout j = 1, . . . , n.
Solution :
On introduit les variables :

1 si x satisfait l’inégalité i
yi = ∀ i = 1, . . . , m
0 sinon
Or, comme 0 6 xj 6 M pour tout j = 1, . . . , n, il existe un M̄ tel que si x ne satisfait pas l’inégalité i, on a
que bi < aTi x 6 M̄ , pour tout i = 1, . . . , m.
nP o
On peut par exemple prendre M̄ = max max{0, aij } M .
i j
Alors on peut formuler le modèle comme suit :
m
X
yi > k
i=1
n
X
aij xj 6 bi + (M̄ − bi ) · (1 − yi ) ∀ i = 1, . . . , m
j=1
0 6 xj 6 M ∀ j = 1, . . . , n
yi ∈ {0, 1} ∀ i = 1, . . . , m
Remarque : Si aTi x 6 bi , alors yi peut ête égale à 1 ou à 0 dans cette formulation. Mais comme
P
yi > k,
i
on est sûr qu’il y a au moins k différents yi qui valent 1.
17
18
Exercice 0. 9
Soient P1 , . . . , Pn des propositions logiques, chacune étant vraie ou fausse. En introduisant des variables
binaires, représenter les relations suivantes par des contraintes linéaires :
1. P1 est vraie.
2. Toutes les propositions sont vraies.
3. Au moins k propositions sont vraies.
4. Si P1 est vraie, alors P2 est vraie.
5. P1 et P2 sont équivalentes.
6. Si P1 ou P2 est vraie, alors au plus deux des propositions P3 , . . . , Pn sont vraies.
Solution :

1 si Pi est vraie
xi =
0 sinon
Alors les propositions logiques peuvent être modélisées comme suit :
1. x1 = 1
2. x1 = 1, x2 = 1, . . . , xn = 1
P
ou bien : xi = n
i
P
3. xi > k
i
4. x1 6 x2
5. x1 = x2
 n
P


 xi 6 2 x1 + (n − 2) (1 − x1 ) = n − 2 − (n − 4) x1
i=3
6. Pn
xi 6 2 x2 + (n − 2) (1 − x2 ) = n − 2 − (n − 4) x2



i=3
19
20
Exercice 0. 10 (Problème du voyageur de commerce)
On considère un ensemble de n villes et les distances cij qui les séparent. Le problème du voyageur de
commerce consiste à déterminer le tour le plus court possible passant exactement une fois par chaque ville
et revenant au lieu de départ (cycle Hamiltonien). Formuler le problème comme un programme linéaire en
nombres entiers.
Solution :
Il y a n villes et nous notons cij la distance entre la ville i et la ville j. Pour modéliser le problème du
voyageur de commerce, nous utilisons les variables suivantes :

1 si le voyageur va de i vers j
xij =
0 sinon
Alors le problème du voyageur de commerce peut être modélisé comme suit :

n X
X n
min cij xij
i=1 j=1
n
X
s.t. : xij = 1 ∀j
i=1
Xn
xij = 1 ∀i
j=1
XX
xij 6 |S| − 1 ∀ S ⊂ {1, . . . , n} avec 2 6 |S| 6 n − 1
i∈S j∈S
ou
XX
xij > 1 ∀ S ⊂ {1, . . . , n} avec ∅ =
6 S 6= {1, . . . , n}
i∈S j ∈S
/
xij ∈ {0, 1} ∀ i, ∀ j
La première contrainte dit qu’il entre exactement 1 fois dans chaque ville, tandis que la deuxième dit qu’il
sort exactement 1 fois de chaque ville.
Ceci n’est pas suffisant, car on pourrait aboutir ainsi à plusieurs petits tours, donc il reste à éliminer les sous–
tours en mettant soit les troisièmes contraintes (élimination de sous-tours) soit les quatrièmes contraintes
(connexité).
21
22
Exercice 0. 11
Un organisateur d’une soirée cocktails dispose des alcools suivants : 1.2 litres de whisky, 1.8 litres de vodka,
1.6 litres de vermouth blanc, 1.8 litres de vermouth rouge, 0.6 litres de cognac et de 0.5 litres de liqueur au
café. Il veut offrir 5 cocktails différents, à savoir :
- Chauncy : 2/3 whisky, 1/3 vermouth rouge

- Black Russian : 3/4 vodka, 1/4 liqueur
- Sweet Italian : 1/2 cognac, 1/4 vermouth rouge, 1/4 vermouth blanc
- Molotov Cocktail : 2/3 vodka, 1/3 vermouth blanc
- Whisky on the Rocks : 1/1 whisky
Chaque cocktail a un contenu de 10 cl. L’organisateur veut mixer les cocktails de manière à maximiser le
nombre total de cocktails servis. En plus il pense que le Molotov Cocktail se vend bien et il veut donc en
avoir au moins deux fois le nombre de cocktails Black Russian.
a. Formuler ce problème sous forme de programme linéaire en variables entières.
L’organisateur aime bien le vodka et il est d’accord de diminuer le nombre de cocktails servis de 5 s’il reste
au moins 0.25 litres de vodka. (c’est-à-dire : s’il reste 0.25 litres de vodka, cela est équivalent à 5 cocktails
servis)
b. Comment faire pour ajouter ceci à la formulation précédente.
Solution :
a. Les variables utilisées sont :

xi = nombre de cocktails de type i servis.
Nous utilisons les indices suivants pour les différents cocktails :
Chauncy → 1
Black Russian → 2
Sweet Italian → 3
Molotov Cocktail → 4
Whisky on the Rocks → 5
La modélisation est la suivante :
5
X
max xi
i=1
2
s.t. : 3 x1 + x5 6 12 (whisky)
3 2
4 x2 + 3 x4 6 18 (vodka)
1 1
4 x3 + 3 x4 6 16 (vermouth blanc)
1 1
3 x1 + 4 x3 6 18 (vermouth rouge)
1
2 x3 6 6 (cognac)
1
4 x2 6 5 (liqueur au café)
2 x2 − x4 6 0 (Molotov > 2 B. Russians)
xi ∈ N ∀i
23
b. Dans ce cas on rajoute une variable y qui nous dit si oui ou non il reste 0.25 litres de vodka.
La fonction objective devient alors :
5
X
max xi + 5 y
i=1
Et la contrainte pour le vodka devient :

3 2
4 x2 + 3 x4 6 18 − 2.5 y (vodka)
Bien sûr il faut que la variable y soit binaire :
y ∈ {0, 1}
24
Exercice 0. 12
Considérons le problème d’une commune en Belgique. Dans la commune, il y a I quartiers, J écoles, et G

classes dans chaque école (p.ex. 1ère – 6e primaire). Chaque école j ∈ J à une capacité de Cjg étudiants pour
la classe g ∈ G. Dans chaque quartier i ∈ I, il y a Sig étudiants qui veulent aller en classe g ∈ G. La distance
entre le quartier i ∈ I et l’école j ∈ J est dij . Donner un programme linéaire, dont l’objectif est d’envoyer
tous les étudiants à la bonne classe, tout en minimisant la distance totale parcourue par les étudiants.
Solution :
xijg = nombre d’étudiants résidant dans le quartier i, qui vont à la classe g de l’école j.
Alors on peut formuler le problème de la manière suivante :

X X X
min dij · xijg
i∈I j∈J g∈G
X
s.t. : xijg = Sig ∀ i, ∀ g ( tout étudiant du quartier i fréquente sa classe g )
j
X
xijg 6 Cjg ∀ j, ∀ g ( dans chaque école j, la capacité de toute classe g
est respectée )
xijg ∈ N ∀ i, ∀ j, ∀ g
25
26
Exercice 0. 13
Regardons le problème d’un éleveur de poules. Supposons que pendant une période de 2 semaines, une poule
peut soit pondre 12 oeufs, soit en éclore 4. Supposons aussi que les poussins peuvent pondre des oeufs après
une période supplémentaire de 2 semaines. Après 4 périodes, l’éleveur veut vendre les oeufs à 0.5 e la pièce
et les poules / poussins à 3 e la pièce. Quelle est le meilleur plan d’élevage si au début l’éleveur possède
100 poules et s’il veut en avoir au moins 80 à la fin de la 4e période ? (il suffit de donner la formulation du
problème)
Solution :
Définissons les variables suivantes :
x1 = nombre de poules qui pondent lors de la période i, i = 1, . . . , 4
y1 = nombre de poules qui éclorent lors de la période i, i = 1, . . . , 4
z = nombre de poules qui sont vendus après la 4e période
On obtient alors le programme linéaire suivant :
4
X
max (12 · 0.5 · x1 ) + 3 z
i=1
s.t. : x1 + y1 = 100 (poules au début de la 1ère période)

x2 + y2 = x1 + y1 (poules à la 2e période)
x3 + y3 = x2 + y2 + 4 y1 (poules à la 3e période)
x4 + y4 = x3 + y3 + 4 y2 (poules à la 4e période)
z 6 x4 + y4 + 4 y3 + 4 y4 − 80 (garder 80 poules après la 4e période)
xi , yi , z ∈ Z+ ∀ i = 1, . . . , 4
27
28
Exercice 0. 14
Considérons N clients et M localisations potentielles de centres. Le problème du p-Centre consiste à localiser

p centres parmi les M localisations possibles, puis à affecter chaque client au centre qui lui est le plus proche,
de façon à minimiser le rayon (c’est-à-dire la distance maximale entre un client et le centre qui le dessert).
Ce problème a plusieurs applications dont les plus connues sont les problèmes de localisation de casernes de
pompiers ou de dépôts d’ambulances.
Soient N le nombre de clients notés C1 , C2 , . . . , CN ;
M le nombre de sites potentiels pour les centres F1 , F2 , . . . , FM ;
dij la distance de Ci à Fj .
Le problème est de trouver un sous-ensemble S de {1, . . . , M } tel que :
- |S| 6 p

- rayon(S) = max min dij est minimum
i=1,...,N j∈S
Donner une formulation de ce problème sous forme de programme linéaire (éventuellement en variables
entières). Expliquer.
Solution :
Utilisons les variables suivantes :
• yj = 1 ssi le centre Fj est ouvert

• xij = 1 ssi le client Ci est affecté au centre Fj

• z = max min dij
i=1,...,N j∈S
Alors on peut écrire le problème de la forme suivante :
min z
M
X
s.t. : yj 6 P
j=1
XM
xij = 1 ∀ i = 1, . . . , N
j=1
xij 6 yj ∀ i = 1, . . . , N ∀ j = 1, . . . M
M
X
dij xij 6 z ∀ i ∈ 1, . . . , N
j=1
xij ∈ {0, 1} ∀ i = 1, . . . , N ∀ j = 1, . . . , M
yj ∈ {0, 1} ∀ j = 1, . . . , M
z>0
29
30
Exercice 0. 15
cf : Model Building in Mathematical Prog. (H.P. Williams) Wiley ; page 262
Considérons le cube 3 x 3 x 3 composé de 27 boı̂tes (voir Figure ci-dessous).
On dit que 3 boı̂tes sont sur une ligne s’ils se trouvent sur une même ligne horizontale, verticale ou diagonale.
On considère les diagonales sur tout plan horizontal et vertical et les diagonales reliant 2 sommets opposés
du cube. (En tout il y a 49 lignes !)
On dispose maintenant de 13 boules blanches et de 14 boules noires. Arranger les boules (1 par boı̂te) de
manière à minimiser le nombre de lignes contenant que des boules de la même couleur !
Donner une formulation de ce problème sous forme de programme linéaire ! (sans le résoudre)
Solution :
On numérote toutes les boı̂tes du cube (de 1 à 27). Alors on associe à chaque boı̂te une variable binaire xi ,
interprétée de la manière suivante :

1 si la boı̂te i contient une boule noire
xi =
0 si la boı̂te i contient une boule blanche
Il y a 49 lignes différentes dans le cube. A chaque ligne on associe une variable binaire yj ayant la signification
suivante :

1 si la ligne j contient que des boules de la même couleur
yj =
0 s’il y des boules de couleurs différentes dans la ligne j
Commençons par modéliser la fonction objective : on veut minimiser le nombre de lignes contenant des
boules de couleur identique :
49
X
min yj
j=1
Ensuite on impose qu’on dispose de 14 boules noires :

27
X
xi = 14
i=1
Maintenant il faut encore s’assurer que si on a trois boules identiques sur la ligne j, alors la variable yj doit
prendre la valeur 1. Notons j1, j2 et j3 les 3 boı̂tes situées sur la ligne j. On doit donc modéliser :

xj1 + xj2 + xj3 = 0 
ou ⇒ yj = 1
xj1 + xj2 + xj3 = 3

31
Ceci peut être fait en introduisant les contraintes suivantes :
yj > 1 − xj1 − xj2 − xj3

∀ j = 1, . . . , 49
yj > xj1 + xj2 + xj3 − 2
Remarque : ces deux dernières contraintes ne garantissent pas que si yj = 1 alors toutes les boules de la
ligne j ont la même couleur. Mais ensemble avec la fonction objective, ceci sera garanti pour
la solution optimale.
32
Exercice 0. 16
cf : La Recherche Opérationnelle (Nobert, Ouellet et Parent) Gaetan Morin ; page 88

cf : Model Building in Mathematical Prog (H.P. Williams) Wiley ; page 260
Regardons un problème de génie minier qui a fait l’objet de nombreux articles dans les revues de recherche
opérationnelle.
Pour juger de la rentabilité d’un projet de mine à ciel ouvert, les ingénieurs miniers découpent (de manière
virtuelle) de gros blocs cubiques de taille uniforme dans le sol et le sous-sol porteurs de minerai. Ils estiment
ensuite par carottage les revenus à tirer de l’extraction de chaque bloc. Pour extraire le minerai d’un bloc,
il faut, dans les opérations à ciel ouvert, extraire les blocs qui le chapeautent. La taille des blocs est fixée
en tenant compte du coefficient de friction de la pierraille engendrée par les opérations d’extraction : il ne
faut pas que l’escalier de géant, qui s’enfonce dans le sol et est formé de banquettes et de gradins, ait une
déclivité si prononcée qu’elle occasionne des éboulis, toujours périlleux.
La figure suivante illustre la coupe verticale d’une partie d’un sous-sol minéralisé dont l’exploitation n’est
possible qu’à ciel ouvert.
A B C
D E
F
Si on veut extraire le bloc F de la figure précédente, il faut d’abord extraire les blocs de surface A, B et C,
qui peuvent ne pas contenir de minerai, et les blocs D et E, qui seront sans doute plus coûteux à extraire
que les blocs situés en surface.
Imaginons un carré de 100 m de côté tracé sur la surface du sol. Il y a donc, au niveau du sol, 16 blocs de
25 m de côté. Au deuxième niveau il y en a 9, au troisième niveau 4, et au quatrième niveau il n’y en a
qu’un seul. Ces blocs forment une pyramide inversée de 30 blocs, tous de 25 m d’arête (voir figure suivante).
Pour chacun des blocs les ingénieurs ont estimé la teneur en métal (pourcentage par rapport au métal pur).
La vente d’un bloc de « métal pur 100 % » rapporterait 200 000 e. On a les teneurs en métal suivantes :
niveau 1 (surface) niveau 2 niveau 3 niveau 4
1.50 1.50 1.50 0.75

4.0 4.0 2.0
1.50 2.00 1.50 0.75 12.0 6.0
3.0 3.0 1.0 6.0
1.00 1.00 0.75 0.50 5.0 4.0
2.0 2.0 0.5
0.75 0.75 0.50 0.25
33
Les coûts d’extraction augmentent avec la profondeur. Pour les différents niveaux, on obtient les coûts
suivants pour extraire un bloc :
- niveau 1 : 3 000 e
- niveau 2 : 6 000 e
- niveau 3 : 8 000 e
- niveau 4 : 10 000 e
Trouver une modélisation sous forme de programme linéaire qui décide quels blocs il faut extraire si on veut
maximiser le gain net.
Solution :
On commence par numéroter tous les blocs (de 1 à 30).
On peut alors utiliser les variables suivantes :

1 si le bloc i est exploité
yi =
0 sinon
On note aussi :
ci = teneur en métal du bloc i
di = coût d’extraction du bloc i
Soit alors le profit du bloc i :

pi = 200 000 · ci − di
Alors on peut formuler la fonction objective qui essaie de maximiser le profit :

30
X
max pi y i
i=1
Si on veut extraire un bloc, on doit être sûr qu’on extrait aussi les 4 blocs qui reposent sur le bloc en question.
Par exemple, si on veut extraire le bloc 1 (jaune) sur la figure ci-dessus, il faut aussi extraire (au moins) les
blocs 2,3,4 et 5 (vert). Ainsi on doit rajouter pour tous les blocs des niveaux 2,3 et 4 les contraintes
suivantes :


 y1 6 y2
y1 6 y3

y 6 y4
 1


y1 6 y5
ce qui peut être remplacé par la contrainte :
1
yi 6 4 · (y2 + y3 + y4 + y5 )
Il ne faut pas oublier de préciser que les variables yi sont binaires :

yi ∈ {0, 1}
34
Exercice 0. 17
cf : Programmation linéaire (Guéret, Prins, Sevaux) Eyrolles ; page 143
Une PME, spécialisée dans la construction de cartes à puces, désire améliorer la production de ses cartes
les plus vendus. Lors de la production de ces cartes, la PME a besoin de certains composants électroniques,
qu’elle produit elle-même. Un facteur de succès réside dans une bonne planification de la production de ces
composants. La demande en composants est dans ce cas interne et facile à anticiper.
Les quatre composants dont la production est à planifier sur six mois sont notés sous les références X43-M1,
X43-M2, Y54-N1 et Y54-N2. La production de ces composants est sensible aux variations des niveaux en
production, et chaque changement entraı̂ne un coût de vérification non négligeable. L’entreprise va alors
tenter de minimiser les coûts liés à ces changements, elle prendra aussi en compte les coûts de production
et les coûts de stockage.
Quand le niveau total de la production change, des réglages machines et des vérifications sont à effectuer
pour le mois en cours. Le coût associé est proportionnel à la quantité totale produite en plus ou en moins
par rapport au mois précédent. Le coût pour une augmentation est de 1 e alors que celui d’une diminution
est seulement de 0.5 e. Notons qu’un changement de niveau de production n’est autre que la différence entre
la quantité totale produite lors du mois en question et la quantité totale produite lors du mois précédent.
Les informations concernant la demande par période, les coûts de production et de stockage ainsi que le
stock initial et le stock final désirés pour chacun des produits sont repris au tableau ci-dessous.
Demandes Coûts Stocks
Mois 1 2 3 4 5 6 Production Stockage Initial Final
X43-M1 1 500 3 000 2 000 4 000 2 000 2 500 20 0.4 10 50

X43-M2 1 300 800 800 1 000 1 100 900 25 0.5 0 10
Y54-N1 2 200 1 500 2 900 1 800 1 200 2 100 10 0.3 50 30
Y54-N2 1 400 1 600 1 500 1 000 1 100 1 200 15 0.3 0 10
Trouver une modélisation sous forme de programme linéaire qui cherche le plan de production qui minimise la
somme des coûts de changement du niveau de production, des coûts de production et des coûts de stockage ?
Solution :
Notons n le nombre de produits, m le nombre de mois et dij la demande du produit i au mois j. Soient CPi
le coût de production de chaque unité de produit i, CSi le coût de stockage d’une unité de produit i, CA le
coût unitaire d’augmentation et CB le coût unitaire de baisse des niveaux de production.
Notons encore si0 le stock initial du produit i et SFi le stock final souhaité.
Les variables xij et sij représentent la quantité produite et le niveau de stock du produit i en période j.
• Commençons par les contraintes d’équilibre des stocks (production et stock précédent est égal à la
demande et le nouveau stock) :
xij + si j−1 = dij + sij ∀ i = 1, . . . , n ∀ j = 1, . . . , m
• Le stock final doit être respecté :

sim > SFi ∀ i = 1, . . . , n
35
• Pour calculer les changemements des niveaux de production, nous avons besoin de deux variables
supplémentaires yj et zj qui représentent les augmentations et les diminutions des productions en
période j. Rappelons qu’un changement de niveau de production n’est autre que la différence entre
la quantité totale produite lors du mois j et la quantité totale produite lors du mois j − 1. Si cette
différence est positive, il s’agit alors d’une augmentation de production, sinon ce sera une baisse. Ce
changement s’exprimera par la valeur de yj − zj .
Comme on ne peut augmenter et diminuer le niveau de production en même temps, une des deux va-
riables sera automatiquement égale à 0, l’autre représentera soit une augmentation, soit une diminution.
Ceci peut être traduit par les contraintes suivantes :
n
X n
X
xij − xi j−1 = yj − zj ∀ j = 2, . . . , m
i=1 i=1
Notons qu’il n’existe pas de valeurs pour y1 et z1 comme c’est le début de la planification.
• La fonction objective est la somme des coûts de production, stockage et changement de niveau :
 
X n m
X m
X m
X m
X
min  cpi · xij + csi · sij + ca ·
 yj + cb · zj
i=1 j=1 j=1 j=2 j=2
• Il ne faut pas oublier le domaine de définition des variables utilisées :
xij > 0 ∀ i = 1, . . . , n ∀ j = 1, . . . , m
sij > 0 ∀ i = 1, . . . , n ∀ j = 1, . . . , m
yj > 0 ∀ j = 1, . . . , m
zj > 0 ∀ j = 1, . . . , m
36

Chap 00 Exercices

Transféré par

Droits d'auteur :

Formats disponibles

Chap 00 Exercices

Transféré par

Informations du document

Description originale:

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chap 00 Exercices

Transféré par

Droits d'auteur :

Formats disponibles

MATH-F-306 – Optimisation

• Programme linéaire (PL) :

où c ∈ Rn , x ∈ Rn , A1 ∈ Rm1 n , A2 ∈ Rm2 n , b1 ∈ Rm1 , b2 ∈ Rm2

• Programme linéaire en variables entières (PLE) :

où c ∈ Rn , x ∈ Rn , A1 ∈ Rm1 n , A2 ∈ Rm2 n , b1 ∈ Rm1 , b2 ∈ Rm2

• Programme linéaire en variables mixtes (PLM) :

max cT1 x + cT2 y min cT1 x + cT2 y

cf : Recherche opérationnelle pour ingénieurs I (de Werra, Liebling, Hêche) ; page 33

Notons pi le pourcentage de plomb dans l’alliage i.

Introduisons les variables suivantes : xi = le nombre de kg de l’alliage i utilisés.

cf : Syllabus (Geir Dahl) ex 0.1 page 8

• ei = l’énergie contenue dans l’aliment Fi

Nous utilisons les variables suivantes :

0 6 xi 6 Ui ∀ i = 1, . . . , 5 (bornes pour chaque aliment)

1 0.03 0.02 0.025

Alors le programme linéaire devient :

Considérons le problème suivant :

min 2 · x1 + 3 · |x2 − 10|

Reformuler ce problème sous forme de programme linéaire.

Type d’essence Performance Barils disponibles Prix / baril ($)

xij = quantité livrée au client j à partir de l’entrepôt i

Alors on peut modéliser le problème de la manière suivante :

Exercice 0. 7 (Cutting Stock Problem)

32 petites barres de longueur 7

Introduisons les notations suivantes :

• L = 10 (Longueur d’une barre)

pattern 7 cm 5 cm 4 cm 3cm chute

cj = chute pour le pattern j

Alors on peut utiliser les variables suivantes :

xj = nombre de barres que l’on découpe selon le pattern j

Et on obtient le programme linéaire le suivant :

cf : Syllabus (Geir Dahl) ex 0.2 page 8

Soit un ensemble d’inégalités linéaires aTi x 6 bi , où i = 1, . . . , m (avec ai ∈ Rn , bi ∈ R).

cf : Syllabus (Geir Dahl) ex 0.3 page 8

Alors les propositions logiques peuvent être modélisées comme suit :

Exercice 0. 10 (Problème du voyageur de commerce)

Alors le problème du voyageur de commerce peut être modélisé comme suit :

- Chauncy : 2/3 whisky, 1/3 vermouth rouge

a. Les variables utilisées sont :

Et la contrainte pour le vodka devient :

Bien sûr il faut que la variable y soit binaire :

Considérons le problème d’une commune en Belgique. Dans la commune, il y a I quartiers, J écoles, et G

Alors on peut formuler le problème de la manière suivante :

s.t. : x1 + y1 = 100 (poules au début de la 1ère période)

Considérons N clients et M localisations potentielles de centres. Le problème du p-Centre consiste à localiser

• yj = 1 ssi le centre Fj est ouvert

Alors on peut écrire le problème de la forme suivante :

cf : Model Building in Mathematical Prog. (H.P. Williams) Wiley ; page 262

Considérons le cube 3 x 3 x 3 composé de 27 boı̂tes (voir Figure ci-dessous).

Ensuite on impose qu’on dispose de 14 boules noires :

Ceci peut être fait en introduisant les contraintes suivantes :

yj > 1 − xj1 − xj2 − xj3

cf : La Recherche Opérationnelle (Nobert, Ouellet et Parent) Gaetan Morin ; page 88

niveau 1 (surface) niveau 2 niveau 3 niveau 4

1.50 1.50 1.50 0.75

Soit alors le profit du bloc i :

Alors on peut formuler la fonction objective qui essaie de maximiser le profit :

Il ne faut pas oublier de préciser que les variables yi sont binaires :

cf : Programmation linéaire (Guéret, Prins, Sevaux) Eyrolles ; page 143