martes, 27 de julio de 2010

Programación lineal con GLP-Solve

Esta vez compartiré una tarea realizada junto a JAC el...?, sobre optimización de recursos disponibles por ejemplo el de una pequeña empresa familiar, algo elemental que no trascienda mas allá de un calculo lineal, para este caso se nos pidió explicar y ejecutar un ejemplo, usando Ilog Cplex un programa bastante avanzado de optimización creado por la IBM, que trabaja con los métodos Simplex revisado, Rama, Cota, etc. a su vez este programa es de uso privativo así que no podíamos usar ni la versión para estudiantes, dado que no posee licencia GNU/GPL etc., por tanto el código fuente no esta disponible al publico, al final encontramos un programa sencillo y libre que nos resolvía problemas comunes y además puede seguir optimizando aun después de encontrar resultados favorables en cada iteración, hablamos de Glp-Solve, idealmente para entorno de escritorio Gnome supone el buen funcionamiento en este entorno y muchas distribuciones (SO's), a continuación veremos dos ejemplos de dicha aplicación:
  • Ejemplo 1

Una empresa desea planificar su producción diaria de dos artículos A y B. La empresa puede disponer de un máximo de 12 horas diarias de mano de obra. Cada unidad de A requiere 3 horas, mientras que cada unidad de B requiere 2. Por otro lado, la producción requiere un input I del que la empresa puede disponer como máximo de 10 unidades diarias. Cada unidad de A requiere una unidad de I mientras que cada unidad de B requiere 2 unidades de I. ¿Cual es la máxima producción diaria que puede conseguir la empresa?, ¿que cantidad debe producir para ello de cada artículo?

  • Definimos el modelo matemático:

Sea X1 el producto A y X2 El producto B a producir;
F(x1, x2)=x1+x2; es la función a maximizar.
  • Sujeto a restricciones: 3x1+2x2<=12; tiempo diario de mano de obra disponible
X1+2x2<=10; input o recursos disponibles X1 >=0; condición para el producto A
X2>=0; condición para el producto B

  • Código:

/*Definir función o modelo*/
/*Función objetivo a maximizar*/
/*f(x1,x2)=x1+x2 */

max:x1+x2;
/*Definiendo limites*/
C1:3x1+2x2<=12; C2: x1+2x2<=10; C3: x1>=0;
C4: x2>=0;
/*Fin de los parámetros*/

  • Donde C1, C2,…Cn son condiciones.
  • Del cual obtenemos una producción diaria de 5.5 con 1 y 4.5 artículos respectivamente.



  • Ejemplo 2.

Una empresa produce dos tipos de producto A y B, a partir de una única materia prima M de la que sólo se cuenta con 18 unidades. Para producir una unidad de A se necesitan tres de M y 2 unidades de M por unidad de B. Por problemas de almacenamiento, no se puede producir más de 4 unidades de A ni más de 6 unidades de B. Si los precios de venta son 3 y 5 dólares respectivamente, cuánto se debe producir de A y B para que la ganancia sea máxima.

  • Modelo matemático.
Sean:
x1: unidades de A a producir
x2: unidades de B a producir
Max = 2x1 + 5x2 :función objetivo (Maximizar)

  • Sujeto a restricciones:
3x1 + 2x2 <=18:recursos disponibles (M) X1<=4:maximo a producir en un día del articulo A x2 <= 6:maximo en un día del articulo B x1>= 0:cantidad valida de A
x2 >=0:cantidad valida de B

  • Código:
/*Definir función o modelo*/
/*Función objetivo a maximizar*/

/*f(x1,x2)=x1+x2 */

max:x1+x2;

/*Definiendo limites*/

C1:3x1+2x2<=12; C2:x1+2x2<=10; C3:x1>=0;

C4:x2>=0;
/*Fin de los parámetros*/

  • Del cual obtenemos 2 y 6 respectivamente con una ganancia maxima de $ 36.0
  • Dichos resultados pueden variar según el número de iteraciones procesadas, en este caso llegamos al máximo valor requerido.

Si no desean descargar o compilar un programa, dejo un enlace a una herramienta online denominada PHPSimplex que resuelve ecuaciones lineales sin limite de variables ni restricciones.


Capturas del programa: