[PDF] Support de cours : Introduction à la programmation linéaire

View - Download Support de cours : Introduction à la programmation linéaire

Previous PDF

Next PDF

Support de cours : Introduction à la

programmation linéaire

Viet Hung Nguyen

Hung.Nguyen@lip6.fr

UPEC - Master ScTIC0

La programmation linéaire

Forme canonique d"un programme linéaire denvariables non-négatives andmcontraintes : maxcx(1) s.c.(2)

Axb(3)

x0(4) oùcT2Rn(cTestctransposé,cest donc un vecteur ligne),x2Rn,b2Rmet A2Rmn. (02Rnest un vecteur dont tous les composantes sont nulles). (1)est la fonction objectif. (3)sont les contraintes.

UPEC - Master ScTIC1

On peut transformer n"importe quel programme linéaire sous forme canonique : Toute égalitésax=best remplacée par deux inégalitésaxbetaxb. Multiplier par un scalaire négatif pour inverser le sens des inégalités et le sens de l"optimisation (maximisation vs minimisation) si nécessaire. Remplacer les variablesxilibre de signe par la différence des deux variables non-négativesx1ix2i.

UPEC - Master ScTIC2

Exemple

max4x1+5x2 s.c.

2x1+x28

x

1+2x27

x 23
x

10;x20

On ac=4 5,b=2

48
7 33
5 etA=2 42 1
1 2 0 13 5

UPEC - Master ScTIC3

Forme standard

maxcx s.c. Ax=b x0 On peut toujours transformer la forme canonique en forme standard en ajoutant des variables d"écart.

UPEC - Master ScTIC4

Forme canonique

maxcx s.c. Axb x0Forme standard maxcx s.c.

Ax+Ie=b

x0;e0 oùe=2 4e 1... e n3 5

2Rnest le vecteur dont les composantes sont les variables

d"écart.

Exemple.

UPEC - Master ScTIC5

Forme canonique

max4x1+5x2 s.c.

2x1+x28

x

1+2x27

x 23
x

10;x20Forme standard

max4x1+5x2 s.c.

2x1+x2+e1=8

x

1+2x2+e2=7

x

2+e3=3

x

1;x2;e1;e2;e30

On va travailler par la suite sur la forme standard. De plus, on va supposer que l"origine 02Rnest toujours une solution pour la forme canonique du problème.

UPEC - Master ScTIC6

Forme standard : base et solution de base

Pour une question simplification de notations, on re-écrit la forme standard comme suit: maxcx s.c. Ax=b x0 oùc2Rn,x2Rn,b2RmetA2Rmn. SoitJ=f1;:::;ngl"ensemble des indices des colonnes deA. Pour tout sous-ensembleBJ, soitN=JnB et soientABetANrespectivement les sous matrices deAconsistant en les colonnes indexées parBet parN.

UPEC - Master ScTIC7

Forme standard : base et solution de base (cont.)

Définition.Best unebasesiABest carrée (i.e.2mathbbRmm) and régulière (i.e.A1Bexiste). On associe à la baseBle vecteur¯x2Rnqui se décompose en¯xB= A

1Bbet¯xN=0. On appelle¯xsolution de baseB. De plus, si¯x0alors

¯xest unesolution de base réalisable. Dans ce cas, on dit queBestune base réalisable.

Dans la décomposition¯x=¯xB

¯xN

, les composantes de¯xBsont appelées les variables de baseet celles de¯xNsont appeléesles variables hors base.

UPEC - Master ScTIC8

Ré-expression des contraintes principales (hormis les

contraintes de non-négativité) par rapport à une baseÉtant donnée une base réalisableB, on peut récrireAx=benABANxB

x N =bouABxB+ANxN=b.

Multiplier ce système parA1B, on obtient

x

B+A1BANxN=A1Bb

ou encore x

B=A1BbA1BANxN;

UPEC - Master ScTIC9

Coûts réduits ou profits marginaux

Utilisons cette expression pour exprimer la fonction objectif par uniquement les variables hors basexN: cx=cBcNxB x N =cBxB+cNxN=cB(A1BbA1BANxN)+cNxN =cBA1Bb+(cNcBA1BAN)xN SoitP2Rm=cBA1B, les composantes dePsont appeléeles multiplicateurs du simplexe. Soit¯cT2Rnoù¯cB=0et¯cN=cNPTAN. On appelle¯c, le vecteur des coût réduits(si l"objectif est une minimisation) ouprofits marginaux(si l"objectif est une maximisation).

UPEC - Master ScTIC10

Tableau du simplexe associé à une base

Étant donné une baseB, on associe àBle tableau suivant:J BA

1BA¯

b¯cPboù

¯b=A1Bb.

Ce tableau nous renseigne les informations suivantes à propos deB:

Est ce queBest réalisable ? (A1Bb0?)

Est ce queBest optimale ? (¯c0si maximisation et¯c0si minimisation). La solution de basexassociée àBestxB=¯bandxN=0. Elle est réalisable siBest réalisable et elle est optimale siBest optimale.

UPEC - Master ScTIC11

Changement de base

On peut améliorer la solution actuelle si elle n"est pas optimale en faisant un changement de base. La procédure est la suivante. Choisir une variable hors basexjoùj2Ntel que¯cj>0si on est en maximisation et¯cj<0si on est en minimisation. La variablexjest appeléela variable entrante.

Soity=A1BAjla colonnejdu tableau. On calcule

i= argmin(¯bky k:k2Bt:q:yk>0)

La variablexiest appeléela variable sortante.

UPEC - Master ScTIC12

On obtient une nouvelle baseB= (Bn fig)[ fjg. On effectue une opération de pivot sur l"élément à la la ligneiet colonnejpour obtenir le tableau associé à la nouvelle base.

UPEC - Master ScTIC13

Opération de pivot sur le tableau du simplexe

J BA

1BA¯

b¯cPbOn suppose quenpremière colonnes du tableau est indexées parJ. La dernière colonne qui est en fait¯bprend l"indicen+1. Lesmpremières lignes du tableau sont indexées parB. La dernière ligne qui se compose de¯cetPbprend également

l"indicen+1.L"opération de pivot sur l"élément à la ligneiet à la colonnej(i.e. le pivot)

est comme suit.

On divise la ligneipar le pivot.

Tous les éléments de la colonnejà l"exception du pivot deviennent 0. Pour tout autre élément à une lignehet à une colonnek, la nouvelle

UPEC - Master ScTIC14

valeurt0hkest calculée par la formule suivante. t

0hk=thkthjtikt

ij;

UPEC - Master ScTIC15

Méthode du simplex du tableau

Initialisation.

Construire le tab leauassocié à la base f orméepar les variables d"écart.

Pas 1.

Si la base est optimale (i.e .¯c0pour maximisation et¯c0pour minimisation) alors STOP.

Pas 2.

Choisir une v ariableentrante xjtel que¯cj0pour maximisation ou¯cj0pour minimisation. Si la colonnejdu tableau contient que les éléments non-positifs (sauf la dernière ligne) alors STOP le problème est non-borné.

Pas 3.

Déterminer une v ariablesor tantexi.

UPEC - Master ScTIC16

Pas 4.Eff ectuerl"opération de piv otsur l"élément à la ligne iet à la colonnej. Retour au Pas 1.

UPEC - Master ScTIC17

Exercice.

On souhaite tirer le meilleur rendement d"un avion transporteur qui rapporte 3K euros par tonne de fret transportée dans la cabine et 1K euros par tonne de fret transportée dans la soute, sachant que la capacité de la soute est de 20 tonnes et celle de la cabine est de 10 tonnes, que pour des raisons de sécurité, la charge maximale que peut accepter l"avion est de 28 tonnes et enfin que, pour des raisons d"équilibrage, le fret de la cabine amputé d"une tonne ne doit pas excéder les deux tiers du fret de la soute. 1. Modéliser ce pr oblèmecomme un pr ogrammelinéaire sous f orme canonique. 2. Eff ectuerune résolution graphique et en déduire le rendement optimal par vol.

UPEC - Master ScTIC18

3.Mettre le pr ogrammede la Question 1 sous f ormestandar det le

résoudre par la méthode du simplexe tableau.

UPEC - Master ScTIC19

quotesdbs_dbs47.pdfusesText_47

[PDF] mise en forme d'un texte

[PDF] Mise en forme des matériaux

[PDF] mise en forme paragraphe word

[PDF] mise en forme tableau croisé dynamique excel 2010

[PDF] mise en forme word

[PDF] mise en forme word 2007

[PDF] Mise en inéquation : les deux transporteurs

[PDF] mise en inéquation d un problème seconde

[PDF] mise en inéquation d'un problème

[PDF] Mise en inéquation: les deux transporteurs

[PDF] Mise En Mouvement ( Arts Plastique )

[PDF] mise en oeuvre de l'échellle de teintes

[PDF] mise en page d'un scénario

[PDF] mise en page d'une dissertation

[PDF] mise en page d'une lettre