Programacion lineal

DUALIDAD
OBJETIVO: PRESENTAR LA FORMA
ALTERNA PARA LA FORMULACIÓN DEL
MODELO DUAL
TEMAS:
TRANSFORMACIÓN ALTERNA AL DUAL
MANEJO DE VARIABLES LIBRES Y NOPOSITIVAS
CONCLUSIONES
17/04/2007 06:20 p.m.

1

TRANSFORMACIÓN ALTERNA

Todo problema de maximización Primal tiene un
problema de minimización en su Dual.
Todo problema de minimización Primal tiene un
problema de maximización ensu Dual.
Cada restricción del Primal implica una variable Dual
Cada variable del Primal implica una restricción Dual

17/04/2007 06:20 p.m.

2

TRANSFORMACIÓN ALTERNA
Los coeficientes del lado derecho del Primal, son los
coeficiente de la función objetivo del Dual.
Los coeficientes de la función objetivo del Primal, son
los coeficientes del lado derecho del Dual.
Los coeficientestecnológicos del la variable j del
Primal, son los coeficientes tecnológicos de la
restricción j del Dual.
Los coeficientes tecnológicos de la restricción i del
Primal, son los coeficientes tecnológicos de la variable i
del Dual.
17/04/2007 06:20 p.m.

3

TRANSFORMACIÓN ALTERNA
Cuando un modelo no está en forma canónica puede
seguirse la siguiente tabla de transformación:
PRIMALFUNCIÓN
OBJETIVO

maximización

minimización

≥0
≤0
LIBRE
≤
≥
=

≥
≤
=
≥0
≤0
LIBRE

VARIABLE

RESTRICCIÓN
DUAL
17/04/2007 06:20 p.m.

DUAL
FUNCIÓN
OBJETIVO
RESTRICCIÓN

VARIABLE
PRIMAL
4

MANEJO DE VARIABLES LIBRES
Y NO-POSITIVAS
Como se observa en la tabla de transformación
anterior, en un momento dado se puede estar utilizando
variables no-positivas ( xk ≤ 0) yvariables libres, esto es,
variables sin restricción de signo (xk ≥ 0 ó xk ≤ 0),
Al definir al algoritmo Simplex siempre se trabajo con
variables no-negativas y así debe continuar.
Por lo tanto debe hacerce un ajuste al modelo para
poder manejar variables no-positiovas y las variables
libres.

17/04/2007 06:20 p.m.

5

MANEJO DE VARIABLES LIBRES
Y NO-POSITIVAS
Si se tiene unavariable no-positivas; xk ≤ 0.
Se realiza la susbstitución
xk = - x’k ,
donde
x’k ≥ 0
Si se tiene una variable LIBRE; xk ≤ 0, xk ≥ 0.
Se realiza la susbstitución
xk = x’k - x’’k
donde
x’k ≥ 0, x’’k ≥ 0
17/04/2007 06:20 p.m.

6

EJEMPLO
Ejercicio 20
FORMULACIÓN PRIMAL:
max z = 2 x1 + 5 x2
sujeta a

x1 - x2
≤3
x2
=4
-2x1 -x1 + 3x2
≤6
x1 ≤ 0, x2 : LIBRE
17/04/2007 06:20 p.m.7

EJEMPLO
FORMULACIÓN DUAL:
min z = 3 w1 + 4 w2 + 6 w3
sujeta a

w1 - 2w2 - w3 ≤ 2
-w1 - w2 + 3 w3 = 5
w1 ,
w3 ≥ 0
w2 : LIBRE

17/04/2007 06:20 p.m.

8

EJEMPLO
DUAL; Se substituye w2 = w’2 - w”2
min z = 3 w1 + 4 w’2 - 4 w”2 + 6 w3
sujeta a

w1 - 2w’2 + 2w”2 - w3 ≤ 2
-w1 - w’2 + w”2 + 3 w3 = 5
w1, w’2, w”2 ,
w3 ≥ 0

17/04/2007 06:20 p.m.

9

EJEMPLO
DUAL; Seutilizará el método de la gran M
min z = 3 w1 + 4 w’2 - 4 w”2 + 6 w3 + MA
sujeta a

w1 - 2w’2 + 2w”2 - w3 + w4
=2
-w1 - w’2 + w”2 + 3 w3
+A = 5
w1,
w’2,
w”2 ,
w3 , w4 , A ≥ 0

17/04/2007 06:20 p.m.

10

EJEMPLO
Tabla Simplex

Coeficientes

Ec
(R)

z

w1

w’2

w”2

w3

w4

A

z

(0)

-1

3

4

-4

6

0

M

0

w4

(1)

0

1

-2

2-1

1

0

2

A

(2)

0

-1

-1

1

3

0

1

5

V.B

17/04/2007 06:20 p.m.

Lado
derecho

11

EJEMPLO
Los coeficientes de las variables básicas en el
renglón cero no son correctos y se reducen a cero.
Coeficientes

Ec
(R)

z

w1

w’2

w”2

w3

w4

A

z

(0)

-1

3

4

-4

6

0

M

0

w4

(1)

0

1

-2

2-1

1

0

2

A

(2)

0

-1

-1

1

3

0

1

5

V.B

17/04/2007 06:20 p.m.

Lado
derecho

12

EJEMPLO
Los coeficientes de las variables básicas en el
renglón cero no son correctos y se reducen a cero.
Coeficientes

Ec
(R)

z

w1

w’2

w”2

w3

w4

A

z

(0)

-1

3

4

-4

6

0

M

0

w4

(1)

0

1

-2

2...