Programmation linéaire

1







Max (x1 − x2 + x3)

−3x1 + 2x2 + x3 = 1

x1 − x2 − x3 + x4 = 3

x1 + 4x2 + 2x3 − 2x4 = 1

x1, x2, x3 et x4 ≥ 0







Max (x1 + 2x2 + 3x3)

x1 + x2 ≤ 5

2x1 + 2x2 − x3 = 6

12x1 + 8x2 − 5x3 = 32

x1, x2 et x3 ≥ 0

Exercice 4

Une raffinerie fabrique deux qualités d’essence (A et B) en mélangeant dans cer-

taines proportions deux produits semi-finis (P1 et P2). Les indices d’octane et les quan-

tités disponibles par jour pour ces deux produits sont indiqués dans le tableau suivant :

Indice d’octane Nb. de barils/jour

Produit 1

Produit 2

71

99

3900

5000

L’indice d’octane de l’essence A doit être d’au moins 96 et celui de l’essence B

d’au moins 85. La raffinerie vend toute sa production de A et B aux prix respectifs de

3,75 $ et 2,75 $ par baril. Les excédents éventuels de P1 sont revendus au prix de 1,25 $

par baril à une fabrique de goudron et ceux de P2 sont revendus à un terrain d’aviation

au prix de 2,25 $ par baril.

On notera x1A et x2A (resp. x1B et x2B) le nombre de barils de P1 et de P2 utilisés

pour fabriquer A (resp. B).

4-1 ) Calculer, en fonction de x1A et x2A, l’indice d’octane de A.

4-2 ) Ecrire le programme correspondant à l’optimisation du profit de la raffinerie.

4-3 ) Résoudre ce programme par la méthode du simplexe.

4-4 )

Quel est finalement leur indice d’octane ?

Indiquer en % la composition des essences A et B, solutions du problème.

Exercice 5

Dans une entreprise qui fabrique des pièces détachées à la demande un client désire

commander des pièces A et B dans un délai d’un mois. Fournisseur et client se sont mis

d’accord sur les prix suivants : 138 e par série de 100 pièces A et 136 e par série de

100 pièces B. La réalisation des pièces A et B nécessite un passage dans trois ateliers

pour lesquels on dispose des renseignements suivants :

Nb d’unités d’oeuvre Nb d’unités d’oeuvre

pour 100 pièces A

2

1

4

pour 100 pièces B

1

4,5

3

Coût variable

d’une unité d’oeuvre

10 e

12 e

14 e

Atelier T

Atelier F

Atelier M

Au moment de la commande, l’entreprise ne dispose que d’un nombre limité d’heures

dans chaque atelier correspondant respectivement à : 200 unités d’oeuvre pour l’atelier

T, 540 unités d’oeuvre pour l’atelier F, 480 unités d’oeuvre pour l’atelier M.

Ces nombres d’unités d’oeuvre sont insuffisants pour satisfaire le client dans le

délai demandé. L’entreprise lui propose une livraison partielle.

Quelles quantités de pièces A et de pièces B l’entreprise a-t-elle intérêt à fabriquer

au cours du mois si elle veut obtenir une marge maximum compte-tenu des moyens

2

de production disponibles. On utilisera la méthode du simplexe dont on donnera par la

suite une interprétation graphique.

Exercice 6

Une entreprise envisage le lancement de deux nouveaux types de moteurs. Ces deux

modèles, A et B, seront fabriqués essentiellement dans trois ateliers pour lesquels on

dispose des renseignements suivants :

Temps opératoire

unitaire

Temps

disponible

pour le modèle A pour le modèle B (en heures)

Temps opératoire

unitaire

Emboutissage

Soudure

Peinture

50 mn

30 mn

20 mn

40 mn

20 mn

10 mn

2500 h

1000 h

800 h

Coût

variable de

l’heure

150 e

60 e

20 e

Une étude de marché a par ailleurs révélé que les prix de vente devaient être fixés

à 215 e pour le modèle A et 150 e pour le modèle B, le marché du modèle A étant en

tout état de cause saturé avec 1800 articles.

On demande de déterminer un plan optimal de fabrication et la marge à l’optimum

par l’algorithme du simplexe.

Exercice 7

Une société se consacre à l’excavation et la distribution de matériaux de carrière.

Elle doit assurer, pour des travaux routiers, la fourniture de graviers en divers calibres.

Un marché a été adjugé pour un prix global de facturation, portant sur les quantités

suivantes :

13 500 tonnes de graviers de calibre 1

11 200 tonnes de graviers de calibre 2

5 000 tonnes de graviers de calibre 3.

La société exploite deux carrières P1 et P2 louées à une société civile qui perçoit

une redevance par tonne extraite : 19,40 e par tonne pour P1 et 20 e par tonne pour

P2.

Après extraction, le pierre est concassée et les graviers ainsi obtenus sont triés selon

leur calibre. Chaque tonne de pierre fournit les quantités suivantes (le complément

représente du sable considéré comme déchet sans valeur marchande) :

Carrière 1 Carrière 2

graviers calibre 1

graviers calibre 2

graviers calibre 3

0,36 t

0,40 t

0,16 t

0,45 t

0,20 t

0,10 t

Formuler le programme linéaire d’optimisation permettant de définir un programme

d’extraction des carrières P1 et P2 afin de minimiser le coût des redevances à la société

civile. Résoudre par la méthode du simplexe. Donner une représentation graphique.

3

1.2 Dualité

Exercice 8

Soit une entreprise capable de produire deux biens en quantités x1 et x2. Ces pro-

ductions font intervenir deux facteurs fixes : la main d’œuvre et des équipements.

L’emploi de la main d’œuvre est rigide à la hausse et à la baisse, la quantité dis-

ponible étant égale à 2. La capacité de production des équipements est égale à 1 et ils

n’interviennent que pour la production du second bien.

On veut maximiser la marge sur coût variable, les marges unitaires étant de 3/2 et

1 respectivement. Le programme s’écrit de la manière suivante :







Max3/2 x1 + x2

2x1 + x2 ≤ 2

x2 ≤ 1

x1 et x2 ≥ 0

8-1 ) Déterminer graphiquement l’optimum. Pour quelle base I cet optimum est-il

solution réalisable de base ? Calculer le vecteur π(I) des prix duaux associés à cette

solution.

8-2 ) Dans quel domaine peut-on faire varier les seconds membres b1 et b2 des

deux contraintes pour que les prix duaux restent inchangés ? Que se passe-t-il en fron-

tière de ce domaine ?

8-3 ) Partant de l’état initial (cid:0)b0

(cid:1) = (2, 1), on envisage successivement deux

directions de développement : augmenter la main d’œuvre disponible b1 avec une ca-

pacité de production b0

2 fixe ou augmenter la capacité de production b2 avec une main

d’œuvre disponible b0

1 constante. Comment évolue, dans chaque cas, la marge opti-

male ?

1, b0

2

8-4 ) Si le prix d’usage des équipements servant à la fabrication du bien 2 est

p2 = 0, 2 à quelle valeur doit-on fixer la capacité de production b2 ? Même question si

ce prix d’usage est p2 = 0, 4.

8-5 ) On envisage maintenant une augmentation simultanée de la quantité de main

d’œuvre disponible b1 et de la capacité de production b2. On suppose que les accrois-

sements correspondant ∆b1 et ∆b2 sont tels que

∆b2

∆b1

= 1/2

On note p1 et p2 les prix unitaires des deux facteurs fixes. Donner une condition por-

tant sur p1 et p2 pour qu’une telle évolution des moyens de production soit profitable.

On calculera pour cela l’accroissement de marge et l’accroissement de coût fixe cor-

respondant à ∆b1 et ∆b2 . Cette condition est-elle valable quelle que soit l’échelle des

extensions ?

Exercice 9

Une entreprise peut fabriquer un même bien selon trois techniques différentes de

production utilisant les services d’une même machine et de la main d’œuvre. Produire

une unité de bien nécessite :

– 0,5 heure de machine et 2 heures de main d’œuvre avec la première technique ;

– 1,5 heure de machine et 1,5 heure de main d’œuvre pour la deuxième technique ;

– 2 heures de machine et 0,5 heure de main d’œuvre pour la troisième technique.

4

On suppose que la capacité d’usinage de la machine est de 12 heures et que le

nombre d’heures de travail disponibles est de 15 heures. L’entreprise cherche à maxi-

miser sa marge sur coût variable. Les marges unitaires sont de 3 e, 4 e et 5 e selon

que le bien est fabriqué à l’aide de la première, deuxième ou troisième technique.

9-1 ) Si on appelle x1, x2 et x3 les quantités de bien fabriquées selon chaque tech-

nique, écrire le programme correspondant. Le mettre sous forme canonique.

9-2 ) Résoudre le programme numériquement en utilisant l’algorithme du sim-

plexe.

9-3 ) Comment écrire que l’on désire satisfaire au moins une demande de 10 uni-

tés ? Cela modifie-t-il la solution précédente ?

9-4 ) On considère le sommet x1 =

, x2 = 0, x3 =

96

15

66

15

, x4 = x5 = 0.

Quelle est la base I correspondante ? Ce sommet est-il optimal ? On utilisera l’ex-

pression algébrique du critère d’optimalité et on cherchera s’il est vérifié par la base

I.

Exercice 10

Une société fabrique deux produits P1 et P2. Elle est formée d’une division auxi-

liaire (administration) et de deux divisions principales (usinage et finition). L’unité

d’œuvre servant à mesurer l’activité de ces deux dernières divisions est l’heure-machine.

Lors du dernier exercice mensuel, la société a produit 5000 unités de P1 et 7000

unités de P2. La fabrication de P1 a demandé 650 heures-machine de la division usi-

nage et 150 heures-machine de la division finition. La fabrication de P2 a demandé 350

heures-machine de la division usinage et 350 heures-machine de la division finition.

Pendant ce même exercice, les coûts supportés par les sections ont été :

Division

Administration

Usinage

Finition

Frais fixes Frais variables

50 000

60 000

40 000

0

80 000

50 000

Le reste des coûts a pu être affecté directement aux produits. Ces coûts directs, qui

sont des coûts variables, se sont élevés à 12 e par unité de P1 et 5,80 e par unité de

P2. Les prix de vente unitaires de P1 et P2 ont été de 50 e et 30 e respectivement.

10-1 ) Calculer les marges sur coût variable unitaires pour les deux produits P1 et

P2.

10-2 ) Les capacités de production mesurées en heures-machine sont de 1100 pour

la division usinage et de 550 pour la division finition. On considère que la main d’œuvre

est disponible sans limitation. Déterminer graphiquement les productions qui maxi-

misent la marge sur coût variable de la société après avoir formé précisément le pro-

gramme correspondant.

10-3 ) Ecrire les conditions d’optimalité et en déduire les prix duaux π1 et π2

relatifs aux deux divisions principales.

10-4 ) En utilisant ces prix duaux, donner une expression de la marge totale de la

société. Expliquer comment cette marge se répartit entre les deux divisions principales.

10-5 ) Calculer les prix d’usage par heure-machine r1 et r2 de ces deux divisions

(il s’agit des frais fixes supportés, rapportés à l’heure-machine).

10-6 ) Pour chacune des divisions principales, examiner s’il est profitable d’aug-

menter les capacités de production.

5