UNIVERSIT PARIS OUEST NANTERRE LA DFENSEU.F.R. SEGMI Anne universitaire 2012 2013Master dconomie Cours de M. Desgraupes

Mthodes Numriques

Document 1 : Programmation linaire

1 Programmation linaire 11.1 Mthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Dualit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1 Programmation linaire

1.1 Mthode du simplexe

Exercice 1Rsoudre les programmes suivants par la mthode du simplexe.

Max (x1 + 2x2)

x1 + 3x2 21x1 + 3x2 18x1 x2 5x1 et x2 0

Min (x1 3x2)

3x1 2x2 7x1 + 4x2 92x1 + 3x2 6

x1 et x2 0

Exercice 2Une raffinerie de ptrole traite deux sortes de brut pour donner des produits finis

avec les rendements suivants :

Brut 1 Brut 2Essence 25% 35%Gasoil 30% 30%Fuel 45% 35%

Les quotas de production imposent de fabriquer au plus 825 milliers de m3 des-sence, 750 milliers de m3 de gas oil et 1065 milliers de m3 de fuel. La marge bnfi-ciaire laisse par le traitement du brut 1 est de 3 milliers deuros par millier de m3 etcelle du brut 2 est de 4 milliers deuros par millier de m3.

Calculer, par la mthode du simplexe, quelles quantits de chaque ptrole il fauttraiter pour obtenir un bnfice maximal. Donner une interprtation graphique.

Exercice 3Trouver un programme de base initial pour les problmes suivants par la mthode

des valeurs ajoutes, puis les rsoudre par la mthode du simplexe :

1

Max (x1 x2 + x3)3x1 + 2x2 + x3 = 1x1 x2 x3 + x4 = 3

x1 + 4x2 + 2x3 2x4 = 1x1, x2, x3 et x4 0

Max (x1 + 2x2 + 3x3)

x1 + x2 52x1 + 2x2 x3 = 6

12x1 + 8x2 5x3 = 32x1, x2 et x3 0

Exercice 4Une raffinerie fabrique deux qualits dessence (A et B) en mlangeant dans cer-

taines proportions deux produits semi-finis (P1 et P2). Les indices doctane et les quan-tits disponibles par jour pour ces deux produits sont indiqus dans le tableau suivant :

Indice doctane Nb. de barils/jourProduit 1 71 3900Produit 2 99 5000

Lindice doctane de lessence A doit tre dau moins 96 et celui de lessence Bdau moins 85. La raffinerie vend toute sa production de A et B aux prix respectifs de3,75 $ et 2,75 $ par baril. Les excdents ventuels de P1 sont revendus au prix de 1,25 $par baril une fabrique de goudron et ceux de P2 sont revendus un terrain daviationau prix de 2,25 $ par baril.

On notera x1A et x2A (resp. x1B et x2B) le nombre de barils de P1 et de P2 utilisspour fabriquer A (resp. B).

4-1 ) Calculer, en fonction de x1A et x2A, lindice doctane de A.4-2 ) Ecrire le programme correspondant loptimisation du profit de la raffinerie.4-3 ) Rsoudre ce programme par la mthode du simplexe.4-4 ) Indiquer en % la composition des essences A et B, solutions du problme.Quel est finalement leur indice doctane ?

Exercice 5Dans une entreprise qui fabrique des pices dtaches la demande un client dsire

commander des pices A et B dans un dlai dun mois. Fournisseur et client se sont misdaccord sur les prix suivants : 138 e par srie de 100 pices A et 136 e par srie de100 pices B. La ralisation des pices A et B ncessite un passage dans trois atelierspour lesquels on dispose des renseignements suivants :

Nb dunits doeuvre Nb dunits doeuvre Cot variablepour 100 pices A pour 100 pices B dune unit doeuvre

Atelier T 2 1 10 eAtelier F 1 4,5 12 eAtelier M 4 3 14 e

Au moment de la commande, lentreprise ne dispose que dun nombre limit dheuresdans chaque atelier correspondant respectivement : 200 units doeuvre pour latelierT, 540 units doeuvre pour latelier F, 480 units doeuvre pour latelier M.

Ces nombres dunits doeuvre sont insuffisants pour satisfaire le client dans ledlai demand. Lentreprise lui propose une livraison partielle.

Quelles quantits de pices A et de pices B lentreprise a-t-elle intrt fabriquerau cours du mois si elle veut obtenir une marge maximum compte-tenu des moyens

2

de production disponibles. On utilisera la mthode du simplexe dont on donnera par lasuite une interprtation graphique.

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

modles, A et B, seront fabriqus essentiellement dans trois ateliers pour lesquels ondispose des renseignements suivants :

Temps opratoire Temps opratoire Temps Cotunitaire unitaire disponible variable de

pour le modle A pour le modle B (en heures) lheureEmboutissage 50 mn 40 mn 2500 h 150 e

Soudure 30 mn 20 mn 1000 h 60 ePeinture 20 mn 10 mn 800 h 20 e

Une tude de march a par ailleurs rvl que les prix de vente devaient tre fixs 215 e pour le modle A et 150 e pour le modle B, le march du modle A tant entout tat de cause satur avec 1800 articles.

On demande de dterminer un plan optimal de fabrication et la marge loptimumpar lalgorithme du simplexe.

Exercice 7Une socit se consacre lexcavation et la distribution de matriaux de carrire.

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 quantits

suivantes :13 500 tonnes de graviers de calibre 111 200 tonnes de graviers de calibre 25 000 tonnes de graviers de calibre 3.La socit exploite deux carrires P1 et P2 loues une socit civile qui peroit

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

Aprs extraction, le pierre est concasse et les graviers ainsi obtenus sont tris selonleur calibre. Chaque tonne de pierre fournit les quantits suivantes (le complmentreprsente du sable considr comme dchet sans valeur marchande) :

Carrire 1 Carrire 2graviers calibre 1 0,36 t 0,45 tgraviers calibre 2 0,40 t 0,20 tgraviers calibre 3 0,16 t 0,10 t

Formuler le programme linaire doptimisation permettant de dfinir un programmedextraction des carrires P1 et P2 afin de minimiser le cot des redevances la socitcivile. Rsoudre par la mthode du simplexe. Donner une reprsentation graphique.

3

1.2 Dualit

Exercice 8Soit une entreprise capable de produire deux biens en quantits x1 et x2. Ces pro-

ductions font intervenir deux facteurs fixes : la main duvre et des quipements.Lemploi de la main duvre est rigide la hausse et la baisse, la quantit dis-

ponible tant gale 2. La capacit de production des quipements est gale 1 et ilsninterviennent que pour la production du second bien.

On veut maximiser la marge sur cot variable, les marges unitaires tant de 3/2 et1 respectivement. Le programme scrit de la manire suivante :

Max3/2 x1 + x2

2x1 + x2 2x2 1x1 et x2 0

8-1 ) Dterminer graphiquement loptimum. Pour quelle base I cet optimum est-ilsolution ralisable de base ? Calculer le vecteur (I) des prix duaux associs cettesolution.

8-2 ) Dans quel domaine peut-on faire varier les seconds membres b1 et b2 desdeux contraintes pour que les prix duaux restent inchangs ? Que se passe-t-il en fron-tire de ce domaine ?

8-3 ) Partant de ltat initial(b01, b

02

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

directions de dveloppement : augmenter la main duvre disponible b1 avec une ca-pacit de production b02 fixe ou augmenter la capacit de production b2 avec une mainduvre disponible b01 constante. Comment volue, dans chaque cas, la marge opti-male ?

8-4 ) Si le prix dusage des quipements servant la fabrication du bien 2 estp2 = 0, 2 quelle valeur doit-on fixer la capacit de production b2 ? Mme question sice prix dusage est p2 = 0, 4.

8-5 ) On envisage maintenant une augmentation simultane de la quantit de mainduvre disponible b1 et de la capacit de production b2. On suppose que les accrois-sements correspondant b1 et b2 sont tels que

b2b1

= 1/2

On note p1 et p2 les prix unitaires des deux facteurs fixes. Donner une condition por-tant sur p1 et p2 pour quune telle volution des moyens de production soit profitable.On calculera pour cela laccroissement de marge et laccroissement de cot fixe cor-respondant b1 et b2 . Cette condition est-elle valable quelle que soit lchelle desextensions ?

Exercice 9Une entreprise peut fabriquer un mme bien selon trois techniques diffrentes de

production utilisant les services dune mme machine et de la main duvre. Produireune unit de bien ncessite :

0,5 heure de machine et 2 heures de main duvre avec la premire technique ; 1,5 heure de machine et 1,5 heure de main duvre pour la deuxime technique ; 2 heures de machine et 0,5 heure de main duvre pour la troisime technique.

4

On suppose que la capacit dusinage de la machine est de 12 heures et que lenombre dheures de travail disponibles est de 15 heures. Lentreprise cherche maxi-miser sa marge sur cot variable. Les marges unitaires sont de 3 e, 4 e et 5 e selonque le bien est fabriqu laide de la premire, deuxime ou troisime technique.

9-1 ) Si on appelle x1, x2 et x3 les quantits de bien fabriques selon chaque tech-nique, crire le programme correspondant. Le mettre sous forme canonique.

9-2 ) Rsoudre le programme numriquement en utilisant lalgorithme du sim-plexe.

9-3 ) Comment crire que lon dsire satisfaire au moins une demande de 10 uni-ts ? Cela modifie-t-il la solution prcdente ?

9-4 ) On considre le sommet x1 =96

15, x2 = 0, x3 =

66

15, x4 = x5 = 0.

Quelle est la base I correspondante ? Ce sommet est-il optimal ? On utilisera lex-pression algbrique du critre doptimalit et on cherchera sil est vrifi par la baseI .

Exercice 10Une socit fabrique deux produits P1 et P2. Elle est forme dune division auxi-

liaire (administration) et de deux divisions principales (usinage et finition). Lunitduvre servant mesurer lactivit de ces deux dernires divisions est lheure-machine.

Lors du dernier exercice mensuel, la socit a produit 5000 units de P1 et 7000units 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 350heures-machine de la division usinage et 350 heures-machine de la division finition.Pendant ce mme exercice, les cots supports par les sections ont t :

Division Frais fixes Frais variablesAdministration 50 000 0Usinage 60 000 80 000Finition 40 000 50 000

Le reste des cots a pu tre affect directement aux produits. Ces cots directs, quisont des cots variables, se sont levs 12 e par unit de P1 et 5,80 e par unit deP2. Les prix de vente unitaires de P1 et P2 ont t de 50 e et 30 e respectivement.

10-1 ) Calculer les marges sur cot variable unitaires pour les deux produits P1 etP2.

10-2 ) Les capacits de production mesures en heures-machine sont de 1100 pourla division usinage et de 550 pour la division finition. On considre que la main duvreest disponible sans limitation. Dterminer graphiquement les productions qui maxi-misent la marge sur cot variable de la socit aprs avoir form prcisment le pro-gramme correspondant.

10-3 ) Ecrire les conditions doptimalit et en dduire les prix duaux 1 et 2relatifs aux deux divisions principales.

10-4 ) En utilisant ces prix duaux, donner une expression de la marge totale de lasocit. Expliquer comment cette marge se rpartit entre les deux divisions principales.

10-5 ) Calculer les prix dusage par heure-machine r1 et r2 de ces deux divisions(il sagit des frais fixes supports, rapports lheure-machine).

10-6 ) Pour chacune des divisions principales, examiner sil est profitable daug-menter les capacits de production.

5