PROGRAMA PRIMAL Y DUAL

PROGRAMA DUAL

Asociada a cualquier estructura canónica de un PL, existe una estructura dual

Programa primal (P1)

Máx Z = CX

St.

AX ≤ b

X ≥ 0

Programa dual (D1)

Min g = b^TY

St.

A^TY ≥ C^T

Y ≥ 0

Donde el programa primal y el dual tienen las siguientes descripciones:

PROBLEMA	ELEMENTO	DIMENSIÓN	CARACTERÍSTICAS
PRIMAL	X	Vector columna de n elementos	Vector de actividades Primarias
	C	Vector fila de n elementos	Vector de costos unitarios primarios
	b	Vector columna de m componentes	Vector de disponibilidad de recursos Primarios
	A	Matriz de m x n	Matriz de coeficientes tecnológicos Primarios
	Z	Escalar	Función objetivo Primaria
	0	Vector columna con n ceros
DUAL	Y	Vector columna de m elementos	Vector de actividades duales
	C^T	Traspuesta del vector C, con n elementos	Vector de costos unitarios primarios
	b^T	Transpuesta del vector b, con m elementos de recursos	Vector de disponibilidad de recursos duales
	A	Matriz de n x m	Matriz de coeficientes tecnológicos duales
	g	Escalar	Función objetivo duales
	0	Vector columna con n ceros

Relaciones primal-dual

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).

Las relaciones las podemos enumerar como siguen:

a) El problema dual tiene tantas variables como restricciones tiene el programa primal.

b) El problema dual tiene tantas restricciones como variables tiene el programa primal.

c) Los coeficientes de la función objetivo del problema dual son los términos independientes de las restricciones o RHS del programa primal.

d) Los términos independientes de las restricciones o RHS del dual son los coeficientes de la función objetivo del problema primal.

e) La matriz de coeficientes técnicos del problema dual es la traspuesta de la matriz técnica del problema primal.

f) El sentido de las desigualdades de las restricciones del problema dual y el signo de las variables del mismo problema, dependen de la forma de que tenga el signo de las variables del problema primal y del sentido de las restricciones del mismo problema. (Ver tabla de TUCKER)

g) Si el programa primal es un problema de maximización, el programa dual es un problema de minimización.

h) El problema dual de un problema dual es el programa primal original.

Tabla de TUCKER

Los problemas duales simétricos son los que se obtienen de un problema primal en forma canónica y ‘normalizada’, es decir, cuando llevan asociadas desigualdades de la forma mayor o igual en los problemas de minimización, y desigualdades menor o igual para los problemas de maximización. Es decir, si el problema original es de la siguiente forma:

Máx Z(x) = ct x

s.a:

A x ≤ b

x ≥ 0

El problema dual (dual simétrico) es:

Mín G(λ) = λb

s.a:

λA ≥ c

λ ≥ 0

Los restantes tipos de combinaciones de problemas, se conocen con el nombre de duales asimétricos. Como por ejemplo:

Máx Z(x) = ct x

s.a:

A x = b

x ≥ 0

El problema dual (dual asimétrico) es:

Mín G(λ) = λ b

s.a:

λA ≥ c

λ >< 0, es decir, variables libres.

PREGUNTAS:

¿Por qué se plantea el programa dual?

¿Qué significado tiene su solución?

¿La solución del dual se puede obtener desde el primal? RESPUESTAS:

a) Por una parte permite resolver problemas lineales donde el número de restricciones es mayor que el número de variables. Gracias a los teoremas que expondremos a continuación la solución de unos de los problemas ( primal o dual) nos proporciona de forma automática la solución del otro programa.

b) La dualidad permite realizar importantes interpretaciones económicas de los problemas de programación lineal.

c) La dualidad permite generar métodos como el método dual del simplex de gran importancia en el análisis de post- optimización y en la programación lineal paramétrica.

Otra de las ventajas de la dualidad, es la posibilidad de resolver gráficamente algunos problemas.

USOS DE LA FORMULACIÓN DUAL

Las estructuras duales permiten entro otras cosas:

1. Resolver problemas lineales que tiene más restricciones que actividades (variables)

Como el grado de dificultad en resolver un PL por computadora está en función del número de filas de la matriz A y no en el número de columnas, al aplicarse la dualidad a un problema primal donde m > n, se obtiene un problema lineal donde el número de filas n es menor al número de columnas m Existen teoremas que aseguran que resolviendo el primal se resuelve automáticamente su correspondiente dual y viceversa.

2. Hacer interpretaciones económicas de las soluciones óptimas de los problemas de programación lineal.

3. Generar métodos como el dual simplex para el análisis de sensibilidad de los PPL.

TEOREMAS QUE RELACIONAN A ESTRUCTURAS PRIMARIAS Y SUS DUALES ASOCIADOS

Sean los programas primal y dual siguientes:

Programa primal (P1)

Máx Z = CX

St.

AX ≤ b

X ≥ 0

Programa dual (D1)

Min g = b^TY

St.

A^TY ≥ C^T

Y ≥ 0

Teorema 4:

Si X* y Y* son soluciones factibles a un par de programas primal (P1) y su correspondiente dual (D1), entonces z = cX* ≤ b^TY* = g

El teorema afirma que para cualquier par de soluciones factibles (X*, Y*), el valor de la función objetivo del primal es menor o igual que el valor de la función objetivo del dual.

La interpretación económica del teorema es que "cuando se ha obtenido las soluciones óptimas el máximo beneficio obtenido z es igual o menor al valor g de los recursos escasos”.

Teorema 5: de la dualidad

Dado un par de problemas primal (Pr) y su correspondiente dual (D1) únicamente, uno y sólo uno de los tres siguientes casos puede ocurrir:

1. Ambos programas tienen soluciones óptimas y el valor de sus funciones objetivos son iguales es decir, si X* es óptimo para (p1) y Y* es óptimo para (D1), entonces Z* = cX*= b^TY* = g*

2. Si el problema primal (Pr) no tiene soluciones factibles y el problema dual (D1) tiene al menos uno entonces, el dual tiene una solución no acotada y viceversa, sí el problema dual no tiene soluciones factibles y el problema primario tiene al menos uno, entonces, el primario tiene una solución óptima no acotada.

3. Ambos problemas (P1) y (D1) no tienen solución

Teorema 6:

Dados el siguiente par de programas primal y dual siguientes:

Programa primal (P1)

Máx Z = CX

St.

AX ≥ b

X ≥ 0

Programa dual (D1)

Min g = b^TY

St.

A^TY ≤ C^T

Y ≥ 0

Una condición necesaria y suficiente para que X* y Y* sean óptimas respectivamente de (P1)) y de (D1) Y*^T(AX - b) = 0 y X*^T(C^T - A^TY) = 0

INTERPRETACIÓN ECONÓMICA DEL PROBLEMA DUAL

Suponga que una fábrica de cervecería produce dos tipos de cerveza: blanca y negra. Existen tecnologías diferentes para la elaboración de cada tipo de cerveza y de costo diferente. EI precio al por mayor por mil litros de cerveza blanca es $5 000, mientras que por mil litros de cerveza negra es de $3 000.

Un estudio de tiempos y de movimientos ha demostrado que para producir 1 000 litros de cerveza blanca se requiere tres obreros en el proceso de producción y cinco obreros para producir 1 000 litros de cerveza negra. Se supone que la fábrica tiene un total de 15 obreros.

Además para producir 1 000 litros, de cerveza blanca le cuestan al dueño $500, mientras que

1 000 litros de cerveza negra le cuesta $ 200. Su capital no le permite gastar más de $ 1 000 semanal. Hallar el plan de producción que maximice el ingreso semanal de la venta de ambos productos.

Sean X₁ = Número de miles de litros de cerveza blanca a producir por semana

X₂= Número de miles de litros de cerveza negra a producir por semana

Max Z = 5000X₁ + 3000X₂

St.

3X1 + 5X2 ≤ 15 (mano de obra)

500X1 + 200X2 ≤ 1000 (capital disponible)

X_i ≥ 0, i=1,2

El programa primal es un problema que consiste en determinar los niveles le producción que maximicen los beneficios de varios productos de la empresa sujetos a un número de insumos escasos (capacidad) que son limitaciones restrictivas. Los insumos determinan los beneficios de la empresa. El empresario desea determinar que proporción del beneficio de cada uno de sus productos, se debe a cada uno de los insumos. Con este propósito le asignará un valor Y₁, Y₂ a cada uno de los insumos escasos.

Y₁ = puedo describirse como el valor contable que la empresa paga por el trabajo de un obrero

Y₂ = es el valor contable que la empresa paga por cada sol del capital

EI programa dual es:

Min g =15Y₁ +1000Y₂

St.

3Y₁+ 500Y₂ ≥ 5000

5Y₂+ 200Y₂ ≥ 3000

Y_i ≥ 0, i = 1,2

La suma en cada desigualdad es el valor total de los insumos necesarios para producir una unidad (mil litros) de cerveza blanca o negra.

La primera desigualdad en el problema dual significa que el valor de los insumos que entran en la producción de mil litros de cerveza blanca debe ser mayor o igual al beneficio que la empresa hace al producir una unidad (mil litros) de cerveza blanca.

La interpretación de la función objetivo del dual es que minimicemos el costo de los insumos que emplea la compañía.

PROBLEMA DUAL Y VARIABLES DE HOLGURA

Sean los problemas primal y dual siguientes:

Programa primal (P1)

Máx Z = CX

St.

AX ≤ b

X ≥ 0

Programa dual (D1)

Min g = b^TY

St.

A^TY ≥ C^T

Y ≥ 0

La forma estándar de estos programas son:

Máx z = c₁x₁ + c₂ X₂ +...+ C_nX_n

St.

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n + u₁ = b₁

a₂₁x₁ + a₂₂x₂+ .... + a_2nx_n+ u₂ = b₂

………………………………………………………

a_m1x₁ + a_m2x₂ + .....+ a_mnx_n + u_m = b_m

x¡ ≥ 0. i = 1, 2,..., n

ui ≥ 0. i=1, 2,...., m

Min g = b₁y₁ + b₂ Y₂ + ...... + b_my_m

St.

a₁₁y₁ + a₂₁y₂ +....,.+ a_m1Y_m - L₁ = C₁

a₁₂y₁ + a₂₂y₂+........+ a_m2y_m - L₂= c₂

……………………………………………

a_1ny₁ + a_2ny₂ + ......+ a_mny_m – L_n = c_n

y_i≥ 0. i = 1,2,......, m

Li ≥ 0. i = 1,2,....., n

Donde:

aij : mide la cantidad del recurso i que absorbe una unidad del producto j

xj : La producción ( es la cantidad del producto = variable del primal )

ui : La capacidad sin utiliza¡ del insumo i ( variable de holgura del primal )

yi : EI valor (precio contable) del insumo i de la variable dual

Lj : La pérdida contable por unidad del producto j (variables de holgura del dual)

Se tiene:

	Variable primal (cantidades físicas)	Variable dual (en unidades monetarias)
Se refiere a los productos	X_i	L_j
Se refiere a los insumos	u_i	y_i

La interpretación económica es: "El problema dual requiere que encontremos el valor más pequeño del nivel de los insumos de la compañía que contabilizan completamente todos los beneficios de cada uno de los productos"

El significado económico de las variables de holgura del dual L₁, L₂,…, L_n. La pérdida relativa del producto j es: L_j

Li = (a_1jy₁ + a_2jy₂ +......+ a_mjy_m) - c_j

= (valor de los recursos que entran en una unidad del producto j) - (beneficio por unidad del producto j)

Si L_j > 0, entonces los recursos en producir el producto j equivalen más beneficios derivados del bien. Por tanto, es mejor no producir nada. Debe interesar que L_j = 0 o sea que no haya pérdida.

Teorema 7:

En un par de soluciones óptimas, la empresa producirá solo los bienes cuyas cifras sobre perdidas contables sean cero. Además, en éstas soluciones óptimas únicamente los insumos que se han usado a plena capacidad recibirán un valor contable Y diferente de cero. Por otro lado, cualquier par de soluciones factibles a los problemas primal y dual que satisfagan este requisito deben ser óptimas.

Simbólicamente en una solución óptima se tiene;

x_¡L_¡ = 0 para cada bien j

y_iu_i = 0 para cada insumo i

A este conjunto de ecuaciones se le conoce como las condiciones de la holgura complementaria.

Analizando. Si x_¡L_¡ = 0, entonces x_j= 0 o L_j= 0 o ambos

Si x_¡ > 0, entonces L_j = 0, Si la producción del bien j es positivo, entonces la pérdida contable debe ser cero.

Si L_j > 0, entonces x_j = 0. Si la pérdida contable es positiva, entonces no se debe producir el bien j.

PROGRAMA PRIMAL Y DUAL

Comentarios

Acerca de mí