19
Investigacion de Operaciones Anter ior Siguie nte 1.4.1. Ejemplos de formulación de modelos de PL. La construcción de un modelo de programación lineal debidamente planteado que represente un problema real es un arte. La mayoría de la gente que lo intenta tiene más dificultades en ello que con los otros aspectos de esta técnica pues se requiere de imaginación e inventiva. Esto se puede mejorar con paciencia y práctica, ajustándose a la estructura dada como modelo general. El siguiente procedimiento puede ser útil antes de pretender la estructura matemática del problema en estudio: Concentrar la atención en identificar el objetivo general como puede ser, el máximo de: utilidades, rendimientos, audiencia; o bien, el mínimo de: costos, personal, distancias, tiempo, materia prima, o contaminación. Identificar las decisiones ( variables controlables) en forma cuantitativa con la unidad precisa de medición, como # de personas, # de pesos, # de toneladas. Identificar las constantes conocidas como coeficientes Cj que aportan al valor del objetivo, o coeficientes aij que contribuyen al consumo de materia prima o al requerimiento de recurso. Identificar todas las condiciones a las que se sujeta el objetivo en forma de restricciones en sus diferentes tipos:<=cuando mucho, >= al menos, = estrictamente lo especificado. A continuación se presentan ejemplos de planteamiento funcional, pero en algunos puede haber alternativa cambiando la definición de variable en la parte 1.

Investigacion de Operaciones.doc

Embed Size (px)

Citation preview

Page 1: Investigacion de Operaciones.doc

Investigacion de OperacionesAnterior Siguiente

1.4.1. Ejemplos de formulación de modelos de PL.

La construcción de un modelo de programación lineal debidamente planteado que represente un problema real es un arte. La mayoría de la gente que lo intenta tiene más dificultades en ello que con los otros aspectos de esta técnica pues se requiere de imaginación e inventiva. Esto se puede mejorar con paciencia y práctica, ajustándose a la estructura dada como modelo general.

El siguiente procedimiento puede ser útil antes de pretender la estructura matemática del problema en estudio:

Concentrar la atención en identificar el objetivo general como puede ser, el máximo de: utilidades, rendimientos, audiencia; o bien, el mínimo de: costos, personal, distancias, tiempo, materia prima, o contaminación.

Identificar las decisiones ( variables controlables) en forma cuantitativa con la unidad precisa de medición, como # de personas, # de pesos, # de toneladas.

Identificar las constantes conocidas como coeficientes Cj que aportan al valor del objetivo, o coeficientes aij que contribuyen al consumo de materia prima o al requerimiento de recurso.

Identificar todas las condiciones a las que se sujeta el objetivo en forma de restricciones en sus diferentes tipos:<=cuando mucho, >= al menos, = estrictamente lo especificado.

A continuación se presentan ejemplos de planteamiento funcional, pero en algunos puede haber alternativa cambiando la definición de variable en la parte 1.

Ejemplo 1-1. PL al combinar camiones refrigerados en transporte de alimento (REFCAM).

En la siguiente tabla se tiene la información de costo en renta y también las capacidades, de dos tipos de camión transportista refrigerado para la distribución de alimentos, una parte de los cuales pueden descomponerse durante el viaje. En particular se requiere un total de 900 y 1200 metros cúbicos (m3) de espacio refrigerado y no refrigerado, respectivamente. Formule un modelo de PL para decidir y resolver el problema de cuántos camiones de cada tipo rentar para que el costo sea el menor posible.

Figura 1-1. Información para renta de camiones con y sin espacio refrigerado del ejemplo REFCAM.

Page 2: Investigacion de Operaciones.doc

1ra. parte.- Definición de las variables de decisión

2da. parte.- Función económica u objetivo de costo

3ra. parte.- Sujeta la función de mínimo costo a restricciones de espacio de carga:

4a. parte.- Condiciones de signo para las variables de decisión:

Observaciones para el Ejemplo 1-1.-El primer problema de ejemplo es de decisión y la pregunta evidente para el distribuidor responsable es ¿ cuántos camiones de cada tipo deben rentarse para cumplir con la distribución?. Para contestarla, en la primera parte del modelo se definen las incógnitas que se acostumbra denotar con la letra X con índices, como XA, XB, para hacer la diferencia entre los dos tipos de camión A y B. Para formular la función objetivo en la parte 2 del modelo, se observa que la renta de un camión tipo A cuesta 3 (3000 pesos) multiplicado por el número XA de camiones tipo A para renta, resulta así el término 3XA que significa el costo de todos los camiones A rentados, por otro lado la renta de un sólo camión tipo B es de 4, por lo tanto 4XB es el costo de rentar los camiones tipo B. Con la suma de los dos términos o contribuciones de costo se obtiene el valor total de Z, la función objetivo de costo, cuya dimensión es:

En la parte 3 correspondiente a las restricciones, debe pensarse en el recurso espacio de carga que es el atributo de interés de los camiones a rentar. La capacidad especificada de carga, refrigerada o no, de los mismos, se emplea para plantear los términos de las restricciones, las que se traducen como requerimiento o necesidad de 900 m3 de espacio de carga refrigerada y 1200 m3 de espacio de carga no refrigerada, lo cual hace un total de dos restricciones a formular. Cada término de ellas se construye considerando el espacio de un sólo camión (20 m3 refrigerados para el A) multiplicado por el número de camiones (XA para A) del tipo que se decida rentar, o sea, 20XA es la contribución de espacio refrigerado de los camiones A para los requeridos 900 m3 del distribuidor. De

Page 3: Investigacion de Operaciones.doc

la misma manera se forma el término 30XB como contribución de espacio refrigerado de los camiones B. En la restricción 20XA + 30XB >= 900 se utiliza la desigualdad >= porque el requerimiento de 900 m3 se interpreta como el espacio mínimo necesario para el alimento perecedero.

Las mismas ideas ya expuestas son aplicables para la segunda restricción referente al requerimiento de 1200 m3 de espacio no refrigerado, ambas se dimensionan así:

Por último en la parte 4, las condiciones de valor no negativo para las incógnitas, son lo natural para este problema ejemplo, entendiendo que el número de camiones a rentar es positivo: XA > 0, XB > 0 o bien, puede que la solución al modelo planteado de este problema, resulte que no conviene rentar algún tipo de camión, en tal caso se presentaría con XA = 0 ó con XB = 0, puesto que XA < 0 ó XB < 0 no tiene significado físico.

Ejemplo 1-2. PL al combinar tamaños de camiones en transporte (TAMACA).

Una compañía transportadora tiene 10 camiones con capacidad de 20 toneladas y 5 camiones de 15 toneladas. Los camiones grandes tienen costos de operación de $150 por kilómetro recorrido y los pequeños de $ 125 por kilómetro recorrido. En la siguiente semana la compañía requiere transportar 200 toneladas de azúcar en un recorrido de 800 kilómetros. La posibilidad de otros compromisos de transporte, impone una política táctica de mantener en reserva, por lo menos, dos camiones pequeños por cada camión grande.¿ Cuál es el número óptimo de camiones de ambas clases que se deben utilizar para transportar el azúcar? Formule un modelo de programación lineal para este problema.

Figura 1-2. Información: costo según el tamaño de camión, recorrido y transporte del ejemplo TAMACA.

Modelo de programación lineal.

1a parte.- Definición de variables de decisión

2a parte.- Función económica u objetivo: Planteamiento de costo mínimo de operar Xj camiones

3a parte.- Restricciones o condiciones.- Requerimiento de carga a transportar:

Page 4: Investigacion de Operaciones.doc

Restricciones de camiones disponibles a utilizar: Xg <= 10 ; Xp <= 5 (camiones).

Para la restricción de tener en reserva dos camiones pequeños por cada camión grande, se definen otras variables y significan camiones en reserva para otro uso:

Sea X r j = número de camiones en reserva de tipo j ( j = g , p)

Camiones grandes reservados = total de grandes menos los utilizados: Xrg=10-Xg

Camiones pequeños reservados = total de pequeños menos los utilizados: Xrp=5-Xp

4a parte: Condiciones de signo para las variables:

Observaciones al Ejemplo 1-2: Análisis de la propiedad de proporcionalidad:

El cambio para diferentes valores de Xg se mantiene constante (20), o las contribuciones de 20, 40, 60,..., son proporcionales al valor incremental de Xg. En contraste, el valor de las contribuciones 20, 80, 180,..., para diferentes valores de la variable en X2

g no se mantiene constante y por lo tanto no hay proporcionalidad.

El problema de ejemplo 1.2, como primera parte, es decidir el número de camiones grandes (Xg) y pequeños (Xp) a utilizar para el transporte del azúcar.

Para construir la función objetivo de la segunda parte del modelo, hay necesidad de pensar como administrador del transporte, pues en cualquier caso se desea cumplirlo con bajo costo. Puesto que existe diferencia al operar camiones de diferente tamaño, pero el recorrido es igual para los grandes y pequeños, en tal caso se calcula el costo del

Page 5: Investigacion de Operaciones.doc

viaje para cada uno de los dos tipos de camión el cual se emplea como coeficiente de costo Cj en cada término de la función Z que representa el costo total a minimizar.

Las restricciones de la parte 3 del modelo matemático son de tres clases: se debe cumplir un requerimiento ( >=) de transporte de 200 toneladas de azúcar. Para la posible pregunta de por qué no se utiliza un simple signo de igualdad (=), considere que la capacidad de los camiones grandes de 20 toneladas, si es múltiplo de las 200 toneladas a transportar, pero en cambio, la capacidad de 15 toneladas de los camiones pequeños, no es múltiplo de 200, en tal caso, puede no cumplirse en igualdad; por otro lado no se debe olvidar la política de mantener en reserva cierto número de camiones. Posteriormente se trata la conveniencia de evitar, en lo posible, las restricciones estrictas de igualdad (=), pues la programación lineal, las restricciones ( <= ) y ( >= ) no excluyen la posibilidad de cumplir la igualdad y aportan flexibilidad en la búsqueda de la mejor solución. Otra clase de restricción a considerar se refiere al total de camiones existentes de cada tamaño, lo cual se expresa con la desigualdad ( <= ) significando, que se dispone de un máximo de 10 grandes y 5 pequeños. La restricción para dejar en reserva algunos camiones, necesita una definición adicional para ellos, pues en la primera parte del modelo sólo se definen las variables de decisión para representar los camiones a utilizar. De esta manera, se plantean las expresiones para: Xrg = 10 - Xg ; Xrp = 5 - Xp, sustituyéndolas en la interpretación de la política de reserva, conteniendo las variables de decisión Xg , Xp , así como también las variables que representan los camiones en reserva Xrg , Xrp las cuales sirven para el análisis durante la formulación, pero no permanecen en la presentación final del modelo.

Se termina el modelo con la parte 4 en que se condicionan las variables sólo a valor positivo o cero, pues el negativo no tiene significado físico en este problema.

Las expresiones en negrita forman el modelo matemático pedido.

Ejemplo 1-3. PL en horarios para cubrir turnos de trabajo (HORAPRO).

Figura 1-3. Policías para vigilancia de un sector de la ciudad en ejemplo HORAPRO.

Cada policía debe laborar 8 horas consecutivas. El periodo 1 sigue al 6.

Formule un modelo de PL para determinar el número óptimo de policías.

Ayuda para el análisis: En este problema se conoce, que para fines de control, se divide el día completo en periodos de 4 horas de duración, logrando continuidad de la vigilancia de policías los que deben trabajar durante dos periodos consecutivos. También se sabe el requerimiento en número de policías para cada uno de los seis periodos; entonces la siguiente forma tabular puede ser buena ayuda para la

Page 6: Investigacion de Operaciones.doc

comprensión del problema considerando a Xj como grupo de policías asignados para iniciar los periodos j ( j = 1,2,...,6 ).

Figura 1-4. Inicio y permanencia de grupos X j de policías en los periodos j del día en ejemplo HORAPRO.

Modelo de programación lineal.

1a parte.- Definición de variables:

2a parte.- Función económica.- Aquí debe pensarse en el menor número de policías necesarios para cumplir, por lo menos, los requeridos en cada uno de los seis periodos j:

3a parte.- Restricciones: La misma tabla da la combinación de los grupos de policías Xj para cubrir, como se observa, los requerimientos de cada periodo j.

4a parte.- Condiciones de signo, NO NEGATIVO:

Ejemplo 1-4. PL en la dieta de jugos (BEDIET).

Un proveedor de bebidas dietéticas debe preparar con las existentes de su bodega, un pedido de 500 litros de ponche dietético el cual debe contener por lo menos 20% de jugo de naranja, 10% de jugo de toronja y 5% de jugo de betabel. La siguiente tabla informa de 5 bebidas existentes con su contenido de jugos y el costo de las mismas. ¿Qué cantidad de cada bebida deberá de emplear el proveedor para cumplir el pedido a un costo mínimo? Formule un modelo de programación lineal que represente este problema.

Page 7: Investigacion de Operaciones.doc

Figura 1-5. Información de bebidas almacenadas en ejemplo BEDIET.

Modelo de programación lineal.

1a parte.- Definición de variables:

2a parte.- Función económica u objetivo:

3a parte: Sujeta a restricciones.-

Restricción de proporción de contenido de jugo:

Para este tipo de restricción es necesario convertir la información de contenido en por ciento (%) de jugo de la tabla a fracción decimal de un sólo litro del mismo, ya que la definición de significado de las variables en la primera parte del modelo se hizo como litros de bebida j. Por lo tanto, la fracción 0.40 ó 400 mililitros de jugo de naranja multiplicado por XA litros, es la contribución de la bebida A (0.40XA) para cumplir el 20% (0.20 por litro de ponche) de jugo de naranja en la bebida pedida. También 0.05XB es la contribución de la bebida B y 1XC, es la contribución de C (pura naranja) al ponche pedido. Las restricciones de toronja y betabel se formulan de la misma manera.

4a parte.- Condición de signo para las variables:

Ejemplo 1-5. PL en la inversión de capital (INVECAP).

Un banco desea establecer una política de préstamo para el siguiente trimestre y por tal motivo asignó un presupuesto de 12 millones de dólares para prestarle a sus clientes. En la tabla siguiente se anotan los tipos de préstamo con el interés correspondiente y las probabilidades de no-recuperación del capital prestado. Lo que no se puede recuperar no tiene intereses. Por competencia con otros bancos, se requiere asignar préstamos de al menos el 40% del total, a los tipos de préstamo 4 y 5. Con la habitación debe prestarse al menos un 50% de la suma de los préstamos 1, 2, y 3. La política de banco es que la relación total de los irrecuperables sea un máximo de 0.04. Formule un modelo de programación lineal para este problema de inversión.

Page 8: Investigacion de Operaciones.doc

Figura 1-6. Información de tipo de préstamos bancarios en ejemplo INVECAP.

Modelo de programación lineal

1a parte.- Definición de variables:

2a parte.- Función objetivo:

En este problema, a la función Z a maximizar se le debe formular con la suma de las contribuciones de rendimiento de los cinco tipos de préstamo, pero descontando la fracción de irrecuperables los cuales se estiman en la columna derecha de la tabla:

3a parte.- Sujeto a restricciones.

4a parte.- Condiciones de signo.

Page 9: Investigacion de Operaciones.doc

El conjunto de expresiones en negrita forma el modelo matemático de programación lineal que se pide formular.

Ejemplo 1-6. PL en la selección de máquinas para un proceso (MAQUIPRO).

Una compañía tiene 3 tipos de máquinas procesadoras con diferentes características en cuanto a velocidad, precisión y costo de producción. En la siguiente tabla se resumen las mismas:

Figura 1-7. Información de características de máquinas tipo j en ejemplo MAQUIPRO.

Cada día de 8 horas deben producirse 500 piezas. Formule un modelo de programación lineal para este problema:

Modelo matemático de programación lineal.

1a parte.- Definición de variables.-

Para este problema el estudiante puede razonar a partir de la información dada, que se conocen las características de las máquinas de procesar piezas, pero no cuántas utilizar de cada uno de los tres tipos, puesto que a las diferencias técnicas entre ellas, se agrega el costo de operarlas. De este modo se define:

Sea Xj = número de máquinas de tipo j ( j = 1, 2, 3 ) necesarias para producir 500 piezas en un día de 8 horas a condición de hacerlo con el menor costo.

2a parte.- Función económica.-

La medida para decidir en este problema, es la conveniencia de cumplir la cuota de producción de 500 piezas en la forma más económica posible; para ello es necesario que se involucren los costos asociados con cada tipo j de máquina calculando antes de la formulación de la función Z, el costo Cj correspondiente; por lo tanto: Z mínima = suma de contribuciones de costo de los tres tipos de máquina.

Page 10: Investigacion de Operaciones.doc

Observe que los coeficientes Cj se obtienen sumando, al costo nominal de una hora de proceso, el costo correspondiente a la estimación de piezas rechazadas, que para el caso de la máquina j =1 es de 10% ó 0.10 en fracción decimal multiplicado por 30 piezas producidas en una hora, resulta en 3 piezas con defecto en una hora de proceso. Cada rechazo cuesta un dólar, entonces se suma este costo: 3(1 dólar) = $3, al nominal de $5 y así se tiene C1 = $8. Los costos C2

y C3 se calculan con el mismo criterio.

3a parte.- Sujeta a restricciones.-

La cuota de producción de 500 piezas en una jornada de 8 horas conviene convertirla a su equivalente para una sola hora, pues se puede observar que la información restante está en esos términos. La producción pedida constituye una importante condición del problema y debe plantearse como restricción u obligación, la cual se construye a partir de las velocidades especificadas por máquina tipo j; pero las tasas anotadas son nominales, puesto que se estima un porcentaje de piezas aceptadas para los diferentes tipos j de máquina, en tal caso es necesario ajustar las velocidades o tasas de producción de acuerdo a su eficiencia para plantear el requerimiento en términos reales:

A j = Producción real por máquina tipo j, debido a la eficiencia en piezas buenas.

Otra restricción a considerar se refiere al número total de máquinas de tipo j que se tienen para este proceso de producción, debiéndose plantear con desigualdad <=, significando que el número de máquinas utilizadas, debe ser menos o cuando mucho, lo anotado en el lado derecho:

Page 11: Investigacion de Operaciones.doc

Como no hay significado físico para valores negativos de las variables, entonces se limitan como sigue

4a parte.- Condiciones de signo a variables

Las expresiones escritas en negrita forman el modelo de programación lineal que se pide.

Ejemplo 1-7. PL para distribuir carga en transporte (BARCOCARGA).

Un barco tiene tres bodegas: en la proa, en el centro, y en la popa con los siguientes límites de:

Figura 1-8. Capacidades en el barco del ejemplo BARCOCARGA.

Los siguientes cargamentos se ofrecen, pudiendo aceptar los dueños del barco, el total o una porción cualquiera de cada uno de los siguientes:

Figura 1-9. Artículos a transportar en ejemplo BARCOCARGA.

Para preservar el equilibrio del barco, el peso de cada bodega debe ser proporcional a la capacidad en toneladas. Formule un modelo de PL para determinar como distribuir la carga en las bodegas para una utilidad máxima.

Modelo de programación lineal

Distribuir la carga en toneladas, de tres artículos j diferentes, en cualquiera de las tres bodegas i, significa la flexibilidad de ocupar los espacios convenientes para máxima ganancia cumpliendo las restricciones de capacidad especificadas. Dado que un artículo j puede asignarse a cualquiera de las tres bodegas i, entonces se pueden definir las variables Xij para representar las toneladas de producto j en las tres bodegas como X1j, X2j, X3j o bien, las toneladas cargadas en las bodegas i de los tres productos como XiA, XiB, XiC. Entonces con la misma letra X con doble índice se pueden definir las variables de decisión.

Page 12: Investigacion de Operaciones.doc

Figura 1-10. Fracciones de la carga distribuidas en ejemplo BARCOCARGA.

1a parte: Definición de variables.

2a parte: Función económica u objetiva.

3a parte: Sujeta a restricciones.-

Las limitaciones de capacidad deben expresarse

con desigualdad <= , lo cual significa que se debe cargar menos o cuando mucho la capacidad especificada ya sea en toneladas o bien el espacio en metros cúbicos. En cada viaje, la suma de la carga ofrecida a transportar, supera la capacidad total del barco, entonces se puede llevar sólo una parte de ella, así las restricciones son <=.

Para conservar el equilibrio debe considerarse que la suma de XiA + XiB + XiC, de toneladas cargadas a cualquier bodega i, es menor a la capacidad de i , por lo tanto es una fracción de ella. Se interpreta como proporción utilizada de la capacidad, que debe igualarse para las tres bodegas y tratarse como una variable adicional, a las ya definidas: sea Xpc la proporción de capacidad que es <= 1 como sigue:

Page 13: Investigacion de Operaciones.doc

4a parte.- Condiciones de no negatividad:

Ejemplo 1-8. PL en la producción de fertilizantes con diferentes ingredientes (FERTILIZ).

Se producen dos clases de fertilizante distinguidos por contenido químico, disponibilidad del mismo y costo de ingredientes como se muestra aquí:

Figura 1-11. Informe: contenido, costo, precio de fertilizantes, ejemplo FERTILIZ.

Formule un modelo de PL. para obtener la combinación de fertilizantes a producir que maximice la utilidad.

La tabla de datos de este problema es un buen ejemplo de ordenación y síntesis de la información dada; con esa ventaja se facilita el análisis al formular el modelo.

Modelo de programación lineal.

1a parte.- Definición de variables.

2a parte.- Función económica u objetivo.

3a parte.- Sujeto a restricciones de contenido químico:

Page 14: Investigacion de Operaciones.doc

4a parte.- Condiciones de signo para las variables.

Ejemplo 1-9. PL para mínimo desperdicio en proceso de corte (CORTEPAPEL).

Una papelería recibe un pedido de 500, 300 y 100 rollos de papel de cierta calidad en ancho de 30, 45 y 56 pulgadas, respectivamente. En almacén se tienen rollos de papel de la calidad solicitada pero con un ancho de 108 pulgadas. Si la papelería desea satisfacer el pedido del cliente deberá someter a corte longitudinal los rollos en existencia pero se tendrá obligadamente un desperdicio de papel.

Formule un modelo de programación lineal que minimice el desperdicio.

Antes de iniciar la formulación del modelo de PL de este problema, se pueden revisar las varias alternativas convenientes para realizar el corte, desde un ancho de 108 pulgadas que tienen los rollos existentes en almacén hasta los anchos del pedido. Para ello se presenta la siguiente tabla que facilita el análisis de cuántos rollos en 30, 45 y 56 pulgadas se pueden obtener en cada proceso de corte, cuidando que las diferentes combinaciones sean posibles y con un desperdicio menor a 30 pulgadas.

Figura 1-12. Tipos de corte conveniente para ajustar anchos solicitados en ejemplo CORTEPAPEL.

Modelo matemático de programación lineal.

1a parte.- Definición de variables:

2a parte.- Función económica u objetivo.-

Se utiliza el cálculo del desperdicio en pulgadas anotado en la columna derecha de la tabla, para construir los términos correspondientes al desperdicio de cada tipo de corte los cuales sumados, valoran la función Z a minimizar.

3a parte.- Sujeto a restricciones.-

La misma tabla ordena el dato de número de rollos con determinado ancho, obtenido en cada corte de tipo j, este número multiplicado por el número de cortes j, es el término contribuyente para surtir los rollos de papel pedidos. Así