On peut toujours transformer la forme canonique en forme standard en ajoutant des variables d'écart UPEC - Master ScTIC 4 Page 6 Forme canonique maxcx
Previous PDF | Next PDF |
[PDF] Programmation Linéaire Cours 1 : programmes linéaires
Programme linéaire Résolution graphique Points extrêmes Forme standard, bases Bilan Motivation et objectif du cours Introduction `a la programmation
[PDF] Chapitre 4 Formes générale, canonique et standard dun probl`eme
Dans ce chapitre, nous définissons la forme générale d'un probl`eme d' optimisation linéaire, ainsi que la forme canonique et la forme standard Nous montrons
[PDF] Programmation linéaire et Optimisation
La forme standard associée au primal (apr`es introduction des variables d'écart) aura m = 1000 contraintes pour n = p + q = 1100 inconnues L'algo- rithme du
[PDF] Fondements de la programmation linéaire
≤ 2 En résolvant le problème de cet exemple sous sa forme standard, on obtiendrait comme solution de base réalisable optimale (2,1,0)
[PDF] Support de cours : Introduction à la programmation linéaire - IA - LIP6
On peut toujours transformer la forme canonique en forme standard en ajoutant des variables d'écart UPEC - Master ScTIC 4 Page 6 Forme canonique maxcx
[PDF] Programmation linéaire - LaBRI
13 Programmation linéaire Interprétation géométrique Bases et points extrêmes L'algorithme du simplexe Programmation linéaire Forme standard d'un PL
[PDF] Programmation linéaire - LACIM - UQAM
Forme standard minimiser cTx sous les contraintes Ax = b A Blondin Massé ( UQAM) Chapitre 5: Programmation linéaire MAT7560 Hiver 2019 17 / 54
[PDF] Programmation linéaire
Un problème d'optimisation linéaire sous forme standard est un problème de la forme (P LS) min Ax=b x≥0 c · x Proposition 2 3 Tout problème d'optimisation
[PDF] Programmation linéaire
Peut-on mettre le problème suivant sous forme standard ? Minimiser : cx Sous les contraintes : Ax = b et l ≤ x ≤ u Exercice Donner une solution optimale pour
[PDF] Chapitre I : Programmation linéaire
La méthode du simplexe nécessite la mise sous forme standard du programme linéaire à résoudre en ajoutant autant de variables d'écart qu'il y a de
[PDF] programmation lineaire methode simplexe
[PDF] programmation linéaire recherche opérationnelle
[PDF] interprétation droite de henry
[PDF] principe droite de henry
[PDF] exercice corrigé droite de henry
[PDF] courbe de henry excel
[PDF] droite de henry pdf
[PDF] programmation linéaire exercices corrigés pdf
[PDF] programmation linéaire exercices corrigés
[PDF] programmation linéaire simplexe
[PDF] recherche opérationnelle programmation linéaire exercices corrigés pdf
[PDF] exercices recherche operationnelle
[PDF] recherche opérationnelle cours complet
[PDF] cours recherche opérationnelle methode de simplexe
Support de cours : Introduction à la
programmation linéaireViet 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
x1+2x27
x 23x
10;x20
On ac=4 5,b=2
487 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 52Rnest le vecteur dont les composantes sont les variables
d"écart.Exemple.
UPEC - Master ScTIC5
Forme canonique
max4x1+5x2 s.c.2x1+x28
x1+2x27
x 23x
10;x20Forme standard
max4x1+5x2 s.c.2x1+x2+e1=8
x1+2x2+e2=7
x2+e3=3
x1;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= A1Bbet¯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 lescontraintes 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
xB+A1BANxN=A1Bb
ou encore xB=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 BA1BA¯
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 BA1BA¯
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 égalementl"indicen+1.L"opération de pivot sur l"élément à la ligneiet à la colonnej(i.e. le pivot)
est comme suit.