Page 110 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 110
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
La programación lineal se planteó como un problema matemático desarrollado durante la Segun-
da Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y
aumentar las pérdidas del enemigo. Esta se mantuvo en secreto hasta 1947. En la posguerra, la
industria observó las bondades del método para reducir los gastos de sus operaciones diarias, por
lo cual originó que se usara en su planificación diaria.
El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestos
de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación nece-
saria para examinar todas las permutaciones (o fuerza bruta) a fin de seleccionar la mejor asignación
es inmensa (¡factorial de 70 o 70!); el número de posibles configuraciones excede al número de par-
tículas en el universo. Sin embargo, toma solo un momento encontrar la solución óptima mediante
el planteamiento del problema como programación lineal y la aplicación del algoritmo Simplex. La
teoría de la programación lineal reduce drásticamente el número de posibles soluciones óp-
timas que deben ser revisadas.
La programación lineal es el campo de la optimización matemática dedicado a maximizar o minimizar
(optimizar) una función lineal, denominada función objetivo, de tal modo que las variables de dicha
función estén sujetas a una serie de restricciones expresadas mediante un sistema de inecuacio-
nes también lineales. Los métodos más recurridos para resolver problemas de programación lineal
son algoritmos de pivote, en particular los algoritmos simplex.
Esta función objetivo representa cada uno de los elementos (recursos) que se desean maximizar o
minimizar, la cual puede ser expresada de la siguiente manera:
La función objetivo (Z) puede quedar expresada de acuerdo con lo que se desee realizar.
donde
C son contantes conocidas (costo por unidad de la variable x).
i
1
X representan cada uno de los elementos (recursos) que se desean satisfacer.
1
104
