Programacion lineal entera. El problema knapsack

Abstract

Se realiza una revisión crítica de los métodos de resolución de problemas lineales enteros y en particular del problema Knapsack. Se proponen dos algoritmos de emimevación implícita para el problema Knapsack y otros dos para problemas lineales enteros acotados. En todos ellos la emimeración se realiza de forma lexicográficamente ordenada proporcionándose un algoritmo que obtiene la solución admisible lexicográficamente máxima. Las experiencias computacionales realizadas con los algoritmos que resuelven el problema Knapsack muestran que uno de los aquí propuestos es mas eficiente que los hasta ahora empleados.