[PDF] IFT 2505 Programmation Linéaire





Previous PDF Next PDF



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 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 les

  • C'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

DIRO

Universite de Montreal

http://www.iro.umontreal.ca/ ~bastin/ift2505.php

Automne 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 x

1+x2+ 2x3+x4+ 2x53

x

1;x2;x3;x4;x50:

Le dual est

max

61+ 32

21+23
1+24

1+ 226

61+27

51+ 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 x

1+x2+ 2x3+x4+ 2x5x7= 3

x

1;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 x

1;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, x

7=3, violent les contraintes de non-negativite.

Le dual, lui, devient

max 6132
2123
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

x

62 116 5 1 06

x

711212 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:

x

62 116 5 1 06

x

71121-20 13

3 4 6 7 1 0 0 0

conduisant au nouveau tableau x 692
32
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 1113
43
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 x

1+x2+ 2x3+x4+ 2x5x7= 3

x

1;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 x

1+x2+ 2x3+x4+ 2x5x7+y2= 3

x

1;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 :

max

61+ 32

21+23
1+24

1+ 226

61+27

51+ 221

10 20

1;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 21
quotesdbs_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