Modelación de Investigación de Operaciones. Aplicaciones de la Programación Lineal (página 2)
8. Formular las funciones de las
restricciones
De la misma manera deben escribirse funciones para
expresar las diferentes limitantes que se presentan en el
proceso, ya sea en lo referente a valores permitidos para las
variables, disponibilidad de recursos, producción total
máxima o mínima y muchas otras.
Principales tipos de
restricciones
Aunque para la infinidad de problemas que pueden
modelarse para ser resueltos mediante la Programación
Lineal se presentan muy diferentes restricciones, podemos decir
que las limitantes de un modelo de P.L. se agrupan en seis tipos
principales, que son:
Restricciones de capacidad: Relacionadas con los
recursos de infraestructura del sistema, como son las horas de
mano de obra, de máquina, el espacio, etc.
Restricciones de entradas: Limitan el valor de
las variables debido a la disponibilidad de recursos como:
materia prima, dinero, etc.
Restricciones de mercado: Son reflejo de los
valores máximos o mínimos en las ventas o en el uso
del producto o en el nivel de la actividad a realizar.
Restricciones de composición: Son
expresiones de las mezclas de los ingredientes, que definen
usualmente la calidad de los productos o resultados.
Restricciones de balance de materiales: Expresan
las salidas de un proceso en función de las entradas,
tomando en cuenta generalmente cierto porcentaje de merma o
desperdicio en el proceso.
Restricciones internas: Son las que se escriben
para definir el valor de una variable que surge en la
formulación del problema, no siendo variable de
decisión, sino una variable auxiliar creada para hacer
más expedita la construcción del modelo.
Restricciones por políticas
administrativas: No hacen parte de la tecnología del
problema, sino que obedecen a decisiones administrativas, como
por ejemplo no invertir más de cierta cantidad de dinero
en alguna opción.
Nuevamente se recalca la importancia de tener muy claras
las unidades de los datos que se usarán. Esta
consideración nos permitirá controlar la
homogeneidad en las unidades de los términos de la
función del objetivo y en las de las funciones de las
restricciones.
En especial debe constatarse que las unidades
resultantes al evaluar la expresión del lado izquierdo de
una restricción, coincidan con las unidades del lado
derecho de la misma. Obviamente cuando un modelo tiene varias
restricciones de un mismo tipo, basta con verificar la
consistencia en una de ellas.
Construcción
de modelos de programación lineal de algunos problemas
sencillos
Como se dijo la programación lineal es una
técnica ampliamente utilizada para la búsqueda de
la solución óptima a problemas de innumerables
disciplinas en muchos campos de la actividad humana.
En este capítulo se presentan algunas
aplicaciones sencillas. En el siguiente estudiaremos otras
aplicaciones que exigen un poco más de análisis y
de conocimiento del área respectiva.
APLICACIONES EN PRODUCCIÓN
Mezcla de producción:
El problema consiste entonces en determinar la cantidad
Xj a producir de cada uno de los artículos que compiten
por el uso de los recursos, de tal forma que se obtenga un
máximo de producción o un máximo de
beneficio, o un mínimo de costo u otro objetivo especial,
en un periodo determinado de producción
Ilustremos este tipo de problemas con dos ejemplos
sencillos:
Ejemplo N° 1
La compañía desea conocer cuantas unidades
de cada tipo de artículo debe producir en el periodo con
el fin de maximizar la utilidad total por venta de los
artículos. Se supone que todos los artículos
producidos se venden y que la utilidad unitaria permanece
constante, sin importar la cantidad vendida.
Construcción del modelo:
Siguiendo la metodología propuesta en este
capitulo, una vez comprendida la situación que se
describe, vamos a organizar los datos en una tabla; con lo cual
será más fácil su utilización para
construir el modelo.
Un bosquejo de la situación puede ser el que se
muestra en la siguiente gráfica, en la cual se observa que
los elementos claves del problema son las tres materias primas y
los dos tipos de artículos, mientras que el objetivo es
maximizar la utilidad. De esta manera aparece claro que el
objetivo se medirá en pesos / periodo.
De igual forma salta a la vista que las actividades
alternativas son, como lo dice el enunciado, producir
artículos tipo 1 y producir artículos tipo 2.
Téngase en cuenta que las actividades no son excluyentes
sino que pueden darse simultáneamente a determinados
niveles; desde llevarse a cabo una sola de ellas, hasta
ejecutarse ambas en cierta combinación. Todo ello depende
de la relación entre su contribución al objetivo y
a su consumo de las materias primas.
Debemos usar unas variables para cuantificar el nivel o
grado al cual llevaremos a cabo cada actividad.
Por ello definimos las variables así:
X1 : cantidad de artículos tipo 1 a fabricar en
el período.
X2 : cantidad de artículos tipo 2 a fabricar en
el período.
Una vez definidas las variables de decisión y
comprendido el objetivo del problema, el modelo se plantea
así:
Función del objetivo
Utilidad total = 400X1+ 300X2 $/periodo
Limitantes o restricciones en el logro del
objetivo
La cantidad utilizada de cada materia prima debe ser
menor o igual que la cantidad disponible.
Los valores de todas las variables deben ser mayores o
iguales a cero
(Condición de no negatividad de las
variables)
X1 = 0, X2 = 0
Por lo cual el modelo tendrá la siguiente forma
final:
Minimizar Utilidad total = 400X1+
300X2
Sujeta a:
Con X1, X2 = 0
Mas con el propósito de ilustrar la manera de
verificar la compatibilidad de unidades, que con el de constatar
la veracidad del modelo, pues este es muy elemental, vamos a
analizar un análisis bidimensional de las
funciones.
En la función objetivo:
400 ( $ / unidad de P1) * X1 ( unidades de P1 /
período)
+ 300 ( $ / unidad de P2) * X2 ( unidades de P2 /
período) = ( $ / período)
Se verifica que son las mismas unidades de la
función objetivo.
En las restricciones analicemos únicamente para
el consumo de la materia prima A, pues para las otras es
similar.
1(libra de A/unidad de P1) * X1 (unidades de
P1/periodo)
+ 1(libra de A/unidad de P2) * X2 (unidades de
P2/periodo) = (libras de A/periodo)
Que coinciden con las unidades del miembro derecho de la
primera desigualdad.
(150 lb. de A/periodo)
Adviértase que la condición de no
negatividad de las variables, tiene sentido lógico en este
modelo, ya que no se puede fabricar una cantidad negativa de
alguno de los tipos del artículo.
Luego evaluaremos problemas en los cuales se puede
presentar el caso de que una o mas variables puedan tomar valores
entre menos infinito y más infinito o incluso que algunas
variables deban tomar valores negativos o cero. En estos casos
debemos efectuar los ajustes necesarios en el modelo para que
todas las variables estén condicionadas a ser no
negativas, ya que esta es una condición del algoritmo
utilizado para la solución de los modelos de
P.L.
Por este motivo a la condición de no negatividad
de las variables se le llama en muchos casos condición
técnica (de no negatividad).
Debemos interpretar también, la parte del
enunciado referente a que la empresa supone que vende todos los
artículos producidos y que la utilidad permanece
constante. La primera parte nos indica que no hay límites
en cuanto al número de artículos de cada tipo a
producir, excepto los inherentes a la disponibilidad de los
recursos productivos.
La segunda parte nos permite considerar la
proporcionalidad entre la cantidad de artículos y la
utilidad total por ventas de cada tipo de
artículo.
En algunas situaciones de mercado ocurre que hay
límites en las ventas máximas o mínimas de
un determinado tipo de artículo, lo cual debe reflejarse
en el modelo como una restricción en el valor de la
variable correspondiente a la actividad.
Por ejemplo si conocemos que la demanda máxima
del artículo 1 es de 30 unidades, debemos incluir en
problema la condición de que no se produzcan más de
30 unidades de este articulo, ya que la producción
adicional no tendría comprador, generando entonces un
inventario en lugar de contribuir a la utilidad total. Igualmente
si tenemos una demanda comprometida de 15 unidades del
artículo 2, la cual deseamos satisfacer, debemos agregar
al modelo una restricción expresando que el número
de unidades del articulo 2 debe ser al menos 15.
Con la dos consideraciones anteriores, el modelo debe
tener estas otras dos restricciones
X1 = 30
X2 = 15
Por otro lado en algunas condiciones de mercado el
precio unitario de venta de los artículos se "quiebra", o
sea se disminuye en alguna cantidad cuando el número de
artículos excede cierto valor. Por ejemplo si X3 es la
cantidad comprada de un articulo cuyo precio unitario es de $10
cuando 0= X3 = 100; pero que rebaja a $7 cuando 101= X3 = 250 y
rebaja de nuevo a $ 6 cuando X3 = 251; en este caso no se cumple
la condición de proporcionalidad en la función del
objetivo ya que no tenemos un coeficiente único para
multiplicar por la cantidad comprada para obtener el costo de
compra de las X3 unidades. El coeficiente depende del intervalo
en el cual se encuentre el valor de X3. En algunos casos podemos
efectuar promedios de los valores de los parámetros
pertinentes y en otros se puede plantear el modelo de la forma de
programación lineal separable, como lo aprenderemos en un
ejemplo posterior.
Ejemplo N° 2.
El costo del material para una unidad del
artículo 1 es $50, para una unidad del artículo 2
es de $80 y para una unidad del artículo 3 es de
$140.
Los precios de venta para los artículos son
respectivamente de $400, $420 y $500, la unidad.
Los tiempos de proceso requeridos por una unidad de cada
tipo de material, se dan en la siguiente tabla:
Minutos de operación por unidad
La compañía necesita conocer cuantas
unidades de cada tipo de artículo debe fabricar en una
hora, para obtener la máxima utilidad.
Construcción del modelo:
Inicialmente podemos elaborar unas tablas con los datos
del problema, así:
El esquema del proceso puede ser el
siguiente:
Los elementos son la materia prima, las tres operaciones
de proceso y los tres artículos.
Determinar los elementos del problema es de gran ayuda
para la elaboración de la función objetivo y las
funciones de las tres restricciones.
El objetivo será maximizar la utilidad resultante
de la producción en una hora. Esta utilidad será la
diferencia entre el ingreso por ventas y los gastos por materia
prima y operaciones en las máquinas.
Calculemos las utilidades netas, así:
Las variables a utilizar se definen como:
Las restricciones se refieren a que una máquina
no puede utilizarse durante una hora por un tiempo total mayor
que la hora. Es decir, el tiempo que una máquina dedique a
la producción del artículo 1, más el que
dedique al artículo 2 más el dedicado al
artículo 3, no puede exceder a una hora de capacidad, pues
ese es el período de tiempo que se tomó como
referencia.
Programación de la
producción
Este es una de las áreas de la
Programación Lineal más rica en aplicaciones. Un
problema de programación de la producción puede
verse como un problema de mezcla de producción para varios
periodos hacia el futuro. Se quieren determinar los niveles de
producción que permitirán a la
compañía obtener el mínimo costo (o la
máxima ganancia), cumpliendo con los requerimientos de las
limitaciones en mano de obra, maquinaria, materiales, espacio de
almacenamiento, requisito de demandas, etc.
Los problemas de Programación de
Producción tienen naturaleza recurrente, es decir que se
presentan un periodo tras otro, sólo que con algunas
variaciones en ciertos datos, como por ejemplo en las demandas, o
en las disponibilidades de algunos recursos. Por este motivo los
modelos de P.L. se usan extensivamente en este campo, pues una
vez que un modelo fue resuelto para un periodo determinado, basta
con repetir su solución para los datos del nuevo periodo,
para obtener recomendaciones acerca del programa óptimo de
producción.
Ilustremos este tipo de aplicaciones mediante al
siguiente ejemplo sencillo:
Ejemplo N° 3
Un fabricante debe cumplir los siguientes compromisos,
en el primer trimestre:
La capacidad mensual de producción de su planta
es de 20.000 unidades. El costo unitario de producción
varia cada mes, así: Enero $20, Febrero $9 y Marzo $12. La
compañía estima en $3 el costo de almacenamiento de
cada unidad que posea en la bodega él último
día del mes. La capacidad de la bodega de que dispone es
de 22.000 unidades.
La empresa tiene en el inventario 50 unidades y desea
tener 70 al final. El problema a resolver consiste en la
determinar del programa de producción mensual que minimiza
los costos totales en el trimestre.
Se supone que la producción se realiza durante
todo el mes y el despacho se efectúa él
último día de mes.
Construcción del modelo
La grafica que describe el problema puede
ser:
Deseamos determinar el programa de producción
para obtener el mínimo costo en el trimestre. Para ello
definimos las variables así:
Los problemas de este tipo también pueden
modelarse de otra manera como lo sugiere el siguiente
grafico:
Acá las variables se definen como:
En esta formulación no incluimos la posibilidad
de contar con inventario inicial ni con inventario final, lo cual
se deja como ejercicio al estudiante.
Por ejemplo, cuál sería el programa de
producción si se tienen 5.000 unidades de inventario
inicial y se desean 10.000 de inventario final.
Los problemas de programación de la
producción también pueden resolverse en forma
relativamente sencilla disponiendo los datos en una tabla, en la
cual se anotan los costos de cada acción alternativa y se
procede a obtener una solución aprovechando la estructura
característica del proceso. El final del capitulo se
resolverá este mismo problema mediante la tabla
mencionada.
Composición o
mezcla
Los problemas de mezcla ocurren en las industrias
alimenticias, petroleras, siderurgicas, en la industria
química en general, y muchas otras en las cuales se deben
mezclar sustancias.
Veamos el siguiente ejemplo sencillo conocido como el
problema de la dieta.
Ejemplo N° 4
Un granjero sabe que debe suministrar diariamente a cada
una de sus vacas, un mínimo de 27, 21 y 30 unidades de los
elementos nutricionales respectivamente. Para prepararles la comida
puede comprar dos clases de alimentos. Una libra del alimento 1
contiene 3, 1, y 1 unidades del nutriente respectivamente, y cuesta $40. Por otra
parte, una libra del alimento 2 contiene respectivamente 1, 1 y 2
unidades de los nutrientes y cuesta $20.
El granjero desea conocer cuántas libras de cada
alimento necesita utilizar para nutrir a cada una de sus vacas,
de tal forma que minimice los costos. Suponga que no hay limite
en cuanto al peso total de la comida (mezcla)
resultante.
Construcción del modelo
Para iniciar, podemos elaborar una tabla con los datos
del problema:
Un esquema de la situación, puede ser:
Sean libras del alimento i que dedicaremos a la
preparación de la dieta
para una vaca
El objetivo es minimizar los costos. El modelo
queda:
Minimizar: Costo
Sujeto a:
Composición de la dieta
Nutriente
(unidades de
vaca)
Nutriente
(unidades de
vaca)
Nutriente
(unidades de
vaca)
Se deja al estudiante la comprobación de la
consistencia de las unidades.
Veamos otro ejemplo que ilustra el caso de
composición o mezcla de ingredientes.
Ejemplo N° 5
Una compañía petrolera produce dos tipos
de gasolina, la corriente y la extra. La corriente se vende a
$3000 galón y la extra a $3600. Las gasolinas se fabrican
a partir de dos crudos, cuyos análisis de componentes
aparecen a continuación:
La gasolina corriente debe contener máximo 60%
demientras que la
extra debe contener mínimo 50% de
El oleoducto de la compañía puede
suministrar un máximo de 2 millones de galones crudo 1, y
3 millones de crudo 2, al día.
La compañía espera vender a lo
máximo 5 millones de galones de gasolina corriente y 1
millón de gasolina extra, cada día.
¿Cómo debe proceder la empresa para
obtener la máxima ganancia diaria?
Construcción del modelo
Elaboraremos una tabla con los datos importantes acerca
de las gasolinas, así:
Un esquema de la situación puede ser:
Las variables se definen así:
Seanel
número de galones de crudo que se dedican a producir la gasolina corriente, extra).
Debemos suponer que al mezclar por ejemplo galones de crudo 1 y
galones de crudo 2,
resultaran galones
de gasolina 1, pues no hay pérdidas en la
operación.
Considerando que el objetivo es maximizar las utilidades
por venta de las gasolinas, y que estas deben cumplir unos
requisitos de composición, además de tener limites
en la producción, debido a la demanda y limites en la
disponibilidad de crudos, el modelo del problema
será:
Maximizar:
Sujeto a:
Composición de gasolinas
en la
corriente: gal
deen gas.
corriente).en la
extra: gal de
en gas.
corriente).
Disponibilidad de crudos:
6
(galón de crudo 1)
6
(galón de crudo 2)
Ventas máximas (producción
máxima)
6
(galón de corriente)
6
(galón de extra)
Para terminar la discusión del ejercicio,
deduzcamos las unidades de la restricción de
composición de la gasolina corriente:
galón de galón de crudo galón de crudo 1
+ 0.70 galón de galón de crudo galón de crudo 2 = galones de
Unidades idénticas a las que se obtienen en el
lado derecho, así:
0.60 galones de B/galones totales de gas corriente *(
X11 galones de crudo 1+ X21 galones de crudo 2) = 0.60 galones de
B/galones totales de gasolina corriente*(galones totales de
gasolina corriente) = galones de B
El estudiante debe notar que en la solución del
problema no hemos considerado la posibilidad de que el proceso
permita separar los componentes de cada crudo, para con ellos
elaborar las gasolinas. ¿Será posible realizar
esto?
Se deja como ejercicio la formulación bajo este
enfoque.
Aplicaciones en las finanzas
Este tipo de problemas surge cuando un ejecutivo del
área financiera dispone de un capital C y tiene que elegir
entre diferentes
alternativas de inversión, cada una de las cuales tiene
una rentabilidad y un riego determinados. El objetivo de este
tipo de problemas es naturalmente la maximización del
rendimiento o la minimización del riesgo
financiero.
Las restricciones provienen comúnmente de
aspectos como : capital disponible, leyes financieras,
políticas de la compañía, riesgo
máximo permitido, etc.
Muchas situaciones de decisión financiera se han
formulado y resuelto usando diferentes técnicas de la
programación matemática, pero si un problema puede
formularse como un modelo de P.L., su solución se obtiene
de una manera más eficiente.
A continuación discutiremos un problema
simplificado que ilustra este tipo de decisiones.
Ejemplo N° 6
Un inversionista dispone de $30.000.000 y desea
invertirlos de tal manera que maximice la ganancia en el periodo
de tres años.
Tiene las siguientes posibilidades de
inversión:
Acciones: Disponible al inicio de cada año,
durante los tres próximos años. Cada peso invertido
en Acciones, retorna 1.20 al siguiente año, a tiempo para
reinvertir el dinero nuevamente. Puede invertir máximo
$12.000.000 cada vez.
Bonos: Disponible a principio del primer año.
Cada peso invertido le retorna 1.50 al cabo de dos años, a
tiempo para reinvertirlos. Puede invertir un máximo de
$20.000.000 en esta alternativa.
Certificados de depósito a dos años:
Disponible al principio del segundo año. Cada peso
invertido le retorna 1.60 dos años después. Puede
invertir un máximo de $15.000.000
Dólares: Disponible al inicio del tercer
año. Cada peso invertido le retorna 1.40, un año
después. Puede invertir un máximo de
$10.000.000
Si por las limitaciones en la cantidad invertida en las
alternativas, en determinado año no se invierte todo el
dinero disponible, el sobrante se deja en una cuenta de ahorros,
que indica una rentabilidad del 12% anual.
Construcción del modelo:
Lo primero que podemos hacer es un esquema de las
posibilidades de inversión, para el horizonte de tiempo a
considerar. Como lo indica el enunciado, se desea estudiar un
periodo de tres años.
En la gráfica se muestran las variables asignadas
a cada actividad. Esta es una forma valida y muy ilustrativa de
definir las variables que se usan:
De esta manera, las variables se definieron
como:
Xij: cantidad invertida en la alternativa al principio del año
j;
El objetivo es obtener la máxima ganancia al
término del tercer año, y también puede
entenderse como obtener el máximo retorno total al
término del mismo periodo.
Al inicio de cada año, en el momento de efectuar
las inversiones, hay dos tipos de limitantes. La primera
consistente en que no se puede invertir más de la cantidad
disponible para ello y la segunda, derivada de la decisión
administrativa de limitar las cantidades que se pueden invertir
en algunas alternativas.
Considerando el análisis anterior, el modelo de
P.L., es:
Maximizar: utilidad
Sujeta a:
Capacidad de inversión en cada
año:
Año 1:
Año 2:
Año 3:
Inversión máxima en cada
alternativa:
con Xij
Como se anotó antes, la función del
objetivo pudo expresarse como:
Con lo cual el modelo tendrá una solución
idéntica a lo que se obtendría con la
función objetiva propuesta. (Verifíquese
solucionando ambos modelos).
El problema del
transporte
Es una de las más conocidas aplicaciones de la
Programación Lineal. Se presenta cuando por ejemplo
necesitamos tomar decisiones con respecto a las mejores rutas de
distribución de artículos desde centros productivos hasta
bodegas o
almacenes.
El siguiente ejemplo nos ayudara a comprender las
características de este tipo de
situación.
Ejemplo N° 7
Una compañía embotelladora tiene plantas
ubicadas en Medellín, Bogotá y Cartagena. La
capacidad de cada una de las plantas es:
La empresa surte a cuatro distribuidoras localizadas en
diferentes zonas del país. La demanda esperada de cada uno
de los distribuidores es la siguiente:
El costo de transportar una caja de cada planta a cada
distribuidor es:
¿Cómo deben programarse los envíos
desde las plantas hasta los distribuidores para tener el
mínimo costo total?
Construcción del modelo:
La situación puede esquematizarse como se muestra
abajo, lo cual nos sugiere definir las variables como:
Xij: cantidad de cajas enviadas de la planta hasta la bodega
j;
Conociendo las capacidades, las demandas esperadas y los
costos, el modelo puede escribirse como:
Minimizar costo:
Sujeta a:
Capacidad de las plantas
Medellín:
Bogotá:
Cartagena:
Demandas de los distribuidores:
1
2
3
4
con
Como el objetivo es minimizar el costo total de los
envíos, es de esperarse que a cada distribuidor se le
envie justamente lo que necesita, motivo por el cual todas las
restricciones de demanda se cumplirán como si fueran
igualdades. Por ello si las expresaremos como igualdades, la
solución del modelo seria la misma.
Por otro lado debe tenerse en cuenta que cuando la
demanda total es inferior a la oferta total, un problema de
transporte tendría una solución en la cual se
satisfacen todas las demandas sobrando capacidad en las plantas,
pero cuando la demanda total es superior a la oferta total, el
problema no tendría solución.
Para que este último caso tenga solución,
se debe agregar al modelo una planta ficticia con capacidad igual
a la que haga falta para igualar la demanda total. Esta
operación se conoce como balanceo y será discutida
más en detalle cuando estudiemos el algoritmo especial
para resolver el problema transporte.
Problema del personal
necesario
Ejercicio N° 8
El administrador de un peaje determinó que el
número de empleados que necesita se distribuyen durante el
día así:
Cada empleado trabaja 8 horas diarias consecutivas. El
administrador desea conocer el número mínimo de
empleados que debe tener para cumplir con las necesidades de
personal durante el día.
Construcción del modelo
La situación puede visualizarse
gráficamente, de la siguiente manera:
El problema del administrador del peaje consiste en
determinar el número de empleados que deben iniciar
trabajo en cada uno de los turnos, de tal forma que se cumplan
los requisitos de personal en ellos, contando con el
mínimo posible de empleados.
Las variables se pueden definir como:
Xi: cantidad de personas que inician un trabajo a la
hora
Cada empleado labora 8 horas consecutivas, entonces
presta sus servicios en dos de los turnos en que se
dividió el día para el estudio.
El modelo de programación lineal es:
Minimizar:
Sujeta a:
Personal necesario en cada intervalo
de 6 –
10
de 10 –
14
de 14 –
18
de 18 –
22
de 22 –
2
de 2 –
6
con
Debe aclararse que en las restricciones se pudo escribir
relación de igualdad en lugar de la relación mayor
o igual, pues el enunciado así lo sugiere. Se optó
por considerar las desigualdades como mayor o igual, para dar
más libertad en la solución del problema, ya que
colocando igualdades se limita la solución a dar valores
que cumplan estrictamente las igualdades, lo cual en algunos
problemas (éste es uno) implica inexistencia de
solución. En cambio al colocar desigualdades mayor o
igual, se permite que las variables tomen valores de tal forma
que se cumplan las desigualdades y como el objetivo es minimizar,
es de esperarse que las variables tomarán los
mínimos valores posibles, dando igualdades en todas las
restricciones en que se pueda.
Se deja como ejercicio al estudiante la solución
de los dos modelos, para que verifique los comentarios
anteriores.
Problemas de los
patrones de corte
Ejemplo N° 10
Una empresa produce papel en rollos de 90 cm. de ancho y
100 m. de largo, pero muchas veces recibe pedidos para despachar
rollos de dimensiones menores. En este momento necesita cumplir
con la siguiente orden de producción:
La compañía desea determinar la forma de
cortar los rollos estándar, de tal manera que se produzca
el mínimo sobrante de papel.
Elabore el modelo matemático de P.L. para este
problema.
Construcción del modelo:
Obviamente la solución a este problema implicara
que sea necesario despachar dos o más rollos para obtener
la longitud pedida de cada uno de los anchos, ya que el rollo
estándar solo mide 100 m. de largo. También
aceptemos que el papel sobrante es todo rollo inferior a 25
cm.
Para entender mejor la lógica de solución
del problema, determinemos todas las formas en que se puede
cortar un rollo de ancho de 90 cm., para obtener anchos de 75, 35
y 25 cm.
Si tomamos como referencia un metro del rollo de ancho
estándar, las posibles formas de corte son:
Observemos que hay cuatro modalidades de corte, en cada
una de las cuales se obtiene un número de franjas de los
anchos necesarios, con un desperdicio determinado.
Las actividades alternativas a desarrollar son las
cuatro modalidades de corte, cada una con su sobrante asociado
por cada metro.
Las características de los cuatro cortes
posibles, se resumen en la siguiente tabla, en donde como se dijo
los datos son para cada metro de ancho de 90 cm. que se corte en
cada modalidad.
Podemos definir las variables del modelo
como:
Xi: número de metros del rollo estándar
cortados en la modalidad i.
Sj: número de metros del ancho j, cortados en
exceso sobre lo pedido (j= 1, 2, 3).
Con lo cual al modelo puede plantarse
así:
Minimizar: Sobrante: 0.15X1 + 0.20X2 + 0.05X3 +
0.15X4
Sujeta a:
Cantidad necesaria de cada ancho
1X1 > 200
2X2 + 1X3 > 500
2X3+3X4 > 300
con Xi > 0, i, Sj > 0, j
Si escribiéramos las restricciones como
igualdades, puede presentarse el caso de que el problema no tenga
solución factible, al ser imposible encontrar modalidades
de corte que produzcan exactamente las cantidades pedidas de cada
ancho.
Una alternativa para no usar las relaciones mayor o
igual y en cambio utilizar relaciones de igualdad, es introducir
al lado izquierdo de las restricciones las variables Sj para
indicar el número de metros de ancho j, cortado en exceso
sobre lo pedido.
Se pide al estudiante que escriba el modelo adecuado
para representar la situación que se acaba de
mencionar.
Ejemplo N° 11
Una empresa se dedica al transporte aéreo de
cargas y cuenta para ello con un avión que tiene tres
compartimientos: frontal, central y trasero. Las capacidades en
peso y espacio para cada compartimiento son:
Por motivos técnicos, debe tenerse igual
proporción de peso ocupado a capacidad en peso en cada
compartimiento.
La empresa recibió el encargo de transportar la
carga de cuatro clientes pudiendo aceptar cualquier
fracción de ellos.
La información de peso, volumen y utilidades de
las cargas es:
¿ Cómo debe programar la ocupación
del avión para obtener la máxima
ganancia?
Construcción del modelo:
Un problema de este tipo es en realidad, similar a un
problema de capacidades de peso y volumen de los
compartimientos.
Antes de construir el modelo, debemos calcular el
volumen por tonelada de cada carga.
Los resultados se registran en la siguiente
tabla:
Las variables de decisión
serán:
Xij; toneladas de la carga i a transportar en el
compartimiento j
( i= 1, 2, 3, 4); ( j= F, C, T )
El modelo de P.L. puede ser el siguiente:
Maximizar:
Utilidad =
Sujeta a:
Capacidades de peso en los compartimientos
Proporción de peso en los
compartimientos
Problema de mezcla de
productos con función objetivo separable
Ejemplo N° 12
Una compañía produce tres artículos
A, B, C. Cada unidad de A, requiere una hora de maquinaria, ocho
horas de mano de obra y cuatro libras de materia.
Cada unidad de B, necesita tres horas de maquinaria,
tres horas de mano de obra y tres libras de materia.
Cada unidad de C, requiere dos horas de maquinaria,
cuatro horas de mano de obra y dos libras de materia.
La empresa dispone de 300 libras de materia prima, 800
horas de mano de obra y 80 horas de maquinaria, para el
próximo periodo.
El precio de venta y por ende las utilidades de los
artículos, van rebajando a medida que aumenta la cantidad
vendida, como se indica en la siguiente tabla:
¿Cuál será el programa de
producción y ventas que maximiza la utilidad
total)
Construcción del modelo:
Inicialmente elaboramos una tabla con los datos de
consumo de los recursos de la empresa:
No es difícil detectar que las actividades
alternativas que pueden realizarse son la fabricación de
cada uno de los artículos. Por ello definimos las
variables como:
Xi: número de unidades del articulo i que deben
fabricarse en el periodo.
La definición anterior es la típica cuando
tenemos varias actividades que compiten por varios recursos. El
paso siguiente será la elaboración de la
función del objetivo y de las restricciones. Pero
encontramos que la definición de las variables no nos
permite escribir una función objetivo
válida.
En la función del objetivo hallaremos el
inconveniente de que tenemos cuatro coeficientes objetivo
diferentes para el articulo A, tres para el artículo B y
dos para el artículo C.
¿Cuál de ellos colocar en la
función objetivo?
La situación anterior refleja la no
proporcionalidad de la utilidad y la cantidad producida. Por lo
tanto ese problema no cumple una de las condiciones
básicas para plantearse directamente como un modelo de
Programación Lineal.
Para adecuar el problema a la forma en que pueda
formularse como modelo de P.L., es posible a veces calcular una
utilidad promedia para cada artículo y colocar este valor
como coeficiente objetivo. Claro que en ese caso estaremos
aceptando que la solución hallada será apenas
aproximada, debido a la simplificación de los valores
reales.
Pero afortunadamente para este tipo de problemas en
donde el objetivo es maximizar y los coeficientes van
disminuyendo al aumentar la variable, es posible construir una
función objetivo en la cual se definan las variables para
reflejar los intervalos que considera el problema.
Para mejor entendimiento construyamos una gráfica
con los intervalos de la variable X1.
Como se dijo las unidades comprendidas en el intervalo
0-40 dan utilidades de $10, las comprendidas en el intervalo
41-100 dan utilidad unitaria de $9, etc.
Para reflejar este hecho en la función objetivo,
vamos a definir las variables así:
Xij: cantidad de unidades vendidas del articulo i, que
pertenecen al intervalo j
(i=1, 2, 3; j=1, 2, 3, 4)
Xi: cantidad total de unidades del articulo i
vendidos.
De esta manera el modelo de P.L., queda:
Maximizar: utilidad:
Sujeta a:
Limites de las cantidades que pertenecen a cada
intervalo.
No se incluyeron X14, X23 y X32 pues estas variables no
tienen límite en sus valores.
Por comodidad al escribir las restricciones de uso de
los recursos, podemos expresar las siguientes
igualdades:
Luego se escriben las restricciones de disponibilidad de
recursos así:
Maquinaria:
Problema del
transbordo
La compañía X puede producir su principal
artículo en dos departamentos diferentes. Cada
departamento puede enviar lo producido al centro de control de
calidad final A o al centro de control de calidad final B, desde
los cuales se remite a cualquiera de las cuatro líneas del
empaque y envío de que dispone la empresa. El departamento
1 tiene capacidad para producir 80 unidades por hora y el
departamento 2 para producir máximo 60 unidades por hora.
Según las demandas esperadas, se ha programado que las
líneas de empaque atiendan al menos las siguientes
cantidades por hora: 30, 20, 40, 40 respectivamente.
La siguiente tabla muestra los tiempos (minutos)
promedio que se gasta en los diferentes movimientos de cada
unidad del producto.
En el centro 1 de control de calidad, se demora 4
minutos para revisar un artículo y en el centro 2 de
control de calidad se demora 6 minutos.
¿Cómo debe organizarse el flujo de las
unidades entre los departamentos productivos y las líneas
de empaque y envío, pasando por algunos de los centros de
control de calidad, de tal forma que se obtenga un mínimo
tiempo total de producción?.
Problema de asignación
Cierta compañía tiene tres empleados para
asignar a tres solicitudes de reparación de licuadoras en
la casa de los clientes, que deben ser atendidos mañana,
por lo cual los empleados viajan directamente de su hogar hasta
el del cliente.
Como la empresa subsidia el combustible del
vehículo de los operarios, desea ahorrar lo máximo,
motivo por el cual necesita conocer la forma de asignar los
operarios a los clientes de tal manera que se tenga la menor
distancia total de viaje de los empleados.
La tabla siguiente muestra las distancias desde la casa
de cada empleado hasta la de cada cliente.
Programación
entera
Corte de madera
Una marquetería debe enmarcar 175 cuadros de
119×96 cm. En el mercado puede comprar varillas de la moldura
indicada con longitud de 300 cm.
¿Cómo deben cortarse las varillas para
obtener los marcos requeridos, obteniendo el menor sobrante
posible?
Solución:
Modalidades de corte
Xi: Número de varillas estándar cortadas
en la modalidad i (i= 1, 2, 3)
Para 175 marcos se necesitan 350 piezas de cada
longitud.
Minimizar: 62X1 + 1X2 + 30X3 longitud
sobrante
s.a: 2X1 + 1X2 > 350 piezas de longitud
119
2X2 + 3X3 > 350 piezas de longitud 90
Pregunta: ¿ El valor de las Xi tiene que ser
entero?
¿Cuál será la diferencia de
sobrantes, si permite que el valor de los Xi sea
fraccionario?
Programación de la producción de un
ensamble.
Cierta empresa produce un artículo que se forma
con cuatro piezas del componente A y tres piezas del componente
B.
Las piezas se pueden fabricar en cualquiera de las tres
máquinas diferentes que posee la compañía,
las cuales transforman las dos materias primas en las piezas que
van al ensamble del producto final.
La tabla siguiente muestra el número de gramos de
cada materia prima que deben utilizarse en cada máquina
para realizar un ciclo de producción de las componentes.
La misma tabla muestra el número de componentes de cada
tipo que se obtienen en cada ciclo de producción de cada
una de las maquinas, así como el número de gramos
disponibles de las materias primas.
¿Cómo debe programarse la
producción para obtener la máxima cantidad de
artículos?
Suponga que una compañía tiene cuatro
proyectos llamémoslos A, B, C, D, que pueden o no
llevarse a cabo, pero un proyecto no puede ejecutarse
parcialmente.
Los proyectos B y D no se pueden ejecutar
simultáneamente (son mutuamente excluyentes)
La información relativa a los proyectos
es:
La compañía dispone actualmente de 25.000
y al inicio del segundo año recibirá $5.000 de
otras inversiones. Además necesita disponer de 15.000 al
inicio del tercer año para cancelar unos compromisos en
esa fecha.
Elabore el modelo de P.L. para determinar cuáles
proyectos ejecutarse con el propósito de maximizar el
valor presente neto de las inversiones realizadas.
Autor:
Rafael Freites
Página anterior | Volver al principio del trabajo | Página siguiente |