[PDF] [PDF] Correction du Contrôle Continu no 1

[PDF] Exercice 121 Résoudre par le simplexe Max x1 + 2x2 sous −3x1

2) Tableau du simplexe (forme canonique ) x1 x2 x3 x4 x5 z b Exercice 1 2 5 Max x1 sous ⎛ Exercice 1 2 3 Résoudre par la méthode du simplexe

[PDF] 1 Programmation linéaire

Document 4 : Corrigé des exercices d'optimisation linéaire 1 Programmation Le tableau de départ pour la méthode du simplexe est donc : x1 x2 x3 x4 x5 3

[PDF] Algorithme du Simplexe

20 avr 2007 · MATH-F-306 – 3 Algorithme du Simplexe Exercice 3 1 Exercice 3 1 On consid`ere le poly`edre S de R5 défini par les conditions suivantes :

[PDF] exercices corrigés

17 déc 2012 · 2 5 Méthode géométrique et Simplexe 2 5 1 Correction de l'exercice 1 5 1 de la page 12 Il s'agit d'un problème de programmation linéaire

[PDF] Simplexe forme Tableau Exercice corrigés Exercice N° 1 : Soit le

Simplexe forme Tableau Exercice corrigés Exercice N° 1 : Soit le problème de Programmation linéaire suivant : Max Z = 3x1 + 2x2 x1 + 2x2

[PDF] - Exercices de TD - 1 Modélisation - LIRMM

Maximiser le gain de l'année par la méthode du simplexe Effectuer tous les choix possibles de variable entrante lors du premier pivot d Repérer sur le graphique 

[PDF] 174 EXERCICES SUPPLÉMENTAIRES — PARTIE II

Exercice 4 5 1 [Illustration graphique] Illustrez graphiquement l'itération de l' algorithme L'algorithme du simplexe primal passe d'un point extrême réalisable à 

[PDF] CORRIGE du TD N°3 : PROGRAMMATION LINEAIRE EXERCICE 1

Résolvons ce problème de maximisation par la méthode des tableaux simplexe La forme standard associée est : [ ] Sous les contraintes { D'où le premier 

[PDF] Recherche opérationnelle - LMPA

2 2 4 Utilisation de la méthode du simplexe lorsque la solution optimale n'existe pas 60 2 2 5 Utilisation de la méthode du 2 2 6 Exercices récapitulatifs

[PDF] Correction du Contrôle Continu no 1

Exercice 1 : On consid`ere le probl`eme d'optimisation suivant : (PI) Phase I : Nous pouvons maintenant débuter l'application de l'algorithme du simplexe en 

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule

[PDF] multiplicateur fiscal macroéconomie

[PDF] cobb douglas explication

[PDF] revenu d'équilibre formule

[PDF] multiplicateur des dépenses publiques macroéconomie

[PDF] fonction de cobb douglas pdf

[PDF] revenu d'équilibre et revenu de plein emploi

[PDF] fonction cobb douglas ses

[PDF] multiplicateur de depense publique(definition)

[PDF] revenu d'équilibre en économie fermée

IUT Dijon-Auxerre

GEA 2eme annee, GMO, 2015-2016

Correction du Contr^ole Continu n

o1 Exercice 1 :On considere le probleme d'optimisation suivant : (P I)8 >>>:maximiserz= 5x1+ 2x2 sous 2x1+x270 x 130
x

1+x210

x

1;x20:

1.

Apr esl'in troductionde v ariablesd' ecartp ositivese1;e2ete3, le probleme se reecrit sous forme standard de

la maniere suivante : (P S)8 >>>:maximiserz= 5x1+ 2x2 sous 2x1+x2+e1= 70 x

1+e2= 30

x

1+x2e3= 10

x

1;x2;e1;e2;e30:

2.

La troisi emecon traintene p ermetpas de c hoix evidentd'une v ariablede base : le c hoixde e3comme variable

de base conduirait a une contradiction (e3serait negatif) et les variablesx1etx2sont presentes dans les

autres contraintes. On doit donc utiliser la methode des deux phases et on doit formuler un probleme articiel

pour soit trouver une solution de base realisable soit detecter l'impossibilite.

Apres l'introduction d'une variable articiellew1et en integrant l'objectif dans les contraintes, le probleme

articiel associe a (P

I) s'ecrit sous la forme :

(P A)8 >>>>>:minimiserzA=w1 sous 2x1+x2+e1= 70 x

1+e2= 30

x

1+x2e3+w1= 10

5x1+ 2x2z= 0

x

1;x2;e1;e2;e3;w10:

Phase I :Nous pouvons maintenant debuter l'application de l'algorithme du simplexe en phase I par la

methode des tableaux avec pour variables de base initialese1;e2etw1. Le premier tableau est le suivant :H

HHHHHv.b.v.x

1x2e1e2e3w1zzAb

e

121 1 0 0 0 0 0 70

e

210 0 1 0 0 0 0 30

w

111 0 0 -1 1 0 0 10

z52 0 0 0 0 1 0 0 zA00 0 0 0 1 0 1 0

On exprime l'objectif articielzAen fonction des "vraies" variables du probleme en mettant a 0 le coecient

dew1dans la ligne dezApar l'operationL5 L5L3. On obtient le tableau : 1 H

HHHHHv.b.v.x

1x2e1e2e3w1zzAb

e

121 1 0 0 0 0 0 70

e

210 0 1 0 0 0 0 30

w

111 0 0 -1 1 0 0 10

z52 0 0 0 0 1 0 0 zA-1-1 0 0 1 0 0 1 -10 Nous traitons un probleme de minimisation dezAet la ligne dezAcontient des coecients strictement

negatifs. Nous allons pouvoir faire entrer une nouvelle variable dans la base. Celle-ci doit ^etre telle que le

coecient correspondant dans la ligne dezAsoit le "plus negatif" possible. Les variablesx1etx2sont

ex-quo et nous choisissons (arbitrairement) de faire entrerx1dans la base. Pour determiner la variable

sortante, nous calculons les quotients des coecients de la colonne debsur les coecients de la colonne de

x

1dans les lignes 1 a 3. On obtient :

35 p oure1,

30 p oure2,

10 p ourw1.

On doit faire sortir de la base la variable correspondant au quotient le plus petit parmi les positifs, c'est-a-dire

w

1. On doit ensuite utiliser la methode de Gauss-Jordan pour mettre un 1 dans la case reperee parx1et

x

1et des 0 dans le reste de la colonne dex1. En eectuant les operationsL1 L12L3,L2 L2L3,

L

4 L45L3etL5 L5+L3, on obtient :H

HHHHHv.b.v.x

1x2e1e2e3w1zzAb

e

10-1 1 0 2 -2 0 0 50

e

20-1 0 1 1 -1 0 0 20

x

111 0 0 -1 1 0 0 10

z0-3 0 0 5 -5 1 0 -50 zA00 0 0 0 1 0 1 0

Il ne reste plus de coecient strictement negatif dans la ligne dezAet l'algorithme s'arr^ete. La valeur optimale

de l'objectif articiel est 0 et on a determine un sommet de l'ensemble des solutions admissibles pour (P

S) : 0 B BBB@x 1 x 2 e 1 e 2 e 31
C

CCCA=0

B

BBB@10

0 50
20 01 C CCCA:

On peut maintenant supprimer les variables articielles et l'objectif articiel pour passer a la phase II de

maximisation dez. Phase IILa phase II debute avec le tableau suivant :H

HHHHHv.b.v.x

1x2e1e2e3zb

e

10- 11 0 2 0 50

e

20- 10 1 1 0 20

x

111 0 0 -1 0 10

z0- 30 0 5 1 -50 2

Nous traitons un probleme de maximisation dezet la ligne dezcontient des coecients positifs. Nous allons

pouvoir faire entrer une nouvelle variable dans la base. Celle-ci doit ^etre telle que le coecient correspondant dans

la ligne dezsoit le "plus positif" possible. Il s'agit dee3. Pour determiner la variable sortante, nous calculons les

quotients des coecients de la colonne debsur les coecients de la colonne dee3dans les lignes 1 a 3. On obtient :

25 p oure1,

20 p oure2,

|10 pourx1.

On doit faire sortir de la base la variable correspondant au quotient le plus petit parmi les positifs. On choisit donc

de faire sortire2. On doit ensuite utiliser la methode de Gauss-Jordan pour mettre un 1 dans la case reperee par

e

2ete2puis des 0 dans le reste de la colonne dee4. En eectuant les operationsL1 L12L2,L3 L3+L2et

L

4 L45L2, on obtient :H

HHHHHv.b.v.x

1x2e1e2e3zb

e

101 1 -2 0 0 10

e

30-1 0 1 1 0 20

x

110 0 1 0 0 30

z02 0 -5 0 1 -150

Cette fois,x2est la variable entrante. Nous calculons les quotients des coecients de la colonne debsur les

coecients de la colonne dex2dans les lignes 1 a 3 :

10 p oure1,

|20 poure3, |1pourx1, et nous choisissons de faire sortire1de la base.

Les operationsL2 L2+L1etL4 L42L1donnent :H

HHHHHv.b.v.x

1x2e1e2e3zb

x

201 1 -2 0 0 10

e

300 1 -1 1 0 30

x

110 0 1 0 0 30

z00 -2 -1 0 1 -170

Il ne reste plus de coecient strictement positif dans la ligne dez(sauf dans la case reperee parzetz) et

l'algorithme s'arr^ete. On a determine une solution optimale du probleme (P I) : z = 170 atteinte en (x1;x2) = (30;10).

Exercice 2 :

1. (a) Denition des variables :Pouri= 1;2, on notexile nombre d'instrumentsCiproduits en un mois. (b)Denition des contraintes : i. Con trainteli eeau nom brede syst emesde palettes disp oniblesc haquemois : x 130:
ii. Con trainteli eeau nom brede branc hesd'em bouchuredisp oniblesc haquemois : x

1+x2100:

3 iii.Con trainteli eeau nom brede soudures r ealisablesen un mo is: x 1+12 x235; soit en multipliant par 2

2x1+x270:

iv.

Con trainteli eeau con trata vecle distributeur :

x

1+x210:

v.

Con traintesde "b onsens" :

x

12Netx22N

que l'on rel^ache enx1;x20. (c)Denition de l'objectif :Le facteur d'instruments souhaite maximiser sa marge mensuelle brute : z= 5x1+ 2x2 exprimee en centaines d'euros. (d)Formulation du probleme : (P) 8 >>>>>:maximiserz= 5x1+ 2x2 sous 2x1+x270 x 130
x

1+x2100

x

1+x210

x

1;x20:

(e) On remarque que ce p roblemeest tr essimilaire au probl eme(P

I) de l'Exercice 1. Plus precisement, les

deux problemes ne dierent que par la contraintex1+x2100 presente dans (P) mais pas dans (PI). 2.

La con traintepr esentedans (P) mais pas dans (P

I) n'est pas saturee par la solution optimale de (PI) : (x1;x2) = (30;10) (30 + 10 = 40<100). On en deduit qu'une solution optimale de (P) est z = 170

atteinte en (x1;x2) = (30;10). Le facteur d'instruments maximisera sa marge mensuelle brute en produisant

4quotesdbs_dbs13.pdfusesText_19