• Author / Uploaded
• Willam Alex

• Categories
• Programación lineal
• Investigación de operaciones
• Linealidad
• Programación de computadoras
• Física y matemáticas

Citation preview

PROGRAMACIÓN LINEAL

Un modelo de programación lineal, es un tipo particular de modelo matemático, en el cual las restricciones que involucran las variables son lineales y hay una medida de desempeño o función objetiva lineal que será maximizada o minimizada. Todas las variables de decisión son no negativas. Formular un modelo de programación lineal significa traducir un problema de decisión de negocios en uno de programación lineal, mediante la definición de variables, la especificación de una función objetivo y la expresión de todas las restricciones como igualdades o desigualdades. CARACTERÍSTICAS DE LA PROGRAMACIÓN LINEAL.

1.- Linealidad: Todas as condiciones que se den estarán expresadas en términos de ecuaciones o inecuaciones de primer grado, es decir que el máximo exponente de as variables es 1.

2.- Análisis de las funciones: La linealidad está representada por los signos: igual, menor que, mayor que, menor o igual que, mayor o igual que por tanto: = representa el límite entre dos áreas. > representa el área sobre el límite o sobre la recta, se utiliza para minimización. < representa el área bajo el límite o bajo la recta, se utiliza en maximización. > representa el límite más el área que esta sobre la recta. < representa el límite más el área que esta bajo la recta.

3.- Divisibilidad.- Un proceso de maximización, minimización o combinado puede subdividirse en etapas de tipo sistemático es decir que hay una interdependencia entre elementos, esto significa que si falla un elemento fallará todo el proceso.

4.- Finitud.- Significa que en Investigación Operativa los datos son reales y alcanzables por lo tanto las soluciones también lo serán, finitud da un significado de términos prácticos y de factibilidad real es decir que el número de procesos como los recursos disponibles deberán corresponder a cantidades finitas, esto es conocidas y cuantificadas en forma determinística.

5.- No negatividad.- Al analizar un problema en Investigación Operativa los términos negativos no tienen sentido por tanto solamente se considerarán valores positivos. Si en un proceso aparecen cantidades negativas se considerarán variables auxiliares que durante el proceso tendrán que eliminarse hasta obtener la respuesta en términos reales y positivos.

6.- Algoritmo.- Se refiere a todos los procedimientos que se utilizan en la Investigación operativa y estos pueden ser de tipo mecánico, matemático, práctico, funcional. Ejemplo: Graficación de una condición.

SOLUCIÓN GRÁFICA PARA PROBLEMAS DE PROGRAMACIÓN LINEAL

Las soluciones óptimas de los problemas de programación lineal siempre se encuentran en un vértice de la región básica factible. Pueden existir varias soluciones óptimas, las cuales presentan el mismo número de vértices (o puntos críticos en las líneas que se conectan). ANÁLISIS DE SENSIBILIDAD DE LAS RESTRICCIONES.

Es importante para el gerente entender que tan sensible es la solución ante los cambios en los supuestos y en los factores exógenos. En la programación lineal una de las mejores características es que gran parte de este análisis de sensibilidad procede directamente de la solución; estas afirmaciones se las aplicará de manera gráfica.

PRECIOS SOMBRA.

Un precio sombra o dual representa el valor marginal asociado con el cambio de una unidad en el lado derecho de una restricción.

COSTO REDUCIDO

De manera similar, un costo reducido representa el valor marginal de incluir una unidad en una variable de decisión en la solución. Los costos reducidos pueden considerarse como precios sombra de las restricciones no negativas. Si una restricción no es obligatoria su precio sombra es cero.

EVALUACIÓN DE UN NUEVO PRODUCTO.

El costo de oportunidad para un nuevo producto se calcula como la suma de: (precio sombra) * (unidades requeridas) para todas las restricciones afectadas. Si el costo de oportunidad es menor que la utilidad de una unidad para el nuevo producto, entonces es rentable y por tanto debe incluirse alguna cantidad en la solución óptima. Si el costo de oportunidad es mayor que la utilidad por unidad, entonces no debe fabricarse el producto.

COEFICIENTES DE LA FUNCIÓN OBJETIVO.

Los rangos de los coeficientes del lado derecho y de la función objetivo tienen gran importancia para interpretar la solución de programación lineal. Los rangos del lado derecho determinan los límites dentro de los cuales se mantiene el precio sombra de cada restricción. Los rangos del coeficiente de la función objetivo determinan los límites dentro de los cuales la solución sigue siendo la misma. CASO DE MAXIMIZACIÓN.

Una fábrica produce dos tipos de chaquetas A y B. Las chaquetas tipo requieren 5 minutos para cortarlas y 10 minutos para confeccionarlas, las de tipo 9 requieren de 8 minutos para cortarlas y 8 minutos para confeccionarlas. Se necesita 3 horas y 20 minutos para corte y 4 horas para confección. El beneficio es de $ 50 por cada chaqueta tipo A y $ 60 por cada chaqueta tipo B. Si el objetivo es maximizar la utilidad.

1.- ¿Cuántas unidades del producto A y cuántas del producto B podrían elaborarse para obtener la máxima ganancia?

Paso 1.- Identificación de las variables de decisión:

La fábrica puede manufacturar dos tipos de chaquetas A y B. Estas representan las variables de decisión que las representaremos por:

PRODUCTOS NÚMERO PRODUCIDO Chaquetas tipo A

X1

Chaquetas tipo 9

X2

Paso 2.- Identificar la función objetivo:

Z(MAX) = 5OX1 + 60X2 Paso 3.- Identificar las restricciones de recursos:

RECURSO

UTILIZACIÓN DE

DISPONIBILIDAD

(TIEMPO)

RECURSOS

DE RECURSOS

Corte Confección

5 X1 + 8X2

200

10 X1 + 8 X2

240

X1; X2> O Paso 4.- Realizar la gráfica con todas las restricciones. 5 X1 + 8 X2

10 X1 + 8 X2

Paso 5.- Determinación de los valores de los puntos críticos:

Cálculo del punto B

Para calcular las coordenadas de este punto se forma un sistema de ecuaciones entre la ecuación 1 y 2

5X1 + 8X2 = 200 / (-1)

- 5 X – 8 X2 = -200

1OX1 + 8 X2 = 240 / (1)

10 X + 8 X2 = 240

5X1 = 40 X1 = 40/ 5 X1 =

8

Reemplazo el valor de X1 en la Ecuación 1

5X1 + 8X2 = 200 5(8) + 8x2 = 200 40 + 8X2 = 200 X2 = 16 / 8 X2 = 20

B (8; 20) Los puntos A y C no se los toma en cuenta porque si se tomara uno de esto no se cumpliría con el objetivo de la empresa que es producir los dos productos ya que en estos puntos uno de ellos no se produce.

Paso 6.- Determinar la solución óptima.

Para determinar la solución óptima reemplazamos los valores del punto B en la función objetivo.

Z (MAX) = 50X1 + 60X2

B (8; 20)

Paso 7.- Interpretación de la solución

Z (MAX) = 5O (8) + 60 (20) = 1600

La máxima utilidad se presenta cuando X1 = 8 y X2 = 20 es decir cuando se manufactura 8 chaquetas tipo A y 20 chaquetas tipo B.

2.- El gerente de la fábrica desea saber cual es la máxima utilidad que se puede obtener si el mercado limita a 24 unidades la cantidad que se puede vender del producto B. La formulación del problema ahora se convierte en: Z (MAX) = 5OX1 + 60X2

Sujeta a:

5X1 + 8X2 < 200 1OX1+ 8X20 y X2>0 lo que lleva a considerar que una unidad de la solución cambia una restricción no negativa a X1>1 y X2>1. Los valores para hacerlos se llaman costos reducidos.

Considerando el problema básico la solución óptima tiene X1=8 y X2=20. Ambos valores son positivos y por eso ninguna de las restricciones no negativas es obligatoria (es decir el costo reducido) asociado con cambios es cero al igual que para otras restricciones no obligatorias.

Sin embargo a manera de ejemplo si la función objetivo fuera:

Z (MAX)= 90X1 + 20X2 como aparece en la siguiente figura.

El punto D sería la solución óptima con coordenadas X1=24 y X2=0 que produce una utilidad de 1680 (aquí X2=0); es decir que la restricción X2>O es obligatoria. Ahora si se tuviera que producir por lo menos una unidad del producto B debido a un compromiso con un cliente habitual, la restricción se convertiría en X2>1. Lo que ocasionaría que la solución óptima del problema cambie al punto de coordenadas Xl =23,2 y X2=1 como se muestra en el gráfico siguiente:

Calculo de la utilidad

Z (MAX)= 90X1 + 20X2 Z (MAX)= 90(23,2) + 20(1) = 2108

Con este punto se obtiene una disminución de $ 52 con respecto a la utilidad anterior, por consiguiente en este caso el costo reducido asociado con la restricción no negativa es de $ 52, el costo de mantener la opinión favorable del cliente o goodwill.

9.- Considerar de nuevo la restricción correspondiente al departamento de corte que tiene una disponibilidad de 200 minutos.

El siguiente gráfico muestra lo que sucede cuando se dispone de horas adicionales sin olvidar que en el análisis inicial de los precios sombra se indicó que cada 10 minutos adicionales lleva a una disminución de 2 unidades del producto A y a un aumento de 2,5 unidades del producto B. El precio sombra de cada 10 minutos incrementales fue de $ 50. Con el siguiente gráfico se va ha determinar cual es el aumento permitido en la restricción del departamento de corte. Con 216 minutos disponibles el punto óptimo de la solución tiene coordenadas X1=4,8 y X2=24. Más halla de este punto los minutos adicionales del departamento de corte no tiene efecto ya que la restricción X2>24 ahora es obligatoria. Dadas las otras restricciones del problema 216 minutos en el departamento de corte es lo máximo que se puede utilizar. Por tanto este aumento de 16 minutos para llegar a 216 disponibles representa el límite superior en el rango sobre el cual el precio sombra o dual de $ 50 es válido. Para la restricción correspondiente al departamento de confección se puede hacer el mismo análisis. Lo cual se lo deja para que el lector lo demuestre con la respuesta que se da a continuación.

10.- Suponga que se desea producir alguna cantidad de un tipo de chaqueta nueva (C) y que se requiere para producirla de 1 minuto en el departamento de corte y 2 minutos en el departamento de confección. Este producto es muy rentable y tiene una utilidad de $ 90. Calcule el costo de oportunidad del nuevo producto.

El costo de oportunidad del producto nuevo es:

(Precio sombra en el departamento de corte) * (Minutos requeridos en el departamento de corte) + (Precio sombra en el departamento de confección) * (minutos requeridos en el departamento de confección).

(50 *1) + (25 *2) = 100

Como la utilidad por unidad es solo $ 90 no debe producirse el producto C ya que el costo de oportunidad excede a la utilidad unitaria.

Otro ejemplo: La misma fábrica tiene la opción de elaborar otro producto D el cual puede utilizar 1 minuto en el departamento de corte y 1 minuto en el departamento de confección; el mismo que deja una utilidad de $ 80 dólares. ¿Debe fabricarse el producto?

(50 * 1) + (25 * 1)= 75

Como la utilidad de $ 80 por unidad excede el costo de oportunidad de $ 50 si debe fabricarse alguna cantidad del producto D. Este análisis no dice exactamente cuantas unidades fabricar del producto D, sino solo que debe incluirse en el proceso de producción. El líder debe replantear los datos del problema de programación lineal para incluir una nueva variable de decisión para el producto D y volver a solucionar el problema.

11.- Suponga que la utilidad del producto A se fija en $ 50, pero que el producto B que se espera sea de $ 60, puede cambiar a $ 70, $ 80, $ 90. ¿Que sucederá con la solución óptima del problema; grafique en cada caso? Para un nivel de $ 70 de utilidad la función objetivo es: Z (MAX) = 50X1 + 70X2 y su gráfico el siguiente:

Para un nivel de $ 80 de utilidad la función es: Z (MAX) = 50X1 + 80X2

Para un nivel de $ 90 de utilidad la función objetivo es: Z (MAX) = 50X1 + 90X2.

Si el coeficiente de la utilidad del producto B disminuye a $ 50, $ 40, $30. ¿Que sucedería con el punto óptimo? Para un nivel de $ 50 de utilidad la función objetivo es: Z (MAX) = 50X1 + 70X2

Para un nivel de $ 40 de utilidad a función objetivo es: Z (MAX) = 50X1 + 40X2

Para un nivel de $ 50 de utilidad la función objetivo es: Z (MAX) = 50X1 + 50X2.

I El mismo análisis se puede realizar con el producto A, lo cual el lector deberá realizarlo para fundamentar más sus conocimientos adquiridos en este proceso. RANGOS DEL COEFICIENTE DE LA FUNCIÓN OBJETIVO

SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL EN COMPUTADORA. El procedimiento gráfico utilizado en el capítulo se usa principalmente para visualizar algunas de las propiedades fundamentales de la solución de casos de programación lineal. En al práctica, donde los modelos normales de programación lineal implican miles de variables y de restricciones, la única forma posible de resolver esos modelos es usar computadora.

En esta sección se describen cuatro paquetes de cómputo para resolver casos de programación lineal: TORA, EXCEL SOLVER, AMPL y LINGO. Los programas TORA y EXCEL SOLVER sólo son útiles en la solución de problemas de tamaño moderado. Para los muy grandes, con cientos (o miles) de restricciones y variables, es necesario tener un paquete comercial, como AMPL y LINGO, para resolver la tarea.

SOLUCIÓN DE PROGRAMACIÓN LINEAL CON TORA (MAXIMIZACIÓN)

El ingreso de datos en TORA es directo, y no requiere de instrucciones especiales. Por esta razón, en este capítulo nos concentraremos en la interpretación del resultado de TORA. Esta información se usará para analizar e interpretar las soluciones de algunas aplicaciones seleccionadas en el ámbito de la administración de empresas.

CASOS DE MINIMIZACIÓN

Un agricultor compra fertilizantes que contienen tres nutrientes, A, B, C. Las necesidades mínimas son: 160 unidades de A, 200 de B y 80 de C. En el mercado existen dos marcas populares de fertilizantes 1, con un costo de $ 4 por bolsa con 3 unidades de A, 5 de B y 1 unidad de 0. 2, con un costo de $ 3 por bolsa con dos unidades de cada nutriente. Si el agricultor desea minimizar el costo mientras se mantenga el requerimiento del nutriente. ¿Cuántas bolsas de cada marca debe comprar?

ALGORITMO PARA LA SOLUCIÓN DE CASOS DE MINIMIZACIÓN.

Paso 1.- Identificación de las variables de decisión: El agricultor puede comprar dos tipos de fertilizantes 1 y 2. Estos representan las variables de decisión que las representaremos por: PRODUCTOS

NÚMERO PRODUCIDO

FERTILIZANTE 1

X1

FERTILIZANTE 2

X2

Paso 2.- Identificar la función objetivo:

Z (MIN) = 4X1 + 3X2

Paso 3.- Identificar las restricciones de recursos:

RECURSO

UTILIZACIÓN DE

NECESIDAD

RECURSOS EN

DE RECURSOS

FERTILIZANTES 1

2

Nutriente A

3X1 + 2X2

>

160

Nutriente B

5X1 + 2X2

>

200

Nutriente O

1X1 + 2X2

>

80

X1; X2 < 0 Paso 4.- Realizar la gráfica con todas las restricciones.

Paso 5.- Determinación de los valores de los puntos críticos:

Cálculo del punto B

Para calcular las coordenadas de este punto se forma un sistema de ecuaciones entre la ecuación 1 y 2 3Xi + 2X2

160 / (-1)

5Xi + 2X2

200 / (1)

-3 X1 - 2X2 = -160 5X1 + 2X2 = 200 2X1

= 40 X1 = 40/2

X1 = 20 Reemplazo el valor de X2 en la Ecuación 1

3X1 + 2X2 =160 3(20) + 2X2 = 160 60 + 2X2 = 160 X2 = 100/2 X2 = 50

B (20; 50)

Cálculo del punto C

Para calcular las coordenadas de este punto se forma un sistema de ecuaciones entre la ecuación 1 y 3.

3X1 + 2X2 = 160 / (-1) X1 + 2X2= 80/(1)

-3 X1 - 2X2 = -160 X1 + 2X2 = 2X1

80

=

80

X1 = 80/2

X1 = 40 Reemplazo el valor de X1 en la Ecuación 1

3X1+ 2X2 = 160 3(40) + 2x2 = 160 120 + 2X2 = 160 X2 = 40 / 2 X2 =20

C (40; 20)

Los puntos A y D se distinguen claramente en las intersecciones con los ejes y no necesita de cálculos para identificar sus coordenadas.

A (0; 100)

D (80; 0) 36

Paso 6.- Determinar la solución óptima.

Para determinar la solución óptima reemplazamos los valores del punto A, B, C y del punto D en la función objetivo.

Z (MAX) = 50X1 + 60X2

A (0; 100)

Z (MIN) = 4(0) + 3(100) = 300

B (40; 20)

Z (MIN) = 4(0) + 3(20) = 220 Punto óptimo

C (20; 50)

Z (MIN) = 4(20) + 3(50) = 230

D (80; 0)

Z (MIN) = 4(80) + 3(0) = 320

Paso 7.- Interpretación de la solución

El costo mínimo se presenta cuando X1 = 40 y X2 = 20 es decir cuando el agricultor compra 40 bolsas de 1 y 20 bolsas de 2.

SOLUCIÓN DE PROGRAMACIÓN LINEAL CON TORA (MAXIMIZACIÓN)

CASO COMBINADO

EJERCICIO N° 6

Un taller de calzado confecciona zapatos para hombre y mujer. El producir un par de zapatos de hombre requiere el doble de tiempo que para producir que para producir un par de zapato para mujer. El taller está en capacidad de producir al menos 10 pares de zapatos, en el mercado solo se puede conseguir diariamente la cantidad de cuero y suela solo para nueve pares de zapatos. Los zapatos de mujer requieren de una fibra la cual solo existe para 6 pares de zapatos diariamente, para la confección de zapatos de hombre solamente se puede conseguir diariamente 5 pares de taco de caucho. ¿Qué cantidad de zapatos de hombre y de mujer debe producir diariamente para maximizar el beneficio? Si se sabe que al vender un par de zapatos de hombre se obtiene $ 35 de utilidad y $ 30 por cada par de zapatos de mujer. ALGORITMO PARA LA SOLUCIÓN DE CASOS COMBINADOS.

Paso 1.- Identificación de las variables de decisión:

El taller puede confeccionar dos tipos de calzados para hombre y mujer. Estos representan las variables de decisión que las representaremos por: PRODUCTOS

NÚMERO PRODUCIDO

Calzado para hombre

X1

Calzado para mujer

X2

Paso 2.- Identificar la función objetivo:

Z (MAX) = 35X1 + 30X2

Paso 3.- Identificar las restricciones de recursos: RECURSO

UTILIZACIÓN DE LOS

DISPONIBILIDAD

RECURSOS EN:

DE RECURSOS

CALZADO

CALZADO

HOMBRE

MUJER

PRODUCCIÓN

2X1

+

1X2

>

10

Cuero y suela

1X1

+

1X2