Análisis de redes, incluyendo PERT-CPM (I)

Los problemas de redes surgen en una gran variedad de situaciones. Las redes de transporte, eléctricas y de comunicaciones predominan en nuestra vida diaria. La representación de redes se utiliza ampliamente en
áreas tan diversas como producción, distribución, planeación de proyectos, localización de instalaciones, administración de recursos y planeación financiera,para nombrar sólo unos cuantos ejemplos. De hecho, una representación de redes proporcionan un panorama general tan poderoso y una ayuda conceptual para visualizar las relaciones entre componentes de los sistemas que se usa casi en todas las áreas científicas, sociales  económicas.

Uno de los mayores desarrollos recientes en investigación de operaciones ha sido el rápido avance tanto en la metodología como en la aplicación de los modelos de optimización redes. La aparición, en las décadas de 1970 y 1980, de algunos algoritmos ha tenido un impacto importante, al igual que las ideas en el área de ciencias de la computación sobre estructuras de datos y la manipulación eficiente de los mismos. En consecuencia, ahora se dispone de algoritmos y paquetes de computadora y se están usando en forma rutinaria para resolver problemas muy grandes que no se habrían podido manejar veinte años antes.

Conclusiones otros algoritmos para programación lineal

La técnica de la toca superior proporciona una forma simplificada del método símplex para aquella situación común en que muchas o todas las variables tienen cotas superiores explícitas Reduce en una gran proporción el esfuerzo computacional en problemas grandes.

El métodos símplex dual y la programación lineal paramétrica son en especial valiosos para el análisis de sensibilidad, aunque también pueden ser muy útiles en otros contextos.

Los paquetes de computación de programación matemática casi siempre incluyen estos tres procedimientos y se usan con frecuencia. Debido a que su estructura básica se apoya en el método símplex presentado en el capítulo 4, conservan la eficiencia computacional excepcional para manejar problemas grandes ocmo los que se describieron en la sección 4.8.

Se ha desarrollado algunos otros tipos de algoritmos de propósitos especiales que aprovechan la estructura especial de ciertos tipos de problemas de programación lineal (como los presentados en el capítulo 7). En la actualidad se lleva a cabo una intensa investigación en esta área.

El algoritmo de punto interior de Karmarkar marca un nuevo desarollo de programación lineal. Este algoritmo y sus variantes abren un nuevo camino como un enfoque poderoso para resolver con eficiencia algunos problemas muy grandes. 

Resumen y ejemplificación del algoritmo - Iteración I (VI)

Aunque las dos versiones de este ejemplo tienen nada más una restricción, el tener más ímplica sólo un cambio en el procedimiento (además del aumento en los cálculos). Si se tiene una sola restricción, significa que A tiene un solo renglón, de manera que el término (AA^T)^-1  en el paso 3 se obtiene tomando el reciproco del número obtenido del vector producto  (AA^T). Si se tienen restricciones funcionales múltiples, A tiene varios renglones y entonces el termino  (AA^T)^-1  quiere decir la inversa de la matriz obtenida con el producto  (AA^T).

Para concluir, es necesario hacer un comentario  que puede dar una mejor perspectiva del algoritmo. Para el ejemplo en extremo pequeño que se presentó, el algoritmo requiere un número relativamente grande de cálculos y después de muchas iteraciones obtiene sólo una aproximación de la solución óptima. Por el contrario, el procedimiento gráfico de la sección 3.1 encuentra de inmediato la solución óptima de la figura 9.3 y el método símplex requiere sólo una iteración rápida. Sin embargo no debe menospreciarse la eficiencia del algoritmo de punto interior. ESte algoritmo está diseñado para manejar problemas grandes que tienen muchos cientos o miles de restricciones funcionales. El método símplex realiza miles de interaciones en este tipo de problemas. Al obtener una solución en el interior de la región factible, el algoritmo de punto interior tienden a requerir un número mucho menor de iteraciones (aunque con mucho más trabajo por iteración) Así, como se dijo en la sección 4.9, los algoritmos de punto interior similares al que se presentó jugarán un papel importante en el futuro de programación líneal.

Resumen y ejemplificación del algoritmo - Iteración I (V)

La figura 9.8 muestra el progreso del algoritmo en el sistema de coordenadas x1 = x2 original antes de aumentar le problema. Los tres puntos (x1,x2) = (2,2), (2.5,3.5) y (2.08, 4.92), son las soluciones prueba para iniciar las iteraciones 1,2 y 3 respectivamente. Se dibujó una curva suave a través de estos tres puntos y se continuó para mostrar la trayectoria del algoritmo en iteraciones subsecuentes conforme se acerca a (x1,x2) = (0,8).

Ocurre que la restricción funcional para este ejemplo en particular es una desigualdad. Sin embargo, las restricciones en forma de igualdad no causen problema al algoritmo, ya que maneja la restricciones sólo después de ponerlas en la forma aumentada para convertirlas en igualdades, Ax = b. Para ilustrar esto, supóngase que el único cambio en el ejemplo es que las restricción x1 + x2 ≤ 8 se cambia a x1 + x2 =8. Entonces, la región factible en la figura 9.3 cambia y queda sólo como el segmento de recta entre (8,0) y (0,8). Dada cualquier solución prueba inicial en el interior (x1 > 0 y x2 > 0) de este segmento de recta, digamos (x1,x2) = (4,4), el algoritmo puede llevar a cabo los mismos cinco pasos dado en el resumen nada más con las dos variables y A= [1,1]. En cada iteración, el gradiente proyectado señala, a lo largo de este segmento, en la dirección de (0,8). Con α = 1/2,la iteración 1 lleva de (4,4) a (2,6), la iteración 2 de (2,6) a (1,7), etc. (El problema 27 pide al lector que verifique estos resultados.

Resumen y ejemplificación del algoritmo - Iteración I (IV)

Como hay muy poco que aprender con la repetición de estos cálculos para otras interaciones, no se haán más; pero se presenta en la figura 9.7 la región factible reconfigurada después de dar la nueva escala sobre la solución prueba que se acaba de obtener en la iteración 3. Cómo siempre, esta nueva escala coloca a la solución  prueba en (x1,x2,x3) = (1,1,1), quidistante de las fronteras de restricción: x1 = 0, x2=0, y x3= 0, Obsérvese en las figuras 9.5, 9.6 y 9.7 que la serie de iteraciones y las nuevas escalas tienen el defecto de *deslizar* la solución óptima hacia (1,1,1) mientras que las otras soluciones básicas factibles tienden a alejarse. Eventualmente, después de suficientes iteraciones, la solución óptima quedará muy cerca de (x1,x2,x3) = (0,1,0) después de dar la nueva escala, mientras que las otras soluciones básicas factibles estarán muy lejos del origen sobre los ejes x1 y x3. ES paso 5 de esta iteración conducirá a una solución en las coordenadas originales muy cerca de la solución óptima (x1,x2,x3)= (0,8,0).

Resumen y ejemplificación del algoritmo - Iteración I (III)

Paso 5: se calcula x = Dx como la solución prueba para la siguiente iteración (paso 1). (Si esta solución prueba casino cambia respecto a la anterior, entonces se dice que el algoritmo converge a una solución óptima y se detiene.)

Ahora se aplicará este resumen a la iteración 2 del ejemplo.

Resumen y ejemplificación del algoritmo - Iteración I (II)

Sea v el valor absoluto de la componente negativa de cp que tiene el mayor valor absoluto, entonces v=|2| = 2 en este caso. En consecuencia, en las coordenadas actuales, el algoritmo se mueve ahora de la solución prueba actual (x1,x2,x3) = (1,1,1) a la siguiente solución prueba,