Metodo Gomory

CAPÍTULO 3. PROBLEMAS LINEALES ESPECIALES.

Se analizan en este capítulo problemas de programación lineal con una estructura especial. En primer lugar se estudian problemas en variables enteras, en los que se requiere que algunas o todas las variables de decisión del problema sean enteras. Seguidamente, se estudia el problema de transporte y el de asignación viéndose, para todos ellos, algunosde los métodos que existen para su resolución.

1.- Programación Entera.
En muchos casos prácticos las soluciones no enteras de problemas de programación lineal no tienen sentido. Estudiamos a continuación problemas de programación lineal en los que algunas o todas las variables del problema deben tomar valores enteros. El primero de los casos se denomina problema entero general o puro y elsegundo problema entero mixto. La formulación de los mismos es la siguiente: • Problema entero general: Max ct x s.a A x = b x≥0 x∈Z • Problema entero mixto: Max ct x s.a A x = b x≥0 xk ∈ Z, k ∈ {1, 2, ..., n} en el que sólo algunas de las variables del problema deben ser enteras.

R. Caballero, T. Gómez, M. González, M. Hernández, F. Miguel, J. Molina, M.M. Muñoz, L. Rey, F. Ruiz

ProgramaciónMatemática para Economistas

Cuando el conjunto de oportunidades está acotado, la resolución de estos problemas puede ser más fácil que en el caso general, ya que al ser el número de soluciones enteras factibles finito, bastaría con evaluar el objetivo en cada una de ellas y escoger la que dé mayor valor para el objetivo. Sin embargo, si el número de soluciones enteras factibles es grande,puede que no sea posible llevar a cabo dicha comparación. Existen numerosos métodos para resolver este tipo de problemas. En general, todos ellos comienzan resolviendo el problema sin tener en cuenta que algunas o todas las variables del problema deben ser enteras, de manera que si la solución obtenida es entera, esa será la solución del problema entero. En caso contrario, se podría considerar comoóptimo del problema en variables enteras, aquella solución factible resultante de redondear la solución obtenida, pero, en ese caso, podríamos dar una solución no factible o una solución factible no óptima. Se hace necesaria, por tanto, la aplicación de métodos específicos para resolver este tipo de problemas. Los dos métodos más representativos son el “método de los planos de corte de Gomory” y el“método de ramificación y acotación” (branch and bound). A continuación analizamos ambos métodos. 1.1.- Método de planos de corte de Gomory. En primer lugar, hemos de resolver el problema de manera “tradicional”, es decir sin tener en cuenta que algunas o todas las variables del problema deben ser enteras. Si la solución obtenida, x*, es entera, ésa será la solución a nuestro problema original. Encaso contrario se construye un PLANO DE CORTE, un hiperplano αtx = β, que divide el conjunto de oportunidades, X, en dos subconjuntos. Uno de ellos contiene la solución no entera x* y el otro el conjunto de soluciones enteras del problema. A partir de una solución no entera se van construyendo planos de corte, de tal forma que los cortes asociados a los mismos generan de forma iterada la soluciónentera buscada, si existe. Para ello se añade a las restricciones que definen el conjunto de oportunidades, restricciones de desigualdad αtx ≤ β que verifican todas las soluciones enteras del problema y elimina del conjunto de oportunidades algunas de las no enteras. A) Caso general: Todas las componentes del vector solución han de ser enteras: Definición 1. Dado un número real, k, se define parteentera de k, [k], al entero más próximo a k que verifique [k] ≤ k. Además, k = [k] + f , donde f es la parte fraccionaria de k, f ∈ [0, 1) Dado el problema: Max ct x
R. Caballero, T. Gómez, M. González, M. Hernández, F. Miguel, J. Molina, M.M. Muñoz, L. Rey, F. Ruiz

Programación Matemática para Economistas

s.a A x = b x≥0 x∈Z resolvemos: Max ct x s.a A x = b x≥0 Si la solución...