Ecole Militaire Polytechnique: Exercice 1

Ecole Militaire Polytechnique
Série d’exercice des Techniques d’optimisation
Programmation linéaire
Exercice 1
La fabrique RadioDz crée deux types de radios A et B. Chaque radio produite est le fruit des
efforts conjoints de 3 spécialistes Walid, Hamid et Aissa. Walid travaille au plus 24 heures par
semaine. Hamid travaille au plus 45 heures par semaine. Aissa travaille au plus 30 heures par
semaine. Les ressources nécessaires pour construire chaque type de radio ainsi que leurs prix
de vente sont donnés dans le tableau ci-dessous :
Radio A Radio B
Walid 1h 2h
Hamid 2h 1h
Aissa 1h 3h
Prix de vente 15 kDA 10 kDA
On suppose que l’entreprise n’a aucun problème à vendre sa production.

a) Modéliser le problème de la recherche d’un plan de production hebdomadaire maximisant
le chiffre d’affaires de RadioDz sous forme d’un programme linéaire. Préciser clairement les
variables de décision, la fonction objectif et les contraintes.
b) Résoudre ce programme linéaire graphiquement et donner le plan de production optimal.
Exercice 2
Une entreprise disposant de 10000𝑚2 de carton en réserve, fabrique et commercialise 2 types de
boîtes en carton. La fabrication d’une boîte en carton de type 1 ou 2 requiert, respectivement,
1 et 2 m2 de carton ainsi que 2 et 3 minutes de temps d’assemblage. Seules 200 heures de
travail sont disponibles pendant la semaine à venir. Les boîtes sont agrafées et il faut quatre
fois plus d’agrafes pour une boîte du second type que pour une du premier. Le stock d’agrafes
disponible permet d’assembler au maximum 15 000 boîtes du premier type. Les boîtes sont
vendues, respectivement, 3 et 5 DA.
a) Formuler le problème de la recherche d’un plan de production maximisant le chiffre d’affaires
de l’entreprise sous forme d’un programme linéaire canonique.
b) Déterminer un plan de production optimal en résolvant graphiquement le programme
linéaire trouvé en a).
1
Exercice 3
L’entreprise N&N’s produit des pastilles chocolatées. Chaque pastille est formée d’un cœur en
chocolat enrobé d’une couche de sucre coloré. Les pastilles sont commercialisées en paquets de
100g. Pour faire 1kg de pastilles, il faut 750g de chocolat et 250g de sucre. Quatre couleurs sont
disponibles pour colorer les pastilles : vert, jaune, rouge et brun. Chaque paquet doit contenir
au moins 20% de pastilles de chaque couleur et la quantité de pastilles rouges et jaunes ne doit
pas être inférieure à celle des pastilles vertes et brunes. On suppose que tous les paquets ont la
même répartition.
Pour le mois ‘a venir, l’entreprise dispose de
• 6 tonnes de chocolat ;
• 3 tonnes de sucre ;
• colorant brun en suffisance ;
• colorant rouge pour au plus 1 tonnes de pastilles ;
• colorant jaune pour au plus 1.5 tonnes de pastilles ;
• colorant vert pour au plus 2 tonnes de pastilles.
En ne tenant compte que des contraintes exposées ci-dessus, formuler un programme linéaire
permettant à l’entreprise de déterminer le nombre maximal de paquets qu’elle peut produire
pendant le prochain mois
Exercice 4
Max 𝑓 (𝑥) = 𝑥1 + 2𝑥2 + 3𝑥3 Min 𝑧 = 10𝑥1 + 5𝑥2 + 8𝑥3

⎧
⎪ 10𝑥1 + 5𝑥2 + 2𝑥3 ≥ 4.2
⎧
⎪ ⎪
⎪ 𝑥1 + 𝑥2 ≤ 3, ⎪
⎪ 10𝑥1 + 4𝑥2 + 6𝑥3 ≤ 6.4
⎪
⎪ ⎪
s.c. ⎨
𝑥2 + 3𝑥3 ≤ 4, s.c. ⎨ 6𝑥1 + 10𝑥2 + 8𝑥3 ≤ 8
⎪ 𝑥1 + 𝑥3 ≤ 5 ⎪
⎪
⎪ ⎪ 𝑥 1 + 𝑥 2 + 𝑥 3 = 1
⎪
⎪ 𝑥1 , 𝑥2 , 𝑥3 ≥ 0 ⎪
⎩ ⎪
⎩ 𝑥𝑖 ≥ 0 𝑖 = 1, 2, 3
Min 𝑓 (𝑥) = 2𝑥1 − 𝑥2 + 4𝑥3 Min 𝑧 = 𝑥2

⎧
⎪ 3𝑥1 + 2𝑥2 + 1𝑥3 ≤ 4,
⎧
⎪ ⎪
⎪
⎪ 𝑥1 + 𝑥2 − 𝑥3 ≤ 7, ⎪ 𝑥 + 2𝑥2 + 3𝑥3 ≤ 3,
⎪ ⎪ 1
⎪ 𝑥 + 2𝑥2 + 3𝑥3 ≤ 6,
s.c. ⎨ 1 s.c. ⎨ 𝑥1 + 𝑥2 + 𝑥3 ≤ 2
⎪ 𝑥1 , 𝑥2 , 𝑥3 ≥ 0 ⎪
⎪
⎪ ⎪ 2𝑥1 + 3𝑥2 + 𝑥3 ≤ 5
⎪
⎪ ⎪
⎪ 𝑥1 , 𝑥2 , 𝑥3 ∈ IR+
⎩ ⎩
Exercice 5
Les problèmes connus comme problèmes de plus court chemin ou problèmes de cheminement,
essayent de trouver le chemin plus court entre deux points. Cela peut s’agir de la distance
entre les points d’origine et de destination ou bien le temps écoulé d’un point à l’autre. Il est
2
très utilisé dans les problèmes des réseaux de communications. Ce type de problèmes peut se
résoudre moyennant la méthode du Simplexe.
Soit une personne qui doit se déplacer tous les jours d’une ville A à une autre G. Elle analyse le
trajet plus court avec la carte de routes. On montre les routes et les distances dans la prochaine
figure:
𝐴
4
12
𝐵 𝐶
5 2
10
𝐷
3
10
𝐸 𝐹
2 4
𝐺
Formuler un programme linéaire permettant de trouver le plus court chemin du point A

jusqu’au point G.

Ecole Militaire Polytechnique: Exercice 1

Transféré par

Droits d'auteur :

Formats disponibles

Ecole Militaire Polytechnique: Exercice 1

Transféré par

Informations du document

Titre original

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

Ecole Militaire Polytechnique: Exercice 1

Transféré par

Droits d'auteur :

Formats disponibles

Ecole Militaire Polytechnique

Série d’exercice des Techniques d’optimisation

On suppose que l’entreprise n’a aucun problème à vendre sa production.

Max 𝑓 (𝑥) = 𝑥1 + 2𝑥2 + 3𝑥3 Min 𝑧 = 10𝑥1 + 5𝑥2 + 8𝑥3

Min 𝑓 (𝑥) = 2𝑥1 − 𝑥2 + 4𝑥3 Min 𝑧 = 𝑥2

Formuler un programme linéaire permettant de trouver le plus court chemin du point A

Vous aimerez peut-être aussi