a) Presentación y contextualización

Los temas que se tratan en la presente Unidad, tienen por finalidad que el

estudiante desarrolle y ejecute el análisis post-optimo de los modelos

matemáticos de programación lineal, durante su proceso de formación

profesional y contribuyan en el logro de su perfil profesional.

b) Competencia

Desarrolla y aplica el análisis de sensibilidad de los modelos matemáticos de

programación lineal.

c) Capacidades

1. Planifica y aplica el análisis de sensibilidad de los modelos matemáticos.

2. Planifica y utiliza el análisis de sensibilidad por computadora.

3. Planifica y aplica la solución de modelos de programación entera.

4. Aplica y reconoce los modelos Primal - Dual.

d) Actitudes

Disposición emprendedora.

Respeto a las normas de convivencia.

Sentido de Organización.

Perseverancia en las tareas.

e) Presentación de ideas básicas y contenido esenciales de la Unidad.

La Unidad de Aprendizaje 2: Análisis de Sensibilidad de los modelos de

Programación Lineal, comprende el desarrollo de los siguientes temas:

TEMA 01: Análisis de Sensibilidad de los Términos Independientes en Situación

de Maximización.

TEMA 02: Análisis de la Solución por la Computadora.

TEMA 03: Programación Lineal Entera.

TEMA 04: El Primal - Dual.

Tema 01: Análisis de Sensibilidad de los Términos Independientes en Situación de Maximización

El análisis Post-optimo es también denominado Análisis de Sensibilidad, estudia las variaciones que se presentan en una solución optima en lo referente a los Términos Independientes, la Función Objetivo y la matriz Principal (esta última también denominada Matriz Tecnológica), tanto para los casos de maximización como los de Minimización

a) Análisis de sensibilidad de los términos independientes en situación de maximización

Procedimiento

Paso 1. Se calcula la solución óptima del modelo originalmente dado.

Paso 2. Se calcula el valor del término independiente modificado, mediante:

bi +/ - Δb = b’

Donde: b i = Es el término independiente original de una determinada restricción del modelo matemático. Δb = Es la cantidad en que se incrementa o disminuye el término independiente. b’ = Es el término independiente modificado

Paso 3. Se multiplica la matriz:

B-1 con el vector modificado del término independiente:

B-1 b’ >= [ O ] entonces Es Factible

De lo contrario se dice que no existe factibilidad.

Paso 4. En el supuesto caso de que no exista factibilidad, se identifica a aquel elemento de la matriz B-1 que lo está ocasionando ( la matriz B-1 es aquella que corresponde en el tablero optimo a la posición que ocupaba la matriz unitaria en el tablero Nº 01 del Método Simples), a dicho elemento identificado, se convierte en el Pívot y partir de esto, se efectúa la inversión de matrices para la matriz B-1; y continuamos con el proceso del Paso 4 las veces que sean necesarios, hasta obtener una solución factible, mediante la fórmula dada en el Paso 3.

Paso 5. Una vez que se obtiene la factibilidad a partir del Paso 3 o Paso 4 según el caso, se procede a calcular la solución optima del modelo dado con la variación propuesta del término independiente, mediante la fórmula:

Zmax = Ci ( B-1 b’ )

Y la participación de las variables, reales en dicho modelo modificado se obtiene de: B-1 b’

EJEMPLO

Max Z : 5X1 + 6X2 s.a. 2X1 + 3X2<= 30 3X1 + 2X2 <= 30

Para cuando:

a) Considerar que b1 , pasa a ser 24 b) Considerar que b , pasa a ser b1=36 y b2=18

Balanceando

Max Z : 5X1 + 6X2+ 0X3 + 0X4

s.a. 2X1 + 3X2+ X3= 30

3X1 + 2X2 + X4= 30

Tema 02: Análisis de la Solución por la Computadora

a) Planeación de la producción

Usando el software Lindo tenemos:

b) Análisis

1. Plan óptimo de producción

Q1 = 1300 unidades

Q2 = 0

Q3 = 100 unidades

Q4 = 800 unidades

Q5 = 200 unidades

2. Cuanto es la utilidad máxima

$ 54,400

3. Costos reducidos.

Solo se le interpreta cuando son diferentes de cero.

Costo reducido de Q2 = 11

Tiene dos significados:

Primera interpretación: Se puede notar que el producto Q2 no conviene fabricar,

para que sea conveniente su producción, su utilidad debe aumentar por lo menos 11

$/unidad.

Segunda Interpretación: Se sabe que el producto Q2 no debemos fabricar, si

forzamos la producción de este producto, la utilidad total se reducirá en forma

proporcional a 11, por cada unidad fabricada.

NOTA

Siempre que hay un cero en el lado izquierdo o derecho, si

no hay cero, el problema no tiene solución. Pero cuando

hay varios ceros, significa que hay varias soluciones

óptimas.

4. Slackor Surplus (variables de holgura y exceso).

Variable de Holguras y Variables de exceso

a) Holgura 0 de la fila 2: Toda la materia prima ha sido utilizada, sobrando cero libras.

b) Holgura 300 de la fila 3: Significa que hay 300 pies cúbicos no utilizables del

almacén. Solo se está utilizando 3700 pies cúbicos.

c) Variable de exceso 1900 en la fila 4: Se están entregando 1900 unidades adicionales

a las empresas industriales, lo mínimo que pedían era 200 unidades y estamos

entregando 2100 unidades (exceso de 1900 unidades).

d) Variables de exceso 0 de la fila 5: Se están entregando exactamente lo mínimo

pedido (300 unidades) a las empresas comerciales, no entregamos ninguna unidad

adicional.

e) En la fila 6 y fila 7 por ser restricción de igualdad.

5. Dual Price (Precios Duales).

Se obtiene como sigue:

Unidad de la función del Primal

Yi = --------------------------------------------------------------------

Unidad del término derecho de la i_esima restricción del Primal

$ de utilidad

Y1 = 3 ----------------------------

Libras de materia prima

$ de utilidad

Y2 = 0 ----------------------------

Pie cúbico de espacio

$ de utilidad

Y3 = 0 ----------------------------

Producto comprado por empresas industriales

$ de utilidad

Y4 = -14 ----------------------------

Por producto comprado por las empresas

comerciales

$ de utilidad

Y5 = 14 ----------------------------

Hora Planta 1

$ de utilidad

Y4 = 21 ----------------------------

Hora Planta 2

6. Unidades de las variables duales.

Sea:

bi = termino derecho de la i_esima restricción del primal

Yi = Variable dual asociada a la i_esima restricción del Primal.

M = Valor optimo de la función objetivo del primal.

Si variamos el término derecho (bi) de la i_esima restricción del primal, en un

cantidad di, entonces:

Si di es positivo significa que estamos incrementando.

Si di es negativo significa que estamos disminuyendo.

El nuevo valor óptimo es

M - di * Yi

i) Si aumentamos 50 libra de materia prima. ¿Cuál es

la nueva utilidad?

M + di * Yi

M = 5400

di = 50

Yi = 3

Entonces 5400 + 50(3) = $ 54,550

ii) Si se deterioran 80 libras de materia prima, como afecta esto a la utilidad.

54400 + di * Yi = 54400 + (-80) (3) = $ 54160

En conclusión:

Por cada libra adicional de materia prima, la utilidad aumenta en 3 $, y por cada

libra que se disminuye la materia prima, la utilidad baja 3 $.

7. Rangos de sensibilidad.

i) Rango de sensibilidad para el coeficiente de Q1 en la Función Objetivo

Mientras la utilidad unitaria del producto 1 sea menor o igual que 26, el Plan de

Producción optimo no cambia.

ii) Rango de sensibilidad para la materia prima (Fila2)

Mientras la cantidad disponibles de materia prima este entre 5800 y 6400 libras, los

precios duales no cambian. Van ha seguir siendo 3.

Podemos comprar hasta 400 libras de materia prima o vender hasta 200 libras, sin

alterar su precio dual.

Tema 03: Programación Lineal Entera

La programación entera tiene que ver con la solución de problemas de programación matemática, en las cuales algunas o todas las variables, solo pueden tomar valores enteros no negativos.

a) Tipos de Modelos de Programación Lineal Entera

Programa enteros puros Un modelo entero puro (PLE) es un problema en el que se exige que todas las variables de decisión tengan valores enteros.

Ejemplo: MIN 6X1 + 5X2 + 4X1 S.A. 108X1 + 92X2 + 58X3 >= 576 7X1 + 18X2 + 22X3 >= 83 X1, X2, X3 >= 0 y Enteros

Programas Enteros Mixtos Se llama programación lineal entero mixto (PLEM), cuando un problema solo requiere que algunos variables tengan valores enteros, mientras que las otras pueden asumir cualquier numero no negativo (es decir, cualquier valor continuo).

Por ejemplo: MIN 6X1 + 5X2 + 4X3 S.A. 108X1 + 92X2 + 58X3 >= 576 7X1 - 18X2 + 22X3 >= 83 X1, X2, X3 >= 0 ; X1 y X3 Enteros

Programación Enteros 0 y 1 En algunos problemas, se restringe el valor de las variables a 0 y 1. Dichos problemas se llaman Binarios o Programas Lineales Enteros 0-1. Son de particular interés, debido a que se pueden usar las variables 0-1 para representar decisiones dicotómicas (si o no). Diversos problemas de asignación, ubicación de plantas, planes de producción y elaboración de cartera, son de programación lineal entera 0-1. Por ejemplo:

MIN 5X1 - 7X2 + 10X3 - 3X4 + X5 S.A. -X1 - 3X2 + 5X3 - X4 - 4X5 >= 0 2X1 + 6X2 - 3X3 + 2X4 + 2X5 >= 4 -X2 + 2X3 + X4 - X5 >= 2 XJ = 0 ó 1 donde (0: se rechaza, 1: se acepta)

b) Métodos de Programación Lineal Entera

Método de Búsqueda Se inician partir de la idea directa de enumerar todos los puntos enteros factibles, El método de búsqueda más sobresaliente es la TÉCNICA DE RAMIFICAR Y ACOTAR, Comienza a partir del optimo continuo, pero “parte” sistemáticamente el espacio de soluciones en subproblemas, suprimiendo partes que no contengan puntos enteros factibles.

Ejemplo: MAX X1 + 5X2 S.A. 11X1 + 6X2 <= 66 5X1 + 50X2 <= 225 X1, X2 >= 0 y Enteros

Resolver el problema, por el método gráfico o método simplex

Ramificar y Acotar

VO de P1 <= 3.75 + 5(4.123) = 24.375 = U = MCSA Máxima Cuota Superior Actual

VO de P1 <= 3 + 5(4) = 24 = F = MCIA Mínima Cuota Inferior Actual

Tema 04: El Primal - Dual

El método PRIMAL- DUAL constituye una técnica de solución complementaria en la Programación Lineal, generalmente su aplicación se da en la Teoría de Estrategia ó Teoría de Juegos, en la cual se busca optimizar entre 2 o más estrategas y determinar la probabilidad de éxito de cada caso, así como el valor de la información o el juego según se trate

a) Primal - Dual

Dado un conjunto cualquiera de datos para un modelo de PL (Primal), podemos usar los mismos datos para formar un modelo de PL diferente (Dual). Para examinar la teoría de Dualidad en una forma satisfactoria, tenemos que desechar la restricción de que las variables de un modelo de PL sean no negativas.

Ejemplo (Modelo Primal)

Max 3X1 + 4X2 - 2X3 Var. Duales S.A. 4X1 - 12X2 + 3X3 <= 12 Y1 -2X1 + 3X2 + X3 <= 6 Y2 -5X1 + X2 - 6X3 >= -40 Y3 3X1 + 4X2 -2X3 = 10 Y4 X1>=0 , X2<=0 , X3 NRS

b) Regla

El Núm. de variables del Dual es igual al número de restricciones del Primal. El número de restricciones del Dual es igual al número de variables del Primal. Los coeficientes de la Función Objetivo en el Dual será el vector de recursos del Primal. Si el primal es un modelo de maximización, el Dual será de Minimización. Si el Primal es un modelo de Minimización el Dual será de Maximización.

Los Coeficientes de la 1ra función de restricción del Dual, son los Coeficientes de la 1ro variable en las restricciones de Primal, y en forma análoga para las otras restricciones. Los recursos de las restricciones duales son los Coeficientes de la función objetivo del Primal. El sentido de la i-ésima restricción Dual es = si y solo si la i-ésima variable del Primal no tiene restricción de signo (NRS). Si el Primal es un modelo de Max (Min), entonces, después

de aplicar la regla anterior, se asigna a las restantes restricciones Duales el mismo (opuesto) sentido a la variable correspondiente del Primal. La i-ésima variable del problema DUAL no tendrá restricción de signo(NRS) si y solo si la i-ésima restricción del PRIMAL es una igualdad.

Si el PRIMAL es un modelo de máx. (Min), entonces después de aplicar la regla anterior, asignar a las demás variables DUALES el signo contrario (el mismo signo) que la restricción correspondiente al PRIMAL.

Modelo Dual

Núm. Variables Dual = 4 (Y1, Y2, Y3 y Y4) Núm. Restricciones Dual = 3 Min 12Y1 + 6Y2 - 40Y3 + 10Y4 S.A. 4Y1 - 2Y2 - 5Y3 + 3Y4 >= 3 -12Y1 + 3Y2 + Y3 + 4Y4 <= 4 3Y1 + Y2 - 6Y3 - 2Y4 = -2 Y1>= 0 , Y2>= 0 , Y3 <= 0 , Y4 NRS

d) Ejercicios

1) Hallar el Dual del siguiente Primal

Max 3X1 + 4X2 S.A. -2X1 + 3X2 <= 6 5X1 - X2 <= 40 X1 + X2 <= 7 X1>= 0 , X2>= 0

Dual Núm. Variables (D) = Num. Restricciones (P) = 3 Núm. Restricciones (D) = Núm. Variables (P) = 2 Min 6Y1 + 40Y2 + 7Y3 S.A. -2Y1 + 5Y2 + Y3 >= 3 3Y1 - Y2 + Y3 >= 4 Y1>= 0 , Y2>= 0 , Y3 >= 0

2) Hallar el Dual del siguiente Primal

Min X1 + 12X2 - 2X3 S.A. 4X1 + 2X2 + 12X3 <= 10 2X1 - X2 + 11X3 >= -2 X1<= 0 , X2 NRS , X3>= 0

Dual

Num. Variables (D) = Num. Restricciones (P) = 2 Num. Restricciones (D) = Num. Variables (P) = 3 Max 10Y1 - 2Y2 S.A. 4Y1 + 2Y2 >= 1 2Y1 - Y2 = 12 12Y1 + 11Y2 <= -2 Y1<= 0, Y2>= 0

3) Hallar el Dual del siguiente Primal

Max 4X1 + 7X2 + 8X3 S.A. 4X1 + 2X2 + X3 <= 100 X1 + 3X2 + 7X3 <= 80 2X1 + 6X2 + 3X3 <= 50 X1 NRS, X2 NRS, X3NRS

Dual

Núm. Variables (D) = Núm. Restricciones (P) = 3 Núm. Restricciones (D) = Núm. Variables (P) = 3 Min 100Y1 + 80Y2 + 50Y3 S.A. 4Y1 + Y2 + 2Y3 = 4 2Y1 + 3Y2 + 6Y3 = 7 Y1 + 7Y2 + 3Y3 = 8 Y1>= 0, Y2>= 0, Y3>= 0