Resumen

Proponemos un nuevo método exacto para resolver problemas de mochila 0-1 de dos niveles. Un problema binivel modela un proceso de decisión jerárquico en el que intervienen dos decisores denominados líder y seguidor. En estos procesos, el líder toma su decisión considerando explícitamente la reacción del seguidor. Desde el punto de vista de la optimización, se trata de problemas en los que un subconjunto de variables debe ser la solución óptima de otro problema de optimización (paramétrico). Estos problemas tienen diversas aplicaciones en el ámbito del transporte y la gestión de ingresos, por ejemplo. Nuestro enfoque se basa en diferentes componentes. Describimos un procedimiento en tiempo polinómico para resolver la relajación lineal del problema de mochila 0-1 de dos niveles. Utilizando la información proporcionada por las soluciones generadas por este procedimiento, calculamos una solución factible (y, por tanto, un límite inferior) para el problema. Este límite se utiliza junto con un límite superior para reducir el tamaño del problema original. La solución entera óptima del problema original se calcula mediante programación dinámica. Presentamos experimentos computacionales que se comparan con los resultados obtenidos con otros enfoques de vanguardia. Los resultados demuestran la eficacia de nuestro método.

• Materias:Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:problema original, proceso de decisión jerárquico, nuevo método exacto, solución entera óptima, procedimiento en tiempo polinómico, enfoque, seguidor, líder, problemas, resultados
• Keywords:original problem, hierarchical decision process, new exact method, optimal integer solution, polynomial time procedure, approach, follower, leader, problems, results