Agenda
Notas
Proyectos
Modelación en redes
Problema de transporte
Problema de transbordo
Corte Evaluación Método de evaluación Valor porcentual
Proyecto 30
3 CORTE 40% Talleres y quices 20
Examen Final 50
Proyecto
I. DATOS DEL PROYECTO
Aplicación de programación lineal para la organización y
TÍTULO DEL PIF
contratación de un Equipo de Futbol
Fechas de entrega 16 de noviembre 2022
Modelación en redes
Modelos de redes
• Terminología de redes
• Nodo o vertice – un punto (instalación, DC, Planta, región)
• Arco – enlace entre dos nodos (camios, flujos, etc)
• Algunos tipos de problemas de red
• La ruta más corta – cuál es la ruta más corta entre el nodo i y el nodo j
• Agente viajero – cuál es el tour más corto que visita cada nodo una única vez
• Ruteo de vehículos – cuál es el conjunto de recorridos de menor costo para que los
vehículos distribuyan producto desde un nodo origen a otros nodos de demanda.
• Flujo de costo mínimo - cuáles son los flujos de menor costo de un producto a través de
una red que satisface la demanda en ciertos nodos y no excede los suministros
disponibles en otros nodos.
• Asignación de trabajos o personas. De acuerdo a unos requerimientos especificados se
pueden asignar elementos para que cumplan con las condiciones o necesidades del
problema a analizar, minimizar gasto/costos, maximizar eficiencia, utilidad etc…
Aproximación al modelado de
redes
• Necesidades básicas para la modelación en redes
• Identificar y cuantificar las compensaciones
• Entender enfoques comunes y sus fortalezas/debilidades
• Formular el modelo matemático para optimización
• Como generalizar el modelo para soluciona una clase de problemas
• Interpretación algebraica de la literatura
• Solución
• Paquetes especializados
Ejemplo: Arena & CIA
• El problema:
• Arena & CIA tiene dos instalaciones que extraen, limpian y clasifican arena
para usar en cemento, cajas de arena, y playas. Ellos distribuyen arena
desde sus dos planta a tres diferentes regiones donde es empacada y
vendida
• Cada planta tiene un máximo suministro disponible cada semana y cada
región tiene una demanda semanal mínima esperada. El costo de distribuir
una tonelada de arena difiere según la planta de origen y la región destino,
entre otros factores.
• Objetivo del problema
• ¿Cuánta arena debe Arena & CIA enviar desde cada una de sus plantas a las
regiones cada semana para satisfacer la demanda al menor costo de
distribución?
Problema transporte
Arena & CIA – Red y Notación
• Índices
P1 • Plantas i
• Regiones j
P1
P2 • Variables de decisión
• Xij = Flujo sobre el arco de la planta i a
la región j (tons) ∀ 𝑖,𝑗
P2 P3
Programación matemática
El objetivo es encontrar la solución para
x que minimiza la función objetivo sujeto
a una serie de restricciones
min 𝑧 = 𝑓(𝑥)
𝑔 𝑥 ≥𝑏
𝑥≥0
Arena & CIA – Formulación
Min z = 𝑐𝑖𝑗 𝑥𝑖𝑗 Z = C11X11 + C12X12 +C13X13 + C21X21 + C22X22 + C23X23
𝑖 𝑗
𝑥𝑖𝑗 ≤ 𝑆𝑖 ∀𝑖 ∈ I X11 + X12 + X13 ≤ S1
X21 + X22 + X23 ≤ S2
𝑗
X11 + X21 ≥ D1
𝑥𝑖𝑗 ≥ 𝐷𝑗 ∀𝑗 ∈ J
X12 + X22 ≥ D2
𝑖
X13 + X23 ≥ D3
X11 ≥0
X12 ≥0
𝑥𝑖𝑗 ≥ 0 ∀ 𝑖, 𝑗 X13 ≥0
X21 ≥0
X22 ≥0
X23 ≥0
Arena & CIA – Red y Notación
𝑆𝑖 = 𝑆𝑢𝑚𝑖𝑛𝑖𝑠𝑡𝑟𝑜 𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑙𝑒 𝑑𝑒 𝑎𝑟𝑒𝑛𝑎 𝑑𝑒 𝑙𝑎 𝑝𝑙𝑎𝑛𝑡𝑎 𝑖 𝑡𝑜𝑛𝑠
∀𝑖 ∈𝑆
𝐷𝑗 = 𝐷𝑒𝑚𝑎𝑛𝑑𝑎 𝑑𝑒 𝑎𝑟𝑒𝑛𝑎 𝑒𝑛 𝑙𝑎 𝑟𝑒𝑔𝑖ó𝑛 𝑗 (𝑡𝑜𝑛𝑠) ∀ 𝑗 ∈ 𝐷
𝐶𝑖𝑗 =
$
𝐶𝑜𝑠𝑡𝑜 𝑑𝑒 𝑒𝑛𝑣𝑖𝑎𝑟 𝑎𝑟𝑒𝑛𝑎 𝑑𝑒𝑠𝑑𝑒 𝑙𝑎 𝑝𝑙𝑎𝑛𝑡𝑎 𝑖 𝑎 𝑙𝑎 𝑟𝑒𝑔𝑖ó𝑛 𝑗
𝑡𝑜𝑛
∀ 𝑖, 𝑗
Arena & CIA – Red y Notación
Información de entrada
𝑆1 = 100, 𝑆2 = 125
𝐷1 = 25, 𝐷2 = 95, 𝐷3 = 80
𝐶11 = 250, 𝐶12 = 325, 𝐶13 = 445
𝐶21 = 275, 𝐶22 = 260, 𝐶23 = 460
Problemas de
transbordo
Ejemplo 2: Arena & CIA (2)
• El problema:
• Arena & CIA tiene dos instalaciones que extraen, limpian y clasifican arena
para usar en cemento, cajas de arena, y playas. Se han agregado 2 centros
de empaque a la red. La arena ahora va de las plantas a los centros de
empaque y luego a las diferentes regiones donde es vendida
• Cada planta tiene un máximo suministro disponible cada semana y cada
región tiene una demanda semanal mínima esperada. El costo de distribuir
una tonelada de arena difiere según la combinación planta de origen, centro
de empaque y región destino, entre otros factores.
• Objetivo del problema
• ¿Cuánta arena debe Arena & CIA enviar desde cada una de sus plantas a los
centros de empaque y luego a cada región cada semana para satisfacer la
demanda al menor costo de distribución?
Arena & CIA – Red y Notación
Índices
• Plantas i P1
• Empaque k
• Regiones j P1
C1
Variables de decisión P2
• Xik = Flujo sobre el arco de la
planta i al centro de empaque k P2
C2
∀ 𝑖, 𝑘 P3
• Xik = Flujo sobre el arco del
centro de empaque k a la región j
(tons) ∀ 𝑘, 𝑗
Arena & CIA (2) – Formulación
Min z = 𝑐𝑖𝑘 𝑥𝑖𝑘 + 𝑐𝑘𝑗 𝑥𝑘𝑗
𝑖 𝑘 𝑘 𝑗
𝑥𝑖𝑘 ≤ 𝑆𝑖 ∀𝑖 ∈ I P1
𝑘
𝑥𝑘𝑗 ≥ 𝐷𝑗 ∀𝑗 ∈ J P2
𝑘
𝑥𝑖𝑘 − 𝑥𝑘𝑗 = 0 ∀𝑘 ∈ K
𝑖 𝑗
P3
𝑥𝑖𝑗 ≥ 0 ∀ 𝑖, 𝑗
Arena & CIA – Red y Notación
• Información de entrada
• 𝑆𝑖 = Suministro disponible de arena de la planta i (tons) ∀ 𝑖 ∈ 𝑆
• 𝐷𝑗 = Demanda de arena en la región j (tons) ∀ 𝑗 ∈ 𝐷
• 𝐶𝑖𝑘 = Costo de enviar arena desde la planta i a la región j ($/ton) ∀ 𝑖, 𝑘
• 𝐶𝑘𝑗 = Costo de enviar arena desde la planta k a la región j ($/ton) ∀ 𝑖, 𝑗
Arena & CIA – Red y Notación
Información de entrada
• S1=100, S2=125
• D1=25, D2=95, D3=80
• C1A = 190, C1B= 210
• C2A = 185, C2B= 105
• CA1=175, CA2=180, CA3=165
• CB1=235, CB2=130, CB3=145
Casos especiales (asignación/programación)
• El número de agentes excede el número de tareas:
𝑥𝑖𝑗 ≤ 1, 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑎𝑔𝑒𝑛𝑡𝑒 𝑖𝑗
• El número de tareas excede el número de agentes
• Añada suficientes agentes (fantasmas/falsos) para igualar el npumero de
tareas. Los coeficientes de las variables serán de 0 o muy altos o muy bajos,
según lo requiera el problema.
Ejercicio en Clase
Building Building Brick Company Company (BBC) tiene ordenes por 80 ton
de ladrillos en tres locaciones suburbanas: Northwood (25 ton), Westwood
Westwood (45 ton) y Eastwood (10 ton). BBC tiene dos plantas, cada una
de las cuales puede producir 50 ton por semana. Cuál debería ser el plan
de envíos si los costos de transporte transporte por tonelada (en US$) son:
Northwood Westwood Eastwood
• Planta 1 24 30 40
• Planta 2 30 40 42
Ejercicio en clase 2
Thomas Industries y Washburn Corporation proveen a tres firmas (Zrox,
Hewes, Rockwright) las cuales personalizan los estantes para sus oficinas.
Ambos ordenan los estantes a los mismos fabricantes, Arnold
Manufacturers y Supershelf, Inc. Actualmente la demanda semanal por
parte de sus clientes son: 50 para Zrox, 60 para Hewes, y 40 para
Rockwright. Tanto Arnold como Supershelf pueden entregar a lo sumo 75
unidades semanalmente.
Debido a largos contratos contratos, basados en acuerdos especiales, los
costos unitarios para cada estante varían para cada cliente. Éstos son:
Ejercicio en clase 2
• Fabrica – intermediario • Intermediario - Cliente
Thomas Washburn Zrox Hewes Rockwright
Arnold 5 8 Thomas 1 5 8
Supershelf 7 4 Washburn 3 4 4
Ejercicio de Tarea (Caso especial)
• La empresa de carnes “El 1 2 3 4
Establo” tiene cuatro tipos de
máquinas (A,B,C,D). La empresa A 12 14 17 19
quiere realizar un proceso de
producción y tiene 4 tipos de B 16 19 24 17
productos que realizar. La C 10 12 18 15
utilidad que genera cada
máquina según el producto es D 13 9 20 17
de:
¿qué producto de los 4 deben ser procesados utilizando los cuatro tipos de
máquinas para maximizar la utilidad, indique máquinas con productos y el
valor total de la utilidad?
