PARADIGMA – Revista Electrónica en Construcción de Software

ISSN: 2011-0065

VOL. 7 No. 3, Diciembre 2013

M3PL: Un Lenguaje de dominio específico para definir

modelos matemáticos de programación lineal

Resumen. La creación de modelos matemáticos a partir de una realidad es uno de los procesos más importantes a la hora de optimizar un sistema. Actualmen-te, los modeladores deben aprender lenguajes para expresar sus modelos en di-

ferentes plataformas de modelado algebraico, como AMPL o GAMS, para ob-tener su solución. En este artículo presentamos M3PL, un lenguaje, construida bajo el enfoque MDE, que cuenta con un lenguaje de dominio específico a tra-vés del cual permite expresar modelos matemáticos de programación lineal y realizar su transformación al formato requerido por algunas de las herramientas que ofrecen la funcionalidad de resolverlos, como AMPL y GAMS. La valida-ción del trabajo se realizó a través de un caso de estudio enmarcado en el con-texto de una empresa productora de gomas de mascar.

Palabras Clave: metamodelo, modelo matemático, programación lineal, trans-formaciones

1 Introducción

Muchas empresas encuentran en los modelos matemáticos una poderosa herra-

mienta para estudiar el comportamiento de un sistema o algún componente del mis-

mo. Específicamente, las empresas los utilizan para optimizar sus procesos [1], como

por ejemplo el proceso de producción de Columbia Candies Factory, quienes buscan

establecer la combinación de la cantidad de producción, de tipos de goma de mascar,

que maximice sus ganancias con un límite de recursos. Este ejemplo se ampliará más

adelante al presentarse como el caso de estudio de este trabajo. Para abordar este tipo

de problemas, En primer lugar se busca realizar una representación del sistema o del

componente que se desea estudiar, luego se realiza una representación abstracta de

éste por medio de un modelo matemático, se buscan programas o plataformas que

permitan resolver el modelo planteado y finalmente se interpretan los resultados por

estos programas. Sin embargo, debido a que existen una gran cantidad de plataformas

para resolver este tipo de modelos los modeladores deben aprender diferentes lengua-

jes para expresarlos en cada una de ellas.

Para liberar al modelador de la responsabilidad de aprender tantos lenguajes como

herramientas utilice, se implementó una herramienta llamada M3PL que permite la

creación y posterior transformación de modelos a dos diferentes plataformas AMPL1

y GAMS2. En dicha implementación, se desarrolló un leguaje de dominio específico

para definir los modelos matemáticos de programación lineal a partir de los cuales se

genera, de manera automática, código valido para las plataformas. Esta herramienta

1A Modeling Language for Mathematical Programming (AMPL). http://www.ampl.com/ 2The General Algebraic Modeling System (GAMS). http://www.gams.com/

fue construida utilizando el IDE de Eclipse, en el marco del proyecto EMF con he-

rramientas como ATL y Acceleo, las cuales soportadas bajo el enfoque MDE permi-

ten realizar transformaciones requeridas para la generación de código.

Este artículo empieza por hacer una presentación del contexto de programación li-

neal y el problema a resolver junto con el caso de estudio utilizado para validar la

herramienta. Luego, se presenta la herramienta desarrollada para dar solución al pro-

blema, el lenguaje de dominio creado, los metamodelos y transformaciones que hacen

parte de la solución y los resultados obtenidos de la validación. Posteriormente se

mostrará el trabajo futuro, las conclusiones y finalmente la bibliografía.

2 Programación Lineal

La programación lineal es una técnica de investigación de operaciones para la de-

terminación de la asignación óptima de recursos escasos cuando la función objetivo y

las restricciones son lineales [2]. Según esto, se puede decir que, el problema que la

programación lineal aborda, se resume en la asignación optima de recursos limitados

a actividades, también conocidas como variables, que compiten por ellos para ser

realizadas. Poniéndolo de esta manera, la variedad de situaciones que se adaptan a

esta descripción son muchas, desde la planeación presupuestal en una casa de familia

hasta la planeación presupuestal en una nación; desde la programación de una dieta de

comida hasta la programación de complicadas mezclas químicas, pasando por la pla-

neación de transportes en una pequeña ciudad o la planeación de las rutas aéreas de

una aerolínea de talla mundial.

2.1 Modelos Matemáticos de PL

Para la solución de los problemas planteados anteriormente, la programación li-

neal ha desarrollado diferentes métodos, cada uno de los cuales tiene como requisito

la construcción de un modelo matemático para describir la situación que se pretende

resolver. Estos modelos matemáticos tienen los siguientes elementos, terminología y

notación, según Hillier y Lieberman [3]:

Variables: En los problemas de programación lineal son las actividades que reali-

za el sujeto del problema, usualmente una empresa productora, un inversionista o una empresa que vende o compra.

Recursos: Son los elementos que el sujeto del problema utiliza para llevar a cabo

las actividades o variables, como materias primas, dinero o máquinas.

Nivel de Variable: Es el resultado que la programación lineal desea encontrar;

básicamente el número o cantidad de elementos de una variable, sujeto a unos ob-

jetivos y a unos recursos limitados.

Función Objetivo: Es el valor que se quiere optimizar. Esta optimización está

sujeta a los niveles de variable y a la limitación de los recursos.

Los modelos matemáticos de programación lineal plantean el problema en térmi-

nos de toma de decisiones sobre los niveles de las variables. Teniendo en cuenta los

elementos descritos anteriormente, se formula el modelo matemático del problema

general de asignar recursos a variables. En particular, este modelo consiste en elegir

valores de para:

Sujeta a las restricciones:

y

La estructura de los modelos de programación lineal se puede resumir así:

Función Objetivo: Está compuesta por un objetivo, en este caso Maximizar,

y por una ecuación que es el valor que se quiere optimizar.

Restricciones Estructurales: Son la limitaciones de los recursos. Usualmente

por cada limitante de los recursos aparece una o más restricciones.

Restricciones de no Negatividad: Son restricciones inherentes a las variables

ya que éstas, para este tipo de problemas, no pueden ser negativas.

A esta forma general que se acaba de describir, donde el objetivo es maximizar ; las restricciones funcionales son desigualdades con sentido menor o igual; las varia-

bles de decisión tienen restricciones de no negatividad y no negativos, se la deno-

mina forma estándar del modelo. [3]

2.2 Caso de Estudio

De acuerdo a lo anterior y con el fin de demostrar la funcionalidad de la herramien-

ta se propone un caso de estudio, el cual fue escogido gracias a que permite probar

todas las funcionalidades de la herramienta y corresponde al siguiente enunciado y

modelo de problema de programación lineal:

Columbia Candies Factory produce diferentes tipos de goma de mascar. Cada tipo

de goma de mascar representa a la compañía una ganancia determinada. El tiempo de

producción de los paquetes de goma de mascar no puede exceder el tiempo de pro-

ducción total de la empresa y para cada tipo de goma de mascar existe un límite de

producción establecido por la compañía. [4]

Su modelo matemático sería:

Dado:

.

∑( )

Sujeta a las restricciones:

∑( )

2.3 Herramientas de Modelado Algebraico

Las herramientas de modelado algebraico permiten expresar y resolver modelos

matemáticos como los que se construyen a partir de los problemas de programación

lineal. Para expresar los modelos, las diferentes herramientas utilizan sintaxis especí-

ficas en las cuales deben ser escritos, lo cual obliga a los usuarios a aprender dichos

lenguajes, es decir que el modelador debe aprender tantas sintaxis como herramientas

utilice. A continuación se presentan las dos plataformas que se tienen como referen-

cia en este proyecto con el caso de estudio escrito en sus sintaxis.

AMPL: Es un lenguaje de modelado algebraico para planteamiento y solución

problemas de optimización lineal y no lineal con variables continuas o discretas [4].

El cual ofrece una versión gratuita para estudiantes que fue utilizada en este proyecto

para realizar las pruebas. Para expresar y solucionar los modelos, AMPL utiliza los

siguientes tres archivos [5]:

.mod: Este script contiene la definición del modelo matemático de PL.

Definición de variables, parámetros, función objetivo y restricciones.

.dat: Cuando el modelo tiene parámetros, este script contiene los valores

de los parámetros con los cuales se va a resolver el modelo.

.run: Este script llama al archivo del modelo y de los datos, si existe, para

ejecutar la solución.

La siguiente figura presenta los scripts que el modelador debe construir para expre-

sar el modelo del caso de estudio propuesto, se puede ver el contenido de los tres

archivos: Dulces.mod con la definición de parámetros, variables, función objetivo y

restricciones, Dulces.dat con los valores para cada parámetro y Dulces.run el cual

ejecuta la solución a partir de los otros dos scripts mostrando el valor obtenido para la

función objetivo y la variable.

Fig1. Scripts en AMPL para caso de estudio propuesto.

GAMS: Es un programa para la solución de modelos matemáticos de optimiza-

ción, como AMPL, maneja los conceptos de variable, parámetro, índice, función obje-

tivo y restricciones, su diferencia está en que el modelo se expresa en un solo archivo

compuesto por los siguientes bloques [6]:

VARIABLES: Declaración de variables.

EQUATIONS: Declaración de ecuaciones.

MODEL: Se definen las ecuaciones que componen el modelo.

SOLVE: Se define los métodos de solución del modelo.

SET: Declaración de conjuntos. (Opcional)

PARAMETERS: Declaración de parámetros y sus valores. (Opcional)

DISPLAY: Se definen las variables que se deben mostrar como resultado.

(Opcional)

Fig2. Archivo Dulces.gms con el modelo matemático del caso de estudio.

La figura anterior presenta el contenido del archivo Dulces.gms, en el editor propio

de GAMS, el cual corresponde al modelo matemático del caso de estudio propuesto.

En este se pueden observar los bloques descritos anteriormente señalados por el editor

con letras azules.

3 M3PL

Con el fin de liberar al modelador de la responsabilidad de aprender los lenguajes

específicos de cada plataforma que utilice, a través de este trabajo, se creó una he-

rramienta que permite expresar los modelos de programación lineal y traducirlos a los

lenguajes específicos, en este caso, de AMPL y GAMS. La herramienta, llamada

M3PL, se construyó bajo el enfoque MDE y está compuesta de dos partes:

3.1 Lenguaje de Dominio Especifico

Para permitir a los usuarios expresar los modelos matemáticos se creó un lengua-

je de dominio específico a partir del metamodelo [7] de modelos matemáticos de pro-

gramación lineal, que se expondrá en la siguiente sección. La sintaxis y gramática del

lenguaje fue definida en EMFText3. El modelo matemático del caso de estudio pro-

puesto, expresado en el lenguaje de M3PL, se puede observar en la siguiente figura:

Fig3. Representación del modelo matemático del caso de estudio en el lenguaje M3PL.

Como se puede ver el lenguaje permite expresar los siguientes conceptos:

Modelo Matemático: Con la palabra reservada ModeloMatematicoPL el

lenguaje permite expresar el concepto de modelo matemático con el cual

se empieza a expresar el modelo, después de la palabra reservada es nece-

sario que el usuario especifique el nombre del modelo en este caso Dul-

ces.

Parámetro Simple: Permite expresar un parámetro que tiene un solo valor

asociado, con la palabra reservada ParametroSimple, después de la pala-

bra se debe especificar el nombre del parámetro, la letra que lo simboliza

dentro del modelo y su respectivo valor. Los parámetros simples del caso

de estudio serían el número de sabores y el total de horas.

Parámetro Vector: Permite expresar un parámetro que tiene más de un va-

lor asociado, formando un vector, con la palabra reservada ParametroVec-

tor, después de la palabra se debe especificar el nombre del parámetro, la

3EMFTexthttp://www.emftext.org/EMFTextGuide.php

letra que lo simboliza dentro del modelo, el índice asociado y los valores

separados por comas (,). En el caso de estudio los parámetros vectores se-

rían las ganancias, la producción y las demandas máximas de los dulces.

Índice: Cuando los modelos matemáticos involucran una gran cantidad de

variables o parámetros es necesario que estos elementos tengan asociado

un subíndice, en el lenguaje propuesto esto se expresa con la palabra re-

servada Indice seguido del símbolo, su valor mínimo y máximo. Para el

caso de estudio planteado el índice está relacionado con el número de sa-

bores.

Variables: Permiten expresar las variables de un modelo, a través de la pa-

labra reservada Variable, seguida de su nombre y también se debe especi-

ficar la letra que lo simboliza dentro del modelo, su índice asociado, si lo

tiene, y la relación de no negatividad si existe. Para el ejemplo se especifi-

ca una variable de símbolo X que tiene asociada un índice.

Función Objetivo: Permite expresar la función objetivo de los modelos

matemáticos de PL, con la palabra reservada FuncionObjetivo seguido de

su nombre, además de su objetivo y expresión matemática. En el caso de

estudio se establece la función objetivo ganancias para maximizar.

Restricción Estructural: Permite expresar las restricciones del modelo, a

través de la palabra RestriccionEstructural seguida por su nombre y la ex-

presión matemática correspondiente, incluyendo iteradores. Para el ejem-

plo las restricciones son la del tiempo disponible y demanda máxima de

cada sabor.

Restricción de No Negatividad: Con la palabra reservada RestriccionNo-

Negatividad permite indicar cuando una variable o un grupo de variables

debe cumplir restricciones de no negatividad. En el ejemplo se establece

la restricción de no negatividad sobre la variable X.

El lenguaje establece que los conceptos del modelo matemático deben ir con su

respectivo nombre, lo cual permite crear modelos con metadatos que permiten inter-

pretar mejor los resultados obtenidos al final de la generación de código para las pla-

taformas. Por otro lado, también existen atributos propios de cada concepto, como lo

son Letra, Valor, Valores, Objetivo, Operación, Mínimo y Máximo. Además se utili-

zaron los corchetes como símbolos que abren y cierran bloques en donde se deben

especificar dichos atributos.

Al ser un lenguaje para representar modelos matemáticos, es importante que éste

permita escribir expresiones matemáticas, la palabra reservada para ello es Operación

con la cual se pueden escribir las siguientes operaciones:

Suma: Con el signo + entre los dos sumandos.

Resta: Con el signo - entre minuendo y sustraendo .

Multiplicación: Con el signo * entre los dos factores.

División: Con el signo / entre dividendo y divisor.

Sumatoria: Con la palabra reservada Sumatoria, también se debe espe-

cificar el índice asociado y la operación que se debe sumar.

Cabe resaltar que los sumandos, el minuendo, sustraendo, los factores, el dividendo

y divisor, pueden a su vez ser un conjunto de operaciones con lo cual se pueden escri-

bir expresiones como: (x+y) * z.

3.2 Cadena de Transformación

Esta sección explica el proceso para traducir los modelos matemáticos, desde la

sintaxis de la herramienta, a las sintaxis de AMPL y GAMS.

Como se muestra en la figura 4, se creó una cadena de transformación donde el

usuario exprese un modelo, en el lenguaje específico, conforme a un metamodelo de

modelos matemáticos [8]. Luego a través de una transformación modelo a modelo se

obtiene un modelo intermedio, conforme al metamodelo intermedio, el cual es some-

tido, nuevamente, a transformaciones de modelo a modelo para obtener dos modelos

conformes a los metamodelos AMPL y GAMS respectivamente. Finalmente, se reali-

za una transformación de modelo a texto para obtener los archivos válidos para las

plataformas.

Fig4. Representación de la cadena de transformación realizada para la traducción a las dos

plataformas.

Las transformaciones modelo a modelo (M2M), se realizan a través de reglas de-

clarativas programadas en la herramienta ATL [9]. Por su parte las transformaciones

de modelo a texto (M2T), se realizan con la herramienta Acceleo en donde se definen

las reglas de generación de código para los archivos correspondientes, estas reglas se

basan en los metamodelos y lenguajes específicos de las plataformas.

En cuanto a los metamodelos [7], se creó un metamodelo de modelos matemáticos

de programación lineal, basado en la estructura descrita en secciones anteriores. Co-

mo se puede ver en la figura 5, se definió que la función objetivo es siempre una

ecuación y las restricciones pueden ser ecuaciones o inecuaciones. En el caso de la

función objetivo esta tiene una expresión matemática en su parte derecha y en el caso

de las restricciones estas tienen una expresión matemática en su parte derecha, un

sentido (<,<=,=,>=,>) y una expresión matemática en su parte izquierda.

Fig5. Representación del metamodelo de modelos matemáticos de PL con sus elementos

principales y las relaciones entre ellos.

En el contexto de este proyecto definimos que una expresión matemática puede ser

una constante, un parámetro, una variable, una sumatoria o una operación entre dos

expresiones, la cual además cuenta con un operador (+, -, *, /), esto corresponde a la

parte del metamodelo presentada en la siguiente figura.

Fig6. Representación de la expresión en el metamodelo de modelos matemáticos.

El metamodelo intermedio, por su parte, tiene como objetivo preparar los datos del

modelo para ser traducidos a los lenguajes específicos de las plataformas. Este meta-

modelo ofrece las siguientes ventajas en el proceso de transformación:

Permite pasar todos los datos numéricos a cadenas de texto ya que nuestra

herramienta generara texto.

Permite transformar las restricciones de no negatividad en atributos de cada

variable con el fin de facilitar la manipulación final.

Permite construir una cadena de texto con el vector de valores del parámetro

con su posición y valor ya que de esta forma deben ser escritos en las dos

plataformas.

En la figura 7, se muestran las variaciones de los conceptos que representan venta-

jas en el metamodelo intermedio.

Fig7. Representación de una variable y un parámetro en un metamodelo intermedio.

Finalmente, se crearon los metamodelos de cada una de las plataformas, los cuales

permiten aplicar las reglas de generación de código valido. Como se puede ver en la

siguiente figura en el metamodelo de AMPL aparecen los conceptos de archivos o

scripts quienes son los que agrupan o se relacionan con los demás elementos del mo-

delo. Al igual que en el metamodelo de modelos matemáticos de PL inicial la función

objetivo y restricciones se componen de sentido y expresiones, conceptos que se mo-

delan de la misma forma.

Fig8. Representación de un metamodelo AMPL y sus principales elementos.

Por otro lado en GAMS la función objetivo y restricciones se componen de expre-

siones que se modelan de la misma forma que en el metamodelo de modelos matemá-

ticos de PL. Como se muestra en la siguiente figura el metamodelo de GAMS cuenta

con los conceptos de archivo y bloques que componen dicho archivo.

Fig9. Representación de un metamodelo GAMS en donde se muestran los principales blo-

ques con los que éste cuenta

4. Resultados Obtenidos

Al aplicar la cadena de transformación y metamodelos propuestos al modelo ma-

temático del caso de estudio, definido en la sintaxis M3PL se obtuvo:

En el caso de AMPL, como se puede ver en la siguiente imagen, los tres bloques de

código con los cuales trabaja la herramienta, es importante resaltar que el código ge-

nerado para el archivo del modelo esta comentado lo que da facilidad de interpreta-

ción para el usuario final.

Fig10. Resultado de la transformación a 3 archivos de texto para la plataforma AMPL.

Por su parte en GAMS, se generó el archivo con los bloques correspondientes de la misma

forma el código generado cuenta con metadatos que permiten una mejor interpretación por

parte del usuario, tal cual se evidencia en la siguiente figura.

Fig11. Resultado de la transformación a un archivo de texto para la plataforma GAMS.

Cabe anotar que tanto el código generado para AMPL como el generado para

GAMS, fueron compilados y solucionados correctamente en las respectivas herra-

mientas, tal como se puede observar a continuación.

Fig12. Resultado de la ejecución del código generado en plataformas.

4. Trabajos relacionados y futuros

Realizando la búsqueda de herramientas similares a la propuesta en este artículo,

no se encontró ninguna que ofrezca funcionalidades parecidas a M3PL, los hallazgos

se limitaron a herramientas que, como las plataformas, sirven para resolver los pro-

blemas ya planteados, algunas de ellas con sintaxis específicas, de esto se concluye

como primer trabajo futuro la creación de metamodelos y reglas de transformación a

nuevas herramientas que enriquezcan el listado de plataformas para las cuales M3PL

puede generar código, gracias a la flexibilidad que el enfoque MDE brinda, esta tarea

no representa mayores complicaciones.

Por otro lado encontramos que el lenguaje matemático es muy amplio por ello las

plataformas exploradas incluyen conceptos en su sintaxis que no fueron contemplados

en este proyecto, la extensión del metamodelo de modelos matemáticos de programa-

ción lineal permitirá, en un futuro, expresar diferentes conceptos a través del lenguaje

específico definido en M3PL, esto con el fin de permitir a los usuarios escribir diver-

sos tipos de modelos. Cabe anotar que la forma en que está construido el metamodelo

en mención, permite adicionar nuevos conceptos de forma fácil, gracias al manejo del

concepto expresión.

Finalmente encontramos que además de la programación lineal, existen muchas

otras áreas del conocimiento que utilizan los modelos matemáticos para plantear y

resolver sus problemas, en este sentido la creación de herramientas similares a M3PL

para estas áreas del conocimiento es un campo de acción e investigación que se abre a

partir de este trabajo.

5. Conclusiones

Desde el punto de vista del modelador de problemas de PL, la herramienta

lo libera de la obligación de aprender diferentes lenguajes de sintaxis espe-

cífica para expresar sus modelos.

En particular M3PL puede servir como base para una herramienta que faci-

lite la labor de los modeladores.

El desarrollo a partir de metamodelos, modelos y transformaciones da un

grado alto de flexibilidad, en nuestro caso por ejemplo sería muy fácil aña-

dir una nueva plataforma para la cual generar código.

El metamodelo de modelos matemáticos de programación lineal presenta

flexibilidad al permitir adicionar nuevos elementos del lenguaje para facili-

tar la expresión de otros conceptos de modelos matemáticos diferentes a los

lineales.

La parte del metamodelo de modelos matemáticos correspondiente a expre-

siones matemáticas también permite adicionar de forma sencilla nuevos

conceptos u operaciones. Actualmente se encuentran la suma, resta, multi-

plicación, división y sumatoria.

La definición del metamodelo inicial debe ser lo más correcta posible desde

el principio de lo contrario un cambio en su estructura puede generar gran-

des modificaciones en todo el desarrollo del proyecto.

La creación de un modelo intermedio facilita la preparación de los datos y

elementos para la transformación a los diferentes modelos finales.

Las plataformas exploradas en este proyecto utilizan un lenguaje algebraico

similar debido a que comparten el mismo dominio, las diferencias están en

la forma de agrupación de dichos elementos del lenguaje y el modelo ma-

temático. Estas diferencias fueron modeladas en sus respectivos metamode-

los.

Las herramientas utilizadas en el proyecto en general mostraron un correcto

desempeño.

Referencias

[1] Taha H. A.: Investigación de operaciones, Séptima Ed. Pearson Prentice Hall. Universty of Arkansas, Fayetteville.(2004)

[2] Moskowitz H., Wright G.: Investigación de Operaciones, Primera Ed., Prentice - Hall, México D.F. (1982)

[3] Hillier F,;Liberman G.: Introducción a la Investigación de Operaciones, Octava Ed. Mc GRAW-HILL, México D.F.(2006)

[4].Herrera T.: AMPL Tutorial.Columbia University.

http://www.columbia.edu/~dano/courses/4600/lectures/6/AMPLTutorialV2.pdf.

(2009).Accedido el 23 de Mayo de 2013

[5] Fourer R.; Gay D. M.;Kernighan B. W: AMPL: A Modeling Language

for Mathematical Programming, Second Ed.Duxbury Press, Brooks, Cole Publishing Com-

pany. (2002).

[6] SalaGarrido R.: Capítulo 14: GAMS: GAMS: Spanish Reference Manual. Universidad de

Valencia.http://www.uv.es/~sala/gams/14.PDF. Accedido el 23 de Mayo de 2013.

[7] Steinberg D.; Budinsky F.; Paternostro M.;Merks E.:EMF: Eclipse Modeling Framework, Second Ed. Addison-Wesley Professional ( 2008).

[8] Bézivin J.: In Search of a Basic Principle for Model Driven Engineering. UPGRADE.http://www.dei.isep.ipp.pt/~alex/publico/mde/up5-2Bezivin.pdf.(2004). Ac-

cedido el 23 de Mayo de 2013 [9] Jouault F.;Kurtev I.: TransformingModelswith ATL.In Proceedings of the Model Trans-

formations in Practice Workshop, Montego Bay, Jamaica. pp. 128-138 (2005).