Chapitre 4 Dualité
Dans cet exemple on observe que la valeur minimale du primal est égale à la dual à l'aide du tableau final du simplexe appliqué au problème primal.
IFT 2505 Programmation Linéaire
Exemple sur le simplexe dual et primal-dual. On consid`ere le probl`eme min x. 3x1 + 4x2 + 6x3 + 7x4 + x5 s.`a. 2x1 ? x2 + x3 + 6x4 ? 5x5 ? 6.
SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual
Il y a 3 contraintes dans le PPL donc 3 variables dans le modèle dual Excel dans son algorithme du simplexe utilise une construction du dual directe ...
Dualité en Programmation Linéaire Algorithmes primal et dual du
Algorithmes primal et dual du simplexe. Alain Faye. Option 3A Définition du dual d'un programme linéaire ... Exemple : écrire le dual de ce PL.
MÉTHODE DU SIMPLEXE DUAL (REVISITÉE) 1. Introduction La
Cette méthode s'applique en ayant déjà déterminer une solution de base réalisable pour le problème dual. C'est par exemple le cas si c ? 01 dans (2). La
IFT 2505 Programmation Linéaire
Dualité : relations `a la procédure du simplexe. Résoudre le primal par le simplexe donne la solution duale. Supposons que le programme Exemple : dual.
Algorithme primal-dual
Simplexe primal-dual. L'idée est de travailler simultanément Algorithme primal-dual : exemple ... du simplexe avec la solution du dual `a l'optimalité.
Sujet 4: Dualité --- la formule pour définir le dual dun programme
Mar 11 2010 “Le dual du dual
Sujet 5: Dualité --- faible et forte
Mar 24 2010 Si le primal est non-borné
Programmation linéaire (dualité et analyse de sensibilité) Dualité
Dualité : exemple Wyndor Glass Voici le modèle pour Dual Glass appelé modèle dual : ... du simplexe : ce sont les coefficients dans la ligne.
[PDF] méthode du simplexe dual (revisitée)
Cette méthode s'applique en ayant déjà déterminer une solution de base réalisable pour le problème dual C'est par exemple le cas si c ? 01 dans (2) La
[PDF] Exemple sur le simplexe dual et primal-dual
Exemple sur le simplexe dual et primal-dual On consid`ere le probl`eme min x 3x1 + 4x2 + 6x3 + 7x4 + x5 s `a 2x1 ? x2 + x3 + 6x4 ? 5x5 ? 6
[PDF] Chapitre 4 Dualité
Dans cet exemple on observe que la valeur minimale du primal est égale à la valeur maximale du dual Essayons de dualiser d'autres types de problèmes
[PDF] Dualité en Programmation Linéaire Algorithmes primal et dual du
Programmation linéaire et dualité – Définition du dual d'un programme linéaire – Théorème de dualité forte • Algorithmes primal et dual du simplexe
[PDF] OPTI1- Dualité en PL - Algorithme dual du simplexe - ENSIIE
2-Résoudre PL en appliquant l'algorithme dual du simplexe en partant de la base constituée par les 2 variables d'écart 3-Vérifier les calculs en faisant une
[PDF] SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual
Il y a 3 contraintes dans le PPL donc 3 variables dans le modèle dual Excel dans son algorithme du simplexe utilise une construction du dual directe
[PDF] Dualité --- la formule pour définir le dual dun programme linéaire
11 mar 2010 · “Le dual du dual c'est le primal ” Page 7 Dualité : introduction La formule Un exemple
[PDF] Sujet 5: Dualité --- faible et forte
L'utilisation du théor`eme dans la méthode du simplexe Rappel : un exemple maximisation et ¯y une solution réalisable de son dual
[PDF] Cours 8 Dualité
En effet à tout modèle de programmation linéaire primal correspond résolution comme l'algorithme du dual simplexe que nous traitons dans ce chapitre
[PDF] FSJES-AC RECHERCHE OPERATIONNELLE Semestre 6 Filière
La méthode du simplexe est un algorithme qui permet la recherche de la solution optimale Donc on présente la méthode à l'aide d'un exemple illustratif
Comment calculer la dualité ?
Le dual est max z = bty, Aty ? c, y ? 0. min z = ctx, (At)tx ? b, x ? 0. ?? min z = ctx, Ax ? b, x ? 0. Donc, le dual du dual est le primal.Comment faire le tableau de simplexe ?
Le tableau initial de la méthode du Simplexe est composé par tous les coefficients des variables de décision du problème original et les variables d'écart, excès et artificielles ajutées dans la deuxième étape (dans les colonnes, étant P0 0 le terme indépendant et le reste de variables Pi sont les mêmes que Xi), et lesC'est quoi un programme dual ?
Par définition, le programme dual est un programme linéaire consistant à minimiser une fonction économique dans un domaine défini par des contraintes sous forme d'inéquations de type inférieures ou égales (?).- La dualité, c'est la théorie qui nous permet de trouver avec confiance une solution optimale d'un programme linéaire. Si on a une solution réalisable qui n'est pas optimale, la dualité nous donne la capacité de savoir pourquoi cela n'est pas optimale.11 mar. 2010
IFT 2505
Programmation Lineaire
Fabian Bastin
DIROUniversite de Montreal
http://www.iro.umontreal.ca/ ~bastin/ift2505.phpAutomne 2012
Fabian BastinIFT2505
Dualite : relations a la procedure du simplexe
Resoudre le primal par le simplexe donne la solution duale.Supposons que le programme
min xcTx t.q.Ax=b x0: a la solution realisable de base optimalex= (xB;0), avec la base correspondante aB.Solution du dual
max Tb t.q.TAcT en termes deB?Fabian BastinIFT2505Relations a la procedure du simplexe
Supposons
A=B D;xB=B1b;rTD=cTDcTBB1D:
Sixest optimal,rTD0, et donc
cTBB1DcTD:
AvecT=cTBB1;
nous avonsTA=TBTD
cTBcTBB1D cTBcTD=cT:Fabian BastinIFT2505Relations a la procedure du simplexe
Des lors,
TAcT; i.e.est realisable pour le dual.De plus,
Tb=cTBB1b=cTBxB
et donc la valeur de la fonction objectif duale pour ceest egale a la valeur du probleme primal. Des lorsest optimal pour le dual. On retrouve le principal resultat du theoreme de dualite.Fabian BastinIFT2505
Relations a la procedure du simplexe
TheoremeSi le programme lineaire (sous forme standard) a une solution de base realisable optimale, correspondant a la baseB, le vecteurt.q.T=cTBB1est une solution optimale du programme dual correspondant. Les valeurs optimales des deux programmes sont egales.Fabian BastinIFT2505
Exemple
min xx14x23x3 t.q. 2x1+ 2x2+x34 x1+ 2x2+ 2x36
x10;x20;x30:
0 @2 2 1 1 0 41 2 2 0 1 6
143 0 0 01
A puis 0 @1 112 12 0 21 0 11 1 2
3 01 2 0 81
AFabian BastinIFT2505
Exemple
Ensuite,
0 @321 0 112
11 0 11 1 2
2 0 0 1 1 101
A On a B=2 1 2 2 B 1=112 1 1La solution optimale est
x1= 0;x2= 1;x3= 2:Fabian BastinIFT2505
Exemple : dual
max41+ 62
t.q. 21+2 121+ 22 4
1+ 22 3
10; 20:
La solution du dual s'obtient directement de la derniere ligne du tableau du simplexe, sous les colonnes ou appara^t l'identite dans le premier tableau (comme les co^uts initiaux associes sont nuls) :T=11:Fabian BastinIFT2505
Multiplicateurs du simplexe
A n'importe quelle iteration du simplexe, nous pouvons former le vecteurTsatisfaisantT=cTBB1:
Ce vecteur n'est pas une solution du dual a moins queBne soit une base optimale pour le primal. Mais il peut ^etre utilise a chaque iteration pour calculer les co^uts reduits, et il aura une interpretation economique. Pour cette raison, le vecteurT=cTBB1est souvent appele le vecteur des multiplicateurs du simplexe.Fabian BastinIFT2505
Interpretation economique
Comme d'ordinaire, denotons les colonnes deApara1;a2;:::;an, et pare1;e2;:::;emlesmvecteurs unites dansEm. Etant donne une baseB, consistant demcolonnes deA, n'importe quel autre vecteur peut ^etre construit comme combinaison lineaire de ces vecteurs de base. S'il y a un co^ut uniteciassocie avec chaque vecteur de baseai, le co^ut d'un vecteur construitya partir de la base peut ^etre calcule comme le combinaison lineaire correspondante desc0isassocies a la base. L'expression deya partir de la base est B 1y et le co^ut associe cTBB1y:Fabian BastinIFT2505
Interpretation economique
En particulier, le co^ut du vecteur uniteej, quand reconstruit a partir de la baseB, estj, lajecomposante deT=cTBB1:
En eet,
j=Tej=cTBB1ej: Des lors, les0jspeuvent ^etre interpretes comme les prix synthetiques des vecteurs unites. Comme y=mX j=1y jej; nous avons comme co^ut poury cTBB1y=mX
j=1cTBB1ejyj=mX
j=1 jyj=Ty:Fabian BastinIFT2505Interpretation economique : optimalite
L'optimalite du primal correspond a la situation ou chaque vecteur a1;a2;:::;an, est "moins cher" quand construit a partir de la base
que quand achete directement a son propre prix.Dans ce cas, nous avons
Taici;i= 1;2;:::;n;
ou de maniere equivalenteTAcT:Fabian BastinIFT2505
Sensibilite
Continuation de l'interpretation des variables duales comme prix.Considerons le probleme standard,
min xcTx t.q.Ax=b x0 avec la base optimaleBet la solution correspondante (xB;0), ou xB=B1b. Une solution correspondante du dual est
T=cTBB1:
Sous l'hypothese de non-degenerescence, de petits changements dansbne conduiront pas a un changement de base optimale.Fabian BastinIFT2505Sensibilite
Considerons un petit changement b. Comme la base optimale n'a pas changee, la nouvelle solution optimale est x= (xB+ xB;0); ou xB=B1b: Le changement correspondant pour la fonction objectif est z=cTBxB=Tb: Des lors,mesure la sensibilite de la fonction objectif a un petit changement dans le terme de droite des contraintes d'egalite : un changement debab+ bconduit a un changement de la fonction objectif deTb,Fabian BastinIFT2505Sensibilite et multiplicateurs du simplexe
Puisquejest le prix du vecteur uniteejquand exprime a partir de la baseB, il mesure directement le changement dans le co^ut a partir d'un changement dans lajecomposante du vecteurb. Cela s'observe aussi depuis la relation precedente z=cTBxB=Tb: Des lors,jpeut ^etre considere comme leprix marginaldebj, puisque modierbjenbj+ bjconduit a un changement de la valeur optimale dejbj.Fabian BastinIFT2505 Ecarts de complementariteTheoreme : ecarts de complementarite { forme asymetrique Soitxetdes solutions pour les programmes primal et dual, le primal etant exprime sous forme standard. Une condition necessaire et susante pour quexetsoient tous deux solutions optimales est que pour touti1x i>0)Tai=ci2x i= 0(TaiTb=cTx;
et par le corollaire du theoreme de dualite faible,etxsont solutions optimales de leur probleme respectif. De maniere reciproque, si les solutions sont optimales, par le theoreme de dualite forte,Tb=cTx;
et donc (TAcT)x= 0: Commex0; TAc, les conditions tiennent.Fabian BastinIFT2505 Ecarts de complementariteTheoreme : ecarts de complementarite { forme symetrique Soitxetdes solutions pour les programmes primal et dual, le primal etant exprime avec les contraintes lineaires sous forme Axb. Une condition necessaire et susante pour quexet soient tous deux solutions optimales est que pour touti1x i>0)Tai=ci2x i= 0(TaiSimilaire au theoreme precedent.
Fabian BastinIFT2505
Methode du simplexe dual
Souvent, on peut obtenir une solution de base du probleme lineaire non realise, mais associee a des multiplicateurs du simplexe qui sont realisables pour le probleme dual. Dans le tableau du simplexe, cette situation revient a ne pas avoir d'elements negatifs dans la derniere ligne, tout en ayant une solution de base non realisable. Ceci arrive par exemple si on resoud un probleme, puis on veut en resoudre un nouveau apres avoir changerb. On va travailler sur le probleme dual en partant du tableau primal.Fabian BastinIFT2505
Methode du simplexe dual : principes
En termes du primal :
maintenir l'optimalite de la derniere ligne; aller vers la realisabilite.En termes du primal :maintenir la realisabilite;
aller vers l'optimalite.Fabian BastinIFT2505
Methode du simplexe dual
On considere le probleme
min xcTx t.q.Ax=b x0:Supposons qu'une baseBest connue, et soit
T=cTBB1:
On supposerealisable pour le dual.
La solutionxb=B1best dit dual-realisable.
SixB0, cette solution est aussi primal-realisable, et est par consequent optimale.Fabian BastinIFT2505
Methode du simplexe dual
Commeest realisable pour le dual,
Tajcj;j= 1;2;:::;n:
Si, comme d'ordinaire, nous supposons queBest constitue desm premieres colonnes deA, i.e.B=a1a2:::am;
nous avonsTaj=cTBB1aj=cTBej=cj;j= 1;2;:::;m:
ouejest lejevecteur unite. En appliquant l'hypothese de non-degenerescence pour le dual, nous avons aussiTaj Methode du simplexe dual
Un cycle du simplexe, applique au dual, reviendra a echanger deux composantes de, de maniere a ce qu'une inegalite stricte devienne une egalite, et vice-versa, tout en augmentant la valeur du dual. Lesmegalites dans la nouvelle solution determineront une nouvelle base. Soituilaieligne deB1, et
T=Tut:
Nous avons (avec0)
Taj=Tajuiaj:Fabian BastinIFT2505
Methode du simplexe dual
Rappelons la notation prealablement introduite
z j=cTByj: Des lors,
Taj=cTBB1aj=zj:
Comme u iaj=yij; nous avons Taj=cj;j= 1;2;:::;m;i6=j;
Tai=ci;
Taj=zjyij;j=m+ 1;m+ 2;:::;n:Fabian BastinIFT2505
Methode du simplexe dual
De plus,
Tb=Tbuib=TbxBi:
Comme Taj nous cherchons a augmenter le terme de gauche, ce qui revient a considerer les situations ouyij<0 dans Taj=zjyij;j=m+ 1;m+ 2;:::;n:
Nous cherchons a ramener la valeur acj, sans la depasser (sinon on violerait les conditions de realisabilite du dual), aussi nous prenons 0= minj
zjcjy ijt.q.yij<0 Fabian BastinIFT2505
Algorithme du simplexe dual
Etape 1Etant donnee une solution de base dual-realisablexB, si x B0, la solution est optimale : arr^et. Sinon, selectionner un indiceitel quexBi<0. Etape 2Si tous lesyij0,j= 1;2;:::;n, le dual n'a pas de maximum. Sinon, calculer 0= minj
zjcjy ijt.q.yij<0 Soitkl'indice correspondant (unique si l'hypothese de non-degenerescence s'applique). Etape 3Former une nouvelle baseBen remplacantaiparak. En utilisant cette base, determiner la solution de base dual-realisable x Bcorrespondante.Fabian BastinIFT2505
Simplexe dual : exemple
min x3x1+ 4x2+ 5x3 soumis ax1+ 2x2+ 3x35 2x1+ 2x2+x36
x 1;x2;x30:
En introduisant des variables de surplus, nous obtenons min x3x1+ 4x2+ 5x3 soumis ax1+ 2x2+ 3x3x4= 5 2x1+ 2x2+x3x5= 6
x 1;x2;x3;x4;x50:Fabian BastinIFT2505
Simplexe dual : exemple
Si nous changeons le signe des inegalites, nous obtenons min x3x1+ 4x2+ 5x3 soumis ax12x23x3+x4=5 2x12x2x3+x5=6
x 1;x2;x3;x4;x50:
conduisnat au tableau x 4123 1 05
x 5221 0 16
3 4 5 0 0 0
La base (a4;a5) est dual-realisable comme tous les co^uts reduits sont non-negatifs. Fabian BastinIFT2505
Simplexe dual : exemple
Nous devons selectionner une composante dexBqui sont strictement negative pour la retirer de l'ensemble des variables de base. Prenons par exemplex5=6. Nous devons alors calculer les rapports
z jcjy 2j ou, en d'autres termes, les rapports entre l'oppose des co^uts reduits et les elements de la seconde ligne. Le plus petit rapport (strictement) positif est obtenu avec l'elementy12: x 4123 1 05
x 5-221 0 16
3 4 5 0 0 0
Fabian BastinIFT2505
Simplexe dual : exemple
Apres le pivot, nous avons
x 40-1
52
112
2 x 11 012
012 3 0 1 72
032
9 puis x 20 152
112
2 x 11 02 11 1
0 0 1 1 111
La solution (1;2;0) est optimale.Fabian BastinIFT2505 Simplexe primal-dual
L'idee est de travailler simultanement sur le primal et le dual. Principales idees :trouver une solution realisable pour le dual; l'ameliorer a chaque etape en optimisant un probleme primal restreint associe;essayer de statisfaire les conditions d'ecart de complementarite. Il s'agit de la variante du simplexe la plus ecace pour les problemes de ots dans les reseaux. Fabian BastinIFT2505
Simplexe primal-dual
Considerons a nouveau le primal
min xcTx t.q.Ax=b x0: et son dual max Tb t.q.TAcT Etant donne une solution realisablepour le dual, denissons P=fijTai=cig:
Vu queest suppose realisable, cela implique
Tai Simplexe primal-dual
Correspondant aetP, nous denissons le problemeprimal restreint associe min y1Ty t.q.Ax+y=b x0;xi= 0 pouri=2P y0 ou1designe the vecteur (1;1;:::;1). Le dual associe est appeledual restreint associe
max uuTb t.q.uTai0;i2P u1:Fabian BastinIFT2505 Theoreme d'optimalite primale-duale
Supposons queest realisable pour le dual et que(x;y)est realisable pour le primal restreint associe, avecy= 0(de sorte que (x;y)est une solution optimal). Alors,xetsont optimaux pour les programmes primal et dual originaux respectifs.Demonstration. xest clairement realisable pour le primal :Ax=b. Nous avons aussi, par denition deP,Tai=ci;sixi6= 0, de sorte que c Tx=TAx:
En combinant ces deux observations, nous avons
c Tx=Tb;
impliquant l'optimalite dexet.Fabian BastinIFT2505 Algorithme primal-dual
Etape 1Etant donne une solution realisable0pour le dual, determiner le primal restreint associe. Etape 2Optimiser le primal restreint associe. Si la valeur optimale de ce primal restreint associe (impliquanty= 0), la solution correspondante est optimale pour le primal original, en vertu du theoreme d'optimalite primale-duale; arr^et. Etape 3Si la valeur optimale du primal restreint associe est strictement positive (i.e. ify6= 0), la solution optimale de ce primal restreint associe n'est pas realisable pour le primal, et on cherche a ameliorer la solution realisable du dual avant de determiner un nouveau primal restreint associe. Fabian BastinIFT2505
Algorithme primal-dual
Etape 3 (suite)Obtenir du tableau du simplexe du primal restreint la solutionu0du dual restreint associe. S'il n'y a pas dej pour lequeluT0aj>0, le primal n'a pas de solution realisable; arr^et. Sinon, construire le nouveau vecteur dual realisable =0+0u0; ou 0= minj
cjT0aju T0aj uT0aj>0 Retour a l'etape 1, en utilisant ce.Fabian BastinIFT2505 Algorithme primal-dual : preuve
Dans l'etape 3, il est indique queuT0aj0 pour toutjimplique que le primal n'a pas de solution realisable. SiuT0aj0 pour toutj, le vecteur
=0+u0 est realisable pour le probleme dual pour toute valeur positive de, comme TA=T0A+uT0AcT:
De plus, comme
u T0b=1Ty>0;
nous voyons que la quantite Tb=T0b+uT0b;
est non bornee, lorsque nous augmentons. Du theoreme de dualite forte, le primal n'est pas realisable. Fabian BastinIFT2505
Algorithme primal-dual : preuve
Supposons a present que pour au moins unj,uT0aj>0. A nouveau, denissons
=0+u0 Par construction,
u T0ai0;8i2P:
Pour unpositif assez petit,est realisable pour le dual, et nous pouvons augmenterjusqu'a transformer une des inegalites Taj en egalite. Ceci determine0et un indicekcorrespondant.Fabian BastinIFT2505quotesdbs_dbs35.pdfusesText_40
Methode du simplexe dual
Un cycle du simplexe, applique au dual, reviendra a echanger deux composantes de, de maniere a ce qu'une inegalite stricte devienne une egalite, et vice-versa, tout en augmentant la valeur du dual. Lesmegalites dans la nouvelle solution determineront une nouvelle base.Soituilaieligne deB1, et
T=Tut:
Nous avons (avec0)
Taj=Tajuiaj:Fabian BastinIFT2505
Methode du simplexe dual
Rappelons la notation prealablement introduite
z j=cTByj:Des lors,
Taj=cTBB1aj=zj:
Comme u iaj=yij; nous avonsTaj=cj;j= 1;2;:::;m;i6=j;
Tai=ci;
Taj=zjyij;j=m+ 1;m+ 2;:::;n:Fabian BastinIFT2505
Methode du simplexe dual
De plus,
Tb=Tbuib=TbxBi:
CommeTaj nous cherchons a augmenter le terme de gauche, ce qui revient a considerer les situations ouyij<0 dans Taj=zjyij;j=m+ 1;m+ 2;:::;n:
Nous cherchons a ramener la valeur acj, sans la depasser (sinon on violerait les conditions de realisabilite du dual), aussi nous prenons 0= minj
zjcjy ijt.q.yij<0 Fabian BastinIFT2505
Algorithme du simplexe dual
Etape 1Etant donnee une solution de base dual-realisablexB, si x B0, la solution est optimale : arr^et. Sinon, selectionner un indiceitel quexBi<0. Etape 2Si tous lesyij0,j= 1;2;:::;n, le dual n'a pas de maximum. Sinon, calculer 0= minj
zjcjy ijt.q.yij<0 Soitkl'indice correspondant (unique si l'hypothese de non-degenerescence s'applique). Etape 3Former une nouvelle baseBen remplacantaiparak. En utilisant cette base, determiner la solution de base dual-realisable x Bcorrespondante.Fabian BastinIFT2505
Simplexe dual : exemple
min x3x1+ 4x2+ 5x3 soumis ax1+ 2x2+ 3x35 2x1+ 2x2+x36
x 1;x2;x30:
En introduisant des variables de surplus, nous obtenons min x3x1+ 4x2+ 5x3 soumis ax1+ 2x2+ 3x3x4= 5 2x1+ 2x2+x3x5= 6
x 1;x2;x3;x4;x50:Fabian BastinIFT2505
Simplexe dual : exemple
Si nous changeons le signe des inegalites, nous obtenons min x3x1+ 4x2+ 5x3 soumis ax12x23x3+x4=5 2x12x2x3+x5=6
x 1;x2;x3;x4;x50:
conduisnat au tableau x 4123 1 05
x 5221 0 16
3 4 5 0 0 0
La base (a4;a5) est dual-realisable comme tous les co^uts reduits sont non-negatifs. Fabian BastinIFT2505
Simplexe dual : exemple
Nous devons selectionner une composante dexBqui sont strictement negative pour la retirer de l'ensemble des variables de base. Prenons par exemplex5=6. Nous devons alors calculer les rapports
z jcjy 2j ou, en d'autres termes, les rapports entre l'oppose des co^uts reduits et les elements de la seconde ligne. Le plus petit rapport (strictement) positif est obtenu avec l'elementy12: x 4123 1 05
x 5-221 0 16
3 4 5 0 0 0
Fabian BastinIFT2505
Simplexe dual : exemple
Apres le pivot, nous avons
x 40-1
52
112
2 x 11 012
012 3 0 1 72
032
9 puis x 20 152
112
2 x 11 02 11 1
0 0 1 1 111
La solution (1;2;0) est optimale.Fabian BastinIFT2505 Simplexe primal-dual
L'idee est de travailler simultanement sur le primal et le dual. Principales idees :trouver une solution realisable pour le dual; l'ameliorer a chaque etape en optimisant un probleme primal restreint associe;essayer de statisfaire les conditions d'ecart de complementarite. Il s'agit de la variante du simplexe la plus ecace pour les problemes de ots dans les reseaux. Fabian BastinIFT2505
Simplexe primal-dual
Considerons a nouveau le primal
min xcTx t.q.Ax=b x0: et son dual max Tb t.q.TAcT Etant donne une solution realisablepour le dual, denissons P=fijTai=cig:
Vu queest suppose realisable, cela implique
Tai Simplexe primal-dual
Correspondant aetP, nous denissons le problemeprimal restreint associe min y1Ty t.q.Ax+y=b x0;xi= 0 pouri=2P y0 ou1designe the vecteur (1;1;:::;1). Le dual associe est appeledual restreint associe
max uuTb t.q.uTai0;i2P u1:Fabian BastinIFT2505 Theoreme d'optimalite primale-duale
Supposons queest realisable pour le dual et que(x;y)est realisable pour le primal restreint associe, avecy= 0(de sorte que (x;y)est une solution optimal). Alors,xetsont optimaux pour les programmes primal et dual originaux respectifs.Demonstration. xest clairement realisable pour le primal :Ax=b. Nous avons aussi, par denition deP,Tai=ci;sixi6= 0, de sorte que c Tx=TAx:
En combinant ces deux observations, nous avons
c Tx=Tb;
impliquant l'optimalite dexet.Fabian BastinIFT2505 Algorithme primal-dual
Etape 1Etant donne une solution realisable0pour le dual, determiner le primal restreint associe. Etape 2Optimiser le primal restreint associe. Si la valeur optimale de ce primal restreint associe (impliquanty= 0), la solution correspondante est optimale pour le primal original, en vertu du theoreme d'optimalite primale-duale; arr^et. Etape 3Si la valeur optimale du primal restreint associe est strictement positive (i.e. ify6= 0), la solution optimale de ce primal restreint associe n'est pas realisable pour le primal, et on cherche a ameliorer la solution realisable du dual avant de determiner un nouveau primal restreint associe. Fabian BastinIFT2505
Algorithme primal-dual
Etape 3 (suite)Obtenir du tableau du simplexe du primal restreint la solutionu0du dual restreint associe. S'il n'y a pas dej pour lequeluT0aj>0, le primal n'a pas de solution realisable; arr^et. Sinon, construire le nouveau vecteur dual realisable =0+0u0; ou 0= minj
cjT0aju T0aj uT0aj>0 Retour a l'etape 1, en utilisant ce.Fabian BastinIFT2505 Algorithme primal-dual : preuve
Dans l'etape 3, il est indique queuT0aj0 pour toutjimplique que le primal n'a pas de solution realisable. SiuT0aj0 pour toutj, le vecteur
=0+u0 est realisable pour le probleme dual pour toute valeur positive de, comme TA=T0A+uT0AcT:
De plus, comme
u T0b=1Ty>0;
nous voyons que la quantite Tb=T0b+uT0b;
est non bornee, lorsque nous augmentons. Du theoreme de dualite forte, le primal n'est pas realisable. Fabian BastinIFT2505
Algorithme primal-dual : preuve
Supposons a present que pour au moins unj,uT0aj>0. A nouveau, denissons
=0+u0 Par construction,
u T0ai0;8i2P:
Pour unpositif assez petit,est realisable pour le dual, et nous pouvons augmenterjusqu'a transformer une des inegalites Taj en egalite. Ceci determine0et un indicekcorrespondant.Fabian BastinIFT2505quotesdbs_dbs35.pdfusesText_40
Taj=zjyij;j=m+ 1;m+ 2;:::;n:
Nous cherchons a ramener la valeur acj, sans la depasser (sinon on violerait les conditions de realisabilite du dual), aussi nous prenons0= minj
zjcjy ijt.q.yij<0Fabian BastinIFT2505
Algorithme du simplexe dual
Etape 1Etant donnee une solution de base dual-realisablexB, si x B0, la solution est optimale : arr^et. Sinon, selectionner un indiceitel quexBi<0. Etape 2Si tous lesyij0,j= 1;2;:::;n, le dual n'a pas de maximum. Sinon, calculer0= minj
zjcjy ijt.q.yij<0 Soitkl'indice correspondant (unique si l'hypothese de non-degenerescence s'applique). Etape 3Former une nouvelle baseBen remplacantaiparak. En utilisant cette base, determiner la solution de base dual-realisable xBcorrespondante.Fabian BastinIFT2505
Simplexe dual : exemple
min x3x1+ 4x2+ 5x3 soumis ax1+ 2x2+ 3x352x1+ 2x2+x36
x1;x2;x30:
En introduisant des variables de surplus, nous obtenons min x3x1+ 4x2+ 5x3 soumis ax1+ 2x2+ 3x3x4= 52x1+ 2x2+x3x5= 6
x1;x2;x3;x4;x50:Fabian BastinIFT2505
Simplexe dual : exemple
Si nous changeons le signe des inegalites, nous obtenons min x3x1+ 4x2+ 5x3 soumis ax12x23x3+x4=52x12x2x3+x5=6
x1;x2;x3;x4;x50:
conduisnat au tableau x4123 1 05
x5221 0 16
3 4 5 0 0 0
La base (a4;a5) est dual-realisable comme tous les co^uts reduits sont non-negatifs.Fabian BastinIFT2505
Simplexe dual : exemple
Nous devons selectionner une composante dexBqui sont strictement negative pour la retirer de l'ensemble des variables de base. Prenons par exemplex5=6.Nous devons alors calculer les rapports
z jcjy 2j ou, en d'autres termes, les rapports entre l'oppose des co^uts reduits et les elements de la seconde ligne. Le plus petit rapport (strictement) positif est obtenu avec l'elementy12: x4123 1 05
x5-221 0 16
3 4 5 0 0 0
Fabian BastinIFT2505
Simplexe dual : exemple
Apres le pivot, nous avons
x 40-152
112
2 x
11 012
012 3 0 1 72032
9 puis x
20 152
1122 x
11 02 11 1
0 0 1 1 111
La solution (1;2;0) est optimale.Fabian BastinIFT2505Simplexe primal-dual
L'idee est de travailler simultanement sur le primal et le dual. Principales idees :trouver une solution realisable pour le dual; l'ameliorer a chaque etape en optimisant un probleme primal restreint associe;essayer de statisfaire les conditions d'ecart de complementarite. Il s'agit de la variante du simplexe la plus ecace pour les problemes de ots dans les reseaux.Fabian BastinIFT2505
Simplexe primal-dual
Considerons a nouveau le primal
min xcTx t.q.Ax=b x0: et son dual max Tb t.q.TAcT Etant donne une solution realisablepour le dual, denissonsP=fijTai=cig:
Vu queest suppose realisable, cela implique
Tai Simplexe primal-dual
Correspondant aetP, nous denissons le problemeprimal restreint associe min y1Ty t.q.Ax+y=b x0;xi= 0 pouri=2P y0 ou1designe the vecteur (1;1;:::;1). Le dual associe est appeledual restreint associe
max uuTb t.q.uTai0;i2P u1:Fabian BastinIFT2505 Theoreme d'optimalite primale-duale
Supposons queest realisable pour le dual et que(x;y)est realisable pour le primal restreint associe, avecy= 0(de sorte que (x;y)est une solution optimal). Alors,xetsont optimaux pour les programmes primal et dual originaux respectifs.Demonstration. xest clairement realisable pour le primal :Ax=b. Nous avons aussi, par denition deP,Tai=ci;sixi6= 0, de sorte que c Tx=TAx:
En combinant ces deux observations, nous avons
c Tx=Tb;
impliquant l'optimalite dexet.Fabian BastinIFT2505 Algorithme primal-dual
Etape 1Etant donne une solution realisable0pour le dual, determiner le primal restreint associe. Etape 2Optimiser le primal restreint associe. Si la valeur optimale de ce primal restreint associe (impliquanty= 0), la solution correspondante est optimale pour le primal original, en vertu du theoreme d'optimalite primale-duale; arr^et. Etape 3Si la valeur optimale du primal restreint associe est strictement positive (i.e. ify6= 0), la solution optimale de ce primal restreint associe n'est pas realisable pour le primal, et on cherche a ameliorer la solution realisable du dual avant de determiner un nouveau primal restreint associe. Fabian BastinIFT2505
Algorithme primal-dual
Etape 3 (suite)Obtenir du tableau du simplexe du primal restreint la solutionu0du dual restreint associe. S'il n'y a pas dej pour lequeluT0aj>0, le primal n'a pas de solution realisable; arr^et. Sinon, construire le nouveau vecteur dual realisable =0+0u0; ou 0= minj
cjT0aju T0aj uT0aj>0 Retour a l'etape 1, en utilisant ce.Fabian BastinIFT2505 Algorithme primal-dual : preuve
Dans l'etape 3, il est indique queuT0aj0 pour toutjimplique que le primal n'a pas de solution realisable. SiuT0aj0 pour toutj, le vecteur
=0+u0 est realisable pour le probleme dual pour toute valeur positive de, comme TA=T0A+uT0AcT:
De plus, comme
u T0b=1Ty>0;
nous voyons que la quantite Tb=T0b+uT0b;
est non bornee, lorsque nous augmentons. Du theoreme de dualite forte, le primal n'est pas realisable. Fabian BastinIFT2505
Algorithme primal-dual : preuve
Supposons a present que pour au moins unj,uT0aj>0. A nouveau, denissons
=0+u0 Par construction,
u T0ai0;8i2P:
Pour unpositif assez petit,est realisable pour le dual, et nous pouvons augmenterjusqu'a transformer une des inegalites Taj en egalite. Ceci determine0et un indicekcorrespondant.Fabian BastinIFT2505quotesdbs_dbs35.pdfusesText_40
Simplexe primal-dual
Correspondant aetP, nous denissons le problemeprimal restreint associe min y1Ty t.q.Ax+y=b x0;xi= 0 pouri=2P y0 ou1designe the vecteur (1;1;:::;1).Le dual associe est appeledual restreint associe
max uuTb t.q.uTai0;i2P u1:Fabian BastinIFT2505Theoreme d'optimalite primale-duale
Supposons queest realisable pour le dual et que(x;y)est realisable pour le primal restreint associe, avecy= 0(de sorte que (x;y)est une solution optimal). Alors,xetsont optimaux pour les programmes primal et dual originaux respectifs.Demonstration. xest clairement realisable pour le primal :Ax=b. Nous avons aussi, par denition deP,Tai=ci;sixi6= 0, de sorte que cTx=TAx:
En combinant ces deux observations, nous avons
cTx=Tb;
impliquant l'optimalite dexet.Fabian BastinIFT2505Algorithme primal-dual
Etape 1Etant donne une solution realisable0pour le dual, determiner le primal restreint associe. Etape 2Optimiser le primal restreint associe. Si la valeur optimale de ce primal restreint associe (impliquanty= 0), la solution correspondante est optimale pour le primal original, en vertu du theoreme d'optimalite primale-duale; arr^et. Etape 3Si la valeur optimale du primal restreint associe est strictement positive (i.e. ify6= 0), la solution optimale de ce primal restreint associe n'est pas realisable pour le primal, et on cherche a ameliorer la solution realisable du dual avant de determiner un nouveau primal restreint associe.Fabian BastinIFT2505
Algorithme primal-dual
Etape 3 (suite)Obtenir du tableau du simplexe du primal restreint la solutionu0du dual restreint associe. S'il n'y a pas dej pour lequeluT0aj>0, le primal n'a pas de solution realisable; arr^et. Sinon, construire le nouveau vecteur dual realisable =0+0u0; ou0= minj
cjT0aju T0aj uT0aj>0 Retour a l'etape 1, en utilisant ce.Fabian BastinIFT2505Algorithme primal-dual : preuve
Dans l'etape 3, il est indique queuT0aj0 pour toutjimplique que le primal n'a pas de solution realisable.SiuT0aj0 pour toutj, le vecteur
=0+u0 est realisable pour le probleme dual pour toute valeur positive de, commeTA=T0A+uT0AcT:
De plus, comme
uT0b=1Ty>0;
nous voyons que la quantiteTb=T0b+uT0b;
est non bornee, lorsque nous augmentons. Du theoreme de dualite forte, le primal n'est pas realisable.Fabian BastinIFT2505
Algorithme primal-dual : preuve
Supposons a present que pour au moins unj,uT0aj>0.A nouveau, denissons
=0+u0Par construction,
uT0ai0;8i2P:
Pour unpositif assez petit,est realisable pour le dual, et nous pouvons augmenterjusqu'a transformer une des inegalitesTaj en egalite. Ceci determine0et un indicekcorrespondant.Fabian BastinIFT2505quotesdbs_dbs35.pdfusesText_40
[PDF] programme dual et primal
[PDF] dualité onde particule formule
[PDF] dualité synonyme
[PDF] dualité exemple
[PDF] dualité définition
[PDF] dualité adjectif
[PDF] dualité de l'homme définition
[PDF] dualité humaine
[PDF] dualité entre deux personnes
[PDF] dualité définition philosophique
[PDF] duane hanson oeuvre
[PDF] duane hanson biography
[PDF] duane hanson supermarket lady
[PDF] tourists ii
[PDF] duane hanson tourists
[PDF] dualité onde particule formule
[PDF] dualité synonyme
[PDF] dualité exemple
[PDF] dualité définition
[PDF] dualité adjectif
[PDF] dualité de l'homme définition
[PDF] dualité humaine
[PDF] dualité entre deux personnes
[PDF] dualité définition philosophique
[PDF] duane hanson oeuvre
[PDF] duane hanson biography
[PDF] duane hanson supermarket lady
[PDF] tourists ii
[PDF] duane hanson tourists
