lunes, 27 de agosto de 2012

Ejemplo de Resolución del Método Simplex para Programación Lineal



tabla-para-resolucion-de-programacion-lineal-mediante-el-metodo-simplex
En artículos anteriores se ha publicado los conceptos teóricos tanto de Programación Lineal (PL) como de una de sus formas de resolución, el Método Simplex. Sin embargo, y dada su dificultad, en esta entrada nos centraremos en un ejemplo que ayudará a la comprensión de los pasos necesarios para resolver el sistema de inecuaciones de PL mediante el Simplex.

Supongamos el siguiente planteamiento:

X1 = Número de pañuelos de seda a fabricar a la semana.
X2 = Número de pañuelos de algodón a fabricar a la semana.

Z (max) = 50X1 + 30X2

s. a.
3X1 + 5X2 ≥ 30 metros de hilo.
1,5X1 + 2,5X2 =40 horas de planchado.
4X1 + 6X2 ≤ 50 horas de máquina.

X1, X2 ≥ 0

Solución Método Simplex siguiendo los pasos explicados:

  1. Convertir las desigualdades en igualdades.
3X1 + 5X2 –h1= 30.
1,5X1 + 2,5X2 = 40.
4X1 + 6X2 + h2= 50

X1, X2, h1, h2 ≥ 0

Z (max)= 50X1 + 30X2 + 0h1 +0h2
  1. Conseguir la matriz identidad dentro de la matriz tecnológica añadiendo las variables artificiales que sean necesarias.
3X1 + 5X2 –h1 + Xa1= 30
1,5X1 + 2,5X2 + Xa2 = 40
4X1 + 6X2 + h2 =50

X1, X2, h1, h2, Xa1, Xa2 ≥ 0

Z (max) = 50X1 + 30X2 + 0h1 +0h2 –MXa1 –MXa2

  1. El programa base está formado por aquellas variables cuyos coeficientes forman la matriz identidad Xa1, Xa2, h2

  1. y 5. Dibujar la tabla y rellenarla. En Pi (la segunda columna del programa efectuable) se colocan las variables del programa base. En Ci (la primera columna del programa efectuable) los rendimientos directos de las variables del programa base y en Xi (la tercera columna del program efectualble) el vector existencia formada por la cantidad de recursos limitados de cada una de las restricciones. En Ci (la fila del cuerpo central de la tabla) se colocan cada uno de los rendimientos directos correspondientes a cada variable y en el resto de la tabla (en su cuerpo central) los coeficientes de cada una de las variables que representan la matriz tecnológica.

Pasos-4-y-5-para-la-resolución-de-programación-lineal-mediante-el-método-simplex

    6. Calcular los Zi, multiplicando los rendimientos directos del programa efectuable por el vector proceso i. Por ejemplo: Z1= -M*3 + (-M)*1,5 + 0*4= -4,5M; Z2= -M*5 + (-M)*2,5 + 0*6= -3,5M y así sucesivamente
Paso-6-para-la-resolución-de-programación-lineal-mediante-el-método-simplex

    7. Calcular los rendimientos marginales. Wi = Ci – Zi

Paso-7-para-la-resolución-de-programación-lineal-mediante-el-método-simplex

    8. No hemos llegado al óptimo porque existen rendimientos marginales positivos y estamos maximizando, lo que quiere decir que es posible aumentar el beneficio total del programa, por lo tanto continuamos con el paso 9.


    9. Se elije para entrar el proceso 2 (P2) puesto que es el que tiene mayor rendimiento marginal positivo (por lo tanto es el que más aumentaría el beneficio) y como estamos maximizando el objetivo es conseguir el mayor rendimiento posible.

    10. Para saber que variable saldría del programa efectuable para que, en su lugar, entre P2, se divide el nivel de la variable (columna Xi) entre vector proceso que entra (columna P2): 30/5= 6; 40/2,5= 16; 50/6= 8,33. Sale aquel proceso con menor cociente positivo por lo tanto el primero, Xa1.

    11. Cambiar los procesos del programa efectuable, P2 en el lugar de Xa1
Paso-11-para-la-resolución-de-programación-lineal-mediante-el-método-simplex


12. Calcular la fila del P2 , dividiendo la fila de Xa1 (proceso que sale) de la tabla antigua entre el pivotte es 5 (el número que cruza en la tabla antigua entre el proceso que entra P2 y el proceso que sale Xa1 )

Paso-12-para-la-resolución-de-programación-lineal-mediante-el-método-simplex

    13. Calcular el resto de las filas, con un semipivotte para la fila de Xa2 de 2,5 (número que cruza en la tabla antigua entre P2 y Xa2 ) y para la fila de h2 de 6 (número que cruza en la tabla antigua entre P2 y h2)
Paso-13-para-la-resolución-de-programación-lineal-mediante-el-método-simplex

    14. Se vuelven a calcular los rendimientos indirectos y se repite el proceso hasta llegar al óptimo. Como el objetivo es maximizar los beneficios, se habrá alcanzado el óptimo cuando todos los rendimientos marginales sean negativos y cero.

    Supongamos que hemos llegado a la siguiente tabla óptima y la interpretamos.

NOTA: esta tabla no está calculada, es ficticia, es sólo para explicar como se interpretan las tablas óptimas del simplex.

tabla-optima-del-metodo-simplex-en-programacion-lineal

Todas las variables que no formen parte del programa efectuable son cero. Jamás se puede llegar al óptimo con variables artificiales en el programa efectuable puesto que no tienen significado económico.

X1= 25 pañuelos de seda a fabricar a la semana.
X2= 31 pañuelos de algodón a fabricar a la semana.
H1 = 0 metros de hilo de sobrecapacidad, es decir, la empresa no usa nada por encima del mínimo exigido, por lo tanto utiliza un total de 30 metros de hilo.
H2 =10 horas máquinas de capacidad ociosa, es decir, a la empresa le sobran 10 horas de las 50 horas máximas establecidas, por lo tanto utiliza un total de 40 horas máquinas.
Xa1=Xa2=0 no tiene significado económico.

Z (max) = 50*25 + 30*31 + 0*0 + 0*10 –M*0 –M*0 = 2.180 euros es el máximo beneficio de la empresa con las condiciones dadas.


Tal vez también te interese:

No hay comentarios:

Publicar un comentario

Deja tu aportación, siempre desde el respeto, la tolerancia y el buen gusto