Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours 6 : dualit´ e Christophe Gonzales LIP6 – Universit´ e Paris 6, France En

Cours 6 : dualit´ e Christophe Gonzales LIP6 – Universit´ e Paris 6, France En route vers la dualit´ e (1/5) max 4x1 + x2 + 5x3 + 3x4 s.c. x1 − x2 − x3 + 3x4 ≤ 1 5x1 + x2 + 3x3 + 8x4 ≤55 −x1 + 2x2 + 3x3 −5x4 ≤ 3 x1, x2, x3, x4 ≥0 Cours 6 : dualit´ e 2/35 En route vers la dualit´ e (1/5) max 4x1 + x2 + 5x3 + 3x4 s.c. x1 − x2 − x3 + 3x4 ≤ 1 5x1 + x2 + 3x3 + 8x4 ≤55 −x1 + 2x2 + 3x3 −5x4 ≤ 3 x1, x2, x3, x4 ≥0 Algo du simplexe = ⇒borne inf´ erieure de la fonction objectif Cours 6 : dualit´ e 2/35 En route vers la dualit´ e (1/5) max 4x1 + x2 + 5x3 + 3x4 s.c. x1 − x2 − x3 + 3x4 ≤ 1 5x1 + x2 + 3x3 + 8x4 ≤55 −x1 + 2x2 + 3x3 −5x4 ≤ 3 x1, x2, x3, x4 ≥0 Algo du simplexe = ⇒borne inf´ erieure de la fonction objectif Et si on voulait une borne sup´ erieure ? Cours 6 : dualit´ e 2/35 En route vers la dualit´ e (1/5) max 4x1 + x2 + 5x3 + 3x4 s.c. x1 − x2 − x3 + 3x4 ≤ 1 5x1 + x2 + 3x3 + 8x4 ≤55 −x1 + 2x2 + 3x3 −5x4 ≤ 3 x1, x2, x3, x4 ≥0 Algo du simplexe = ⇒borne inf´ erieure de la fonction objectif Et si on voulait une borne sup´ erieure ? 2` eme contrainte ×5 3 : 25 3 x1 + 5 3x2 + 5x3 + 40 3 x4 ≤275 3 or z ≤25 3 x1 + 5 3x2 + 5x3 + 40 3 x4 = ⇒z ≤275 3 Cours 6 : dualit´ e 2/35 En route vers la dualit´ e (2/5) max 4x1 + x2 + 5x3 + 3x4 s.c. x1 − x2 − x3 + 3x4 ≤ 1 5x1 + x2 + 3x3 + 8x4 ≤55 −x1 + 2x2 + 3x3 −5x4 ≤ 3 x1, x2, x3, x4 ≥0 Somme des 2` eme et 3` eme contraintes : 4x1 + 3x2 + 6x3 + 3x4 ≤58 = ⇒z ≤58 Cours 6 : dualit´ e 3/35 En route vers la dualit´ e (2/5) max 4x1 + x2 + 5x3 + 3x4 s.c. x1 − x2 − x3 + 3x4 ≤ 1 5x1 + x2 + 3x3 + 8x4 ≤55 −x1 + 2x2 + 3x3 −5x4 ≤ 3 x1, x2, x3, x4 ≥0 Somme des 2` eme et 3` eme contraintes : 4x1 + 3x2 + 6x3 + 3x4 ≤58 = ⇒z ≤58 principe valable pour toute combinaison lin´ eaire ` a coeffs ≥0 Cours 6 : dualit´ e 3/35 En route vers la dualit´ e (3/5) Principe du dual faire une combinaison lin´ eaire des contraintes : m X i=1 yi× i ` eme contrainte, avec yi ≥0 z inf´ erieur ` a la combinaison lin´ eaire = ⇒z ≤ m X i=1 yibi Cours 6 : dualit´ e 4/35 En route vers la dualit´ e (4/5) max 4x1 + x2 + 5x3 + 3x4 s.c. x1 − x2 − x3 + 3x4 ≤ 1 5x1 + x2 + 3x3 + 8x4 ≤55 −x1 + 2x2 + 3x3 −5x4 ≤ 3 x1, x2, x3, x4 ≥0 y1 × ( x1 − x2 − x3 + 3x4 ≤ 1 ) y2 × ( 5x1 + x2 + 3x3 + 8x4 ≤55 ) y3 × ( −x1 + 2x2 + 3x3 −5x4 ≤ 3 ) ( y1 + 5y2 − y3 )× x1 + ( −y1 + y2 + 2y3 )× x2 + ( −y1 + 3y2 + 3y3 )× x3 + ( 3y1 + 8y2 −5y3 )× x4 ≤(y1 + 55y2 + 3y3) Cours 6 : dualit´ e 5/35 En route vers la dualit´ e (5/5) ( y1 + 5y2 − y3 ) × x1 + ( −y1 + y2 + 2y3 ) × x2 + ( −y1 + 3y2 + 3y3 ) × x3 + ( 3y1 + 8y2 −5y3 ) × x4 ≤(y1 + 55y2 + 3y3) Or fonction objectif = 4x1 + 1x2 + 5x3 + 3x4 = ⇒ ( y1 + 5y2 − y3 ) ≥4 ( −y1 + y2 + 2y3 ) ≥1 ( −y1 + 3y2 + 3y3 ) ≥5 ( 3y1 + 8y2 −5y3 ) ≥3 Cours 6 : dualit´ e 6/35 En route vers la dualit´ e (5/5) ( y1 + 5y2 − y3 ) × x1 + ( −y1 + y2 + 2y3 ) × x2 + ( −y1 + 3y2 + 3y3 ) × x3 + ( 3y1 + 8y2 −5y3 ) × x4 ≤(y1 + 55y2 + 3y3) Or fonction objectif = 4x1 + 1x2 + 5x3 + 3x4 = ⇒ ( y1 + 5y2 − y3 ) ≥4 ( −y1 + y2 + 2y3 ) ≥1 ( −y1 + 3y2 + 3y3 ) ≥5 ( 3y1 + 8y2 −5y3 ) ≥3 = ⇒z ≤(y1 + 55y2 + 3y3) Cours 6 : dualit´ e 6/35 En route vers la dualit´ e (5/5) ( y1 + 5y2 − y3 ) × x1 + ( −y1 + y2 + 2y3 ) × x2 + ( −y1 + 3y2 + 3y3 ) × x3 + ( 3y1 + 8y2 −5y3 ) × x4 ≤(y1 + 55y2 + 3y3) Or fonction objectif = 4x1 + 1x2 + 5x3 + 3x4 = ⇒ ( y1 + 5y2 − y3 ) ≥4 ( −y1 + y2 + 2y3 ) ≥1 ( −y1 + 3y2 + 3y3 ) ≥5 ( 3y1 + 8y2 −5y3 ) ≥3 = ⇒z ≤(y1 + 55y2 + 3y3) meilleure borne = ⇒min y1 + 55y2 + 3y3 Cours 6 : dualit´ e 6/35 Probl` eme dual D´ eﬁnition du dual probl` eme d’origine : le primal : max n X j=1 cjxj s.c.      n X j=1 aijxj ≤bi (i = 1, 2, . . . , m) xj ≥0 (j = 1, 2, . . . , n) le probl` eme dual : min m X i=1 biyi s.c.      m X i=1 aijyi ≥cj (j = 1, 2, . . . , n) yi ≥0 (j = 1, 2, . . . , m) Cours 6 : dualit´ e 7/35 Comparaison primal – dual (1/2) min m X i=1 biyi s.c.      m X i=1 aijyi ≥cj (j = 1, 2, . . . , n) yi ≥0 (j = 1, 2, . . . , m) (x1, . . . , xn) solution du primal (y1, . . . , ym) solution du dual n X j=1 cjxj ≤ n X j=1 m X i=1 aijyi ! xj Cours 6 : dualit´ e 8/35 Comparaison primal – dual (1/2) min m X i=1 biyi s.c.      m X i=1 aijyi ≥cj (j = 1, 2, . . . , n) yi ≥0 (j = 1, 2, . . . , m) (x1, . . . , xn) solution du primal (y1, . . . , ym) solution du dual n X j=1 cjxj ≤ n X j=1 m X i=1 aijyi ! xj ≤ m X i=1   n X j=1 aijxj  yi Cours 6 : dualit´ e 8/35 Comparaison primal – dual (1/2) min m X i=1 biyi s.c.      m X i=1 aijyi ≥cj (j = 1, 2, . . . , n) yi ≥0 (j = 1, 2, . . . , m) (x1, . . . , xn) solution du primal (y1, . . . , ym) solution du dual n X j=1 cjxj ≤ n X j=1 m X i=1 aijyi ! xj ≤ m X i=1   n X j=1 aijxj  yi ≤ m X i=1 biyi n X j=1 cjxj ≤ m X i=1 biyi Cours 6 : dualit´ e 8/35 Comparaison primal – dual (2/2) n X j=1 cjxj ≤ m X i=1 biyi (x∗ 1, . . . , x∗ n) solution du primal (y∗ 1, . . . , y∗ m) solution du dual alors n X j=1 cjx∗ j = m X i=1 biy∗ i = ⇒(x∗ 1, . . . , x∗ n) et (y∗ 1, . . . , y∗ m) optimaux Cours 6 : dualit´ e 9/35 Comparaison primal – dual (2/2) n X j=1 cjxj ≤ m X i=1 biyi (x∗ 1, . . . , x∗ n) solution du primal (y∗ 1, . . . , y∗ m) solution du dual alors n X j=1 cjx∗ j = m X i=1 biy∗ i = ⇒(x∗ 1, . . . , x∗ n) et (y∗ 1, . . . , y∗ m) optimaux D´ emonstration : transparent pr´ ec´ edent : ∀(x1, . . . , xn), n X j=1 cjxj ≤ m uploads/Litterature/cours-dualite.pdf