LP : forme primale (exercices)

Tutoriel

Un fabriquant d’outillage de fraisage fabrique deux types de fraises : A et B. Les fraises de type A se vendent 300 l’unité, et se fabrique à avec 1 unité d’acier, 2 unités de carbure amovible et 1 unité de diamant synthétique. Les fraises de type B se vendent 200 l’unité, et se fabrique à avec 2 unité d’acier, 1 unités de carbure amovible et 1 unité de diamant synthétique. Les stocks sont de 5 unités d’acier, 5 unités de carbure et 2 unités de diamant. Le fabriquant souhaite construire au moins 5 fraises de type A et 5 fraises de type B. Le coût d’entretien de l’usine est de 2500. Comment le fabriquant doit-il répartir sa production pour maximiser son profit, est-ce rentable ?

Correction

Dans un premier temps il faut réaliser le programme linéaire :

  • Fonction objectif : z = 300A+200B-2500
  • Contraintes :
    • A+2B  ≤ 5
    • 2A+B ≤ 5
    • A+B ≤ 2
    • A  ≥ 5
    • B  ≥ 5

Le programme n’est pas sous forme canonique, il faut le rendre sous cette forme avant de le résoudre.

Posons x1 = A-5 et x2 = B-5. Le programme linéaire devient le suivant :

Le programme linéaire possède 2 variables, il est donc possible de le résoudre graphiquement. Les contraintes donnent le domaine des solutions suivant :

Le gradient de la fonction objectif est (3,2), ce qui donne pour point extrême l’intersection de la deuxième et troisième contrainte. Il faut donc résoudre le système :

Qui a pour solution le vecteur (10, 2). Ce qui donne dans le problème initial le vecteur (15, 7) et pour fonction objectif égale à 900. L’opération est positif donc profitable pour l’usine.

S’entraîner

Exercice 1

Un brooker a besoin, pour sa clientèle, de 108 MWh d’électricité pour la ville 1 et de 96 MWh d’électricité pour la ville 2. Cependant, les lois de Kirchhoff ne permettent pas à un distributeur de cibler une ville unique pour le transit énergétique. Deux distributeurs desservent ces villes : le Distributeur A peut envoyer 12 MWh à la ville 1 et 8MWh à la ville 2 par lot acheté; le Distributeur B peut envoyer 9 MWh à la ville 1 et 12 MWh à la ville 2 par lot acheté. Les lots ont tous le même prix. Combien de lots doit acheter le brooker pour combler la demande énergétique des deux villes ? Résoudre par méthode graphique.

Exercice 2

Résoudre par la méthode graphique puis par le simplexe les problèmes suivants :

  1. Une compagnie fabriquant deux types de produits cherchent à maximiser son profit. Voici sa feuille de route.
  1. De même avec le programme linéaire suivant :

Exercice 3

Le BIM optimise la construction, la rénovation et la maintenance de bâtiments. Parmi les éléments à optimiser il y a les ouvriers. En général, il existe 4 types d’ouvriers en fonction de leur week-end. Le salaire des ouvriers dépendent de ces journées de congés :

Les demandes quotidiennes en ouvriers sont les suivantes :

Combien de personnes de chaque catégorie doit-on faire travailler de façon à satisfaire la demande et à minimiser le coût du personnel ? Donner la forme canonique du problème et résoudre à l’aide du Solver Excel.

Valider ses compétences

Exercice 4

Une entreprise fabrique trois types de produits, A, B et C. Chaque produit nécessite des matières premières et de la main d’oeuvre, ainsi que de l’espace de stockage. Voici les besoins en matières premières, mains d’oeuvre et stockage pour une unité de chacun des 3 types de produits :

  • Produit A : 4 kg de matières premières, 2 heures de main d’oeuvre, 1 unité de volume.
  • Produit B : 2 kg de matières premières, 1/2 heure de main d’oeuvre 1 unité de volume.
  • Produit C : 1 kg de matières premières, 3 heures de main d’oeuvre, 1 unité de volume.

Chaque produit rapporte 6 euros s’il est de type A, 2 euros s’il est de type B, et 4 euros s’il est de type C. Les ressources disponibles sont 6000 kg de matières premières, 4000 heures de main d’oeuvre, et 2500 unités de volume de stockage.

Modélisation le programme linéaire et le résoudre à la main à l’aide du simplexe.

Un concurrent, qui manque de matières premières, propose d’en racheter 300 kg à cette entreprise, au prix de 1.5 euros par kg. Pensez-vous que l’entreprise devrait accepter cette proposition ? (On supposera qu’elle l’accepte si elle est rentable, résoudre le problème à la main avec le simplexe.)

Exercice 5

Une entreprise fabrique trois types de piles : sèches de type 1 (PS1), sèches de type 2 (PS2) et à combustible (PC). Le processus de fabrication comporte trois étapes : l’assemblage, un test de qualité, un traitement d’isolation. Seules les piles satisfaisant le test de qualité sont soumises au traitement d’isolation. Les piles qui ratent le test de qualité sont mises au rebut. Au cours du mois prochain, l’entreprise disposera en temps-machine de 9000 heures pour l’assemblage, de 1200 heures pour les tests de qualité et de 8500 heures pour le traitement d’isolation. Le tableau suivant résume les informations pertinentes du procédé de fabrication :

Quel est le nombre optimal de piles de chaque type à fabriquer le mois prochain si l’entreprise est assurée de vendre toute sa production ?

Exercice 6

Dans un réseau électrique, la quantité d’énergie pouvant transiter des centrales vers les villes est limité par les capacités des lignes à très hautes tension. Le problème est décrit de la façon suivante :

  • Des sources, représenté par des sommets, produisent une quantité d’énergie
  • Des puits, représenté par des sommets, reçoivent une quantité d’énergie
  • Des lignes, représenté par des arêtes entre une pair de sommet, par lesquels passent l’énergie.

Ce graphe se lit ainsi :

  • S est une source fictive, qui décrit la production des sources énergétiques représentées par le sommet 1 et le sommet 2.
  • T est un puits fictif, qui décrit la réception énergétique des villes représentées par le sommet 3 et le sommet 4.
  • Les lignes sont orientés, c’est à dire que l’énergie ne passe que dans un seul sens. Par exemple la lien (1, 3) peut faire circuler jusqu’à 4 unités d’énergie entre le sommet 1 et le sommet 3.
  • Les liens entre S et les sources décrient la production énergétique de la source. Par exemple le lien (S, 1) dit que la source 1 peut produire jusqu’à 10 unités d’énergie.
  • Les liens entre les puits et T décrient la demande énergétique du puits. Par exemple le lien (3, T) dit que la ville 3 réclament 10 unités en énergie.

La fonction objectif de se type de problème est :

  • maximiser la quantité d’énergie que l’on peut faire transiter de S à T. La solution fournira la quantité d’énergie transitant dans chaque ligne. Pour calculer ce flot, un arc est ajouté entre le puits fictif et la source fictive sans contrainte. La solution optimale est égale au flot transitant par cet arc.

Ce problème est soumis à deux types de contraintes :

  • la somme des énergies entrant dans un sommet moins la somme des énergies sortant du même sommet est nulle. C’est à dire qu’il n’y a pas de pertes énergétiques dans le réseau
  • l’énergie transitant par une ligne ne peut pas être supérieur à la capacité de la ligne.
  • l’énergie transitant par une ligne est positive ou nulle.

Les variables sont donc :

  • pour chaque ligne, une variable décrit la quantité d’énergie transitant dessus.

Formuler le problème linéaire pour le graphe donné ci-dessus et résolvez le via Excel.