Soluciones factibles en vértices adyacentes (IV)

Para n=3, todas las aristas de la región factible se forman de esta manera, como el segmento factible de la línea que está en la intersección de dos fronteras de restricción y los dos puntos terminales de una arista son soluciones factibles en un vértice adyacentes. En la figura 5.2 hay 15 aristas de la región factible y tanto hay 15 pares de soluciones factibles en un vértice adyacente. Para la solución factible en un vértice actual (2,4,3) hay tres formas de eliminar una de sus tres ecuaciones de definición para obtener la intersección de las otras dos fronteras de restricción, así hay tres aristas que emanan de (2,4,3). Estas aristas llevan a (4,2,4), (0,4,2) y (2,4,0) y éstas son las soluciones factibles en un vértice adyacentes a (2,4,3).

En la siguiente iteración, el método símplex elige una de estas tres aristas, digamos el segmento de línea más oscuro y se mueve a lo largo de él alejándose de (2,4,3) hasta que llega a la primera frontera de restricción nueva x1 = 4 en la otra punta. [No se puede continuar por esta línea hasta la siguiente frontera de restricción, x1 = 0, porque se llegaría a una solución no factible en un vértice, (6,0,5)]. la intersección de esta primera frontera de restricción nueva con las dos fronteras de restricción que forman la arista conduce a la nueva solución factible en un vértice, (4,2,4).

Soluciones factibles en vértices adyacentes (III)

Cuando n=3, las respuestas son un poco más complejas. Para ayudar y visualizar lo que ocurre, la figura 5.2 muestra un dibujo en tres dimensiones de una región factible representativas para este caso, en la que los puntos son las soluciones en los vértices. Esta región factible es un poliedro en lugar del polígono que se tenía para n = 2 (figura 5.1), ya que las fronteras de restricción son ahora planos y no líneas. Las caras del poliedro forman la frontera de la región factible, donde cada cara es la porción de la frontera de restricción que también satisface a las otras restricciones. Nótese que cada solución factible en un vértice se encuentra en la intersección de tres fronteras de restricción (quizá incluyendo para de las frontera de restricción x1 = 0, x2 = 0 y x3 = 0 para las restricciones de no negatividad) y que la solución también satisface las otras restricciones. Las intersecciones que no satisfacen una o más de las otras restricciones llevan a soluciones no factible en un vértice.

El segmento de línea más oscuro en la figura 5.2 traza la trayectoría que sigue el método símplex en una iteración normal. El punto (2.4.3) es la solución factible en un vértice actual que se usa para iniciar una iteración y el punto (4,2,4) será la nueva solución factible en un vértice al término de la iteración. El punto (2,4,3) se encuentra en la intersección de la frontera de restricción x2 = 4, x1 + x2 =6 y -x1 + 2x3 =4, por lo que estas tres ecuaciones son las ecuaciones de definición para esta solución factible en un vértice. Si se eliminara la ecuación de definición x2 = 4, la intersección de las otras dos fronteras de restricción (planos) formarían una línea. Un segmento de esta línea, que se muestra en la figura5.2 como el segmento más oscuro que va de (2,4,3) a (4,2,4), está sobre la frontera de la región factible, mientras que el resto de la línea es no factible. Este segmento de línea se llama arista de al región factible y sus puntos terminales (2,4,3) y (4,2,4) son soluciones factibles en un vértice adyacentes.

Soluciones factibles en vértices adyacentes (II)

La respuesta a estas preguntas es sencilla cuando n=2. En este caso la frontera de la región factible consiste de varios segmentos de línea conectados que forman un polígono, como se muestra en la figura 5.1 con los cinco segmentos más oscuros. Estos segmentos de líneas se conocen como aristas de la región factible. De cada solución factible en un vértice emanan dos de estas aristas que llevan a una solución factible en un vértice adyacente en la otra punta (Nótese en la figura 5.1 que cada solución factible en un vértice tiene dos soluciones adyacentes) Cada iteración sigue una trayectoria a lo largo de estas aristas moviéndose de una punta a otra. En la figura 5.1 la primera iteración se mueve a lo largo de la arista que va de (0,0) a (0,6), y en el siguiente se mueve por la arista que va de (0,6) a (2,6). Como se puede ver en la tabla 5.1, cada uno de estos movimientos a una solución factible en un vértice significa sólo un cambio en el conjunto de ecuaciones de definición (fronteras de restricción sobre las que se encuentra la solución)

Soluciones factibles en vértices adyacentes (I)

Ahora se analizaran las soluciones factibles en vértices adyacentes y el papel que juegan en la solución de problemas de programación lineal. Recuérdese que en el capitulo 4 al ignorar las variables de holgura y artificiales, cada iteración del método símplex se mueve de la solución factible en el vértice actual a uno adyacente. Cuál es la trayectoria que sigue este proceso? Qué significa en realidad una solución factible en un vértice adyacente? Primero se contestará a estas preguntas desde el punto de vista geométrico y después se dará la interpretación algebraica.

Fundamentos del método símplex - Terminología (IV)

No obstante, esto no quiere decir que todo conjunto de n ecuaciones frontera que se elija entre las (n+m) restricciones (n restricciones de no negatividad y m funcionales) conduzca a una solución factible en un vértice. En particular, la solución simultánea de algún sistema puede violar una o más de las otras m restricciones no seleccionadas, en cuyo caso se trata de una solución no factible en un vértice. El ejemplo tiene tres soluciones de este tipo, y en la tabla 5.2 se resume esta situación.

Más aún, un sistema de n ecuaciones de frontera puede no tener solución. Esto ocurre dos veces en el ejemplo con los pares de ecuaciones 1) x1=0 y x1 = 4, y 2) x2 = 0 y 2x2 = 12. Tales sistemas no son de interés en el contexto de este blog.

La última posibilidad (que nunca ocurre en el ejemplo) es que un sistema de n ecuaciones de frontera tenga soluciones múltiples ocasionadas por una ecuación redundante. Tampoco es necesario preocuparse por este caso, ya que el método símplex salva estas dificultades.

Para resumir, en el ejemplo con cinco restricciones y dos variables existen 10 pares de ecuaciones frontera. Cinco de estos pares se convierten en ecuaciones de definición para las soluciones factibles. Cinco de estos pares se convierten en ecuaciones de definición para las soluciones factibles en los vértices, tres se vuelven ecuaciones de definición para soluciones no factibles en un vértice y cada uno de los otros dos pares no tiene solución.

Fundamentos del método símplex - Terminología (III)

Según esta definición, una solución factible está sobre un segmento de línea que conecta otras dos soluciones factibles no es una solución factible en un vértice. Para dar un ejemplo cuando n=2, considérese la figura 5.1. El punto (2,3) no es una solución factible en un vértice puesto que se encuentra en varios de estos segmentos, por ejemplo, en el segmento de línea que conecta los puntos (0,3) y (4,3). De igual manera, (0,3) no es una solución factible en un vértice ya que se encuentra sobre el segmento de línea que conecta (0,0) con (0,6). Sin embargo, (0,0) es una solución factible en un vértice porque es imposible encontrar otras dos soluciones factibles que se encuentren en lados completamente opuestos de (0,0).

Cuando el número de variables de decisión es mayor que 2 o 3, esta definición no es muy conveniente para identificar soluciones factibles en los vértices. Por tanto, una interpretación algebraica de estas soluciones resultará muy útil. En el ejemplo de la Wyndor Glass Co. cada solución factible en un vértice en la figura 5.1 está en la intersección de dos (n=2) líneas de restricción; es decir, es una solución simultánea de un sistema de dos ecuaciones frontera.

Esta situación se resume en la tabla 5.1, en las que las ecuaciones de definición se refieren a las ecuaciones de la frontera de las restricciones que definen o conducen hacia las soluciones factibles en un vértice indicadas. De manera similar, en cualquier problema de programación lineal, cada solución factible en un vértice se encuentra en la intersección de n fronteras de restricción; esto es, se trata de una solución simultánea de un sistema de n ecuaciones frontera.

Fundamentos del método símplex - Terminología (II)

Por ejemplo,el problema de la Wyndor Glass Co. tiene cinco restricciones (tres funcionales y dos de no negatividad), de manera que tiene cinco ecuaciones de frontera que se muestra en la figura 5.1. Como n=2, los hiperplanos definidos por estas ecuaciones de frontera son sólo rectas. Por lo tanto, las fronteras de restricción para las cinco restricciones son las cinco líneas que se muestran en la figura 5.1

La frontera de la región factible consiste en aquellas soluciones factibles que satisfacen una o más de las ecuaciones de frontera de las restricciones.

Geométricamente, cualquier punto sobre la frontera de la región factible se encuentra sobre uno o más de los hiperplanos definidos por las ecuaciones de frontera de restricciones respectivas. En la figura 5.1 la frontera consiste en los cinco segmentos de recta oscuros.

En seguida se da una definición general de solución factible en un vértice en el espacio de n dimensiones.

Una solución factible en un vértice es aquélla que no está sobre ningún segmento de linea que conecta a otras dos soluciones factibles.