Problema de la ruta más corta

Aunque al final de la sección se mencionan otras versiones del problema de la ruta más corta (incluyendo algunas para redes dirigidas), la atención se centrará en la siguiente versión sencilla. Considérese una red conexa y no dirigida con dos nodos especiales llamados origen y destinos. A cada una de las ligaduras (arcos no dirigidos) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) que va del origen al destino.

Se dispone de un algoritmo relativamente sencillo para este problema. La esencia de este procedimiento es que analiza toda la red a partir del origen, identificando sucesivamente la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen, quedando resuelto el problema en el momento de llegar al nodo destino. Primero se describirá el método y después se ejempleficara con la solución del problema de la rauta más corta que enfrenta la administración de Seervada Park en la sección 10.1

Terminología de redes (V)

Considérese un conjunto de n nodos (por ejemplo, n=5 nodos en la figura 10.2) sin arcos. Se puede entonces "hacer crecer" un "árbol" agregando un arco (o rama) a la vez de cierta manera. El primer arco puede ir a donde sea para conectar algún par de nodos. De ahí en adelante, cada arco nuevo debe agregarse entre un nodo que haya sido conectado a otros nodos y a un nuevo nodo no conectado. Si se agregan arcos de esta manera, se evita que se forme un ciclo y además se asegura que el número de nodos conexos es uno más que el número de arcos. Cada nuevo arco crea un árbol más grande, que es una red conexa (para algún subconjunto de n nodos) que no contiene ciclos no dirigidos. Una vez que se ha agregado el (n-1)-ésimo arco, el proceso se detiene porque el árbol resultante se expande (conecta) a todos los n nodos.

Este árbol se llama árbol de expansión, y es una red conexa para los n nodos que no contiene ciclo no dirigidos. Todo árbol de expansión tiene exactamente (n-1) arcos, ya que este es el mínimo número de arcos necesarios para tener una red conexa y el máximo número posible para que no hay ciclos no dirigidos.

La figura 10.3 muestra los cinco nodos y algunos de los arcos de la figura 10.2 para ilustrar este proceso de hacer crecer un árbol poniendo un arco (rama) a la vez, hasta que se obtiene un árbol de expansión. En cada etapa se tienen varias alternativas para el nuevo arco,por lo que la figura 10.3 muestra sólo una de las muchas formas de construir un árbol de expansión en este caso. Ahora bien, obsérvese cómo cada nuevo arco que se agrega satisface las condiciones especificadas en el párrafo anterior. Los árboles de expansión se estudiarán más a fondo en la sección 10.4.

Los árboles de expansión juegan un papel clave en el análisis de muchas redes. Por ejemplo, forman la base del problema del árbol de mínima expansión que se presenta en la sección 10.4. Otro ejemplo es que los árboles de expansión (factibles) corresponden a las soluciones básicas factibles en el método símplex de redes que se analiza en la sección 10.6.

Por último, será necesario introducir la terminología adicional sobre los flujos en redes. La cantidad máxima de flujo (quizá infinito) que puede circular en un arco dirigido se conoce como capacidad del arco. Entre los nodos, se pueden distinguir aquellos que son generadores de flujo, absorbedores netos o ninguno de los dos. Un nodo fuente (o nodo de origen) tiene la propiedad de que el flujo sale del nodo excede el flujo que entra a él. El caso inverso es un nodo demanda (o nodo destino), en el que el flujo que llega excede al que sale del nodo. Un nodo de trasbordo (o nodo intermedio)satisface la conservación del flujo, así el flujo que entra es igual al que sale.

Terminología de redes (IV) - Ciclo y nodos están conectados

Un ciclo es una trayectoria que comienza y termina en el mismo nodo. En una red dirigida un ciclo puede ser dirigido o no dirigido, según si la trayectoria en cuestión es dirigida o no dirigida. (como una trayectoria dirigida también es no dirigida, un ciclo dirigido es un ciclo no dirigido, pero en general el inverso no es cierto). Por ejemplo, en la figura 10.2, DE-ED es un ciclo dirigido. Por el contrario, AB-BC-AC es un ciclo no dirigido puesto que la dirección del arco AC es opuesta a la de lo arcos AB y BC. Por otro lado, AB-BC-AC es un ciclo no dirigido por que A→B→C→A es una trayectoria no dirigida. En la red no dirigida que se muestra en la figura 10.1 existen muchos ciclos, por ejemplo, OA-AB-BC-CO. DE cualquier forma, nótese que la definición de trayectoria (una sucesión de arcos distintos) elimina la posibilidad de retroceder al formar un ciclo. Por ejemplo, OB-BO en la figura 10.1 no califica como ciclo, porque OB y BO son dos etiquetas para el mismo arco (ligadura). Por otra parte, en la figura 10.2, DE-ED es un ciclo (dirigido) por que DE y ED son arcos distintos.

Se dice que dos nodos están conectados si la red contiene al menos una trayectoria no dirigida entre ellos. (nótese que no es necesario que la trayectoria sea dirigida aun cuando la red es dirigida) Una red conexa es una red en la que cada para de nodos está conectado. Entonces, la redes de las figuras 10.1 y 10.2 son ambas conexas. La última red no sería conexa si se eliminaran los arcos AD y CE.

Terminología de redes (III)

Cuando dos nodos no están unidos por un arco surge la pregunta natural de si están conectados por una serie de arcos. Una trayectoria entre dos nodos es una sucesión de arcos distintos que conectan estos nodos. Por ejemplo, una de las trayectorias que conectan a los nodos O y T en la figura 10.1 es la sucesión de arcos OB-BD-DT (O → B → D → T), y viceversa. Cuando algunos o todos los arcos de una red son arcos dirigidos, se hace la distinción entre trayectorias dirigidas y trayectorias no dirigidas. Una trayectoria dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el flujo del nodo i al nodo j a través e esta trayectoria sea factible. Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tienen) puede ser hacia o desde el nodo j. (obsérvese que una trayectoria dirigida también satisface la definición de trayectoria no dirigida, pero el inverso no se cumple.) Con frecuencia una trayectoria no dirigida tendrá algunos arcos dirigidos hacia el nodo j y otros desde él (es decir, hacia el nodo i). En las secciones 10.5 y 10.6 se verá que, tal vez de manera sorprendete, las trayectorias no dirigidas juegan un papel muy importante en el análisis de la redes dirigidas.

Para ilustrar estas definiciones, la figura 10.2 muestra una red dirigida común, la sucesión de arcos AB-BC-CE (A→ B→ C→ E) es una trayectoria dirigida del nodo A al nodo E, ya que el flujo hacia el nodo E a lo largo de toda esta trayectoria es factible. Por otro lado, BC-AC-AD (B→ C→ A→ D) no es una trayectoria dirigida al nodo B al nodo D, porque la dirección del arco AC es desde el nodo D (sobre su trayectoria). No obstante, B→ C→ A→ D es una trayectoria no dirigida del nodo B al nodo D. Como ejemplo de la relevancia des esta trayectoria no dirigida, supóngase que 2 unidades del flujo del nodo A al nodo C se habían asignado antes del arco AC. dada esta asignación previa, ahora es factible asignar un flujo más pequeño, D, ya que esto implica reducir el flujo sobre el arco AC en 1 unidad. La reducción de un flujo asignado antes "en la dirección equivocada" cuando se agrega un flujo a una trayectoria no dirigida será un concepto medular en las secciones 10.5 y 10.6

Terminología de redes (II)

Si el flujo a través de  un arco se permite en ambas direcciones (como en calles de dos sentidos), se dice que el arco es un arco no dirigido. Para ayudar a distinguir entre los dos tipos de arcos, con frecuencia se hará referencia a los arcos no dirigidos con el sugestivo nombre de ligadura.

Una red que tiene sólo arcos dirigidos se llama red dirigida. De igual manera, si todos sus arcos son no dirigidos, se dice que se trata de una red no dirigida. Una red con una mezcla de arcos dirigidos y no dirigidos (o incluso una con todos sus arcos no dirigidos) se puede convertir en una red dirigida, si se desea, sustituyendo cada arco no dirigido por un par de arcos dirigidos en direcciones opuestas.

Terminología de redes (I)

Se ha desarrollado una terminología relativamente extensa para describir los tipos de redes y sus componentes. Aunque se ha evitado en lo posible el uso del vocabulario específico, es necesario introducir un número considerable de términos que se usarán en este capítulo.  Se sugiere al lector que lea la sección completa una vez para entender las definiciones y panee después regresar a refrescar la memoria conforme se usen los términos en las secciones subsecuentes. Como ayuda, se resalta el nombre de cada términoen negritas en el punto en que se define.

Una gráfica consiste en un conjunto de puntos y un conjunto de líneas que unen ciertos pares de puntos. Los puntos se llaman nodos (o vértices); por ejemplo, la red de la figura 10.1 tiene siete nodos representados por siete círculos. Las líneas se llaman arcos (o ligaduras, aristas o ramas); por ejemplo, la red de la figura 10.1 tiene 12 arcos que corresponden a los 12 caminos del sistema del parque. Los arcos se etiquetan dando nombre a los nodos en sus puntos terminales; por ejemplo AB es el arco entre los nodos A y B en la figura 10.1

Los arcos de una red pueden tener flujo de algún tipo que pasa por ellos, por ejemplo, el flujo de tranvías sobre los caminos de Seervada Park en la sección 10.1. La tabla 10.1 proporciona varios ejemplos de flujo en redes. Si el flujo a través de un arco se permite sólo en una dirección (como en una calle de un sentido), se dice que el arco es un arco dirigido. La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco. Al etiquetar un arco con el nombre de los nodos que une, siempre se pone primero el nodo de donde viene y despues el nodo a donde va, esto es, un arco dirigido del nodo A al nodo B debe etiquitarse como AB y no como  BA. Otra manera de etiquetarlo es  A→B

Ejemplo Prototipo de Redes (II)

El segundo problema reside en que deben instalarse líneas telefónicas subterráneas para establecer comunicación entre todas las estaciones (inclusive la entrada). Como la instalación ese cara y perturba la ecología, se instalarán líneas que siguen sólo los caminos necesarios para obtener comunicación entre cualquier par de estaciones. La pregunta es por dónde deben tenderse las líneas para lograr esto con el mínimo número total de millas de cable instalado.

El tercer problema es que, durante al temperada pico, hay más personas que quieren tomar el tranvía a la estación T de las que se pueden acomodar. Para evitar la perturbación indebida de la ecología y de la vida silvestre de la región, se ha impuesto un racionamiento estricto en el número de viajes al día que pueden hacer las tranvías en cada camino. Así,durante la temporada pico, se pueden seguir varias rutas sin tomar en cuenta la distancia, para aumentar el número de viajes de travía diarios. La pregunta es cómo panear las rutas para los distintos viajes, de manera que se maximice el número total de viajes que se pueden hacer cada día, sin violar los límites individuales impuestos sobre cada camino.

Ejemplo Prototipo de Redes (I)

En fecha reciente se reservó el área de SERVADA PARK para paseos y campamentos. Nose permite la entrada de automóviles pero existe un sistema de caminos angostos para tranvías y "jeeps" conducidos por los guardabosques. En la figura 10.1 se muestra este sistema de caminos (sin las curvas), en donde O es la entrada al parque; las otras letras representan la localización de las casetas de los guardabosques (y otras instalaciones de servicio). Los números son las distancias en millas de estos caminos sinuosos.

El parque contiene un mirador a un hermoso paisaje en la estación T. Unos cuantos tranvías transportan a los visitantes desde la entrada a la estación T y de regreso.

En este momento el administradro del parque se enfrenta a tres problemas. Uno consiste en determinar qué ruta, desde la entrada del parque a la estación T, es la que tiene la distancia total más corta para la operación de los tranvías.

La planeación y control de proyectos

Es el último tipo de problemas que se ha resuelto por medio de las técnicas de redes, en especial el PERT ("Program Evaluation and Review Technique"  o técnica de evaluación y revisión de programas) y el CPM ("Critical Path Method" o método de la ruta crítica). Aunque limitados a su área de aplicación el PERT y el CPM han demostrado ser herramientas invaluables. De hecho, desde su desarrollo a finales de la década de 1950, el PERT y el CPM han sido (y probablemente seguirán siendo) las técnicas de redes más ampliamente usadas en la investigación de operaciones.

La primera sección introduce un ejemplo prototipo que se usará más adelante para ilustrar los fundamentos de los primeros tres tipos de problema. En la sección 10.2 se presenta la terminología básica para redes. La sección 10.7 está dedicada al método símplex de redes y la sección 10.8 presenta el último tipo de problemas.

El problema del flujo de costo mínimo

El cuarto tipo, el problema del flujo de costo mínimo, proporciona un enfoque unificador de muchas otras aplicaciones pro su estructura mucho más general. De hecho, esta estructura es tan general que incluye como casos especiales el problema de la ruta más corta  y el flujo máximo, al igual que los problemas de transporte, de trasbordo y de asignación del capítulo 7. Lo mismo que muchos otros modelos de optimización de redes, el problema del flujo de costo mínimo se puede formular como un problema de programación lineal y se puede resolver en forma eficiente mediante una versión simplificada del método símplex llamada método símplex de redes.

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

En este capítulo sólo se podrán plantear las bases de la metodología de redes actual. Sin embargo, se dará una introducción a cinco tipos importantes de problemas de redes y algunas ideas básicas sobre cómo resolverlos (sin profundizar en los aspectos de bases de datos, etc., tan vitales para ponerlos en práctica con éxito en la gran escala). Los tres primeros tipos de problemas, el problema de la ruta más corta, el problema del árbol de la mínima expansión y el problema del flujo máximo, tienen una estructura específica que surge con frecuencia en la práctica.

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

Un ejemplo de una aplicación reciente es un estudio que ha sido objeto de premios (véanse las referencias selectas 8 y 9) llevado a cabo a mediados de la década de 1980 por la Citgo Petroleum Corporation. EStá dedicado a las operaciones de refinamiento y comercialización del petróleo y tiene ventas de varios millones de millones de dólares. Cuando en 1983 la Southland Corporation (conocida por sus tiendas 7-Eleven) adquirió Citgo, la alta administración vio la necesidad urgente de un sistema de modelado para ayudar a Citgo a superar las presiones de los precios cambiantes de petróleo crudo y un aumento de 30 veces los costos de capital de trabajo. El equipo de investigación de operaciones desarrolló un sistema para apoyar las decisiones basados en la optimización, utilizando la metodología de redes y lo unió a la base de datos corporativa. El modelo toma en cuenta todos los aspectos del negocio, ayuda a la administración en todas las decisiones, desde la producción en las refinerías, hasta los precios que debe pagar o cobrar. Es esencial la representación de redes debido al flujo de bienes a través  de las distintas etapas: la compra de petróleo crudo de los proveedores, el embarque a las refinerías, el refinamiento de los diferentes productos y el embarque de estos productos a los centros de distribución y terminales de almacenamiento para su venta posterior. El sistema de modelado ha permitido a la compañia reducir su inventario en $116 millones de dólares. Esto ha significado un ahorro en los intereses anuales de $14 millones de dólares y mejoras en las decisiones de coordinación, costeo y compra, equivalentes  a otros $2.5 millones de dólares anuales.

En este estudio para Citgo, el modelo que se usa para para cada producto se ajusta al modelo del problema del flujo de costo mínimo que se presenta en al sección 10.6. Cada modelo tiene cerca de 3000 ecuaciones (nodos) y 15 000 variables (arcos), que es un problema de tamaño modesto para los estándares actuales de aplicación de los modelos de optimización de redes.

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,

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

Dada la solución prueba inicial, (x1,x2,x3) = (2,2,4), sea D la matriz diagonal correspondiente tal

Resumen y ejemplificación del algoritmo

Se presentará ahora un resumen y un ejemplo del algoritmo haciendo la primera iteración del ejemplo, después dando un resumen del procedimiento general y después aplicando este resumen a una segunda iteración.

Esquema de centrado para poner en práctica el concepto 3 (II)

En la figura 9.3 del ejemplo se tienen tres fronteras de restricción, cada una corresponde a un valor de cero para una de las tres variables del problema en la forma aumentada, es decir, x1=0, x2 = 0 y x3 =0. En la figura 9.4 se puede observar que estas tres restricciones cortan el plano Ax=b(x1+x2+x3 = 8) para formar la frontera de la región factible. La solución prueba inicial es (x1,x2,x3) = (2,2,4) y se encuentra dos unidades, alejada de las restricciones x1 = 0 o x2 =0 y alejada cuatro unidades x3 = 0, si se usan las unidades de las variables respectivas. Sin embargo, cualesquiera que sean estas unidades, son bastante arbitrarias y se pueden cambiar como se desee sin variar el problema. Entonces, se dará la siguiente escala a las variables:

Nótese que la solución prueba (1,1,1) en la figura 9.5 equidista de las fronteras de restricción x1=0, x2 =0 y x3 =0. En cada iteración subsecuente se da una nueva escala al problema para que la solución prueba sea siempre (1,1,1) en las coordenadas actuales.

Esquema de centrado para poner en práctica el concepto 3 (I)

Sólo falta un paso para completar la descripción del algoritmo, a saber, un esquema especial para transformar la región factible de manera que la solución prueba actual quede cerca del  centro. Se acaba de  describir el beneficio  de tener la solución prueba cerca del centro, pero otro beneficio importante del esquema de centrado es que constantemente cambia la dirección del gradiente proyectado hacia la solución óptima, conforme el algoritmo converge a esta solución.

Esta idea básica del esquema de centrado es directa, sencillamente se cambia la escala (unidades) para cada variable de manera que la solución prueba quede equidistante de las fronteras de restricción en el nuevo sistema de coordenadas. (El algoritmo original de Karmarkar utiliza un esquema de centrado más sofisticado).

Uso del gradiente proyectado para llevar a cabo los conceptos 1 y 2 (III)

Cuándo debe crecer α para moverse a la siguiente solución prueba? Como el incremento en Z es proporcional al de α, un valor cercano a 1 es bastante bueno para dar un paso relativamente grande hacia la optimalidad en la iteración actual. Sin embargo, el problema de un valor muy cercano a 1 es que la siguiente solución prueba puede quedar amontonada con una frontera de restricción, haciendo difícil realizar mejoras grandes en las iteraciones subsecuentes. Es de gran ayuda que las soluciones prueba quedan cerca del centro de la región factible (o al menos la porción de la región factible en la vecindad de la solución óptima) y no demasiado cerca de ninguna frontera de restricción. Con esto en mente, Karmarkar estableció para su algoritmo que con un valor de α = 0.25 se debe estar "a salvo". En la práctica a veces se usan valores mucho mayores (como α =0.9). Para desarrollar este ejemplo (y los problemas al final del capítulo) se eligió α = 0.5

Uso del gradiente proyectado para llevar a cabo los conceptos 1 y 2 (II)

Se dispone de una fórmula para calcular directamente el gradiente proyectado. Sea P la matriz de proyección.

Uso del gradiente proyectado para llevar a cabo los conceptos 1 y 2 (I)

En la forma aumentada, la solución prueba inicial para el ejemplo es (x1,x2,x3) = (2,2,4).
Si se agrega el gradiente (1,2,0) se obtiene

(3,4,4) = (2,2,4) + (1,2,0)

Sin embargo, ahora se tiene una complicación. El algoritmo no se puede mover de (2,2,4) hacia (3,4,4) porque (3,4,4) es no factible! si x1 =3 y x2 =4, entonces x3 = 8 -x1-x2= 1 en lugar de 4. El punto (3,4,4) se encuentra en la cara de enfrente al ver el triángulo factible de la figura 9.4. Entonces, para que siga siendo factible, el algoritmo proyecta (de manera indirecta) el punto (3,4,4) al triángulo factible bajando una línea perpendicular a este triángulo. Esta perpendicular llega al triángulo en el punto (2,3,3). Como.

(2,3,3) = (2,2,4) + (0,1,-1)

el gradiente proyectado de la función objetivo (el grandiente proyectado sobre la región factible) es (0,1,-1). En este gradiente proyectado el que define la dirección del movimiento para el algoritmo, como lo indica la flecha de la figura 9.4.

La relevancia del gradiente para los conceptos 1 y 2 (II)

El algoritmo de hecho opera sobre los problemas de programación lineal una vez que se han escrito en la forma aumentada. Sea x3 la variable de holgura de la restricción funcional del ejemplo, esta forma es:

La relevancia del gradiente para los conceptos 1 y 2 (I)

El algoritmo comienza con una solución prueba inicial que (al igual que todas las soluciones prueba subsecuentes) se encuentra en el interior de la región factible. Así, por ejemplo, la solución no debe estar en ninguna de las tres recta (x1=0, x2=0, x1+x2 =8) que forman la frontera de esta región en la figura 9.3. Se eligió arbitrariamente (x1,x2) = (2,2) como esta solución prueba inicial.

Para comenzar la aplicación de los conceptos 1y 2, obsérvese  en la figura 9.3 que la dirección del movimiento desde el punto (2,2) que aumenta el valor de Z a la mayor tasa posible es perpendicular  a (y hacia) la recta de la función objetivo, Z =16 = x1 + 2x2. Esta durección se indica con la flecha de (2,2) a (3,4). Sumando vectores,

(3,4) = (2,2) + (1,2),

donde el vector (1,2) es el gradiente de la función objetivo. (En la sección 14.5 se estudian los gradientes con más detalle, dentro del contexto de programación no lineal, campo en el que desde hace mucho se aplican algoritmos similares al de Karmarkar. ) Las componentes de (1,2) son justo los coeficientes de la función objetivo. Así, con una modificación más, el gradiente (1,2) define la dirección ideal para moverse; la pregunta sobre la distancia que hay que moverse se considerará más adelante.

Algoritmo de punto interior (II)

Para ilustrar estas ideas a través de la sección se usará el siguiente ejemplo:

Algoritmo de punto interior (I)

En la sección 4.9 se presentó un importante desarrollo nuevo en programación que se debe a Narendra Karmarkar de AT&T Laboratories. Se trata de un poderoso algoritmo para resolver problemas muy grandes de programación lineal. SE introducirá aquí la naturaleza del enfoque de Karmarkar con la descripción de una variante relativamente sencilla (la variante "afin" o de "escala afin") de este algoritmo.

En esta sección se centrará la atención sobre las principales ideas de Karmarkar a un nivel intuitivo evitando los detalles matemáticos. En particular, se pasarán por alto ciertos detalles que se necesitan para la aplicación completa del algoritmo (por ejemplo, cómo encontrar una solución factible inicial de prueba) pero que no son esenciales para la comprensión de los conceptos básicos. Las ideas se pueden resumir como sigue:

Concepto 1: Obtener, del interior de la región factible,  una solución factible que lleve a la solución óptima.

Concepto 2: Moverse en la dirección que mejore el valor de la función objetivo lo más rápido posible.

Concepto 3: Transformar la región factible para colocar la solución prueba actual cerca del centro permitiendo así una mejora grande cuando se lleve a cabo el concepto 2.

Resumen del procedimiento de programación líneal paramétrica para cambios sistemáticos en los parámetros bi (II)

Se aplicará este procedimiento al problema dual de la Wyndor Glass Co. (véase la tabla ) con el fin de resaltar su relación de dualidad con el procedimiento para cambios sistemáticos en los parámetros cj. En particular, supóngase que α1 =2 y α2 = -1, con lo que las restricciones funcionales se vuelven