Investigación de Operaciones · II Semestre, 2026 · Tecnológico de Costa Rica
Cuatro modelos del curso con Python y R, y el problema de transbordo con Python, R y Solver
| Ruta | Integrante | Presenta |
|---|---|---|
| A | Aarón Líos Cubillo | Introducción · I.4 Asignación · II.3 Modelo matricial |
| D | David Molina Guerrero | I.1 Programación lineal · II.4 Solución en R, Python y Solver |
| J | Juan Ignacio Alpízar Villalobos | I.2 Programación lineal entera · II.5 Modelos desbalanceados |
| M | Mariana De Los Ángeles Acuña Rodríguez | I.3 Transporte · II.1 y II.2 Transbordo y transporte |
Profesor: Esteban José Ballestero Alfaro
Minimizar el costo de llevar bienes desde unos orígenes hasta unos destinos.
Repartir tareas para minimizar el costo o maximizar el rendimiento de quienes las hacen.
La mercancía puede pasar por puntos intermedios antes de llegar a su destino. Es el tema de la Parte II.
| Punto | Modelo | Librerías | Ruta |
|---|---|---|---|
| I.1 | Programación lineal | SciPy · PuLP · lpSolve | David |
| I.2 | Programación lineal entera | SciPy · PuLP · lpSolve | Juan Ignacio |
| I.3 | Transporte | PuLP · OR-Tools · lpSolve | Mariana |
| I.4 | Asignación | SciPy · PuLP · lpSolve · clue | Aarón |
Cada problema tiene al menos tres restricciones y se resuelve con varias librerías para comparar.
| Punto | Pregunta del enunciado | Ruta |
|---|---|---|
| II.1 | Qué es y qué situaciones modela | Mariana |
| II.2 | Relación y diferencias con transporte | Mariana |
| II.3 | Ejemplo y modelo matricial paso a paso | Aarón |
| II.4 | Solución con R, Python y Solver | David |
| II.5 | Modelos desbalanceados | Juan Ignacio |
linprog [1] PythonEl modelo se pasa en matrices: costos, restricciones y lados derechos.
Sólo minimiza: para maximizar se le cambia el signo a la función objetivo y después al resultado.
El modelo se escribe casi igual que en el cuaderno, como LpMaximize o LpMinimize.
En la 4.2 las variables se crean con add_variable y el solver se instala aparte (highspy).
lp() [3] RRecibe "max" o "min", la función objetivo, la matriz de restricciones, el tipo de cada una y los lados derechos.
Acepta maximizar tal cual, sin cambiar signos.
Una mueblería hace mesas y sillas. ¿Cuántas de cada una conviene hacer a la semana?
| Mesa | Silla | Disponible | |
|---|---|---|---|
| Tablones | 2 | 1 | 100 |
| Horas de trabajo | 1 | 1 | 80 |
| Utilidad (miles de ₡) | 30 | 20 |
Además, no se pueden vender más de 40 mesas.
x_1 = mesas por semana, x_2 = sillas por semana
sujeto a
| Vértice | (x_1, x_2) | Z (miles de ₡) |
|---|---|---|
| O | (0, 0) | 0 |
| A | (40, 0) | 1 200 |
| B | (40, 20) | 1 600 |
| C | (20, 60) | 1 800 |
| D | (0, 80) | 1 600 |
El máximo está en C, donde se cruzan la recta de tablones y la de horas. Es lo que las librerías tienen que devolver.
from scipy.optimize import linprog
c = [-30, -20] # sólo minimizaA = [[2, 1],
[1, 1],
[1, 0]]
b = [100, 80, 40]
r = linprog(c, A_ub=A, b_ub=b,
method="highs")
print("utilidad =", -r.fun)
import pulp
m = pulp.LpProblem("Muebleria",
pulp.LpMaximize)x1 = m.add_variable("mesas", lowBound=0)
x2 = m.add_variable("sillas", lowBound=0)
m += 30 * x1 + 20 * x2
m += 2 * x1 + x2 <= 100
m += x1 + x2 <= 80
m += x1 <= 40
m.solve(pulp.HiGHS(msg=False))
library(lpSolve)
f.obj <- c(30, 20)
f.con <- matrix(c(2, 1,
1, 1,
1, 0),
nrow = 3, byrow = TRUE)
f.dir <- c("<=", "<=", "<=")
f.rhs <- c(100, 80, 40)
sol <- lp("max", f.obj, f.con,
f.dir, f.rhs)
| Librería | Mesas | Sillas | Utilidad (miles de ₡) |
|---|---|---|---|
| SciPy | 20 | 60 | 1 800 |
| PuLP | 20 | 60 | 1 800 |
| lpSolve | 20 | 60 | 1 800 |
Utilidad máxima de ₡1 800 000 por semana.
| Restricción | Usado | Límite | Estado |
|---|---|---|---|
| Tablones | 2(20) + 60 = 100 | 100 | se agota |
| Horas | 20 + 60 = 80 | 80 | se agota |
| Mesas | 20 | 40 | sobran 20 |
Mismas restricciones lineales, pero algunas o todas las variables tienen que ser enteras [14].
| Caso | Qué es entero |
|---|---|
| Entera pura | todas las variables |
| Entera mixta | sólo algunas |
Se usa cuando las decisiones son unidades indivisibles. Redondear la solución continua puede violar restricciones o quedar lejos del óptimo.
milp [15] y PuLP [2] Pythonintegrality=[1, 1] marca las variables enteras; milp minimiza, así que se cambia el signo. En PuLP, cat="Integer" con HiGHS.
lp() [3] Rall.int = TRUE si todas son enteras, o int.vec si sólo algunas.
Dos tipos de kits, A y B. Cada kit se fabrica completo: no hay fracciones.
| Recurso | Kit A | Kit B | Disponible |
|---|---|---|---|
| Horas de ensamble | 4 | 6 | 35 |
| Componentes | 3 | 4 | 25 |
| Horas de pruebas | 2 | 1 | 12 |
| Utilidad (miles de ₡) | 45 | 60 |
x_1 = kits A por semana, x_2 = kits B por semana
sujeto a
Relajación lineal
x_1 = 4{,}625,\ x_2 = 2{,}75, con ₡373 125. No es un plan que se pueda fabricar.
Redondear a (5, 3)
4(5) + 6(3) = 38 > 35. Se sale de la región.
Óptimo entero
x_1 = 4,\ x_2 = 3, con ₡360 000: el mejor de los 29 puntos enteros factibles, comprobado también enumerándolos.
from scipy.optimize import (
milp, LinearConstraint)
c = [-45, -60] # milp minimiza
A = [[4, 6], [3, 4], [2, 1]]
b = [35, 25, 12]
r = milp(c=c, integrality=[1, 1], constraints=LinearConstraint(
A, -np.inf, b))
x1, x2 = np.rint(r.x).astype(int)
m = pulp.LpProblem("Kits_enteros",
pulp.LpMaximize)
x1 = m.add_variable("kit_A", lowBound=0,
cat="Integer")x2 = m.add_variable("kit_B", lowBound=0,
cat="Integer")m += 45 * x1 + 60 * x2
m += 4 * x1 + 6 * x2 <= 35
m += 3 * x1 + 4 * x2 <= 25
m += 2 * x1 + x2 <= 12
m.solve(pulp.HiGHS(msg=False))
library(lpSolve)
f.obj <- c(45, 60)
f.con <- matrix(c(4, 6,
3, 4,
2, 1),
nrow = 3, byrow = TRUE)
f.dir <- c("<=", "<=", "<=")
f.rhs <- c(35, 25, 12)
sol <- lp("max", f.obj, f.con,
f.dir, f.rhs,
all.int = TRUE)
| Librería | Kits A | Kits B | Utilidad (miles de ₡) |
|---|---|---|---|
| SciPy (milp) | 4 | 3 | 360 |
| PuLP | 4 | 3 | 360 |
| lpSolve | 4 | 3 | 360 |
| Restricción | Usado | Límite |
|---|---|---|
| Ensamble | 4·4 + 6·3 = 34 | 35 |
| Componentes | 3·4 + 4·3 = 24 | 25 |
| Pruebas | 2·4 + 1·3 = 11 | 12 |
| Modelo | Plan | Utilidad (₡) |
|---|---|---|
| Relajación lineal | (4,625; 2,75) | 373 125 |
| Entero | (4; 3) | 360 000 |
| Diferencia | 13 125 |
Es lo que cuesta que los kits sean indivisibles. Por eso se resuelve el problema entero y no se redondea [14][15].
lp.transport [4] REl transporte también es programación lineal. lp.transport recibe la matriz de costos, la oferta, la demanda y el signo de cada restricción.
Dos de las librerías de optimización de código abierto más usadas. Modelan un objetivo sujeto a restricciones de oferta (capacidad de las plantas) y de demanda (lo que necesita cada cliente).
Costo de llevar un saco de arroz de cada planta a cada supermercado.
| Súper A | Súper B | Súper C | Oferta | |
|---|---|---|---|---|
| Planta 1 | 200 | 300 | 400 | ≤ 100 |
| Planta 2 | 250 | 150 | 350 | ≤ 150 |
| Demanda | 80 | 120 | 50 | 250 |
x_{ij} = sacos de la planta i al súper j
sujeto a
m = pulp.LpProblem("Transporte_arroz",
pulp.LpMinimize)
x = pulp.LpVariable.dicts("x",
(plantas, supers), lowBound=0)
m += pulp.lpSum(costos[i][j] * x[i][j]
for i in plantas for j in supers)
for i in plantas:
m += pulp.lpSum(x[i][j] for j
in supers) <= oferta[i]for j in supers:
m += pulp.lpSum(x[i][j] for i
in plantas) == demanda[j]
solver = pywraplp.Solver.CreateSolver(
"GLOP")
x = [[solver.NumVar(0, solver.infinity(),
f"x_{i}_{j}") for j in range(3)]
for i in range(2)]
for i in range(2):
solver.Add(sum(x[i][j] for j in
range(3)) <= oferta[i])for j in range(3):
solver.Add(sum(x[i][j] for i in
range(2)) == demanda[j])solver.Minimize(sum(costos[i][j] *
x[i][j] for i in range(2)
for j in range(3)))
costos <- matrix(c(200, 300, 400,
250, 150, 350),
nrow = 2, byrow = TRUE)
oferta <- c(100, 150)
demanda <- c(80, 120, 50)
res <- lp.transport(costos,
direction = "min",
row.signs = rep("<=", 2), row.rhs = oferta,
col.signs = rep("=", 3), col.rhs = demanda)
| Envíos | Súper A | Súper B | Súper C | Total |
|---|---|---|---|---|
| Planta 1 | 80 | 0 | 20 | 100 |
| Planta 2 | 0 | 120 | 30 | 150 |
| Recibido | 80 | 120 | 50 | 250 |
PuLP, OR-Tools y lpSolve dan el mismo plan.
Usar la planta 1 en vez de la 2 cuesta por saco: A −50, B +150, C +50.
Z = 80(200) + 20(400) + 120(150) + 30(350) = 52\,500
Las dos plantas usan toda su capacidad (100 y 150 sacos) y los tres supermercados reciben exactamente lo que piden.
linear_sum_assignment [6] PythonRecibe la matriz de costos y devuelve qué fila queda con qué columna. Usa una variante del método húngaro y minimiza por defecto.
Programación lineal con variables binarias, una restricción por fila y una por columna, creadas con add_variable_dicts.
lp.assign [3] y solve_LSAP [7] RNinguna acepta más filas que columnas, así que, igual que en clase, se agrega una columna ficticia de ceros.
Kilómetros entre cada tráiler y cada comunidad; el transporte cuesta $8 por km. Ejemplo 2 del material del curso [8].
| km | C1 | C2 | C3 | C4 | C5 | C6 |
|---|---|---|---|---|---|---|
| A | 17 | 22 | 15 | 43 | 27 | 0 |
| B | 12 | 26 | 28 | 43 | 18 | 0 |
| C | 30 | 34 | 16 | 21 | 16 | 0 |
| D | 32 | 21 | 41 | 36 | 41 | 0 |
| E | 27 | 43 | 39 | 29 | 12 | 0 |
| F | 14 | 6 | 13 | 17 | 22 | 0 |
C6, con costo 0, vuelve la matriz 6 × 6 para SciPy y R. El tráiler que quede ahí no se usa.
PuLP · modelo 6 × 5, sólo C1 a C5
x_{ij} = 1 si el tráiler i \in \{A,\dots,F\} va a la comunidad j \in \{C_1,\dots,C_5\}
sujeto a
11 restricciones · costo = 8Z
d = np.hstack([d, np.zeros( (6, 1), dtype=int)])filas, cols = ( linear_sum_assignment(d))km = d[filas, cols].sum() print("km =", km, " costo =", km * 8)
x = m.add_variable_dicts("x",
(T, C), cat="Binary")for t in T:
m += pulp.lpSum(x[t][c]
for c in C) <= 1
for c in C:
m += pulp.lpSum(x[t][c]
for t in T) == 1
d <- cbind(d, C6 = 0)sol <- lp.assign(d,
direction = "min")
km <- sol$objval
cat("km =", km,
" costo =", km * 8)
d <- cbind(d, 0)
a <- solve_LSAP(d,
maximum = FALSE)km <- sum(d[cbind(1:6, a)])
| km | C1 | C2 | C3 | C4 | C5 | C6 |
|---|---|---|---|---|---|---|
| A | 17 | 22 | 15 | 43 | 27 | 0 |
| B | 12 | 26 | 28 | 43 | 18 | 0 |
| C | 30 | 34 | 16 | 21 | 16 | 0 |
| D | 32 | 21 | 41 | 36 | 41 | 0 |
| E | 27 | 43 | 39 | 29 | 12 | 0 |
| F | 14 | 6 | 13 | 17 | 22 | 0 |
SciPy, PuLP, lpSolve y clue dan la misma asignación, la misma que da el método húngaro del material del curso. D queda en la ficticia: no se usa.
Revisamos las 720 asignaciones posibles: sólo esta da 66 km, y la siguiente mejor da 77 km.
Una extensión del transporte en la que los envíos pueden pasar por puntos intermedios antes de llegar a su destino [10].
| Nodo | Qué hace | Ejemplo |
|---|---|---|
| Origen | tiene oferta | fábrica |
| Transbordo | recibe y vuelve a enviar | almacén |
| Destino | tiene demanda | tienda |
Modela redes de distribución, cadenas de suministro y sistemas de comunicación [10][11].
Conservación del flujo [16]
Transporte
Transbordo
| Criterio | Transporte | Transbordo |
|---|---|---|
| Rutas | directas | directas o con paradas |
| Nodos | oferta y demanda | oferta, demanda y paso |
| Variables | pares origen-destino | arcos de una red dirigida |
| Clave | cumplir oferta y demanda | balance de flujo en cada nodo |
Los dos minimizan casi siempre el costo. El transporte es un caso particular del transbordo: el caso sin nodos intermedios. El transbordo además permite rutas de varios tramos [11][12][13][16].
Dos plantas, P1 y P2, producen 1 000 y 1 200 autos. Tres concesionarios, D1, D2 y D3, necesitan 800, 900 y 500 [9].
Los envíos pueden pasar por los centros de tránsito T1 y T2, y de D1 a D2 y de D2 a D3. Cada flecha lleva su costo por auto, en cientos de dólares.
La idea: convertir la red en un problema de transporte balanceado, resoluble con una solución inicial (esquina noroeste, costo mínimo o Vogel) y el cruce del arroyo, o con Solver.
Clasificar los nodos
| Tipo | Nodos | Por qué |
|---|---|---|
| Origen puro | P1, P2 | sólo envían |
| Transbordo | T1, T2, D1, D2 | reciben y envían |
| Destino puro | D3 | sólo recibe |
Revisar el balance y calcular el colchón
\text{Oferta} = 1000 + 1200 = 2200
\text{Demanda} = 800 + 900 + 500 = 2200
B = 2200\ \text{autos}
B toma la oferta total como cota de lo que un nodo puede reenviar.
Definir filas y columnas
\text{Orígenes: } P_1, P_2, T_1, T_2, D_1, D_2 \quad (m = 6)
\text{Destinos: } T_1, T_2, D_1, D_2, D_3 \quad (n = 5)
| Nodo | s_i | d_j |
|---|---|---|
| P1 | 1 000 | — |
| P2 | 1 200 | — |
| T1 | 0 + 2 200 | 0 + 2 200 |
| T2 | 0 + 2 200 | 0 + 2 200 |
| D1 | 0 + 2 200 | 800 + 2 200 |
| D2 | 0 + 2 200 | 900 + 2 200 |
| D3 | — | 500 |
| Total | 11 000 | 11 000 |
Se suma lo mismo a los dos lados (4 × 2 200): sigue balanceada.
Ruta que existe: su costo · de un nodo a sí mismo: 0 · ruta que no existe: M.
| T1 | T2 | D1 | D2 | D3 | s_i | |
|---|---|---|---|---|---|---|
| P1 | 3 | 4 | M | M | M | 1 000 |
| P2 | 2 | 5 | M | M | M | 1 200 |
| T1 | 0 | 7 | 8 | 6 | M | 2 200 |
| T2 | M | 0 | M | 4 | 9 | 2 200 |
| D1 | M | M | 0 | 5 | M | 2 200 |
| D2 | M | M | M | 0 | 3 | 2 200 |
| d_j | 2 200 | 2 200 | 3 000 | 3 100 | 500 | 11 000 |
Cientos de dólares por auto. Transporte balanceado de 6 × 5.
x_{ij} = cantidad en la casilla i, j (en la diagonal, colchón sin usar)
sujeto a
| Casillas | Cantidad |
|---|---|
| Total (6 × 5) | 30 |
| Rutas inexistentes (M) | 15 |
| Rutas de la red | 11 |
| Diagonal (colchón) | 4 |
| Restricciones | 11 |
No degeneración
m + n - 1 = 6 + 5 - 1 = 10Una solución básica no degenerada tiene 10 casillas básicas positivas.
Balance de rutas reales: las casillas con M se toman en cero.
Nodo T1
lo que entra a T1 = lo que sale de T1
Nodo D2, con demanda propia
lo que entra − lo que sale = la demanda de D2
La diagonal es el colchón sin usar: si de T1 salen 1 200 autos, x_{T_1T_1} = 2200 - 1200 = 1000. Por eso su costo es 0.
La matriz balanceada del paso 6, tal como quedó. Cada M se carga con un costo de 1 000, muy por encima del mayor costo real (9). En las tres soluciones, las 15 casillas con M quedaron en cero.
| Herramienta | Función | Restricciones |
|---|---|---|
| Python | PuLP [2] | todas con igualdad |
| R | lpSolve · lp.transport [3] | todas con igualdad |
| Excel | Solver [17] | todas con igualdad |
Cada fila envía exactamente su oferta y cada columna recibe exactamente su demanda:
\textstyle\sum_j x_{ij} = s_i \qquad \sum_i x_{ij} = d_jM = 1000
oferta = [1000, 1200, 2200, 2200, 2200, 2200]
demanda = [2200, 2200, 3000, 3100, 500]
m = pulp.LpProblem("Transbordo", pulp.LpMinimize)
x = m.add_variable_dicts("x", (O, D), lowBound=0)
m += pulp.lpSum(c[i][j] * x[O[i]][D[j]]
for i in range(6) for j in range(5))
for i in range(6):
m += pulp.lpSum(x[O[i]][d] for d in D) == oferta[i]for j in range(5):
m += pulp.lpSum(x[o][D[j]] for o in O) == demanda[j]m.solve(pulp.HiGHS(msg=False))
sol <- lp.transport(costos, direction = "min", row.signs = rep("=", 6), row.rhs = oferta,
col.signs = rep("=", 5), col.rhs = demanda)
| T1 | T2 | D1 | D2 | D3 | |
|---|---|---|---|---|---|
| P1 | 0 | 1000 | 0 | 0 | 0 |
| P2 | 1200 | 0 | 0 | 0 | 0 |
| T1 | 1000 | 0 | 800 | 400 | 0 |
| T2 | 0 | 1200 | 0 | 1000 | 0 |
| D1 | 0 | 0 | 2200 | 0 | 0 |
| D2 | 0 | 0 | 0 | 1700 | 500 |
costo = 20700 · gris = diagonal (colchón sin usar). T1 reenvía 2 200 − 1 000 = 1 200. D2 recibe 1 400, se queda 900 y reenvía 2 200 − 1 700 = 500.


| Parámetro | Valor |
|---|---|
| Objetivo | B22, costo total · Mín |
| Variables | B13:F18 |
| Oferta | G13:G18 = H13:H18 |
| Demanda | B19:F19 = B20:F20 |
| No negatividad | B13:F18 ≥ 0 |
| Método | Simplex LP |
Costo total = SUMAPRODUCTO(B3:F8;B13:F18) = 20 700.
| Nodo | Entra | Sale | Se queda |
|---|---|---|---|
| T1 | 1 200 | 800 + 400 | 0 |
| T2 | 1 000 | 1 000 | 0 |
| D1 | 800 | 0 | 800 |
| D2 | 400 + 1 000 | 500 | 900 |
| D3 | 500 | 0 | 500 |
| P1→T2 | P2→T1 | T1→D1 | T1→D2 | T2→D2 | D2→D3 | Costo* | |
|---|---|---|---|---|---|---|---|
| PuLP | 1 000 | 1 200 | 800 | 400 | 1 000 | 500 | 20 700 |
| lpSolve | 1 000 | 1 200 | 800 | 400 | 1 000 | 500 | 20 700 |
| Solver | 1 000 | 1 200 | 800 | 400 | 1 000 | 500 | 20 700 |
Z = 4(1000) + 2(1200) + 8(800) + 6(400) + 4(1000) + 3(500) = 20\,700
* Cientos de dólares: $2 070 000.
Cinco rutas quedan sin envío. Por ejemplo, T2→D2→D3 cuesta 4 + 3 = 7 por auto, contra 9 de T2→D3 directo.
Prueba de no degeneración
6 \text{ rutas} + 4 \text{ diagonales} = 10 = m + n - 1Diagonal positiva: T1 1 000 · T2 1 200 · D1 2 200 · D2 1 700. Las 10 conectan filas y columnas sin formar ciclo.
La oferta total puede superar la demanda o no alcanzarla. Además de ajustar los totales, hay que respetar el balance de flujo en cada nodo intermedio y usar sólo rutas que existen [16].
Balance general de la red
El excedente se queda sin enviar. Con envíos ≤ oferta basta no usarla toda; con igualdades se agrega un destino ficticio por la diferencia, con arcos de costo 0 o el costo de almacenar [9][16].
Si D3 pidiera 400 en vez de 500
800 + 900 + 400 = 2100 < 2200 \Rightarrow \text{sobran } 100
| … | D3 | F | s_i | |
|---|---|---|---|---|
| P1 | … | M | 0 | 1 000 |
| P2 | … | M | 0 | 1 200 |
| d_j | … | 400 | 100 | 2 200 |
F es el destino ficticio: el sobrante se queda en las plantas y el total vuelve a 2 200, antes de sumar el colchón.
Si se exige atender todo, no hay solución factible. Se agrega un origen ficticio por la diferencia o, lo que es igual, faltantes h_j: pedidos sin cubrir, no autos transportados, con una penalización p_j [16].
Si D3 pidiera 600 en vez de 500
800 + 900 + 600 = 2300 > 2200 \Rightarrow \text{faltan } 100
Si se despachan los 2 200 autos disponibles:
h_{D_1} + h_{D_2} + h_{D_3} = 100,\quad h_j \ge 0
Si todo el faltante se carga a D3, h_{D_3} = 100: recibe 500 autos reales y le quedan 100 sin atender. Cuál conviene dejar depende de las rutas y las penalizaciones.
En la matriz equivale a un origen ficticio O con oferta 100, unido sólo a los concesionarios donde se permite faltante.
| Situación | Ajuste al modelo | Interpretación |
|---|---|---|
| Oferta > demanda | destino ficticio por el excedente | inventario no despachado |
| Demanda > oferta | origen ficticio o faltantes h_j | demanda no satisfecha |
| Oferta = demanda | no hace falta un nodo ficticio | totales reales iguales |
Con el método del colchón, B sale del total ya ajustado: 2 200 con el excedente y 2 300 con el origen ficticio. El ajuste no quita el balance de flujo ni permite rutas que no existen [9][16].