Revista Cubana de Ciencia Agrícola ISSN: 0034-7485 [email protected] Instituto de Ciencia Animal Cuba

Roche, A.; Kakes, Alibeit; Gómez, Saraí; Noda, Aida C.; Sotolongo, Anaily; Vega, Yanelis Comparación de los métodos SIMPLEX y Punto Interior en la optimización de formulaciones de dietas para el ganado Revista Cubana de Ciencia Agrícola, vol. 40, núm. 1, 2006, pp. 9-14 Instituto de Ciencia Animal La Habana, Cuba

Disponible en: http://www.redalyc.org/articulo.oa?id=193017708002

Cómo citar el artículo Número completo Más información del artículo Página de la revista en redalyc.org

Sistema de Información Científica Red de Revistas Científicas de América Latina, el Caribe, España y Portugal Proyecto académico sin fines de lucro, desarrollado bajo la iniciativa de acceso abierto

Revista Cubana de Ciencia Agrícola, Tomo 40, No. 1, 2006.

9

Comparación de los métodos SIMPLEX y Punto Interior en la optimización de formulaciones de dietas para el ganado A. Roche1, Alibeit Kakes2, Saraí Gómez1, Aida C. Noda1, Anaily Sotolongo1 y Yanelis Vega1 1

Instituto de Ciencia Animal, Apartado Postal 24, San José de las Lajas, La Habana. Correo electrónico: [email protected] 2 Facultad de Matemática, Universidad de La Habana. Calle San Lázaro y L. Vedado, Ciudad de la Habana Una de las técnicas más importantes de optimización matemática, aplicada a la ciencia animal, es la programación lineal en el problema de las raciones óptimas. Existen diferentes algoritmos para resolver esta situación, los más utilizados son el SIMPLEX y, más recientemente, los métodos de Punto Interior. La eficiencia computacional de estos algoritmos depende, en gran medida, de las características dimensionales y numéricas de las matrices con que trabajan. Por otra parte, hay diferencias entre las matrices obtenidas al aplicar el modelo de raciones óptimas a especies monogástricas y rumiantes, en cuanto al tamaño de la matriz y a los valores numéricos de sus componentes. Por lo anterior, el objetivo de este trabajo es comparar los algoritmos SIMPLEX y Punto Interior, como solución al problema de raciones óptimas para especies monogástricas y rumiantes. Se utilizaron 16 raciones para monogástricos y 15 para rumiantes y se realizaron corridas de ambas por el método SIMPLEX y Punto Interior. Se obtuvieron valores en cuanto al número de iteraciones para llegar a la solución óptima y a la exactitud del óptimo alcanzado para cada una de las especies. Se utilizó una prueba T de Student para los datos pareados en la comparación de los resultados, en cuanto al número de iteraciones necesarias para llegar al óptimo, al usar uno u otro método. Se comprobó que resulta más eficiente utilizar el método SIMPLEX para la solución del problema de optimización de formulaciones de dietas para la alimentación de rumiantes y monogástricos. Palabras clave: optimización lineal, formulación de dietas, métodos SIMPLEX y Punto Interior.

La optimización matemática es una de las principales ramas de la matemática aplicada. Desde su descubrimiento a mediados del siglo XX, se considera uno de los campos más controvertidos de la investigación matemática (Illés y Terlaky 2002). Los problemas del tipo P0:min {f (x )/x ∈ M} se conocen como Problemas de Optimización con Restricciones. El problema P0 recibe el nombre de Problema de Programación Lineal, cuando la función objetivo y el conjunto de restricciones se expresan de forma lineal (Tedeschi et al. 2000): P1:min {f (x ) = ct x/Ax = b; 0 ≤ h ≤ x ≤ H} [I] Con el desarrollo de la investigación de operaciones y la optimización, han surgido una gran cantidad de algoritmos para resolver pro-

blemas lineales. Conjuntamente con el surgimiento de la optimización lineal, Dantzig (1949) desarrolla un algoritmo computacional, conocido como el Método SIMPLEX. Posteriormente, otros métodos se han expuesto; pero sin éxito, como es el caso de Khachian (1958). Después de casi treinta años, Karmarkar (1984) presenta la teoría de los Métodos de Punto Interior (IPM, según sus siglas en inglés), el cual prometía un rendimiento computacional superior al SIMPLEX. Una de las primeras cuestiones que debían resolverse mediante la programación lineal es el problema de la dieta. Tradicionalmente, la determinación de la dieta óptima se ha concebido como el problema de minimizar el costo de los ingredientes, sujeto a las restricciones de

10

Revista Cubana de Ciencia Agrícola, Tomo 40, No. 1, 2006.

los requerimientos nutritivos (Torres-Rojo 2001). Este se ha resuelto mediante diferentes algoritmos, entre ellos el Método SIMPLEX (Dantzig 1990) y el IPM (Marsten y Shanno 1998). La eficiencia computacional de estos algoritmos depende, en gran medida, de las características dimensionales y numéricas de las matrices con que trabajan. Una de las aplicaciones del problema de la dieta ha sido la formulación de raciones y piensos para el ganado. La alimentación animal representa entre el 60 y 80 % de los costos variables de los sistemas de producción (Heard et al. 2004). De ahí, la importancia de utilizar raciones que, además de cumplir con el requerimiento, sean de mínimo costo. De esta forma, se busca la máxima utilidad económica, dados los requerimientos para la alimentación animal. Existen diferencias entre los ingredientes y nutrientes que se utilizan para la alimentación de las especies monogástricas y rumiantes. Esto implica que existan diferencias dimensionales y numéricas de la matriz resultante, al aplicar el problema de optimización de formulaciones de dietas para estas especies, lo que influye en la eficiencia computacional del método que se utiliza para su solución. En este caso, se consideró como eficiencia computacional el número de iteraciones (número de soluciones factibles que verifica el método antes de alcanzar la solución óptima) y la exactitud del óptimo alcanzado (valor correspondiente de la función objetivo como resultado de la aplicación de cada método) (Oliveira y Lyra 2004). El objetivo de este trabajo es comparar la eficiencia de los algoritmos SIMPLEX e IPM, al aplicarlos al problema de optimización de formulaciones de dietas para la alimentación de las especies monogástricas y rumiantes. Materiales y Métodos La metodología que se utilizó en la comparación de los métodos se propuso por Oliveira y Lyra (2004) para el análisis del comportamiento del SIMPLEX e IPM en los problemas de optimización, conocidos como problemas de adaptación L∞.

En la confección de la dieta, los alimentos que están involucrados se consideran ingredientes o materias primas, y la composición nutritiva de esos alimentos conforma los nutrientes. Se consideró la formulación estándar del problema de optimización de la dieta óptima, ecuación II, en la cual los nutrientes representan el número de filas y los ingredientes, las columnas (Torres-Rojo 2001).

Min D = ∑cjxj j

s.a. ∑aijxj ≥ ri

[II]

∀i=1, 2, …m

j

xj aporte del j-ésimo ingrediente (j=1, 2, …, n) cj costo por unidad del ingrediente xj aij aporte del i-ésimo nutriente (i=1, 2, …, m) que contiene el j-ésimo ingrediente (x j), ri necesidades a ser cubiertas del i-ésimo nutriente. Para el análisis se establecieron diferentes tamaños y coeficientes de las matrices resultantes del problema de optimización en la formulación de dietas, a partir de dietas reales. Se consideraron las especificaciones de cada especie. Tamaño de las matrices. Se realizó el análisis de la cantidad de ingredientes y nutrientes involucrados en las raciones, según la especie. En los rumiantes, la cantidad de nutrientes que se consideraron son: proteína bruta, fibra bruta, calcio, fósforo y el componente energía, entre otros. Sin embargo, en las raciones de los monogástricos se incluyen además, los aminoácidos (metionina, cistina, arginina, lisina, triptófano, treonina, valina, entre otros), así como las vitaminas A y E, el Riboflavin y minerales (sodio, potasio, magnesio, zinc, entre otros) (Dale y Batal 2002.) Por tanto, el número de filas de las matrices que se obtienen para la representación del problema en las especies monogástricas es mayor que en el caso de los rumiantes. Sin embargo, se valora la matriz como pequeña, a partir de los criterios de Andersen et al. (1996), pues la cantidad de nutrientes (filas de la matriz) se comporta en un rango de 4 a 20; en los casos extremos puede llegar hasta 40, lo que resulta casi imposible considerar al elaborar una ración.

11

Revista Cubana de Ciencia Agrícola, Tomo 40, No. 1, 2006.

Con respecto a la cantidad de columnas de la matriz, dígase ingredientes involucrados en la confección de la dieta, tampoco resulta un número muy alto. Según Jones (2002), la cantidad de materia prima fluctúa entre 5 y 20 (este último para el caso extremo), siempre menor en los rumiantes, en los que oscila entre 2 y 10. Por tanto, se considera que en los problemas de optimización de formulaciones de dietas para monogástricos y rumiantes, las matrices resultantes son pequeñas, según Andersen et al. (1996). A partir de los criterios anteriores, se seleccionaron matrices con diferentes tamaños que representan situaciones reales en la confección de raciones para monogástricos y rumiantes. El tamaño de estas matrices influye en la eficiencia del método que soluciona el problema de programación lineal. Se utilizaron 15 raciones para monogástricos y 16 raciones para rumiantes. Las dimensiones de las matrices variaron de 7 x 6 a 12 x 11 para monogástricos y de 3 x 5 a 8 x 6 para rumiantes. Coeficientes de las matrices. Otro criterio de comparación entre los métodos es el análisis numérico de los coeficientes de las matrices resultantes, al resolver el problema de optimización de la dieta. Estos coeficientes representan el porcentaje de cada nutriente que tiene el ingrediente (variable aij en la ecuación II). Los nutrientes de aminoácidos, vitaminas y minerales representan un bajo porcentaje dentro de los ingredientes (por lo general menor que 1). Esto significa que en raciones típicas para monogástricos, en las que se consideran varios aminoácidos, vitaminas y minerales, la matriz resultante tendrá una cantidad considerable de coeficientes (aij), entre 0 y 1. En

cambio, los nutrientes que se analizan en los ingredientes de las fórmulas de los rumiantes tienen valores, en su mayoría, superiores a 1. Si se consideran estos criterios, las matrices resultantes tienen características numéricas dadas por la cantidad de coeficientes en el intervalo [0,1]. En los monogástricos, el 59.4 % del total de coeficientes estaba en ese intervalo y en los rumiantes, el 5.6 %. A partir de esa información, se realizaron las corridas de las matrices por los dos métodos. En el SIMPLEX se utilizó el software QMWIN, versión 1.41 (Copyright Howard J. Weiss) y en el IPM, el software UHMPI, versión 1.0 (Copyright Facultad de Matemática, Universidad de la Habana). Como resultado de las corridas, se recopilaron datos relacionados con la cantidad de iteraciones necesarias para alcanzar el mínimo, así como con el valor óptimo alcanzado al evaluar la función objetivo. Para el análisis estadístico de la información se utilizó la prueba T de Student para datos pareados, con el objetivo de comparar los resultados, en cuanto a la variable número de iteraciones para llegar al óptimo, cuando se usa uno u otro método, así también para la variable exactitud del óptimo. En los rumiantes, el tamaño de muestra fue de 15 y en los monogástricos 16. El software para el análisis estadístico fue InfoStat (Balzarine et al. 2001). Resultados y Discusión Al aplicar el procesamiento estadístico se obtuvo un grupo de valores correspondientes a las variables. Las tablas 1 y 2 muestran estos resultados para monogástricos y rumiantes, respectivamente.

Tabla1. Comparación entre los dos métodos para la variable número de iteraciones (monogástricos) Método Media SIMPLEX 13.73 Punto Interior 19.06 Prueba T de Student para datos pareados Media SIMPLEX- Punto Interior - 5.33

N 15 15 EE ± 1.06

Desviación estándar 2.31 3.65

EE ± Media 0.59 0.94

t- Student - 4.99

Significación 0.0001

12

Revista Cubana de Ciencia Agrícola, Tomo 40, No. 1, 2006.

Tabla 2. Comparación entre los dos métodos para la variable número de iteraciones (rumiantes) Método Media N Desviación estándar EE ± Media SIMPLEX 10.93 16 3.47 0.86 Punto Interior 19.93 16 6.75 1.68 Prueba T de Student para datos pareados Media EE ± t- Student Significación SIMPLEX- Punto Interior - 9.00 1.03 - 8.71 0.0001

Para ambas especies se encontraron diferencias significativas, en cuanto al número de iteraciones necesarias para llegar al óptimo, al usar el Método SIMPLEX o el de Punto Interior. Cuando se utilizó el SIMPLEX, el número de iteraciones necesarias fue menor que con el Punto Interior. En la tabla 3 se muestran los resultados para monogástricos, al aplicar la prueba T de Student a la variable exactitud de óptimo.

do coincide con los de Illés y Terlaky (2002) cuando plantean que el SIMPLEX es el mejor método para matrices pequeñas y estables numéricamente; sin embargo, el IPM es especialmente eficaz para resolver problemas en los que se involucre un gran número de variables, y cuyas matrices sean inestables numéricamente. A partir de los resultados obtenidos fue posible estimar un polinomio que acote el número de iteraciones (y), en función de la canti-

Tabla 3. Comparación entre los dos métodos para la variable exactitud del óptimo alcanzado (monogástricos) Método Media N Desviación estándar EE ± Media SIMPLEX 26.698 15 5.234 1.351 Punto Interior 26.675 15 5.239 1.352 Prueba T de Student para datos pareados Media EE ± t- Student Significación SIMPLEX- Punto Interior 0.02 0.02 1.00 0.334

A los rumiantes no se aplicó la prueba T de Student, pues todos los resultados para esta variable fueron iguales en el método SIMPLEX y en el método de Punto Interior. Por tanto, la variable exactitud del óptimo no mostró diferencia para el método SIMPLEX ni para el Punto Interior. Esto quiere decir que ambos métodos llegan a la misma solución óptima para las dos especies. Sin embargo, según las tablas 1 y 2, el método SIMPLEX alcanza el óptimo en un número menor de iteraciones. Esto comprueba su eficiencia al utilizarse para resolver el problema de la dieta para monogástricos y rumiantes, cuyas matrices resultantes al aplicar el modelo se consideran pequeñas y estables, según el criterio de Andersen et al. (1996). Este resulta-

dad de ingredientes (x) involucrados en la ración. Para el método SIMPLEX, el polinomio obtenido fue y = 1.66 x y para el IPM, y = 3.32 x. Este resultado coincide con el informado por Bazaraa et al. (1989), quienes plantean que para la mayoría de los problemas prácticos el polinomio que se obtiene en el método SIMPLEX es, aproximadamente, y = 1.5 x y, raramente llega a y = 3 x. En este trabajo, el coeficiente del polinomio del IPM es mayor que el SIMPLEX, lo que corrobora la ineficiencia de la utilización del IPM para la solución del problema de optimización en la formulación de dietas para monogástricos y rumiantes. Un último análisis se realizó al comparar la variable número de iteraciones en cada una de las repeticiones (es decir, por cada ración), para

13

Revista Cubana de Ciencia Agrícola, Tomo 40, No. 1, 2006.

obtener el óptimo, al aplicar ambos tratamientos (SIMPLEX e IPM) en monogástricos y rumiantes, respectivamente (figuras 1 y 2).

bles numéricamente, mientras que el SIMPLEX es favorable para las pequeñas. Afirman, además, que la llave del éxito está en estudiar las

No. de Iteraciones 35 25 15 5 -5

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 Raciones (No. de repeticiones)

SIM PLEX Punto Interior Figura 1. Número de iteraciones para cada ración en monogástricos No. de Iteraciones 35 25 15 5 -5

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16

Raciones (No. de Repeticiones) SIM PLEX

Punto Interior

Figura 2. Número de iteraciones para cada ración en rumiantes

La figura 1, correspondiente a monogástricos, muestra que es menor la diferencia de los valores de las variable número de iteraciones entre el método SIMPLEX e IPM, con respecto a lo representado en la figura 2, que procede de las raciones para rumiantes. Esto ocurre porque las matrices que se generan para los monogástricos son relativamente mayores y más inestables numéricamente. Por tanto, el IPM tiene un comportamiento relativamente mejor, para el caso de los monogástricos que para los rumiantes. Oliveira y Lyra (2004) plantean que los métodos IPM ganan para los problemas que generan matrices grandes e inesta-

características subyacentes del problema de optimización, de forma tal que el método haga mejor uso de las características de dispersión y arquitectura de la computadora. Por tanto, se concluye que el método SIMPLEX es más eficiente que el IPM en la optimización de formulaciones de dietas para especies monogástricas y rumiantes, por lo que se recomienda su utilización en ambas especies. Referencias Andersen, E.D., Gondzio, J., Mészáros, C.S. & Xu, X. 1996. Implementation of interior point

14

Revista Cubana de Ciencia Agrícola, Tomo 40, No. 1, 2006.

methods for large scale linear programming. En: Interior Point Methods of Mathematical Programming. Eds. T. Terlaky. Kluwer Academic Publishers. Dordrecht, The Netherlands. p. 189 Balzarine, G.M., Casanovas, F., DiRienzo, J.A., Gonzalez, L.A. & Robledo, C.W. 2001. Software Estadístico. Manual de Usuario. Versión 1. Córdova, Argentina. Bazaraa, M., Jarvis, J. & Sherali, H.D. 1989. Linear Programming and Network flows. Second Ed. Jonh Wiley & Sons. Dale, N. & Batal, A. 2002. Ingredient analysis table: 2002 edition. Feedstuffs. Reference Issue & Buyers Guide. 74:28. p. 16 Dantzig, G.B. 1949. Programming in a Linear Structure. Econometric. 17:1. Summary. Dantzig, G.B. 1990. The diet problem. Interfaces. 20:4. p. 43 Heard, J.W., Cohen, D.C., Doyle, P.T., Wales, W.J. & Stockdale, C. R. 2004. Diet Check—a tactical decision support tool for feeding decisions with grazing dairy cows. Animal Feed Sci. and Tech.112 :177 Illés, T. & Terlaky, T. 2002. Pivot versus interior point methods: Pros and cons. European J. Operational Res.140:170

Jones, F.T. 2002. Quality control in feed manufacturing. Feedstuffs. Reference Issue & Buyers Guide. 74:58 Karmarkar, N. 1984. A new polynomial – time algorithm for linear programming. Combinatorica 4. p. 150 Khachian, L.G. 1958. A polynomial algorithm in linear programming. Doklady Akademiia Nauk. SSSR 244. p.1093 Oliveira, A.R.L. & Lyra, C. 2004. Interior point methods meet simplex in L∞, fitting problems. Intl. Trans. En: Op. Res. 11:309 Marsten. R.E. & Shanno, D. 1998. A reduced gradient variant of Karmarkar‘s algorithm and null- space projections. J. Optimizations Theory and Applications. 57:45 Tedeschi, L.O., Fox, D.G., Chase, L.E. & Wang, S.J. 2000. Whole-herd optimization with the Cornell net carbohydrate and protein system. I. Predicting feed biological values for diet optimization with linear programming. J. Dairy Sci. 83:2139. Torres-Rojo, J.M. 2001. Risk management in the design of a feeding ration: a portfolio theory approach. Agric. Systems. 68:1 Recibido: 23 de diciembre de 2004.