Programmation linéaire

- Modélisation -

4Info
2020-2021
M. Gharbi Majdi
Exercice 1
Une compagnie fabriquant des Climatiseurs et des Ventilateurs
voudrait connaitre le nombre optimal de produits finis à fabriquer
par semaine pour maximiser son profit hebdomadaire. Elle vous
demande de l’aider en vous informant que les heures-machine et
heures de Main d’œuvre sont limitées comme indiqué dans le
tableau suivant :

Heures-Machine Heures-Main d’œuvre Profit

unitaire
h/unité h/unité
Climatiseurs 2 3 250 Dt

Ventilateur 1 3 150 Dt

Total 240 140

M. Gharbi Majdi 2
 Exercice 2
Une entreprise de relations publiques veut faire un sondage d’opinions.
Chaque employé fait par jour 80 interviews par téléphone ou bien 40
interviews en direct.
Un employé ne peut faire qu’un seul type d’interviews pendant une
journée.
Afin d’avoir un échantillon représentatif, on doit satisfaire les 3 critères
suivants
✓ Au moins 3000 interviews
✓ Au moins 1000 interviews par téléphone
✓ Au moins 800 interviews en direct.

L’employé qui conduit l’interview par téléphone est payé 50Dt/jour

L’employé qui conduit l’interview en direct est payé 70Dt/jour.

M. Gharbi Majdi 3
Exercice 3
Un agriculteur veut déterminer les quantités de 3 types
de grains à donner à son bétail au coût minimum.
Type
de
grains
Mais Blé Orge Minimum Requis
Nutri-ments

Protéines mg/Kg 10 9 11 20 mg

Fer mg/Kg 9 8 7 12 mg

Calories/kg 1000 800 850 4000 cal

Coût / Kg 0,55Dt 0,47Dt 0,45Dt

M. Gharbi Majdi 4
Exercice 4
• On annonce à la gérante d’une charcuterie qu’elle dispose de
112 Kg de mayonnaise dont 70 Kg seront bientôt périmés.
Pour écouler cette mayonnaise, elle a décidé de l’utiliser pour
préparer une mousse au jambon et une autre aux épices. Les
mousses sont préparées par lots. Un lot de mousse au jambon
nécessite 1.4Kg de mayonnaise contre 1Kg pour la mousse aux
épices. La gérante reçoit une commande de 10 lots de mousse
au jambon et 8 aux épices. Elle désire garder (au moins) 10
lots par type pour la vente locale.
• Chaque lot coûte 3Dt à préparer et se vend à 5Dt le lot au
jambon et 7Dt aux épices.

• Formuler le problème pour maximiser le profit de la gérante.

M. Gharbi Majdi 5
Exercice 5
Un agriculteur voudrait cultiver 2 sortes de légumes : des carottes et
des courgettes.
Il pourrait pour cela planter toute sa terre si le besoin nécessite .
Il utilise 2 sortes d’engrais (A et B) et 1 sorte d’antiparasite.
Les rendements des carottes et des courgettes sont de 4Kg/m2 et
5Kg/m2 respectivement.
Ses stocks sont de 800 litres d’engrais A, 700 litres d’engrais B et 300
litres d’antiparasites.
Les besoins en ces matières sont de 2 litres/10m2 d’engrais A et 1
litre/10m2 d’engrais B pour les carottes contre 1 litre/10m2 d’engrais
A et 2 litres/10m2 d’engrais B pour les courgettes.
L’antiparasite n’est utilisé que pour les courgettes à raison de
1litre/10m2

L’agriculteur voudrait produire le maximum de poids de légumes. Il

vous demande de l’aider ☺

M. Gharbi Majdi 6
 Exercice 6
• Une compagnie de papier produit du papier en rouleau
standard de 100cm de large et 10m de longueur.
Quoique la plupart des commandes soient pour ce rouleau
standard, la compagnie reçoit néanmoins des commandes
pour des rouleaux de moindre largeur. Ainsi, elle reçoit la
commande suivante:
Largeur Quantité
75 200
35 500
25 300

La compagnie doit décider comment couper les rouleaux

standards pour répondre à cette commande en utilisant le
moins de rouleaux total.
M. Gharbi Majdi 7
Exercice 7

M. Gharbi Majdi 8
 Exercice 8
• Etant donné N produits assemblés avec M types de Matière
première.

• Pi: profit d’un produit de type « i ».

• Xi: le nombre des produits « i » à fabriquer (1=< i =< N)

• Les « M » types des matières premières sont limitées en stocks.

• Ak: nombre maximal de pièces (MP) de type K (1=< k =< M)

• aik: nombre des pièces (MP) requises pour fabriquer une unité de
produit de type « i ».

M. Gharbi Majdi 9
 Exercice 9
• Etant donné 3 produits (Chaise, porte et fenêtre) assemblés avec 4
types de Matière première (vis, bois, acier et vitre).
• Pi: profit d’un produit « i »:
– P1: 95 Dnt
– P2: 160 Dnt
– P3: 150 Dnt

• Xi: le nombre des produits de type « i » à fabriquer

(1=< i =< N; N=3):
• Les « M » types des matières premières sont limitées en stocks
(M=4).

M. Gharbi Majdi 10
Exercice 9
• Ak: nombre maximal de pièces (MP) de type K (1=< k =< M):
– A1: 375 vis
– A2: 233 unités
– A3: 341 unités
– A4: 187 unités

• Une chaise demande 8 vis, 3 unités de bois et 2 unités d’acier.

• Une porte demande 16 vis, 7 unités de bois, 1 unité d’acier et 2
unités de vitre.
• Une fenêtre demande 12 vis, 4 unités de bois et 6 unités de
vitre.

M. Gharbi Majdi 11
 Exercice 10
• Un fast-food vend des Hamburgers et des
Cheeseburgers. Un Hamburger utilise 125g de
viande alors qu’un Cheeseburger n’en utilise que
100g.
• Le fast-food démarre chaque journée avec 10kg de
viande mais peut commander de la viande
supplémentaire avec un coût additionnel de 2 dinars
par 1kg pour la livraison.
• Le profit est de 1900millimes pour un Hamburger et
1700millimes pour un Cheeseburger.
• La demande ne dépasse pas 900 Sandwichs par jour.
• Comment on peut avoir un gain maximal par jour ?
Quelle est la valeur de ce gain ?
M. Gharbi Majdi 12
Exercice 10

• Fonction Objectif:
– Max 1,900 A + 1,700 B – 0.002 C-

• Fonctions Contraintes:
– A + B =< 900
– 125 A + 100 B + C = 10 000
– A >=0 , B >=0 , C non restreinte

M. Gharbi Majdi 13
Exercice 11
• Choisir de nouveaux emplacements pour construire
des usines et des entrepôts. Deux emplacements
possibles : Tunis et Sfax.
• On ne peut construire un entrepôt que dans une ville là
où il y’en a une usine.
• On ne peut pas construire plus qu’un entrepôt dans les
deux villes.
• Un emplacement ne peut recevoir qu’une seule usine.
• On associe à chaque construction (d’une usine ou d’un
entrepôt dans chacun des lieux envisagés):
• Sa valeur estimée
• Son coût de construction

M. Gharbi Majdi 14
Exercice 11
• Objectif : maximiser la valeur totale estimée, en
ne dépassant pas une limite maximum sur les
coûts.
• Données du problème :
Valeur Coûts de construction
Usine à Tunis 9 6
Usine à Sfax 5 3
Entrepôt à Tunis 6 5
Entrepôt a Sfax 4 2
Limite maximum - 15

M. Gharbi Majdi 15