Ejemplo del método del simplex - Construcción de la tabla para las iteraciones

Principios y Conceptos básicos

Formulación de un problema de programación lineal

Veremos en esta sección una aplicación de solución práctica de un típico problema de maximización. A veces lo dificil es llegar a plantear el problema de programación lineal, una vez planteado, usaremos los métodos aprendidos en la teoría: con el método del simplex y método de las dos fases.

Comenzamos con el enunciado de un problema de optimización.

Problema de programación lineal



Una compañía minera produce lignito y antracita.
Por el momento, es capaz de vender todo el carbón producido, siendo la ganancia por tonelada de lignito y antracita de 4 y 3 unidades monetarias, respectivamente. El procesado de cada tonelada de lignito requiere 3 horas de trabajo de la máquina de cortar carbón y otras 4 horas de la de lavado.
Por otra parte, el procesado de una tonelada de antracita requiere para las mismas tareas 4 y 2 horas, respectivamente.
El tiempo disponible diariamente para cada una de estas actividades es de 12 y 8 horas, respectivamente. Además, se desea producir diariamente al menos 4 toneladas de carbón.

1) Plantear el problema de programación lineal para determinar el número de toneladas de lignito y antracita que deben producirse diariamente con el fin de maximizar la ganancia.

2) Usar el algoritmo del simplex para resolver el problema por el método de las dos fases.


Comenzamos entendiendo este largo enunciado. Para ello construimos unas tablas.

La primera de ellas es la de costes, o en este caso, es una tabla de Ganancias.
MaterialGanancia produdida
(unidades monetarias/Tn)
Lignito4
Antracita3


MaterialHoras de cortado (por Tn)Horas de lavado (por Tn)
Lignito34
Antracita42


Unido a esta tabla, tenemos la restricción del tiempo disponible diario para cada máquina

ProcesoHoras disponibles diariamente
Lavado8
Cortado12


y finalmente, tenemos el objetivo de producir al menos 4 Toneladas diarias de carbón.

Teoría en extensión

Con estos datos, tenemos lo que necesitamos para plantear el problema de programación lineal.
Procedemos de la siguiente manera:

Sean

x1=Toneladas de lignito producidas
x2=Toneladas de antracita producidas

Lo que queremos es maximizar la ganancia, es decir, maximizar la función 4x1+3x2, ya tenemos la función objetivo, ahora construimos las restricciones.

Comenzamos por el proceso de lavado, obsérvese que para cada día tenemos que

3x1+ 4x2 ≤ 12

Ya que para cada día el número disponible de horas de lavado es 12.

Análogamente para el cortado tenemos que

4x1+ 2x2 ≤ 8

Ya que 8 es el número de horas disponibles para la máquina de cortado.

Finalmente, la última de las restricciones es la de nuestro objetivo de toneladas de producción

x1 + x2 ≥ 4

Juntando todo, obtenemos el problema de programación lineal

Maximizar (4x1 + 3x2)
Sujeto a
3x1 + 4x2 ≤ 12
4x1 + 2x2 ≤ 8
x1 + x2 ≥ 4
x1, x2 ≥ 0


Ahora, podemos resolver el problema de progrmación lineal usando el método del simplex o el método de las dos fases si es necesario como hemos visto en las secciones de teoría. En este caso usarmos nuestro famoso calculador de problemas de programación lineal simplex method calculator.

Colocamos cada uno de los pasos, primero introducimos el problema en el programa



Paso 1:


Paso 2:


Paso 3:


Como puede verse, el problema ha salido sin solulción óptima, esto es debido a que las restricciones son demasiado fuertes, la región factible es vacía.

Observe que si representamos gráficamente la región factible aparece el conjunto vacío, es decir, no se pueden satisfacer a la vez las tres restricciones.

Tendremos que alterar alguna (o varias) de nuestras restricciones para ello, hablamos con el dueño de la fábrica y le enviamos un email, diciendo que no es posible producir 4 Toneladas diarias de carbón y cumplir con todas estas restricciones, hay dos opciones
     1) O relajamos nuestro objetivo ó
     2) buscamos el método de relajar estas restricciones.

El jefe nos responde que había un error, y que el objetivo real es producir 3 Toneladas de Carbón. Introducimos este nuevo dato en nuestro problema de programación lineal, esto es, cambiamos la última de las restricciones por

x1 + x2 ≤ 3

Introducimos de nuevo el problema en simplex method calculator y ahora sí, obtenemos



Así, hablamos con el jefe y le decimos que lo máximo que podemos producir con estas restricciones es

x1=1 Tn de lignito/día x2=2 Tn antracita/dia

Y esa es la solución de nuestro problema (modificado) de programación lineal. Alguna duda? ejecuta este problema aquí o envíanos un feedback.





Ha sido util? Alguna idea para complementar el texto?



Deja tu post

Comentarios de otros usuarios





Deja tu post