CAP3H 9E

3

C A P Í T U L O

Introducción a la programación lineal

E

l desarrollo de la programación lineal ha sido clasificado como uno de los avances científicos
más importantes de mediados del siglo xx, y estamos de acuerdo con esta aseveración. Su
efecto desde 1950 ha sido extraordinario. En la actualidad es una herramienta de uso normal que
ha ahorrado miles o millones de dólares a muchas compañíaso negocios, incluso empresas medianas, en los distintos países industrializados del mundo; su aplicación a otros sectores de la
sociedad se ha ampliado con rapidez. Una proporción muy grande de los programas científicos en
computadoras está dedicada al uso de la programación lineal. Se han escrito docenas de libros de
texto sobre esta materia y se cuentan por cientos los artículos publicados quedescriben aplicaciones importantes.
¿Cuál es la naturaleza de esta notable herramienta y qué tipos de problemas puede manejar? El
lector adquirirá una noción de este tema a medida que trabaje en los ejemplos que se presentarán
más adelante. Sin embargo, un resumen verbal puede permitirle elaborar una idea. Expresado en
forma breve, el tipo más común de aplicación abarca el problema general deasignar de la mejor
manera posible —es decir, de forma óptima— recursos limitados a actividades que compiten entre
sí por ellos. Con más precisión, este problema consiste en elegir el nivel de ciertas actividades que
compiten por recursos escasos necesarios para realizarlas. Después, los niveles de actividad que se
eligen dictan la cantidad de recursos que consumirá cada una de ellas. La variedad desituaciones a
las que se puede aplicar esta descripción es sin duda muy grande, ya que abarca desde la asignación
de instalaciones de producción a los productos hasta la asignación de los recursos nacionales a las
necesidades de un país; desde la selección de una cartera de inversiones hasta la selección de los
patrones de envío; desde la planeación agrícola hasta el diseño de una terapia deradiación, etc. No
obstante, el ingrediente común de todas estas situaciones es la necesidad de asignar recursos a las
actividades mediante la elección de los niveles de éstas.
La programación lineal utiliza un modelo matemático para describir el problema. El adjetivo
lineal significa que todas las funciones matemáticas del modelo deben ser funciones lineales. En
este caso, la palabra programación no serefiere aquí a términos computacionales; en esencia es
sinónimo de planeación. Por lo tanto, la programación lineal involucra la planeación de actividades para obtener un resultado óptimo; esto es, el resultado que mejor alcance la meta especificada
—de acuerdo con el modelo matemático— entre todas las alternativas factibles.
Aunque la asignación de recursos a las actividades es la aplicación másfrecuente, la programación lineal tiene muchas otras posibilidades. En realidad, cualquier problema cuyo modelo
matemático se ajuste al formato general del modelo de programación lineal, es un problema de
programación lineal. (Por esta razón, un problema de programación lineal y su modelo se denominan con frecuencia programa lineal, o incluso sólo PL.) Aún más, se dispone de un procedimiento
desolución muy eficiente llamado método símplex para resolver estos problemas lineales, incluso
los de gran tamaño. Éstas son algunas razones del tremendo efecto de la programación lineal en
las décadas recientes.
Debido a su gran importancia hemos dedicado a la programación lineal éste y los siguientes
seis capítulos. Después de presentar aquí las características generales de programación lineal,los
capítulos 4 y 5 se dedican al método símplex. El capítulo 6 analiza los problemas de programación

22

CAPÍTULO 3

INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL

lineal después de la aplicación inicial del método símplex. El capítulo 7 examina varias extensiones
muy empleadas de este método e introduce el algoritmo de punto interior que en ocasiones se usa
para resolver problemas de programación...