UNIVERSIDAD NACIONAL
DE COLOMBIA
. MODELO DE PROGRAMACIÓN LINEAL
. OPTIMIZACIÓN .
Integrantes:
- Laura Ximena Sierra Valero, lsierrava@unal.edu.co
- David Ricardo Rios Garcia, drriosg@unal.edu.co
- Edgar Santiago Olivos Aguirre, eolivos@unal.edu.co
- Kevin Vanegas, kavanegasm@unal.edu.co
1. Un negociante de frutas y verduras desea mandar tomate, zanahoria, manzana y
maracuyá, de Bogotá a Villavicencio. Para mandar estos productos tiene la
posibilidad de utilizar tres vehículos: un camión, un furgón y una volqueta. Las
capacidades de estos vehículos son:
El tomate y el maracuyá vienen en cajas de madera, la zanahoria viene en bultos y
las manzanas vienen en cajas de cartón: 20 manzanas por caja. En la siguiente
tabla aparecen los valores de: peso de cada paquete (kilos), volumen necesario
para cada paquete (cm3), beneficio por paquete (pesos) y número máximo de
paquetes de cada producto
Plantee el modelo correspondiente que permita maximizar el beneficio total.
Respuesta:
Usando el método Dantzig se resuelve el primer punto como modelo de asignación.
1.1. Identificación de las Actividades.
Para este modelo se identifican 4 actividades principales en combinatoria con 3 variaciones
de la actividad (método de transporte).
1) Enviar tomate → X1n
2) Enviar zanahoria → X2n
3) Enviar manzana → X3n
4) Enviar maracuyá → X4n
Donde n son las siguientes sub actividades
1) Enviar en camión → A
2) Enviar en furgón → B
3) Enviar en volqueta → C
1.2. Identificación de las entradas y salidas.
Se identificaron las siguientes entradas y salidas para el sistema completo:
Y se identificaron las siguientes entradas y salidas para la combinación de enviar los
productos en camión:
1.3. Identificación de las variables de holgura.
Dado que los medios de transporte manejan dos limitantes que son Peso y Volumen y dada
la presentación de los productos a enviar es muy poco probable que se llegue a el tope
exacto de estas limitantes, por tanto se crean 2 variables de holgura relacionadas con peso
y volumen para 3 tipos de transporte diferente nos da un total de 6 variables de holgura.
(X1H,...,X6H).
1.4. Identificar los flujos externos.
Como ya lo mencionamos anteriormente los flujos externos en este modelo únicamente son
las limitantes en peso y volumen propios de cada transporte especificadas en el texto del
problema.
1.5. Plantear las ecuaciones de equilibrio.
1.6. Análisis dimensional.
Podemos observar que se han realizado las correspondientes equivalencias en pesos y
volúmenes para trabajar con un estándar de peso (Kg) y volumen (m3).
1.7. Análisis Lógico.
Haremos un análisis para la fila “Peso A”. Donde recibimos un ingreso de peso de cada uno
de los productos a enviar. Entonces recibimos 20X1A que se corresponde al peso por una
caja de tomates, sumado con 60X2A que sería el peso de un bulto de zanahoria, sumado
con 15X3A que seria el peso de una caja de maracuyá, sumado con 6X4A correspondiente
a una caja de manzanas y por último sumado con X1H que se corresponde a la variable de
holgura del peso o en otras palabras, lo que falta para llenar el peso total del camión.
Obtenemos entonces la ecuación: 20X1A + 60X2A + 20X3A + 6X4A +X1H = 20000 kg.
2. Un campesino desea planear su cultivo de maíz por un periodo de 3 años. Al
empezar el primer año tiene “a” kilos de granos de maíz y se sabe que, al sembrar
un kilo de granos de maíz, al cabo de un año, se obtienen “b” (b > 1) kilos de maíz.
Este campesino tiene mucha experiencia y sabe o puede prever gi, i = 1,..., 4, la
ganancia neta correspondiente a la venta de un kilo de maíz al empezar el año i. Al
iniciar cada uno de los tres años el campesino vende una parte del maíz disponible
y siembra el resto. Al finalizar el tercer año, o sea, al empezar el cuarto año, él
vende todo el maíz disponible. El campesino desea saber cuántos kilos debe
vender y cuantos sembrar al comenzar cada uno de los tres años de tal manera
que maximice sus ganancias. Plantee el anterior problema de programación lineal.
Respuesta:
Usando el método Dantzig se resuelve el primer punto como modelo de producción
por periodos.
2.1. Identificación de las Actividades.
Se hace la identificación de las siguientes actividades:
1) Sembrar Maíz → XAt
2) Vender Maiz → XBt
Donde t es el periodo en el cual se lleva a cabo dicha actividad. Nota: para el periodo 1 no
existe venta de maíz y apesar que son 3 periodos, dado que la venta se hace al principio del
siguiente periodo la venta final se hace en el periodo 4.
2.2. Identificación de las entradas y salidas.
Se identificaron las siguientes entradas y salidas para el sistema completo:
Se identificaron las siguientes entradas y salidas por cada actividad:
2.3. Identificación de las variables de holgura.
Dado que el maíz que no se siembra se vende, es decir, el maíz disponible en cada periodo
será usado ya sea para sembrar o vender y no habrá sobrantes, no existen variables de
holgura en este modelo.
2.4. Identificar los flujos externos.
Los flujos externos que se manejan en este modelo son únicamente la cantidad de maíz
disponible al inicio de cada periodo, no existen limitaciones más allá de la cantidad de maiz
disponible para siembra o venta.
2.5. Plantear las ecuaciones de equilibrio.
2.6. Análisis dimensional.
En la descripción de este problema no se manejan cantidades cuantitativas sin embargo se
especifica que las cantidades a trabajar tanto en siembra como venta serán en peso (kg).
2.7. Análisis Lógico.
Haciendo el análisis lógico sobre la fila de “kg de maíz para p2” tenemos que -bXA1 es la
cantidad de maíz producido en el periodo 1, sumado con 1XA2 que seria la cantidad de
maíz a sembrar en el periodo 2, sumado también 1XB2 que sería la cantidad de maíz a
vender del periodo 1 tiene que ser igual a 0, de manera que la ecuación queda de la forma:
-bXA1 + XA2 + XB2 = 0
3. Una planta manufacturera tienen un contrato para producir 1200 unidades de cierta
mercancía C, con el agendamiento de entregas como se ve en la tabla
¿Qué planificación de contrataciones, despidos, producción y almacenamiento
debería tomar el productor para minimizar el costo de su contrato bajo las
siguientes condiciones?
a. Cada unidad de producción no entregada a tiempo involucra una penalización de
$30 por semana hasta su entrega.
b. Cada producto extra requiere almacenamiento con un costo de $10 /por
producto/semana.
c. Todas las entregas requeridas deben cumplirse para el final de la quinta semana.
d. Inicialmente hay 20 trabajadores y 10 unidades de producto C.
e. Cada trabajador implicado en la producción durante una semana puede producir 8
unidades de producto C.
f. Cada trabajador usado para entrenamiento de nuevos empleados puede entrenar
a 5 nuevos empleados.
g. El salario de un trabajador es de $100 por semana.
h. El salario de un trabajador usado en entrenamiento más los nuevos empleados es
de $600.
i. El costo de despedir un trabajador es de $150.
Identificación de las entradas y salidas por el sistema
Identificación de las entradas y salidas por cada actividad
El análisis dimensional se manejan los períodos por semana, donde se asocia al producto
‘C’ con la demanda del mismo.
Con una heurística de no despedir ninguna persona se tiene:
4. El Servicio de Parques Nacionales está recibiendo cotizaciones para talar árboles en tres
localidades de un bosque. Las localidades tienen áreas de 10000, 20000 y 30000
hectáreas. Una sola empresa taladora puede cotizar para no más del 50% de la superficie
en todas las localidades. Cuatro empresas han presentado sus cotizaciones por hectáreas,
en unidades monetarias para las tres localidades de acuerdo con la siguiente tabla:
¿Cuántas hectáreas deben asignarse a cada empresa para maximizar la suma total
de ingresos?
Respuesta:
M: Representa un número positivo muy pequeño
Suma de oferta: 12.000
Suma de demanda: 12.000
Ingreso Máximo: 36.700
5. Construya el modelo de programación lineal que permita minimizar los costos de
envío de T unidades X desde seis bodegas principales a ocho puntos de destino,
en los cuales la demanda está dada respectivamente como Dj , para j = 1,2,...,n,
teniendo en cuenta que al momento de recibir los pedidos, las existencias de
bodega son Ei, con i=1,2, ..., m, en forma respectiva. Los costos unitarios de
transporte desde cada origen a cada destino son cij.
Respuesta:
Se plantea un modelo de transporte donde se envían unidades Xij, tomando i
como el origen y j como el destino:
Xij: Unidades enviadas desde origen i=1,2,...,m hasta el destino j=1,2,...,n
Cij: Costo unitario por transporte desde i hasta j
ai: Oferta del origen i= 1,2,...,m
bj: Demanda del destino j=1,2,...,n
En este modelo se pueden presentar tres casos:
- Cuando la demanda es mayor que la oferta, es decir 𝑎 < 𝑏
𝑖 𝑗
Aparece una variable de holgura, ya que para balancear este
problema es necesario agregar un origen ficticio m+1 que supla con
la oferta faltante
- Cuando la oferta es mayor a la demanda, es decir 𝑎𝑖 > 𝑏𝑗
Igual que para el caso anterior aparece una variable de holgura, ya
que en este caso entra un nuevo factor que sería un sobrante por el
exceso de oferta, sin embargo es posible agregar un destino ficticio
n+1 el cual se asume que se enviaría el excedente a este destino
- Cuando la oferta es igual a la demanda, es decir 𝑎𝑖 = 𝑏𝑗
Para este caso no aparecen variables de holgura ya que no existe un
exceso de demanda o un exceso de oferta, es decir el modelo está
balanceado
6. Acerías Bacatá prepara una aleación de tipo especial en un alto horno, el cual debe
ser cargado con dos toneladas de material. Por requisitos de calidad dicha aleación
debe contener mínimo 30% de sílice pero no más de 35%; y máximo 28% de
aluminio. La compañía carga el horno con hierro, Zinc y Cobre, los cuales adquiere
a 3.000, 7.000 y 6.000 pesos por kilo respectivamente. ¿Con qué cantidad de cada
producto se debe alimentar el horno si se sabe que el hierro contiene 18% de sílice
y 15% aluminio; el zinc contiene 7% de Sílice y 25% de aluminio; mientras que el
cobre contiene 16 % de sílice y 5% de aluminio?
Formule el modelo de producción que permita minimizar los costos de preparación
de la aleación.
Respuesta:
- Definición de variables:
Primero definiremos las variables con las que se trabajarán en este ejercicio
con sus unidades definidas
X1 = Kilogramos de Hierro cargados en el horno
X2 = Kilogramos de Zinc cargados en el horno
X3 = Kilogramos de Cobre cargados en el horno
- Restricciones:
El horno no puede estar vacío
X1+ X2+ X3 > 0
El horno debe ser cargado con una cantidad específica de material:
X1+ X2+ X3 ≤ 2000
Restricción de la cantidad de sílice y aluminio en el horno:
0,18 x 1+0,07 x 2+ 0,16 x 3 ≥ 600, → 0,3% de sílice como mínimo
0,18 x 1+0,07 x 2+ 0,16 x 3 ≤ 700, → 0,35% de sílice como máximo
0,15 x 1+0,25 x 2+ 0,05 x 3 ≤ 560, → 0,28% de aluminio como máximo
- Tabla de datos y restricciones:
- Función Objetivo:
MIN Z= 3000 x 1 + 7000 x 2+ 6000 x 3
7. Identifique una situación de su contexto o un contexto conocido, que pueda ser
modelado en el marco de la programación matemática lineal, determinística,
estática y continua. Describa el contexto, delimite el problema y formule el modelo
correspondiente con la metodología de Dantzig.
Se planteó una situación de la vida cotidiana con diferentes datos, tablas y procesos que se
realizaron en un libro de excel que se adjunto al trabajo enviado
