PROGRAMACION LINEAL

Solución de Problemas de Programación Lineal

• SOLUCIONES GRÁFICAS DE PROGRAMACIÓN LINEAL
• PANORAMA GENERAL DE OTROS MÉTODOS DE SOLUCIÓN PARA PROGRAMACIÓN LINEAL

Las decisiones operacionales con restricciones se han identificado y estructurado para su análisis desde hace varias décadas. En los años 30, W. W. Leontief desarrolló sus análisis económicos de entradas-salidas que estaban estructurados de manera similar al formato actual de la programación lineal. Durante los años 30 y 40, F. L. Hitchcock y T. C. Koopsmans desarrollaron un método para estructurar y resolver problemas de programación lineal del tipo de transporte. En 1947, George Dantzig desarrolló el método simplex de programación lineal. El método simplex de Dantzig fue probablemente el inicio del desarrollo del campo actual de laprogramación matemática.

Uno de los primeros métodos de solución usando programación lineal fue desarrollado en la administración de la producción y de las operaciones para resolver problemas de ubicación de las instalaciones. Sobre un mapa con las áreas geográficas examinados se construyó un modelo físico. Sobre cada ubicación propuesta se enhebró un hilo a través de una perforación en el mapa y se sujetó en el extremo del hilo un peso que era proporcional al costo total de la ubicación. Entonces se conectaron todos los hilos en la parte superior del mapa mediante un nudo corredizo. Cuando todos los pesos se dejaban caer simultáneamente, el nudo era llevado por la gravedad al punto de ubicación que minimizaba los costos totales. Aunque este método de “dejar caer el hilo” resulta arcaico en comparación con los estándares actuales, el tiempo y el esfuerzo utilizados en estos sistemas pioneros enfatiza la importancia que los gerentes le dan a la necesidad de tener técnicas de programación lineal para solución de problemas.

El procedimiento gráfico de solución muestra conceptualmente el proceso de la solución de la programación lineal para aquellos que no tengan experiencia con ella. Las soluciones gráficas tienen, por lo tanto, la intención de utilizarse como una herramienta de enseñanza para ayudar a comprender el proceso obtención de soluciones en la programación lineal. El método simplex, el de transporte y el de asignación son herramientas prácticas para la solución de la programación lineal.

SOLUCIONES GRÁFICAS DE PROGRAMACIÓN LINEAL

La tabla 6.4 da el esquema de los pasos en el método gráfico de solución de los problemas de programación lineal. Estos pasos se demuestran en el ejemplo 6.4, un problema de maximización, y

[pic 1]TABLA 6.4 PASOS EN EL MÉTODO GRÁFICO DE SOLUCIÓN 

Página 206  |  Inicio del artículo

[pic 2]Las empresas de mensajería, como Federal Express, pueden utilizar un sistema de cómputo basado en programación lineal para la selección de rutas de entrega que reduzcan costos y tiempos de recorrido (es decir, consolidando cargas de clientes, etcétera). 

en el ejemplo 6.5, un problema de minimization. Estudie ambos ejemplos y asegúrese de que comprende los fundamentos de estas soluciones: el trazo de las ecuaciones de las restricciones, la gra-ficación del espacio de la solución factible, el circulado de los puntos de solución y finalmente, la selección de la solución óptima.

Recuadro: Ocultar

EJEMPLO 6.4: SOLUCIÓN GRÁFICA DE LP-I

Para demostrar los pasos de solución gráfica de un problema de maximización utilizaremos el problema LP-1. Vuelva a leer LP-1 (ejemplo 6.1) y la tabla 6.4, antes de iniciar este ejemplo.

1. Formule las funciones objetivo y de las restricciones. Cuando en el ejemplo 6.3 se formu ló LP-1, las variables de decisión eran X1 = cantidad de sierras circulares mensuales a fabricar, y X2 = cantidad de sierras de mesa a fabricar por mes. Las funciones objetivo y de las restricciones eran:

Max Z = 900X1 + 600X2

2X1 + X2 ≤ 4,000 (fabricación—horas)

X1 + 2X2 ≤ 5,000 (ensamble—horas)

X1 + X2 ≤ 3,500 (mercado—sierras)

1. Dibuje una gráfica.
2. Trace las funciones de las restricciones.
3. Delinee el espacio de la solución factible.
4. Circule los puntos de solución potencial en el perímetro del espacio de la solución factible (vea la figura 6.3 de la página 208).

Observe que las restricciones se trazan tratando a cada restricción como una igualdad o una línea. En el caso de cada una de las líneas de las restricciones, hagamos X1 = 0 y resolvamos en función de X2. Después hagamos X2 = 0, y resolvamos en función de X,. Esto nos da dos juegos de valores para X1 y X2, es decir, dos puntos. Conecte cada par de puntos con una línea recta. Este proceso se repetirá para cada uno de los factores.

Página 207  |  Inicio del artículo

Note que, dado que las restricciones son de tipo ≤ todos los valores de X1 y X2deben quedar en el interior de todas las restricciones (hacia el origen). Los puntos D y E no son factibles, ya que ambos violan la primera restricción. Aunque cualquiera de los puntos que aparecen dentro del espacio de la solución factible satisface todas las restricciones, sólo los puntos A, B y C son candidatos para una solución óptima, porque ocurren en las intersecciones de restricciones o ejes y están en el perímetro exterior del espacio de la solución factible.

...