[PDF] Programmation lin eaire et Optimisation

Programmation Lin aire Cours 1 : programmes lin aires, mod

Exemples Programme lin´eaire R´esolution graphique Points extrˆemes Forme standard, bases Bilan Forme normale d’un programme lin´eaire Tout programme lin´eaire peut s’´ecrire sous forme normale max P n i=1 c ix i sous les contraintes P n i=1 a ijx i ≤b j,(j= 1, ,m) x i ≥0,x i ∈R,(i= 1, ,n) Si on a une variable x i ∈R, on

Programmation Linéaire - École nationale supérieure d

•Définition d’un programme linéaire •Résolution graphique •Algorithme du simplexe •Méthode des tableaux •Méthode des 2 phases •Utilisation du « solveur » Excel •Conclusion •Annexes 2

Programmation linéaire

2 CHAPITRE 1 INTRODUCTION 1 2 Un exemple résolu par voie graphique Problème: La direction d’une usine de meubles a constaté qu’il y a des temps morts dans chacun des départements de l’usine

Chapitre I : Programmation linéaire

déterminer un plan de production de chaises et de tables optimal Pour ce faire, une modélisation sous forme dun programme linéaire simpose b) Modélisation La construction d¶un modèle est, en général, une opération en trois étapes : 1- Le choix des variables de décision 2- Lexpression de l¶objectif en fonction de ces variables

De lintérêt du théorème de la forme globale en programmation

2 3 Résolution graphique La méthode de résolution graphIque est une mélhode qui s'applique aux programmes linéaires comportant deux ou trois vaoables pour en fournir le (ou les) soJulion(s) optimale(s) si ellc(s) exi,tetnt), Le processus de rés o luuon graphique d'un rogramme linéaire à deux variables peut se résumer 8 lnsi :

Programmation lin eaire et Optimisation

Un probl eme d’optimisation lin eaire en dimension sup erieure Dans ce chapitre, nous allons d ecrire un probl eme de transport optimal assimilable a un probl eme d’optimisation lin eaire en dimension 6 De ce fait, il ne sera plus possible de le r esoudre au moyen de la m ethode graphique du chapitre pr ec edent

Résolution de systèmes linéaires : Méthodes directes Polytech

On ne change pas la solution d’un système linéaire lorsque : on permute deux lignes, on permute deux colonnes, on multiplie une ligne par un réel non nul, on ajoute une ligne à une autre Nous allons donc utiliser ces transformations pour se ramener à un cas simple

Recherche op erationnelle - Université du Littoral Côte dOpale

Beaucoup d’autres probl`emes de recherche op´erationnelle peuvent ˆetre exprim´es comme des probl`emes d’optimisation lin´eaire En optimisation, qui est une branche des math´ematiques, un probl`eme d’optimisation lin´eaire est un probl`eme d’optimisation dans lequel on minimise une fonction lin´eaire sur un poly`edre convexe

LAIRET CONSEIL DADMINISTRATIONCONSEIL DADMINISTRATION

cette activité Il s’agit d’une facture au montant de 67,72 $ à l’ordre du Lydie Colaye, graphiste RÉSOLUTION 10RÉSOLUTION 10- ---CACCAACA- ---15115515 concernant concernant le paiement pour les frais le paiement pour les fraisle paiement pour les frais d'adaptation graphique de la d'adaptation graphique de la

[PDF] résolution graphique d'un système d'inéquation ? 2 inconnues

[PDF] résolution graphique d'un système de deux équations ? deux inconnues

[PDF] Résolution graphique et algébrique d'une inéquation

[PDF] Résolution graphique et algébrique de fonction et translation

[PDF] resolution graphique fonction

[PDF] resolution graphique inequation seconde exercices

[PDF] resolution graphique SECONDE

[PDF] resolution graphique statique

[PDF] Résolution graphique système équations

[PDF] Résolution graphique, et calcul

[PDF] résolution image

[PDF] résolution image dpi

[PDF] resolution image hd

[PDF] resolution image wikipedia

[PDF] resolution inéquation

Programmation lineaire et Optimisation

Didier Smets

Chapitre 1

Un probleme d'optimisation lineaire

en dimension 2 On considere le cas d'un fabricant d'automobiles qui propose deux modeles a la vente, des grosses voitures et des petites voitures. Les voitures de ce fabriquant sont tellement a la mode qu'il est certain de vendre tout ce qu'il parvient a produire, au moins au prix catalogue actuel de 16000 euros pour les grosses voitures, et 10000 euros pour les petites voitures. Son probleme vient de l'approvisionnement limite en deux matieres premieres, le caoutchouc et l'acier. La construction d'une petite voiture necessite l'emploi d'une unite de caoutchouc et d'une unite d'acier, tandis que celle d'une grosse voiture necessite une unite de caoutchouc mais deux unites d'acier. Sachant que son stock de caoutchouc est de 400 unites et son stock d'acier de 600 unites, combien doit-il produire de petites et de grosses voitures au moyen de ces stocks an de maximiser son chire d'aaire? Nous appelleronsxle nombre de grosses voitures produites,yle nombre de petites voitures produites, etzle chire d'aaire resultant. Le probleme se traduit alors sous la formemaximiserz= 16000x+ 10000y sous les contraintesx+y400

2x+y600

x0; y0:(1.1)

1.1 Solution graphique

Un tel systeme, parce qu'il ne fait intervenir que deux variables, peu se resoudre assez facilement de maniere graphique, en hachurant la zone correspondant aux contraintes, et en tracant les lignes de niveaux (ici des lignes paralleles) de la fonction a maximiser (cfr. graphique ci-dessous). On obtient ainsi la solution optimalex= 200 ety= 200, qui correspond az= 5200000:Elle est unique dans ce cas precis, et correspond a un \sommet" de la zone de contraintes. 1

1.2 Sensibilite a la variation des stocks

Observons comment la solution du probleme evolue lorsqu'on modie certaines donnees de depart, par exemple une augmentation du stock de caoutchouc ou du stock d'acier. Imaginons que le stock d'acier soit de 700 au lieu de 600, le nouveau probleme s'ecrit maximiserz= 16000x+ 10000y sous les contraintesx+y400

2x+y700

x0; y0:(1.2) Toujours de maniere graphique, on s'apercoit que la solution optimale est maintenant donnee parx= 300 ety= 100, ce qui correspond az= 5800000:Autrement dit, une augmentation de 100 unites d'acier a un impact de 600000 euros sur le chire d'aaire. On dira alors que leprix marginalde l'unite d'acier est de 6000 euros. 2 Si le stock d'acier passe a 800, la solution optimale devientx= 400 ety= 0 et le chire d'aairez= 6400000:Augmenter le stock d'acier au-dela de 800, sans changer le stock de caoutchouc, n'a plus aucune in uence sur la solution optimale, caryest contraint a rester positif. Imaginons maintenant que le stock d'acier reste xe a 600 mais que le stock de caou- tchouc passe de 400 a 500. Le nouveau probleme s'ecrit maximiserz= 16000x+ 10000y sous les contraintesx+y500

2x+y600

x0; y0:(1.3) Toujours de maniere graphique, on s'apercoit que la solution optimale est maintenant donnee parx= 100 ety= 400, ce qui correspond az= 5600000:Autrement dit, une augmentation de 100 unites de caoutchouc a un impact de 400000 euros sur le chire 3 d'aaire. On dira alors que leprix marginalde l'unite de caoutchouc est de 4000 euros. Si le stock de caoutchouc passe a 600, la solution optimale devientx= 0 ety= 600 et le chire d'aairez= 6000000:Augmenter le stock de caoutchouc au-dela de 600, sans changer le stock d'acier, n'a plus aucune in uence sur la solution optimale, carxest contraint a rester positif. 4

1.3 Le probleme dual du concurrent

Supposons maintenant que le fabricant d'automobile possede un concurrent qui, pour honorer des commandes en trop grand nombre, se propose de lui racheter tous ses stocks. Ce dernier doit faire une ore de prix (la m^eme, disonsu) pour chaque unite de caoutchouc et une ore de prix (disonsv) pour chaque unite d'acier. Pour que l'ore soit acceptee, il faut que le prix paye par le concurrent soit au moins egal a ce que le fabriquant pourrait en tirer en produisant des voitures. Le probleme du concurrent s'ecrit ainsi minimiserp= 400u+ 600v sous les contraintesu+v10000 u+ 2v16000 u0; v0:(1.4) Une analyse graphique fournit la solution optimaleu= 4000 etv= 6000, ce qui corres- pond a un prix globalp= 5200000:On remarque (nous verrons par la suite que ce n'est pas un hasard) que la solution optimale du probleme du concurrent (on parlera deprobleme dual, par opposition auprobleme primaldu fabriquant) correspond aux prix marginaux du probleme du fabricant, et que le prix minimal que puisse proposer le concurrent est egal au chire d'aaire maximal du fabricant. 5

Chapitre 2

Un probleme d'optimisation lineaire

en dimension superieure Dans ce chapitre, nous allons decrire un probleme de transport optimal assimilable a un probleme d'optimisation lineaire en dimension 6. De ce fait, il ne sera plus possible de le resoudre au moyen de la methode graphique du chapitre precedent. Notre fabricant d'automobiles possede trois cha^nes de montageM1,M2etM3, tandis que son stock d'acier provient de deux acieriesA1etA2:Les co^uts de transport d'une unite d'acier d'une acierie vers une usine de montage sont donnes par le tableau suivant :M 1M 2M 3A

191628

A

2142919

Les besoins de production des cha^nes de montage dierent, ainsi que les capacites de production des acieries, et sont donnees par les deux tableaux suivants :A 1206
A 2394M
1142
M 2266
M 3192
Il s'agit donc pour le fabricant de determiner le plan de transport des unites d'acier produites vers les cha^nes de montage an de minimiser le co^ut total de transport. Pour i= 1;2 etj= 1;2;3, notonsxijle nombre d'unites d'acier acheminees depuis l'acierieAi vers la cha^ne de montageMj:Le probleme de transport optimal peut alors s'ecrire : minimisert= 9x11+16x12+28x13+14x21+29x22+19x23 sous les contraintesx11+x12+x13206; x

21+x22+x23394;

x

11+x21142;

x

12+x22266;

x

13+x23192;

x

11; x12; x13; x21; x22; x230:

Nous verrons par la suite qu'il est possible de traiter un tel probleme de maniere systematique, par le biais d'une reduction a une forme standard suivie d'un algorithme 6 qui porte le nom de methode du simplexe. Toutefois, dans ce cas precis, cela nous menerait a des manipulations trop fastidieuses pour ^etre realisees sans l'aide d'un ordinateur. A sa place, nous allons proceder a un certain nombre de remarques ad hoc qui vont nous permettre de poursuivre les calculs a la main. La remarque principale ici est que dans la mesure ou la somme des capacites productions des acieries (206 + 394 = 600) est egale a la somme des besoins de production des trois cha^nes de montage (142 + 266 + 192 = 600), chacune des 5 premieres inegalites dans le probleme d'optimisation ci-dessus doit necessairement ^etre une egalite. Si on omet momentanement de s'occuper des contraintesxij0 (i= 1;2,j= 1;2;3), les contraintes restantes se reduisent a un systeme de 5 equations a 6 inconnues, que nous pouvons tenter de resoudre par la methode du pivot de Gauss (cfr. Algebre lineaire L1). On recrit le sous-systeme des contraintes d'egalite sous la forme (on choisit l'ordre des equation an de faciliter le pivot de Gauss) : x

11+x21= 142;

x

12+x22= 266;

x

13+x23= 192;

x

11+x12+x13= 206;

x

21+x22+x23= 394:

On echelonne ensuite (methode du tableau) :

0 B

BBB@1 0 0 1 0 0j142

0 1 0 0 1 0j266

0 0 1 0 0 1j192

1 1 1 0 0 0j206

0 0 0 1 1 1j3941

C

CCCA!0

B

BBB@1 0 0 1 0 0j142

0 1 0 0 1 0j266

0 0 1 0 0 1j192

0 1 11 0 0j64

0 0 0 1 1 1j3941

C CCCA! 0 B

BBB@1 0 0 1 0 0j142

0 1 0 0 1 0j266

0 0 1 0 0 1j192

0 0 111 0j 202

0 0 0 1 1 1j3941

C

CCCA!0

B

BBB@1 0 0 1 0 0j142

0 1 0 0 1 0j266

0 0 1 0 0 1j192

0 0 0111j 394

0 0 0 1 1 1j3941

C CCCA! 0 B

B@1 0 0 1 0 0j142

0 1 0 0 1 0j266

0 0 1 0 0 1j192

0 0 0 1 1 1j3941

C CA!0 B

B@1 0 0 011j 252

0 1 0 0 1 0j266

0 0 1 0 0 1j192

0 0 0 1 1 1j3941

C CA: La forme echelonnee laisse appara^tre les variablesx22etx23comme libres, desquelles on deduitx

21= 394x22x23;

x

13= 192x23;

x

12= 266x22;

x

11=252 +x22+x23:(2.1)

On exprime ensuite le co^uttuniquement en termes des variables libresx22etx23: t= 9(252 +x22+x23) + 16(266x22) + 28(192x23) + 14(394x22x23) + 29x22+ 19x23 = 8x2214x23+ 12880:(2.2) 7 An de minimisertil est donc opportun de choisirx23le plus grand possible, etx22le plus petit possible. C'est a ce niveau qu'il nous est necessaire de faire reappara^tre les contraintesxij0 (i= 1;2,j= 1;2;3), sans lesquellestpourrait ^etre rendu aussi negatif que souhaite. En examinant les equation (2.1), on se convainc assez rapidement que le meilleur choix est obtenu en prenantx23= 192 (an de satisfaire mais saturer la contrainte x

130), et ensuitex22= 60 (an de satisfaire mais saturer la contraintex110). On

propose alors la solution suivante x

11= 0;

x

12= 206;

x

13= 0;

x

21= 142;

x

22= 60;

x

23= 192;(2.3)

comme candidat a ^etre le transport optimal. Pour verier notre intuition, on choisit d'ex- primer cette fois le systeme (2.1) uniquement en termes des variablesx11etx13(on com- prendra ce choix dans un instant), ce qui donne (on n'a en realite besoin que d'exprimer x

22etx33puisqu'elles seules interviennent dans l'expression detdans (2.2)) :

x

22= 60 +x11+x13;

x

23= 192x13:(2.4)

On obtient ainsi l'expression

t= 8x2214x23+ 12880 = 8(60 +x11+x13)14(192x13) + 12880 = 8x11+ 22x13+ 10672:(2.5) Commex110 etx130 par contrainte, on a necessairementt10672 quel que soit le choix dexij(i= 1;2,j= 1;2;3) satisfaisant l'ensemble des contraintes. Par ailleurs, le choix propose en (2.3) fournitt= 10672 et satisfait a l'ensemble des contraintes. Il s'agit donc eectivement de la solution optimale. Pour terminer cet exemple par une synthese, observons que nous sommes parvenus a recrire le probleme d'optimisation initial sous la forme d'un systeme lineaire augmente de contraintes de positivite de toutes les variables. Nous avons ensuite determine le rang du systeme lineaire en question et exprime de diverses manieres possibles (deux en l'occur- rence) la fonction a optimiser (icit) en termes de variables libres pour ce systeme lineaire. Nous nous sommes arr^etes lorsque les coecients des variables libres dans l'expression de la fonction a optimiser furent tous positifs ou nuls, et avons conclu que les egaler a zero fournissait une solution assurement optimale. Dans le chapitre qui suit, nous reprenons cette demarche de maniere un peu plus systematique sur un exemple initialement en dimension 3. 8

Chapitre 3

Methode du simplexe : un apercu

par l'exemple

Considerons le probleme d'optimisation lineaire :

maximiserz= 5x1+4x2+3x3 sous les contraintes 2x1+3x2+x35;

4x1+x2+2x311;

3x1+4x2+2x38;

x

1; x2; x30:(3.1)

An de se ramener a un systeme d'equations plut^ot que d'inequations, on introduit les variables d'ecartx4;x5;x6et l'on ecrit le probleme ci-dessus sous la forme x

4= 52x13x2x3;

x

5= 114x1x22x3;

x

6= 83x14x22x3;

z= 5x1+4x2+3x3;(3.2) avec pour but de maximiserzsous les contraintes additionnellesxi0;(i= 1;;6):Il est aise (et recommande) de verier que si (x1;x2;x3;x4;x5;x6) est une solution optimale de ce dernier probleme, alors les (x1;x2;x3) correspondants constituent une solution op- timale du probleme (3.1). Inversement, si (x1;x2;x3) est une solution optimale de (3.1), alors (x1;x2;x3;52x13x2x3;114x1x22x3;83x14x22x3) constitue une solution optimale de (3.2). Le systeme (3.2) possede la solution (non optimale) (0;0;0;5;11;8) (l'usage est d'ap- pelersolution realisabletout choix de variables satisfaisant a l'ensemble des contraintes (cfr. le chapitre suivant)). On observe que dans l'expressionz= 5x1+4x2+3x3, une augmentation dex1entra^ne une augmentation dez:L'idee premiere est alors d'augmenterx1autant que possible (sans modier nix2nix3) tant qu'aucune des variables d'ecartx4;x5oux6ne devient negative. Le choix maximal est doncx1= min(5=2;11=4;8=3) = 5=2, lorsquex4devient nulle, et qui fait passer a la solution realisable (5=2;0;0;0;3;1=2): On recrit le systeme (3.2) en exprimant cette fois (x1;x5;x6) (ainsi quez) en termes 9 de (x2;x3;x4), au moyen de l'equation x 1=52 32
x212 x312 x4:

Ceci donne, apres substitutions :

x 1=52 32
x212 x312 x4; x

5= 1 +5x2+2x4;

x 6=12 +12 x212 x3+32 x4; z=252 72
x2+12 x352 x4:(3.3) Cette fois, on observe que dans l'expressionz= 25=27=2x2+ 1=2x35=2x4;une augmentation dex3(c'est ici le seul choix possible) entra^ne une augmentation dez: A nouveau, on augmente doncx3autant que possible (sans modier nix2nix4) tant qu'aucune des variables (ditesvariables en bases(cfr. Chapitre 5))x1;x5oux6ne devient negative. Le choix maximal est doncx3= min((5=2)=(1=2);(1=2)=(1=2)) = 1, lorsquex6 devient nulle, et qui fait passer a la solution realisable (2;0;1;0;1;0): On recrit le systeme (3.3) en exprimant cette fois (x1;x3;x5) (ainsi quez) en termes de (x2;x4;x6), au moyen de l'equation x

3= 1 +x2+ 3x42x6:

Ceci donne, apres substitutions :

x

1= 22x22x4+x6;

x

3= 1 +x2+3x42x6;

x

5= 1 +5x2+2x4;

z= 133x2x4x6:(3.4) Puisque les coecients dex2;x4etx6intervenant dans l'expression dezci-dessus sont tous negatifs ou nuls, on deduit que la solution realisable x 1= 2; x 2= 0; x 3= 1; x 4= 0; x 5= 1; x

6= 0;(3.5)

est une solution optimale, pour laquellez= 13: Avant de formaliser l'algorithme du simplexe, et d'en decouvrir les bases theoriques, voyons une deuxieme methode pour l'aborder et qui consiste a placer les calculs en tableau (toutes les variables se retrouvant du m^eme c^ote du signe d'egalite) plut^ot que sous forme dictionnaire comme ci-dessus. L'avantage de cette deuxieme facon de presenter les choses (mais qui est bien s^ur equivalente a la premiere) et qu'elle se rapproche plus de la methode bien connue du pivot de Gauss. 10 Considerons donc maintenant le probleme d'optimisation lineaire maximiserz=x1+5x2+x3 sous les contraintesx1+3x2+x33; x1+3x32;

2x1+4x2x34;

x

1+3x2x32;

x

1; x2; x30:(3.6)

On introduit les variables d'ecartx4;x5;x6;x7(il y a une contrainte supplementaire par rapport au probleme precedent) et on recrit le probleme sous la forme maximiserz=x1+5x2+x3 sous les contraintesx1+3x2+x3+x4= 3; x1+3x3+x5= 2;

2x1+4x2x3+x6= 4;

x

1+3x2x3+x7= 2;

x

1; x2; x3x4; x5; x6; x70:(3.7)

On adopte alors la notation sous forme de tableau :

1 3 1 1 0 0 0j3

1 0 3 0 1 0 0j2

2 41 0 0 1 0j4

1 31 0 0 0 1j21 5 1 0 0 0 0j0

La derniere ligne du tableau correspond a un expression possible dezcomme fonction ane des variablesx1;;x7, l'oppose du terme constant se trouvant en bas a droite du tableau. On part de la solution realisable (0;0;0;3;2;4;2) et puisque le terme enx1dans la derniere ligne du tableau (=1) est positif, on va augmenterx1(sans modier nix2ni x

3) jusqu'a ce que l'une des variablesx4;x5;x6oux7devienne nulle. Ceci se produit pour

x

1= 2 pour lequel a la foisx6etx7deviennent nuls. On choisit donc de faire rentrerx1

en base, et de faire sortir (par exemple)x6. Cela donne

1 3 1 1 0 0 0j3

1 0 3 0 1 0 0j2

2 41 0 0 1 0j4

1 31 0 0 0 1j21 5 1 0 0 0 0j0!1 3 1 1 0 0 0j3

1 0 3 0 1 0 0j2

1 212 0 012 0j2

1 31 0 0 0 1j21 5 1 0 0 0 0j0!

0 1 32
1 012 0j1quotesdbs_dbs49.pdfusesText_49