Investigación de operaciones

Introducción a la
programación lineal
E

l desarrollo de la programación lineal ha sido clasificado como uno de los avances cien­

tíficos más importantes de mediados del siglo xx, y estamos de acuerdo con esta aseve­

ració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ñías onegocios,

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 ma­
nejar? 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 resumeu verbal puede permitirle elaborar una
idea. Expresado en forma breve, el tipo más común de aplicación abarca el problema generalde asignar de la mejor manera posible --es decir, de foÍlna óptima- recursos limitados a ac­

tividades que compiten entre sí por ellos. Con más precisión, este problema consiste en ele­

gir el nivel de ciertas actividades que compiten por recursos escasos necesarios para realizar­
las. Después, los niveles de actividad elegidos dictan la cantidad de recursos que consumirá
cada una deellas. La variedad de situaciones 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ñode una terapia de radiación, etc. No obstante, el ingre­
diente 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 ad­
jetivo lineal significa que todas las funciones matemáticas del modelo deben ser funciones
lineales. En estecaso, la palabra programación no se refiere aquí a términos computaciona­
les; en esencia es sinónimo de planeación. Por lo tanto, la programación lineal involucra la
planeación de las actividades para obtener un resultado óptimo; esto es, el resultado que me­
jor alcance la meta especificada -de acuerdo con el modelo matemático- entre todas las
alternativas factibles.
Aunque la asignación derecursos a las actividades es la aplicación más frecuente, 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, los problemas de programación lineal y
sus modelos con frecuencia son llamados sólo programas lineales.)Aún más, se dispone de
25

26

CAPíTULO 3

INTRODUCCiÓN A LA PROGRAMACiÓN LINEAL

un procedimiento de solució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 efec­
to de la programación lineal en las décadas recientes.
Por su gran importancia, hemos dedicado a la programación lineal éste ylos siguientes
seis capítulos. Después de presentar aquí las características generales de programación li­
neal, los capítulos 4 y 5 se dedican al método símplex. El capítulo 6 analiza los problemas
de programación lineal después de la aplicación inicial del método símplex. El capítulo 7
examina varias extensiones del método símplex ampliamente usadas e introduce el algorit­
mo de punto...