1/ 24

OBJETIVO GENERAL:

Al finalizar este tema el estudiante estará en capacidad de:

Formular un modelo de programación Lineal, de dos o más variables, comprender su estructura general y suposiciones básicas, así como también las aplicaciones directas al campo de la Economía, Contaduría y Administración.

OBJETIVOS ESPECÍFICOS:

Describir el modelo básico de Programación Lineal, estructura y suposiciones implícitas.

Caracterizar un enfoque general para formular modelos de optimización lineal restringidos.

Ejemplificar aplicaciones de optimización lineal de: producción, portafolios de inversión, Dietas, Planeación agregada, Inventarios, Transporte, Mezcla de materiales, Punto de equilibrio, Corte de Materiales entre otros.

Contenido:

o Elementos Básicos.o Supuestos del modelo de Programación Linealo Formulación del modelo de Programación linealo Sugerencias para la formulación del problema.o Aplicaciones.o Ejercicios Propuestos.

1. Elementos Básicos.

1.1. El modelo básico de Programación Lineal (PL).

Un problema de PL se expresa por:

MAX o MIN Z=F(X)X S

Donde:

X: Representa las variables de decisión X1, X2,...,Xn

Z=F(X), Representa la función objetivo.

2/ 24

S: Representa la región factible del espacio de opciones. Con las variables de decisión continuas1, y siendo F(x) y las restricciones que definen a S, expresiones lineales de esas variables. Recordemos que una expresión Y=F(X) es lineal en las variables cuando las X aparecen elevadas a una potencia de 1 y dicha variable no está dividida ni multiplicada por otra variable. (términos como X2, X/Y y similares son excluidos).

El objeto de un problema de programación lineal es determinar una opción factible que arroje el mejor valor del objetivo, es decir una solución óptima. La solución óptima se caracteriza porque no existe una solución factible que arroje un mejor valor de la función objetivo.

En síntesis la PL, trata el problema de optimizar una función objetivo lineal en una región limitada por restricciones lineales2.

1.2. El modelo general.

Desarrollando el modelo básico, para el caso de minimización, planteado en 1.1, tenemos:

MIN Z=C1X1+ C1X2+ C1X3+.... C1Xn

Sujeto a:

a11X1+a12X2+a13X3+.....+a1nXn ≤ = ≥ b1

a21X1+a22X2+a23X3+....+a2nXn ≤ = ≥ b2

a31X1+a32X2+a33X3+....+a3nXn ≤ = ≥ b3

.

.

.am1X1+am2X2+am3X3+....+amnXn ≤ = ≥ bm

X1, X2, X3, ....Xn ≥ 0

Donde:

Z: Es la función que se desea optimizar, se le denomina función objetivo.

1 Una variable es continua si puede tomar cualquier valor dentro de un intervalo de valores, la estatura de un individuo por ejemplo puede tomar un valor de 1,805 y 1.825 Mts, dependiendo de la precisión de la medición. Trabajar con variables enteras, implica estudiar la programación lineal entera, objeto de estudio de cursos avanzados. 2 F(x), es la expresión matemática del objetivo que se desea optimizar. Al trabajar con un solo objetivo, decimos que estamos ante un modelo uni-objetivo, el caso de la optimización de múltiples objetivos no es trabajado en este curso.

3/ 24

Cn: Los coeficientes C1, C2, C3, Cn son los coeficientes de contribución unitarios [Por ejemplo costo unitario, utilidad por unidad, retorno/Bs, utilidad/ Ha, desperdicio por corte entre otros]. Estos valores se suponen que son conocidos con certeza absoluta.

Xn: Son las variables de decisión a ser determinadas, constituyen atributos susceptibles de cambiar de valor en las distintas opciones de un problema dado.

aij (para i= 1, 2, 3, m y j= 1, 2, 3, n), son llamados los coeficientes tecnológicos, es decir la cantidad de recurso necesaria por cada unidad de variable.3 Similarmente, se suponen que son conocidos con certeza absoluta.

Las inecuaciones representan las restricciones funcionales m problema, pudiendo ser estas restricciones en forma de ecuaciones ( = ), o inecuaciones ( ≥ o ≤ ).

bi ( i= 1, 2, 3, m) es referido como el vector de lado derecho de las restricciones o término independiente y representa el requerimiento mínimo a satisfacer y las restricciones X1, X2, X3, ....Xn ≥ 0, se les conocen como las restricciones de no negatividad y significa que las variables de decisión no pueden tomar valores negativos4.

2. Supuestos del modelo de Programación Lineal

Para representar un problema de programación lineal es necesario conocer los diversos supuestos que están implícitos en la formulación del modelo presentado en 1.1. Entre los supuestos se tienen:

2.1. Proporcionalidad.

Esta suposición indica que la función objetivo y las restricciones deben ser proporcionales al nivel de actividad. Desde el punto de vista matemático se tiene que si Xj es una variable de decisión, su medida de optimización (max. o min.f) es igual a Cj Xj y su contribución a las restricciones es a Xj . Esto significa que si Xj es doblada, también lo será su contribución a la función objetivo y a cada una de las restricciones. Por ejemplo, si Xj = 5 entonces, la medida de optimización es 5c1 y si Xj = 10 entonces, su contribución a la función objetivo será l0c, y así sucesivamente. Esta restricción

3 Por ejemplo si de un Kg de Harina se fabrican 20 arepas, el coeficiente tecnológico seria 1/20, es decir la cantidad de harina necesaria para producir una arepa.4 Es posible formular modelos con variables irrestrictas de signos, pero se requiere una transformación adicional, que se discute en el apartado 4.10.

4/ 24

de linealidad implica que el ingreso, beneficio ó costo total de cada actividad, es directamente proporcional al nivel de actividad.

2.2. Aditividad.

Esta suposición indica que la medida total de optimización (ingreso total, costo total desperdicio total entre otros) es la suma de las contribuciones individuales de cada actividad, y la contribución total a las restricciones es la suma de las contribuciones individuales de cada actividad, es decir las actividades deben ser aditivas respecto al uso de los recursos.

El supuesto de aditividad significa que el total es igual a la suma de las partes y que no hay efectos de interacción entre los niveles de las actividades.

2.3. Divisibilidad.

La suposición de divisibilidad significa que es posible obtener en programación lineal una solución óptima no entera, es decir que los valores de las variables de decisión no sean enteros. Frecuentemente, aún cuando la solución obtenida no es entera el resultado se puede redondear al entero más cercano, sin embargo hay problemas donde no es conveniente redondear por lo tanto hay que recurrir a la programación entera, la cual es un tema no abordado en este curso.

2.4. Certidumbre.

La suposición de certidumbre indica que todos los coeficientes del modelo de programación lineal ( Cn, aj y bi ) son constantes conocidas; es decir que los costos, utilidades, las relaciones entre los niveles de producción, la disponibilidad de recursos, no están sujetas a ninguna incertidumbre.

3. Formulación del modelo de Programación lineal

El diseño e implantación de un modelo de programación lineal involucra una serie de etapas: la primera etapa es la formulación del problema, en la cual se estudia detalladamente el sistema, se lleva a cabo la recopilación de información y se presenta el modelo de programación matemática.

Una segunda etapa consiste en la resolución del modelo matemático planteado, para ello se puede utilizar el método gráfico, el método simplex, este ultimo se puede implementar de manera manual o

5/ 24

automatizada o el uso de paquetes computarizados tales como: WINQSB., SOLVER de EXCEL, STORM., LP1., LINDO y otros.

La tercera etapa consiste en probar, analizar, interpretar y reestructurar el modelo, examinando la solución del modelo a través de análisis de sensibilidad. Por ultimo se tiene la etapa de la implantación y control del modelo.

Este tema se concentra en la primera etapa, es decir en la formulación del problema. Para formular un problema de programación lineal, no hay pasos o procedimientos a aplicar, sin embargo representa una gran ayuda el proceder de la siguiente forma:

1) Identificar las variables de decisión: Este proceso consiste identificar las variables incógnitas, las cuales una vez conocidas permiten resolver el problema, representan cosas bajo nuestro control y que podemos modificarlas con un acción especifica. Una guía útil para identificar las variables es hacerse a si mismo la pregunta: ¿Qué decisión debe tomarse para optimizar la función objetivo?. La respuesta a esta pregunta le ayudará a llegar a identificar correctamente las variables de decisión. Al identificar las variables se les asigna un nombre simbólico, (por regla general se utiliza literales acompañados de subíndices simples y dobles X1, X2, Xn, Xij), es muy importante definir las unidades de cada variable cuidadosamente, y respetar la homogeneidad de las mismas en las ecuaciones lineales.

2) Construir la función objetivo: Es decir escribir la función objetivo (maximizar o minimizar) en términos de las variables de decisión como una suma, resta, multiplicación o división de cantidades. Luego se debe expresar las cantidades individuales matemáticamente como una función lineal de las variables de decisión y los coeficientes de contribución unitaria. Entre los objetivos mas utilizados tenemos:

Maximizar utilidades. Minimizar costos. Maximizar el beneficio bruto. Maximizar el efectivo. Minimizar las horas de sobre tiempo. Minimizar el riesgo. Minimizar el desperdicio al cortar. Minimización de la desviación a un estándar. Minimizar la distancia recorrida. Maximizar el uso de un recurso.

6/ 24

Es necesario e imperativo comprobar si las unidades son consistentes. Por ejemplo, si los coeficientes de una función objetivo están dados en Bs por Kg, las variables de decisión que aparezcan en la función objetivo deben resultar en Kg, no en toneladas o gramos.

3) Identificar restricciones Son los diferentes requisitos que debe cumplir cualquier solución para que pueda llevarse a cabo y considerarse factible. En cierta manera son las limitantes en los valores de los niveles de las diferentes actividades (variables). Estas restricciones pueden ser de Disponibilidad (<=menor ó igual que, no mayor que, como máximo), Requerimientos (>=mayor ó igual que, al menos, por lo menos, como mínimo), de Balance (=igual a, exactamente igual a), Restricciones lógicas (es decir aquellas que involucran relaciones implícitas entre los recursos). Cuando sea apropiado, se deben descomponer como una suma, resta, multiplicación o división de cantidades. Posteriormente se debe expresar matemáticamente como una función lineal, utilizando los coeficientes tecnológicos, y escribir las restricciones en términos de las variables de decisión.

Es necesario respetar el principio de dimensionalidad a ambos lados de la desigualdad, es decir verificar si las unidades del lado derecho son las mismas que las del lado izquierdo. Por ejemplo, si una de las restricciones es una limitante de la forma ≤ de horas de trabajo, el lado derecho e izquierdo debe ser de horas de trabajo.

Las restricciones más comunes son:

Restricción de capacidad: limitan el valor de las variables debido a las disponibilidad de horas-hombre, horas-máquina, espacio, etc.

Restricción de mercado: Surge de los valores máximos y mínimos en las ventas o el uso del producto o actividad a realizar.

Restricción de entradas: Son limitantes debido a la escasees de materias primas, mano de obra, dinero, etc.

Restricción de calidad: Son las restricciones que limitan las mezclas de ingredientes, definiendo usualmente la calidad de los artículos a manufacturar.

Restricciones de balance de material: Estas son las restricciones que definen las salidas de un proceso en función de las entradas, tomando en cuenta generalmente cierto porcentaje de merma o desperdicio.

7/ 24

Condición de no negatividad: en este apartado se establece que todas las variables deben tomar valores no negativos.

4. Sugerencias para la formulación del problema.

Para escribir las expresiones matemáticas que formalmente definen el problema, sugerimos que previamente se tome un tiempo para entender el problema. Se requiere que el analista se entretenga formulando un boceto en castellano del problema de optimización y tabulando la data numérica del problema.

Para proceder a la definición de las variables de decisión utilice una simbología matemática adecuada, identifique cada variable y acompañe a cada una con una frase en castellano que la describa- utilice identificadores nemotécnicos.

Cuando formule la función objetivo exprésela como una relación lineal de las variables de decisión, trate de conservar la frase en castellano que la describe.

En la formulación de las restricciones exprese las relaciones lineales de las variables de decisión. Asegúrese del cumplimiento de la aditividad y de la proporcionalidad. No olvide las restricciones de signo de las variables que puedan existir. Paralelamente al planteamiento de las expresiones de la función objetivo y de las restricciones haga una revisión dimensional para verificar la consistencia en las unidades involucradas.

Recuerde que uno de los propósitos de los modelos es la comunicación, por lo que se debe ser claro y explicito al formular un problema, para que otra persona pueda entender lo que usted quiere transmitir.

8/ 24

5. Aplicaciones.

Los principales campos de aplicación se clasifican en este apartado por tipos de problemas, que ilustran casos de optimización, y que además dan una idea de aquellas situaciones que se pueden resolver con las técnicas de PL.

5.1.Producción:

Este tipo de modelo responde a la pregunta ¿cuánto producir de cada línea de producción?, en un número determinado de fabricas o centros de producción. También se le denomina modelo de mezcla de productos, pues se utiliza para determinar la cantidad óptima a producir de una gama de productos diferenciados durante un período de tiempo.

Ejemplo 01. Problema de producción.

Un fabricante de muebles de oficina, produce dos tipos de escritorios: ejecutivos y secretariales. La compañía tiene dos plantas en las que fabrica los escritorios. La planta 1 es una planta antigua que opera con doble turno de 40 horas por turno por semana. La planta 2 es una planta mas nueva y no opera a su capacidad total. Cada turno de la planta 2 trabaja 25 horas por semana y la planta opera 2 turnos. La siguiente tabla muestra el tiempo de producción (horas/unidad) y los costos estándar ($/unidad) en cada planta.

También se muestran los precios de venta de cada escritorio. Debido a que la compañía ha estado experimentando un exceso de costos durante el ultimo periodo presupuestal, los administradores han fijado una restricción semanal sobre los costos de producción. El presupuesto semanal para la producción también se muestra en la tabla.

Se le pide a usted averiguar cuál es el numero óptimo de escritorios de cada tipo, a producirse en cada planta con el objeto de maximizar las ganancias.

Tipo de Escritorio

Tiempo de producción

Costo / u Precio de venta

Presupuesto

Planta 1

Planta 2 Planta 1

Planta 2

Ejecutivo 7 6 $250$26

0$350 $2.000

Secretarial 4 5 $200 $18 $275 $2.200

9/ 24

0

Respuesta:

1) Variables:

Xij = Nº de escritorios producidos en la planta i del modelo ji={1,2}j={E,S}

2) Función Objetivo:

MÁX Z = (350 - 250) X1E + (275 - 200) X1S + (350 - 260) X2E + (275 - 180) X2s

MAX Z =100 X1E + 75 X1S + 90 X2E + 95 X2s

4) Restricciones:

Restricciones de Capacidad:

7X1E + 4X1S 80 horas/semana [Planta 1]6X2E + 5X2S 50 horas/semana [Planta 2]

Restricciones de Presupuesto:

250X1E + 260X2E $ 2.000 [Escritorios Ejecutivos]200X1S + 180X2S $ 2.200 [Escritorios Secretariales]

Restricciones de No-Negatividad:

X1E ,X1S ,X2E ,X2S 0

Ejemplo 02. Problema de producción.

Una compañía de refrescos produce 7 diferentes productos denotados de P1 a P7, y dispone para ello de la siguiente maquinaria:

• 4 mezcladoras• 2 molinos horizontales• 3 molinos verticales • 1 filtro• 1 dosificador

La contribución de cada producto a la ganancia, el tiempo en horas requerido en cada proceso para producir una unidad de cada

10/ 24

producto (0 indica que el producto no requiere del proceso) y la máxima demanda mensual se dan en la siguiente tabla. La compañía trabaja 200 horas mensuales.

Descripción P1 P2 P3 P4 P5 P6 P7

Contribución a la ganancia (Bs)

10 6 8 4 11 9 3

Mezclado (horas) 0.5 0.7 0 0 0.3 0.2 0.5

Molienda horizontal (horas)

0.1 0.2 0 0.3 0 0.6 0Molienda vertical (horas)

0.2 0 0.8 0 0 0 0.6

Filtrado (horas) 0.05 0.03 0 0.07 0.1 0 0.08

Dosificado (horas) 0 0 0.01 0 0.05 0 0.05Máxima demanda mensual (u)

500 1.000 300 300 800 200 100

Formule el problema lineal que arroje la producción de cada refresco que maximice la ganancia de un mes normal.

Respuesta:

1) Variables:

Pi= Unidades de Producto i a producir en el mes.i={1..7}

2) Función Objetivo:

Max Z = 10P1+6P2+8P3+4P4+11P5+9P6+3P7

Restricciones:

Mezclado:

Se dispone de 4 mezcladoras que trabajan 200 horas mensuales cada una.0.5P1+0.7P2+0.3P5+0.2P6+0.5P7<=800

Molienda horizontal:

Se dispone de 2 molinos horizontales que trabajan 200 horas mensuales cada uno.0.1P1+0.2P2+0.3P4+0.6P6<=400

Molienda vertical:

11/ 24

Se dispone de 3 molinos verticales que trabajan 200 horas mensuales cada uno.0.2P1+0.8P3+0.6P7<=600 Filtrado:

Se dispone de 1 filtro que trabaja 200 horas mensuales.0.05P1+0.03P2+0.07P4+0.1P5+0.08P7<=200

Dosificado:

Se dispone de 1 dosificador que trabaja 200 horas mensuales.0.01P3+0.05P5+0.05P7<=200

Demanda máxima:

P1<=500P2<=1.000P3<=300P4<=300P5<=800P6<=200P7<=100

No negatividad:

Pi>=0; i={1..7}5.2. Planeación agregada, manejo de inventarios.

Este tipo de modelo responde a la pregunta ¿cuánto producir y almacenar de cada línea de producción en diferentes periodos de tiempo?. Se utiliza para determinar la cantidad óptima a producir durante múltiples períodos de tiempo y condiciones de producción (tiempo normal o extra).

Ejemplo 03. Manejo de inventarios.

La compañía OVM fabrica un producto cuya demanda es estacional y cambia mes con mes. El pronóstico de la demanda para los próximos cuatro meses es 1800, 2200, 3400, y 2800 unidades. Debido a la demanda variable, se ha encontrado que en algunos meses existe producción en exceso lo cual ocasiona grandes costos de almacenaje y mantenimiento. En otros meses la compañía no puede cubrir la demanda resultando en perdidas de oportunidades de venta. La capacidad de la planta es de 2400 artículos por mes utilizando turnos normales. De requerirse turnos extras es posible fabricar hasta 800

12/ 24

artículos adicionales. Los costos de producción son 400 y 420 dólares por unidad, para artículos fabricados en tiempo normal y en tiempo extra respectivamente. De no venderse un articulo y almacenarse para el próximo mes se incurre en un costo de 15 dólares por mes. Se le pide a usted que determine un programa optimo de producción que minimice los costos de producción y almacenaje para el periodo de 4 meses. El programa debe satisfacer la demanda pronosticada.

Respuesta:

1) Variables:

Xij = unidades a producir durante período i = 1,2,3,4 en tiempo j = 1 normal, 2 extra.Ik = inventario al final del período k = 0,1,2,3,4

X11 X21 X31 X41

X12 X22 X32 X42

I0 I1 I2 I3 I4 1 2 3 4

1800 2200 3400 2800

2) Función Objetivo:

MIN Z = 400[X11 + X21 + X31 + X41] +420[X12 + X22 +X32 + X42] +15[I1

+ I2 +I3 +I4 ]

3) Restricciones:

Restricciones de Balance: X11 + X12 = 1800 + I1 [Mes 01] I1 + X21 + X22 = 2200 + I2 [Mes 02] I2 + X31 + X32 = 3400 + I3 [Mes 03] I3 + X41 + X42 = 2800 + I4 [Mes 04]

Restricciones de Capacidad:

X11 2400 X12 3200X21 2400 X22 3200X31 2400 X32 3200X41 2400 X42 3200

13/ 24

No negatividad:

X11 , X21 , X31 , X41 , X12 , X22 , X32 , X42 ,I1 , I2 , I3 ,I4 0

5.3. Mezcla para empacar.

Este tipo de modelo responde a la pregunta ¿cuánta cantidad de producto mezclar para empacar?. Se utiliza para determinar la cantidad óptima a mezclar con el fin de empacar en envases o contenedores determinados.

Ejemplo 04. Mezcla para empacar.

Un distribuidor de ferretería planea vender paquetes de tuercas y tornillos mezclados. Cada paquete pesa por lo menos 2 libras. Tres tamaños de tuercas y tornillos componen el paquete y se compran en lotes de 200 libras. Los tamaños 1, 2 y 3 cuestan respectivamente $20, $8 y $12, además: a) El peso combinado de los tamaños 1 y 3 debe ser al menos la mitad del peso total del paquete. b) El peso de los tamaños 1 y 2 no debe ser mayor que 1,6 libras c) Cualquier tamaño de tornillo debe ser al menos el 10% del paquete total. ¿Cuál será la composición del paquete que ocasionará un costo mínimo ?.

Respuesta:

1) Variables:

Xj= Peso en libras de las tuercas y tornillos del tamaño j-ésimo (j=1,2 y 3) en la bolsa

2) Función Objetivo:

MIN Z = 20/200 X1 + 8/200 X2 + 12/200 X3

3) Restricciones:

X1 + X3 ≥ (X1 + X2 + X3) / 2 [Los tamaños 1 y 3 al menos la mitad del peso] X1 + X2 ≤ 1,6 [Los tamaños 1 y 2 no deben ser mayor de 1,6 lbs] X1 ≥ 0,1 (X1 + X2 + X3) [El tamaño 1 debe ser al menos el 10% del total] X2 ≥ 0,1 (X1 + X2 + X3) [El tamaño 2 debe ser al menos el 10% del total] X3 ≥ 0,1 (X1 + X2 + X3) [El tamaño 3 debe ser al menos el 10% del total]

14/ 24

X1 + X2 + X3 ≥ 2 [El paquete debe ser al menos de 2 libras] XJ ≥ 0 J = 1, 2 y 3 [Condición de no negatividad]5.4. Problema de dietas o de planeación de menús.

Estos tipos de modelos responden al problema económico de encontrar la combinación de alimentos que satisfaga un conjunto de requerimientos nutricionales dados a un costo mínimo. Se requiere hacer la mezcla5 más barata que satisfaga las restricciones de los nutrientes o de la cantidad mínima de cada alimento. Este modelo también se puede aplicar para la formulación de dietas para humanos, aves, ganado vacuno, ganado porcino entre otros.

Ejemplo 05. Mezclas.

El personal técnico de un hospital desea elaborar un sistema computarizado para planear diversos menús. Para empezar, deciden planear el menú de la comida. El menú se divide en tres grandes categorías: legumbres, carne y postre. Se desea incluir en el menú por lo menos el equivalente a una porción de cada categoría. A continuación se resume el costo por ración de algunos de los alimentos sugeridos, así como su contenido de carbohidratos, vitaminas, proteínas y grasas.

Carbohidratos

Vitaminas

Proteínas

Grasa

Costo $/Ración

VegetalesGuisantes 1 3 1 0 0.10Frijoles verdes

1 5 2 0 0.12

Ají 1 5 1 0 0.13Maíz 2 6 1 2 0.09Macarrones

4 2 1 1 0.10

Arroz 5 1 1 1 0.07CarnesPollo 2 1 3 1 0.70Res 3 8 5 2 1.20Pescado 3 6 6 1 0.63PostresNaranja 1 3 1 0 0.28Manzana 1 2 0 0 0.42Budín 1 0 0 0 0.15Gelatina 1 0 0 0 0.12

5 Por ello esta catalogado entre los problemas de mezcla o de Blending Problem.

15/ 24

Suponga que los requerimientos por comida mínimos de carbohidratos, vitaminas, proteínas y grasas son 5, 10, 10 y 2, respectivamente. Resuelva el problema de planeación de menús como un problema de P.L.

Respuesta:

1) Variables:

X1= Ración de GuisantesX2= Ración de Frijoles verdesX3= Ración de AjíX4= Ración de MaízX5= Ración de MacarronesX6= Ración de ArrozX7= Ración de PolloX8= Ración de ResX9= Ración de PescadoX10= Ración de NaranjaX11= Ración de ManzanaX12= Ración de BudínX13= Ración de Gelatina

2) Función Objetivo:

Minimizar el costo total del menú.

Costo total = Costo de los vegetales + Costo de las carnes + Costo del postre

Min Z= 0.10X1+0.12X2+0.13X3+0.09X4+0.10X5+0.07X6+0.70X7+1.20X8+0.63X9+0.28X10+0.42X11+0.15X12+0.12X13

3) Restricciones:

Requerimiento mínimo de carbohidratos:

X1+X2+X3+2X4+4X5+5X6+2X7+3X8+3X9+X10+X11+X12+X13>=5

Requerimiento mínimo de vitaminas:

3X1+5X2+5X3+6X4+2X5+X6+X7+8X8+6X9+3X10+2X11 >=10

16/ 24

Requerimiento mínimo de proteínas:

X1+2X2+X3+X4+X5+X6+3X7+5X8+6X9+1X10 >=10

Requerimiento mínimo de grasa:

2X4+X5+X6+X7+2X8+X9 >=2

Al menos una ración de cada categoría:

X1+X2+X3+X4+X5+X6>=1X7+X8+X9>=1X10+X11+X12+X13>=1

No negatividad:

Xi>=0 i=1..13

17/ 24

5.5. Problema de corte unidimensional.

El problema consiste en determinar cómo cortar un material en una sola dimensión para servir todas las piezas demandadas de una forma tal que la cantidad desperdiciada sea mínima.

Ejemplo 06. Corte de papel.

Paper montoya es una compañía de papel que actualmente fabrica papel para periódicos, se conoce que los rollos producidos conforman un stock con longitud L= 108” y demanda semanal mínima de:

800 piezas de longitud 30”500 piezas de longitud 45”1000 piezas de longitud 56”

La compañía desea determinar la manera de realizar los cortes para surtir el pedido con la finalidad de minimizar el desperdicio de papel.

Respuesta:

1) Variables:

Cada manera de cortar un rollo de papel esta asociada con una variable. Por ejemplo usted puede, recortar 2 pedazos de 45” de un rollo. Eso lo dejará con 18” de desperdicio.

Rollos de 30”, 45” y 56” cortados por cinco patrones

PatronesAncho

Requerido1 2 3 4 5

30” 3 2 1 0 045” 0 1 0 1 256” 0 0 1 1 0

Utilizado 90 105

86 101

90

Desperdicio 18 3 22 7 18

Definimos 5 variables, es decir, Xi= Número de rollos de tamaño 108” que se cortarán con el patrón i. i = 1,2,3,4,5.

X1= Número de rollos de tamaño 108” que se cortarán con el patrón 1.

18/ 24

X2= Número de rollos de tamaño 108” que se cortarán con el patrón 2.X3= Número de rollos de tamaño 108” que se cortarán con el patrón 3.X4= Número de rollos de tamaño 108” que se cortarán con el patrón 4.X5= Número de rollos de tamaño 108” que se cortarán con el patrón 5.

2) Función objetivo:

Minimizar el desperdicio al realizar los cortes en cada patrón

Desperdicio = (Desperdicio en X1) + (Desperdicio en X2) + (Desperdicio en X3) +(Desperdicio en X4) +(Desperdicio en X5)Min Z = 18X1 + 3X2 + 22X3 + 7X4 + 18X5

3) 1) Restricciones:

Las restricciones del modelo tienen que ver directamente con la satisfacción del numero mínimo de rollos solicitados:

Por ejemplo:

La cantidad de rollos de 30" a cortar debe ser como mínimo 800.  (Rollos de 30" en X1) + (Rollos de 30" en X2) + (Rollos de 30" en X3) + (Rollos de 30" en X4) + (Rollos de 30" en X5) deben ser como mínimo 800. 3X1 + 2X2 + X3 + 0X4 + 0X5> = 800 (Rollos de 30")

Similarmente construimos:

0X1 + X2 + 0X3 + X4 + 2X5> = 500 (Rollos de 45")0X1+ 0X2 + X3 + X4 + 0X5 >=1000 (Rollos de 56")

X1,X2,X3,X4,X5 >= 0 y enteros.5.6. Problema de Inversión financiera.

Consiste en determinar de forma simplificada el destino de los fondos (en unidades monetarias) de tal forma que, cumpliendo las restricciones para cada una de las posibles variables que intervienen en el problema, se optimice el beneficio de la estrategia de inversión considerada.

19/ 24

Ejemplo 07. Portafolios de inversión.

Supongamos que un banco se dedica a invertir en créditos al consumo, bonos corporativos, depósitos de oro, y préstamos a la construcción. Con el fin de diversificar la cartera de valores, la Junta Directiva del banco ha puesto límite a las cantidades que se permiten invertir en cada una de las opciones anteriores. En la actualidad dispone de 5 millones de euros para invertir, y se pretende: (1) Maximizar el interés esperado para los próximos seis meses, y (2) cumplir con la diversificación propugnada por la Junta Directiva según se especifica en la tabla:

Tipo de Inversión Interés esperado

(%)

Límite de Inversión

(millones de Euros)

Crédito al consumo 7 1,0Bonos corporativos 11 2,5Depósitos de Oro 19 1,5Préstamos a la construcción

15 1,8

Además, la Directiva requiere que al menos un 5% de los fondos se dediquen a depósitos de oro y préstamos a la construcción, mientras que el porcentaje dedicado a créditos al consumo no debe superar el 15%.

Respuesta:

1) Variables:

X1= Euros invertidos en crédito al consumo.X2= Euros invertidos en bonos corporativos.X3= Euros invertidos en depósitos de oro.X4= Euros invertidos en préstamos a la construcción.

2) Función objetivo:

Maximizar el interés esperado.

Max Z = 0,07X1 + 0,11X2 + 0,19X3 + 0,15 X4

3) Restricciones:

Limite de Inversión:

20/ 24

X1 1.000.000X2 2.500.000X3 1.500.000X4 1.800.000

Políticas de Inversión:

X3 + X4 250.000X1 750.000

Inversión Total:

X1 + X2 + X3 + X4 5.000.000

No Negatividad:

X1 , X2 , X3 , X4 0

21/ 24

5.9. Problema de Transporte.

Se refieren a la posibilidad de transportar los artículos desde los orígenes (i) a los destinos (j) en una forma que minimice el costo total de transporte.

Ejemplo 08. Transporte de granos.

Una empresa agrícola dispone de dos almacenes para abastecer de granos a tres distribuidores regionales. El almacén 1 dispone de 1000 ton. de grano y el almacén 2 dispone de 2000 ton. por periodo. La demanda en los tres distribuidores se estima en 1500, 750 y 750 toneladas por periodo, respectivamente. El costo de transporte por tonelada de grano es:

Distribuidor 1

Distribuidor 2

Distribuidor 3

Almacén 1

50 100 60

Almacén 2

30 20 35

Formule un modelo que permita calcular las toneladas de granos a transportar en un periodo para satisfacer la demanda y lograr un costo mínimo de transporte.

1) Variables:

Xij = Ton. de grano del almacén i al distribuidor j (i= 1,2 y j =1,2,3)X11 = Ton. de grano del almacén 1 al distribuidor 1.X12 = Ton. de grano del almacén 1 al distribuidor 2.X13 = Ton. de grano del almacén 1 al distribuidor 3.X21 = Ton. de grano del almacén 2 al distribuidor 1.X22 = Ton. de grano del almacén 2 al distribuidor 2.X23 = Ton. de grano del almacén 2 al distribuidor 3.

2) Función Objetivo:

Minimizar el costo de transporte.

Min Z = 50 X11 + 100 X12 + 60X13 + 30 X21 + 20X22 + 35X23

3) Restricciones:

Oferta de cada almacén i:

X11 + X12 + X13 <= 1000X21 + X22 + X23 <= 2000

Demanda de cada distribuidor j:

22/ 24

X11 + X21 = 1500 X12+ X22 = 750 X13+ X23 = 750

No negatividad:Xij>=0 para i = 1,2 y j = 1,2,3.

6. Ejercicios Propuestos para resolver en casa.

1. Una compañía de ámbito nacional produce y distribuye una línea de bicicletas de alta competición. La empresa tiene líneas de montaje en dos ciudades, Castellón y Sabadell, mientras que sus tres principales cadenas de distribución están localizadas en Madrid, Barcelona, y Vitoria. La oficina de Madrid presenta una demanda anual de 10.000 bicicletas, mientras que la de Barcelona solicita 8.000 y la de Vitoria 15.000. La planta de Castellón puede producir hasta 20.000 bicicletas anuales, por 15.000 la de Sabadell. Los costes de transporte por unidad son los siguientes:

DESTINOORIGEN Madrid

(Euros)Barcelona

(Euros)Vioria (Euros)

Castellón 2 3 5Sabadell 3 1 4

La compañía pretende establecer un plan de distribución que minimice sus costes anuales de transporte.

2. La compañía “Bombas Horizonte” fabrica y vende dos tipos de bombas hidráulicas: (1) Tamaño Normal y (2) Tamaño extra grande. El proceso de manufactura asociado con la fabricación de ambos tipos de bombas implica tres actividades: ensamblado, pintura y pruebas (control de calidad). Los requerimientos de tiempo para ensamblaje, pintura y prueba de las bombas se muestran en la tabla 1.1. Las bombas normales generan una utilidad por unidad de 500.000, en tanto que la utilidad por una bomba extra grande es de Bs. 750.000. Existen disponibles por semana 4.800 horas para ensamble, 1.980 horas de tiempo de pintura y 54.000 minutos de tiempo de prueba. Consultores externos estiman que la compañía puede vender cuando menos 300 bombas normales y a lo más 180 de las extra grandes. Su tarea consiste en formular un modelo de P.L. que determine la cantidad de cada tipo de bomba que debe fabricar semanalmente “Bombas Horizonte”, con el objeto de maximizar sus utilidades.

Tabla 1.1. Requerimientos de manufactura. Bombas Horizonte.

Tipo Tiempo de Tiempo de Tiempo

23/ 24

Ensamblaje Pintura deprueba

Bomba Normal 3.6 horas/u 1.6 horas/u 36 min/u

Bomba Extra Grande

4.8 horas/u 1.8 horas/u 36 min/u

3. Mangos de Torunos C.A.(MANTOCA), procesa mangos y los transforma en pulpa para jugo concentrado en tres plantas ubicadas en Barinas, Sabaneta y Santa Bárbara. De cualquiera de los dos huertos ubicados en Obispos y Pedraza se puede enviar fruta hacia cualquier planta. Dado el costo de embarque del producto se desea determinar como distribuir los envíos de manera de minimizar el costo total, conocida la información siguiente:

Costo flete ($/Kg)

OrigenBarinas

Santa Bárbara

SabanetaProducción (ton./mes)

Obispos 0,050 0,060 0,075 19Pedraza 0,060 0,045 0,090 25Capacidad (ton./mes)

10,00 15,00 9,00

4. Hexxon Oil Company obtiene tres tipos de petróleo crudo de sus pozos de Mississippi, Nuevo México y Texas. La gasolina obtenida de estos petróleos crudos y aditivos contienen azufre, plomo y fósforo, como se muestra en la tabla 1. El costo de cada componente también se presenta. Debido a los residuos e impurezas, cada galón de petróleo crudo de Mississippi resulta sólo en 0,35% de galón del producto final, que contiene 0,07% de azufre. De manera similar, cada galón de crudo de Nuevo México produce 0,40 de galón del producto final que contiene 0,08% de sulfuro y cada galón de crudo de Texas resulta en 0,30% de galón del producto final que contiene 0,10% de azufre. La gerencia ha establecido las siguientes especificaciones para controlar las cantidades de azufre, plomo y fósforo:

1. Cada galón debe tener a lo más de 0,07% de azufre.2. Cada galón debe tener entre 1,25 y 2,5 gramos de plomo.3. Cada galón debe tener entre 0,0025 y 0,0045 gramos de fósforo.4. La cantidad total de los aditivos no puede exceder de 19% de la mezcla.

Tabla Nº1 Composición y costo de los componentes de la mezcla

PETROLEOS CRUDOS ADITIVOS

24/ 24

Mississippi

Nuevo México

Texas 1 2

Azufre (%) 0,07 0,08 0,10 - -Plomo (g/gal)

- - - 7 6

Fósforo (g/gal)

- - - 0,025

0,02

Costo ($/gal)

0,55 0,47 0,33 0,08 0,12

Como gerente de producción. Determine un plan de mezclado que produzca una gasolina aceptable al mínimo costo.

5.Cada galón de leche, libra de queso y libra de manzana proporciona según la tabla nº1 un numero conocido de miligramos de proteínas, vitaminas A, B y C, además esa misma tabla muestra los requerimientos diarios de los ingredientes nutricionales, según lo recomendado por el INN, la cantidad mínima de cada alimento que debe incluirse en la comida y su respectivo costo.

Leche (mg/gal

)

Queso (mg/lb)

Manzanas (mg/lb)

Requerimientos minimos diarios

(mg)Proteínas 40 30 10 80

Vitamina A 5 50 30 60Vitamina B 20 30 40 50Vitamina C 30 30 60 30Cantidad Mínima

0,5 gal 0,5 lb 0,5

Costo Unitario

($/unidad)2,15 2,25 1,25

Formule un modelo de Programación Lineal para encontrar la combinación de alimentos que satisfaga el conjunto de requerimientos nutricionales dados en la tabla a un costo mínimo.