Primal dual

3. DUALIDAD.

3.1. Introducci´n. o

3.2. Ejemplo.

3.3. Problema dual.

3.4. Teoremas de dualidad.

3.5. Soluci´n dual optima en la tabla. o ´

3.6. M´todo simplex dual. e M´todo de la restricci´n artificial. e o

3.7. Algoritmo simplex dual.
1

3.1. Introducci´n. o

MODELO PRIMAL ←→ MODELO DUAL

Algunas razones por las que conviene tener en cuenta la dualidad: 1. Resolver elm´s conveniente de los modelos para a dar la soluci´n para ambos. o 2. Interpretaci´n econ´mica del problema. o o 3. Algoritmo simplex dual.

2

3.2. Ejemplo.
PRODUCTOS RECURSOS A B C BENEFICIO 1 2 2 5 4 2 3 4 1 3 3 1.5 3 2 6 4 4 1 2 2 UNIDADES DE RECURSOS 300 500 250

Problema primal. xj : unidades de producto j, j = 1, . . . , 4. max z = 4x1 + 3x2 + 6x3 + 2x4 sujeto a 2x1 + 3x2 + 1.5x3+ 4x4 ≤ 300 2x1 + 4x2 + 3x3 + x4 ≤ 500 5x1 + x2 + 2x3 + 2x4 ≤ 250 xj ≥ 0 j = 1, . . . , 4 Problema dual. yj : cantidad a pagar por unidad de rec. j, j = A, B, C. min G = 300y1 + 500y2 + 250y3 sujeto a 2y1 + 2y2 + 5y3 ≥ 4 3y1 + 4y2 + y3 ≥ 3 1.5y1 + 3y2 + 2y3 ≥ 6 4y1 + y2 + 2y3 ≥ 2 y1 , y 2 , y 3 ≥ 0
3

3.3. Problema dual. Definici´n 1 (Forma sim´trica de maximizaci´n) Un o e o modelo lineal est´escrito en forma sim´trica de maxia e mizaci´n si o • El objetivo es maximizar. • Todas las restricciones son del tipo ≤. • Todas las variables son no negativas. Definici´n 2 (Forma sim´trica de minimizaci´n) Un o e o modelo lineal est´ escrito en forma sim´trica de minia e mizaci´n si o • El objetivo es minimizar. • Las restricciones son del tipo ≥. • Las variables son no negativas.

43.3.1. Relaci´n primal dual en forma sim´trica. o e PRIMAL max z = cT x sujeto a DUAL min G = bT y sujeto a ←→

Ax ≤ b x≥0

AT y ≥ c y≥0

Modelo primal

↔ ↔ ↔ ↔ = =

Modelo dual

A es m × n b: vector de recursos cT : vector de costes
N´mero de restricciones u N´mero de variables u

AT es n × m bT : vector de costes c: vector de recursos
N´mero de variables u N´mero de restricciones u5

3.3.2. Dualidad: el caso general. ´ RELACION PRIMAL-DUAL max restricci´n i o restricci´n i o variable i variable i ≤ ≥ restricci´n i = o ≥ 0 ≤ 0 ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ min variable i variable i ≥ 0 ≤ 0 ≥ = ≤ variable i no restringida restricci´n i o restricci´n i o restricci´n i o

variable i no restringida

3.4. Teoremas de dualidad Los siguientes teoremas establecen las relacionesentre el problema primal, el dual y sus soluciones. En todas ellas se utiliza la forma primal-dual sim´trica. e Teorema 1 El dual del dual es el primal. Teorema 2 (Dualidad d´bil) Sean x e y soluciones e factibles para los problemas primal y dual respectivamente. Se verifica z = cT x ≤

bT y = G
6

Corolario 1 Si las soluciones factibles x∗ e y∗ verifican cT x∗ = bT y∗ , entonces x∗ e y∗ sonsoluciones optimas ´ para el primal y el dual respectivamente. Corolario 2 Si el problema primal es factible y no acotado, el dual no tiene soluci´n. o Corolario 3 Si el problema dual es factible y no acotado, el primal es infactible. Teorema 3 (Principio fundamental de la dualidad) Si existe una soluci´n optima x∗ para el problema primal, o ´ entonces existe una soluci´n optima y∗ para el problema o ´dual. De la misma forma, si existe una soluci´n optima o ´ y∗ para el problema dual, entonces existe una soluci´n o ∗ para el problema primal. En ambos casos, optima x ´ z ∗ = c T x∗ = b T y ∗ = G ∗ Teorema 4 Si B es base optima para el problema pri´ ∗T = cT B−1 es una soluci´n optima del mal, entonces y o ´ B dual.

7

3.5. Soluci´n dual optima en la tabla. o ´

y∗T = cT B−1 es lasoluci´n optima del modelo dual. o ´ B
• Si el modelo est´ en forma can´nica y b ≥ 0, la a o tabla optima es la siguiente ´ x1 x2 . . . x n xn+1 xn+2 . . . xn+m

cT B−1 A − cT B

cT B−1 B

c T xB B

cB

B

B−1A

B−1

xB

• Si hay variables artificiales en la base
T T T cB B−1I − cT = cB B−1 − cI I

Sumando cT se obtiene y∗T = cT B−1 . I B

8

Ejemplo 1. Dados los siguientes...