Una introduccion al metodo del escalado af´in para programacion lineal

Description
Una introduccion al metodo del escalado af´in para programacion lineal

Please download to get full document.

View again

of 51
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Software

Publish on:

Views: 8 | Pages: 51

Extension: PDF | Download: 0

Share
Tags
Transcript
  UNA INTRODUCCI´ON AL M´ETODO DEL ESCALADOAF´IN PARA PROGRAMACI´ON LINEALJordi CastroStatistics & Operations Research Dept.UPCDATE 2/2000DR 2000/02  Una introducci´on al m´etodo del escaladoaf´ın para programaci´on lineal Jordi CastroDept. d’Estad´ıstica i Investigaci´o OperativaUniversitat Polit`ecnica de CatalunyaPau Gargallo 5, 08028 Barcelona Abstract:  El m´etodo del escalado af´ın fue el primero de los algoritmos denominados de punto interior para la soluci´on de problemas de programaci´on lineal. A pesar de que puede ser in-troducido mediante sencillos razonamientos geom´etricos, los aspectos m´as te´oricos de dicho algoritmo (como la demostraci´on de su convergencia) suelen ser m´as sutiles que los de m´etodos alternativos. Este hecho ha motivado que la mayor´ıa de textos bien presenten el m´etodo de forma muy superficial, bien reduzcan su exposici´on a la demostraci´on de una lista de teoremas  y proposiciones. En este trabajo, de car´acter principalmente docente, se ha pretendido compen-sar ambas carencias, de forma que, manteniendo el rigor, la presentaci´on sea adecuada tanto  para estudios de Ingenier´ıa como de Matem´aticas. Se incluye un apartado con una serie de  problemas resueltos sobre el tema, entre los que aparece una implementaci´on del algoritmo enel lenguaje Matlab. Esta implementaci´on se utiliza para solucionar un problema de ingenier´ıa de pocas variables, el cual se propone como ejercicio pr´actico a realizar. Tambi´en se presenta una comparativa computacional entre una implementaci´on eficiente del m´etodo del escalado af´ın y una del algoritmo del s´ımplex en la soluci´on de un total de 90 problemas est´andar de  programaci´on lineal. Los resultados obtenidos ratifican la eficiencia del algoritmo del escalado af´ın. An introduction to the affine scaling algorithm for linear programming.Keywords:  Algoritmo de escalado af´ın, M´etodos de punto interior, Programaci´on lineal. Clasificaci´on AMS:  90C05, 90C06. 1. Introducci´on Los m´etodos de punto interior han sido utilizados durante los ´ultimos a˜nos con gran ´exitopara solucionar problemas de programaci´on lineal. Este ´exito ha provocado que actualmentese consideren una alternativa m´as efectiva que el m´etodo del s´ımplex para una gran variedadde problemas lineales. En este documento vamos a desarrollar uno de estos m´etodos: el delescalado af´ın.Este m´etodo fue el primero de los denominados de punto interior, y data del 1967 (Dikin(1967)), aunque no fue conocido en Occidente hasta dos d´ecadas m´as tarde. En la actuali-dad existen ya diversos textos que describen dicho algoritmo. La mayor´ıa de ellos, sin em-bargo, no realizan una presentaci´on que balancee los aspectos te´oricos con los m´as intuititivosy geom´etricos del algoritmo. As´ı, por ejemplo, mientras las obras de Arbel (1993) y Vanderbei(1996) realizan una presentaci´on de car´acter muy introductorio, en Tsuchiya (1996) la expo-sici´on se reduce principalmente a un conjunto de teoremas y proposiciones. Algunos textos,como Bertsimas y Tsitsiklis (1997), s´ı realizan el esfuerzo de presentar ambos aspectos, aunque,en este caso, la presentaci´on se centra en la versi´on del algoritmo del escalado af´ın denominadade paso corto, la cual ha mostrado ser la menos eficiente. A diferencia de estos textos, en estedocumento nos hemos centrado en la variante m´as eficiente —de paso largo—, presentando1  una demostraci´on de convergencia de la misma, sin olvidar los aspectos m´as geom´etricos delalgoritmo.Iniciaremos la exposici´on presentando la notaci´on que se utilizar´a (secci´on 2) e introdu- ciendo el problema lineal que pretendemos solucionar as´ı como los requisitos necesarios parael seguimiento de la exposici´on (secci´on 3). En la secci´on 4 se dar´a una visi´on global de las diferentes t´ecnicas de punto interior para programaci´on lineal. Acto seguido pasaremos a ex-poner en la secci´on 5 el m´etodo del escalado af´ın. Se realiza una presentaci´on constructivadel m´etodo, introduciendo en cada apartado sus diferentes etapas algor´ıtmicas. Se incluyendiversos ejemplos para ilustrar cada una de estas etapas. La secci´on 5 finaliza presentando losprincipales resultados sobre la convergencia del algoritmo, y una comparativa de su rendimientocomputacional respecto el algoritmo del s´ımplex. En la secci´on 6 se listan una serie de ejerci-cios propuestos, con sus respectivas soluciones. Durante la presentaci´on del m´etodo se hacendiversas referencias a estos ejercicios. En la secci´on 7 se sugiere un trabajo pr´actico donde debesolucionarse un problema de optimizaci´on real de peque˜na dimensi´on, utilizando una implemen- taci´on del algoritmo del escalado af´ın en el lenguaje Matlab. Se adjunta la soluci´on de dichotrabajo pr´actico. Las secciones 8 y 9 listan determinados aspectos del algoritmo no tratados enel documento y la bibliograf´ıa utilizada, respectivamente. 2. Notaci´on Se seguir´a el siguiente convenio a lo largo del documento: Los t´erminos con supra´ındice(como  x k ) har´an referencia a los diferentes puntos obtenidos por el algoritmo. Los t´erminosque tengan un  ∗ como supra´ındice (como  x ∗ ) denotar´an puntos ´optimos o puntos soluci´on. Las expresiones con sub´ındices (como  x i ) denotar´an componentes de vectores. Las letras griegas re-presentar´an escalares. Las letras may´usculas ( A ,  X  , etc.) ser´an matrices. Las letras min´usculaspodr´an representar tanto vectores ( x ) como dimensiones de vectores ( n ,  m ), y se distinguir´aseg´un el contexto. La letra  k  se reserva para indicar el n´umero de iteraci´on del algoritmo ( x k denotar´a, por tanto, la soluci´on que se tiene en la iteraci´o  k -´esima). La letra  e  denotar´a el vec-tor todo de unos  e  = (1  ,..., 1) T  . Se seguir´a la convenci´on de que los vectores ser´an vectores columna, y sus traspuestos vectores fila. 3. Presentaci´on del problema y requisitos necesarios El problema lineal que queremos solucionar (y que denotaremos por ( P  )) estar´a en formaest´andar:min x c T  x sujeto a  Ax  =  bx ≥ 0  , ( P  )donde  x  ∈  IR n es nuestro vector de variables,  A  ∈  IR m × n es la matriz de restricciones delproblema (donde  m < n ),  b  ∈  IR m el vector de t´erminos independientes, y  c  ∈  IR n el vectorde costes lineales. El conjunto de puntos  { x  |  Ax  =  b,x  ≥  0 }  se denomina  regi´on factible  (o  pol´ıtopo factible  ). Un punto que pertenece a este conjunto se denomina  punto factible  .Consideraremos las siguientes hip´otesis acerca de ( P  ). Hip´otesis 1.  La matriz  A  es de rango completo, esto es, rango( A )=  m . Hip´otesis 2.  El problema ( P  ) no es degenerado. Esto significa que todo punto  x  factible para( P  ) tiene como m´ınimo  m  componentes diferentes de 0.2  La interpretaci´on de no-degeneraci´on coincide con la del m´etodo del s´ımplex, donde sedenomina degenerada a una soluci´on b´asica  x  = [ x T B  x T N  ] T  ( x B  ∈  IR m ,  x N   ∈  IR n − m ,  x N   = 0, x B  ≥ 0) que tiene alguna componente de  x B  igual a 0. Esta hip´otesis facilita la presentaci´on y justificaci´on de determinadas etapas del m´etodo, as´ı como su convergencia.Entre los requisitos necesarios para desarrollar el m´etodo del escalado af´ın hallamos algunosconceptos b´asicos de teor´ıa de la dualidad. En primer lugar debemos saber que el problema( P  ) tiene asociado un problema dual ( D ), que tiene la siguiente formulaci´on:max y,z b T  y sujeto a  A T  y  +  z  =  cz  ≥ 0 , ( D )donde  y  ∈ IR m es el vector de variables duales, y  z  ∈ IR n es el vector denominado de holgurasduales. Al igual que para el problema primal, consideraremos que el dual no es degenerado(esta hip´otesis ser´a ´unicamente utilizada para demostrar la convergencia del m´etodo). Hip´otesis 3.  El problema ( D ) no es degenerado. Esto significa que todo punto ( y,z ) factiblepara ( D ) tiene como m´aximo  m  componentes de  z  iguales a 0.Las Hip´otesis 2 y 3 garantizan que los problemas primal y dual, si son factibles, tienen un ´unicopunto ´optimo.Las relaciones entre los problemas ( P  ) y ( D ) nos vienen dadas por los Teoremas de laDualidad D´ebil, Dualidad Fuerte, y de la Holgura Complementaria, que tambi´en ser´an utilizadosdurante la exposici´on: Teorema 1.  (Teorema de la Dualidad D´ebil) Si   x  es factible para el problema primal (P), e   y es factible para el problema dual (D), entonces  c T  x ≥ b T  y. Teorema 2.  (Teorema de la Dualidad Fuerte) Si el problema primal (P) tiene una soluci´on´optima   x ∗ , entonces el problema dual tambi´en tiene una soluci´on ´optima   y ∗ de forma que  c T  x ∗ =  b T  y ∗ . Teorema 3.  (Teorema de la Holgura Complementaria) Si   x  es factible para el problema primal (P), y el par   ( y,z )  es factible para el problema dual (D), entonces son ´optimos de sus respectivos  problemas si y solamente si  x i z i  = 0  para todo   i  = 1 ,...,n. La distancia  c T  x − b T  y  entre las funciones objetivo primal y dual se denominar´a  gap dual  . Enel ´optimo de ambos problemas, el gap dual es 0.En determinados puntos del desarrollo se utilizar´an tambi´en algunos conceptos de progra-maci´on no lineal, como las condiciones de optimalidad de problemas sujetos a restricciones deigualdad (m´etodo de los multiplicadores de Lagrange). Estos conceptos se usar´an para justificarformalmente determinados pasos del algoritmo. En particular, usaremos el siguiente resultado:3
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks