Dialidad6 Ok

Dualidad y postoptimizacin

ESCUELA TCNICA SUPERIOR DE INGENIERA

DDDDEPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE EPARTAMENTO DE OOOORGANIZACINRGANIZACINRGANIZACINRGANIZACIN IIIINDUSTRIALNDUSTRIALNDUSTRIALNDUSTRIAL

Dualidad y postoptimizacin

Jos Mara Ferrer CajaUniversidad Pontificia Comillas

Definicin

A cada problema de optimizacin lineal le corresponde otro que se denomina problema dual

En forma cannica

max

( )

T

xc x

P Ax b

min Tyb y

Primal Dual

Dualidad y postoptimizacin - 1ESCUELA TCNICA SUPERIOR DE INGENIERA


La correspondencia es biunvoca El dual del dual es el primal

, , , ,n m n m n mx y c A b

( )

0

P Ax b

x

( )

0

y

TD A y c

y

Problema dual en forma cannica. Ejemplo

1 2

1

2

1 2

max 3 5

4

2 12

3 2 18

, 0

z x x

x

x

x x

x x

= +

+

Primal Dual

1 2 3

1 3

2 3

1 2 3

min 4 12 18

3 3

2 2 5

, , 0

w y y y

y y

y y

y y y

= + +

+

+



1 2, 0x x

1 2 3, , 0y y y

Interpretacin econmica

El valor de la variable dual yj representa el incremento en la funcin objetivo z del problema primal al aumentar marginalmente el recurso bj

Expresiones equivalentes: Variable dual Precio en la sombra Multiplicador simplex



Multiplicador simplex

Tabla de transformaciones

minimizacin

maximizacin VARIABLES RESTRICCIONES

0 0

No restringida = RESTRICCIONES VARIABLES

0



0 0 = No restringida

Las transformaciones y las relaciones entre ambos problemas son simtricas

Problema dual. Ejemplo

1 3 4

1 2 4

2 3 4

1 2 3

1 2 3

min 2 4

3 2 0

4 5 3

2 3 1

, 0, 0

z x x x

x x x

x x x

x x x

x x x

= +

+

+ +

+ =

Primal



2 3

1 3

1 2 3

2 3

1 2

1 2

max 3

2 2

3 4 0

3 1

2 5 4

0, 0

w y y

y y

y y y

y y

y y

y y

= +

+

+ =

Dual

Teorema dbil de dualidad

El valor de la funcin objetivo para cualquier solucin factible del problema de maximizacin es menor o igual que el valor de la funcin objetivo para cualquier solucin factible del problema de minimizacin

T Tc x b y



Teorema fuerte de dualidad

Si uno de los problemas tiene solucin ptima, entonces el otro tambin, y los valores objetivos ptimos coinciden

* *T Tc x b y=



Soluciones bsicas complementarias (1) En cada iteracin del mtodo simplex, se encuentra

una solucin bsica factible del primal y una solucin bsica ptima (con costes reducidos positivos) del dual. Los valores objetivos coinciden

1 1

T

B B

T T

x B b y c B

c x b y

= =

=



Si la solucin bsica del primal no es ptima, la solucin bsica del dual no es factible

Si la solucin bsica del primal es ptima, la solucin bsica del dual tambin es ptima

c x b y=

Soluciones bsicas complementarias (2) Cuando los problemas primal y dual originales

corresponden a la forma cannica, en cada iteracin del mtodo simplex: Los valores de las variables duales originales son los costes

reducidos de las variables primales de holgura (y exceso) Los valores de las variables duales de holgura (y exceso)

son los costes reducidos de las variables primales originales



Los costes reducidos de las variables duales no bsicas son los valores de las variables primales bsicas

Soluciones complementarias. Ejemplo (1)

1 2

1 2

1 2

1 2

max 3

3( )

1

, 0

x x

x xP

x x

x x

+

+

+

1 2

1 2

1 2

1 2

min 3

1( )

3

, 0

y y

y yD

y y

y y

+

+

En forma estndar



1 2

1 2 3

1 2 4

1 2 3 4

min 3

1( )

3

, , , 0

y y

y y yD

y y y

y y y y

+

=

+ =

1 2

1 2 3

1 2 4

1 2 3 4

min 3

3

1

, , , 0

x x

x x x

x x x

x x x x

+ + =

+ + =


Tabularmente

( )3 11 14 2

1 0 3 ; ; 0 0

0 1 1T T

B B

x yB x B b y c B

x y

= = = = = = =

z x x x x RHS

3 4 1, 3y y= =

1 2 0, 0y y= =



z x1 x2 x3 x4 RHS-z -1 -1 -3 0 0 0x3 0 1 1 1 0 3x4 0 -1 1 0 1 1

Costes reducidosde y1 e y2

Solucin no ptima para (P) y no factible para (D)


3 4 4, 0y y= =

1 2 0, 3y y= =


z x1 x2 x3 x4 RHS-z -1 -4 0 0 3 3x3 0 2 0 1 -1 2x2 0 -1 1 0 1 1



( ) ( )1 12

1 1 0 3 0 3

0 1T T

B

yy c B

y

= = = =

Solucin no ptima para (P) y no factible para (D)

Algebraicamente


3 4 0, 0y y= =

1 2 2, 1y y= =


z x1 x2 x3 x4 RHS-z -1 0 0 2 1 7x1 0 1 0 1/2 -1/2 1x2 0 0 1 1/2 1/2 2



( ) ( )1 12

* 1/2 1/2( *) 1 3 2 1

* 1/2 1/2T T

B

yy c B

y

= = = =

Solucin ptima para (P) y factible para (D)

Algebraicamente

Soluciones complementarias. Ejemplo (5) Geomtricamente

(0,0)

(0,1)

(3,0)

(1,2)

(-1,0)

(0,3)



(0,0)(3,0)(1,0)

(0,3)

(0,-1)

(2,1)

Teorema fundamental de dualidad

Dados dos problemas respectivamente duales, se cumple una y slo una de las siguientes afirmaciones: Ambos problemas tienen solucin ptima Uno de ellos tiene solucin no acotada y el otro es no factible Ambos problemas son no factibles



Teorema de holguras complementarias

Dados dos problemas respectivamente duales, con soluciones ptimas x* e y*: Si una variable es bsica su restriccin dual se cumple con

igualdad (la variable dual de holgura no es bsica) Si una restriccin se cumple estrictamente (variable de holgura

bsica) su variable dual no es bsica (y por tanto, nula)



Dada una solucin Se llama restriccin activa a la que se cumple con igualdad Se llama restriccin inactiva a la que se cumple con

desigualdad estricta

Holguras complementarias. Ejemplo (1)Queremos resolver el problema:

Como tiene 2 restricciones, su problema dual tendr dos

1 2 3

1 2 3

1 2 3

1 2 3

min 8 4 2

5( )

4 2 2

, , 0

z x x x

x x xP

x x x

x x x

= + +

+ +

+



Como tiene 2 restricciones, su problema dual tendr dos variables, y podr resolverse geomtricamente:

1 2

1 2

1 2

1 2

1 2

max 5 2

4 8

( ) 4

2 2

, 0

w y y

y y

D y y

y y

y y

= +

+

+

Holguras complementarias. Ejemplo (2)

1 24 8y y+ =

10y =

ptimo10 2,3 3

1 22 2y y =



1 24y y+ =

20y =

5

2c

=

La solucin ptima del problema dual es y1* = 10/3, y2* = 2/3

La funcin objetivo vale w* = 18

Holguras complementarias. Ejemplo (3) y1* = 10/3 > 0 (la 1 variable es bsica) x1* + x2* + x3* = 5 (la 1

restriccin es activa) y2* = 2/3 > 0 (la 2 variable es bsica) 4x1* + x2* - 2x3* = 2 (la 2

restriccin es activa) y1* + 4y2* < 8 (la 1 restriccin es inactiva) x1* = 0

Se resuelve el sistema:



Se resuelve el sistema: x2* + x3* = 5x2* - 2x3* = 2

Se ha llegado a la solucin ptima del problema primal sin necesidad de usar el teorema de dualidad fuerte, que asegura

z* = w* = 18 Esta propiedad podr aplicarse conjuntamente con el teorema de

holguras complementarias, aportando una ecuacin ms

x2* = 4, x3* = 1 con z* = 18

Mtodo simplex dual

Mtodo alternativo al simplex para resolver un problema de optimizacin lineal

Parte de una solucin bsica ptima (con costes reducidos positivos), pero quiz infactible Solucin dual factible: solucin bsica con costes reducidos

positivos En cada iteracin se saca de la base una variable con



En cada iteracin se saca de la base una variable con valor negativo, y se mete una variable de forma que no se pierda la optimalidad

Cuando se consiga una solucin bsica factible (primal factible) el mtodo termina. Si no se puede, el problema es infactible

Algoritmo dual simplex

1. Inicializacin Elegir una base B que proporcione una solucin bsica dual

factible (con costes reducidos positivos)

2. Criterio de factibilidad. Eleccin de la variable de salida Si La solucin actual es ptima

1

0B

N

x b B b

x

= =

=

1 0T T T T TN N B N Bc c c B N c c Y= =

1 0b B b=



Si La solucin actual es ptima Si no, elegir la variable bsica tal que

3. Eleccin de la variable de entrada Si Problema infactible (el dual es no acotado) Si no, elegir no bsica tal que

4. Pivoteo Con la nueva base actualizar Volver al paso 2

sx

min : 0N

j jt t

sjj Ist sj

c zc zy

y y

=

Inicializacin del algoritmo dual simplex

Si se conoce una base que proporcione una solucin bsica dual factible, se utiliza sta como solucin inicial del algoritmo Cuando el problema est en forma cannica de minimizacin

con c 0, la base asociada a las variables de holgura/exceso proporciona siempre una solucin bsica dual factible

Si no, se requiere un mtodo para encontrar una



Si no, se requiere un mtodo para encontrar una solucin bsica dual factible

Un mtodo rpido es la tcnica de la restriccin artificial

Algoritmo dual simplex. Ejemplo (1)

Aadimos variables de exceso y cambiamos de signo:

1 2 3

1 2 3

1 2 3

1 2 3

min 8 4 2

5( )

4 2 2

, , 0

z x x x

x x xP

x x x

x x x

= + +

+ +

+

min 8 4 2z x x x= + +



La base asociada a las variables x4 y x5 es la identidad

1 2 3

1 2 3 4

1 2 3 5

min 8 4 2

5

4 2 2

0j

z x x x

x x x x

x x x x

x j

= + +

+ =

+ + =

( )1 8 4 2 0T T T TN N B Nc c c B N c= = = Dual factible

Algoritmo dual simplex. Ejemplo (2)Se aplica el algoritmo dual simplex en forma tabular:

8 4 2 0 0z x1 x2 x3 x4 x5 RHS

-z -1 8 4 2 0 0 00 x4 0 -1 -1 -1 1 0 -50 x5 0 -4 -1 2 0 1 -2

8 4 2



8 4 2

z x1 x2 x3 x4 x5 RHS-z -1 6 2 0 2 0 -10x3 0 1 1 1 -1 0 5x5 0 -6 -3 0 2 1 -12

1 2/3

Algoritmo dual simplex. Ejemplo (3)

Como hemos alcanzado una solucin factible (sin perder laoptimalidad), la solucin actual es ptima

z x1 x2 x3 x4 x5 RHS-z -1 2 0 0 2/3 2/3 -18x3 0 -1 0 1 -1/3 1/3 1 0x2 0 2 1 0 -2/3 -1/3 4 0



optimalidad), la solucin actual es ptima

1 2 3* 0, * 4, * 1, * 18x x x z= = = =

Tcnica de la restriccin artificial (1) Expresar el problema en forma cannica de minimizacin

Aadir variables de holgura (exceso) en todas las restricciones y cambiar de signo para obtener la identidad

min

( )

0

Tc x

P Ax b

x

min Tc x minTc x



Construir la tabla asociada a la base Si la solucin bsica actual es dual factible

Aplicar el algoritmo dual simplex Si no, agregar la restriccin con arbitrariamente

grande Aadir una variable de holgura

0j jc z j

B I=

N

jj I

x M

0, 0h

h

Ax Ix b

x x

=

0, 0h

h

Ax Ix b

x x

+ =

M

1

N

j nj I

x x M+

+ =

Tcnica de la restriccin artificial (2) Introducir a la tabla la fila asociada a la restriccin artificial, con

variable bsica Meter en la base la variable con y sacar la

variable pivotando sobre el elemento Se habr alcanzado una solucin dual factible Aplicar el

algoritmo dual simplex

1nx

+

tx { } min : 0t j jjc c c= *x

1 1 1* 0, 0

n n nx c z

+ = = *x

1 1 1* 0, 0

n n nx c z

+ = >

Tcnica de la restriccin artificial. Ejemplo (1)

La 1 restriccin es de igualdad. Habra que desglosarla en dos

1 2 3

1 2 3

2 3

2 3

1 2 3

min 2 3

2 6

2 2

2 4

, , 0

x x x

x x x

x x

x x

x x x

+

+ + =

+

+



La 1 restriccin es de igualdad. Habra que desglosarla en dos desigualdades. En este caso lo podemos evitar ya que x1 aporta una columna a la identidad. Aadimos variables de holgura a las otras dos:

1 2 3

1 2 3

2 3 4

2 3 5

1 2 3 4 5

min 2 3

2 6

2 2

2 4

, , , , 0

x x x

x x x

x x x

x x x

x x x x x

+

+ + =

+ =

+ + =

Tcnica de la restriccin artificial. Ejemplo (2)Cambiamos de signo la 2 restriccin para obtener la identidad:

Tomamos la base B = I asociada a las variables x1, x4 y x5

1 2 3

1 2 3

2 3 4

2 3 5

1 2 3 4 5

min 2 3

2 6

2 2

2 4

, , , , 0

x x x

x x x

x x x

x x x

x x x x x

+

+ + =

+ =

+ + =



Tomamos la base B = I asociada a las variables x1, x4 y x5La tabla inicial es

No es dual factible, ya que c3 z3 < 0

-2 1 -3 0 0z x1 x2 x3 x4 x5 RHS

-z -1 0 5 -1 0 0 12-2 x1 0 1 2 1 0 0 60 x4 0 0 -1 -2 1 0 -20 x5 0 0 2 1 0 1 4

Tcnica de la restriccin artificial. Ejemplo (3)Aadimos al problema la restriccin artificial, con su variable de holgura

Aadimos la columna de x6 a la base anterior consiguiendo de nuevo laidentidad (de orden 4 ahora)

2 3 2 3 6 6, 0x x M x x x M x+ + + =

z x1 x2 x3 x4 x5 x6 RHS-z -1 0 5 -1 0 0 0 12x1 0 1 2 1 0 0 0 6



Entra en la base x3 por ser la nica variable con coste reducido negativoSale de la base x6Se pivota sobre el elemento correspondiente

x1 0 1 2 1 0 0 0 6x4 0 0 -1 -2 1 0 0 -2x5 0 0 2 1 0 1 0 4x6 0 0 1 1 0 0 1 M

Tcnica de la restriccin artificial. Ejemplo (4)Tras el pivoteo, se obtiene una solucin bsica dual factibleSe aplica normalmente el algoritmo dual simplex

z x1 x2 x3 x4 x5 x6 RHS-z -1 0 6 0 0 0 1 12+Mx1 0 1 1 0 0 0 -1 6-Mx4 0 0 1 0 1 0 2 2M-2



Sale de la base x5 por ser la variable bsica con valor ms negativoEntra en la base x6 por ser la nica variable con y5j < 0Se pivota sobre el elemento correspondiente

x5 0 0 1 0 0 1 -1 4-Mx3 0 0 1 1 0 0 1 M

1

Tcnica de la restriccin artificial. Ejemplo (5)

z x1 x2 x3 x4 x5 x6 RHS-z -1 0 7 0 0 1 0 16x1 0 1 0 0 0 -1 0 2 0x4 0 0 3 0 1 2 0 6 0x6 0 0 -1 0 0 -1 1 M-4 0x 0 0 2 1 0 1 0 4 0



Hemos alcanzado una solucin factible (sin perder la optimalidad)La solucin actual es ptima para el problema modificadoComo x6* > 0 tambin es ptima para el problema original:

x3 0 0 2 1 0 1 0 4 0

1 2 3

4 5

* 2, * 0, * 4

* 6, * 0

* 16

x x x

x x

z

= = =

= =

=

Anlisis de sensibilidad

Estudia los efectos sobre la solucin ptima de un cambio en alguno de los elementos del problema

Se trata de aprovechar la informacin dada en la tabla ptima, no de comenzar a resolver de nuevo el problema

Se introducirn los cambios de forma oportuna en la tabla ptima



tabla ptima Si se pierde la optimalidad Aplicar simplex Si se pierde la factibilidad Aplicar dual simplex

Anlisis de sensibilidad. EjemploSea el siguiente problema

Su tabla ptima es

1 2 3

1 2 3

1 2 3

1 2 3

min 2 4

1

4 3 5

, , 0

x x x

x x x

x x x

x x x

+

+

+



Se quiere resolver el problema tras algunas modificaciones

x1 x2 x3 x4 x5 RHS-z 14 0 0 13 3 28x3 5 0 1 4 1 9x2 4 1 0 3 1 8

1 2 3* 0, * 8, * 9, * 28x x x z= = = =

Cambio en el vector de costes

Sustitucin de ck por ck

Si xk es no bsica Recalcular su coste reducido Si la solucin actual sigue siendo ptima Si solucin no ptima. Aplicar simplex

' 'k k k kc c c c= +

' 0kc

' 0kc k+1Si no, Hacer k = k+1 y volver al paso 2

Perturbacin en el vector de costes. Ejemplo (1)Se quiere resolver el problema

El vector de costes es (-1 -3)T + (1 1)T

1 2

1 2

1 2

1 2

min( 1 ) ( 3 )

3

1

, 0

x x

x x

x x

x x

+ + +

+

+



El vector de costes es (-1 -3) + (1 1) Paso 1. Obtener la solucin ptima del problema con = 0

Solucin ptima:

x1 x2 x3 x4 RHS-z 0 0 2 1 7x1 1 0 1/2 -1/2 1x2 0 1 1/2 1/2 2

1 2* 1, * 2, * 7x x z= = =

Perturbacin en el vector de costes. Ejemplo (2)Paso 2. Reemplazar el vector de costes c = (-1 -3)T por c = (-1+ -3+)T

La tabla sigue siendo ptima si 2 - 0 2

-1+ -3+ 0 0x1 x2 x3 x4 RHS

-z 0 0 2- 1 7-3-1+ x1 1 0 1/2 -1/2 1-3+ x2 0 1 1/2 1/2 2



La tabla sigue siendo ptima si 2 - 0 2Para [0,2] la solucin ptima esPaso 3. Hacer = 2. Meter en la base x3 por tener coste reducido 0

x1 x2 x3 x4 RHS-z 0 0 0 1 1x1 1 0 1/2 -1/2 1 2x2 0 1 1/2 1/2 2 4

1 2* 1, * 2, * 7 3x x z = = = +

Perturbacin en el vector de costes. Ejemplo (3)

Tabla ptimaPaso 2. Reemplazar el vector de costes c = (1 -1)T por c = (-1+ -3+)T

x1 x2 x3 x4 RHS-z 0 0 0 1 1x3 2 0 1 -1 2x2 -1 1 0 1 1

-1+ -3+ 0 0



La tabla sigue siendo ptima si -4 + 2 0 y 3 - 0 2 3

Para [2,3] la solucin ptima es

-1+ -3+ 0 0x1 x2 x3 x4 RHS

-z -4+2 0 0 3- 3-0 x3 2 0 1 -1 2

-3+ x2 -1 1 0 1 1

1 2* 0, * 1, * 3x x z = = = +

Perturbacin en el vector de costes. Ejemplo (4)Paso 3. Hacer = 3. Meter en la base x4 por tener coste reducido 0

x1 x2 x3 x4 RHS-z 2 0 0 0 0x3 2 0 1 -1 2x2 -1 1 0 1 1 1



Tabla ptima

x2 -1 1 0 1 1 1

x1 x2 x3 x4 RHS-z 2 0 0 0 0x3 1 1 1 0 3x4 -1 1 0 1 1

Perturbacin en el vector de costes. Ejemplo (5)Paso 2. Reemplazar el vector de costes c = (2 0)T por c = (-1+ -3+)T

-1+ -3+ 0 0x1 x2 x3 x4 RHS

-z -1+ -3+ 0 0 00 x3 1 1 1 0 30 x4 -1 1 0 1 1



La tabla sigue siendo ptima si -1 + 0 y -3 + 0 3Para [3,) la solucin ptima es

1 2* 0, * 0, * 0x x z= = =

0 x4 -1 1 0 1 1

Perturbacin en el vector de cotas

Se quiere resolver un problema de PL con vector de cotas b + d, siendo 0

1. Hacer 0 = 0 y k = 0 Obtener la solucin ptima del problema con = 0

2. Mediante anlisis de sensibilidad, determinar el intervalo [k,k+1]para el que la tabla sigue siendo factible



para el que la tabla sigue siendo factible3. Si k+1 = parar

Si no, hacer = k+1 y aplicar dual simplex, sacando de la base una variable bsica con valor 0Si su fila es positiva Problema infactible para > k+1Si no, Hacer k = k+1 y volver al paso 2

Perturbacin en el vector de cotas. Ejemplo (1)Se quiere resolver el problema

El vector del lado derecho es (3 1)T + (-1 1)T

1 2

1 2

1 2

1 2

min 3

3

1

, 0

x x

x x

x x

x x

+

+ +



El vector del lado derecho es (3 1) + (-1 1) Paso 1. Obtener la solucin ptima del problema con = 0

Solucin ptima:

x1 x2 x3 x4 RHS-z 0 0 2 1 7x1 1 0 1/2 -1/2 1x2 0 1 1/2 1/2 2

1 2* 1, * 2, * 7x x z= = =

Perturbacin en el vector de cotas. Ejemplo (2)Paso 2. Reemplazar el vector de cotas b = (3 1)T por b = (3- 1+)T

La tabla sigue siendo factible si 1 - 0 1Para [0,1] la solucin ptima es

( )11 1

3 1 12 2 ' ' ; ' ' 1 3 71 1 1 2 2

2 2

T

Bb B b z c b

= = = = = = +

1 2* 1 , * 2, * 7x x z = = = +



Paso 3. Hacer = 1. Sacar de la base x1 por tener valor 0

x1 x2 x3 x4 RHS-z 0 0 2 1 6x1 1 0 1/2 -1/2 0x2 0 1 1/2 1/2 2

Perturbacin en el vector de cotas. Ejemplo (3)

Paso 2. Reemplazar el vector de cotas b = (2 2)T por b = (3- 1+)T

x1 x2 x3 x4 RHS-z 2 0 3 0 6x4 -2 0 -1 1 0x2 1 1 1 0 2



La tabla sigue siendo factible si -2 + 2 0 y 3 - 0 1 3Para [1,3] la solucin ptima es

( )

11 1 3 2 2

' '1 0 1 3

2 2 ' ' 0 3 9 3

3T

B

b B b

z c b

+ = = = +

+ = = =

1 2* 0, * 3 , * 9 3x x z = = = +

Perturbacin en el vector de cotas. Ejemplo (4)Paso 3. Hacer = 3. Sacar de la base x2 por tener valor 0

Como la fila 2 es completamente positiva no se puede pivotar

x1 x2 x3 x4 RHS-z 2 0 3 0 6x4 -2 0 -1 1 4x2 1 1 1 0 0



Como la fila 2 es completamente positiva no se puede pivotarPara (3, ) el problema es infactible

Documents

Dialidad6 Ok