investigacion de operaciones



Introducción Y Los Casos De Aplicación
En muchos problemas prácticos, las variables de decisión sólo tienen sentido real si su valor es entero. Por ejemplo, con frecuencia es necesario asignar a las actividades cantidades enteras de personas, máquinas o vehículos. Si el hecho de exigir valores enteros es la única diferencia que tiene un problema con la formulación de programación lineal,entonces se trata de un problema de programación entera (PE).
El modelo matemático para programación entera es sencillamente el modelo de programación lineal con la restricción adicional de que las variables deben tener valores en-teros. Si sólo es necesario que algunas
de las variables tengan valores enteros —y el supuesto de divisibilidad se cumple para el resto
Se realizan numerosas aplicaciones deprogramación entera que involucran una extensión directa de programación lineal en la que debe eliminarse el supuesto de divisibilidad. Sin embargo, existe otra área de aplicación que puede ser mucho más importante, como el problema que incluye cierto número de “decisiones tipo: sí o no”. En situaciones de este tipo, las únicas dos elecciones posibles son Sí y no.
Por ejemplo, ¿debe emprenderse unproyecto específico? ¿Debe hacerse cierta inversión fija? ¿Debe localizarse una instalación en un sitio en particular?

Las variables de este tipo se llaman binarias(o variables 0-1). En consecuencia, algunas veces se hace referencia a los problemas de programación entera que contienen sólo variables binarias como problemas de programación entera binaria (PEB) (o problemas 0-1 de programaciónentera).









Definición de modelos de programación entera y binaria

Puede parecer que la solución de problemas de PE es sencilla. Después de todo, los problemas de programación lineal se pueden resolver en forma eficiente, y la única diferencia es que la PE tiene muchas menos soluciones que considerar. En realidad, se garantiza que los problemas de PE pura con región factible acotada tengansólo un número finito de soluciones factibles. Desafortunadamente, existen dos falacias en esta línea de razonamiento. Una es que tener un número finito de soluciones factibles asegura que el problema se puede resolver. Los números󿬁nitos pueden ser astronómicamente grandes. Por ejemplo, considere el caso sencillo de problemas de PEB. Si se tienen n variables, existen 2n soluciones que considerar(algunas de las cuales se pueden descartar por violar las restricciones funcionales). En consecuencia, cada vez que n aumenta en 1, el número de soluciones se duplica. Este patrón se llama crecimiento exponencial de la dificultad del problema. Con n5 10, existen más de mil soluciones (1 024); con n5 20, son más de un millón; con n5 30 resultan más de mil millones, y así sucesivamente; en razón de ello,aun las computadoras más eficientes son incapaces de realizar una enumeración exhaustiva —que verifique la factibilidad de cada solución y, de ser factible, que calcule el valor de la función objetivo en problemas de PEB con unas cuantas docenas de variables, sin mencionar los problemas de PE general con el mismo número de variables enteras. Por fortuna, empezando con las ideas que sedescribirán en secciones subsecuentes, en la actualidad los mejores algoritmos de PE son ampliamente superiores al método de la numeración exhaustiva. La mejora en las dos décadas pasadas ha sido sorprendente. Los problemas PEB que requerían años de procesamiento para resolverse hace 20 años, en la actualidad pueden resolverse en segundos mediante el uso de paquetes de software comerciales (como, porejemplo, el paquete CPLEX). Este aumento dramático en la velocidad se debe al enorme progreso en tres áreas: mejoras significativas en los algoritmos PEB(así como en otros algoritmos de PE), mejoras sorprendentes en algoritmos de programación lineal muy utilizados en los algoritmos de programación entera y el notable incremento de la velocidad delas computadoras (entre las cuales se incluyen las de...