Programación lineal: el método del Simplex

Un problema de programación lineal (PL) consiste en minimizar (maximizar) una función lineal f(x) = ctx (llamada función objetivo), c perteneciente a Rn, sobre un poliedro P incluido en Rn, definido por un conjunto de restricciones lineales.

El método Simplex, siempre puede resolverlo, en el supuesto de que su tamaño no exceda a ciertos límites. Existen programas comerciales que permiten aplicar el algoritmo a problemas grandes de hasta 15000 ó 20000 restricciones. El método Simplex fue presentado en 1947 por George B. Dantzing. La idea en que se apoya es la siguiente: las diferentes restricciones determinan una región factible formada por un conjunto de "hiperplanos" en un espacio de dimensión superior (poliedro de soluciones posibles).

 

Como en el caso del problema en dos dimensiones (2 variables), cada una de las restricciones divide al espacio en dos partes: a un lado hay puntos que forman parte de la región factible y al otro están los puntos que "violan" la restricción. Todas las restricciones juntas forman un poliedro o politopo multidimensional, que encierra a todas las soluciones posibles.

La idea (muy simplificada) que hay detrás del método Simplex es ir escalando el poliedro en la dirección que maximiza la función objetivo, de manera que en cada paso pasamos de un vértice a otro. El número de vértices es inmenso, de manera que podría pensarse que el paso de uno a otro puede llevar una gran cantidad de tiempo; en la práctica mediante elaborados mecanismos de direccionamiento se consigue alcanzar el óptimo con sorprendente rapidez..

El estudio de este tipo de cuerpos n-dimensionales y del espacio de soluciones de los problemas lineales ha abierto un nuevo capítulo de las matemáticas llamado "Combinatoria Poliédrica"

Si a las soluciones de un problema lineal les exigimos que sean sean enteras, nos encontramos con un problema de programación lineal entera (PLE). Este problema es NP-duro, desde el punto de vista de la complejidad algorítmica. pero el problema lineal (PL), pertenece a la clase P. Aunque el método Simplex es capaz de resolver cualquier PL (si el tamaño del problema no es muy grande), no es un algoritmo polinómico. A pesar de todo sigue siendo el más utilizado, porque aunque no sea teóricamente polinómico, en la práctica se comporta como si lo fuera, llegando a ser incluso más eficiente que el método de las elipsoides. Este método, que también resuelve cualquier PL, ha permito demostrar que el PL es de la clase P, pero no resulta eficiente.

El método de las elipsoides fue presentado en 1979 por el ruso L.G. Khchian: se basa en la construcción de ciertos elipsoides sobre el poliedro de soluciones. Pero en la práctica, por la propia estructura del algoritmo, resultó demasiado lento. Últimamente K. Karmarkar de los laboratorios AT&T Bell ha construido un algoritmo que resuelve problemas lineales muy grandes en tiempo polinómico, lo que permite aumentar el número de variables y restricciones dentro de un tiempo computacional aceptable. Esto ha permitido resolver algunos problemas que antes eran intratables.

Programación lineal entera

Muchos problemas pueden ser planteados en términos de un problema de programación lineal entera. Algunos de ellos son

Problema de secuenciación de actividades con limitación de recursos: supongamos que una empresa de construcción ha de realizar un proyecto (por ejemplo un edificio). Este proyecto está compuesto de una serie de actividades, algunas de las cuales pueden ser, desde poner los cimientos, poner la fontanería, hasta cubrir aguas, poner las ventanas, etc. El problema de secuenciación de actividades con limitación de recursos consiste en planificar las actividades a lo largo del tiempo, sin posibilidad de interrumpirlas, con límites para los recursos disponibles, constantes a lo largo del tiempo, y con el objetivo de minimizar el tiempo total de ejecución. La duración de las actividades, los requerimientos de cada una de la actividades en términos de recursos, y la disponibilidad de los mismos, se suponen enteros, conocidos y constantes. Existen además relaciones de precedencia entre las actividades, de manera que no se puede empezar una actividad, hasta que sus perdecesoras no hayan acabado.

Problema de secuenciación de actividades sin limitación de recursos: cuando los recursos no están limitados, las técnicas PERT y CPM permiten resolver el problema, aun cuando el número de actividades sea muy alto. Pero si los recursos están limitados, se exige el uso de algoritmos heurísticos.

Enunciado del problema en términos de programación lineal: supongamos que el proyecto está formado por un conjunto de actividades {1, 2, ...., n}. Cada actividad requiere un tiempo di para su ejecución, y requiere rik unidades de cada recurso k = 1, 2, .., K, siendo bk la cantidad total disponible de cada uno de ellos. Podemos representar las relaciones de precendencia entre las actividades por medio de un grafo dirigido H, llamadografo de precedencia o grafo del proyecto, de manera que los vértices representan las actividades, y las aristas las relaciones de precedencia entre las actividades, de forma que si (i, j) pertenece a H, la actividad j no puede iniciarse mientras la activad i no se haya completado. Un grafo de un proyecto, tiene un vértice inicial único y un único vértice final, ambos de duración 0, que marcan el inicio y el final del proyecto. En cada arista del grafo el coste asignado es la duración de su vértice inicial.

El problema de secuenciación de actividades del proyecto consistirá entonces en determinar los tiempos t1, t2, ..., tn, en los que debe empezar cada actividad con las siguiente condiciones:

  1. Se tienen que respetar las relaciones de precedencia
  2. La cantidad de recursos utilizada en cada momento no puede superar la cantidad de recursos totales disponibles
  3. El tiempo total de realización del proyecto debe ser lo mínimo posible

Este problema puede ser enunciado como un problema de programación lineal entero, de la siguiente manera

siendo S(t) el conjunto de actividades en proceso en el tiempo t.

Los problemas de Rutas de Vehículos, más sencillos son los siguientes

  • El problema del agente viajero (TSP, por sus siglas en inglés): un agente tiene que visitar, exactamente una vez, una serie ciudades. El agente sale de su casa, y debe regresar a la misma. Se debe encontrar la secuencia en la que debe visitar las ciudades para que la distancia total recorrida sea lo menor posible. En términos de teoría de grafos, este problema puede ser enunciado de la siguiente manera: dado un grafo completo y no dirigido, con un coste asociado a cada arista, el TSP consiste en encontrar un ciclo hamiltoniano de coste mínimo.
  • El problema del cartero chino (CPP): un cartero parte de su oficina, reparte el correo, recorriendo las calles, y debe regresar de nuevo a su oficina. ¿En qué orden debe recorrer las calles para que la distancia recorrida sea la menor posible?

Como ya se ha dicho, estos problemas se pueden plantear en términos de un PLE. Para ellos, no existen algoritmos exactos que los resuelvan en tiempos computacionales aceptables (excepción hecha de algunos problemas para los que sí hay procedimientos específicos que se llaman algoritmos heurísticos). Pero estos algoritmos no suelen garantizar la obtención del óptimo del problema; en general sólo son capaces de obtener buenas soluciones.

Como referencia, el problema del horario escolar de un centro mediano, puede ser planteado como un PLE, en términos de un problema de secuenciación de actividades.. El tamaño del problema sería del orden de 4300 restricciones con 25200 variables; dicho problema al ser resuelto mediante el método Simplex no da solución entera. Para resolverlo, por tanto, no queda más remedio que el recurso a algoritmos heurísticos.

Un ejemplo de PL en dos dimensiones

Un agricultor posee una parcela de 480 m2 que dedica al cultivo de naranjos y perales. Se pregunta de qué forma repartirá la superficie de la parcela entre las dos variedades para conseguir máximo beneficio sabiendo que:

a) Cada naranjo precisa como mínimo 16 m2 y cada peral 4 m2
b) Dispone de 720 horas de trabajo/año (120 jornales) precisando cada naranjo de 12 horas/año y cada peral de 9 horas/año
c) Los beneficios unitarios son de 75 y 30 unidades monetarias por cada naranjo y peral respectivamente.

Veamos cómo plantear el problema

A) Definimos las variables: sea x el número de naranjos, y el número de perales y z el beneficio en unidades monetarias

B) En consecuencia la función objetivo será: z = 75x+30y, a maximizar.

C) Las restricciones serán
1ª.- Por la superficie: 16x+4y (menor o igual que) 480

2ª.- Por horas de trabajo: 12x+9y (menor o igual que) 720;

3ª.- Por ser x e y cantidades físicas: x (mayor o igual que) 0; y (mayor o igual que) 0

El poliedro de soluciones, 2-dimensional, viene dado por la siguiente región del plano

El vector (75, 30), nos indica que al mover las rectas 75x+30y = k, según indica su dirección, el máximo se obtiene en el punto de corte de las rectas 4x + y = 120, 4x+36 = 240.

En consecuencia se obtiene máximo beneficio plantando 15 naranjos y 60 perales. El beneficio, en este caso será: z=75 · 15+30 · 60=2925 unidades monetarias