Dualidad.

DUALIDAD Y
ANÁLISIS
POSTÓPTIMO
IBARRA HERNÁNDEZ PAOLA
MATURANO MURILLO CUAHUTEMOC
ESTRELLA TREJO OLINCER
TEORÍA DE LA DUALIDAD
DEFINICIÓN DEL PROBLEMA DUAL
El problema dual se define sistemáticamente a partir del

modelo de PL primal (u original).
Los dos problemas están estrechamente relacionados en el

sentido de que la solución óptima de uno proporciona
automáticamente la solución óptima al otro.
Cualquier Problema Dual (D)

problema lineal
Tendrá una variable dual por cada
restricción primal.
Y tendrá una restricción dual por
cada variable primal.
Problema Primal
Restricción Variable
(P)
Ejemplo
Problema Primal Problema Dual (D)

(P)
Zmin = 6x1 + 8x 2 Zmax = 4y 1 + 7y 2
Restricciones: Restricciones:
3x 1+ x 2 ≥ 4 3y 1 + 5y2 ≤ 6
5x 1 + 2x2 ≥ 7 y 1 + 2y2 ≤ 8
x1 , x 2 ≥ 0 y1 , y 2≤ 0
Las ideas clave para construir el dual a partir del primal se resumen como:
RELACIONES PRIMAL-DUAL
Los cambios realizados en los datos de un modelo de PL pueden afectar la

optimalidad y/o factibilidad de la solución óptima actual
Asociado a cada problema lineal existe otro problema de programación lineal

denominado problema dual (PD) , que posee importantes propiedades y relaciones
notables con respecto al problema lineal original, problema que para diferencia del
dual se denomina entonces como problema primal (PP).
Repaso de operaciones con matrices simples

Una matriz es una forma rectangular donde se ordenan los números reales mediante
coordenadas reflejadas en los subíndices.
La dimensión de una matriz se representa como la multiplicación de la dimensión de la
fila con la dimensión de la columna. Denominamos (m) para la dimensión de las filas y
(n) para la dimensión de las columnas. Entonces, una matriz mxn tendrá m filas y n
columnas.
Suma y resta
La unión de dos o más matrices solo puede hacerse si dichas matrices tienen la
misma dimensión. Cada elemento de las matrices puede sumarse con los
elementos que coincidan en posición en diferentes matrices.
En el caso de restar dos o más matrices se sigue el mismo procedimiento que
usamos para sumar dos o más matrices.
En otras palabras, cuando sumamos o restamos matrices nos vamos a fijar en:
1. Las matrices compartan la misma dimensión.

2. Sumar o restar los elementos con la misma posición en matrices distintas.
Como hemos dicho, primero comprovamos que sean matrices de igual dimensión. En
este caso, son dos matrices 2×2. A continuación, sumamos los elementos que tienen
las mismas coordenadas. Por ejemplo, (d) y (h) comparten la misma posición en
matrices distintas. La posición, denotada como P, para (d) y (h) es P22.
Ejemplo
Multiplicacion
Generalmente, la multiplicación de matrices cumple la propiedad no conmutativa, es
decir, importa el orden de los elementos durante la multiplicación. Existen casos
llamados matrices conmutativas que sí cumplen la propiedad.
Para multiplicar dos matrices necesitamos que el número de columnas de la primera
matriz sea igual al número de filas de la segunda matriz.
Despues
multiplicamos la
Vamos a empezar primera fila de

multiplicando la la matriz A por
primera fila le la la segunda
matriz A por la columna de la
primera columna matriz B
de la matriz B Hacemos lo mismo
1A*1B 1A*2B
con la segunda fila
de la matriz A con
las columnas 1 y 2
de la matriz B
2A*1B 2A*2B
Finalmente
realizamos las
operaciones
correspondientes
Diseño de la tabla simplex
Solución dual óptima
Las soluciones primal y dual están estrechamente relacionadas en el
sentido de que la solución óptima de uno u otro problema da la solución
óptima al otro. Así pues, en un modelo de PL en el que la cantidad de
variables es considerablemente menor que la de restricciones, pueden
ahorrarse cálculos resolviendo el dual porque la cantidad de cálculos
simplex depende en gran medida (aunque no totalmente) de la cantidad
de restricciones
Esta sección proporciona dos métodos para
determinar los valores duales.
Los elementos del vector fila deben aparecer en el mismo orden en que las
variables básicas aparecen en la columna Básica de la tabla simplex.
Ejemplo
Considere la siguiente PL:
Para preparar el problema para su solución mediante el método simplex, agregamos una variable de
holgura x4 en la primera restricción y una variable artificial R en la segunda. Por consiguiente, el primal
resultante y los problemas duales asociados se definen como sigue:
A continuación demostramos cómo se determinan los valores duales óptimos aplicando los
dos métodos descritos al inicio de esta sección.
Tabla optima del primal del ejemplo anterior

Método 1
En la tabla anterior, las variables primales iniciales x3 y R corresponden sólo a las variables
duales y1 y y2, respectivamente. Por lo tanto, determinamos la solución dual óptima como sigue:
Método 2
La matriz inversa óptima, resaltada la primer tabla, bajo las variables iniciales x4 y R, es :
El orden de las variables básicas primales óptimas en la columna Básica es x2 seguida por x1. Los
elementos de los coeficientes objetivo originales para las dos variables deben aparecer en el
mismo orden, es decir,
(Coeficientes objetivo originales) = (Coeficiente de x2, coeficiente de x1)

= (12,5)
Los valores óptimos duales son

DUALIDAD Y ANÁLISIS POSTÓPTIMO
Relación entre z máxima y w mínima

Valores objetivo primales-duales.
Para cualquier par de soluciones primales y duales
factibles
En el óptimo, la relación se mantiene como una ecuación estricta, lo que significa que los dos
valores objetivo son iguales. Observe que la relación no especifica cuál problema es primal y cuál
es dual. En este caso sólo el sentido de optimización (maximización o minimización) es importante.
El óptimo no puede ocurrir con 'z' estrictamente menor que 'w' porque, no
importa qué tan cerca estén 'z' y 'w', siempre hay la oportunidad de una mejora.

Dualidad.

Cargado por

Copyright:

Formatos disponibles

Dualidad.

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Dualidad.

Cargado por

Copyright:

Formatos disponibles

DUALIDAD Y

DEFINICIÓN DEL PROBLEMA DUAL

El problema dual se define sistemáticamente a partir del

Los dos problemas están estrechamente relacionados en el

Cualquier Problema Dual (D)

Problema Primal Problema Dual (D)

Los cambios realizados en los datos de un modelo de PL pueden afectar la

Asociado a cada problema lineal existe otro problema de programación lineal

Repaso de operaciones con matrices simples

1. Las matrices compartan la misma dimensión.

Vamos a empezar primera fila de

Tabla optima del primal del ejemplo anterior

(Coeficientes objetivo originales) = (Coeficiente de x2, coeficiente de x1)

Los valores óptimos duales son

Relación entre z máxima y w mínima

También podría gustarte