Algoritmo del símplex

El método o algoritmo del símplex se utiliza para hallar las soluciones óptimas de un problema de programación lineal con tres o más variables. Es un procedimiento iterativo de programación lineal que va desechando las soluciones no factibles y, en cada paso, evalúa si la solución obtenida es óptima o no. Las etapas de este algoritmo son:

• 1. Planteamiento del problema: identificación de las variables y definición de la función objetivo y del sistema de inecuaciones lineales para restricciones.
• 2. Conversión de las desigualdades en igualdades; en cada restricción se introduce una variable de holgura en el miembro menor (o menor o igual) de la desigualdad.
• 3. Igualación a cero de la función objetivo.
• 4. Escritura de una tabla inicial símplex (matriz): en las columnas, las variables del problema; una fila para cada conjunto de coeficientes de una restricción y una fila más para los coeficientes de la función objetivo.
• 5. Determinación de las variables y los coeficientes.

Ejemplo de tabla inicial símplex:

Variables y coeficientes

Para determinar las variables de un problema mediante el método del símplex, es preciso hallar primero la base de resolución. En esta base:

• Se incluye una variable de decisión, la que posee el coeficiente negativo mayor. La columna a la que corresponde se llama columna pivote.
• Se excluye una variable de holgura. Se divide cada término por el correspondiente de la columna pivote y se calcula el menor cociente positivo.

Se aplica entonces el método de eliminación gaussiana para anular los términos de la columna pivote, tantas veces como se precisa hasta que en la última fila sólo haya coeficientes positivos. (Tal será la solución).

Problema del transporte

El problema del transporte es un planteamiento clásico de las técnicas de programación lineal. En este problema se pretende elegir el camino óptimo de envío de una mercancía desde varios orígenes (por ejemplo, plantas de producción) a diferentes destinos (centros de almacenamiento o consumo), de forma que el coste sea mínimo.

Como en todo problema de programación lineal, han de cumplirse las siguientes etapas:

• Definir las variables del problema (por ejemplo, las cantidades de partida solicitadas en cada destino, el coste de envío de una unidad de mercancía a cada destino).
• Escribir conceptualmente el sistema de inecuaciones asociado a las restricciones del problema (por ejemplo, el número de unidades máximas producidas en cada origen y las requeridas en cada destino).
• Definir conceptualmente la función objetivo, que determina el coste.

Resolución del problema del transporte

Una vez planteado el problema, se construye una tabla de distribución, de la que se obtienen las expresiones matemáticas de las inecuaciones del sistema y la función objetivo. Para resolverla se usan los métodos gráficos o algebraicos comunes de la programación lineal.