Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
Dualit´ faible
e
Ecarts compl´mentaires
e
Sujet 5: Dualit´ — faible et forte
e
MHT 423 :
Mod`les et m´thodes d’optimisation
e
e
Andrew J
...
1
Dualit´ faible
e
2
Dualit´ forte : Ecarts compl´mentaires
e
e
Th´or`me des ´carts compl´mentaires
e e
e
e
L’utilisation du th´or`me dans la m´thode du simplexe
e e
e
Dualit´ faible
e
Ecarts compl´mentaires
e
1
Dualit´ faible
e
2
Dualit´ forte : Ecarts compl´mentaires
e
e
Th´or`me des ´carts compl´mentaires
e e
e
e
L’utilisation du th´or`me dans la m´thode du simplexe
e e
e
Dualit´ faible
e
Ecarts compl´mentaires
e
Rappel : un exemple
max
s
...
9x1 + 2
...
Une solution r´alisable pour le dual est y = (0, 1
...
mais cela
e
n’est pas optimale
...
4, 1
...
Cette
solution a la mˆme valeur objective que la solution optimale
e
primale
...
¯
e
Alors c T x ≤ b T y est toujours vrai
...
= (¯ T A)¯
y
x
= y T (A¯)
¯
x
≤ yT b
¯
≤ bT y
...
Dualit´ faible
e
Ecarts compl´mentaires
e
Une cons´quence : probl`mes non-born´s et irr´alisables
e
e
e
e
Si le primal est non-born´, alors le dual est irr´alisable
...
`
a
x1 + x2
x1 − 2x2 ≤ 1
x1 , x2 ≥ 0
Dualit´ faible
e
Ecarts compl´mentaires
e
Une cons´quence : probl`mes non-born´s et irr´alisables
e
e
e
e
Evidemment, on peut aussi dire le suivant : Si le dual est
non-born´, alors le primal est irr´alisable
...
`
a
x1 + x2
−x1 ≤ −2
−x2 ≤ −1
x1 + 2x2 ≤ 3
x1 , x2 ≥ 0
Dualit´ faible
e
Ecarts compl´mentaires
e
Une autre cons´quence : probl`mes r´alisables
e
e
e
Si tous les deux probl`mes ont une solution r´alisable, alors chaque
e
e
probl`me a (au moins) une solution optimale
...
e
Exemple :
max
s
...
2
Le primal est non-born´ est le dual est irr´alisable
...
e
e
4
Tous les deux probl`mes sont irr´alisables
...
Pour prouver qu’il existe seulement ces quatre possibilit´s, ainsi
e
que la d´claration pr´c´dente concernante le premier cas est vraie,
e
e e
il faut consid´rer la dualit´ forte et le th´or`me des ´carts
e
e
e e
e
compl´mentaires
...
La solution
¯
e
e
x est optimale si et seulement si il existe une solution r´alisable y
¯
e
¯
pour le probl`me dual telle que
e
(bi −
(cj −
n
¯ y
j=1 aij xj )¯i
m
¯ x
i=1 aij yi )¯j
= 0, i = 1,
...
, n
Dualit´ faible
e
Ecarts compl´mentaires
e
Corollaire
C’est ´vident que si une telle solution duale y existe, y est
e
¯
¯
forc´ment une solution optimale
...
Alors
e
(bi −
(cj −
n
¯ y
j=1 aij xj )¯i
m
¯ x
i=1 aij yi )¯j
= 0, i = 1,
...
, n
Dualit´ faible
e
Ecarts compl´mentaires
e
Corollaire : dualit´ forte
e
En consid´rant la preuve de la dualit´ faible, on voit l’in´galit´
e
e
e
e
c T x ≤ (AT y )T x =⇒ (c − AT y )T x ≤ 0
...
e
Corollaire : dualit´ forte
e
Soit x une solution optimale pour le probl`me primal, et y une
¯
e
¯
solution optimale pour le probl`me dual
...
e
Dualit´ faible
e
Ecarts compl´mentaires
e
Corollaire : les quatre possibilit´s
...
2
Le primal est non-born´ est le dual est irr´alisable
...
e
e
4
Tous les deux probl`mes sont irr´alisables
...
e
Mais cette solution ne sera pas r´alisable pour le probl`me dual
...
e ee
e
Dualit´ faible
e
Exemple 1 : Monet dans deux dimensions
Solution optimale: (1000, 2000)
Solution non-optimale: (0, 2500)
Ecarts compl´mentaires
e
Dualit´ faible
e
Ecarts compl´mentaires
e
Exemple 2 : Di´t´tique
ee
Solution optimale:
2 49 2 5
(6 , 9 , 6 , 5 )
3 99 3 99
Solution non-optimale:
(10, 9
39
6
, 0, 6 )
99
99
Dualit´ faible
e
Ecarts compl´mentaires
e
A souvenir
Th´orem D’´carts Compl´mentaires
e
e
e
A quoi sert le probl`me dual :
e
Son importance pour d´finir les crit`res d’optimalit´ ; cette
e
e
e
importance d´pend sur le Th´orem D’´carts Compl´mentaires
e
e
e
e
son utilisation dans l’algorithme de simplexe