Master statistique
Optimisation M. Duprez
2015-2016
TP1 : Minimisation d’une application linéaire sous
contraintes
Résoudre les exercices suivants en utilisant la fonction karmarkar de Scilab.
Cette fonction implémente un algorithme pour de programmation linéaire, i.e. la re-
cherche du minimum d’une fonction linéaire sous des contraintes affines, proposé par une
mathématicien indien Narendra Karmarkar en 1984. Avant d’attaquer les exercices, prenez
le temps de lire l’article d’aide de scilab consacré à la fonction karmarkar (help karmarkar).
Exercice 1 : Minimiser la fonction :
f (x, y) = −2x + y
soumis aux contraintes
2x + 3y ≥ 6
−x + y ≤ 3
x ≤ 2
x ≥ 0, y≥0
Exercice 2 : Un bûcheron a 100 hectares de bois de feuillus. Couper un hectare de bois
et laisser la zone se régénérer naturellement coûte 10 k$ par hectares, et rapporte 50 k$.
Alternativement, couper un hectare de bois, et replanter avec des pins coûte 50 k$ par
hectares, et rapporte à terme 120 k$. Sachant que le bûcheron n’a que 4000 k$ en caisse au
début de l’opération, déterminer la meilleure stratégie à adopter et le profit escomptable.
1
Master statistique
Optimisation M. Duprez
2015-2016
Exercice 3 : Une entreprise doit transporter du beurre de cacahuète entre trois dépôts
D1, D2 et D3 et trois magasins M 1, M 2 et M 3. Chaque dépôt a une quantité limitée
de marchandise, chaque destination une demande, et le coût unitaire pour transporter un
camion de beurre de cacahuète varie suivant le dépôt et le magasin. On résume tout dans
le tableau ci-dessous (la dernière colonne représente le coût unitaire) :
Dépôt Quantité disponible Magasin Demande M1 M2 M3
D1 35 M1 45 D1 5 10 10
D2 40 M2 50 D2 20 30 20
D3 40 M3 15 D3 5 8 12
Quel est le coût minimum pour l’entreprise ?
Exercice 4 :
1. Trois machines M 1, M 2 et M 3 peuvent produire chacune deux types de pièces P 1
et P 2. Les temps de fabrication d’un pièce P i sur la machine M j sont donnés dans
le tableau :
M1 M2 M3
P1 3h 4h 4h
P2 4h 6h 5h
On veut fabriquer au moindre coût 6 pièces de type P 1 et 8 pièces de type P 2. La
machine M 1 est disponible 15 heures, la machines M 2 25 heures et la machines
M 3 35 heures. Le coût horaire de M 1 est 7, celui de M 2 est 5 et celui de M 3 est 6.
2. La solution donnée par karmarkar sera irréaliste, car elle est en nombres non
entiers et donc elle préconise de partager la fabrication d’une pièce par plusieurs
machines ce qui entraı̂ne logiquement des coûts supplémentaires. Comment trouver
la stratégie optimale sous la contrainte complémentaire qu’on doit fabriquer un
nombre entier de pièces P i sur la machine M j ?