Recherche Opérationnelle

Exercice 1 - Maximisation du profit

Pour formuler un programme linéaire, il est indispensable de suivre trois étapes : définir les variables de décision, établir la fonction objectif et lister les contraintes.

1. Variables de décision Nous cherchons à déterminer les quantités à produire pour chaque type de produit. Posons : x1 = nombre d'unités du produit 1 à fabriquer par semaine x2 = nombre d'unités du produit 2 à fabriquer par semaine x3 = nombre d'unités du produit 3 à fabriquer par semaine

2. Fonction objectif L'entreprise veut maximiser son profit total. Sachant que les profits unitaires sont respectivement de 30 D, 12 D et 15 D, la fonction à maximiser est : Max Z = 30 x1 + 12 x2 + 15 x3

3. Contraintes La production est limitée par le temps machine disponible (en heures par semaine) :

• Pour la machine de coupe : 9 x1 + 3 x2 + 5 x3 <= 500
• Pour le tour : 5 x1 + 4 x2 + 0 x3 <= 350
• Pour la fraiseuse : 3 x1 + 0 x2 + 2 x3 <= 150

De plus, il y a une limite commerciale sur le produit 3, dont les ventes ne peuvent dépasser 20 unités :

• Ventes produit 3 : x3 <= 20

Enfin, les quantités produites ne peuvent pas être négatives :

• x1, x2, x3 >= 0

Exercice 2 - Problème de mélange alimentaire

1. Formulation sous forme d'un programme linéaire

Variables de décision Nous devons déterminer la composition de l'aliment. Posons les variables comme les proportions (ou fractions) massiques de chaque produit brut dans 1 tonne de mélange final : x1 = proportion d'orge dans le mélange x2 = proportion d'arachide dans le mélange x3 = proportion de sésame dans le mélange

Fonction objectif L'objectif est de minimiser le coût de production d'une tonne du mélange. Min Z = 25 x1 + 41 x2 + 39 x3

Contraintes

• Le mélange doit totaliser 100% de la tonne finale : x1 + x2 + x3 = 1
• Le taux de protéines doit être d'au moins 22% : 12 x1 + 52 x2 + 42 x3 >= 22
• Le taux de graisses ne doit pas excéder 3.6% : 2 x1 + 2 x2 + 10 x3 <= 3.6
• Positivité des variables : x1, x2, x3 >= 0

2. Réduction de la dimension du problème

Puisque la somme des proportions vaut 1 (x1 + x2 + x3 = 1), nous pouvons exprimer x1 en fonction de x2 et x3 : x1 = 1 - x2 - x3

Substituons x1 dans la fonction objectif et les contraintes :

• Fonction objectif : Z = 25 (1 - x2 - x3) + 41 x2 + 39 x3 Z = 25 - 25 x2 - 25 x3 + 41 x2 + 39 x3 Z = 25 + 16 x2 + 14 x3

• Contrainte sur les protéines : 12 (1 - x2 - x3) + 52 x2 + 42 x3 >= 22 12 - 12 x2 - 12 x3 + 52 x2 + 42 x3 >= 22 40 x2 + 30 x3 >= 10

• Contrainte sur les graisses : 2 (1 - x2 - x3) + 2 x2 + 10 x3 <= 3.6 2 - 2 x2 - 2 x3 + 2 x2 + 10 x3 <= 3.6 8 x3 <= 1.6 Ce qui se simplifie en : x3 <= 0.2

• Contrainte de positivité sur x1 : 1 - x2 - x3 >= 0 => x2 + x3 <= 1

Le nouveau programme linéaire est donc réduit à deux variables (x2 et x3) : Min Z = 25 + 16 x2 + 14 x3 Sous les contraintes : 40 x2 + 30 x3 >= 10 x3 <= 0.2 x2 + x3 <= 1 x2, x3 >= 0

Exercice 3 - Planification du personnel

Variables de décision Soit xi le nombre d'agents affectés à l'équipe i pour la journée. x1 = nombre d'agents de l'Équipe 1 (6h à 14h) x2 = nombre d'agents de l'Équipe 2 (8h à 16h) x3 = nombre d'agents de l'Équipe 3 (12h à 20h) x4 = nombre d'agents de l'Équipe 4 (16h à minuit) x5 = nombre d'agents de l'Équipe 5 (22h à 6h)

Fonction objectif L'entreprise cherche à minimiser le coût journalier total, qui dépend de la rémunération de chaque équipe : Min Z = 170 x1 + 160 x2 + 175 x3 + 180 x4 + 195 x5

Contraintes Chaque plage horaire a un besoin minimal d'agents, qui doit être couvert par la somme des agents des équipes actives sur ce créneau (indiquées par les coches dans le tableau) :

• De 6h à 8h : x1 >= 48
• De 8h à 10h : x1 + x2 >= 79
• De 10h à midi : x1 + x2 >= 65
• De midi à 14h : x1 + x2 + x3 >= 87
• De 14h à 16h : x2 + x3 >= 64
• De 16h à 18h : x3 + x4 >= 73
• De 18h à 20h : x3 + x4 >= 82
• De 20h à 22h : x4 >= 43
• De 22h à minuit : x4 + x5 >= 52
• De minuit à 6h : x5 >= 15

Puisqu'on ne peut pas recruter des fractions de personnes, les variables doivent être entières : x1, x2, x3, x4, x5 >= 0 et entiers.

Exercice 4 - Optimisation d'un assortiment de chocolats

Variables de décision Puisque le chocolatier doit répondre à une commande totale de 3000 assortiments d'un kilo, raisonnons sur les quantités totales à acheter pour honorer l'ensemble de la commande. x1 = quantité (en kg) de chocolat 1 à acheter au total x2 = quantité (en kg) de chocolat 2 à acheter au total x3 = quantité (en kg) de chocolat 3 à acheter au total

Fonction objectif Le revenu total brut pour 3000 assortiments vendus à 8 D l'unité est de 24000 D. Le coût des matières premières est de : 4 x1 + 1.45 x2 + 2.40 x3. Pour maximiser les revenus nets, le confiseur doit maximiser : Max Z = 24000 - (4 x1 + 1.45 x2 + 2.40 x3) (Note : Maximiser ce profit équivaut mathématiquement à minimiser la fonction de coût d'achat).

Contraintes

• Le poids total de la commande est de 3000 kilos (3000 assortiments d'1 kg) : x1 + x2 + x3 = 3000
• Le chocolat de type 1 doit représenter entre 10 % et 20 % du poids total : x1 >= 0.10 * 3000 (soit x1 >= 300) x1 <= 0.20 * 3000 (soit x1 <= 600)
• Les chocolats 1 et 2 combinés ne doivent pas dépasser 800 gr (0.8 kg) par assortiment, donc pour 3000 assortiments : x1 + x2 <= 0.8 * 3000 (soit x1 + x2 <= 2400)
• Au moins la moitié du poids doit provenir des chocolats 1 et 3 : x1 + x3 >= 0.5 * 3000 (soit x1 + x3 >= 1500)
• Contraintes de non-négativité : x1, x2, x3 >= 0

Exercice 5 - Planification de la production avec garantie et pénalités

A. Maximiser le profit de l'usine

Variables de décision xp = quantité de produits p à fabriquer (en pièces) xq = quantité de produits q à fabriquer (en pièces) t = coût total du transporteur à payer à la fin de la journée (en dinars)

Fonction objectif Le revenu des ventes est de 42 D pour p et 48 D pour q. On y soustrait le coût du transport t. Max Z = 42 xp + 48 xq - t

Contraintes de production

• Disponibilité du matériau M : 4 xp + 2 xq <= 3000
• Disponibilité du matériau N : 3 xp + 1 xq <= 2000
• Limite de traitement journalière : chaque pièce de p pèse 7 kg (4+3) et chaque pièce de q pèse 3 kg (2+1). L'usine ne peut traiter que 5600 kg. 7 xp + 3 xq <= 5600

Contraintes de transport Le coût de transport t est facturé 2 D/kg avec une garantie (un seuil minimum) de 4000 D. Mathématiquement, t = Max(4000 ; 2 * poids total). Dans un problème de maximisation (où l'algorithme cherchera naturellement à minimiser le coût t), on modélise cela par deux bornes inférieures :

• t >= 4000

• t >= 2 * (7 xp + 3 xq) soit t >= 14 xp + 6 xq

Non-négativité et intégrité : xp, xq >= 0 (et entiers), t >= 0.

B. Ajout des pénalités de livraison

Nouvelles variables de décision pour les pénalités Le grossiste exige des quantités en kilos, que nous pouvons traduire en déficits possibles (manques). mp = quantité manquante du produit p (en kg) par rapport à la demande mq = quantité manquante du produit q (en kg) par rapport à la demande

Nouvelle fonction objectif Nous devons soustraire au profit précédent les pénalités (5 D par kg manquant pour p et 1.5 D par kg manquant pour q). Max Z = 42 xp + 48 xq - t - 5 mp - 1.5 mq

Nouvelles contraintes Le poids produit de p est de 7 xp. La demande est de 2450 kg. Le manque est la différence entre la demande et la production (s'il y en a un).

• mp >= 2450 - 7 xp
• mp >= 0

Le poids produit de q est de 3 xq. La demande est de 1800 kg.

• mq >= 1800 - 3 xq
• mq >= 0

Les contraintes de la partie A restent actives et inchangées. Les variables mp et mq s'ajustent pour être au minimum absolu permettant de satisfaire ces inéquations.

Méthode

Face à un problème de formulation linéaire, la méthode de résolution requiert rigueur et structuration. Voici comment aborder les futurs examens :

1. Identifier l'objectif global : Déterminez immédiatement si vous devez maximiser (profit, rendement, couverture) ou minimiser (coûts, distance, temps, déchets).
2. Nommer les variables précisément : C'est l'erreur la plus fréquente. Ne définissez pas x1 = produit 1, mais plutôt x1 = quantité en kg du produit 1 achetée. Précisez systématiquement les unités.
3. Traiter les contraintes non linéaires par astuces : Si vous rencontrez un coût minimum garanti ou des fonctions "Max(A, B)" dans une fonction de coût, créez une variable intermédiaire (comme t à l'exercice 5) contrainte simultanément par >= A et >= B.
4. Vérifier l'homogénéité : Assurez-vous que de chaque côté d'une contrainte A <= B, les unités sont identiques (on ne compare pas des kilos à des dinars, ni des pourcentages à des masses brutes sans conversion préalable).
5. Ne jamais oublier la non-négativité : Terminez toujours votre modèle par xi >= 0. Précisez si elles sont entières lorsqu'il s'agit d'objets indivisibles (personnes, pièces manufacturées).