sep inv. operaciones usmp-muy bueno.pdf

CURSO: Investigación de Operaciones Documento de trabajo

Ciclo 2008 1 3

1.1 Formulación de modelos

Modelo formal

En toda organización, siempre hay objetivos que quieren ser maximizados (p.e. las utilidades, la rentabilidad de la inversión, la difusión de los avisos, la satisfacción de los clientes, la productividad de los trabajadores, etc.) o minimizados (p.e. costos de producción, mermas en la materia prima, plazos de entrega de proyectos, etc.). Estos objetivos deben ser logrados mediante decisiones (p.e. cuántos productos fabricar, cuántos trabajadores contratar, cuántas acciones comprar, en qué proyectos invertir, cuántos avisos publicar, etc.). Sin embargo, estas decisiones deben cumplir con determinadas condiciones, ya sea porque los recursos con que cuenta la organización son limitados (p.e. materia prima, máquinas disponibles, área de almacenamiento, presupuesto, etc.) o porque hay determinadas políticas o compromisos que cumplir (p.e. lotes mínimos de producción, compromisos con los proveedores, normas técnicas, acuerdos con el sindicato, etc.). Las situaciones mencionadas generalmente conducen a la formulación de un problema de programación lineal, el cual es un modelo matemático que expresa cuantitativamente el objetivo que se quiere alcanzar (función objetivo) mediante determinadas decisiones que están bajo el control de quien toma la decisión (variables de decisión) y que deben cumplir las condiciones determinadas por la situación analizada (restricciones). Tomemos el siguiente ejemplo para mostrar cómo se formula un problema de programación lineal. Enigma S.A. es una pequeña empresa fabricante de carteras de cuero. Una importante cadena de tiendas por departamentos está interesada en adquirir en los próximos tres meses todas las carteras que pueda producir Enigma S.A. en sus dos tipos, (cartera estándar y cartera de lujo). Un análisis cuidadoso de los requerimientos de fabricación dio como resultado la siguiente tabla en la que se muestra la necesidad de tiempos de producción (en horas) para las tres operaciones de manufactura que requiere cada producto.

Producto Tiempo de producción (horas) Corte Costura Acabado Cartera Estándar 0,5 1,0 0,5 Cartera de Lujo 1,5 0,5 0,5

El departamento de Contabilidad ha determinado que la utilidad por bolsa estándar es de S/. 20 y por bolsa de lujo S/. 15.


Ciclo 2008 1 4

El departamento de Producción estima que para los siguientes tres meses estarán disponibles 750 horas de tiempo para Corte, 600 horas de tiempo para Costura y 350 horas de tiempo para Acabado. También se sabe que el lote mínimo de producción es de 300 unidades, en cualquier combinación de las cantidades de productos. La pregunta es: ¿cuántas carteras de cada tipo debe fabricar la empresa los próximos tres meses, de tal manera que se obtenga la máxima utilidad dentro de los límites capacidad de producción mencionados? Primero se definen las variables de decisión en este caso:

X1: número de carteras estándar a fabricar los próximos tres meses. X2: número de carteras de lujo a fabricar los próximos tres meses.

De acuerdo a la situación planteada, la utilidad total por la producción y venta de las carteras es:

Utilidad total = 20 X1 + 15 X2

La solución óptima es la combinación de producción que maximice la utilidad, el problema es determinar los valores de las variables X1 y X2 que dan el valor más elevado de utilidad.

Max 20 X1 + 15 X2

La producción de las carteras está limitada por la cantidad de horas disponibles. De la tabla sabemos que cada cartera estándar necesita de 0,5 horas de Corte por lo que X1 carteras estándar necesitarán 0,5 X1 horas de Corte. Así también, una cartera de lujo necesita 1,5 horas de Corte por lo que X2 carteras de lujo necesitarán 1,5 X2 horas de Corte. El total de horas utilizadas para producir X1 carteras estándar y X2 carteras de lujo es:

Total de horas utilizadas en la operación de corte = 0,5 X1 + 1,5 X2

En vista que para Corte sólo se dispone de 750 horas, se debe cumplir que:

0,5 X1 + 1,5 X2 ≤ 750 Horas disponibles para Corte Esta desigualdad se conoce como restricción. En general una restricción es una limitación de un recurso a utilizar (≤ ) o un requerimiento mínimo a satisfacer (≥), que puede ser expresada matemáticamente como una desigualdad o igual-dad, y que debe ser cumplida por las variables del modelo.


Ciclo 2008 1 5

De manera similar a la operación de Corte, las limitaciones de horas para las otras operaciones son las siguientes restricciones:

X1 + 0,5 X2 ≤ 600 Horas disponibles para Costura 0,5 X1 + 0,5 X2 ≤ 350 Horas disponibles para Acabado

También hay un lote mínimo a producir, es decir la cantidad de unidades a producir (X1 + X2) debe ser por lo menos 300 unidades, entonces la restricción es:

X1 + X2 ≥ 300 Lote mínimo de producción Además debemos considerar que no pueden producirse un número de carteras negativo, por lo tanto debe cumplirse:

X1 ≥ 0 y X2 ≥ 0 Condiciones de no negatividad Estas restricciones aseguran que la solución no tendrá valores negativos y se les conoce como condiciones o restricciones de no negatividad. En resumen, el modelo formal de programación lineal para el problema plan-teado es el siguiente:

Max 20 X1 + 15 X2 Utilidad en soles Sujeto a:

0,5 X1 + 1,5 X2 ≤ 750 Horas disponibles para Corte X1 + 0,5 X2 ≤ 600 Horas disponibles para Costura 0,5 X1 + 0,5 X2 ≤ 350 Horas disponibles para Acabado X1 + X2 ≥ 300 Lote mínimo de producción X1, X2 ≥ 0 Condiciones de no negatividad

Sobre el modelo formal de programación lineal hay que hacer algunas observaciones: La función objetivo puede ser minimizar. Las restricciones también pueden ser estrictamente de igualdad (=), mayor

que (>) o menor que (<). La función objetivo y todos los lados izquierdos de las restricciones son

funciones lineales de las variables de decisión (las variables tienen exponente 1) y no hay multiplicación ni división entre variables.

Las variables de decisión en las restricciones siempre se colocan en el lado izquierdo de la restricción.

En determinados problemas es posible que unas variables sean positivas, otras negativas e inclusive pueden no tener limitaciones de signo. Entonces, según sea el caso puede que algunas variables no necesiten cumplir con la condición de no negatividad.


Ciclo 2008 1 6

Guías para la formulación de modelos

Como hemos visto, formulación de modelos de programación lineal es el proceso mediante el cual un enunciado verbal se traduce en un enunciado matemático. El modelado de problemas de programación lineal sólo se puede dominar con la práctica y la experiencia. A continuación se dan una guías para la formulación de modelos:

Comprenda el problema en su totalidad. Identifique el enunciado verbal de la función objetivo y de cada una de las

restricciones. Defina las variables de decisión.

Describa la función objetivo en función de las variables de decisión.

Escriba las restricciones en función de las variables de decisión.

Problema 1.1.- Enigma Diet S.A. es una empresa que produce alimentos dietéticos. En la línea de alimentos deshidratados produce dos tipos de alimentos: Fit y Sbelt. Cada tipo de alimento deshidratado se produce mezclando trigo, fruta deshidratada y avena. En la siguiente tabla se presentan los precios de venta de los productos y los precios de compra de los insumos (en nuevos soles) programados para el siguiente mes: Producto Precio de venta

( 1 Kg.) Insumo Precio de compra

(1 Kg.) Máxima cantidad disponible (Kg.)

Fit 14 Trigo 6 10 000 Sbelt 10 Fruta deshidratada 4 5 000

Avena 2 No tiene límite En la programación de la producción del próximo mes, Enigma debe tener en cuenta las siguientes condiciones: El producto Fit debe tener un contenido de por lo menos de 30% de trigo y a

lo más de 50% de fruta deshidratada. El producto Sbelt debe tener por lo menos 45% de trigo y a lo más 40% de

frutas deshidratadas. La transformación de un kilogramo de insumos en producto Fit cuesta $1,2 y

en el caso del producto Sbelt la transformación cuesta $1. Existe un compromiso en realizar una entrega de 6 000 kilogramos del

producto Fit. Dada la gran demanda de productos dietéticos, todos los productos

elaborados por Enigma se venden.


Ciclo 2008 1 7

En el proceso de mezclado de los insumos existe una merma en el peso de 5%, es decir, por cada kilogramo de insumos se obtiene 0,95 kilogramos de producto.

Determine el modelo de programación lineal que maximice las utilidades obtenidas por la producción y venta de los productos Fit y Sbelt. Solución:

X1A: Kilogramos de trigo utilizados en el producto Fit X2A: Kilogramos de fruta deshidratada utilizados en el producto Fit X3A: Kilogramos de avena utilizados en el producto Fit X1B: Kilogramos de trigo utilizados en el producto Sbelt X2B: Kilogramos de fruta deshidratada utilizados en el producto Sbelt X3B: Kilogramos de avena utilizados en el producto Sbelt

Max 14 . 0,95 (X1A + X2A + X3A) + ingreso por venta de producto Fit

10 . 0,95 (X1B + X2B + X3B) – ingreso por venta de producto Sbelt 6 (X1A + X1B) – costo del trigo 4 (X2A + X2B) – costo de fruta deshidratada 3 (X3A + X3B) – costo de avena 1,2 (X1A + X2A + X3A) – costo de mezcla de insumos de Fit 1 (X1B + X2B + X3B) costo de mezcla de insumos de Sbelt

Sujeto a:

X1A ≥ 0,30 (X1A + X2A + X3A) contenido de trigo en Fit X2A ≤ 0,50 (X1A + X2A + X3A) contenido de fruta deshidratada en Fit X1B ≥ 0,45 (X1B + X2B + X3B) contenido de trigo en Sbelt X2B ≤ 0,40 (X1B + X2B + X3B) contenido de fruta deshidratada en Sbelt X1A + X1B ≤ 10 000 disponibilidad de trigo X2A + X2B ≤ 5 000 disponibilidad de fruta deshidratada

0,95 ( X1A + X2A + X3A ) ≥ 6 000 compromiso de entrega de Fit X1, X2 ≥ 0 condiciones de no negatividad

Finalmente, el modelo quedaría: Max 6,1 X1A + 8,1 X2A + 9,1X3A + 2,5 X1B + 4,5 X2B + 5,5 X3B

Sujeto a:

0,70 X1A - 0,30 X2A - 0,30 X3A ≥ 0 0,50 X2A - 0,50 X1A - 0,50 X3A ≤ 0 0,55 X1B - 0,45 X2B - 0,45 X3B ≥ 0 0,60 X2B - 0,40 X1B - 0,40 X3B ≤ 0

X1A + X1B ≤ 10 000 X2A + X2B ≤ 5 000

0,95 X1A + 0,95 X2A + 0,95 X3A ≥ 6 000

X1, X2 ≥ 0


Ciclo 2008 1 8

Solución por método gráfico Solución gráfica

Una vez establecido el modelo de programación lineal, el siguiente paso es resolver el modelo, es decir, encontrar los valores de las variables de decisión que optimizan la función objetivo. Si el modelo tiene dos variables puede ser resuelto gráficamente. Si bien es cierto que los problemas se pueden resolver mediante el uso de programas aplicativos en computadora, tema que desarrollaremos posteriormente, la solución gráfica tiene la bondad de permitirnos comprender conceptos que posteriormente vamos a utilizar en la solución de modelos con más de dos variables pero que por no poderse representar gráficamente sería muy difícil de interpretar. Tomemos el modelo de programación lineal encontrado para la producción de carteras de Enigma S.A., el cual se muestra a continuación.

Max 20 X1 + 15 X2 Utilidad en soles Sujeto a:

0,5 X1 + 1,5 X2 ≤ 750 (1) Horas disponibles para Corte X1 + 0,5 X2 ≤ 600 (2) Horas disponibles para Costura 0,5 X1 + 0,5 X2 ≤ 350 (3) Horas disponibles para Acabado X1 + X2 ≥ 300 (4) Lote mínimo de producción

X1, X2 ≥ 0 Condiciones de no negatividad Mostremos el método gráfico para encontrar los valores de X1 y X2 que maximizan la función objetivo. Región factible: Para facilitar su identificación en el desarrollo del método gráfico se ha numerado cada una de las restricciones. En el método gráfico se utiliza el plano cartesiano y se asigna cada variable a uno de los ejes cartesianos. La asignación es arbitraria, en nuestro caso, X1 se asigna al eje horizontal y X2 al eje vertical. Dado que las variables X1 y X2 en el modelo deben cumplir las condiciones de no negatividad, su representación gráfica se hará en el primer cuadrante, tal como se muestra el siguiente gráfico.


Ciclo 2008 1 9

A continuación se representan las restricciones. Como se puede observar, las restricciones gráficamente corresponden a regiones del plano limitadas por rectas. Para la representación gráfica de la restricción (1) primero se representa la ecuación de la recta:

0,5 X1 + 1,5 X2 = 750

X1

X2

(1)

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

0,5 X1 + 1,5 X2 = 750

X1

X2

(1)

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

X1

X2

(1)

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

0,5 X1 + 1,5 X2 = 750

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

X1 ≥ 0

X2 ≥ 0

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

X1 ≥ 0

X2 ≥ 0


Ciclo 2008 1 10

Luego se establece la región que corresponde a la desigualdad:

0,5 X1 + 1,5 X2 ≤ 750

La región definida por la restricción (1) interceptada con la región definida por las condiciones de no negatividad determina la región indicada en el siguiente gráfico.

X1

X2

(1)

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

0,5 X1 + 1,5 X2 ≤ 750

X1

X2

(1)

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

X1

X2

(1)

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

X1

X2

(1)

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

0,5 X1 + 1,5 X2 ≤ 750

X1

X2

(1)

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

X1

X2

(1)

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200


Ciclo 2008 1 11

El procedimiento seguido para representar la restricción (1) es el mismo para cada una de las otras restricciones. Por ejemplo, si representamos en el plano la restricción (2):

X1 + 0,5 X2 ≤ 600

La región definida por la restricción (2) se intercepta con las establecidas por las restricciones anteriores. La representación gráfica de los puntos que cumplen las restricciones hasta ahora analizadas es como se indica a continuación:

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(2)

X1 + 0,5 X2 ≤ 600

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(2)

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(2)

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(2)

X1 + 0,5 X2 ≤ 600

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(1)

(2)

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(1)

(2)


Ciclo 2008 1 12

Para el caso de la restricción (3)

0,5 X1 + 0,5 X2 ≤ 350

La región de puntos que cumplen las restricciones hasta ahora analizadas es la siguiente:

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(3)

0,5 X1 + 0,5 X2 ≤ 350

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(3)

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(3)

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(3)

0,5 X1 + 0,5 X2 ≤ 350

X1

X2

(1)

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(2)

(3)

X1

X2

(1)

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(2)

(3)


Ciclo 2008 1 13

Finalmente, la restricción (4)

X1 + X2 ≥ 300

Entonces la intersección de todas las regiones determinadas por las restricciones será:

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(4)

X1 + X2 ≥ 300

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(4)

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(4)

X1 + X2 ≥ 300

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(1)

(2)

(3)

(4)

X1

X2

100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500

100

200

300

400

500

600

700

800

900

1000

1100

1200

(1)

(2)

(3)

(4)


Ciclo 2008 1 14

La región de puntos que cumplen simultáneamente todas las restricciones se conoce como región factible y es la que se muestra en el gráfico siguiente. Cada uno de los vértices de región factible se conoce como punto extremo (A, B, C, D, E y F). Cada uno de los puntos que forman parte de la región factible se conoce como solución factible. La solución factible que optimiza (en este caso maximiza) la función objetivo se le conoce como solución óptima.

Solución óptima y valor óptimo: El siguiente paso es encontrar los valores de X1 y X2 que den el máximo valor posible a la función objetivo:

Utilidad total = 20 X1 + 15 X2 Dado un valor de utilidad total en particular, todos los pares de valores X1 y X2 que dan dicho valor de utilidad describen una recta, razón por la cual se le denomina recta isoutilidad. Inicialmente tracemos en el plano algunas rectas que expresen valores arbitrarios de utilidades, por ejemplo:

20 X1 + 15 X2 = 3 000

20 X1 + 15 X2 = 6 000

20 X1 + 15 X2 = 9 000

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

Regiónfactible

A

B

C

D

EF

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

Regiónfactible

A

B

C

D

EF


Ciclo 2008 1 15

El gráfico a continuación muestra la región factible y las rectas de isoutilidad mencionadas. Como se puede apreciar en el caso de la primera recta (20 X1 + 15 X2 = 3 000), ninguno de sus puntos intercepta la región factible y por lo tanto ninguna combinación de X1 y X2 que den utilidad 3000 cumple con todas las restricciones. La segunda recta (20 X1 + 15 X2 = 6 000) sí tiene puntos dentro de la región factible y por lo tanto sí hay valores de X1 y X2 que dan una utilidad de 6000 y que cumplen las restricciones. Al trazar la tercera recta (20 X1 + 15 X2 = 9 000) sucede algo similar a la anterior. Observando el gráfico podemos notar también que a medida que aumentamos el valor de la función objetivo, las rectas de isoutilidad se “desplazan” paralelamente siguiendo la dirección indicada por la flecha. Como nuestro objetivo es maximizar la utilidad, entonces debemos encontrar una recta de isoutilidad lo más “desplazada” en la dirección indicada pero sin salir de la región factible. En el ejemplo, el máximo valor de utilidad se logra cuando la recta de isoutilidad pasa por el vértice D, y por lo tanto el punto D es la solución óptima. Los valores de X1 y X2 del punto D se obtienen del mismo gráfico, o dado que el punto pertenece a las restricciones (2) y (3), se obtienen también resolviendo el siguiente sistema de ecuaciones:

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF20 X

1 + 15 X2 = 9000

20 X1 + 15 X

2 = 6000

20 X1 + 15 X

2 = 3000

Dirección de incremento

de la función objetivo

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF20 X

1 + 15 X2 = 9000

20 X1 + 15 X

2 = 6000

20 X1 + 15 X

2 = 3000

Dirección de incremento

de la función objetivo


Ciclo 2008 1 16

X1 + 0,5 X2 = 600 (restricción 2) 0,5 X1 + 0,5 X2 = 350 (restricción 3) Los valores obtenidos son: X1 = 500 y X2. = 200. Reemplazando estos valores en la función objetivo se obtiene el valor óptimo igual a S/. 13 000. Podemos concluir que si para los próximos 3 meses se produjera 500 carteras estándar y 200 carteras de lujo se obtendría la máxima utilidad posible la cual sería S/. 13 000. Del método gráfico podemos concluir: Las rectas de isoutilidad son paralelas. Por lo tanto, lo importante de trazar

una recta con valor de utilidad arbitraria y la “desplazamos” paralelamente en la dirección conveniente hasta determinar el punto óptimo.

La dirección a la cual se desplazará la recta de la función objetivo (hacia

donde aumenta o disminuye el valor de la función objetivo) se hará dependiendo si el objetivo del problema es de maximizar o minimizar.

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

solución óptima

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

solución óptima


Ciclo 2008 1 17

Debido a que la recta de isoutilidad se desplaza hasta un extremo de la región factible, la solución óptima siempre es un punto extremo o vértice de la región factible.

La solución óptima es el punto de intercepción de dos rectas, los valores

correspondientes a X1 y X2 se determinan gráficamente o resolviendo un sistema de ecuaciones formado por las ecuaciones de las rectas de las restricciones.

Holguras y excedentes: Si reemplazamos los valores de la solución óptima (X1 = 500; X2. = 200) en la primera restricción (0,5 X1 + 1,5 X2 ≤ 750) que corresponde a las horas disponibles para Corte tenemos:

0,5 . 500 + 1,5 . 200 = 550 ≤ 750

550 ≤ 750 Esto no sólo significa que cumple la restricción, también significa que de las 750 horas disponibles para Corte, si se ejecutara el plan de producción óptimo sólo se necesitarían 550 horas. Es decir, quedarían 200 horas “libres”. La diferencia entre el recurso disponible (750) y lo que se utilizaría (550) al ejecutar la solución propuesta se denomina holgura. En este caso la holgura es 200 horas Si reemplazamos los valores de las variables de la solución óptima en la segunda restricción (X1 + 0,5 X2 ≤ 600) que corresponden a las horas disponibles para Costura tenemos:

500 + 0,5 . 200 ≤ 600

600 ≤ 600 Esto significa que de las 600 horas disponibles para Costura, si se ejecutara el plan óptimo de producción se utilizarían las 600 horas, es decir, estamos utilizando todo el recurso disponible. En este caso decimos que la holgura es cero horas. Si reemplazamos los valores de las variables de la solución óptima en la tercera restricción (0,5 X1 + 0,5 X2 ≤ 350) que corresponden a la horas disponibles para Acabado tenemos:

0,5 . 500 + 0,5 . 200 ≤ 350

350 ≤ 350


Ciclo 2008 1 18

Esto significa que de las 350 horas disponibles para Acabado, si se ejecutara el plan óptimo de producción se utilizarían todas las horas disponibles. En este caso, como en la anterior restricción, la holgura es cero. Si reemplazamos los valores de las variables en la solución óptima en la cuarta restricción (X1 + X2 ≥ 300) que corresponde al lote mínimo de producción, tenemos:

500 + 200 ≥ 300 700 ≥ 300

Esto significa que con el plan óptimo de producción, se producirán 400 unidades más de la cantidad mínima requerida. La diferencia entre lo que realmente se está obteniendo al ejecutar la solución propuesta (700) y el requisito mínimo a cumplir (300) se denomina excedente. En este caso se dice que se cumple el requerimiento mínimo de producción con un excedente de 400 unidades. Las holguras se presentan en las restricciones del tipo (≤) y los excedentes se presentan en las restricciones del tipo (≥ ). Las restricciones con holgura o excedente cero se denominan restricciones activas y son las que determinan la solución óptima. Estas restricciones son las más importantes en el modelo de programación lineal. Cuando las restricciones tienen holguras o excedentes mayores a cero se denominan restricciones no activas. Estas restricciones están en un segundo nivel de importancia. También existen algunas restricciones no activas que se denominan restricciones redundantes, es decir, restricciones que no definen la región factible y que perfectamente pudieron no ser consideradas. De todos los tipos de restricciones son las menos importantes. Problema 1.2.- Dado el siguiente problema de programación lineal:

Min 2 X1 + 2 X2 sujeto a:

X1 + 3 X2 ≤ 12 3 X1 + X2 ≥ 12

X1 , X2 ≥ 0 Mediante el método gráfico determine: a. La región factible. b. Los puntos extremos de la región factible c. La solución óptima. d. La región factible y la solución óptima si se agrega la restricción: X1 - X2 = 3.


Ciclo 2008 1 19

X2

X12 4 6 8

2

4

6

8

1 3 5 7 9 10 11 12

1

3

5

7

9

10

11

12

A

BC

X2

X12 4 6 8

2

4

6

8

1 3 5 7 9 10 11 12

1

3

5

7

9

10

11

12

A

BC

Solución: a. La región factible es:

b. Los puntos extremos son:

A: x1 = 3; x2 = 3 B: x1 = 12; x2 = 0 C: x1 = 4; x2 = 0

c. La solución óptima es el vértice C.

X2

X12 4 6 8

2

4

6

8

1 3 5 7 9 10 11 12

1

3

5

7

9

10

11

12

3X1 + x

2 = 12

X1 + 3x2 = 12

Región factible

A

BC

X2

X12 4 6 8

2

4

6

8

1 3 5 7 9 10 11 12

1

3

5

7

9

10

11

12

3X1 + x

2 = 12

X1 + 3x2 = 12

Región factible

X2

X12 4 6 8

2

4

6

8

1 3 5 7 9 10 11 12

1

3

5

7

9

10

11

12

3X1 + x

2 = 12

X1 + 3x2 = 12

Región factible

A

BC


Ciclo 2008 1 20

X2

X12 4 6 8

2

4

6

8

1 3 5 7 9 10 11 12

1

3

5

7

9

10

11

12

D

E

-2

-3

-1

X 1– X 2

= 3

X2

X12 4 6 8

2

4

6

8

1 3 5 7 9 10 11 12

1

3

5

7

9

10

11

12

D

E

-2

-3

-1

X 1– X 2

= 3

d. Dado que la nueva restricción es una igualdad, sólo los puntos del segmento DE que pertenece a la recta forman la región factible.

Los puntos extremos son: D: X1 = 3,75 y X2 = 0,75 E: X1 = 5,25 y X2 = 2,25

La solución óptima es el punto D.


Ciclo 2008 1 21

Casos especiales Soluciones óptimas alternativas: Las soluciones óptimas alternativas se presentan cuando más de una solución nos da el valor óptimo de la función objetivo. Gráficamente se puede ver cuando la línea de la función objetivo coincide con una de las líneas de restricción de recursos. Tomando como referencia el modelo de Enigma S.A. pero esta vez cambiemos la función objetivo es: 15 X1 + 15 X2. Obtengamos gráficamente la solución óptima. Como no han cambiado las restricciones, la región factible tampoco cambia. Al trazar la recta de máxima utilidad, el vértice D (500, 200) sigue siendo solución óptima, pero también el punto C (300, 400). De hecho, cualquier punto sobre el segmento CD es solución óptima. Por lo tanto, si existe más de una solución óptima se dice que el problema tiene soluciones óptimas alternativas. Si reemplazamos el punto C y el punto D en la función objetivo tendremos: Utilidad en el punto D: 15 . 500 + 15 . 200 = 10 500 Utilidad en el punto C: 15 . 300 + 15 . 400 = 10 500

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

línea de utilidad máxima

Puntos de solución óptima

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

línea de utilidad máxima

Puntos de solución óptima


Ciclo 2008 1 22

Región no factible: Una región no factible se presenta cuando no existe solución al problema que satisfaga simultáneamente todas las restricciones Tomando como referencia el modelo de Enigma S.A. obtenga gráficamente la región factible si además agregamos las siguientes restricciones: “se sabe que la producción mínima de las carteras estándar debe ser 600 unidades y de las carteras de lujo 200 unidades”. A la región factible original se le intercepta con la región determinada por las dos nuevas restricciones:

X1 ≥ 600 (5) Lote mínimo de carteras estándar

X2 ≥ 200 (6) Lote mínimo de carteras de lujo

Como se puede apreciar, la intercepción de las regiones es vacía, es decir, ningún punto cumple simultáneamente con todas las restricciones. Se dice entonces que el problema tiene una región no factible y consecuentemente no tiene soluciones factibles ni solución óptima.

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

X1 ≥ 600 y X2 ≥ 200

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

X1 ≥ 600 y X2 ≥ 200

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

X1 ≥ 600 y X2 ≥ 200

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

X1 ≥ 600 y X2 ≥ 200


Ciclo 2008 1 23

Región factible no acotada: Una región factible no acotada se presenta cuando no está limitada en uno de sus lados. Para mostrar el concepto resolvamos el siguiente modelo de programación lineal:

Max 20 X1 - 15 X2 Sujeto a:

X1 ≤ 100 (1) X2 ≥ 200 (2)

X1, X2 ≥ 0 Al trazar las restricciones observamos que la región factible se prolonga indefinidamente hacia la derecha y se dice que es una región factible no acotada. Al tratar de hallar la solución óptima, la rectas de isoutilidad se pueden desplazar en la dirección creciente indefinidamente, por lo que el problema carece de solución óptima. Sin embargo, si la función objetivo hubiese sido de minimización, la solución óptima sí existiría y sería el vértice B En conclusión, puede existir una región factible no acotada y dependiendo de la función objetivo puede o no carecer de solución óptima.

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

X1 ≥ 100 y X2 ≤ 200

En esta dirección elproblema tiene como

solución óptimael vértice B(100,200)

En esta dirección elproblema carece

de solución óptima

A

B

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

X1 ≥ 100 y X2 ≤ 200

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

X1 ≥ 100 y X2 ≤ 200

En esta dirección elproblema tiene como

solución óptimael vértice B(100,200)

En esta dirección elproblema carece

de solución óptima

A

B


Ciclo 2008 1 24

Problema 1.3.- El siguiente problema de programación lineal, ¿qué tipo de soluciones tiene?

Max X1 + X2 sujeto a:

4 X1 + 3 X2 ≥ 12 2 X2 ≥ 4

X1 , X2 ≥ 0 Solución:

La región es no acotada y no existe solución óptima.

X2

X11 2 3 4

1

2

3

4

Región factible

X2

X11 2 3 4

1

2

3

4

Región factible


Ciclo 2008 1 25

Análisis de sensibilidad con gráficos Al encontrar la solución óptima de un problema, las utilidades (o costos) y los lados derecho de consideraron fijos y exactos. Sin embargo estas cantidades pueden ser sólo aproximadas o estar sujetas a variaciones (p.e: si se está negociando el precio de un producto con un cliente). Por lo tanto los valores que se utilizan en el modelo podrían ser sólo referenciales. Lo mismo podría decirse de los lados derechos de las restricciones. Entonces es necesario preguntarse qué pasa con la solución óptima o con el valor óptimo si algunos valores del modelo están sujetos a ciertas variaciones. Justamente el análisis de sensibilidad consiste en determinar las implicancias que tendría variar determinados parámetros dentro del modelo formulado de programación lineal. Concretamente, el análisis de sensibilidad se centra en dos puntos: La variación de los coeficientes de las variables en la función objetivo. La variación de los lados derechos de las restricciones.

Inicialmente se presenta el análisis de sensibilidad para dos variables apoyados en el método gráfico, lo que nos permitirá comprender más fácilmente los criterios utilizados en dicho análisis. Posteriormente extenderemos el análisis de sensibilidad a problemas con más de dos variables mediante en el uso del computador. Cambios en los coeficientes de las variables en la función objetivo: Gráficamente los coeficientes de las variables en la función objetivo determinan la pendiente de las rectas de isoutilidad. Por tanto, si un coeficiente varía, la pendiente de las rectas de isoutilidad varía. La variación de la pendiente de la función objetivo puede ser tal que no necesariamente cambie la solución óptima. Tomemos como referencia la solución gráfica de la producción de carteras de Enigma S.A. La pendiente de la función objetivo (mfo = - 4/3) cambia si uno de los coeficien-tes de las variables cambia. Mientras este valor esté entre la pendiente de la restricción 2 (m2 = -2) y la pendiente de la restricción 3 (m3 = -1), la solución óptima no cambiará, geométricamente seguirá siendo el punto D. Es decir, la solución óptima del problema no cambiará mientras el valor de la pendiente de la función objetivo se encuentre en el rango:

- 2 ≤ m fo ≤ - 1 Si la pendiente de la función objetivo coincide exactamente con –2 ó con –1 habrá soluciones óptimas alternativas. Esto es porque en esos casos la pendiente de la función objetivo coincide con la de un recurso.


Ciclo 2008 1 26

Si la pendiente de la función objetivo excede el rango, la solución óptima cambia, geométricamente ya no es el punto D. Si la recta cambió a más vertical la nueva solución óptima es el punto E. Si la recta cambió a más horizontal, la nueva solución óptima es el punto C. Calculemos ahora cuánto puede variar el coeficiente de una variable en la función objetivo sin que varíe la solución óptima. Volvamos al problema Enigma S.A. y su producción de carteras. La pregunta sería ¿cuál es el rango de variación de la utilidad unitaria de la cartera estándar sin que cambie el plan de producción? La utilidad unitaria actual de la cartera estándar es 20. Reemplacemos dicho valor por uno genérico C1. Entonces la función objetivo será:

Max C1 X1 + 15 X2

La pendiente de la recta es:

15Cm 1

fo −=

Para que la solución óptima no cambie se debe cumplir que:

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

Regiónfactible

solución óptima

restricción 30,5 x1 + 0,5 x2 = 350

m = - 1

restricción 2x1 + 0,5 x2 = 600

m = - 2

función objetivo20 x1 + 15 x2 = 13 000

m = - 4 / 3

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

Regiónfactible

solución óptima

restricción 30,5 x1 + 0,5 x2 = 350

m 3 - 1

restricción 2x1 + 0,5 x2 = 600

m 2 - 2

función objetivo20 x1 + 15 x2 = 13 000

m fo - 4 / 3


Ciclo 2008 1 27

30C15

115C2

1m2

1

1

fo

≤≤

−≤−≤−

−≤≤−

La solución matemática es que mientras el coeficiente de X1 en la función objetivo tenga un valor entre 15 y 30, la solución óptima siempre será X1 = 500 y X2 = 200. La interpretación de la solución matemática es: mientras que la utilidad de la cartera estándar tenga un valor entre 15 y 30 soles, el plan de producción que maximiza la utilidad será producir 500 carteras estándar y 200 carteras de lujo. El mismo análisis se podrá realizar para determinar el rango de variación de la utilidad unitaria de la cartera de lujo. La utilidad unitaria actual de la cartera de lujo es 15. Reemplacemos dicho valor por uno genérico C2. Entonces la función objetivo será

Max 20 X1 + C2 X2

La pendiente de la recta es:

2fo C

20m −=

Para que la solución óptima no cambie se debe cumplir que:

20C01

1C202

1m2

2

2

fo

≤≤

−≤−≤−

−≤≤−

La solución matemática es que mientras el coeficiente de X2 en la función objetivo tenga un valor entre 10 y 20, la solución óptima siempre será X1 = 500 y X2 = 200. La interpretación de la solución matemática es: mientras que la utilidad de la cartera de lujo tenga un valor entre 20 y 40 soles, el plan de producción que maximiza la utilidad será producir 500 carteras estándar y 200 carteras de lujo. Los rangos entre los que pueden variar los coeficientes de las variables en la función objetivo sin que varíe la solución óptima se conocen como rangos de optimalidad .


Ciclo 2008 1 28

Cambios en los lados derechos de las restricciones: Para mostrar el efecto en el cambio del lado derecho de una restricción, volvamos al modelo de programación lineal de Enigma S.A. Tomemos inicialmente una restricción activa, por ejemplo la restricción 2, que es: Restricción 2: X1 + 0,5 X2 ≤ 600 Horas disponibles para Costura Cambiemos el lado derecho de la restricción de 600 horas disponibles a 500 horas disponibles, entonces la restricción 2 quedaría: Restricción 2´: X1 + 0,5 X2 ≤ 500 Horas disponibles para Costura Geométricamente el cambio del lado derecho de un recurso producirá un desplazamiento paralelo de la recta de restricción produciéndose un cambio en la región factible. Además, como la restricción es activa, el punto de solución óptima también cambia, lo cual se aprecia claramente en el siguiente gráfico. Como las horas disponibles para Costura son un recurso limitante (se utiliza la totalidad de dicho recurso y por lo tanto la restricción es activa) un cambio en la cantidad del recurso disponible no solo cambiará la región factible y la solución óptima sino que como en este caso el cambio disminuye un recurso limitante, la región factible disminuye en tamaño (más difícil de cumplir y por lo tanto menos puntos cumplen) y la solución óptima empeora (la solución óptima se debe lograr con menos recursos). Lógicamente si el cambio aumentara la disponibilidad del recurso limitante, la región factible aumentaría en tamaño y la solución óptima mejoraría.

La nueva solución óptima es X1 = 300 y X2 = 400; el valor óptimo es S/. 12 000. Como ya analizamos, la disminución de un recurso limitante disminuye la utilidad.

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

soluciónóptima

restricción 2x1 + 0,5 x2 ≤ 600

función objetivoóptima

regiónfactible

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

soluciónóptima

restricción 2x1 + 0,5 x2 ≤ 600


regiónfactible

D

E

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C D´

F

nuevaregiónfactible

E´

nuevasoluciónóptima

restricción 2´x1 + 0,5 x2 ≤ 500

NuevafunciónObjetivo óptima

D

E

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C D´

F


E´

nuevasoluciónóptima

restricción 2´x1 + 0,5 x2 ≤ 500

NuevafunciónObjetivo óptima


Ciclo 2008 1 29

Ahora centremos nuestro análisis en el cambio del lado derecho de una restricción no activa, por ejemplo la restricción 4 que es:

Restricción 4: X1 + X2 ≥ 300 Lote mínimo de producción Cambiemos el lado derecho de la restricción de un lote mínimo de 300 unidades a 200 unidades, entonces la restricción 4 quedaría: Restricción 4´: X1 + X2 ≥ 200 Lote mínimo de producción El cambio del lado derecho de la restricción se puede apreciar en el siguiente gráfico: Como el lote mínimo de producción no es una condición a cumplir limitante (se excede lo mínimo requerido) un cambio en dicha condición mínima cambiará sólo la región factible pero no la solución óptima. Como en este caso el cambio en la condición mínima disminuye, la región factible aumenta en tamaño (más fácil de cumplir y por lo tanto más puntos cumplen) pero la solución óptima no cambia (la solución óptima cumple largamente lo mínimo requerido). Lógicamente si el cambio aumentara la condición mínima requerida, la región factible disminuiría de tamaño pero la solución óptima no cambiaría necesariamente.

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A´

B

C

D

EF´

soluciónóptima

restricción 4´x1 + x2 ≥ 200



X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A´

B

C

D

EF´

soluciónóptima

restricción 4´x1 + x2 ≥ 200restricción 4´x1 + x2 ≥ 200




X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

soluciónóptima


regiónfactible

restricción 4x1 + x2 ≥ 300

X1

X2

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

A

B

C

D

EF

soluciónóptima



regiónfactible

restricción 4x1 + x2 ≥ 300restricción 4x1 + x2 ≥ 300


Ciclo 2008 1 30

Precio Dual: El Precio dual de una restricción es la mejora del valor óptimo si se agrega una unidad adicional al lado derecho de dicha restricción. Dado que el precio dual de una restricción es la mejora del valor óptimo, esta mejora va a depender si el modelo es de maximizar o minimizar la función objetivo. Si el objetivo es maximizar, entonces la mejora significará un aumento del valor óptimo. Si el objetivo es minimizar, entonces la mejora significará una disminución del valor óptimo. Para ilustrar el cálculo y la interpretación del precio dual, retomemos el ejemplo de la producción de las carteras estándar y de lujo y calculemos el precio dual de la restricción 3. Aumentamos una unidad el lado derecho de dicha restricción y calculemos la nueva solución óptima:

X1 + 0,5 X2 = 600 (restricción 2) 0,5 X1 + 0,5 X2 = 351 (restricción 3) Resolviendo el sistema de ecuaciones obtenemos la nueva solución óptima: X1 = 498 y X2 = 204. Reemplazando estos valores en la función utilidad, nuevo valor óptimo es 13 020. Si compara estos resultados con la solución óptima original (X1 = 500, X2 = 200) y valor óptimo original (13 000) notará un cambio de valores. El aumento en 1 del lado derecho de la restricción 3 ha producido una mejora de 20 en el valor óptimo, es decir, el precio dual de la restricción 3 es 20. La interpretación del precio dual de la restricción 3 es que si aumentamos una hora la capacidad del departamento de Acabado, este aumento generará un incremento de S/. 20 en la utilidad. Costo Reducido: El costo reducido de una variable en el modelo de programación lineal es la cantidad en que debe cambiar el coeficiente de esa variable en la función objetivo para que en la solución óptima dicha variable tenga un valor positivo También se interpreta como el valor que disminuye la función objetivo cuando esta variable cuyo valor óptimo es cero, es forzada a entrar en una unidad. Como en el ejemplo de las carteras, la solución óptima tiene valores de las variables positivas, entonces no es necesario realizar ningún cambio en los coeficientes de las variables en la función objetivo y por lo tanto el costo reducido de ambas variables es cero.


Ciclo 2008 1 31

Sobre el análisis de sensibilidad se podría concluir que: Al cambiar los coeficientes de la función objetivo, ésta puede cambiar su

pendiente. El cambio de la pendiente puede afectar a la solución óptima y al valor óptimo.

El cambio en el valor del lado derecho de una restricción produce un

desplazamiento paralelo de la restricción. Esto puede afectar tanto a la solución óptima como al valor óptimo. El efecto dependerá de qué restricción se haya cambiado y en qué medida.

Estrechar una restricción de desigualdad significa hacerla más difícil de

satisfacer. Para una restricción ≥ esto significa aumentar el lado derecho. Para una restricción ≤ significa disminuirlo.

Relajar una restricción de desigualdad, o bien contrae el conjunto factible o

posiblemente queda inalterado. Al relajar una restricción de desigualdad o bien se expande el conjunto factible o posiblemente quede inalterado.

Al estrechar una restricción de desigualdad, o bien se contrae el conjunto

factible posiblemente quede inalterado. Al relajar una restricción de desigualdad o bien se expande el conjunto factible o posiblemente quede inalterado.

Una restricción es redundante si al ser retirada no cambia la región factible.

Es muy importante considerar que una restricción puede ser redundante para

un conjunto dado, no lo sea cuando se cambian algunos datos. En cualquier modelo de programación lineal, para un conjunto fijo de datos,

las restricciones inactivas pueden ser retiradas sin afectar la solución óptima. Esta depende por completo de las restricciones activas.

Al eliminar las restricciones la región factible queda inalterada o aumenta.

La adición de restricciones hace que la región factible quede inalterada o se

reduzca. La adición de restricciones a un modelo o bien empeora el valor óptimo o lo

deja inalterado. La eliminación de restricciones o bien mejora el valor óptimo o lo deja inalterado.


Ciclo 2008 1 32

Problema 1.4.- Dado el siguiente problema de programación lineal:

Max 100 X1 + 500 X2 sujeto a:

3 X1 + 2 X2 ≥ 600 2 X1 + 4 X2 ≥ 800 X1 , X2 ≥ 0 Encuentre el precio dual y el costo reducido de las variables. Solución:

Conceptos clave:

Variable de decisión: son los valores sobre los cuales se va a tomar decisiones, es decir están bajo el control del decidor. Función objetivo: expresión matemática que resume el objetivo a optimizar por el modelo Restricción: Son los requisitos que debe cumplir los valores de las variables.

X2

X2100 200 300 400

100

200

300

400

X2

X2100 200 300 400

100

200

300

400


Ciclo 2008 1 33

Conceptos clave:

Región factible: Conjunto de soluciones que satisfacen todas las restricciones de manera simultánea. Puntos extremos: Los puntos factibles de la solución que ocurren en los vértices o “esquinas” de la región factible. Solución: cualquier conjunto de valores de las variables Solución factible: una solución que satisface todas las restricciones o limitantes. Solución óptima: una solución que cumpliendo con todas las restricciones, maximiza (o minimiza) la función objetivo. Valor óptimo: valor de la función objetivo en la solución óptima.

Restricción activa: restricción que indica que para el caso de la solución óptima un recurso se está utilizando totalmente (en el caso ≤) o se está cumpliendo una condición con lo mínimo indispensable (en el caso ≥). Restricción no activa: restricción que indica que para el caso de la solución óptima un recurso tiene excedentes (en el caso ≤) o se está cumpliendo una condición con más de lo mínimo indispensable (en el caso ≥). Restricción redundante: restricción que no influye en la región factible y consecuentemente en la solución óptima. Su presencia en el modelo no es necesaria. Holgura: aplicada la solución óptima en una restricción ≤ es la cantidad de recurso no utilizado en dicha restricción. Excedente: aplicada la solución óptima en una restricción ≥ es la cantidad adicional que excede el lado derecho a lo mínimo indispensable requerido por dicha restricción. Solución óptima alternativa: La situación en la cual un programa lineal tiene más de una solución que proporcione el valor óptimo de la función objetivo. Región no factible: Cuando la región factible es vacía, es decir, cuando ningún punto puede cumplir con todas las condiciones o restricciones simultáneamente.

Análisis de sensibilidad: Estudia la forma en que los coeficientes del problema de programación lineal afectan a la solución óptima del problema. Rango de optimalidad: El rango de los valores en el cual puede variar un coeficiente de la función objetivo sin causar ninguna modificación en los valores de las variables de decisión en la solución óptima. Precio Dual: La mejoría en el valor de la solución óptima por incremento unitario en el valor del lado derecho de una restricción. Rango de factibilidad: El rango de valores en el cual puede variar el lado derecho de una restricción y es aplicable el precio dual. Costo reducido: Cantidad en que debe cambiar el coeficiente de esa variable en la función objetivo para que tenga valor positivo para esa variable. También es el valor que disminuye la función objetivo cuando esta variable cuyo valor óptimo es cero, es forzada a entrar en una unidad.


Ciclo 2008 1 34

1.3 Solución por computadora

Uso del LINDO

El método gráfico permite encontrar la solución óptima en modelos con dos variables. Para problemas de más de dos variables existen procedimientos (algoritmos) que permiten encontrar la solución. Sin embargo, gracias al avance de la tecnología, hoy en día podemos acceder a programas aplicativos fáciles de usar y que hacen que los esfuerzos se orienten principalmente al modelado de situaciones cada vez más complejas y al análisis de resultados, dejando el procedimiento de resolución al programa. En el mercado existen programas como el LINDO, el WIN QSB, el Minitab, POM, etc. algunos de ellos con versiones de uso libre. Por su fácil acceso y su uso directo en la resolución de modelos los problemas de la guía han sido resueltos mediante el WINQSB, además el reporte de los resultados es similar al generado por otros programas. Para mayores detalles de la sintaxis y uso de los comandos del WINQSB puede consultar una amplia variedad de libros que existen en la biblioteca y la propia ayuda de programa. En esta parte de la separata nos concentraremos directamente en el ingreso de modelo al programa y a la obtención de resultados. Para ingresar el modelo al programa, simplemente escribimos el modelo formal respetando unas reglas sencillas de sintaxis. Tomemos como ejemplo el modelo de la producción de Enigma S.A. e ingresémoslo en la ventana principal del programa de la siguiente manera:


Ciclo 2008 1 35

Las reglas básicas de sintaxis son: La función objetivo va precedida del término MAX (para maximizar) o MIN

(para minimizar). Las restricciones van precedidas por cualquiera de las siguientes

expresiones:

SUBJECT TO SUCH THAT S.T. ST

El final de las restricciones se indica con la palabra END. Es indistinto ingresar las palabras mencionadas con mayúsculas o

minúsculas. El nombre de las variables debe tener una extensión máxima de 8 caracteres.

El nombre de las variables debe comenzar con un carácter alfabético.

El nombre de las variables no debe utilizar ninguno de los siguientes

caracteres: ! ) + - = < >. Las condiciones de no negatividad no se indican pues el LINDO las asume

por omisión. Para que el reporte presente el modelo que se ha resuelto, active el comando Reports, Formulation, como se indica en la siguiente figura:


Ciclo 2008 1 36

Para que el reporte con la solución del modelo se presente, use el comando Solve o el icono indicado en la siguiente figura.

Al activar el comando Solve (o el icono correspondiente), el programa mostrará una pantalla como es presenta en la siguiente figura. Se debe indicar si se quiere que además de la solución al modelo, el reporte muestre el análisis de sensibilidad.

Icono Solve


Ciclo 2008 1 37

modelo

solución

análisis de sensibilidad

El reporte obtenido por el LINDO es el siguiente: MAX 20 X1 + 15 X2 SUBJECT TO 2) 0.5 X1 + 1.5 X2 <= 750 3) X1 + 0.5 X2 <= 600 4) 0.5 X1 + 0.5 X2 <= 350 5) X1 + X2 >= 300 END OBJECTIVE FUNCTION VALUE 1) 13000.00 VARIABLE VALUE REDUCED COST X1 500.000000 0.000000 X2 200.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 200.000000 0.000000 3) 0.000000 10.000000 4) 0.000000 20.000000 5) 400.000000 0.000000 NO. ITERATIONS= 2 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 20.000000 10.000000 5.000000 X2 15.000000 5.000000 5.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 750.000000 INFINITY 200.000000 3 600.000000 100.000000 100.000000 4 350.000000 40.000000 50.000000 5 300.000000 400.000000 INFINITY

Como se puede apreciar, el reporte presentado consta de tres partes: La primera parte (opcional) es el modelo que se ha resuelto. La segunda parte muestra el valor óptimo, la solución óptima con sus respectivos costos reducidos y las restricciones con sus respectivas holguras o excedentes y precios duales. La tercera parte (opcional) muestra el análisis de sensibilidad de los coeficientes de las variables en la función objetivo (rangos de optimalidad) y los rangos de variación de los lados derechos de las variables en los que son válidos los precios duales antes mostrados.


Ciclo 2008 1 38

Interpretación de reportes de LINDO

En el reporte se ha incluido el modelo de programación resuelto. Si bien esta inclusión es opcional, es recomendable incluirla para que se tenga a la mano el modelo resuelto. MAX 20 X1 + 15 X2 SUBJECT TO 2) 0.5 X1 + 1.5 X2 <= 750 3) X1 + 0.5 X2 <= 600 4) 0.5 X1 + 0.5 X2 <= 350 5) X1 + X2 >= 300 END Note que el programa ha numerado las restricciones pero que esta numeración empieza en 2). Esto es porque la numeración la realiza por filas y la fila 1) es la correspondiente a la función objetivo. Esta numeración de las filas, que sirve para identificar las restricciones, es mantenida a lo largo del reporte. La parte siguiente del reporte:

OBJECTIVE FUNCTION VALUE 1) 13000.00

Corresponde al valor óptimo del modelo. Como ya lo habíamos mencionado, la numeración 1) corresponde a la función objetivo. En este caso, el ingreso máximo es S/. 13 000. La siguiente parte del reporte:

VARIABLE VALUE REDUCED COST X1 500.000000 0.000000 X2 200.000000 0.000000

Muestra el valor de cada variable en la solución óptima. Coincidiendo con la solución obtenida mediante el método gráfico, la solución óptima (el plan óptimo de producción) es fabricar 500 unidades de carteras estándar y 200 unidades de carteras de lujo. También se muestra el costo reducido de cada variable que en este caso es cero. La siguiente parte de reporte muestra las filas numeradas que corresponden a las restricciones, sus correspondientes holguras/excedentes y sus precios duales.

ROW SLACK OR SURPLUS DUAL PRICES 2) 200.000000 0.000000 3) 0.000000 10.000000 4) 0.000000 20.000000 5) 400.000000 0.000000

Para la fila 2), que corresponde a una disponibilidad de 750 horas para Corte, se tiene una holgura de 200 horas, por tanto es una restricción no activa, Para la fila 3) que corresponde a una disponibilidad de 600 horas para Costura, la holgura es cero y por lo tanto es una restricción activa. Para la fila 4) que corresponde a 350


Ciclo 2008 1 39

horas de Acabado, también la holgura es cero y por lo tanto, también es una restricción activa. La fila 5) corresponde al lote mínimo de producción y el excedente es 400 unidades y por lo tanto es una restricción no activa. Como se puede apreciar, los resultados coinciden con la solución gráfica. Respecto a los precios duales, para la fila 2) si aumenta en una unidad el lado derecho de la restricción la utilidad no cambia porque el precio dual es cero. Es decir, si a las 750 horas con que se cuenta para Corte le agregamos una hora, la utilidad no cambia. Esto es lógico porque si para la solución óptima y el valor óptimo hay horas sobrantes de Corte, agregar una hora más no mejora la solución óptima ni el valor óptimo. Para la fila 3), si aumentamos una hora adicional a las 600 ya disponibles, la utilidad aumenta en un monto equivalente al precio dual es decir $10. Para la fila 4), si aumentamos una hora adicional a las 350 ya disponibles, la utilidad aumenta en un monto equivalente al precio dual es decir $20. Este resultado confirma el que obtuviéramos en el análisis que hiciéramos en la solución gráfica (ver página 26) Para la fila 5), si exigimos una unidad adicional a las 300 del lote mínimo, la utilidad no varía (el precio dual es cero) dado que se han producido 400 unidades más de las mínimas exigidas. La siguiente parte del reporte muestra los coeficientes de las variables en la función objetivo, en este caso las utilidades unitarias. OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 20.000000 10.000000 5.000000 X2 15.000000 5.000000 5.000000 La utilidad actual de la cartera estándar es $20 y puede aumentar hasta en $10 ó puede reducirse hasta en $5 y la solución óptima no variará, es decir, mientras la utilidad unitaria de la cartera estándar tenga un valor entre $15 y $30 (rango de optimalidad) el plan óptimo de producción será X1 = 500; X2. = 200. Note que si bien la solución óptima no varía, el valor óptimo sí. Un análisis similar se cumple para la utilidad unitaria de la cartera de lujo, la utilidad actual es $15 y puede aumentar como máximo hasta $5 y disminuir como máximo hasta $5 sin que la solución óptima cambie. La última parte del reporte se refiere al lado derecho de las restricciones y los rangos de variación en los que es válido el valor del precio dual.

RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 750.000000 INFINITY 200.000000 3 600.000000 100.000000 100.000000 4 350.000000 40.000000 50.000000 5 300.000000 400.000000 INFINITY


Ciclo 2008 1 40

1.4 Aplicaciones especiales Problema de transporte

El problema de transporte se presenta frecuentemente al planear la distribución de bienes y servicios desde varias localizaciones de suministro hacia varias localizaciones de demanda. Características del modelo: La cantidad de bienes disponibles en cada localización de suministro

(origen) es limitada. La cantidad de bienes necesarios en cada una de las localizaciones de

demanda (destino) es conocida. El objetivo generalmente es minimizar costos de traslado de los bienes desde

los orígenes hasta los destinos.

Para mostrar el modelo que resuelve el problema de transporte tomemos la siguiente situación: Enigma S.A. tiene cuatro centros de distribución de productos marinos en Lima y están ubicadas en Ate, Barranco, Comas y Magdalena. Los productos que distribuye los acopia de los terminales pesqueros de Ventanilla, San Juan de Miraflores y La Victoria. La demanda diaria solicitada por cada centro de distribución (en Kg.) son los siguientes:

Centro de distribución Cantidad (Kg.)

Ate 400 Barranco 900 Comas 200 Magdalena 500

La cantidad de productos marinos que puede disponer cada terminal pesquero es la mostrada en la siguiente tabla:

Terminal Pesquero Cantidad (Kg.) Ventanilla 500 San Juan de Miraflores 700 La Victoria 800

El costo por transporte de cada kilogramo de producto marino desde uno de los terminales pesqueros a un centro de distribución (en soles) es el siguiente:

Terminal Pesquero Centro de distribución

Ate Barranco Comas Magdalena Ventanilla 1,20 1,30 0,40 0,60 San Juan de Miraflores 0,50 0,40 1,00 1,10 La Victoria 1,00 0,90 1,20 0,40

Se debe decidir cuántos kilogramos debe destinar de cada terminal pesquero a cada centro de distribución de manera que se minimice el costo de transporte.


Ciclo 2008 1 41

Diagrama de red: El diagrama de red muestra los centros de suministro y los de destinos y están representados por círculos conectados con una línea que indica la ruta. Al lado de cada círculo se indica la cantidad de bienes suministrados y demandados sobre las líneas se indican los costos unitarios respectivos.

Variables: Xij: número de unidades embarcadas del suministro i al destino j Modelo:

Min 1,2 X11 + 1,3 X12 + 0,4 X13 + 0,6 X14 + 0,5 X21 + 0,4 X22 + x23 + 1,1 X14 + X31 + 0,9 X32 + 1,2 X33 + 0,4 X34

sujeto a : X11 + X12 + X13 + X14 ≤ 500 (suministro de Ventanilla) X21 + X22 + X23 + X14 ≤ 700 (suministro de San Juan de Miraflores) X31 + X32 + X33 + X34 ≤ 800 (suministro de La Victoria) X11 + X21 + X31 = 400 (demanda de Ate) X12 + X22 + X32 = 900 (demanda de Barranco) X13 + X23 + X33 = 200 (demanda de Comas) X14 + X14 + X34 = 500 (demanda de Magdalena)

Xij ≥ 0 para i = 1, 2, 3; j = 1, 2, 3, 4

2San Juan deMiraflores

1Ventanilla

3

La Victoria

1Ate

2Barranco

3Comas

4Magdalena

400

900

200

500

500

700

800

1,2

1,3

0,40,6

0,50,4

1,0

1,1

1,00,9

1,2

0,4

Suministros Rutas de distribución(arcos)

Demandas

Plantas(nodos de origen)

Centros de distribución(nodos de destino)

Costo unitariode transporte


1Ventanilla

3

La Victoria

1Ate

2Barranco

3Comas

4Magdalena

400

900

200

500

500

700

800

1,2

1,3

0,40,6

0,50,4

1,0

1,1

1,00,9

1,2

0,4


1Ventanilla

3

La Victoria

1Ate

2Barranco

3Comas

4Magdalena

400

900

200

500

500

700

800

1,2

1,3

0,40,6

0,50,4

1,0

1,1

1,00,9

1,2

0,4


Demandas

Plantas(nodos de origen)

Centros de distribución(nodos de destino)



Ciclo 2008 1 42

Resolviendo el problema usando el programa LINDO se tiene el siguiente reporte:

OBJECTIVE FUNCTION VALUE 1) 1200.000 VARIABLE VALUE REDUCED COST X11 0.000000 0.000000 X12 0.000000 0.200000 X13 200.000000 0.000000 X14 300.000000 0.000000 X21 0.000000 0.100000 X22 700.000000 0.000000 X23 0.000000 1.300000 X24 0.000000 1.200000 X31 400.000000 0.000000 X32 200.000000 0.000000 X33 0.000000 1.000000 X34 200.000000 0.000000 De acuerdo al reporte la solución es: X13: 200 Kg. transportados de Ventanilla a Comas X14: 300 Kg. transportados de Ventanilla a Magdalena X22: 700 Kg. transportados de San Juan de Miraflores a Barranco X31: 400 Kg. transportados de La Victoria a Ate X32: 200 Kg. transportados de La Victoria a Barranco X34: 200 Kg. transportados de La Victoria a Magdalena El costo total del transporte propuesto es de S/. 1200 Diagrama de red con la solución:

2San Juan de

Miraflores

1Ventanilla

3

La Victoria

1Ate

2Barranco

3Comas

4Magdalena

400

900

200

500

500

700

800

200300

700

400200

200

Unidadestransportadas

2San Juan de

Miraflores

1Ventanilla

3

La Victoria

1Ate

2Barranco

3Comas

4Magdalena

400

900

200

500

500

700

800

200300

700

400200

200

Unidadestransportadas


Ciclo 2008 1 43

Variantes del modelo:

Oferta o suministro total es mayor a la demanda total. Oferta o suministro total es menor a la demanda total. Maximización e la función objetivo. Rutas con capacidad limitada. Rutas no aceptables.

Problema de asignación

El problema de asignación consiste en asignar un elemento (persona, máquina, contrato, etc.) a un destino (territorio, trabajo, limitante, etc.) Características del modelo:

El número de elementos y el número de destinos son iguales. Un elemento es asignado a un solo destino. El objetivo es minimizar costos. Todas las asignaciones son posibles. Es un caso especial del problema de transporte donde Xij es igual a 1 si el

elemento i es asignado al destino j y 0 si no es asignado. Para mostrar el modelo de resolución del problema de asignación tomemos el siguiente ejemplo: La gerencia de Enigma S.A. quiere asignar a tres ejecutivos para que visiten e inspeccionen las tres plantas con que cuenta la empresa en provincias. Los costos de asignación (en soles) de cada ejecutivo a cada planta son mostrados en el siguiente cuadro:

Ejecutivo Planta

Tacna Huánuco Cusco Finanzas 24 10 21 Mercadeo 14 22 10 Operaciones 15 17 20

Encuentre la solución óptima de asignación de los ejecutivos a cada planta de Enigma S.A. de tal manera que se minimice el costo. Diagrama de red: De una manera similar al caso de transporte, el diagrama de red en el problema de asignación muestra las unidades a asignar y los de destinos y están representados por círculos conectados con una línea que indica la asignación. Al lado de cada círculo se indica 1 que es la única asignación del modelo y sobre las líneas se indican los respectivos costos de la asignación.


Ciclo 2008 1 44

Variables:

⎩⎨⎧

=casoelesesernode0

jclientealasignaseiejecutivoelsi1ijX

donde: i = 1, 2, 3 y j = 1, 2, 3 Modelo: Min 24 X11 + 10 X12 + 21 X13 + 14 X21 + 22 X22 + 10 X23 + 15 X31 + 17 X32 + 20 X33

Sujeto a:

X11 + X12 + X13 ≤ 1 (Asignación de ejecutivo de Finanzas) X21 + X22 + X23 ≤ 1 (Asignación de ejecutivo de Mercadeo) X31 + X32 + X33 ≤ 1 (Asignación de ejecutivo de Operaciones) X11 + X21 + X31 = 1 (Cliente 1) X12 + X22 + X32 = 1 (Cliente 2) X13 + X23 + X33 = 1 (Cliente 3) Xij ≥ 0 para i = 1, 2, 3; j = 1, 2, 3

Resolviendo el problema usando el programa LINDO tenemos:

2Mercadeo

1Finanzas

3Operaciones

Tacna1

Huánuco2

Cusco3

1

1

1

1

1

1

24

10

21

14

22

10

1517

20

Ofertas Asignaciones posibles(arcos)

Demandas

Ejecutivos(nodos de origen)

Clientes(nodos de destino)

Costo de asignación

2Mercadeo

1Finanzas

3Operaciones

Tacna1

Huánuco2

Cusco3

1

1

1

1

1

1

24

10

21

14

22

10

1517

20

2Mercadeo

1Finanzas

3Operaciones

Tacna1

Huánuco2

Cusco3

1

1

1

1

1

1

24

10

21

14

22

10

1517

20

Ofertas Asignaciones posibles(arcos)

Demandas

Ejecutivos(nodos de origen)

Clientes(nodos de destino)

Costo de asignación


Ciclo 2008 1 45


VARIABLE VALUE REDUCED COST X11 0.00 9.00 X12 1.00 0.00 X13 0.00 10.00 X21 0.00 0.00 X22 0.00 13.00 X23 1.00 0.00 X31 1.00 0.00 X32 0.00 7.00 X33 0.00 9.00 Los resultados se interpretan de la siguiente manera: Ejecutivo de Finanzas asignado a Huánuco (X12 = 1) Ejecutivo de Mercadeo asignado a Cusco (X23 = 1) Ejecutivo de Operaciones asignado a Tacna (X31 = 1)

El costo total de asignar los ejecutivos a las diferentes plantas es de S/. 35. Diagrama de red con la solución:

Variantes del modelo:

Número de elementos que se van a asignar es mayor al número de destinos. Número de elementos que se van a asignar es menor al número de destinos. Hay un problema de maximización. Se dan asignaciones inaceptables. Un elemento puede ser asignado a más de un destino.

2Mercadeo

1Finanzas

3Operaciones

Tacna1

Huánuco2

Cusco3

1

1

1

1

1

1

1

1

1

2Mercadeo

1Finanzas

3Operaciones

Tacna1

Huánuco2

Cusco3

1

1

1

1

1

1

1

1

1


Ciclo 2008 1 46

Problema de trasbordo

El problema de trasbordo es una extensión del modelo de transporte, al cual se agregan nodos intermedios denominados nodos de trasbordo. Características del modelo: La oferta disponible es limitada. En cada destino, la demanda está especificada. El objetivo generalmente es minimizar costos de traslado de los bienes desde

los orígenes hasta los destinos.

Para mostrar el problema de trasbordo, desarrollemos el siguiente ejemplo: Enigma S.A. tiene plantas de producción en Lima y Tacna. Los productos fabricados en cualquiera de estas instalaciones pueden ser enviados a cualquiera de sus almacenes regionales en Ica y Arequipa. De los almacenes regionales, la empresa distribuye a detallistas al menudeo en Ayacucho, Huancayo, Cusco y Huánuco. En las siguientes tablas aparece el costo unitario de transporte de cada ruta de distribución.

Planta Almacén Cantidad ofrecida

Ica Arequipa Lima 2 3 600

Tacna 3 1 400

Almacén Distribuidor al detalle Ayacucho Huancayo Cusco Huánuco

Ica 2 6 3 6 Arequipa 4 4 6 5 Cantidad demandada 200 150 350 300

Se debe determinar cuántos productos deben ser trasladados por cada rut propuesta de tal manera que se cumpla con la cantidad demandada por cada distribuidor al menor costo posible. Diagrama de red:

Como es un caso de transporte, el diagrama de red en el problema de trasbordo muestra las unidades a transportar. Los lugares de origen trasbordo y los de destinos están representados por círculos conectados con una línea que indica la ruta. Al lado de cada círculo de origen y destino se indica la cantidad de unidades ofrecidas y demandadas sobre las líneas se indican los respectivos costos de la transporte. La numeración de los nodos se hace de manera consecutiva dado que los nodos de trasbordo son tanto origen como destino de rutas.


Ciclo 2008 1 47

Variables: Xij: número de unidades transportadas del suministro i al destino j

Modelo:

Min 2 X13 + 3 X14 + 3 X23 + 1 X24 + 2 X35 + 6 X36 + 3 X37 + 6 X38 + 4 X45 + 4 X46 + 6 X47 + 5 X48

Sujeto a: X13 + X14 ≤ 600 (suministro de Lima)

X23 + X24 ≤ 400 (suministro de Tacna) - X13 - X23 + X35 + X36 + X37 + X38 = 0 (transbordo en Ica) - X14 - X24 + X45 + X46 + X47 + X48 = 0 (transbordo en Arequipa) X35 + X45 = 200 (demanda de Ayacucho) X36 + X46 = 150 (demanda de Huancayo) X37 + X47 = 350 (demanda de Cusco) X38 + X48 = 300 (demanda de Huanuco) Xij ≥ 0 para todos los i, j

Resolviendo el problema usando el programa LINDO tenemos:

Distribuidores al menudeo(nodos destino)

1Lima

3Ica

4Arequipa

5Ayacucho

6Huancayo

7Cusco

8Huánuco

200

150

350

300

600

2

6

36

44

6

5

2Tacna400

2

3

3

1


Demanda

Plantas(nodos origen)

Almacenes(nodos tranbordo)


Distribuidores al menudeo(nodos destino)

1Lima

3Ica

4Arequipa

5Ayacucho

6Huancayo

7Cusco

8Huánuco

200

150

350

300

600

2

6

36

44

6

5

2Tacna400

2

3

3

1


Demanda

Plantas(nodos origen)

Almacenes(nodos tranbordo)



Ciclo 2008 1 48

OBJECTIVE FUNCTION VALUE

1) 5200.000

VARIABLE VALUE REDUCED COST X13 550.00 0.00 X14 50.00 0.00 X23 0.00 3.00 X24 400.00 0.00 X35 200.00 0.00 X36 0.00 1.00 X37 350.00 0.00 X38 0.00 0.00 X45 0.00 3.00 X46 150.00 0.00 X47 0.00 4.00 X48 300.00 0.00 Los valores de las variables representan la cantidad de productos que serán transportados siguiendo la respectiva ruta. X13: 550 unidades transportadas de Lima a Ica X14: 50 unidades transportadas de Lima a Arequipa X24: 400 unidades transportadas de Tacna a Arequipa X35: 200 unidades transportadas de Ica a Ayacucho X37: 350 unidades transportadas de Ica a Cusco X46: 150 unidades transportadas de Arequipa a Huancayo X48: 300 unidades transportadas de Arequipa a Huánuco El costo total de la operación es de S/. 5 200 Diagrama de red con la solución:

1Lima

3Ica

4Arequipa

5Ayacucho

6Huancayo

7Cusco

8Huánuco

200

150

350

300

600

200

350

150

300

2Tacna400

550

50

400

1Lima

3Ica

4Arequipa

5Ayacucho

6Huancayo

7Cusco

8Huánuco

200

150

350

300

600

200

350

150

300

2Tacna400

550

50

400


Ciclo 2008 1 49

Variantes del modelo: Oferta o suministro total es mayor a la demanda total. Oferta o suministro total es menor a la demanda total. Maximización de la función objetivo. Rutas directas a destinos finales. Rutas entre destinos finales. Rutas entre puntos de trasbordo. Rutas con capacidad limitada. Rutas no aceptables.

1.5 Problemas de programación lineal Problemas de formulación de modelos

1. Enigma S.A. fabrica y vende dos productos. Dicha compañía obtiene una

ganancia de S/. 12 por cada unidad que vende del producto 1 y de S/. 4 por cada unidad del producto 2. Los requerimientos en términos de horas de trabajo para la fabricación de estos productos en los tres departamentos de producción se muestran de manera resumida en la siguiente tabla:

Departamento Producto 1 Producto 2

A 1 2 B 1 3 C 2 3

Los supervisores de estos departamentos han estimado que tendrán las siguientes disponibilidades de horas de trabajo durante el próximo mes: 800 horas en el departamento A, 600 horas en el departamento B y 2 000 horas en el departamento C. Además, las condiciones particulares del mercado de los productos indican que todo los productos que se fabrique serán vendidos. Si la compañía está interesada en maximizar las ganancias y suponiendo que todo lo producido se venderá, desarrolle el modelo de programación lineal correspondiente.

2. La firma Análisis Financiero S.A. es una empresa de inversiones que maneja las

carteras de acciones para diversos clientes. Un cliente nuevo acaba de solicitarle que maneje una cartera de US$ 80 000. El cliente desea, como estrategia inicial de inversión, restringir la cartera a una combinación de las tres acciones cuyas características principales se muestran en la siguiente tabla:


Ciclo 2008 1 50

Acción Precio

por acción (US$)

Rendimiento anual estimado por acción

(US$)

Inversión máxima posible

Blue chip 50 6 50 000 Best 30 4 45 000 Regular 35 5 30 000

Formule un modelo de programación lineal para el problema de inversión si el cliente desea maximizar el rendimiento anual total.

3. La Cámara de Comercio patrocina periódicamente programas educativos. En estos momentos se están elaborando los planes promocionales para los programas del presente año. Las alternativas de publicidad incluyen anuncios en televisión, radio y periódicos. A continuación se muestran las estimaciones de audiencia, los costos y las limitaciones sobre el uso máximo de los medios son:

Medio Televisión Radio Periódico

Audiencia por anuncio 100 000 18 000 40 000 Costo por anuncio (en nuevos soles) 2 000 300 600 Uso máximo del medio (números de avisos) 10 20 10

Para asegurar una utilización equilibrada de los medios publicitarios, los anuncios por radio no deben rebasar el 50% del número total de anuncios que se autoricen. Además, se requiere que el número de avisos en televisión constituya cuando menos el 10% del número total de anuncios autorizados. Si el presupuesto disponible para el año es de S/. 20 000, presente un modelo de programación lineal que maximice la audiencia obtenida por los avisos en los medios.

4. Cannes S. A. proporciona alojamiento por una noche para mascotas. Una característica particular en Cannes S. A. es la calidad del cuidado que reciben las mascotas, incluyendo una excelente alimentación. La comida para perros de la perrera se elabora mezclando dos alimentos de marca para perros a fin de obtener lo que la perrera identifica como una “dieta para perros balanceada”: Los datos para las dos comidas para perros son las siguientes:

Comida para perros Costo por onza Proteínas (%) Grasa (%)

Guau 0,06 30 15 Sniff 0,05 20 30

El gerente desea asegurarse de que los perros reciben por lo menos 5 onzas de proteínas y como mínimo 3 onzas de grasas cada día y quiere hacerlo al menor costo. De acuerdo a lo planteado formule el modelo de programación lineal.


Ciclo 2008 1 51

5. Sport S.A. fabrica raquetas desde tamaño normal y grande. Las raquetas de la empresa son extremadamente ligeras debido al uso de una aleación especial de magnesio y grafito. Cada raqueta de tamaño normal utiliza 0,125 Kg. de aleación especial y cada

raqueta grande utiliza 0,4 Kg. de aleación especial. Para el siguiente periodo de producción de dos semanas sólo hay disponible

80 Kg. de aleación especial. Cada raqueta de tamaño normal ocupa 10 minutos de tiempo de fabricación

y cada raqueta tamaño grande utiliza 12 minutos. Las contribuciones a la utilidad son de $10 por cada raqueta normal y $15

por cada raqueta grande y están disponibles 40 horas de tiempo de producción por semana.

La administración ha especificado que por lo menos 20% de la producción total debe ser de la raqueta de tamaño estándar.

Suponiendo que debido a la naturaleza única de los productos, la empresa venderá todas las raquetas que puede producir, se pide que desarrolle el modelo de programación lineal que maximice la contribución a la utilidad las dos siguientes semanas.

6. Aerolíneas S.A. está considerando la posibilidad de adquirir aviones comerciales en el mercado mundial a USA, Inglaterra o Rusia. El costo del avión USA es de US$ 6,7 millones, el avión de Inglaterra es de US$ 5 millones y el avión de Rusia de US$ 3, 5 millones. El directorio de dicha empresa ha autorizado la compra de aviones por un valor máximo de US$ 150 millones. Los economistas de Aerolíneas S.A. han calculado que el avión de USA proporcionará una utilidad neta de US$ 420 000 anuales, el avión de Inglaterra proporcionará una utilidad neta de US$ 300 000 y el avión de Rusia una utilidad de US$ 230 000. Por otro lado se conoce que se dispone sólo de 30 pilotos debidamente entrenados para pilotear dichos aviones. Si sólo se adquiriesen los aviones de Rusia, que son los más pequeños y simples, los servicios de reparación y mantenimiento con que cuenta Aerolíneas S.A. podrían atender un máximo de 40 unidades. Además se sabe que reparar y mantener un avión de Inglaterra demanda 4/3 veces los recursos que requiere un avión de Rusia y que reparar y mantener el avión de USA requiere 5/3 veces los recursos que requiere el avión de Rusia. Formule el modelo de programación lineal que maximice la utilidad de Aerolíneas S.A.

7. Un granjero puede criar ovejas, cerdos y vacas. Tiene espacio para 30 ovejas ó

50 cerdos ó 20 vacas, aunque, siempre que el espacio lo permita, pueden estar en él combinaciones de estos tres tipos de animales. Las utilidades dadas por animal son 500, 400 y 1000 soles para ovejas, cerdos y vacas respectivamente. El granjero desea criar al menos tantos cerdos como ovejas y vacas juntas. Formule un modelo de programación lineal que le ayude al granjero a determinar el número de ovejas, cerdos y vacas que debe criar.


Ciclo 2008 1 52

8. Walter Luna heredó recientemente una gran suma de dinero y desea utilizar una parte para establecer un fideicomiso para sus dos hijos. El fideicomiso tiene dos opciones de inversión: (1) un fondo de bonos y (2) un fondo de acciones. Los requerimientos proyectados durante la vida de las inversiones son de 6% para el fondo de bonos y 10% para el fondo de acciones. Independientemente de la porción de la herencia que finalmente decida comprometer al fideicomiso, desea invertir por lo menos 30% de dicha cantidad en el fondo de bonos. Además desea seleccionar una combinación que le permita obtener un rendimiento total de por lo menos 7,5%. Formule un modelo de programación lineal que pueda utilizarse para determinar el porcentaje que deba asignarse a cada una de las posibles alternativas de inversión.

9. Considere que la empresa Enigma Mutual Funds acaba de obtener fondos de un cliente por $ 100 000 y está buscando oportunidades de inversión. Con base a las inversiones actuales de Enigma, el analista financiero principal de la empresa recomienda que todas las nuevas inversiones se efectúen en empresas del sector minero, empresas del sector agroindustrial o en bonos del gobierno. Específicamente, el analista ha identificado las siguientes oportunidades de inversión:

Inversión Tasa de rendimiento proyectado (%)

Minera Atacocha 7,3 Minera San Vicente 10,3 Compañía Agroindustrial La Hacienda 6,4 Agrícola Oxapampa S.A.C. 7,5 Bonos del gobierno 4,5

La administración de Enigma ha impuesto las siguientes guías de inversión:

Ningún sector (minero o agroindustrial) debe recibir más de $50 000. Los bonos del gobierno deben ser por lo menos 25% de las inversiones en el

sector agroindustrial. En las inversiones en la Minera San Vicente, dado que es de elevado

rendimiento pero de alto riesgo, no pueden superar el 60% del total de las inversiones en el sector minero.

Desarrolle el modelo de programación lineal que permita maximizar el rendimiento proyectado definiendo las variables como el monto a destinar en cada tipo de inversión. Vuelva a resolver el problema definiendo las variables como una fracción de los fondos invertidos en cada uno de los valores. También modifique las restricciones que limitan las inversiones en las industrias de la minería y agroindustria como sigue: no más del 50% de los fondos totales invertidos en acciones puede ser invertido en la industria de la minería y no más del 50% de los fondos invertidos en acciones puede invertirse en la agroindustria.


Ciclo 2008 1 53

10. El gerente de programación del Canal M desea determinar la mejor forma de

asignar el tiempo para la difusión de las noticias en el horario de 11 h a 11:30 h. Específicamente le gustaría determinar el número de minutos de tiempo de difusión dedicado a las noticias locales, noticias nacionales, el clima y los deportes. A lo largo de los 30 minutos de difusión, se reservan 10 minutos para

publicidad. La política de difusión de la estación indica que por lo menos 15% del

tiempo disponible deberá dedicarse a cobertura de noticias locales. El tiempo dedicado a noticias locales y nacionales deberá ser por lo menos el

50% del tiempo total de difusión. El tiempo dedicado al segmento del clima deberá ser inferior o igual al

tiempo dedicado a deportes. El tiempo dedicado al segmento de deportes no deberá ser superior al tiempo

dedicado a noticias locales y nacionales. Por lo menos 20% del tiempo disponible deberá dedicarse al segmento del

clima. Si los costos de producción por minuto son S/. 300 para noticias locales, S/. 200 para noticias nacionales, S/. 100 para el clima y S/. 100 para deportes, formule el modelo de programación lineal que permita obtener una programación usando de manera óptima los recursos disponibles.

11. Cierta persona requiere por razones de salud como mínimo una cantidad diaria

de 6 000 unidades de carbohidratos, 4 000 unidades de proteínas y 3 500 unidades de grasas. Los carbohidratos, proteínas y grasas se encuentran principalmente en dos alimentos diferentes A y B. La cantidad de cada uno de estos nutrientes presentes en los dos alimentos por cada 100 gramos de cada alimento y los requerimientos mínimos diarios se muestran en la siguiente tabla:

Nutriente A B Requerimiento diario mínimo

Carbohidratos 500 200 6 000 Proteínas 300 200 4 000 Grasas 500 100 3 500

Si se sabe que el costo de 100 g. del alimento A es S/. 1,50 y el costo de 100 g. del alimento B es S/. 0,60. Desarrolle el modelo de programación lineal que obtenga la mezcla de ambos alimentos y pueda cumplir la dieta al menor costo.

12. TACO S. A. produce dos líneas de equipo pesado. Una de estas líneas de productos se destina esencialmente a aplicaciones de construcción (E). La otra línea está destinada a la industria maderera (F). Los equipos se producen en los mismos departamentos y con las mismas máquinas y personal. Haciendo uso de las predicciones económicas para el próximo mes, el gerente de mercadotecnia de TACO S. A. juzga que durante ese periodo será posible vender todos equipos E y F que la empresa pueda producir. La administración debe ahora recomendar una meta de producción para el próximo mes, es decir, ¿cuántos equipos E y F deben producirse para maximizar la utilidad?


Ciclo 2008 1 54

En la toma de decisiones, los principales factores a considerar son los siguientes:

TACO S. A. tendrá una utilidad de $5 000 por cada equipo E y $4 000 por

cada equipo F. Cada producto para su fabricación pasa tanto por el departamento A como

por el departamento B. Para la producción del próximo mes, estos departamentos tienen disponibles

150 y 160 horas respectivamente. Cada E consume 10 horas de operación mecánica en el departamento A y 20 horas en el departamento B, mientras que cada F consume 15 horas en el departamento A y 10 horas en el departamento B.

Con el objeto de cumplir un compromiso con el sindicato, el total de horas de trabajo que se dedicarán a la verificación de los productos terminados del próximo mes no puede ser menor en 10% a una meta establecida de 150 horas. Esta verificación se realiza en un tercer departamento que no tiene relación con los departamentos A y B. Cada E requiere 30 horas de comprobación y cada F requiere de 10 horas.

Con el objeto de mantener su posición actual en el mercado, la alta gerencia ha definido que para la política de operación es necesario construir al menos un F por cada 3 Es.

Un cliente importante ha ordenado un total de por lo menos cinco equipos (en cualquier combinación de E y F) para el próximo mes, así que por lo menos debe producirse dicha cantidad.

Formule el modelo de programación lineal del problema.

13. Una compañía puede anunciar su producto mediante el uso de estaciones de radio y televisión locales. Su presupuesto limita los gastos en publicidad a $ 10 000 por mes. Cada minuto de anuncio en la radio cuesta $ 10 y cada minuto de publicidad en televisión cuesta $ 200. La compañía desearía utilizar la radio cuando menos dos veces más que la televisión. La experiencia pasada muestra que cada minuto de publicidad por televisión generará en términos generales 25 veces más ventas que cada minuto de publicidad por la radio. Formule el modelo de programación para determinar el número de anuncios por radio y televisión para maximizar las ventas.

14. Un nuevo producto puede ser obtenido mezclando insumos de cuatro

proveedores diferentes. Los análisis han demostrado que para producir el nuevo producto con las cualidades adecuadas mínimas se debe contar con tres elementos básicos que para abreviar designaremos A, B y C. En particular, cada tonelada del producto debe contener por lo menos 5 Kg. del el elemento A, por lo menos 100 Kg. del elemento B y al menos 30 Kg. del elemento C. El insumo de cada uno de los cuatro proveedores contienen los tres elementos básicos, pero en diferentes proporciones. La composición, en kilogramos, de cada elemento básico por tonelada de insumo es:

Elemento Insumo del proveedor


Ciclo 2008 1 55

básico 1 2 3 4 A 10 3 8 2 B 90 150 75 175 C 45 25 20 37

Los costos en dólares por tonelada de insumo de cada uno de los proveedores se muestran en la siguiente tabla:

Insumo del proveedor 1 2 3 4

Costo de una tonelada ($) 800 400 600 500 Se pide encontrar el modelo de programación lineal de las proporciones (o cantidades) de insumo de cada proveedor que permita obtener una tonelada del nuevo producto que cumpla los requisitos antes mencionados al menor costo posible.

15. La Unión de Crédito para Empleados en la Universidad Estatal está planeando la asignación de fondos para el próximo año. La unión de crédito hace cuatro tipos de préstamos a sus miembros; además, invierte sus excedentes de efectivo en valores sin riesgo para estabilizar sus ingresos. Las diversas inversiones posibles junto con sus respectivas tasas de interés anuales son las siguientes:

Tipo de préstamo o inversión Tasa de interés anual (%)

Préstamos para compra de automóviles 8 Préstamos para mobiliario 10 Otros préstamos garantizados 11 Préstamos quirografarios 12 Valores libres de riesgos 9

La Unión de Crédito dispondrá de S/.2 000 000 para préstamos o inversiones durante el próximo año. Las leyes estatales y las políticas de la unión de crédito imponen las siguientes restricciones en la composición de los préstamos e inversiones.

Los valores libres de riesgos no pueden exceder el 30% de los fondos totales

disponibles para inversión. Los préstamos quirografarios no pueden exceder el 10% de los fondos

invertidos en todos los préstamos. Los préstamos para mobiliario más otros préstamos garantizados no pueden

exceder los préstamos para compra de automóviles. Otros préstamos garantizados más los préstamos quirografarios no pueden

exceder los fondos invertidos en valores sin riesgos.

Formule un modelo matemático de programación lineal con la finalidad de determinar ¿cómo se asignarían los S/.2 000 000 a cada una de las alternativas de préstamo o inversión para maximizar el rendimiento anual total?


Ciclo 2008 1 56

16. Enigma Trucks ha decidido entrar al mercado de vehículos recreativos con la Dunamis, una especie de motocicleta con tres llantas extra-grandes. Dado que se trata de una nueva línea de productos se plantea una campaña de publicidad bastante intensa durante el mes de introducción a la cual se le asignó un presupuesto de $ 72 000 para ejecutarla.

Enigma Trucks decidió usar la radio durante la mañana, la televisión en la tarde y los periódicos durante toda la campaña. La agencia de publicidad de Enigma proporciona los datos relativos al costo de los anuncios en cada uno de los medios y el número de unidades de compra que serán logrados mediante dichos anuncios de acuerdo a la siguiente tabla:

Medio de

publicidad Número de unidades de

compra alcanzados por anuncio Costo por anuncio

($) Radio en la mañana 30 000 1 700

TV en la tarde 60 000 2 800 Periódicos 45 000 1 200

La efectividad de un anuncio se mide en unidades de exposición en una escala de 0 a 100 para cada anuncio exhibido. También se sabe que la eficacia del anuncio disminuye con el número de exposiciones en un medio durante un tiempo específico. La siguiente tabla muestra el número de exposiciones por anuncio y su variación de acuerdo al medio usado y a la cantidad de avisos utilizados en el mismo medio.

Medio de publicidad Primeros 10 anuncios Todos los anuncios siguientes Radio en la mañana 60 40

TV en la tarde 80 55 Periódicos 70 35

Además se quiere asegurar que la campaña de publicidad satisfará ciertos criterios que se consideran importantes. En concreto: no deberán aparecer más de 25 anuncios en un solo medio; se deberá alcanzar un total de por lo menos 1 800 000 unidades de compra a través de todos los medios y al menos una cuarta parte de los anuncios aparecerán en la TV en la tarde. Obtenga el modelo de programación lineal que permita maximizar el total de unidades de exposición.

17. Una compañía de inversiones tiene que elegir entre cuatro proyectos que compiten por un presupuesto de inversión máximo de $ 1 500 000. En la siguiente tabla se muestra la inversión neta y los rendimientos estimados de cada proyecto. A cada proyecto se le puede asignar fondos a cualquier nivel fraccional menor o igual al 100%. La compañía requiere una rendimiento mínimo del 25% y desea minimizar el riesgo. Suponga que el riesgo es aditivo, por ejemplo, el riesgo de asignar fondos para aceites al 20% y para oficinas al 50% será (0,2).(9) + (0,5).(4) = 3,8.

Proyecto Inversión Rendimiento neto Riesgo

Centros comerciales 550 000 170 000 6


Ciclo 2008 1 57

Aceite 400 000 500 000 9 Edificios de oficinas 450 000 100 000 4 Edificios Mivivienda 500 000 100 000 2

Elabore el modelo de programación lineal correspondiente.

18. Una planta puede manufacturar cinco productos diferentes en cualquier

combinación. Cada producto requiere de cada una de las tres máquinas, tal como se muestra en la siguiente tabla:

Producto Máquina

1 2 3 A 12 8 5 B 7 9 10 C 8 4 7 D 10 0 3 E 7 11 2

Todos los datos de la tabla están en minutos por kilogramo de producto. Cada máquina está disponible 128 horas por semana. Los productos A, B, C, D y E son netamente competitivos y cualquier

cantidad fabricada puede venderse a los precios respectivos de $5, $4, $5, $4 y $4 por kilogramo de producto.

Los costos variables de trabajo son $4 por hora de las máquinas 1 y 2, y $3 para la máquina 3.

Los costos de material por cada kilogramo de los productos A y C son de $2 y para los productos B, D y E son de $1 por kilogramo.

La empresa desea maximizar la utilidad generada por los productos, para lo cual se pide que elabore el modelo de programación lineal correspondiente.

19. La administración de Alta Tecnología S. A. (ATSA) desea desarrollar un modelo que le ayude a asignar el tiempo de sus técnicos entre llamadas de servicio por contrato a clientes tanto normales como nuevos. En el periodo de planeación de 2 semanas hay disponible un máximo de 80 horas de tiempo de técnico. A fin de satisfacer los requisitos de flujo de caja, deben generarse por lo menos $800 de ingresos durante el periodo de 2 semanas. El tiempo de los técnicos para los clientes normales genera $25 la hora, pero para clientes nuevos sólo genera $8 la hora, porque en muchos casos el contacto con un cliente nuevo no llega a generar servicios. Para asegurarse de que se mantienen contactos con los clientes nuevos debe ser por lo menos 60% del tiempo utilizado en contactos con clientes normales. Para los requerimientos de ingresos y de políticas enunciadas, ATSA desearía determinar cómo asignar el tiempo de los técnicos entre clientes normales y nuevos, a fin de maximizar el número total de clientes en contacto durante el periodo de 2 semanas. Los técnicos requieren un promedio de 50 minutos por cada contacto de cliente normal y de una hora para cada contacto de cliente nuevo.


Ciclo 2008 1 58

Desarrolle el modelo de programación lineal que permita a ATSA asignar el tiempo de los técnicos entre clientes normales y nuevos.

20. Enigma Manufacturing es un pequeño fabricante de productos de plástico que se utilizan en las industrias automotrices y de computación. Tiene un contrato importante con una gran empresa de computadoras que implica la producción de cajas de plástico para las impresoras portátiles de dicha empresa. Las cajas de impresora se producen en dos máquinas de moldeo por inyección. La máquina M100 tiene una capacidad de producción de 20 cajas de impresora por hora y la M200 tiene una capacidad de producción de 40 cajas por hora. Ambas máquinas utilizan la misma materia prima para producir las cajas de la impresora: la M100 utiliza 40 kilogramos de materia prima por hora y la M200 utiliza 50 kilogramos por hora. La empresa de computadoras le ha pedido a Enigma que produzca tantas cajas durante la semana siguiente como sea posible y le ha dicho que pagará 18 dólares por caja que pueda entregar. Sin embargo, la siguiente semana es un periodo normal de vacaciones programadas para la mayor parte de trabajadores de producción de Enigma. Durante ese tiempo, se efectúa el mantenimiento anual de todo el equipo de la planta. Debido al tiempo parado para mantenimiento, la M100 estará disponible a lo más 15 horas y la M200 a lo más 10 horas. Sin embargo, en razón del elevado costo de preparación involucrado con ambas máquinas, la administración requiere que, si se programa producción en cualquiera de estas máquinas, la máquina deberá operarse por lo menos durante 5 horas. El proveedor de la materia química utilizada en el proceso de producción le ha informado a Enigma que tendrá disponible un máximo de 1 000 Kg. de la materia prima para la producción de la siguiente semana. El costo de esta materia prima es de $6 por kilogramo, Enigma estima que los costos por hora de operación de la M100 y de la M200 son de $50 y $75 respectivamente. Formule el modelo de programación lineal que permita encontrar el plan de producción óptima que maximice la utilidad.

Problemas con solución por método gráfico 21. Al resolver el problema 1, se obtuvo el siguiente modelo de programación lineal:

X1: número de productos 1 a fabricar el próximo mes. X2: número de productos 2 a fabricar el próximo mes.

Max 12 X1 + 4 X2 sujeto a :

X1 + 2 X2 ≤ 800 (horas disponibles del departamento A) X1 + 3 X2 ≤ 600 (horas disponibles del departamento B)

2 X1 + 3 X2 ≤ 2 000 (horas disponibles del departamento C) X1 , X2 ≥ 0 (condición de no negatividad)

Se pide obtenga la solución óptima aplicando el método gráfico.


Ciclo 2008 1 59

22. Con el modelo obtenido en el problema 4, ¿cuál es la mezcla de costo mínimo de los alimentos para perros y cuál es el costo de la mezcla?

X1: Cantidad diaria del alimento Guau. (en onzas). X2: Cantidad diaria del alimento Sniff. (en onzas).

Min 0,06 X1 + 0,05 X2 sujeto a :

0,30 X1 + 0,20 X2 ≥ 5 (requerimiento diario mínimo de proteínas en onzas) 0,15 X1 + 0,30 X2 ≥ 3 ((requerimiento diario mínimo de proteínas en onzas) X1 , X2 ≥ 0 (condición de no negatividad)

23. Al resolver el problema 5 se obtuvo el siguiente modelo de programación lineal:

X1: cantidad de raquetas normal a fabricar las próximas dos semanas. X2: cantidad de raquetas grande a fabricar las próximas dos semanas.


- 0,8 X1 + 0,2 X2 ≤ 0 (mezcla de producción) 0,125 X1 + 0,4 X2 ≤ 80 (aleación disponible)

10 X1 + 12 X2 ≤ 4 800 (tiempo disponible) X1 , X2 ≥ 0 (condición de no negatividad) ¿Cuántas raquetas de cada tipo deberá fabricar la empresa en las dos siguientes semanas a fin de maximizar la contribución total a la utilidad?. ¿Cuánto sería dicha contribución? Utilice el método gráfico para responder las preguntas.

24. Para el modelo obtenido en el problema 8, determine gráficamente la solución óptima.

X1: proporción del fideicomiso invertido en bonos. X2: proporción del fideicomiso invertido en acciones.

Max 0,06 X1 + 0,10 X2 sujeto a :

X1 ≥ 0,30 (mínima proporción invertida en bonos) 0,06 X1 + 0,10 X2 ≥ 0,075 (rendimiento total mínimo)

X1 + X2 = 1 (la suma de las proporciones da la unidad) X1, X2 ≥ 0 (condición de no negatividad)

25. El modelo obtenido en el problema 11 fue el siguiente:

X1: Número de unidades diarias de 100 gramos del alimento A. X2: Número de unidades diarias de 100 gramos del alimento B.

Min 1,5 X1 + 0,6 X2 sujeto a:

500 X1 + 200 X2 ≥ 6 000 (requerimiento diario mínimo de u. de carbohidratos) 300 X1 + 200 X2 ≥ 4 000 (requerimiento diario mínimo de u. de proteínas) 500 X1 + 100 X2 ≥ 3 500 (requerimiento diario mínimo de u. de grasas)

X1, X2 ≥ 0 (condición de no negatividad)


Ciclo 2008 1 60

Determine gráficamente la solución óptima del problema.

26. Al resolver el problema 12 se obtuvo el siguiente modelo de programación lineal.

Xe: número de equipos E a fabricar el próximo mes. Xf : número de equipos F a fabricar el próximo mes.

Max 5000 Xe + 4000 Xf sujeto a:

10 Xe + 15 Xf ≤ 150 (horas disponibles Departamento A) 20 Xe + 10 Xf ≤ 160 (horas disponibles Departamento B) 30 Xe + 10 Xf ≥ 135 (acuerdo con el sindicato) Xe - 3 Xf ≤ 0 (recomendación de Mercadeo) Xe + Xf ≥ 5 (pedido mínimo) Xe, Xf ≥ 0 (condición de no negatividad)

a. Determine gráficamente el plan óptimo de producción y el valor óptimo. b. Determine e interprete las holguras y excedentes de las restricciones. c. Calcule e interprete los precios duales. d. Determine e interprete los rangos de optimalidad.

27. De acuerdo a la solución del problema 13, determine la solución óptima:

X1: número de avisos en radio. X2 : número de avisos en televisión.

Max X1 + 26 X2 sujeto a:

10 X1 + 200 X2 ≤ 10 000 (presupuesto) X1 – 3 X2 ≥ 0 (política de la compañía) X1, X2 ≥ 0 (condición de no negatividad)

28. El modelo obtenido en la solución del problema 19 es:

X1: número de clientes normales contactados las próximas dos semanas. X2: número de clientes nuevos contactados las próximas dos semanas.

Max X1 + X2 sujeto a :

65 X1 + X2 ≤ 80 (tiempo disponible)

6

125 X1 + 8 X2 ≥ 800 (ingreso requerido)

- 0,5 X1 + X2 ≥ 0 (contacto con los clientes) X1 , X2 ≥ 0 (condición de no negatividad)

a. Obtenga la gráfica de la región factible. b. Resuelva las ecuaciones lineales apropiadas para determinar los valores de

las variables en cada punto extremo de la región factible. c. Encuentre la solución óptima.


Ciclo 2008 1 61

29. El modelo del problema 20 puede ser planteado de manera distinta dependiendo

cómo se hayan definido las variables. Para ambas alternativas y utilizando el procedimiento gráfico obtenga la solución óptima y el valor óptimo de dicho modelo y compruebe si ambas soluciones son equivalentes. Modelo 1:

X1: número de cajas producidas en la máquina M100 la siguiente semana. X2: número de cajas producidas en la máquina M200 la siguiente semana.

Max 3,5 X1 + 8,625 X2 sujeto a:

2 X1 + 1,25 X2 ≤ 1000 (materia prima disponible) 0,05 X1 ≤ 15 (tiempo disponible de M100) 0,05 X1 ≥ 5 (tiempo de funcionamiento de M100) 0,025 X2 ≤ 10 (tiempo disponible de M200) 0,025 X2 ≥ 5 (tiempo de funcionamiento de M200) X1, X2 ≥ 0 (condición de no negatividad)

Modelo 2:

X1: tiempo asignado a la máquina M100 la siguiente semana (h). X2: tiempo asignado a la máquina M200 la siguiente semana (h).

Max 70 X1 + 345 X2 sujeto a:

40 X1 + 50 X2 ≤ 1000 (materia prima disponible) X1 ≤ 15 (tiempo disponible de M100)

X1 ≥ 5 (tiempo de funcionamiento de M100) X2 ≤ 10 (tiempo disponible de M200) X2 ≥ 5 (tiempo de funcionamiento de M200) X1, X2 ≥ 0 (condición de no negatividad)

30. Para el problema 21 se desarrolló el siguiente modelo de programación lineal:

Max 1,04 X1 + 1,18 X2 sujeto a:

0.32 X1 + 0.24 X2 ≤ 8100 0.08 X1 + 0.16 X2 ≤ 3000

X1, X2 ≥ 0 Se pide que encuentre e interprete la solución óptima y el valor óptimo del modelo.

31. Para el problema 22 se desarrolló el siguiente modelo de programación lineal

Max 0,03 X1 + 0,04 X2 sujeto a:

5 X1 + 4 X2 ≤ 1 200 000 X1 ≥ 30 000 X2 ≥ 10 000


Ciclo 2008 1 62

0,25 X1 – 0,40 X2 ≥ 0 X1 , X2 ≥ 0

Se pide encuentre la solución óptima

32. Para el problema 23 se desarrolló el siguiente modelo de programación lineal


30 X1 + 20 X2 ≤ 7 200 45 X1 + 15 X2 ≤ 7 200 0,8 X1 – 0,2 X2 ≥ 0 X1 – 3 X2 ≤ 0 X1 , X2 ≥ 0

Se pide encuentre la solución óptima

33. Considere el siguiente problema de programación lineal.

Max X1 + 2 X2 sujeto a :

X1 + 4 X2 ≤ 21 2 X1 + X2 ≥ 7 3 X1 + 1,5 X2 ≤ 21 -2 X1 + 6 X2 ≥ 0 X1 , X2 ≥ 0

a. Encuentre la solución óptima y el valor óptimo. b. Determine las holguras o excedentes de cada una de las restricciones. c. Suponga que la función objetivo se modifica a Max 5X1 + 2X2, encuentre la

nueva solución óptima y el nuevo valor óptimo. 34. Considere el siguiente programa lineal.

Max 5X1 + 7 X2 sujeto a :

2 X1 + X2 ≥ 3 - X1 + 5 X2 ≥ 4

2 X1 - 3 X2 ≤ 6 3 X1 + 2 X2 ≤ 35

73 X1 + X2 ≤ 10

X1, X2 ≥ 0

a. Determine la solución óptima. b. Realice el análisis de sensibilidad del coeficiente X1 en la función objetivo. c. Suponga que el coeficiente de X1 en la función objetivo se reduce a 2. ¿Cuál

será la nueva solución óptima? d. Calcule los precios duales de la segunda y cuarta restricción.


Ciclo 2008 1 63

35. Considere el programa lineal:

Min X1 + X2 sujeto a : X1 + 2 X2 ≥ 6

3 X1 + X2 ≥ 6 X1 - 12 X2 ≤ 0 X1 + X2 ≤ 10 X1 + 6 X2 ≥ 12 X1 , X2 ≥ 0

a. Determine la región factible. b. Encuentre la solución óptima y el valor óptimo. c. Determine las holguras o excedentes de cada una de las restricciones. d. Calcule el rango de optimalidad para el coeficiente de X2. e. Suponga que el coeficiente de la variable X2 en la función objetivo se reduce

a 1/3. Encuentre la nueva solución óptima. 36. Considere el siguiente problema de programación lineal.

Min 5 X1 + 2 X2 sujeto a : 3 X1 + 6 X2 ≥ 18

5 X1 + 4 X2 ≥ 20 8 X1 + 2 X2 ≥ 16 7 X1 + 6 X2 ≤ 42 X1 , X2 ≥ 0

a. Usando el método gráfico encuentre la solución óptima y el valor óptimo. b. ¿Cuáles son los valores de holgura o excedente asociados a cada restricción? c. ¿Cuál es el rango de variación del coeficiente de X2 en la función objetivo de

manera que la solución óptima no cambie? d. Si simultáneamente los coeficientes de X1 y X2 cambian a 2,5 y 1

respectivamente, ¿cuál es la nueva solución óptima? e. Si el coeficiente de X1 se reduce a 2, ¿cuál es la nueva solución óptima?

37. Considere el siguiente problema de programación lineal.


2 X1 + X2 ≤ 4 2 X1 + 2 X2 ≤ 6 X1, X2 ≥ 0

a. Usando el método gráfico encuentre la solución óptima y el valor óptimo. b. Indique los valores de holgura y/o excedentes de las restricciones. c. Manteniendo todos los demás datos como están, ¿cuál debe ser la utilidad

por unidad del producto cuyo valor óptimo actual es cero, para que el producto se encuentre en la solución óptima en un nivel positivo?


Ciclo 2008 1 64

d. ¿Cuántos vértices óptimos existen luego del cambio descrito en (c)?. ¿Cuáles son estos?

e. En el problema original, ¿en cuánto puede cambiar (aumentar y/o disminuir) el lado derecho de la segunda restricción para que cambie la solución óptima?

f. Conteste la parte (e) para el lado derecho de la primera restricción. g. ¿Cómo explica la diferencia entre las partes (e) y (f)? h. ¿Cuál será el efecto de agregar la restricción 4X1 + X2 = 4 al modelo

original? i. ¿Cuál será el efecto (sobre la solución óptima) de agregar la restricción 3 X1

+ 3 X2 ≤ 15 al modelo original? Problemas con solución por computadora 38. Desarrollado el modelo del problema 12, mediante la computadora se obtuvo el

siguiente reporte: Max 5000 xe + 4000 xf subject to 10 xe + 15 xf <= 150 20 xe + 10 xf <= 160 30 xe + 10 xf >= 135 xe - 3 xf <= 0

xe + xf >= 5 end OBJECTIVE FUNCTION VALUE 1) 50500.00 VARIABLE VALUE REDUCED COST XE 4.500000 0.000000 XF 7.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 150.000000 3) 0.000000 175.000000 4) 70.000000 0.000000 5) 16.500000 0.000000 6) 6.500000 0.000000 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE XE 5000.000000 3000.000000 2333.333252 XF 4000.000000 3500.000000 1500.000000


Ciclo 2008 1 65

RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 150.000000 90.000000 47.142857 3 160.000000 73.333336 40.000000 4 135.000000 70.000000 INFINITY 5 0.000000 INFINITY 16.500000 6 5.000000 6.500000 INFINITY a. Identifique la solución óptima y el valor óptimo del modelo y compárelos

con los obtenidos gráficamente (problema 33). b. Interprete las holguras y los excedentes de las restricciones. c. Interprete los precios duales de las restricciones. d. Determine los rangos de optimalidad de las utilidades unitarias de los

productos. 39. Desarrollado el modelo del problema 14 se obtuvo el siguiente reporte de

computadora:

Min 800 x1 +400 x2 + 600 x3 + 500 x4 subject to 10 x1 + 3 x2 + 8 x3 + 2 x4 >= 5 90 x1 + 150 x2 + 75 x3 + 175 x4 >= 100 45 x1 + 25 x2 + 20 x3 + 37 x4 >= 30 x1 + x2 + x3 + x4 = 1

end


VARIABLE VALUE REDUCED COST

X1 X2 X3 X4

0.259259 0.703704 0.037037 0.000000

0.000000 0.000000 0.000000 91.111115

ROW SLACK OR

SURPLUS DUAL PRICES

2) 3) 4) 5)

0.000000 31.666666 0.000000 0.000000

-44.444443 0.000000 -4.444445

-155.555557 NO. ITERATIONS= 1

RANGES IN WHICH THE BASIS IS UNCHANGED

OBJ COEFFICIENT RANGES VARIABLE CURRENT

COEF ALLOWABLE INCREASE

ALLOWABLE DECREASE

X1 X2 X3 X4

800.000000 400.000000 600.000000 500.000000

223.636337 66.847824 85.714294 INFINITY

120.000008 300.000031 118.269241 91.111107

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE


Ciclo 2008 1 66

RHS INCREASE DECREASE 2 3 4 5

5.000000 100.000000 30.000000 1.000000

2.375000 31.666666 0.714286 0.250000

0.250000 INFINITY 7.000000 0.043478

Se pide: a. Encuentre la solución óptima del modelo. b. Encuentre el valor óptimo del modelo. c. Si el requisito del elemento B es 100, ¿por qué se debe usar más de 100 si

esto eleva el costo? d. ¿Qué acciones debería tomarse para reducir el costo mínimo a $500 dólares

o menos por tonelada de mezcla? e. ¿Qué sucede si el precio de mineral de la mina 2 aumenta más a $500? f. ¿Cuánto tendría que disminuir el costo del mineral de la mina 4 para decidir

comprarlo? 40. En un problema de mezcla de fabricación de productos, x1, x2, x3 y x4 son

unidades de los productos 1, 2, 3 y 4 respectivamente y el modelo de programa de programación lineal que maximiza la utilidad en unidades monetarias para la próxima temporada es:

Max 4 x1 + 6 x2 + 3 x3 + x4 subject to x1 + 2 x2 + 4 x3 + 3 x4 ≤ 550 (horas de la máquina A) 4 x1 + x2 + 2 x3 + x4 ≤ 700 (horas de la máquina B) 2 x1 + 3 x2 + x3 + 2 x4 ≤ 200 (horas de la máquina C) end

OBJECTIVE FUNCTION VALUE

1) 528.5714 VARIABLE VALUE REDUCED COST

X1 X2 X3 X4

35.714287 0.000000

128.571426 0.000000

0.000000 0.142857 0.000000 3.571429

ROW SLACK OR

SURPLUS DUAL PRICES

2) 3) 4)

0.000000 300.000000 0.000000

0.285714 0.000000 1.857143

NO. ITERATIONS= 1 RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES VARIABLE

CURRENT COEF

ALLOWABLE INCREASE

ALLOWABLE DECREASE

X1 X2 X3 X4

4.000000 6.000000 3.000000 1.000000

2.000000 0.142000 12.999999 3.571000

0.100000 INFINITY 0.999999 INFINITY


Ciclo 2008 1 67

RIGHTHAND SIDE RANGES ROW

CURRENT RHS

ALLOWABLE INCREASE

ALLOWABLE DECREASE

2 3 4

550.000000 700.000000 200.000000

250.000000 INFINITY

150.000000

449.999999 300.000000 62.500000

a. ¿Cuál es la solución óptima y cuál es el valor óptimo? b. ¿Qué restricciones tienen restricciones limitantes? Identifique e interprete el

rango de optimalidad de la contribución de cada producto. c. Interprete los precios duales de las restricciones. d. Interprete el siguiente resultado:


CURRENT RHS

ALLOWABLE INCREASE

ALLOWABLE DECREASE

3 700.000000 INFINITY 300.000000 e. Interprete los costos reducidos reportados.

41. Mercurio Sport S.A. tiene que determinar cuál es la cantidad idónea de balones de fútbol Ases (x1), Bólidos (x2) y Crack (x3) a producir a fin de maximizar las utilidades. Las restricciones incluyen limitaciones en la capacidad de producción (tiempo disponible en minutos) en cada uno de los departamentos (corte y teñido, costura e inspección y empaque), así como la restricción que requiere la producción de por lo menos 1000 balones de fútbol Ases. A continuación se presenta el modelo de programación lineal y el reporte de computadora de la solución del modelo:

Max 3 x1 + 5 x2 + 4 x3 subject to 12 x1 + 10 x2 + 8 x3 <= 18000 Corte y teñido 15 x1 + 15 x2 + 12 x3 <= 18000 Costura 3 x1 + 4 x2 + 2 x3 <= 9000 Inspección y empaque x1 >= 1000 Modelo Ases

end



X1 X2 X3

1000.000000 0.000000

250.000000

0.000000 0.000000 0.000000

ROW SLACK OR

SURPLUS DUAL PRICES

2) 3) 4) 5)

4000.000000 0.000000

5500.000000 0.000000

0.000000 0.333333 0.000000 -2.000000

RANGES IN WHICH THE BASIS IS UNCHANGED:


CURRENT COEF

ALLOWABLE INCREASE

ALLOWABLE DECREASE

X1 X2 X3

3.000000 5.000000 4.000000

2.000000 0.000000 INFINITY

INFINITY INFINITY 0.000000


Ciclo 2008 1 68


ROW

CURRENT RHS

ALLOWABLE INCREASE

ALLOWABLE DECREASE

2 3 4 5

18000.000000 18000.000000 9000.000000 1000.000000

INFINITY 6000.000000

INFINITY 200.000000

4000.000000 3000.000000 5500.000000 1000.000000

a. ¿Cuál es el plan de producción óptimo y la contribución óptima? b. ¿Qué departamentos tienen recursos limitantes? c. El pago de trabajo extra en el departamento de Costura es $12 por hora

¿Recomendaría usted que la empresa considere usar tiempo extra en dicho departamento?

d. Suponga que la contribución a la utilidad del balón de fútbol Crack aumenta en $1. ¿Cómo esperaría usted que cambie la solución?

e. ¿Cuál es la interpretación para la administración del precio dual de la última restricción?

f. ¿Cuál es la interpretación de los costos reducidos?

42. Don Francisco quiere mejorar el negocio familiar de elaboración de productos a partir de la papa. Su negocio es la venta de cuatro productos derivados de la papa: papas trozadas para ensalada, puré de papas, papas fritas a la inglesa y papas congeladas para freír. A su negocio, don Francisco y doña Remedios, su mujer, dedican como máximo entre los dos, 100 horas semanales. El tiempo en horas necesario para fabricar un kilo de cada producto es el siguiente: papas trozadas para ensalada 3 h, puré de papas 5 h, papas fritas a la inglesa 10 h, papas congeladas 15 h. Como su almacén es pequeño no pueden tener almacenados semanalmente más de 15 kilos de productos terminados. Su presupuesto semanal alcanza para la compra de 120 kilos en sacos de papas. Por cada kilo de producto terminado necesita una cantidad mayor de producto bruto, de acuerdo a las siguientes relaciones:

Para hacer un kilo de papas para ensalada se necesita 7 kilos de papas. Para hacer un kilo de puré de papas se necesita 5 kilos de papas. Para hacer un kilo de papas a la inglesa se necesita 3 kilos de papas. Para hacer un kilo de papas congeladas se necesita 2 kilos de papas.

La ganancia por kilo de producto también difiere en cada tipo: 4 $/Kg. papas para ensalada, 5 $/Kg. puré de papas, 9 $/Kg. papas fritas a la inglesa y 11 $/Kg. papas congeladas para freír. Don Francisco desea establecer el plan de producción para la próxima temporada de ventas y estima que es posible vender todo lo que produzca. Don Francisco ha formulado un modelo de programación lineal con el fin de optimizar el plan de producción, el cual se muestra a continuación.

Max 4 X1 + 5 X2 + 9 X3 + 11 X4 subject to 3 X1 + 5 X2 + 10 X3 + 15 X4 <= 100


Ciclo 2008 1 69

X1 + X2 + X3 + X4 <= 15 7 X1 + 5 X2 + 3 X3 + 2 X4 <= 120 end


VARIABLE VALUE REDUCED COST X1 X2 X3 X4

7.142857 0.000000 7.857143 0.000000

0.000000 0.428571 0.000000 1.571429

ROW SLACK OR SURPLUS

DUAL PRICES

2) 3) 4)

0.000000 0.000000 46.428570

0.714286 1.857143 0.000000



CURRENT COEF

ALLOWABLE INCREASE

ALLOWABLE DECREASE

X1 X2 X3 X4

4.000000 5.000000 9.000000 11.000000

2.200000 0.428571 4.333333 1.571429

0.600000 INFINITY 0.916667 INFINITY


ROW

CURRENT RHS

ALLOWABLE INCREASE

ALLOWABLE DECREASE

2 3 4

100.000000 15.000000 120.000000

49.999996 5.327868 INFINITY

54.999996 5.000000 46.428570

a. ¿Cuál es el programa óptimo? ¿Qué beneficio total se obtiene? b. Si aumentamos en 50 horas la disponibilidad actual de las horas semanales

¿aumenta en aproximadamente $ 35.7 el valor de la función objetivo? c. Para aumentar la capacidad de almacenamiento de productos terminados en

5 Kg. se necesita alquilar un pequeño local contiguo, cuyo propietario solicita $ 8 por semana ¿sería conveniente el alquiler? Explique.

d. A don Francisco y doña Remedios le resulta ahora tedioso el trabajo semanal, por lo que han decidido dedicar 30 horas semanales de su tiempo del negocio a consultoría a $ 5 la hora, ¿cómo afecta esto a las utilidades totales?

e. Si usted tiene que tomar la decisión excluyente de contratar personal de apoyo o alquilar más espacio para su almacén de productos terminados ¿qué decidiría y porqué? De ser así ¿qué cantidad de horas adicionales programaría o en cuánto aumentaría usted el espacio disponible?

43. De acuerdo al problema 18 se elaboró un modelo de programación lineal que se

resolvió por computadora y cuyo reporte se muestra a continuación:

Max 1,416 XA + 1,433 XB + 1,85 XC + 2,183 XD + 1,7 XE subject to 12 XA + 7 XB + 8 XC + 10 XD + 7 XE <= 7680 8 XA + 9 XB + 4 XC + 11 XE <= 7680


Ciclo 2008 1 70

5 XA + 10 XB + 7 XC + 3 XD + 2 XE <= 7680 end



XA XB XC XD XE

0.000000 0.000000

512.000000 0.000000

512.000000

1.380000 0.240000 0.000000 0.750000 0.000000

ROW SLACK OR

SURPLUS DUAL PRICES

2) 3) 4)

0.000000 0.000000

3072.000000

0.222222 0.010000 0.000000



CURRENT COEF

ALLOWABLE INCREASE

ALLOWABLE DECREASE

XA XB XC XD XE

1.146000 1.433000 1.850000 2.183000 1.700000

1.380000 0.240000 0.090000 0.070000 0.111111

INFINITY INFINITY 0.0400000 INFINITY 0.0800000


CURRENT RHS

ALLOWABLE INCREASE

ALLOWABLE DECREASE

2 3 4

7680.000000 7680.000000 7680.000000

2671.300000 4388.570000

INFINITY

2792.720000 3840.000000 3072.000000

De acuerdo a dicho desarrollo se pide: a. Indique con precisión las variables utilizadas en el modelo. b. Explique la función objetivo del modelo. c. ¿Cuál es el plan óptimo de producción y qué utilidad se obtendría? d. ¿Cuántas horas se utilizan en cada una de las tres máquinas? e. Interprete los valores de los precios duales de las restricciones que controlan

la capacidad de las máquinas? f. Si existiera la posibilidad de aumentar una hora adicional de disponibilidad a

la semana en cada una de las máquinas, ¿a qué máquinas se les agregaría dicha capacidad adicional y cuánto debería pagarse como máximo por la obtención de dicha hora adicional?

g. ¿Cuánto puede variar el precio de venta del producto A sin que cambie el plan óptimo de producción?

44. En una imprenta comercial se desea determinar la mejor programación de los

trabajos para el próximo período. La disponibilidad de tiempo, en sus 4 departamentos, de tipografía, fotografía, prensa y empaste, es limitada.


Ciclo 2008 1 71

Los trabajos han sido clasificados en 3 clases, 1, 2 y 3, de acuerdo al tiempo que necesitan en cada departamento. Los requerimientos en horas, por departamento y por cada unidad de trabajo producida, se han estimado como:

Departamento Trabajo 1 Trabajo 2 Trabajo 3

Tipografía 0 2 3 Fotografía 3 1 4

Prensa 3 5 2 Empaste 4 4 0

Si los trabajos se ejecutan en tiempo normal, el beneficio unitario neto es de $250, $300 y $150 para trabajos tipo 1, 2 y 3, respectivamente. Compromisos adquiridos requieren que la producción de trabajos tipo 1, 2 y 3 sea por lo menos de 10, 7 y 10 unidades, respectivamente. Las disponibilidades máximas de tiempo, para el período analizado son:

Departamento Tiempo normal (horas) Tipografía 45 Fotografía 90

Prensa 210 Empaste 170

Max 250 X1 + 300 X2 + 150 X3

subject to 2 X2 + 3 X3 <= 45 3 X1 + X2 + 4 X3 <= 90 3 X1 + 5 X2 + 2 X3 <= 210 4 X1 + 4 X2 <= 170 X1 >= 10 X2 >= 7 X3 >= 10 end



X1 X2 X3

14.166667 7.500000 10.000000

0.000000 0.000000 0.000000

ROW SLACK OR

SURPLUS DUAL PRICES

2) 3) 4) 5) 6) 7) 8)

0.000000 0.000000

110.000000 83.333336 4.166667 0.500000 0.000000

108.333336 83.333336 0.000000 0.000000 0.000000 0.000000

-508.333344 RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES


Ciclo 2008 1 72

VARIABLE

CURRENT COEF

ALLOWABLE INCREASE

ALLOWABLE DECREASE

X1 X2 X3

250.000000 300.000000 150.000000

650.000000 INFINITY

508.333344

250.000000 216.666672 INFINITY


CURRENT RHS

ALLOWABLE INCREASE

ALLOWABLE DECREASE

2 3 4 5 6 7 8

45.000000 90.000000 210.000000 170.000000 10.000000 7.500000 10.000000

24.999998 62.500000 INFINITY INFINITY 4.166667 0.500000 0.000000

0.000000 12.499999 110.000000 83.333336 INFINITY INFINITY 8.928572

a. Explique el modelo que se ha formulado (identificación de las variables, función objetivo y restricciones).

b. ¿Cuál es el programa de producción óptimo? c. ¿Existe capacidad ociosa? ¿Cuánto y en qué departamentos? d. Es posible operar el departamento de fotografía en tiempo extra. ¿Hasta

cuánto debería estar dispuesto a pagar por una hora adicional? e. Si las horas disponibles en el departamento fotográfico se reducen a 78

horas, ¿cambia el programa de producción óptimo? ¿Cambia la ganancia óptima?

f. ¿Qué significa un precio dual de –508.33 en la última restricción? 45. Bus Electronics S.A. fabrica tres componentes que se usan para fabricar

teléfonos celulares. Este mes la demanda de los componentes puede exceder la capacidad de fabricación de Bus. Si fuera así, Bus tendría que satisfacer la demanda comprando los componentes a otro fabricante con el aumento del costo por componente. El costo de fabricación y el costo de compra por unidad para los tres componentes son los siguientes:

Fuente Componente 1 Componente 2 Componente 3

Manufactura $ 4,50 $ 5,00 $ 2,75 Compra $ 6,50 $ 8,80 $ 7,00

Los tiempos de manufactura en minutos por unidad para los tres departamentos de Bus son los siguientes:

Departamento Componente 1 Componente 2 Componente 3

Producción 2 3 4 Ensamblado 1 1,5 3

Prueba y empaque 1,5 2 5

Bus tiene capacidades de 360 horas en el departamento de producción, 250 horas en el departamento de ensamblado y 300 horas en el departamento de prueba y empaque. Las demandas a satisfacer son 6000 unidades del componente 1, 4000 unidades del componente 2 y 3500 unidades del componente 3.


Ciclo 2008 1 73

El modelo de programación lineal que determina cuántas unidades de cada componente fabricar y cuántas unidades de cada componente comprar al menor costo es el siguiente:

Min 4.5 M1 + 5 M2 + 2.75 M3 + 6.5 P1 + 8.8 P2 + 7 P3

subject to

2 M1 + 3 M2 + 4 M3 <= 21 600 M1 + 1.5 M2 + 3 M3 <= 15 000

1.5 M1 + 2 M2 + 5 M3 <= 18 000 M1 + P1 = 6 000 M2 + P2 = 4 000 M3 + P3 = 3 500

end OBJECTIVE FUNCTION VALUE 1) 73550.00 VARIABLE VALUE REDUCED COST M1 2000.000000 0.000000 M2 4000.000000 0.000000 M3 1400.000000 0.000000 P1 4000.000000 0.000000 P2 0.000000 0.831250 P3 2100.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.906250 3) 2800.000000 0.000000 4) 0.000000 0.125000 5) 0.000000 -6.500000 6) 0.000000 -7.968750 7) 0.000000 -7.000000 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE M1 4.500000 0.725000 0.125000 M2 5.000000 0.831250 INFINITY M3 2.750000 0.250000 2.416667 P1 6.500000 0.125000 0.725000 P2 8.800000 INFINITY 0.831250 P3 7.000000 2.416667 0.250000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 21600.000000 3200.000000 1600.000000 3 15000.000000 INFINITY 2800.000000 4 18000.000000 2000.000000 2800.000000 5 6000.000000 INFINITY 4000.000000 6 4000.000000 1142.857178 2285.714355 7 3500.000000 INFINITY 2100.000000


Ciclo 2008 1 74

a. ¿Qué departamentos limitan la capacidad de manufactura de Bus? b. Determine el valor de una hora extra en cada uno de los departamentos. c. ¿Qué pasa si Bus debe obtener una unidad adicional del componente 2? d. Interprete el valor del costo reducido de la variable P2.

46. Marketing Survey (MSI) se especializa en evaluar la reacción del consumidor a

productos, servicios y campañas publicitarias nuevas. Un cliente solicitó la asistencia del MSI para determinar la reacción del consumidor a un producto doméstico recién comercializado. Durante las reuniones con los clientes, MSI acordó efectuar entrevistas personales de puerta en puerta para obtener respuestas en hogares con niños y hogares sin niños. Además, MSI aceptó hacer entrevistas por la mañana y por la tarde. Específicamente, el contrato del cliente exigía que MSI realizara mil entrevistas bajo los siguientes lineamientos: Entrevistar al menos a 400 hogares con niños. Entrevistar al menos a 400 hogares sin niños. La cantidad total de hogares entrevistados durante la tarde debe ser al menos

igual a la cantidad de hogares entrevistados durante la mañana. Al menos el 40% de las entrevistas para los hogares con niños deben

realizarse durante la tarde. Al menos el 60% de las entrevistas para hogares sin niños deben realizarse

durante la tarde. Debido a que la entrevista para hogares con niños requiere tiempo adicional del entrevistador y a que los entrevistadores vespertinos se les paga más que a los matutinos, el costo varía con el tipo de entrevista. Con base de estudios previos, las estimaciones de los costos de las entrevistas son las siguientes:

Hogar Costo de la entrevista Mañana Tarde Con niños $20 $25 Sin niños $18 $20

Con el objeto de determinar el plan de entrevistas que satisfaga los requerimientos del contrato a un costo mínimo, se presenta a continuación el modelo matemático lineal correspondiente, su solución óptima, así como el análisis de sensibilidad utilizando el programa LINDO.

CM ... cantidad de entrevistas CON NIÑOS por la MAÑANA CT ... cantidad de entrevistas CON NIÑOS por la TARDE SM ... cantidad de entrevistas SIN NIÑOS por la MAÑANA ST ... cantidad de entrevistas SIN NIÑOS por la TARDE MIN 20 CM + 25 CT + 18 SM + 20 ST

SUBJECT TO 2) CM + CT + SM + ST = 1000 3) CM + CT >= 400 4) SM + ST >= 400 5) - CM + CT - SM + ST >= 0 6) -0.4 CM + 0.6 CT >= 0 7) - 0.6 SM + 0.4 ST >= 0


Ciclo 2008 1 75

OBJECTIVE FUNCTION VALUE 1) 20320.00 VARIABLE VALUE REDUCED COST CM 240.000000 0.000000 CT 160.000000 0.000000 SM 240.000000 0.000000 ST 360.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -19.200000 3) 0.000000 -2.800000 4) 200.000000 0.000000 5) 40.000000 0.000000 6) 0.000000 -5.000000 7) 0.000000 -2.000000 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE CM 20.000000 5.000000 4.666667 CT 25.000000 INFINITY 5.000000 SM 18.000000 2.000000 INFINITY ST 20.000000 4.666667 2.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2) 1000.000000 INFINITY 200.000000 3) 400.000000 100.000000 400.000000 4) 400.000000 200.000000 INFINITY 5) 0.000000 40.000000 INFINITY 6) 0.000000 240.000000 20.000000 7) 0.000000 240.000000 20.000000

Responder sustentando adecuadamente, las siguientes preguntas: a. Describa la solución óptima del problema. b. ¿Qué porcentaje del costo total está destinado a cubrir los honorarios de los

entrevistadores matutinos? c. Interprete administrativamente el valor de 200 que figura en la columna

SLACK OR SURPLUS. d. ¿Qué pasa si la exigencia del cliente fuese realizar 1500 entrevistas? e. ¿Qué pasa si se produce un incremento del 10% en el costo de cada

entrevista en hogares con niños por la tarde? f. ¿Qué pasa si el cliente exigiese que la cantidad de entrevistas por la tarde

fuese mayor que la cantidad de entrevistas por la mañana en por lo menos 30 unidades?

g. ¿Qué pasa si el cliente solicita disminuir las entrevistas en hogares con niños en 50?

h. ¿Qué pasa si se agrega la restricción: “la cantidad de entrevistas durante la tarde a hogares sin niños debe ser mayor a la cantidad de entrevistas durante la mañana a hogares con niños”?


Ciclo 2008 1 76

i. ¿Qué pasa si el costo de la entrevista a hogares con niños en la mañana fuera de S/.23 para las primeras 200 entrevistas y S/.16 para las entrevistas adicionales a las primeras 200?

Nota: Las respuestas a las preguntas ¿Qué pasa si ...? deberán indicar si habría o no un cambio en el Plan Optimo de Entrevistas y en el Costo Total asociado a ella. En el caso que haya un cambio en el Costo Total se deberá calcular su nuevo valor.

47. ABC S.A. fabrica y vende muebles y tiene, entre otras, una línea de jardín. Actualmente se producen en esta línea sillas, bancos y mesas. Los productos se fabrican en un proceso de dos etapas, en el departamento de doblado de tubos y el de armado. La siguiente tabla muestra el tiempo requerido (en horas) para la fabricación de cada producto por departamento y la disponibilidad de tiempo de cada departamento (en horas):

Proceso Doblado de tubos Capacidad Silla Banco Mesa actual

Doblado de tubos 1,2 1,7 1,2 1 000 Armado 0,8 0,0 2,3 1 200

El beneficio asociado a la fabricación y ventas de una unidad de cada ítem es $ 300 por silla, $ 300 por banco y $ 500 por mesa. La empresa desea establecer el plan de producción para la próxima temporada de ventas. Se estima que es posible vender todo lo que produzca, sin embargo, la producción está restringida por la materia prima disponible. La empresa dispone sólo de 2000 Kg. de tubos para muebles y los productos requieren las siguientes cantidades de este material de 2 Kg. por silla, 3 Kg. por banco y 4.5 Kg. por mesa. El administrador de la empresa ha formulado el siguiente problema de programación lineal con el fin de optimizar el plan de producción. Resolviéndolo, mediante el programa LINDO, en el computador local, el administrador obtuvo lo siguiente: Max 300 X1 + 300 X2 + 500 X3 subject to

1.2 X1 + 1.7 X2 + 1.2 X3 <= 1000 0.8 X1 + 2.3 X3 <= 1200 2.0 X1 + 3.0 X2 + 4.5 X3 <= 2000

end



X1 X2 X3

700.000000 0.000000

133.333333

0.000000 138.333333 0.000000

ROW SLACK OR

SURPLUS DUAL PRICES


Ciclo 2008 1 77

2) 3) 4)

0.000000 333.333333 0.000000

116.666666 0.000000 80.000000



CURRENT COEF

ALLOWABLE INCREASE

ALLOWABLE DECREASE

X1 X2 X3

300.000000 300.000000 500.000000

200.000000 138.333333 175.000000

77.777777 INFINITY

200.000000


CURRENT RHS

ALLOWABLE INCREASE

ALLOWABLE DECREASE

2 3 4

1000.000000 1200.000000 2000.000000

200.000000 INFINITY

555.555555

466.666666 333.333333 333.333333

a. ¿Cuál es el programa óptimo de producción? b. ¿Qué beneficio total se obtiene? c. ¿Qué valor tendría como máximo la programación de 100 horas extras en el

departamento de doblado? ¿Qué valor tendrían como máximo la programación de 20 horas extras en el departamento de armado? ¿Y 10 kilogramos más de materia prima?

d. Un distribuidor local ofrece materia prima a $ 60 por Kg. ¿Es conveniente comprar? Si fuera conveniente, ¿en cuánto aumentaría el beneficio al comprar 500 kilogramos y usarlas en forma óptima?

e. Es posible arrendar el departamento de doblado a $ 150 la hora. Si la empresa arrienda 200 horas a este precio. ¿En cuánto se modifica el beneficio total?

f. Si fuera posible aumentar más la disponibilidad de uno de los recursos, ¿cuál escogería y en qué cantidad? Explique.

g. Estudios de mercado sugieren la fabricación de un nuevo tipo de silla (aparte de los productos que se producen) que requeriría, 1.8 horas de doblado, 0.5 horas de armado y 1.3 Kg. de materia prima. Explique cómo reformularía el modelo y cómo hallaría el beneficio unitario que debería tener este producto de modo de hacer conveniente su fabricación en esta temporada.

h. Si el beneficio unitario de cada silla fuera $ 400 si 0 ≤ X1 ≤ 500 (por las primeras quinientas) $ 250 si X1 > 500 (por las unidades adicionales a 500)

¿Qué puede decir de la solución óptima? 48. El departamento de mercadeo de HOME S.A. está enfrentado el problema de

cómo promover efectivamente sus juguetes en la próxima campaña navideña. Hay tres medios de comunicación básicos a través de los cuales la firma puede promover sus juguetes: prensa, radio y televisión. El costo por anuncio en cada medio publicitario y el tamaño promedio de audiencia son los siguientes:

Medio Costo por Audiencia por anuncio

Publicitario Anuncio ($) Total Niños Prensa 4 000 20 000 1 000


Ciclo 2008 1 78

Radio 3 000 14 000 1 000 Televisión 8 000 36 000 3 000

El gerente del departamento de mercadeo, ha decidido que la función objetivo de la firma debería ser "maximizar la audiencia de las personas expuestas a la publicidad", y que la audiencia de niños sea por lo menos de 6,000. La firma HOME S.A. ha dispuesto un presupuesto de $ 20,000 para la publicidad de los juguetes. Además considera que las utilidades en dólares están perfectamente correlacionados con el nivel de audiencia total que alcance; es decir, si por ejemplo alcanzara una audiencia total de 50 000 personas, espera obtener utilidades totales por valor de $ 50 000.

Max 20000 P + 14000 R + 36000 T subject to 4000 P + 3000 R + 8000 T <= 20000 1000 P + 1000 R + 3000 T >= 6000 end



P R T

3.000000 0.000000 1.000000

0.000000 0.000000 0.000000

ROW SLACK OR

SURPLUS DUAL PRICES

2) 3)

0.000000 0.000000

6.000000 -4.000000



CURRENT COEF

ALLOWABLE INCREASE

ALLOWABLE DECREASE

P Q R

20000.000000 14000.000000 36000.000000

INFINITY 0.00000

3999.99999

0.000000 INFINITY 0.000000


ROW

CURRENT RHS

ALLOWABLE INCREASE

ALLOWABLE DECREASE

2 3

20000.000000 6000.000000

3999.999999 1499.999999

4000.000000 999.999999

De acuerdo a los resultados reportados se pide: a. Explicite la solución completa y las holguras interpretando las magnitudes. b. Si existe otra mezcla óptima de publicidad P = 2 y R = 4, ¿existe alguna

razón para preferir alguna? Explique. c. Halle el rango de variación del presupuesto de publicidad y de la audiencia

de niños, en forma independiente, para que la solución hallada en (a) no varíe.


Ciclo 2008 1 79

d. Si la audiencia total de los medios publicitarios es aproximada. Hallar el rango de variación de la audiencia total de cada medio publicitario, en forma independiente, para que la solución hallada en (a) no varíe.

e. Interprete los valores de los precios duales. f. Si se dispusiera de $ 4000 de presupuesto adicional con un préstamo

bancario, ¿cuánto estaría dispuesto a pagar en total en dólares de intereses? 49. Quesos Andinos S. A. produce dos quesos crema: Rico y Súper, mezclando el

queso mantecoso suave con el queso mantecoso fuerte. Los quesos crema se empacan en recipientes de 0,4 Kg que después se venden a distribuidores en todo el país. El queso crema Rico contiene 80% de queso mantecoso suave y 20% de queso mantecoso fuerte. La mezcla Súper contiene 60% de queso mantecoso suave y 40% de queso mantecoso fuerte. Este año, una cooperativa lechera local ha ofrecido entregar hasta 8 100 Kg. de queso mantecoso suave a S/. 12 por Kg. y hasta 3 000 Kg. de queso mantecoso fuerte a S/. 14 por Kg. El costo de mezclar y empacar estos quesos crema, excluyendo el costo del queso mismo, es de S/. 0,20 por recipiente. Cada recipiente de Rico se vende a S/. 6,20 y cada recipiente Súper a S/. 6,50. A continuación se presenta el modelo de programación lineal desarrollado que permite estimar el número de recipientes de cada tipo de queso el presente año que deberá producir la Quesos Andinos S.A. para maximizar sus utilidades, así como el reporte del modelo obtenido en LINDO

. Max 1.04 X1 + 1.18 X2

St 0.32 X1 + 0.24 X2 <= 8100 0.08 X1 + 0.16 X2 <= 3000 end



X1 X2

18000.00 9750.00

0.000000 0.000000

ROW SLACK OR

SURPLUS DUAL PRICES

2) 3)

0.00 0.00

2.25 4.00



CURRENT COEF

ALLOWABLE INCREASE

ALLOWABLE DECREASE

X1 X2

1.040 1.180

0.533 0.900

0.45 0.40


ROW

CURRENT RHS

ALLOWABLE INCREASE

ALLOWABLE DECREASE

2 3

8100.00 3000.00

3900.00 2400.00

3600.00 975.00


Ciclo 2008 1 80

Dado que los miembros del directorio de la Quesos Andinos S.A. no están familiarizados con la términos utilizados en un reporte generado por el LINDO, le han pedido a usted que, a manera de un breve informe, absuelva de la manera más precisa las siguientes interrogantes: a. ¿Cuál es el plan de producción óptimo sugerido y cuál sería la utilidad que

obtendríamos si ponemos dicho plan en práctica? b. ¿Cuál(es) es(son) el(los) recurso(s) limitante(s)? Sustente. c. Si pudiera aumentar la disponibilidad de un recurso limitante, ¿cuál sería el

más adecuado de aumentar? d. Una empresa lechera ha ofrecido vender queso mantecoso suave, ¿qué

cantidad se debería comprar para aumentar la producción? Sustente. e. El ingreso de un nuevo competidor nos ha obligado a rebajar el precio de

queso crema Súper en un 10%, ¿qué consecuencias se deben esperar? f. ¿Qué significado tiene los costos reducidos iguales a cero?

50. Manwalk S.A fabrica intercomunicadores portátiles. El nuevo producto de la

empresa tiene largo alcance (50 kilómetros) y es adecuado para una diversidad de usos comerciales y personales. Los canales de distribución utilizados por la empresa son:

Distribuidores de equipos marinos. Distribuidores de equipos de oficina. Tiendas nacionales de menudeo. Pedidos por correo.

Debido a los diferentes costos de distribución y promocionales, la rentabilidad del producto variará según el canal de distribución. Además el costo de publicidad y el esfuerzo de ventas personales requerido variarán de acuerdo con los canales de distribución, tal como se muestra:

Canal de distribución

Utilidad por unidad vendida

(dólares)

Costo de publicidad por unidad vendida

(dólares)

Esfuerzo de personal por unidad vendida

(horas) Distribuidores de equipos marinos 90 10 2 Distribuidores de equipos de oficina. 84 8 3 Tiendas nacionales de menudeo 70 9 3 Pedidos por correo. 60 15 Ninguna

La empresa ha asignado un presupuesto de publicidad de $5 000 y está

disponible de 1 800 horas como máximo para el esfuerzo de ventas. La administración también ha decidido asignar 600 unidades durante el

periodo de producción actual. Finalmente un contrato vigente con las tiendas nacionales de menudeo

requiere que por lo menos se distribuyan 150 unidades a través de este tipo de canal de distribución.


Ciclo 2008 1 81

Para establecer una estrategia de distribución de los intercomunicadores que maximice la rentabilidad de la producción, se ha propuesto un modelo de programación lineal que ha sido resuelto en LINDO:

MAX 90 X1 + 84 X2 + 70 X3 + 60 X4 SUBJECT TO 2) 10 X1 + 8 X2 + 9 X3 + 15 X4 <= 5000 3) 2 X1 + 3 X2 + x3 <= 1800 4) X1 + X2 + X3 + X4 = 600 5) X3 >= 150 END OBJECTIVE FUNCTION VALUE 1) 48450.00 VARIABLE VALUE REDUCED COST X1 25.000000 0.000000 X2 425.000000 0.000000 X3 150.000000 0.000000 X4 0.000000 45.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.000000 3) 325.000000 0.000000 4) 0.000000 60.000000 5) 0.000000 -17.000000 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 90.000000 15.000000 6.000000 X2 84.000000 6.000000 12.000000 X3 70.000000 17.000000 INFINITY X4 60.000000 45.000000 INFINITY RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 5000.000000 850.000000 50.000000 3 1800.000000 INFINITY 325.000000 4 600.000000 6.250000 85.000000 5 150.000000 50.000000 150.000000

De acuerdo a la situación planteada se pide: a. Identifique en el modelo desarrollado las variables, la función objetivo y las

restricciones. b. Identifique en el modelo desarrollado las variables, la función objetivo y las

restricciones. c. ¿Cuál es la estrategia de distribución propuesta por el modelo? d. ¿Cuál el presupuesto de publicidad asignado a cada canal de distribución? e. Interprete el significado de las holguras o excedentes de las restricciones. f. Respecto al contrato vigente con las tiendas nacionales de menudeo, ¿usted

recomendaría aumentar o disminuir la cantidad de unidades que se distribuyen mediante este canal? Sustente.

g. Interprete el valor del costo reducido de x4.


Ciclo 2008 1 82

Problemas de aplicaciones especiales

51. Enigma S.A fabrica unidades de procesamiento central CPU para computadoras

personales. La CPU se fabrican en tres plantas (P1, P2 y P3) y se almacenan en 5 almacenes (A1, A2, A3, A4 y A5) para su distribución posterior. La siguiente tabla muestra el número de CPUs disponibles en cada planta, el número de CPUs requeridos por cada almacén y los costos de embarque (soles por unidad)

Planta Almacén CPU

A1 A2 A3 A4 A5 disponibles P1 10 20 5 9 10 9 000 P2 2 10 8 30 6 4 000 P3 1 20 7 10 4 8 000

CPU requeridos 3 000 5 000 4 000 6 000 3 000 21 000

a. Elabore el diagrama de red. b. Desarrolle el modelo que permita determinar la cantidad a transportar desde

cada una de las plantas a cada uno de los almacenes para minimizar el costo de embarque.

c. Encuentre la solución mediante el programa LINDO. d. Elabore el diagrama de red con la solución obtenida

52. Industria Química S.A. (IQSA) produce un material especial con base en

petróleo, que actualmente es muy escaso. Cuatro de los clientes de IQSA ya han colocado pedidos, que en conjunto exceden la capacidad combinada de las dos plantas de IQSA. La administración de IQSA se enfrenta al problema de decidir cuántas unidades deberá suministrar a cada uno de los clientes. Dado que los cuatro clientes son de distintas ramas industriales, es posible cargar un precio diferente debido a las diferentes estructuras de precios en las industrias. Después de considerar el precio, los costos de producción y los de transporte, IQSA ha definido la siguiente utilidad por unidad para cada alternativa planta-cliente:

Planta Cliente

D1 D2 D3 D4 Callao 32 34 32 40 Vitarte 34 30 28 38

La capacidad de producción de la planta de Callao es de 5 000 unidades y la de Vitarte es de 3 000 unidades. Los pedidos de los clientes es:

Cliente D1 D2 D3 D4 Pedido 2 000 5 000 3 000 2 000

a. Elabore el diagrama de red de la situación planteada. b. Desarrolle el modelo de programación lineal para el problema planteado. c. Usando el programa LINDO obtenga la solución del problema. d. Elabore el diagrama de red indicando en él la solución obtenida.


Ciclo 2008 1 83

53. Un producto es manufacturado en tres plantas y embarcado a tres almacenes. Los costos de transporte en dólares por unidad se muestran en la siguiente tabla.

Planta Almacén Capacidad

A1 A2 A3 de la planta P1 20 16 24 300 u P2 10 10 8 500 u P3 12 18 10 100 u

Demanda de cada almacén 200 u 400 u 300 u 900 u

a. Desarrolle el modelo de programación lineal para minimizar el costo de trasporte. Utilice adecuadamente la anotación de las variables y la presentación del modelo.

b. Si la ruta de la planta P3 al almacén A1 tiene una capacidad de 50 unidades debido a disponibilidad limitada de espacio en el modo de transporte usado, ¿cómo cambiaría la formulación del problema en comparación con el inciso (a)?

c. Si la ruta de la planta P2 al almacén A2 no puede utilizarse por razones de seguridad, ¿cómo cambiaría la formulación del problema en comparación con el inciso (a)?

d. Si los valores mostrados en la tabla representan utilidad por unidad producida en una planta y vendida a un almacén, ¿cómo cambiaría la formulación del problema en comparación con el inciso (a)?

e. Si la capacidad de la planta P1 es en realidad 500 unidades, ¿qué consecuencias habría en la formulación y la solución del problema (a)?

f. Si la demanda del almacén A3 es en realidad 500 unidades, ¿qué consecuencias habría en la formulación y la solución del problema (a)?

54. Enigma Consulting Group S.A. tiene dos asesores, Abelardo y Belisario, que

pueden programarse para trabajar con clientes hasta un máximo de 160 horas durante las cuatro siguientes semanas. Un tercer asesor, Casimiro, tiene ya planeadas algunas asignaciones administrativas y está disponible para los clientes un máximo de 140 horas durante las cuatro semanas siguientes. La empresa tiene cuatro clientes con proyectos en proceso. Las necesidades horarias estimadas de cada uno de los clientes durante el periodo de cuatro semanas son:

Cliente A B C D Horas 180 75 100 85

Las tarifas horarias para la combinación asesor-cliente varían y se basan en varios factores, incluyendo el tipo de proyecto y la experiencia del asesor. Las tasas (dólares por hora) de cada combinación asesor-cliente son:

Asesor Cliente A Cliente B Cliente C Cliente D Abelardo 100 125 115 100 Belisario 120 135 115 120 Casimiro 155 150 140 130

a. Elabore el diagrama de red de la situación planteada.


Ciclo 2008 1 84

b. Si Enigma Consultin Group S.A. quiere maximizar sus ingresos, desarrolle el modelo de programación lineal de la situación planteada.

c. Nueva información indica que Abelardo no tiene experiencia necesaria para que lo programen con los clientes B y C. Si no se permite que Abelardo asesore al cliente B y que no asesore más de 10 horas al cliente C, indique las modificaciones que se tendrá que hacer al modelo de programación lineal desarrollado anteriormente para incorporarle la nueva información?

55. Se debe decidir cuál de cuatro ejecutivos debe asignarse a cada uno de cuatro

clientes mayores. En la siguiente tabla se presentan los costos estimados de las asignaciones de cada ejecutivo:

Ejecutivo Cliente

1 2 3 4 A 15 19 20 18 B 14 15 17 14 C 11 15 15 14 D 21 24 26 24

Por razones de rotación de personal no es posible asignar al ejecutivo A al cliente 1 y al ejecutivo B al cliente 3. Determine el modelo de programación lineal para el modelo planteado.

56. La gerencia de Enigma S.A. quiere asignar a cuatro ejecutivos para que visiten e

inspeccionen las cuatro plantas ubicadas en provincias. Los costos de asignación de cada ejecutivo para la visita a determinada planta se muestran en el siguiente cuadro:

Ejecutivo Planta

Tacna Huánuco Cusco Chiclayo Finanzas 24 10 21 11 Mercadotecnia 14 22 10 15 Operaciones 15 17 20 19 Personal 11 19 14 13

a. Desarrolle el diagrama de red de la situación. b. Encuentre la solución óptima de asignación de los ejecutivos a cada planta

de Enigma S.A. de tal manera que se minimice el costo. 57. Una empresa de investigación de mercados tiene tres clientes, cada uno de los

cuales ha solicitado que la empresa lleve a cabo una encuesta de muestreo. A estos tres proyectos se pueden asignar cuatro especialistas. Sin embargo, los especialistas 1, 2 y 3 están muy ocupados y cada uno de ellos puede manejar sólo un cliente; en cambio el profesional 4 podría manejar hasta dos clientes. Por política de la empresa, el profesional 2 no puede ser asignado al cliente C. Los datos que siguen muestran el número de horas requerido por cada profesional para terminar cada una de las tareas; las diferencias de tiempo representan la experiencia y capacidad de cada uno de los profesionales.


Ciclo 2008 1 85

Especialista Cliente A B C

1 150 210 270 2 170 230 220 3 180 230 225 4 160 240 230

Formule el modelo de programación lineal para la situación planteada.

58. Javier, Carlos y Víctor están disponibles para efectuar ciertos trabajos. Cada persona debe efectuar sólo un trabajo en el tiempo asignado. Hay cuatro trabajos por hacer. La matriz de pagos de cada hombre asignado a cada trabajo es como sigue:

Soldar Enmarcar Trazar Alambrar

Javier 4 2 5 3 Carlos 1 3 4 2 Víctor 3 3 1 5

a. ¿Qué hombre debe asignarse a qué trabajo? b. Suponga ahora que cada hombre puede efectuar hasta dos trabajos, ¿qué

deben hacer cada uno de ellos?

59. Un bufete de abogados ha aceptado tres nuevos casos, cada uno de los cuales puede ser llevado adecuadamente por cualquiera de los cuatro asociados más recientes. Debido a la diferencia en experiencia y práctica, los abogados emplearán distintos tiempos en los casos. Uno de los asociados más experimentados ha estimado las necesidades de tiempo (en horas) como sigue:

Caso 1 Caso 2 Caso 3

Abogado 1 145 122 130 Abogado 2 80 63 85 Abogado 3 121 107 93 Abogado 4 118 83 116

Se desarrolló el modelo de programación lineal de la situación planteada y mediante el LINDO se obtuvieron los resultados que se muestran a continuación:

Min 145 a1c1 + 122 a1c2 + 130 a1c3 + 80 a2c1 + 63 a2c2 + 85 a2c3 + 121 a3c1 + 107 a3c2 + 93 a3c3 + 118 a4c1 + 83 a4c2 + 116 a4c3 subject to

a1c1 + a1c2 + a1c3 <= 1 a2c1 + a2c2 + a2c3 <= 1 a3c1 + a3c2 + a3c3 <= 1 a4c1 + a4c2 + a4c3 <= 1 a1c1 + a2c1 + a3c1 + a4c1 = 1 a1c2 + a2c2 + a3c2 + a4c2 = 1 a1c3 + a2c3 + a3c3 + a4c3 = 1

end


Ciclo 2008 1 86

OBJECTIVE FUNCTION VALUE 1) 256.0000 VARIABLE VALUE REDUCED COST A1C1 0.000000 145.000000 A1C2 0.000000 122.000000 A1C3 0.000000 130.000000 A2C1 1.000000 80.000000 A2C2 0.000000 63.000000 A2C3 0.000000 85.000000 A3C1 0.000000 121.000000 A3C2 0.000000 107.000000 A3C3 1.000000 93.000000 A4C1 0.000000 118.000000 A4C2 1.000000 83.000000 A4C3 0.000000 116.000000 a. Basándose en el modelo propuesto así como en el reporte proporcionado por

el programa LINDO, redacte un breve informe al Directorio del buffet de abogados donde dé a conocer la solución óptima del problema.

b. Añadir al modelo la restricción: “… por razones de política del buffet el segundo abogado no puede ser asignado al caso 1 al mismo tiempo que el abogado 4 al caso 2”.

c. El añadir la restricción planteada en el inciso b, ¿obligará redactar otro informe distinto al presentado en el inciso a? Sustente.

60. El sistema de distribución para la Logistic Company S.A. está formado por tres plantas, dos almacenes y cuatro clientes. La capacidad de las plantas y los costos de embarque (en dólares) desde cada una de las plantas a cada uno de los almacenes son:

Almacén 1 Almacén 2 Capacidad

Planta 1 4 7 450 Planta 2 8 5 600 Planta 3 5 6 380

La demanda de clientes y los costos unitarios de embarque (en dólares) de cada uno de los almacenes a cada uno de los clientes son:

Cliente 1 Cliente 2 Cliente 3 Cliente 4 Almacén 1 6 4 8 4 Almacén 2 3 6 7 7 Demanda 300 300 300 400

Además se sabe que están permitidos embarques entre los dos almacenes a 2 dólares la unidad y que se pueden efectuar embarques directos de la planta 3 al cliente 4 a un costo de 7 dólares por unidad. a. Desarrolle una representación en red para la situación planteada. b. Formule el modelo de programación lineal del problema.

sep inv. operaciones usmp-muy bueno.pdf

Documents