Manual de Usuario de la clase TSimplex.
Contents
1. spx mensajeDeError end Ep SimSEE SimSEE p g 14 16 Depuraci n y funciones avanzadas procedure DumpSistemaToXLT archi string InfoAdicional string overload virtual Vuelca los datos contenidos en el simplex a un archivo Es til para verificar que una vez que se arm el problema este sea el problema deseado Al definir las cotas de una variable el simplex realiza un cambio de variable con respecto a la original donde si xi esta acotada por Xi xi E XL se representa como xi xi Xi con 0 xi lt fi Xt Es importante tener esto en cuenta a la hora de usar el m todo DumpSistemaToXLT ya que este imprime ar ne ar xt en la fila de las x_inf pero Xi t en la fila de las x_sup El formato de salida es el siguiente InfoAdicional Informaci n adicional que se haya incluido al llamar a DumpSistemaToXLT NEnteras nroEnteras Enteral1 Entera2 sass iEnteraNroEnteras nroEnteras es el n mero de variables enteras en el simplex Los valores Enterak indican el ndice de la columna original de la variable entera n mero k ivae VarAcoplada ResAcoplada Si hay variables enteras con acoples indican para cada ivae ndice de variable entera de O a nroEnteras 1 la variable y restricci n acopladas indicadas por su ndice de fila o columna al armar el simplex ent_varfijas N mero de variables cuyo valor haya sido fijado cnt_RestriccionesRedundantes N mero de restricciones que hay2. spx TSimplex Create_init 4 6 NIL NIL end Armado y acceso a la matriz function e k j integer NReal virtual Obtiene el valor del elemento de la matriz en la fila k y columna j Ejemplo spx TSimplex m12 NReal begin Obtenemos el valor de la matriz en la fila 1 columna 2 m12 spx e 1 2 end procedure pon_e k 3j integer x NReal virtual Fija en x el valor del elemento en la fila k y columna j de la matriz Ejemplo var spx TSimplex begin Fijamos el valor de la matriz en la fila 1 columna 2 a 10 spx pon_e 1 2 10 end procedure acum_e k j integer x NReal virtual Suma x al valor del elemento en la fila k y columna j Ejemplo var spx TSimplex begin Sumamos 10 al valor de la matriz en la fila 1 columna 2 spx acum_e 1 2 10 end procedure FijarRestriccionlgualdad kfila integer Declara a la restricci n en la fila kfila como de igualdad Por defecto todas las restricciones son de mayor o igual debi ndose especificar expl citamente cuales se deben considerar de igualdad Ejemplo E SimSEE SimSEE p g 11 16 var spx TSimplex begin Fijamos la restricci n en la fila 5 como de igualdad spx FijarRestriccionlgualdad 5 end Fijado de cotas para las variables de decisi n procedure cota_inf_set ivar integer vxinf NReal Fija la cota inferior de la variable ivar en vxinf Ejemplo var spx TSimplex begin Fijamos la cota inferior de
3. la variable 1 en 2 spx cota_inf_set 1 2 end procedure cota_sup_set ivar integer vxsup NReal Fija la cota superior de la variable ivar en vxsup Ejemplo var spx TSimplex begin Fijamos la cota superior de la variable 1 en 2 spx cota_inf set 1 2 end Resoluci n function resolver integer virtual Una vez armada la matriz con las ecuaciones y fijadas las cotas superiores inferiores de las variables correspondientes el m todo resolver resuelv l simplex Retorna 0 si encontr una soluci n ptima factible lt gt 0 si no En caso de no encontrar soluci n la variable mensajeDeError contiene una descripci n del problema encontrado Ejemplo var spx TSimplex E SimSEE SimSEE p g 12 16 z NReal begin Armado del simplex if spx resolver 0 Obtenemos el valor de la funci n objetivo tras resolver z spXx fval else raise Exception Create Error resolviendo simplex spx mensajeDeError end Acceso a resultados function xval ix integer NReal virtual Retorna el valor de una variable ix es la columna que ocupaba la variable cuando se arm el simplex Ejemplo var spx TSimplex x1 NReal begin Obtenemos el valor de la variable que cargamos en la posici n 1 xl spx xval 1 end function yval iy integer NReal virtual Retorna el valor de una restricci n iy es la fila que ocupaba la restricci n cuando se
4. se encuentra en la fila k si iix i k la variable se encuentra en la columna k iiy j guarda la posici n que ocupa la restricci n que originalmente estaba en la fila j Si iiy j m la variable se encuentra en la columna m si iiy j m la variable se encuentra en la fila m Se indexan desde 1 y el primer elemento no se utiliza Al iniciar a resolver iix i i y iiy j Ejemplo Si la variable que originalmente estaba en la columna 8 se encuentra en la fila 3 gt 11x 8 3 Si la restricci n que originalmente estaba en la fila 1 se encuentra en la columna 4 gt iiy 1 4 cnt_RestrIinfactibles integer Guarda la cantidad de restricciones que aun no son factibles en la iteraci n actual cnt_igualdades integer Guarda la cantidad de restricciones declaradas de igualdad mediante FijarRestriccionlgualdad al inicio de A ent_varfijas integer Guarda la cantidad de variables fijadas mediante FijarVariable ent_columnasFijadas Integer Guarda la cantidad de columnas fijadas con variables y restricciones cnt_RestriccionesRedundantes Integer Guarda la cantidad de restricciones declaradas como redundantes Hasta esta fila inclusive las restricciones se consideran resueltas flg_x array of shortint es 0 si no hay cota superior SimSEE SimSEE p g 8 1 16 Guardan informaci n sobre las cotas de las variables fle_x 1 1 si la variable actualmente en la columna i tiene cota superior pero es la inferio
5. _set 3 5 spx cota_sup_set 3 5 Vuelco el simplex al archivo ProblemaEjemplo x1t para verificar que el problema armado sea el que quer a spx DumpSistemaToXLT ProblemaEjemplo x1t intento resolver E SimSEE if spx resolver 0 then begin ok encontr soluci n SimSEE p g 5 16 Writeln Soluci n ptima encontrada spx fval obtiene el valor de z Writeln 9 z FloatToStrF spx fval ffGeneral 8 4 Writeln for i 1 to 3 do el valor de la variable spx xval i obtiene Writeln 9 spx fGetNombreVar i FloatToStrF spx xval i ffGeneral Writeln for i 1 to 3 do spx yval i obtiene 8 3 el valor de la restriccion i Writeln 9 spx fGetNombreRes i FloatToStrF spx yval i ffGeneral 8 3 Writeln Presione lt Enter gt para continuar Readln end else Error lanzamos la excepci n raise Exception Create Error resolviendo simplex spx mensajeDeError Liberamos la memoria usada por el objeto spx Free true end La salida en pantalla del programa ser Soluci n ptima encontrada z 10 1 Varl 0 7 Var2 6 Var3 3 6 Resl 8 8 Res2 0 Res3 0 Presione lt Enter gt para continuar 1 3 rbol de herencias TMatR Filas Create_Init filas columnas integer SimSEE SimSEE p g 6 16 TVectR e
6. an sido declaradas redundantes cnt_violacionesUsadas N mero de violaciones permitidas utilizadas ver permitirViolarBordeSupParaSatisfacerRestriccion violacionesPermitidas violacionesPermitidas Count Cantidad fichas de violaciones permitidas ires usada ViolacionA Usar nIvars ivars ires es el ndice de la fila original de la restricci n usada indica si se uso o no la violaci n 1ViolacionAUsar es el ndice de la pr xima variable a modificar la cota superior para resolver una restricci n nIvars es el tama o del arreglo con las variables cuya cota superior es violable ivars es el arreglo con las variables cuya cota superior es violable PEE EEEE o oe oe oe le le ole ol le ole ole ol oe E E ole oe le ale ole oe x nombre de la variable x_inf cota inferior 2 de la variable x_sup cota superior menos cota inferior de la variable Ft flg x banderas de las variables dan informaci n sobre las cotas de la variable es 0 si la variable no tiene cota superior es 1 si la variable tiene cota superior pero es la inferior la considerada actualmente es 1 si la variable tiene cota superior y es la considerada actualmente en el sistema es 2 si la variable fue fijada flg y banderas de las restricciones dan informaci n sobre el tipo de restricci n 0 para restricciones de gt 0 2 si es una 0 2 si es una 0 a la que le cambi el signo top Guardan el ndice original k cuando fue armada la matriz de la variable que est ahora en D
7. arm el simplex Ejemplo var spx TSimplex y2 NReal begin Obtenemos el valor de la restricci n que cargamos en la fila 2 y2 spx yval 2 end function xmult ix integer NReal virtual Retorna el valor del multiplicador de Lagrange de una variable ix es la columna que ocupaba la variable cuando se arm el simplex Ejemplo var E SimSEE SimSEE p g 13 16 spx TSimplex x1Mult NReal begin Obtenemos el valor del multiplicador de Lagrange de la variable que cargamos en la columna 1 x1Mult spx xmult 1 end function ymult iy integer NReal virtual Retorna el valor del multiplicador de Lagrange de una restricci n iy es la fila que ocupaba la restricci n cuando se arm el simplex Ejemplo spx TSimplex y2Mult NReal begin Obtenemos el valor del multiplicador de Lagrange de la restricci n que cargamos en la fila 2 ylMult spx ymult 2 end function fval NReal virtual Retorna el valor obtenido de la funci n objetivo fila nf de la matriz al resolver el simplex Tener en cuenta que el problema se debe escribir como problema de maximizaci n por lo que si nuestro problema original era de minimizaci n debemos considerar spx fval Ejemplo var spx TSimplex z NReal begin Armado del simplex if spx resolver 0 Obtenemos el valor de la funci n objetivo tras resolver z spXx fval else raise Exception Create Error resolviendo simplex
8. e esta cerca de estar lleno y tiene un volumen de aportes importante puede suceder que el vertimiento m ximo no nos permita vaciar lo suficiente el embalse Para solucionar esta situaci n se permite especificar que la cota de la variable Volumen Vertido del embalse puede violarse en caso de no poder resolver el problema por la restricci n de volumen m ximo almacenado del embalse con la cota fijada Para cada restricci n que se desee poder resolver de esta forma debe especificarse su n mero de fila y el n mero de columna de las variables a las que se les pueda violar la cota superior Estos n meros refieren a las posiciones que ocupaban la restricci n y las variables al armar el simplex Di SimSEE SimSEE p g 16 16 Destrucci n y liberaci n de recursos procedure Free borrarListaViolacionesPermitidas boolean Destruye el objeto simplex y libera la memoria que tuviera asignada El par metro borrarListaViolacionesPermitidas responde a una necesidad de implementaci n de la clase TMIPSimplex usando esta clase se debe pasar siempre con true Ejemplo var spx TSimplex begin spx Free true end
9. error encontrado al llamar el m todo resolver violacionesPermitidas TListaViolacionesPermitidasSimplex Di SimSEE SimSEE p g 7116 Contiene una lista de las violaciones a las cotas superiores que est n permitidas en caso de no encontrar una soluci n factible al problema actual Ver permitirViolarBordeSupParaSatisfacerRestriccion fGetNombreVar fGetNombreRes TFuncNombre Funciones para obtener el nombre de la variable y la restricci n en la posici n i al momento de armar la matriz top left array of smallint abs top i guarda el n mero de fila original de la restricci n o variable en la columna i abs left guarda el n mero de fila original de la restricci n o variable en la fila j Para determinar si se trata de una restricci n o una variable se utiliza el signo si su valor es negativo es una variable si es positivo es una restricci n Se indexan desde 1 y el primer elemento no se utiliza Al iniciar a resolver top i i y left j Ejemplo Si en la columna 8 se encuentra la restricci n que se hab a creado en la fila 2 gt top 8 2 Si en la fila 1 se encuentra la variable que se hab a creado en la columna 3 gt left 1 3 iix array of smallint gt 0 est n arriba lt 0 est n abajo iiy array of smallint lt 0 est n arriba gt 0 est n abajo 1ix 1 guarda la posici n que ocupa la variable que originalmente estaba en la columna i Si 11x 1 k la variable
10. i SimSEE SimSEE p g 15 16 left la posici n i Para las variables se guarda k y para las restricciones k Si la variable que est en la columna 8 hab a comenzado en la columna gt top 8 2 El arreglo left contiene lo propio para las filas Se indexan desde 1 A partir de aqu se muestra la matriz del simplex tal como la contiene el objeto Al final de cada fila se muestra que condici n debe cumplir el valor actual de la restricci n ti t rmino independiente para considerarse satisfecha En caso de que la fila este ocupada por una variable con cotas superior e inferior se muestran ambas condiciones Ejemplo var spx TSimplex z NReal begin Armado del simplex spx DumpSistemaToXLT ProblemaArmado xlt Verifico que el problema en el archivo sea el que realment deseo if spx resolver 0 Obtenemos el valor de la funci n objetivo tras resolver z Sspx fval else raise Exception Create Error resolviendo simplex spx mensajeDeError end procedure permitirViolarBordeSupParaSatisfacerRestriccion ires integer ivars TDAofNInt Declara que las variables en ivars pueden agrandar su cota superior si la restricci n ires no puede satisfacerse de otra manera Debe ser llamado con los ndices que ten an la restricci n y las variables cuando se cargaron en el Simplex Esto se hizo para poder resolver las restricciones de cota superior de volumen almacenado Si un embals
11. imizaci n y sus restricciones a restricciones de 0o0 gt 0 max z y 312 2103 my SimSEE SimSEE p g 4 16 ad 12 13 105 0 x14 124 53 xa1 33 29 gt 0 0x1x1 lt 12 6 lt 12 lt 6 52133 lt 5 Teniendo el problema en esta forma estamos en condiciones de armar el simplex procedure ejemplo var i Integer spx TSimplex begin Creamos un simplex vac o cuya matriz M tendr 3 restricciones la funci n objetivo 3 variables los t rminos independientes spx TSimplex Create_init 4 4 NIL NIL Cargamos la fila 1 pon_e k j x hace Mkj x spx pon_e 1 1 1 spx pon_el 2 DD spx pon_e 1 3 spx pon_e 1 spx nc 10 5 Cargamos la fila 2 y la declaramos como de igualdad spx pon_e 2 1 1 spx pon_e 2 2 1 spx pon_e 2 3 0 spx pon_e 2 spx nc 5 3 spx FijarRestriccionlgualdad 2 Cargamos la fila 3 spx pon_e 3 1 1 spx pon_e 3 2 0 spx pon_e 3 3 1 3 spx pon_e 3 spx nc 2 9 Cargamos la fila objetivo z spx pon_e spx nf 1 1 spx pon_e spx nf 2 3 spx pon_e spx nf 3 2 cota_inf_set i x fija la cota inferior de la variable en la posici n i a x sota_sup_set hace lo propio con la cota superior Cotas inferior y superior de x1 spx cota_inf_set 1 0 spx cota_sup_set 1 12 Cotas inferior y superior de x2 spx cota_inf_set 2 6 spx cota_sup_set 2 6 Cotas inferior y superior de x3 spx cota_inf
12. k j integer double pon_e k j integer x NReal acum_elk j integer x NReah 1 is TSimplex Create_init m n integer xfGetNombreVar xfGetNombreRes TFuncNombra FijarRestriccionlgualdaa kfila integer cota_inf_set ivar integer vxinf NReal cota_sup_set ivar integer vxsup NReal resolver int xval ix integer double yval iy integer double xmult ix integer double ymult iy integer double fval double DumpSistemaToXLT archi string InfoAdicional string permitirViolarBordeSupParaSatisfacerRestriccion ires integer ivars TDAofNInt Free borrarListaViolacionesPermitidas boolean 1 4 Propiedades x_inf x_sup TVectkR gt Create_Init ne integer e k integer pon_e k integer x NRea acum_e k integer x NReal Contienen informaci n sobre las cotas de las variables Si la variable Xi esta acotada por xd gt E ae Xini Xup A A SIFDEF GATILLOS_CAMBIOVAR ecnt_Gatillos integer gatillos_CambioVar array of smallint gatillos_no_procesados boolean SENDIF TODO SIFDEF CNT_COTAS ent_cotas_inf cnt_cotas_sup integer SENDIF Cuentan la cantidad de cotas inferiores y superiores que fueron fijadas mediante cota_inf_set y cota_sup_set mensajeDeError string Contiene en caso de haberlo un mensaje describiendo el
13. mp SimSEE SimSEE p g 1 16 Manual de Usuario de la clase TSimplex Proyecto SimSEE Archivo mu_TSimplex doc Autor Pablo Alfaro Fecha creaci n 11 11 2009 16 13 Fecha ltima revisi n 11 11 2009 16 17 Instituci n ADME Montevideo Uruguay Di SimSEE SimSEE p g 2 1 16 ndice General 1 TSIMPLEX AA a aaae AA e aaa aa Eea aAa aaa aeea EAEE 3 KSAM ohea olo INe eLo a PAn E A E A E E 3 RADA oTo lo de U E o Apea EE E S E onaridnisnccidncnridn sae 3 1 3 rb lide herencias ici ata 5 A RR O 6 1 5 EA AS 9 SimSEE SimSEE p g 3 16 1 TSimplex 1 1 Introducci n Esta clase permite modelar y resolver problemas de programaci n lineal del tipo max c X 5 0 Yx ec 0 Ax b gt 0 X e D D un subconjunto de R A real Es modelada sobre una matriz con nf filas y nc columnas donde la fila nf es la funci n objetivo c y la columna nc son los t rminos independientes dl Por defecto todas las restricciones son consideradas de gt debi ndose indicar expl citamente si se desea declarar una restricci n como de igualdad Se puede especificar adem s para cada variable en X cotas inferiores y superiores determinando el dominio D 1 2 Modo de Uso Explicaremos la forma de utilizar la clase mediante el siguiente problema de ejemplo mins yl 3x2 233 Sa xl x2 x3 2 10 5 xl x2 5 3 xl x3 2 9 Dd2311 lt 12 6 lt x2 lt 6 5213325 Comenzamos llevando su funci n objetivo a una de max
14. r la considerada actualmente flg_x i 1 si la variable actualmente en la columna i tiene cota superior y es la considerada actualmente flg_x i 2 si la variable actualmente en la columna i fue fijada Se indexa desde 1 flg_y array of shortint Guarda informaci n sobre los tipos de restricciones flg_y i 0 si la restricci n actualmente en la fila 1 es de gt 0 flg_y i 2 si la restricci n actualmente en la fila i es de 0 flg_y i 2 si la restricci n actualmente en la fila 1 es de 0 pero se le cambio el signo SimSEE SimSEE p g 9 1 16 1 5 M todos P blicos Creaci n y reserva de memoria 9 Constructor Create_init m n integer xfGetNombreVar xfGetNombreRes TFuncNombre virtual 9 Armado y acceso a la matriz 10 function e k j integer NReal virtual 10 procedure pon_e k j integer x NReal virtual 10 procedure acum_e k j integer x NReal virtual 10 procedure FijarRestriccionIgualdad kfila integer 10 Fijado de cotas para las variables de decisi n 11 procedure cota_inf_set ivar integer vxinf NReal 11 procedure cota_sup_set ivar integer vxsup NReal 11 Resoluci n 11 function resolver integer virtual 11 Acceso a resultados 12 function xval ix integer NReal virtual 12 function yval iy integer NReal virtual 12 function xmult ix integer NReal virtual 12 function ymult iy integer NReal virtual 13 function fval NReal virtual 13 Depuraci n y f
15. unciones avanzadas 14 procedure DumpSistemaToXLT archi string InfoAdicional string 14 procedure permitirViolarBordeSupParaSatisfacerRestriccion ires integer ivars TDAOfNInt 15 Destrucci n y liberaci n de recursos 16 procedure Free borrarListaViolacionesPermitidas boolean 16 Ejemplo de armado y resoluci n de un problema 16 Creaci n y reserva de memoria Constructor Create_init m n integer xfGetNombreVar xfGetNombreRes TFuncNombre virtual Crea un simplex con una matriz nula todos sus elementos con el valor 0 de m filas por n columnas Tener en cuenta que la funci n objetivo es una fila m s y los t rminos independientes son una columna mas por lo que si se quiere crear un simplex con 5 variables y 3 restricciones se debe pasar m 4 y n 6 Los par metros xfGetNombreVar y xfGetNombreRes permiten especificar funciones de objeto para obtener el nombre de las variables o restricciones Reciben un entero con el n mero de columna fila que ocupa la variable restricci n al armar el problema Si se pasan con el valor NIL las variables tendr n por defecto el nombre Vari y las restricciones Resj donde i y j son la columna y fila que ocupan al armar el problema Ejemplo procedure crearSimplex var spx TSimplex begin Creamos un simplex con 3 restricciones y la funci n objetivo y 5 variables y los t rminos independientes Utilizamos los nombres por defecto SimSEE SimSEE p g 10 16
Download Pdf Manuals
Related Search