La notion de dualit¶e Dual d’un PL sous forme standard
Dual d’un PL sous forme standard Un programme lin¶eaire est caract¶eris¶e par le tableau simplexe " A b c #: Par d¶eflnition, le problµeme dual est obtenu en transposant ce tableau " AT cT bT #: Soit v 2
IFT 2505 Programmation Lin eaire - Université de Montréal
Simplexe primal-dual Ajoutons au tableau les valeurs des contraintes du dual, sous la forme c i Ta i: 2 1 1 6 5 1 0 1 0 6 1 1 2 1 2 0 1 0 1 3 3 0 3 7 3 1 1 0 0 9
Programmation linéaire
Passage du premier tableau au deuxième Un sélectionne un pivot (ici en bleu) qui est au croisement des deux ariablesv incriminées (ici, le pivot avut 1 : ligne x 6, colonne x 1) On modi e le tableau ligne par ligne, en commençant par la ligne du pivot Pour la ligne x 4, on soustrait à l'ancienne ligne x
Sujet 4: Dualité --- la formule pour définir le dual dun
Probl eme primal et probl eme dual Chaque programme lin eaire peut ^etre consid er e comme unprobl eme primal Il y a un autre programme lin eaire associ e avec le primal, uniquement d e ni par celui-l a Ce programme lin eaire-ci est leprobl eme dual Ces deux programmes sont toujours symm etriques, dans les sens suivants (entre autres):
1) Formulation mathématique du problème
D’autre part, la fonction objectif du primal a la même valeur optimale que celle du dual, d’où la solution du problème primal : {Remarque: Les valeurs optimales des variables primales sont, au signe près, les valeurs des variables d’écart dans la dernière ligne de l’objectif du dernier tableau simplexe obtenu lors de la
Optimisation discrète, Séance 5 : Cours et Exercices
Itérations au moyen du Tableau : Fig 1 Primal (P) Dual (D) C x V Noter au passage que cet algorithme dual prend les critères en ordre inverse Le
COURS DE RECHERCHE OPERATIONNELLE
Le tableau 1 permet de présenter une meilleure notion de la large application de la RO avec une liste de ses applications utilisées dans les différentes organisations et les économies réalisées par ces dernières suite à l’adoption de ces méthodes
1 Programmation linéaire - pagesperso-orangefr
On obtient le tableau suivant : x 1 x 2 x 3 x 4 x 5 2 0 1 -1 0 3 x 3-1/3 1 0 1/3 0 6 x 2 2/3 0 0 1/3 1 11 x 5-5/3 0 0 2/3 0 12 Maintenant c’est x 1 qui entre et x 3 qui sort car : Min 3 2; 11 2=3 = 3 2 Un nouveau pivot autour du nombre 2 (à l’intersection de la ligne de x 3 et de la colonne de x 1) conduit au tableau suivant : x 1 x 2 x 3
Moca B2 - devpulsednet
, T Ü0 Î sommet du polygone 2) Calculer z 3) Garder la valeur max Calcul du nombre de solutions de base : Ë á > à á L : J E I Si n=2 et m=6 comme dans cet exemple il y a 10 solutions de base n=6, m=6 Î 924 solutions de base 4) Méthode algébrique du simplexe En utilisant le même exemple
[PDF] Passage en 1ere ES :S
[PDF] Passage en 1ère ST2S
[PDF] passage en 1ère STG
[PDF] passage en 2nd l'an prochain
[PDF] Passage en 2nd URGENT AIDER MOI
[PDF] passage en 3 éme
[PDF] passage en 3 éme
[PDF] Passage en 4 émé
[PDF] Passage en Es , Conseiller ou non
[PDF] Passage en L : révisions vacances
[PDF] Passage en pemière S
[PDF] Passage en polyphonie (musique)
[PDF] Passage en première
[PDF] Passage en première
IFT 2505
Programmation Lineaire
Fabian Bastin
DIROUniversite de Montreal
http://www.iro.umontreal.ca/ ~bastin/ift2505.phpAutomne 2012
Fabian BastinIFT2505
Exemple sur le simplexe dual et primal-dual
On considere le probleme
min x3x1+ 4x2+ 6x3+ 7x4+x5 s.a. 2x1x2+x3+ 6x45x56 x1+x2+ 2x3+x4+ 2x53
x1;x2;x3;x4;x50:
Le dual est
max61+ 32
21+231+24
1+ 226
61+2751+ 221
1;22 R:Fabian BastinIFT2505
Admissibilite du dual
Comme tous les coecients dans la fonction objectif sont strictement positifs, une solution realisable pour le dual est = (0;0): Nous savons de plus que l'admissibilite deest equivalente a l'existence d'une solution primale satisfaisant les conditions d'optimalite en termes de co^uts reduits, mais violant possiblement les contraintes de non-negativites.Essayons de demarrer le simplexe.
Fabian BastinIFT2505
Forme standard
min x3x1+ 4x2+ 6x3+ 7x4+x5 s.a. 2x1x2+x3+ 6x45x5x6= 6 x1+x2+ 2x3+x4+ 2x5x7= 3
x1;x2;x3;x4;x5;x6;x70:
Nous n'avons pas la forme canonique, mais nous pouvons facilement l'obtenir en multipliant les contraintes par -1 : min x3x1+ 4x2+ 6x3+ 7x4+x5 s.a.2x1+x2x36x4+ 5x5+x6=6 x1x22x3x42x5+x7=3 x1;x2;x3;x4;x5;x6;x70:Fabian BastinIFT2505
Forme standard
Probleme : la base associee ax6,x7n'est pas realisable vu que les termes non-nuls de la solution de base associee, a savoirx6=6, x7=3, violent les contraintes de non-negativite.
Le dual, lui, devient
max 61322123
124
1226
6127
51221
1;22 R:Fabian BastinIFT2505
Forme standard : dual
(1;2) = (0;0) reste realisable, et donc nous savons qu'il existe unxpour lequel les conditions d'optimalites sur les co^uts reduits sont satisfaits.On peut en deduire la motivation du simplexe duale :conserver les conditions d'optimalite et la realisabilite duale;
forcer la realisabilite primale (et partant de la, trouver une solution primale optimale).Fabian BastinIFT2505
Simplexe dual
Sous forme de tableau, cela donne
x62 116 5 1 06
x711212 0 13
3 4 6 7 1 0 0 0
On doit decider d'une variable qui va quitter la base, car de mauvais signe. Il n'y a pas de regle de selection ici; on se contente de selectionner une ligne avec un terme de droite strictement negatif.Supposons que nous choisissionsx7.
On calcule les rapports entre la derniere ligne et la ligne dex7, en se limitant aux entrees strictement negatives. On selectionne le minimum en valeur absolue de ces rapports.Fabian BastinIFT2505
Simplexe dual
De ce qui precede, le pivot est surx5:
x62 116 5 1 06
x71121-20 13
3 4 6 7 1 0 0 0
conduisant au nouveau tableau x 69232
6172
0 152 272
x 512
12 112
1 012 32
52
72
5132
0 012 32
Il faut a present faire sortirx6. Les rapports a considerer sont59 ,73 56
,1317 , et le minimum est59 . La variable entrante est doncx1.
Cela donne
x 111343
179
029
59
3 x 5013
13 49
119
29
0 0 83
53
3218
059
179
9Fabian BastinIFT2505
Simplexe dual
On en deduit la solution primale
x = (3;0;0;0;0) associee a la solution duale 59;179 Les valeurs optimales primales et duales sont egale a 9. On peut noter la correspondance entre les variables de base et les contraintes duales, comme seules les premiere et cinquieme contrainte du dual sont actives.
Fabian BastinIFT2505
Simplexe primal-dual
Il peut y avoir un grand nombre de rapports a calculer, ce qui peut ^etre co^uteux s'il y a un grand nombre de variables et de contraintes, et il n'est pas toujours aise d'avoir la forme canonique. On va essayer de limiter le nombre de variables qui peuvent ^etre candidates pour entrer dans la base, et introduire des variables articielles pour avoir une forme canonique initiale facile a denir.On part du primal :
min x3x1+ 4x2+ 6x3+ 7x4+x5 s.a. 2x1x2+x3+ 6x45x5x6= 6 x1+x2+ 2x3+x4+ 2x5x7= 3
x1;x2;x3;x4;x5;x6;x70:Fabian BastinIFT2505
Simplexe primal-dual
Probleme articiel :
min x3x1+ 4x2+ 6x3+ 7x4+x5 s.a. 2x1x2+x3+ 6x45x5x6+y1= 6 x1+x2+ 2x3+x4+ 2x5x7+y2= 3
x1;x2;x3;x4;x5;x6;x7;y1;y20:
Tableau :
21 1 651 0 1 0 6
1 1 2 1 2 01 0 1 3
3 0373 1 1 0 09:
On pourrait continuer la phase 1, mais on veut resoudre directement le probleme.Fabian BastinIFT2505
Simplexe primal-dual
Regardons du c^ote du dual du probleme initial :
max61+ 32
21+231+24
1+ 226
61+2751+ 221
10 201;22 R:
Une solution admissible du dual est, comme precedemment,1=2= 0.Fabian BastinIFT2505
Simplexe primal-dual
Ajoutons au tableau les valeurs des contraintes du dual, sous la formeciTai:21 1 651 0 1 0 6
1 1 2 1 2 01 0 1 3
3 037 3 1 1 0 09
3 4 6 7 1 0 0
SoitPl'ensemble deni comme
P def=fijTai=cig; i.e. l'ensemble des indices des contraintes duales actives. Ici,P=f6;7g:
Notons toutefois que dans le cas present, malgre le caractere actif de deux contraintes du dual, les variables primales associees sont hors-base. Ces contraintes pourront des lors devenir inactives plus tard.Fabian BastinIFT2505
Simplexe primal-dual
On va se tourner vers le dual pour decider de la variable primale a entrer dans la base, tout en maintenant l'admissibilite du dual (et donc implicitement de l'existence des conditions d'optimalite pour le primal).Dual restreint :
max 6u1+ 3u2 s.a.u10 u20 u 11 u 21u