Tests de eficiencia en programación lineal multiobjetivo para caras incidentes en un vértice degenerado
Editorial: Universidad de Murcia. Departamento de Estadística e Investigación Operativa
ISBN: 978-84-691-8159-1
Ano de publicación: 2009
Congreso: Congreso Nacional de Estadística e Investigación Operativa (31. 2009. Murcia)
Tipo: Achega congreso
Resumo
En este trabajo presentamos diversos tests de eciencia para las caras de un problema de programacion lineal multiobjetivo (MOLP) que incidan en un vertice degenerado conocido. Este tipo de tests tienen una gran importancia practica para el MOLP dado que: a) pueden ser particularizados para vertices no degenerados (adoptando una forma mas sencilla) y, por tanto, son aplicables cualquiera que sea el vertice sobre el que incida la cara, b) su utilizacion requiere menor esfuerzo computacional que los tests generales de eciencia para caras que no tienen en cuenta los vertices sobre los que estas inciden y c) constituyen la piedra angular de los algoritmos generadores de soluciones ecientes de tipo local (basados en busquedas a traves de vertices ecientes). Los tests que aqu se proponen identican las caras bajo estudio a traves de su descriptor maximal y pueden ser considerados como una generalizacion de la caracterizacion de eciencia de Evans-Steuer para vertices degenerados.