Programmation linéaire : TD1

Résolution graphique d'un programme linéaire

Résoudre graphiquement les 5 programmes linéaires suivants :

  1. Max   z = x1 + 2 x2
    x1 + x2 <= 6
    x2 <= 3
    x1, x2 >= 0
  2. Max   z = x1 + 2 x2
    x2 <= 3
    x1, x2 >= 0
  3. Max   z = -x1 + 2 x2
    x2 <= 3
    x1, x2 >= 0
  4. Max   z = x1 + 2 x2
    x1 - x2 <= -4
    x2 <= 3
    x1, x2 >= 0
  5. Max   z = x1 + x2
    x1 + x2 <= 6
    x2 <= 3
    x1, x2 >= 0

Sable et ciment

Une usine produit deux types de mortiers A et B en mélangeant du sable et du ciment.

Les besoins en sable et en ciment pour fabriquer les deux types de mortiers ainsi que la durée de brassage sont indiqués sur le tableau suivant :

  A B
durée de brassage 1h 2h
ciment 2 kg 2 kg
sable 9 kg 4 kg

Illustration : la production d'un sac de mortier A requiert 2 kg de ciment et 9 kg de sable et utilise le mélangeur pendant une heure.

Les profits réalisés sont de 5 euros par sac de mortier A et 6 euros par sac de mortier B.

Sachant que l'on ne peut utiliser la machine que 8h par jour et que l'on ne dispose respectivement que de 10kg et de 36 kg de ciment et de sable par jour.

Combien de sacs de mortier A et B doit on produire afin d'obtenir un profit maximal?

  1. Exprimer ce problème par un programme linéaire.
  2. Le résoudre graphiquement.
  3. Le résoudre par la méthode du simplexe.

Moteurs électriques

Un industriel fabriquant des moteurs électriques est convaincu par son distributeur qu'il peut vendre en grande quantité ses deux principaux types de moteurs (MS) et (MHP). En fait, le distributeur est tellement confiant dans les possibilités du marché qu'il est prêt à acheter au fabricant, à l'avance, tous les moteurs qu'il pourra fabriquer dans les trois mois à venir.

Les principales phases de production des moteurs sont les suivantes :

  1. Fabrication des pièces élémentaires
  2. Bobinage
  3. Assemblage
  4. Contrôle et emballage

Durées des phases de production : les deux moteurs ont des temps de fabrication différents. Les temps unitaires (h) sont donnés sur le tableau ci-dessous :

Phases/type de moteur MS MHP
Fabrication des pièces élémentaires 0.7 1
Bobinage 0.5 5/6
Assemblage 1 2/3
Contrôle et emballage 0.1 0.25

Après analyse du comptable, il s'avère que les profits dégagés par chaque type de moteur sont les suivants : 100 euros pour MS et 90 euros pour MHP.

Après analyse du planning, le directeur de production estime que la disponibilité de production pour les trois mois à venir est la suivante :

Le problème posé à cette entreprise est de savoir combien de moteurs de chaque type elle doit fabriquer durant les trois mois, de telle sorte que le profit soit maximum au niveau de cette opération.

  1. Exprimer sous forme d'équations ou d'inéquations les différents éléments du problème
    1. Équation du profit
    2. Inéquations des contraintes
    3. Conditions autres
  2. Définir graphiquement la zone de faisabilité du problème posé
  3. Déterminer graphiquement le nombre de moteurs à produire de chaque type afin d'avoir un profit maximum
  4. Dans l'hypothèse où le profit pour le MS est de 50 euros et reste de 90 euros pour le MHP, déterminer le nombre optimal de moteurs de chaque type pour un profit maximal
  5. Idem dans l'hypothèse où le profit pour le moteur standard est de 63 euros et reste 90 euros pour MHP.

Objets en terre cuite

Une fabrique d'objets en terre cuite peinte produit des cendriers, des cruches, des bols et des vases. La fabrication de chacun de ces objets nécessite un certain nombre d'heures de moulage, de cuisson et de peinture. La vente de ces objets rapporte un certain bénéfice.

Ces données sont récapitulées dans le tableau suivant :
Objet Cendrier Bol Cruche Vase
Moulage 2 4 5 7
Cuisson 1 1 2 2
Peinture 1 2 3 3
Bénéfice 7 9 18 17

L'entreprise dipose, quotidiennement, de 42 heures de moulage, 17 heures de cuisson et 24 heures de peinture.

On souhaite établir un plan de fabrication de façon à maximiser le chiffre d'affaires (on suppose que l'on est en régime stable de fabrication et non en phase initiale où il faut mouler avant de cuire et cuire avant de peindre).

  1. Modéliser le problème sous forme d'un programme linéaire
  2. Le résoudre par la méthode du simplexe
  3. Combien faut-il fabriquer de cendriers, bols, cruches et vases par jour pour optimiser le chiffre d'affaire? Reste-t-il des heures disponibles? Quel est le chiffre d'affaire optimal?

À propos de ce document...

This document was generated using the LaTeX2HTML translator Version 99.2beta6 (1.42)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 sujtd1.tex

The translation was initiated by Florence Bannay on 2003-02-03

Florence Bannay 2003-02-03