Exercices de td modelisation -Programmation linaire - Recher
Télécharger PDFExercices de Modélisation en Programmation Linéaire
Cette série d'exercices porte sur la modélisation mathématique de problèmes réels à l'aide de la programmation linéaire. Ces cas pratiques couvrent des domaines variés tels que l'industrie, la nutrition, la logistique et la gestion de production.
Exercice 1 : Optimisation de la production de piles
Une manufacture de piles souhaite ajouter deux nouveaux produits à son catalogue : la Everlast III et la Xeros dry-cell.
- Everlast III : contient 2g de Cadmium et 4g de Nickel. Bénéfice net : 1000 euros par millier.
- Xeros dry-cell : nécessite 3g de Nickel et 4g de Zinc en poudre. Bénéfice net : 1200 euros par millier.
Les contraintes de ressources sont les suivantes :
- Cadmium disponible : 1 tonne.
- Nickel disponible : 3 tonnes.
- Zinc : quantité illimitée.
- Temps machine (Presse Glunt II) : 2 heures pour 1000 Everlast III et 3 heures pour 1000 Xeros. Disponibilité totale : 2400 heures par an.
Questions :
a. Traduire par un programme linéaire en forme canonique.
b. Résoudre le problème par une méthode graphique.
c. Maximiser le gain annuel par la méthode du simplexe.
d. Analyser l'impact d'une baisse du bénéfice de la Xeros à 750 euros (suite à des frais publicitaires écologiques) sur la solution optimale.
Exercice 2 : Régime alimentaire et nutriments
Un nutritionniste élabore un régime à partir de quatre aliments : Œufs, Lait, Fromage et Pain. Les teneurs en mg sont les suivantes :
- Œufs : Cadmium (6), Nickel (2), Zinc (1).
- Lait : Cadmium (8), Nickel (1), Zinc (3).
- Fromage : Cadmium (5), Nickel (1), Zinc (1).
- Pain : Cadmium (9), Nickel (3), Zinc (2).
Contraintes journalières : Nickel ≤ 15 mg, Zinc ≤ 10 mg. L'objectif est de maximiser l'apport en Cadmium, considéré ici comme bénéfique.
Variante : Recalculer la solution si le Cadmium devient toxique (limité à une certaine dose), si le régime doit inclure au moins une unité de pain et au plus trois œufs.
Exercice 3 : Gestion forestière d'un bûcheron
Un bûcheron possède 100 hectares de bois de feuillus. Il dispose de deux options pour chaque hectare :
- Régénération naturelle : Coût de 10 k€, rapport de 50 k€.
- Replantation de pins : Coût de 50 k€, rapport de 120 k€.
Avec un capital initial de 4000 k€, quelle est la stratégie optimale pour maximiser le profit total ?
Exercice 4 : Problème du cambrioleur (Sac à dos)
Un cambrioleur possède un sac de 60 litres. Il doit choisir parmi sept objets :
| Objet | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Volume (L) | 20 | 16 | 7 | 10 | 42 | 4 | 12 |
| Prix (€) | 25 | 18 | 10 | 12 | 50 | 5 | 14 |
L'objectif est de modéliser ce problème en nombres entiers et de comparer la solution optimale avec la relaxation linéaire (algorithme glouton).
Exercice 5 : Assignation de taxis
Une compagnie doit assigner quatre taxis à quatre clients en minimisant la distance totale parcourue. Les distances (km) sont :
- Taxi 1 : (6, 4, 5, 4) vers clients 1, 2, 3, 4.
- Taxi 2 : (3, 5, 6, 4)
- Taxi 3 : (4, 4, 6, 3)
- Taxi 4 : (5, 6, 7, 5)
Exercice 6 : Fabrication de boîtes en carton
Une entreprise produit deux types de boîtes avec 10 000 m² de carton et 200 heures de travail.
- Type 1 : 1 m² de carton, 2 min d'assemblage, prix 3€.
- Type 2 : 2 m² de carton, 3 min d'assemblage, prix 5€.
Une contrainte supplémentaire porte sur les agrafes : le stock permet d'assembler au maximum l'équivalent de 15 000 boîtes de type 1 (le type 2 consommant quatre fois plus d'agrafes).
Exercice 7 : Théorie des jeux - Jeu de Morra
Deux joueurs cachent 1 ou 2 pièces et devinent le total. Si un seul devine juste, il gagne la somme des pièces cachées. Modéliser ce jeu sous forme de programme linéaire pour trouver une stratégie mixte optimale.
Exercice 8 : Planification d'une usine de jambons
Une usine traite 480 jambons, 400 poitrines et 230 lardons par jour. Les produits peuvent être vendus frais ou fumés (en heures normales ou supplémentaires). L'objectif est de maximiser le bénéfice net en tenant compte des capacités de fumage (420 unités en heures normales, 250 en supplémentaires).
Exercice 9 : Production de radios
RadioIn produit des modèles A et B utilisant le temps de trois spécialistes : Pierre (24h), Paul (45h) et Jean (30h).
- Radio A : 1h Pierre, 2h Paul, 1h Jean. Prix : 15€.
- Radio B : 2h Pierre, 1h Paul, 3h Jean. Prix : 10€.
Exercice 10 : Gestion de la main-d'œuvre pour mobiles
Un assembleur doit livrer 20 000 téléphones en 4 semaines. Il doit gérer l'embauche et la formation d'ouvriers temporaires par les ouvriers permanents (1 formateur pour 3 apprentis). Les salaires et les prix de vente varient selon les semaines.
Exercice 11 : Problème de la bicyclette
N personnes doivent parcourir 10 km avec une seule bicyclette monoplace. Chaque personne a une vitesse de marche et une vitesse à vélo différente. L'objectif est de minimiser l'heure d'arrivée de la dernière personne.
Exercice 12 : Aménagement d'un hôtel thermal
Le propriétaire d'un hôtel doit choisir la répartition de ses chambres (2 ou 3 couchages, douche ou salle de bains) pour maximiser son bénéfice, sachant que la salle de restaurant est limitée à 100 personnes et qu'il existe des contraintes sur le pourcentage de douches et de grands lits.
Exercice 13 : Composition d'aliment pour bétail
Mélange de maïs, soja et herbe au coût minimum respectant les seuils nutritionnels : Calcium ≤ 0,5%, Fibres ≤ 5%, Protéines ≥ 30%.
Exercice 14 : Production de pastilles colorées
L'entreprise R&O's fabrique des paquets de 100g. Chaque paquet doit contenir au moins 20% de chaque couleur (vert, jaune, rouge, brun) avec des stocks limités de chocolat, de sucre et de colorants.
Exercice 15 : Verrerie artisanale
Déterminer la production optimale de verres à vin, verres à eau et flûtes à champagne selon les temps de façonnage, d'emballage et la quantité de verre disponible.
Exercice 16 : Horaires de chauffeurs de bus
Couvrir toutes les tranches horaires de 9h à 17h au coût minimal en choisissant parmi sept horaires de travail possibles pour les chauffeurs.
Exercice 17 : Vendeur de téléphones et kits
Maximiser le profit en créant des offres groupées (téléphone + cartes prépayées ou téléphone + kit + cartes) à partir d'un stock limité.
Exercice 18 : Modélisation avancée du sac à dos
Formuler mathématiquement le problème de sélection d'objets pour un sac de 50 litres avec des valeurs et des volumes spécifiques.
Exercice 19 : Découpe de barres de métal
Le directeur d'une école doit découper des barres de 2,10 m pour obtenir des pieds de bureaux de hauteurs différentes (50cm, 80cm, 1,10m) en minimisant la perte de métal.
Exercice 20 : Production de pièces automobiles
Gestion d'ateliers d'usinage, d'assemblage et de finition. Les pièces peuvent être vendues "brutes" ou "finies". Le problème inclut des contraintes de contrats de livraison, de vente chez des distributeurs et de recours aux heures supplémentaires.
Exercice 21 : Distribution d'énergie électrique
Trois centrales électriques doivent alimenter deux villes. L'objectif est de satisfaire les besoins des villes (800 MW chacune) en minimisant les coûts de transport entre les centrales et les zones de consommation.
Exercice 22 : Assemblage d'ordinateurs portables
Un assembleur dispose de stocks limités de cartes Wifi et de barrettes mémoire pour deux modèles de PC (X1 et X2). Il doit décider s'il accepte un contrat de sous-traitance et définir les quantités à produire pour maximiser son bénéfice.
Exercice 23 : Industrie pharmaceutique
Fabrication de somnifères, euphorisants et analgésiques à partir de caféine, valériane et morphine. Chaque produit a un rendement et un besoin en matières premières spécifique à optimiser.
FAQ sur la Modélisation Linéaire
Qu'est-ce qu'un programme linéaire en forme canonique ?
La forme canonique est une écriture standard où l'on cherche à maximiser une fonction objectif sous des contraintes de type "inférieur ou égal" (≤), avec des variables de décision non négatives.
Pourquoi utilise-t-on la méthode du simplexe ?
La méthode du simplexe est un algorithme efficace pour résoudre des problèmes de programmation linéaire comportant plus de deux variables, ce qui rend la résolution graphique impossible.
Quelle est la différence entre un PL et un PLNE ?
Un programme linéaire (PL) autorise des solutions avec des nombres réels, tandis qu'un programme linéaire en nombres entiers (PLNE) impose que certaines ou toutes les variables soient des entiers, comme dans le cas de la production d'objets indivisibles.