mÉtodos de puntos interiores aplicado a problemas de programaciÓn lineal con Óptimos alternativos

Scientia et Technica Ao X, No x, Mes 200x. UTP. ISSN 0122-1701 1

MTODOS DE PUNTOS INTERIORES APLICADO A PROBLEMAS DE PROGRAMACIN LINEAL CON PTIMOS ALTERNATIVOS

RESUMENEn problemas de programacin lineal que presentan ptimos alternativos es posible determinar la solucin ms atractiva entre ellas de acuerdo a determinadas condiciones del problema. En este documento se presenta una propuesta de modificacin al mtodo de Puntos Interiores Primal-Dual para ser aplicado a problemas de optimizacin con mltiples soluciones. PALABRAS CLAVES: Direcciones de Bsqueda, Mtodo de Barrera

Logartmica, ptimos Alternativos, Programacin Lineal, Puntos Interiores.

ABSTRACTIn problems of linear programming that have alternatives optimal solutions is possible to determine the most attractive solution among them but according to certain conditions of the problem. In this document is presented a proposal of modification of the Primal-Dual Interior Point Method to be applied to problems of optimization with solutions multiple.

KEYWORDS: Directions of Search, Method of Logarithmic Barrier, Optimal Alternative, Linear programming, Interior Points.

OSCAR GOMEZ CARMONAIngeniero ElectricistaProfesor Universidad Tecnolgica de [email protected]

LUIS ALFONSO GALLEGO.Ingeniero ElectricistaEstudiante MaestraUniversidad Tecnolgica de [email protected]

LINA PAOLA GARCES N.Ingeniera ElectricistaProfesor Universidad Tecnolgica de [email protected]

Grupo de Investigacin en Planeamiento de Sistemas Elctricos

1. INTRODUCCIN

La programacin lineal es una metodologa de optimizacin que permite resolver problemas de la vida real, en los cuales una funcin objetivo es optimizada sujeta a un conjunto de restricciones.

Figura 1 Problemas de Programacin Lineal.

Generalmente, los problemas de la vida real pueden ser descritos a travs de un modelo matemtico seleccionando adecuadamente las variables de decisin (a cada variable de decisin est asociada una actividad), planteando la funcin objetivo y todas las restricciones del problema.

Un problema matemtico es lineal (PL) si la funcin objetivo f (x1 ,x2 ,...,xn) y cada restriccin gi (x1, x2, ..., xn) (i =1, 2, ... ,m) son lineales. El problema de optimizacin se puede escribir como:

1 2 1 1 2 2

1 2 1 1 1 2 1

( , ,..., ) ...( . ):

( , ,..., ) ...

( 1,2,..., ; 1, 2,..., )

n n n

i n i i i n

j i j

f x x x c x c x c xSujeto a s ag x x x a x a x a xdondec y a i m j n

= + + +

= + + +

= =

son constantes conocidas [1],[2].El espacio de solucin del conjunto de ecuaciones lineales simultneas es un conjunto convexo que tiene un nmero finito de puntos extremos (un punto extremo no puede ser expresado como una combinacin convexa de otros dos puntos del conjunto).

Si S es un conjunto convexo con un nmero finito de puntos extremos, entonces S es el conjunto de todas las soluciones factibles al problema lineal. La solucin ptima del problema, as sea de maximizacin o minimizacin, es un punto extremo de S, siempre y cuando dicho ptimo exista [2].

Existe tambin la posibilidad de que exista un ptimo que no es un punto extremo (ptimos alternativos). En este caso, el conjunto de soluciones ptimas es dado por el conjunto de combinaciones convexas de los puntos extremos del problema.

En problemas donde existen ptimos alternativos, es posible determinar, de todo ese conjunto, una solucin que procure un objetivo adicional. Por ejemplo, distribucin uniforme de los recursos o agotar un recurso para preservar otro que se tiene en menor cantidad.

Las metodologas tradicionales, encuentran soluciones que corresponden a puntos extremos, sin brindar la posibilidad de explorar todo el conjunto de soluciones

Fecha de Recepcin: (Letra Times New Roman de 8 puntos)Fecha de Aceptacin: Dejar en blanco

Scientia et Technica Ao X, No x, Mes 200x. UTP

ptimas. El mtodo de puntos interiores tiene la capacidad de obtener una solucin diferente a un punto extremo y que hace parte del conjunto de soluciones ptimas factibles, en el caso de ptimos alternativos.En este documento se propone una metodologa para resolver problemas de programacin lineal con ptimos alternativos, que modifica el algoritmo de Puntos Interiores Primal Dual, permitiendo obtener soluciones ptimas que satisfagan objetivos adicionales.

2. METODO DE PUNTOS INTERIORES

Durante dcadas el mtodo simplex ha sido el mtodo de solucin de los problemas de programacin lineal. Sin embargo, desde el punto de vista terico, el tiempo de clculo requerido por este mtodo crece exponencialmente con el tamao del problema.

Muchos investigadores han tratado de desarrollar algoritmos cuyos tiempos de clculo tuviesen un crecimiento polinomial con el tamao del problema. En 1984, Karmarkar propuso un algoritmo cuya complejidad computacional es polinomial y que result altamente competitivo frente al mtodo simplex para resolver problemas de programacin lineal de gran tamao.

El algoritmo de Karmarkar origin multitud de trabajos alrededor de su idea, la cual ha sido mejorada en muchos aspectos. Una de las ms fructferas variantes es el algoritmo de barrera logartmica Primal-Dual. [3]

2.1 Mtodo de Barrera Logartmica Primal-Dual

Este mtodo resuelve el problema de PL primal estndar:

min.

0

Tc xs aAx bx

=

donde x es el vector de variables primales y su problema dual estndar en funcin del vector de variables duales y, incluyendo el vector de variables de holgura z es:

min.

0

T

T

b ys a

A y z cz

+ =

Se utiliza la funcin de barrera logartmica para penalizar las restricciones de desigualdad z 0.

1

max ln

.

nT k

ii

T

b y z

s a

A y z c

=

+

+ =

donde k es el parmetro de barrera en la iteracin k y debe ser disminuido a cero durante el proceso iterativo.

El algoritmo general de solucin es el siguiente: [4]

1. Calcular un punto inicial. Vector primal:

0 :x x donde=

1 12 y 1 12 2

bx jAx A j

+

= =

+ +

Vector dual.

0 1, 100 ,

si c zj jz

caso contrario z cj j

< ==

=

2. Calcular el parmetro de barrera y hacer k = 0.

0 0( )0Tx z

n =

3. Verificar convergencia.

Factibilidad primal: 1

k

k

Ax b

fx

+

Factibilidad dual: 1

k k

k k

TA y z c

fy z

+

+ +

Condicin de optimalidad: 1

o

k k

k

T Tc x b y

Tb y

+

donde f es el error de factibilidad y o es el error de optimalidad.

En caso de que los criterios de convergencia se cumplan pare.

4. Calcular los errores para el punto actual.

2

Scientia et Technica Ao X, No x, Mes 200x. U.T.P

:

[ ... ]1 2[ ... ]1 2

[1 1 ... 1]

k T k kr c A y zpk kr b Axdk k T kr e X Z ec

donde

X diag x x xnZ diag z z zn

Te

=

=

=

=

=

=

5. Obtener las direcciones de bsqueda.

k k k kx x x xctr obj fac = + +

1 1 ( )k k k kDireccion central x D P D X ectr k k =

1 1 k kDireccion objetivo x D P D cobj k k

=

2 2 1 ( )k T T kDireccion factible x D A AD A rpfac k k =

2 1 2 1( ) [ ( ) ]k T k k k ky AD A AD r A Z r rc pk k d = +

k k T kz r A yd =

( )1 2 1 1( )

12

dondek T TP I D A AD A ADk k k

kkD z xk

=

=

6. Calcular los tamaos de los pasos para las variables primal y dual.

min 1, min : 1, ...,0

kxk i i np k kx xi i

= =

<

min 1, min : 1, ...,0

kzk i i nd k kz zi i

= =

<

7. Actualizar las variables Primal y Dual:

1

1

1

k k k kp

k k k kd

k k k kd

x x x

y y y

z z z

+

+

+

= +

= + = +

0.95 0.99995donde

8. Reducir el parmetro de barrera:

1 ( )k T kk k z xn

+ =

donde n es el nmero de variables primales.

9. Volver al paso 3.

3. APLICACIN DE LOS MTODOS DE SOLUCIN DE PL A PROBLEMAS CON PTIMOS ALTERNATIVOS.

Entre los mtodos tradicionales para resolver problemas de programacin lineal el ms utilizado es el mtodo simplex y sus variantes. Cuando se solucionan problemas de PL por medio del mtodo Simplex, la solucin encontrada es un punto extremo, siempre y cuando exista el ptimo.

El mtodo de Puntos Interiores aunque es una tcnica nueva, ha dado buenos resultados, tanto as, que en los ltimos tiempos se ha incrementado el estudio de este mtodo.

La solucin que encuentra este mtodo en problemas con ptimos alternativos, puede ser un punto extremo o un punto dentro del conjunto de soluciones ptimas dependiendo del punto inicial. Normalmente la solucin encontrada es un punto diferente al extremo.

3.1 Ejemplo

Para exponer las diferentes soluciones que se tienen cuando se aplican los mtodos anteriores a problemas con ptimos alternativos, se plantear el siguiente ejemplo:

Una empresa fabrica 2 tipos de fertilizantes, llamados fertilizantes A y B. Se emplean 3 tipos de materia prima en la preparacin de estos fertilizantes como se muestra a continuacin [1]:

Tabla 1. Datos del ejemplo.Toneladas de materia

prima necesarias para

preparar 1 tonelada de

Cantidad mensual mxima de materia

prima disponibleMateria prima

Fertilizantestipo A

Fertilizantes tipo B Toneladas

____________________________1. Las notas de pie de pgina debern estar en la pgina donde se citan. Letra Times New Roman de 8 puntos

3


1 2 1 15002 1 1 12003 1 0 500

Lucro por tonelada $ 20 $ 10

El modelo matemtico de este problema es:

max ( ) 20 101 2.

2 1500 (1)1 2 1200 (2)1 2 500 (3)1

0 ; 01 2

z x x x

s a

x x

x x

x

x x

= +

+

+

La representacin grfica del espacio de soluciones se muestra en la fig. 2.

Figura 2 Espacio de soluciones.

El segmento de recta resaltado es el conjunto de soluciones ptimas del problema, es decir todos los puntos sobre este segmento tienen el mismo valor para la funcin objetivo.

La solucin x* del problema por el mtodo Simplex, es:

( ) 15000

500 15002

z x

x

x

=

=

=

Esta solucin corresponde al vrtice resaltado en la fig. 2.

La solucin del problema usando el mtodo de Puntos Interiores Barrera Logartmica Primal-Dual es:

( ) 15000

396.2926 1707.41442

z x

x

x

=

=

=

La fig. 3 muestra el punto inicial calculado por el algoritmo y el camino seguido hasta encontrar el ptimo del problema.

Ntese que la solucin no corresponde a un punto extremo del conjunto de soluciones.

Figura 3 Solucin mediante puntos interiores.Se puede observar que el mtodo de puntos interiores da la posibilidad de tener respuestas diferentes a los vrtices del problema donde las restricciones se encuentran activas implicando el consumo total de los recursos.

Cuando un problema de programacin lineal es resuelto por el mtodo simplex, la solucin es un vrtice del conjunto factible de soluciones. Esto implica que las restricciones que forman ese vrtice estn activas (su relacin es de igualdad). Para el caso del ejemplo mostrado, las soluciones posibles encontradas con el mtodo simplex, podran ser:

. 500 ; 5001 2

. 300 ; 9001 2

a x x

b x x

= =

= =

La solucin (a) corresponde al caso donde las restricciones (1) y (3) se encuentran activas, es decir, la cantidad mensual de materia prima disponible 1 y 3 (Tabla 1) se agotan totalmente. En la solucin (b) las restricciones (1) y (2) se encuentran activas, es decir, la cantidad mensual de materia prima 1 y 2 se agotan totalmente. De lo anterior se puede concluir que la materia prima 1 es indispensable y debe gastarse totalmente. Las materias primas 2 y 3 pueden ser manejadas de tal manera que se utilice una y se conserve la otra, o viceversa.

Se pretende por lo tanto, modificar el algoritmo de Puntos Interiores de Barrera Logartmica Primal-Dual con el fin de que la respuesta obtenida persiga un objetivo adicional al de obtener el ptimo del problema.

Este objetivo adicional est directamente relacionado con las restricciones del problema, puesto que si existen

4


ptimos alternativos, se pueden introducir elementos adicionales que permitan manipular de forma adecuada los recursos asociados a cada una de dichas restricciones.

4. MODIFICACIN AL ALGORITMO DE PUNTOS INTERIORES BARRERA LOGARTMICA PRIMAL-DUAL PARA PROBLEMAS CON PTIMOS ALTERNATIVOS.

En el algoritmo mostrado en la seccin 2.1 se observa que la direccin de bsqueda del mtodo est dado por:

k k k kx x x xctr obj fac = + +

2 1 2 1( ) [ ( ) ]k T k k k ky AD A AD r A Z r rc pk k d = +

k k T kz r A yd =

Donde y y z son las direcciones de bsqueda dual. x es la direccin de bsqueda primal y esta compuesta por tres componentes: xctr direccin central, xobj direccin objetivo y xfac direccin factible. Esta direccin de bsqueda nos permite obtener una variacin directa sobre la solucin del problema primal.

Las direcciones central y factible tienen como objetivo encontrar un punto factible cerca del centro del politope primal, estas direcciones inicialmente son predominantes debido a que los parmetros y rp son grandes.

Cuando se encuentra un punto factible, rp tiende a cero y la direccin objetivo es la que domina.

Debido a que el punto inicial dado en el algoritmo se encuentra normalmente en la regin factible, la direccin objetivo predomina desde el inicio del proceso de bsqueda, por lo tanto, se propone modificar dicha direccin de tal forma que persiga un segundo objetivo dado por las restricciones.

La modificacin en dicha direccin est directamente relacionada con los gradientes de las restricciones que se pretenden favorecer; por tanto la direccin objetivo tendr la siguiente forma:

1 1k kx D P D c Ki Riobj k k i = +

donde:

i : es el numero de restricciones que se incluirn para el ajuste de la direccin objetivo.

Ki : es un factor entre cero y uno, que indica el porcentaje de contribucin del parmetro de barrera.

: es el parmetro de barrera, debe incluirse debido a que la direccin dada por el gradiente debe disminuir durante el proceso.

Ri : Es el gradiente de las restricciones que se pretenden favorecer. 4.1 Ejemplo de aplicacin

Se aplicar la metodologa expuesta al ejemplo tratado en la seccin 3.1. Para realizar la comparacin se parte del resultado mostrado en la fig. 3.

( ) 15000

396.2926 1707.41442

z x

x

x

=

=

=

En este, los recursos de las restriccin 1 fueron agotados debido a que sobre esta recta se encuentra el espacio de soluciones, en cuanto a las restricciones 2 y 3, cuentan con recursos debido a que la solucin obtenida no activa dichas restricciones.

Se pretende repartir los recursos de las restricciones 2 y 3 de tal forma que la solucin siga siendo ptima.

Caso 1: Conservar una buena cantidad de la materia prima 2, y a la vez, mantener disponible en bajo porcentaje la materia prima 3. La direccin positiva del gradiente de la restriccin 2 indica gastar recursos mientras que el gradiente negativo implica ahorro de dicho recurso. La proporcin que se desee conservar est sujeto a otro tipo de restricciones que pueden ser adicionadas al problema. Para este caso solo se utilizar informacin de la restriccin 2. Se fijar el factor K igual a 0.6 que indica una contribucin del 60% del parmetro de barrera sobre la direccin de ajuste. Este valor debe ser sintonizado de acuerdo al objetivo que se persigue.


5


Figura 4 Ejemplo de aplicacin caso 1.

( ) 14997.54

479.9680 1539.81852

z x

x

x

=

=

=

Caso 2: Conservar una buena cantidad de la materia prima 3, y a la vez, mantener disponible en bajo porcentaje la materia prima 2. La direccin del gradiente de la restriccin 3 indica gastar recursos mientras que el gradiente negativo implica ahorro de dicho recurso.

Para este ejemplo se incluir informacin de ambas restricciones ( 2 , 3 ) para ver el comportamiento de la direccin de bsqueda. Se fijar el factor K1 en 0.6 y K2 en 1 para los porcentajes de contribucin del parmetro de barrera sobre la direccin de ajuste.

Figura 5 Ejemplo de aplicacin caso 2.

( ) 15000

339.2772 1821.43032

z x

x

x

=

=

=

Lo anterior muestra que si se considera el gradiente de las restricciones que acotan el espacio de soluciones, de tal forma que contribuyan al cambio de la direccin

objetivo, se obtendr una convergencia ms exacta del mtodo.

5. CONCLUSIONES Y RECOMENDACIONES

Algunos problemas de Programacin Lineal tienen la caracterstica de tener ms de una solucin ptima. Esta propiedad puede ser utilizada con la finalidad de escoger entre ese nmero infinito de soluciones una que sea mejor que las otras respecto a un propsito adicional.

El mtodo de Puntos Interiores obtiene soluciones diferentes a los puntos extremos cuando existen ptimos alternativos, esta propiedad me permite explorar una infinidad de posibles soluciones a las cuales no tenia acceso mediante las metodologas tradicionales.

El mtodo de Puntos Interiores Primal-Dual presenta la particularidad que siempre intenta encontrar un punto factible del problema que se encuentra ubicado en el centro del politope y desde all realiza una bsqueda del ptimo actualizando las variables del problema. Este comportamiento permite que sea posible desarrollar algoritmos que mejoren el proceso de bsqueda ya sea para volverlo ms eficiente o que tenga un objetivo adicional.

Una modificacin posible en el algoritmo consiste en la variacin de la direccin objetivo del vector de bsqueda primal, pues durante el proceso de evolucin del algoritmo predomina sobre las direcciones central y factible.

El gradiente de las restricciones del problema que acotan el espacio de soluciones, permiten ajustar de manera directa la direccin objetivo del vector de bsqueda primal, de tal forma que considerando aspectos adicionales al problema se obtenga una solucin igualmente ptima.

Para modificar la direccin objetivo de bsqueda primal, es necesario multiplicar por el valor de k a los gradientes de las restricciones por que en el punto de solucin k ser cero y no se afectaran las condiciones de optimalidad.

La contribucin del parmetro de barrera en la modificacin de dicha direccin, debe sintonizarse de acuerdo al problema, de forma que al momento de modificar la direccin de bsqueda solo experimente regiones que correspondan a la del problema original.

BIBLIOGRAFA

[1] GALLEGO, Ramn A., Escobar Antonio H., Romero Rubn A. Optimizacin en Sistemas Elctricos I.

6


Programacin Lineal, Primera edicin, Universidad Tecnolgica de Pereira, Pereira, 2003.

[2] BRONSON, Richard. Investigacin de Operaciones, Mc Graw Hill, Mxico 1996.

[3] CASTILLO, Enrique, Conejo Antonio, Pedregal Pablo, Garca Ricardo, Alguacil Natalia. Formulacin y Resolucin de Modelos de Programacin Matemtica en Ingeniera y Ciencia. Febrero, 2002.

[4] RIDER, Marcos J. Mtodo de Puntos Interiores para Optimizacin en Sistemas de Potencia. Universidad Tecnolgica de Pereira, Pereira 2004.

[5] S.J. WRIGHT, Primal-Dual Interior Point Methods. SIAM, Philadelphia, PA, 1997.

[6] S. MEHROTRA, On the implementation of a primal-dual interior point method, SIAM Journal on optimization, 1992.

[7] C.C. GONZAGA, Path following methods for linear programming, SIAM Review, vol 34, 1992.

[8] QUINTANA, V.H., Torres G.L. and Medina Palomo J., Interior point methods and their applications to power systems: A classification of publications and software codes, IEEE transactions Power Systems, vol 15, No. 1, Febrero 2000.


7

MTODOS DE PUNTOS INTERIORES APLICADO A PROBLEMAS DE PROGRAMACIN LINEAL CON PTIMOS ALTERNATIVOSRESUMENPALABRAS CLAVES: Direcciones de Bsqueda, Mtodo de Barrera Logartmica, ptimos Alternativos, Programacin Lineal, Puntos Interiores.ABSTRACTOSCAR GOMEZ CARMONAIngeniero ElectricistaLUIS ALFONSO GALLEGO.Ingeniero ElectricistaLINA PAOLA GARCES N.Ingeniera Electricista1. INTRODUCCIN2. METODO DE PUNTOS INTERIORES3. APLICACIN DE LOS MTODOS DE SOLUCIN DE PL A PROBLEMAS CON PTIMOS ALTERNATIVOS.4. MODIFICACIN AL ALGORITMO DE PUNTOS INTERIORES BARRERA LOGARTMICA PRIMAL-DUAL PARA PROBLEMAS CON PTIMOS ALTERNATIVOS.5. CONCLUSIONES Y RECOMENDACIONESBIBLIOGRAFA

mÉtodos de puntos interiores aplicado a problemas de programaciÓn lineal con Óptimos alternativos

Documents