Teorema fundamental de la programación lineal y holgura complementaria

Teorema fundamental de la programación lineal y holgura complementaria
Índice
  1. El problema de programación lineal
  2. Teorema fundamental
  3. Ejemplo resuelto por vértices
    1. Ejemplo con región no acotada
  4. Variables de holgura
  5. Dualidad y teorema de la holgura complementaria
    1. Aplicación al ejemplo
  6. Errores habituales en los ejercicios
  7. Un poco de historia
  8. Preguntas frecuentes
    1. ¿Qué dice el teorema fundamental de la programación lineal?
    2. ¿Qué es una variable de holgura?
    3. ¿Qué dice el teorema de la holgura complementaria?
    4. ¿Qué pasa si la región factible no está acotada?
  9. Fuentes

Actualizado el

El teorema fundamental de la programación lineal dice que, si un problema lineal tiene solución óptima, al menos una de esas soluciones está en un vértice de la región factible. Por eso, en los problemas de dos variables de bachillerato basta con calcular los vértices y evaluar la función objetivo en cada uno. El teorema de la holgura complementaria, por su parte, relaciona el problema con su dual y permite comprobar si una solución es óptima y obtener los precios sombra de los recursos.

El problema de programación lineal

Se trata de maximizar (o minimizar) una función lineal z = c1x1 + … + cnxn sujeta a restricciones lineales, normalmente de la forma ai1x1 + … + ainxn ≤ bi, y a xj ≥ 0. El conjunto de puntos que cumplen todas las restricciones es la región factible: un polígono convexo en el plano (o un poliedro convexo en más dimensiones), que puede ser acotado o no.

Teorema fundamental

Sea un problema lineal cuya región factible tiene al menos un vértice (esto ocurre siempre con las restricciones xj ≥ 0). Entonces:

  1. Si la región factible es acotada y no vacía, la función objetivo alcanza su máximo y su mínimo, y los alcanza en algún vértice.
  2. Si la región no es acotada, puede que el óptimo no exista (la función crece sin límite), pero si existe, también se alcanza en un vértice.
  3. Si el óptimo se alcanza en dos vértices contiguos, se alcanza en todos los puntos del lado que los une (soluciones múltiples).

Idea de la prueba. Las curvas de nivel de z (los puntos con z = k) son rectas paralelas. Al desplazarlas en la dirección en que z crece, la última que toca el polígono convexo lo toca en un vértice o en un lado entero. Algebraicamente: todo punto de un polígono acotado es combinación convexa de sus vértices, x = Σ λivi con λi ≥ 0 y Σ λi = 1; como z es lineal, z(x) = Σ λiz(vi) ≤ máx z(vi). Ningún punto supera al mejor vértice.

Ejemplo resuelto por vértices

Maximizar z = 3x + 5y sujeto a x ≤ 4, 2y ≤ 12, 3x + 2y ≤ 18, x ≥ 0, y ≥ 0.

Los vértices se obtienen cortando las rectas de las restricciones dos a dos y quedándose con los puntos que cumplen todas:

VérticeRectas que lo formanz = 3x + 5y
(0, 0)x = 0, y = 00
(4, 0)x = 4, y = 012
(4, 3)x = 4, 3x + 2y = 1827
(2, 6)2y = 12, 3x + 2y = 1836
(0, 6)x = 0, 2y = 1230

El máximo es z = 36 en (2, 6). Por el teorema, ningún punto interior del pentágono puede dar más.

Ejemplo con región no acotada

Minimizar z = 2x + 3y con x + y ≥ 4, x + 3y ≥ 6, x ≥ 0, y ≥ 0. La región se extiende sin límite hacia arriba y a la derecha, y sus vértices son (0, 4), (3, 1) y (6, 0), con z = 12, 9 y 12. El mínimo es z = 9 en (3, 1). En cambio, si se pidiera maximizar, no habría solución: z crece sin límite al alejarse por la región.

Variables de holgura

Para resolver problemas con muchas variables (con el método símplex) se convierten las desigualdades en igualdades añadiendo una variable de holgura si ≥ 0 por restricción:

ai1x1 + … + ainxn + si = bi

La holgura es lo que «sobra» del recurso i. En una restricción de tipo ≥ se resta una variable de exceso en lugar de sumar una de holgura.

En el ejemplo, en el óptimo (2, 6):

  • s1 = 4 − 2 = 2: la primera restricción no está apurada.
  • s2 = 12 − 12 = 0 y s3 = 18 − (6 + 12) = 0: las otras dos están activas (saturadas).

Que el óptimo esté en un vértice se traduce en que, en el plano, al menos dos de las cinco variables (x, y, s1, s2, s3) valen cero. Esa es la noción de solución básica que recorre el método símplex, saltando de vértice en vértice mientras z mejora.

Dualidad y teorema de la holgura complementaria

A cada problema de maximización (primal) le corresponde un problema de minimización (dual). Para el ejemplo, con una variable dual ui ≥ 0 por cada restricción:

Minimizar w = 4u1 + 12u2 + 18u3 sujeto a u1 + 3u3 ≥ 3 y 2u2 + 2u3 ≥ 5.

El teorema de dualidad fuerte afirma que, si el primal tiene óptimo, el dual también, y los dos valores óptimos coinciden.

El teorema de la holgura complementaria dice que una solución factible x del primal y una u del dual son óptimas a la vez si y solo si:

  • para cada restricción del primal, ui · si = 0 (si sobra recurso, su precio dual es cero; si el precio es positivo, el recurso se agota);
  • para cada variable del primal, xj · (exceso de la restricción j del dual) = 0.

Aplicación al ejemplo

  1. Como s1 = 2 > 0, ha de ser u1 = 0.
  2. Como x = 2 > 0, la primera restricción dual es una igualdad: u1 + 3u3 = 3, luego u3 = 1.
  3. Como y = 6 > 0, la segunda también: 2u2 + 2u3 = 5, luego u2 = 1,5.
  4. Comprobación: w = 4·0 + 12·1,5 + 18·1 = 36, igual que el máximo del primal. Las dos soluciones son óptimas.

Los ui son los precios sombra: cuánto aumentaría el beneficio máximo por cada unidad más del recurso i, mientras la base óptima no cambie. Aquí, una unidad más del recurso 1 no sirve de nada (sobran 2), una más del recurso 2 vale 1,5 y una más del recurso 3 vale 1.

Errores habituales en los ejercicios

  • Dar por vértice un punto que no es factible. Al cortar rectas dos a dos salen puntos que incumplen otra restricción; hay que comprobarlas todas. En el ejemplo, el corte de x = 4 con 2y = 12, el punto (4, 6), no es vértice porque 3·4 + 2·6 = 24 > 18.
  • Olvidar las regiones no acotadas. Antes de declarar un máximo, comprobar que la región está acotada en la dirección en que crece z.
  • Ignorar las soluciones múltiples. Si dos vértices dan el mismo valor óptimo, la respuesta es todo el segmento que los une.

Un poco de historia

Leonid Kantoróvich en la Unión Soviética y Wassily Leontief en Estados Unidos trabajaron en problemas de este tipo a finales de los años treinta. George Dantzig formuló el problema general y creó el método símplex en 1947, y la conjetura de la dualidad surgió de su conversación con John von Neumann. En 1979 Leonid Jachiyán demostró que la programación lineal se resuelve en tiempo polinómico, y en 1984 Narendra Karmarkar presentó un método de punto interior eficiente en la práctica.

La programación lineal se apoya en el álgebra de matrices. Decidir si las restricciones activas determinan un único vértice es una cuestión de rango, la misma que resuelve el teorema de Rouché-Frobenius; la dimensión de las caras de la región se relaciona con el teorema del rango y la nulidad, y los sistemas de restricciones activas se pueden resolver por determinantes con el desarrollo de Laplace.

Preguntas frecuentes

¿Qué dice el teorema fundamental de la programación lineal?

Que si un problema lineal tiene solución óptima, al menos una solución óptima está en un vértice de la región factible. Si la región es acotada y no vacía, el óptimo siempre existe.

¿Qué es una variable de holgura?

Una variable s ≥ 0 que se suma a una restricción de tipo ≤ para convertirla en igualdad. Indica cuánto sobra del recurso en esa solución.

¿Qué dice el teorema de la holgura complementaria?

Que soluciones factibles del primal y del dual son óptimas si y solo si, en cada restricción, el producto de la holgura por la variable dual correspondiente es cero, y lo mismo para cada variable primal y el exceso de su restricción dual.

¿Qué pasa si la región factible no está acotada?

El óptimo puede no existir: por ejemplo, la función puede crecer sin límite. Si existe, sigue estando en un vértice.

Fuentes

Teoremas

RELACIONADOS

Subir