Programación lineal

La idea

Un problema de programación lineal consiste en elegir los valores de unas variables de decisión x₁, x₂, …, xₙ (cuánto producir, cuánto invertir, cuánto transportar) para maximizar o minimizar una función objetivo lineal z = c₁x₁ + … + cₙxₙ, respetando un conjunto de restricciones también lineales, casi siempre desigualdades del tipo a₁x₁ + … + aₙxₙ ≤ b que expresan recursos escasos: horas de máquina, kilos de materia prima, presupuesto. A ellas se suman las condiciones de no negatividad xᵢ ≥ 0, porque no se producen cantidades negativas.

Cada desigualdad divide el espacio en dos mitades y se queda con una: un semiplano en dos variables. La intersección de todos esos semiplanos es la región factible, un poliedro convexo (posiblemente vacío o no acotado). El teorema fundamental de la programación lineal afirma que, si existe óptimo finito, se alcanza en un vértice de esa región. Por eso el método gráfico funciona: se dibujan las rectas de nivel c₁x + c₂y = z, todas paralelas entre sí, y se desplazan en la dirección del gradiente (c₁, c₂) hasta el último punto de contacto con la región factible. Ese punto es la solución.

Con más de dos variables el dibujo es imposible y se usa el método símplex de Dantzig: parte de un vértice factible y salta a un vértice vecino que mejore el objetivo, repitiendo hasta que ningún vecino mejore. Si la región no está acotada en la dirección de mejora, el problema es no acotado; si las restricciones se contradicen, es infactible. La teoría de la dualidad asocia a cada restricción un precio sombra que mide cuánto crecería el beneficio si dispusiéramos de una unidad más de ese recurso.

Fórmulas clave

• Forma canónicamax z = cᵀx sujeto a A x ≤ b, x ≥ 0
• Región factibleF = { x : a₁ᵀx ≤ b₁, …, a_mᵀx ≤ b_m, x ≥ 0 } (convexa)
• Recta de nivel (2 variables)c₁ x + c₂ y = z → y = (z − c₁ x) / c₂
• Dirección de mejora∇z = (c₁, c₂), perpendicular a las rectas de nivel
• Teorema fundamentalsi el óptimo es finito, se alcanza en un vértice de F
• Precio sombrayᵢ = ∂z*/∂bᵢ (valor marginal del recurso i)

Dónde se aplica

Las refinerías de petróleo fueron el primer gran cliente del símplex: deciden cuántos barriles de cada mezcla producir para maximizar el margen respetando capacidades de destilación y especificaciones de octanaje. Las aerolíneas resuelven a diario modelos lineales gigantescos de asignación de tripulaciones y de revenue management, y las cadenas logísticas usan el problema de transporte (un caso particular de programación lineal) para decidir qué almacén sirve a qué tienda con coste mínimo. En agricultura y nutrición, el «problema de la dieta» calcula la combinación de alimentos más barata que cubre todos los requerimientos de vitaminas y calorías.

Con programación (Python)

# Metodo de los vertices para un PL de dos variables
# max z = 40x + 30y   s.a.  x + y <= 12,  2x + y <= 16,  x >= 0, y >= 0
restricciones = [(1, 1, 12), (2, 1, 16), (-1, 0, 0), (0, -1, 0)]
c1, c2 = 40, 30

def interseccion(r1, r2):
    a1, b1, k1 = r1
    a2, b2, k2 = r2
    det = a1 * b2 - a2 * b1
    if abs(det) < 1e-12:
        return None
    return ((k1 * b2 - k2 * b1) / det, (a1 * k2 - a2 * k1) / det)

def factible(p):
    return all(a * p[0] + b * p[1] <= k + 1e-9 for a, b, k in restricciones)

mejor, valor = None, float("-inf")
for i in range(len(restricciones)):
    for j in range(i + 1, len(restricciones)):
        p = interseccion(restricciones[i], restricciones[j])
        if p is not None and factible(p):
            z = c1 * p[0] + c2 * p[1]
            print("vertice (%6.2f, %6.2f)  z = %8.2f" % (p[0], p[1], z))
            if z > valor:
                mejor, valor = p, z
print("Optimo:", mejor, " z =", valor)

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Sistemas lineales y eliminación de Gauss · Convexidad · Programación entera