TD (solution)
Techniques d’optimisation
Exercice 1
Modélisation de problème
Choix des variables
X1 le nombre kits de 400 DA
X2 le nombre kits de 500 DA
Fonction objectif à maximiser
Max Z=400X1+500X2
Contraintes à respecter
10X1+10X2≤50 (leds)
10X1+20X2≤80 (resistances)
20X1+10X2≤80 (switches)
Exercice 1
Max Z=400X1+500X2
10X1+10X2≤50
10X1+20X2≤80
20X1+10X2≤80
X1 0 et X2 0
Exercise 2
Modélisation de problème
Choix des variables
Notons X1 le nombre d'œufs Extra et X2 le nombre d'œufs Sublime à
produire
Fonction objectif à maximiser
max Z = 20X1 + 30 X2
Contraintes à respecter
X1+3X2 ≤ 18 (cacao)
X1+X2 ≤8 (noisettes)
2X1+X2 ≤ 14 (lait)
Exercise 2
Modélisation de problème
max Z = 20X1 + 30 X2
X1+3X2 ≤ 18
X1+X2 ≤8
2X1+X2 ≤ 14
X1 0 et X2 0
Exercice 3
Modélisation de problème
Choix des variables
Soit XA le nombre d'heures travaillées par A
XB le nombre d'heures travaillées par B.
Fonction objectif à minimiser
f (XA, XB) min Z = 300 XA + 200 XB (min Z = 300 XA + 200 XB)
Contraintes à respecter
A et B ne peuvent pas travailler plus de 11 heures.
XA + XB 11
A produit par heure 14 cartes, dont 10 du type "Variateur". B produit par heure 12
cartes, dont 5 du type "Variateur".
10 XA + 5 XB 50
A produit par heure 14 cartes, dont 4 du type "Alarme". B produit par heure 12 cartes,
dont 7 du type "Alarme".
4 XA + 7 XB 50
XA 0 et XB 0
Problème
min Z = 3 XA + 2 XB
XA + XB 11
10 XA + 5 XB 50
4 XA + 7 XB 50
XA 0 et XB 0
Solution XA=2, XB=6 min Z=18 heures
Exercice 4
On note par :
x1= la quantité du plat 1 consommée par le client ,
x2= la quantité du plat 2 consommée par le client,
x3= la quantité du plat 3 consommée par le client,
x4= la quantité du plat 4 consommée par le client,
D'après les données, on a les contraintes suivantes :
400𝑥1 + 200𝑥2 + 150𝑥3 + 500𝑥4 ≥ 500
3𝑥1 + 2𝑥2 ≥ 6
2𝑥1 + 2𝑥2 + 4𝑥3 + 4𝑥4 ≥ 10
2𝑥1 + 4𝑥2 + 𝑥3 + 5𝑥4 ≥ 500
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0, 𝑥4 ≥ 0
La fonction à minimiser est :
𝒎𝒊𝒏 𝒁 = 𝟎, 𝟓𝒙𝟏 + 𝟎, 𝟐𝒙𝟐 + 𝟎, 𝟑𝒙𝟑 + 𝟎, 𝟖𝒙𝟒
En utilisant l'applet de Simplexe, on trouve :
𝒙𝟏 = 𝟎, 𝒙𝟐 = 𝟑, 𝒙𝟑 = 𝟏, 𝒙𝟒 = 𝟎
Les variables x1, x2 et x3 sont positives d'où :
𝑥1 + 𝑥2 − 𝑥3 ≤ −2 ∃𝑥4 ≥ 0 𝑥1 + 𝑥2 − 𝑥3 − 𝑥4 = −2
−𝑥1 + 𝑥2 + 2𝑥3 ≤ 1 ∃𝑥5 ≥ 0 −𝑥1 +𝑥2 + 2𝑥3 − 𝑥5 = 1
D’où:
min 2𝑥1 − 𝑥2 + 𝑥3
𝑥1 +𝑥2 − 𝑥3 − 𝑥4 = −2
−𝑥1 + 𝑥2 + 2𝑥3 + 𝑥5 = 1
(𝑝0 )
𝑥1 + 𝑥3 =1
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0, 𝑥4 ≥ 0, 𝑥5 ≥ 0
3- La troisième contrainte du problème (P0) est :x1+x3=1 avec x1≥0 et x3≥0 .
D'où, x3=1-x1≥0 ce qui donne x1≤1 . Pour obtenir un problème de dimension
2 équivalent à (P0) , il suffit de remplacer la variable x3 par 1-x1 et la
contrainte x3≥0 par x1≤1 , on obtient alors :
Solution optimale
x1=1; x2=2 ; x3=0
Z=0
