• Author / Uploaded
• Leticia Tisnado

Citation preview

Clases 4, 5 y 6. PROGRAMACIÓN LINEAL (P.L) 2.1 DEFINICIÓN DE PROGRAMACIÓN LINEAL (P.L) Técnica matemática para determinar la mejor asignación de los recursos limitados de una organización para el desarrollo o producción de bienes y servicios en una forma óptima. 2.2 REQUERIMIENTOS DE UN MODELO DE PROGRAMACIÓN LINEAL (P.L) Definir claramente una función objetivo en forma matemática. Las restricciones o limitaciones se expresan en forma matemática a través de ecuaciones o desigualdades. Las ecuaciones y desigualdades deben describir el problema en forma lineal. Las variables del problema deben interrelacionarse. Debe existir un suministro limitado de recursos. 2.3 FORMULACIÓN CANÓNICA DE LA PROGRAMACIÓN LINEAL (P.L) Características Función Objetivo: Maximizar Z Restricciones funcionales: Tipo menor o igual Cj : Utilidad o ganancia unitaria Función Objetivo: Maximizar Z = C1X1 + C2X2 + C3X3 + ..… + Cn Xn sujeta a: a11X1 + a12X2 + a13X3 + ..… + a1n Xn b1 a21X1 + a22X2 + a23X3 + ..… + a2n Xn b2 a31X1 + a32X2 + a33X3 + ..… + a3n Xn b3

Restricciones Funcionales

::::::::::::::::::::::::::::::::::::::::::::::

am1X1 + am2X2 + am3X3 +....+ amn Xn bm

X1, X2 , X3 , ..….... Xn 0

Restricción de No Negatividad

La formulación anterior puede presentarse en el siguiente cuadro de datos: Actividades 1

2

3

...

n

Disponibilidad de recursos

Recursos 1 2 3 . . . . m Utilidades Variables de decisión

a11 a21 a31 . . . . am1 c1 X1

a12 a22 a32 . . . . am2 c2 X2

a13 . . . a23 . . . a33 . . . . . . . am3 . . . c3 X3 . . .

a1n a2n a3n . . . . . amn cn Xn

b1 b2 b3 . . . . . .

bm

TERMINOLOGÍA m = Recursos limitados. n = Actividades competitivas para ubicar recursos. Xj = Cantidad de cada actividad “j” (variables de decisión o incógnitas del problema). cj = Ganancia unitaria para cada actividad “j”. bi = Cantidad del recurso “i” disponible. aij= La cantidad consumida del recurso “i” por cada unidad de actividad “j”. Z = Medida de efectividad (Función Objetivo). El número de restricciones funcionales depende del número de recursos (m). El número de restricciones de no negatividad está en función del número de actividades (n). Por lo tanto, el número de restricciones funcionales y de no negatividad es igual a m+n. Pueden existir otros tipos de restricciones, dependiendo de las condiciones del problema a resolver. 2.4 FORMAS NO CANÓNICAS Función Objetivo: Minimizar Z Restricciones funcionales: Tipo mayor o igual Cj : Costo unitario Función Objetivo: Maximizar Z Restricciones funcionales: Tipo menor o igual, mayor o igual o de igualdad Cj : Utilidad o ganancia unitaria. Función Objetivo: Minimizar Z Restricciones funcionales: Tipo menor o igual, mayor o igual o de igualdad Cj : Costo unitario 2.5 PASOS PARA CONSTRUIR EL MODELO DE PROGRAMACIÓN LINEAL (P.L) 1-Definir la variable de decisión del problema. 2-Definir la función objetivo en términos de su variables de decisión. Esta función objetivo consiste en escoger valores para las variables tales que maximicen la utilidad o minimicen costos. 3-Definir las restricciones usando las variables de restricción. 4-Restringir todas las variables para que sean no negativas. Ejemplos Ilustrativos: 1. La compañía Reddy Mikks, produce pinturas para interiores y exteriores. La tabla siguiente proporciona los datos básicos del problema. m1, m2, son las materias prima para elaborar pintura de interiores y exteriores.

Toneladas de Materia prima Actividades Recursos Materia prima m1 Materia prima m2 Utilidad por toneladas (miles$)

Pintura para exteriores 6 1

Pintura para interiores 4 2

5

4

Disponibilidad diaria máxima (toneladas) 24 6

La demanda diaria de pintura para interiores no puede ser mayor de una tonelada (resta) más que la de exteriores. También la demanda máxima diaria de pintura para interiores es de dos toneladas. Formule el modelo de programación lineal a fin de determinar la mezcla óptima (la mejor) de productos para exteriores e interiores que maximice la utilidad total. Solución: 1. Variables de decisión Sea: X1= Cantidad de toneladas producidas de pintura para exteriores. X2= Cantidad de toneladas producidas de pintura para interiores. 2. Función Objetivo Max Z (x1, x2) = 5x1+ 4x2 3. Restricciones: - Uso de materiales para ambas pinturas  Disponibilidad * - Demanda 4.

**

- No negatividad

***

6x 1  4x 2  24

*

x 1  2x 2  6

*

x2  x1

 1

x2

 2

x1, x 2  0

** ** ***

1 2 3 4 5

Restricciones Funcionales Restricciones de demanda Restricción de No Negatividad

2- Una empresa manufacturera y vende 2 productos( A, B) obteniendo una utilidad de por unidad del

$12

producto 1, y $4 por unidad del producto 2 que se venden. Las horas de

trabajo que se requieren para los productos en c/u de los departamentos de producción se muestran en el cuadro siguiente:

Datos de Producción (Horas de trabajo / Unidad) Producto Departamento

A

B

Disponibilidad

1

1

2

800 horas

2

1

3

600 horas

3

2

3

2000 horas

$12

$4

Utilidad por Unidad de producto

Los supervisores de estos departamentos. Han estimado que durante el próximo mes estén disponibles las siguientes horas de trabajo: 800 hrs. en el depto. 1 ;

600 hrs.

en el 2; y

2000 hrs. en el 3, la compañía quiere maximizar sus utilidades. ¿Formule el modelo de P. L ? SOLUCIÓN: Paso 1: Identificar las variables de decisión: Sea X1: Número de unidades del producto A. a fabricar el próximo mes X2: Número de unidades del producto B, a fabricar el próximo mes Paso 2: Identificar la función objetivo (max. ó min) Maximizar Z = 12X1 + 4X2. Paso 3: Identificar Restricciones: Sujeto a

1x 1  2x 2  800

1

1x 1  3x 2  600

2

2x 1  3x 2  2000

3

Restricciones Funcionales

Paso 4:

x1, x 2  0

5

Restricción de No Negatividad

3- Se procesan tres productos a través de tres operaciones diferentes los tiempos (en minutos) requeridos por unidad de cada producto, la capacidad diaria de las operaciones

( en minutos por día ) y el beneficio por unidad vendida de cada producto son como sigue: Tiempo por Unidad ( Minutos) Productos Operación

Producto 1

Producto 2

Capacidad de Operación

Producto 3

(Minutos de cada día) 1

1

2

1

430

2

3

0

2

460

3

1

4

0

420

3

2

5

Ganancia por Unidad ($)

Suponiendo que todas las unidades producidas se vendan, formule el modelo de P. L que determine la producción diaria óptima para los tres productos que maximice los beneficios. SOLUCIÓN Paso 1: Identificar las variables de decisión: Sea X1: Número de unidades del producto 1 a producir por día. X2: Número de unidades del producto 2 a producir por día. X3: Número de unidades del producto 3 a producir por día. Paso 2: Identificar la función objetivo (max. ó min) Maximizar Z = 3X1 + 2X2+5X3 Paso 3: Identificación de Restricciones: Sujeto a:

x 1  2x 2  x 3  430

1

x 1  0x 2  2x 3  460

2

x 1  4x 2  0x 3  420

3

x1, x 2 , x 3  0

4 Restricción de No Negatividad

Restricciones Funcionales

Paso 4:

4-Una lata de 16 onzas de alimento para perros debe contener proteínas, carbohidratos y grasas en las siguientes cantidades mínimas:

Proteínas 3 onzas. ; Carbohidratos 5 onzas. ;

Grasas 4 onzas. .

Se va a mezclar 4 tipos de alimentos en diversas proporciones para producir una lata de alimentos para perro que satisfagan los requerimientos mínimos. Los contenidos y los costos de 16 onzas de cada alimento se dan en el cuadro siguiente:

Contenido y Costo por cada 16 onzas de Alimento. Contenido en

Contenido de

Contenido

Alimento

Proteinas (onz)

Carbohidratos (onz)

Grasas (onz)

Costo

1

3

7

5

$4

2

5

4

6

$6

3

2

2

6

$3

4

3

8

2

$2

Formule un modelo de P. L tal que se minimicen los costos y que se satisfagan los requerimientos mínimos. Solución: Paso1: Identificar las variables de decisión. Sea X1: cantidad de alimento 1 que se utiliza para fabricar 1 lata de 16 onzas. Sea X2: cantidad de alimento 2 que se utiliza para fabricar 1 lata de 16 onzas. Sea X3: cantidad de alimento 3 que se utiliza para fabricar 1 lata de 16 onzas. Sea X4: cantidad de alimento 4 que se utiliza para fabricar 1 lata de 16 onzas. Paso 2: Planteamiento de la función objetivo Minimizar Z = 4x1  6x 2  3x 3  2x 4 Paso 3: Restricciones: Sujeto a

3x 1  5x 2  2x 3  3x 4  3 7x 1  4x 2  2x 3  8x 4  5 5x 1  6x 2  6x 3  2x 4  4 x 1  x 2  x 3  x 4  16

1 2 3 4 5

Restricciones Funcionales

Paso 4:

x 1 , x 2 , x 3 , x 4  0.

6 Restricción de No Negatividad

5-Se desea determinar cuántos codos y ductos se deben producir si se tienen 800 libras de aluminio clase 1 y 500 libras de aluminio clase 2. Comprados en $5 y $10 la libra respectivamente, el problema es decidir el uso óptimo de las 1300 libras de aluminio para maximizar el beneficio obtenido de la producción de codos y ductos. Los ingresos por cada codo son $10 y $30 por cada ducto, los costos de producción por cada codo son $4 y de $12 por ducto. Cada codo usa una libra de aluminio clase 1 y 2 libras de aluminio clase 2. Cada ducto usa 3 libras de aluminio clase 1 y 5 libras de aluminio clase 2. Formule el problema de P. L.

SOLUCIÓN: Observación: En los problemas de optimación solamente los costos variables tienen importancia puesto que los costos fijos ya han sido pagados, lo cual significa que ninguna decisión futura puede afectarlos. Paso 1: Variables de decisión; x1 : Número de codos a ser producidos. x2: Número de ductos a ser producidos. Paso 2: Función objetivo: 800 libras de aluminio clase 1 ($ 5 c/u) 500 libras de aluminio clase 2 ($ 10 c/u) Ingreso por codo $10; costo de producción por codo $4 Ingreso por ducto $30; costo de producción por ducto $12 Maximizar Z = (Ingreso – Costo) x1 + (Ingreso – Costo) x2 Maximizar Z = 6x 1  18x2 Paso 3: Restricciones:

1x 1  3x 2  800

1

2x 1  5x 2  500

2

Restricciones Funcionales

Paso 4:

x1, x 2  0

3 Restricción de No Negatividad

6-Determinar una mezcla óptima de alimento para satisfacer las necesidades

nutritivas de

un animal o de una persona con el costo mínimo. Este ejemplo consiste en la formulación de una dieta para pollos. Suponga que el lote diario requerido de la mezcla son 100 litros la dieta debe contener.

a- Al menos 0.8 % pero no más de 1.2 % de calcio. b- Al menos 22 % de proteínas. c- A lo más 5 % de fibra cruda. Suponga además, que los principales ingredientes utilizados incluyen maíz,

soya y

carbonato de calcio. El contenido nutritivo de estos ingredientes se resume a continuación. Libras por Libra de Ingrediente Ingredientes

Calcio

Proteína

Fibra

Costo ($) x Libra

Carbonato de

0.380

0.00

0.00

0.0164

Maíz

0.001

0.009

0.02

0.0463

Soya

0.002

0.5

0.08

0.1250

calcio

Solución: Sean x1, x2 y x3, las cantidades en libras de Carbonato de calcio, maíz y soya utilizada para producción la mezcla de 100 libras Minimizar x0 = 0.0164x1+0.0463 x2+ 0.1250 x3 Sujeto a: x  x  x  100 1 2 3 0.380x  0.001x  0.002x  0.0012  100 1 2 3 0.380x  0.001x  0.002x  0.008  100 1 2 3 0.09x  0.5x  0.22  100 2 3 0.02x  0.08x  0.05  100 2 3

1 2 Restricciones Funcionales

3 4 5 6

x1, x 2 , x 3  0

Restricción de No Negatividad

Nota; Restricción 1 representa el tamaño del lote. EJERCICIOS PROPUESTOS PARA PRACTICAR 1. Una fábrica posee tres artículos que son procesados en igual número de etapas. El tiempo requerido (minutos) para cada unidad en el proceso de los tres productos y la capacidad de trabajo es como sigue: Actividad Recurso Etapa 1 Etapa 2 Etapa 3

Producto 1 1 3 1

Producto 2 2 0 4

Producto 3

Capacidad por etapa (min/día)

1 2 0

430 460 420

Se requiere determinar el número de unidades al día a fabricar de cada uno de los tres productos, si se sabe que la utilidad por unidad es $3, $2 y $5 respectivamente. Formule el problema como un modelo de PL. 2. Una compañía fabrica dos tipos básicos de teléfonos móviles: sin cámara digital y con cámara digital. Cada uno de ellos requiere el empleo de tres equipos electrónicos A, B y C. Un teléfono sin cámara requiere el empleo del equipo A dos horas al día, una hora en B y una hora en C. Un teléfono con cámara requiere una hora en A, dos horas en B y una hora en C. El número máximo de horas diarias disponibles para el uso de los tres equipos es 180, 160 y 100 respectivamente. La utilidad que se obtiene de los teléfonos sin cámara es de $15 por unidad y la de los teléfonos con cámara es de $25 por unidad. ¿Cuántas teléfonos móviles de cada tipo se deben elaborar para maximizar las utilidades?. Formule el problema como un modelo de PL. 3. Una persona debe seguir una dieta, la cual reúne los siguientes requisitos alimenticios. Al menos 4 mg. de vitamina A Al menos 6 mg. de vitamina B Al menos 3 mg. de vitamina D La dieta está formada por pan, queso, huevos y carne. Se desea conocer las cantidades de cada alimento que cumplan los requisitos a un costo mínimo. La tabla siguiente da los requerimientos por vitamina en mg. así como el costo unitario ($/unidad) de cada alimento:

ALIMENTO Pan Queso Huevos Carne

Contenido en mg. por unidad de alimento VITAMINA A VITAMINA B VITAMINA D 20 18 10 15 10 14 15 40 15 30 35 16

COSTO $0.05 $0.25 $0.15 $0.20

Formule el problema como un modelo de programación lineal. 4. Una compañía fabrica cuatro tipos de productos C, D, E y F que pasan por los departamentos de cepillado, fresado, taladrado y ensamble. El tiempo de producción en cada departamento (horas) se presenta a continuación.

Producto C D E F

Cepillado Ensamble 0.5 1.0 1.0 0.5

Fresado 2.0 1.0 1.0 1.0

Taladrado

0.5 0.5 1.0 1.0

3.0 1.0 2.0 3.0

Contribución por unidad ($) 8 9 7 6

La capacidad por departamento en un mes para los productos C, D, E y F, así como los requerimientos de ventas son: Departamento Cepillado Fresado Taladrado Ensamble

Capacidad (hrs / mes) 1800 2800 3000 6000

Producto

Requerimientos de ventas 100 600 500 400

C D E F

Formule un modelo de programación lineal para maximizar las ganancias de la compañía a través de la combinación óptima de unidades de productos C, D, E y F. 5. Una empresa manufacturera elabora tres productos diferentes en dos plantas. Los datos de tiempo de producción en cada planta, el precio de venta y las demandas máximas se presentan como sigue. Tiempo de producción (hrs) Producto 1 2 3 Capacidad (hrs / sem)

Planta A 0.25 0.33 0.15 100

Planta B 0.20 0.30 0.10 100

Precio de venta unitario $1,000 $1,700 $ 500

Demanda máxima 300 200 100

Conociendo que el costo por hora de operación en la planta A es de $1,000 y en la planta B de $1,500, ¿Cuánto se debe producir en cada planta para obtener la máxima utilidad?. Formule el problema como un modelo de PL.