Procedimiento global

Existen dos implicaciones importantes en la forma matricial del conjunto de ecuaciones actual. La primera es que sólo es necesario obtener B^-1 para poder calcular todos los números de la tabla símplex a partir de los parámetros originales (A, b, cB) del problema. (Esta implicación es la esencia de la idea fundamental que se describe en la siguiente sección.) La segunda es que cualquiera de estos números (excepto Z = cBB^-1b) se puede obtener al efectuar nadamás una parte de la multiplicación de matrices. Por tanto, se pueden calcular los números requeridos para llevar a cabo una iteración conforme se necesiten sin dedicar todo el esfuerzo computacional que toma obtener todos los números.

Ejemplo para ilustrar la forma matricial

Para ilustrar esta forma matricial para el conjunto de ecuaciones actual, considerese el último conjunto de ecuaciones que se obtiene en la iteración 2 para el problema de la Wyndor Glass Co. Si se emplea la B^-1 que se da en la iteración 2.

Forma matricial del conjunto de ecuaciones actual (III)

DEbido a que se realiza la misma serie de operaciones algebraicas en ambos lados del conjunto original de ecuaciones, se usa esta misma matriz que premultiplica el lado derecho original para premultiplicar el lado izquierdo original. En consecuencia, como

Forma matricial del conjunto de ecuaciones actual (II)

Las operaciones algebraicas realizadas por el método simplex (multiplicar una ecuación por una constante y sumar un múltiplo de una ecuación a otra) se expresan en forma matricial premultiplicando ambos lados del conjunto original de ecuaciones por la matriz apropiada. Esta matriz tiene el mismo número de elementos que la matriz idéntica, excepto que cada múltiplo de una operación algebraica se debe colocar en el lugar que se necesita para que la multiplicación de matrices realice esta operación. Aún después de una serie de operaciones algebraicas a través de varias iteraciones se puede deducir cuál debe ser esta matriz (simbólicamente) en cada paso usando lo que ya se sabe sobre el lado derecho del nuevo conjunto de ecuaciones. En particular, después de cualquier iteración, xB = B^-1b y Z = cBB^-1b, por lo que el lado derecho de las ecuaciones se ha convertido en

Forma matricial del conjunto de ecuaciones actual (I)

El último preliminar antes de resumir el método símplex revisado es mostrar la forma matricial del conjunto de ecuaciones que aparece en la tabla símplex en cualquier iteración del método original.

Para el conjunto original de ecuaciones, la forma matricial es

Este conjunto de ecuaciones se exhibe también en la primera tabla símplex de la tabla 5.7

Ejemplo Obtención de una solución básica factible

Para ilustrar este método para obtener una solución básica factible, considérese otra vez el problema de la Wyndor Glass Co., presentado en la sección 3.1 que se resolvió empleando el método símplex original en la tabla 4.8. En este caso,

Obtención de una solución básica factible (II)

El método símplex introduce sólo variables básicas tales que B sea no singular, de manera que B^-1 siempre existe. Así, para resolver BxB =b, ambos lados se premultiplicarán por B^-1

Obtención de una solución básica factible

Recuérdese que el objetivo general del método símplex es obtener una sucesión de soluciones básicas factibles mejoradas hasta alcanzar la solución óptima. Una de las caracteristicas clave del método símplex revisado tiene que ver con la forma en que obtiene cada nueva solución básica factible después de identificar sus variables básicas y no básicas. Dadas estas variables, la solución básica que resulta es la solución de las m ecuaciones.

se obtiene al eliminar las columnas correspondientes a los coeficientes de las variables no básicas de [A, I]. (Aún más los elementos de xb y, por lo tanto, las columnas de B pueden quedar colocadas en diferente orden al ejecutar el método símplex.)

El método símplex revisado (II)

El método símplex revisado usa explicitamente operaciones con matrices, por lo que se vuelve importante describir el problema en notación matricial. Para ayudar al lector a distinguir entre mátrices, vectores y escalares, usarán siempre letras MAYUSCULAS en negritas para representar matrices, letra minúsculas en negritas para representar vectores y letras cursivas normales en el caso de los escalares. También se usará el cero en negritas (0) para denotar el vector nulo (un vector cuyos elementos son todos cero) ya sea en forma de columna o de renglón (lo que debe ser claro por la forma del problema), mientras que el cero normal (0) seguirá representado el número cero.

So se emplean matrices, nuestra forma estándar del modelo general de programación lineal establecido en la sección 3.2 se convierte en:

El método símplex revisado (I)

El método símplex, tal como se describió en el capitulo 4 (y que en adelante se llamará método símplex original) es un procedimiento algebraico directo. Sin embargo, esta forma de ejecutar el algoritmo (ya sea en su forma algebraica o tabular) no es el procedimiento de cálculo más eficiente cuando se trata de emplear una computadora digital, pues calcula y almacena muchos números que no se necesitan para la iteración actual y muchos que ni siquiera son pertinentes para la toma de decisiones en iteraciones subsecuentes. Las únicas cifras importantes en cada iteración son los coeficientes de las variables no básicas en la ecuación (0), los coeficientesde la variable básica entrante en las restricciones y el lado derecho de las ecuaciones. Sería muy útil contar con un procedimiento que obtuviera esta información de manera eficiente sin tener que calcular y almacenar los demás coeficientes.

Como se mencionó en la sección 4.8 estas ideas motivaron el desarrollo del método símplex revisado. Este método se ideó para que lograra exactamente las mismas cosas que el método símplex original, pero que, al llevarlo a la computadora, las hiciera en una forma más eficiente. Así, se trata de una versión simplificada del procedimiento original. Calcula y almacena sólo la información que se necesita en el momento y guarda los datos esenciales de manera más compacta.

El método símplex comienza con una solución básica factible

El método símplex comienza con una solución básica factible y se mueve en forma iterativa a una solución básica adyacente mejor, hasta que logra una solución óptima. Cómo se alcanza la solución básica factible adyacente en cada iteración?

Recuérdese que para el problema original se obtiene una solución en un vértice adyacente a partir de la solución actual cuando: 1) se elimina una ecuación de frontera (ecuación de definición) del conjunto n restricciones que definen la solución actual, 2) se hace un movimiento alejándose de la solución actual, enla dirección factible a lo largo de las (n-1) restricciones de frontera (una arista de la región factible) restantes y 3) el movimiento se detiene al encontrar la primera restricción (ecuación de definición) nueva.

De manera equivalente, en la terminología nueva el método simplex llega a una solución básica factible adyacente a partir de la solución actual cuando: 1) se elimina una variable (la variable básica entrante) del conjunto de n variables no básicas que definen la solución actual, 2) se aleja de la solución actual incrementando el valor de esta variable (y ajustando las otras variables básicas para que sigan satisfaciendo el sistema de ecuaciones) y manteniendo las (n-1) variables restantes a nivel cero y 3) se detiene cuando el valor de la primera variable básica (la variable básica que sale) llega a cero (a su ecuación de frontera). Con cualquiera de estas dos interpretaciones, la elección entre las n alternativas en el paso 1 se hace escogiendo aquella que da la tasa más alta para mejorar el valor de Z (por cada unidad de incremento de la variable básica entrante) durante el paso 2.

Extensiones a la forma de igualdades del problema (V)

De igual manera, las otras tres soluciones en los vértices llevan a las otras soluciones básicas que se muestran en la tabla 5.6.

Los otros dos conjuntos de variables de definición -1) x1 y x3 y 2) x2 y x4 - no conducen a una solución básica para el sistema de ecuaciones 1) -3) que se da en la tabla 5.4 Esta conclusión se equipara a la observación que se hizo antes respecto a que los conjuntos correspondientes de ecuaciones de definición no conducen a una solución.

Extensiones a la forma de igualdades del problema (IV)

Ya se hizo notar que no todo conjunto de n ecuaciones de frontera conduce a una solución en un vértice, ya sea porque el sistema no tiene soluciones o porque tiene soluciones múltiples. Por razones análogas, no todo conjunto de n variables no básicas conduce a una solución básica. Sin embargo, el método símplex evita los casos.

Para ejemplificar estas definiciones, considérese una vez más el ejemplo de la Wyndor Glass Co. Sus ecuaciones de frontera y las variables indicativa se muestran en la tabla 5.4.

Al aumentar las soluciones factibles en los vértices (véase la tabla 5.1) se obtienen las soluciones básicas factibles enumeradas en la tabla 5.5. En esta tabla se han colocado junta las soluciones básicas factibles adyacentes, excepto el par formado por la primera y la última. Nótese que en todos los casos, las variables no básicas son necesariamente las variables indicativas de las ecuaciones de definición. Entonces, las soluciones básicas factibles adyacentes difieren en que tienen sólo una variable no básica distinta. También nótese que cada solución básica factible es necesariamente la solución simultánea del sistema de ecuaciones para el problema en forma aumentada (véase la tabla 5.4) cuando las variables no básicas se igualan a cero.

Extensiones a la forma de igualdades del problema (III)

Ahora considérense las soluciones básicas factibles. Se puede observar que los únicos requisitos para que una solución sea factible en la forma aumentada del problema son que satisfaga el sistema de ecuaciones y que todas las variables sean no negativas.

Una solución factible es aquella en la que la m variables básicas son no negativas (≥0). Se dice que una solución básica factible es degenerada si cualquiera de estas m variables es igual a cero.

Extensiones a la forma de igualdades del problema (II)

En este punto deben aclararse las relaciones algebraicas entre las soluciones básicas y las soluciones en vértices. Recuérdese que cada solución en un vértice es la solución simultánea de un sistema de n ecuaciones de frontera, a las que se dio el nombre de ecuaciones de definición. La pregunta clave es: "cómo puede distinguirse cuando una ecuación de frontera en particular es una de las ecuaciones de definción si el problema se encuentra en forma aumentada?" Por fortuna, la respuesta es sencilla. Como ahora se cuenta con (n+m) variables, una para cada una de las (n+m) restricciones, cada restricción tiene exactamente una variable indicativa que marca por completo (según si su valor es cero o no) cuando la solución actual satisface la ecuación de frontera de esa restricción.

Así pues, siempre que la ecuación de frontera de una restricción sea una de las ecuaciones de definición, la variable indicativa tiene valor cero en la forma aumentada del problema. Cada una de estas variables indicativas se llama variable no básica para la solución básica correspondiente. En seguida se resumen las conclusiones y la terminología (que ya se introdujo en la sección 4.2).

Cada solución básica tiene n variables no básicas iguales a cero. Los valores de las m variables restantes (llamadas variables básicas) constituyen la solución simultánea del sistema de m ecuaciones del problema en la forma aumentada ( después de igualar a cero las variables no básicas). Esta solución básica es la solución en el vértice aumentada cuyas n ecuaciones de definición son las indicadas por las variables no básicas.

Extensiones a la forma de igualdades del problema (I)

En cualquier problema de programación lineal en nuestra forma estandar la apariencia de las restricciones funcionales después de introducir variables de holgura.

en donde x(n+1), x(n+2),.......,x(n+m) son variables de holgura. En la sección 4.6 se describió cómo puede obtenerse esta misma forma (la forma apropiada de eliminación Gaussiana) para otros problemas de programación líneal, introduciendo variables artificiales, etc. Entonces las soluciones originales (x1, x2,......,xn) quedan aumentadas con los valores correspondientes de las variables de holgura o artificiales (xn+1, xn+2,........., xn+m). A partir de este aumento, en la seccion 4.2 se definieron las soluciones básicas como soluciones aumentadas en un vértice y las soluciones básicas factibles como soluciones factibles aumentadas en un vértice. En consecuencia, las tres propiedades anteriores de las soluciones factibles en un vértice también se cumplen para las soluciones básicas factibles.

Propiedades de las soluciones factibles en un vértice (VI)

Por el contrario, la figura 5.3 muestra una región factible que nunca puede ocurrir en un problema de programación líneal, pero que viola la propiedad 3. El problema que se muestra es idéntico al de la Wyndor Glass Co. (incluso con la misma función objetivo) excepto que se aumentó la región factible hacia la derecha de (8/3, 5). Así, las soluciones factibles en un vértice adyacentes a (2,6) son ahora (0,6) y (8/3, 5). y de nuevo ninguna delas dos es mejor que (2,6). Sin embargo, ahora otra solución factible en un vértice, (4,5), es mejor que (2,6), lo que viola la propiedad 3. La razón es que la frontera de la región factible va de (2,6) a (8/3,5) y después "dobla hacia afuera" hasta (4,5), más allá de la línea de la función objetivo que pasa pr (2,6).

El punto clave es que el tipo de situación que se ilustra en la figura 5.3 no puede ocurrir en programación líneal. La región factible en esta figura implica que las restricciones 2x2 ≤ 12 y 3x1 + 2x2 ≤ 18 se cumplen para 0 ≤ x1 ≤ (8/3). Sin embargo, bajo la condición de que 8/3 ≤ x1 ≤4, la restricción 2x1 + 2x2 ≤ 18 se elimina y la reemplaza x2 ≤5. Este tipo de "restricciones condicionales" simplemente no están permitidos en la programación líneal.

Propiedades de las soluciones factibles en un vértice (V)

La propiedad 2 sugiere que puede obtenerse una solución óptima mediante la enumeración exhaustiva, esto es, se pueden encontrar y comparar todas las soluciones factibles en los vértices, pues son un número finito. Desafortunadamente existen números finitos que (para propósitos prácticos) bien podráin ser infinitos. Por ejemplo, un problema de programación líneal bastante pequeño que consta de sólo m = 50 restricciones y n =50 variables, tendría (100!)/(50!) ≈ 10^29 sistemas de ecuaciones que resolver. En contraste, el método símplex necesitaría examinar nada más alrededor de 100 soluciones factibles en los vértices para un problema de este tamaño. este ahorro tan grande se puede obtener gracias a la prueba de optimalidad que proporciona la propiedad 3:

Propiedad 3. Si una solución factible en un vértice no tiene soluciones factibles en vértices adyacentes que sean mejores (en cuanto al valor de Z), entonces no existen soluciones factibles en un vértice que sean mejores, es decir, la solución es óptima.

A manera de ilustración de la propiedad 3 considérese la figura 5.1 (o la figura 3.3) para el ejemplo de la Wyndor Glass Co. Las soluciones facrtibles en los vértices (0,6) y (4,3) son adyacentes a la solución factible en el vértice (2,6) y ninguna te las dos tiene un valor mejor de Z. Esto implica que ninguna de las otras soluciones factibles en un vértice (0,0) y (0,4), pueden ser mejores que (2,6) y por lo tanto (2,6) debe ser óptima.

Propiedades de las soluciones factibles en un vértice (IV)

El significado real de la propiedad 1 es que simplifica la búsqueda de la solución óptima, ya que sólo tienen que tomarse en cuenta las soluciones factibles en los vértices. La propiedad 2 pone de relieve la magnitud de esta simplificación.


Propiedad 2. Existe sólo un número finito de soluciones factibles en los vértices.

Esta propiedad sin duda se cumple en las figuras 5.1 y 5.2 donde nada más se tienen cinco y diez soluciones factibles en un vértice, respectivamente. Para ver por qué en general este número es finito, recuérdese que cada solución factible en un vértice es la solución simultánea de un sistema de n entre (m +n) ecuaciones de frontera de restricción. El número de combinaciones diferentes de las (m+n) ecuaciones tomadas n a la vez es:

(m+n)!/m!n!

Que es un número finito. Este número a su vez, es una cota superior para el número de soluciones factibles en los vertices. En la figura 5.1 m=3 y n=2, de manera que existen 10 sistemas diferentes de dos ecuaciones, pero sólo la mitad de ellos son soluciones factibles en un vértice. En la figura 5.2., m=4 y n =2, de manera que hay 35 sistemas diferentes de tres ecuaciones, pero sólo 10 conducen a soluciones factibles en un vértice.

Propiedades de las soluciones factibles en un vértice (III)

Como las ponderaciones α y (1-α) suman 1, las únicas posibilidades que se tienen al conparar Z*, Z1 y Z2 son: 1) Z* = Z1 = Z2, 2)Z1 < Z* Z* > Z2. La primera posibilidad implica que x' y x'' también son óptimas, lo que contradice la suposición de que se cumple el caso del inciso a. Las otras posibilidades contradicen la suposición inicial de que x* es óptima. En conclusión, es imposible tener siquiera una solución óptima que no sea una solución factible en un vértice.

Ahora considérese el caso del inciso b que se demostró en la sección 3.2 bajo la definición de solución óptima cambiando la función objetivo del ejemplo a Z = 3x1 + 2x2. Lo que ocurre en el procedimiento gráfico es que la recta que representa la función objetivo se mueve hacia arriba hasta que contiene el segmento que conecta la dos soluciones factibles en los vértices (2,6) y (4,3). Lo mismo pasa en dimensiones más altas, excepto que en este caso la función objetivo es un hiperplano que se mueve hasta que contiene el o los segmentos que conectan dos (o más) soluciones factibles en los vértices. Como consecuencia, es posible obtener todas las soluciones óptimas como promedios ponderados de soluciones óptimas factibles en los vértices.

Propiedades de las soluciones factibles en un vértice (II)

El punto de vista algebraico siguiente también aclara por qué en el caso del inciso a la propiedad debe cumplirse. Se desarrollará una demostración por contradicción suponiendo que esa solución óptima no es una solución factible en un vértice y demostrando que esta suposición lleva a una contradicción y por lo tanto no puede ser cierta. El paso más importante es observar, a partir de la definición de solución factible en un vértice que esta suposición implica que deben existir otras dos soluciones factibles tales que el segmento de línea que las une contiene la solución óptima. Sean x*, x', x'''los vectores que denotan la solución óptima y estas otras dos soluciones óptimas respectivamente, y sean Z*, Z1, Z2 los valores respectivos de la función objetivo. Igual que para cualquier otro punto sobre el segmento de línea que conecta x' y x''

x* = αx'' + (1+α )x'

para algún valor de α tal que 0 < α < 1. Entonces

Z* = αZ2 + (1-α )Z1

Propiedades de las soluciones factibles en un vértice (I)

En la sección 4.1 se habló de propiedades clave de las soluciones factibles en los vértices que constituyen los principios fundamentales del método símplex. En este momento se tiene la posibilidad de explicar por qué estas propiedades (que se acaban de restablecer) de hecho se cumplen para cualquier problema de programación lineal que tiene soluciones factibles y una región factible acotada.

Propiedad 1. a) Si el problema tiene exactamente una solución óptima, entonces ésta debe ser una solución factible en un vértice; b) si el problema tiene soluciones múltiples, entonces al menos dos deben ser soluciones factibles en vértices adyacentes.

La propiedad 1 es un concepto bastante intuitivo desde el punto de vista geométrico. Primero, considérese el caso del inciso a que se ilustra con el problema de la Wyndor Glass Co., el que la única solución óptima (2,6) es sin duda una solución factible en un vértice. Nótese que nada especial hay en el ejemplo que lleve a este resultado. Para cualquier problema que tiene sólo una solución óptima, siempre es posible seguir elevando la línea (hiperplano) de la función objetivo hasta que nada más toque en un punto (la solución óptima), esquina o vértice, de la región factible.

Propiedades de las soluciones factibles en un vértice (VII)

La razón básica para que la propiedad 3 se cumpla es que en cualquier problema de programación lineal la región factible siempre tiene la propiedad de ser un conjunto convexo, como se define en el apéndice 1 se ilustra en varias figuras ahí mismo. Para un problema de dos variables, esta propiedad de convexo que significa que el ángulo dentro de la región factible en todas las solucione factibles en un vértice es menor a 180°. Esto se ilustra en la figura 5.1 en donde los ángulos en (0,0), (0,6) y (4,0) son de 90° y aquellos en (2,6) y (4,3) tienen entre 90° y 180°. Por el contrario, la región factible de la figura 5.3 no es un conjunto convexo debido a que el ángulo en (8/3, 5) es mayor a 180°. Éste es el tipo de "doblez hacia afuera" en un angulo mayor a 180° que no puede ocurrir en programación líneal. En problemas de n dimensiones se sigue aplicando este concepto intuitivo de "nunca doblar hacia afuera".

Para aclarar el significado de región factible convexa, considérese el hiperplano de la función objetivo que pasa por una solución factible en un vértice, y que es igual o mejor que todas las soluciones factibles en vértices adyacentes. [En el ejemplo original de la Wyndor Glass Co. este hiperplano es la recta que pasa por (2,6) en la figura 3.3] Todas estas soluciones adyacentes [(0,6) y (4,3) en el ejemplo] deben estar ya sea en el hiperplano o en el lado no favorable (según lo mide el valor de Z) del hiperplano. El que la región factible sea convexa significa que su frontera no se puede "doblar hacia afuera" más allá de una solución factible en un vértice adyacente para dar una solución que se encuentre en el lado favorable del hiperplano de manera que la propiedad 3 se cumple.

Soluciones factibles en vértices adyacentes (VI)

En seguida se analizarán algunas propiedades importantes de las soluciones factibles en un vértice y se describirán las implicaciones de todos estos conceptos al interpretar el método símplex. Sin embargo, ahora que se tiene fresco el resumen anterior, se expondrá un panorama general de estas implicaciones. Cuando el método símplex elige una variable básica entrante, la interpretación geométrica es que está eligiendo una de las aristas que emanan de la solución factible en un vértice actual para trasladarse sobre ella. El aumento en el valor de esta variable (y al mismo tiempo el cambio en los valores de las otras variables básicas según sea necesario) corresponde a moverse a lo largo de esta arista. El que la primera variable básica llegue a cero (la variable básica que sale) corresponde a llegar a la primera frontera de restricción nueva en la otra punta de esta arista de la región factible.

Soluciones factibles en vértices adyacentes (V)

Cuando n>3, estos mismos conceptos se generalizan a mayores dimensiones, sólo que las fronteras de restricción son ahora hiperplanos en lugar de planos. Para resumir:

Una solución factible en un vértice se encuentra en la intersección de n fronteras de restricción (y satisface también las otras restricciones). Una arista de la región factible es un segmento de línea factible que se encuentra en la intersección de (n-1) fronteras de restricción, en el que cada punto terminal se encuentra en una frontera de restricción adicional (por lo que estos puntos terminales son soluciones factibles en un vértice). Dos soluciones factibles en un vértice son adyacentes si el segmento de línea que las conecta es una arista de la región factible. De cada solución factible en un vértice emanan n aristas, cada una lleva a una de las n soluciones factibles en un vértice adyacentes. Cada iteración del método símplex se mueve de la solución factible en un vértice actual a una adyacente a lo largo de una de estas n aristas.

Al cambiar del punto de vista geométrico al algebraico, la intersección de fronteras de restricción cambia a la solución simultánea de las ecuaciones de frontera de restricción. Las n ecuaciones de frontera que llevan a (definen) una solución factible en un vértice son las ecuaciones de definición, y al eliminar una de estas ecuaciones se obtiene una línea cuyo segmento factible es una arista de la región factible.

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.

Fundamentos del método símplex - Terminología

Puede entenderse de manera intuitiva que las soluciones óptimas de cualquier problema de programación líneal deben estar sobre la frontera de la región factible, y de hecho, ésta es una propiedad general. Como la frontera es un concepto geométrico, las dos primeras definiciones se pueden identificar algebraicamente.

La ecuacion de la frontera para cualquier restricción se obtiene sustituyendo su signo ≤, = o ≥ por un signo =.

En consecuencia, la forma de una ecuación de la frontera de restricción es ai1x1 + ai2x2+ ..... + ainxn = bi para las restricciones funcionales y xj = 0 para las de no negatividad. Estas ecuaciones definen una figura geométrica "plana" (llamada hiperplano) en un espacio n-dimensional, análoga a la línea en el espacio de dos dimensiones y al plano en el de tres dimensiones. Este hiperplano forma una frontera de restricción para la restricción correspondiente ya que cualquier punto que se encuentre a un lado de esta frontera viola esa restricción, mientras que cualquier punto sobre ella, satisface la restricción. (Los puntos en el otro lado también la satisfacen si se trata de una desigualdad.)

Fundamentos del método símplex

En la sección 4.1 se introdujo el concepto de soluciones factibles en un vértice  y el papel clave que desempeñan en el método símplex. Estos conceptos geométricos se relacionaron con el álgebra del método símplex en la sección 4.2. Sin embargo, todo esto se hizo en el contexto del problema de la compañia Wyndor Glass, que tiene sólo dos variables y por ende tiene una interpretación geométrica directa. Cómo puede generalizarse estos conceptos a dimensiones mayores cuando se manejan problemas más grandes?. La respuesta se dará en esta sección.

Para comenzar, se introducirá parte de la terminología básica para cualquier problema de programación lineal con n variables (antes de introducir variables de holgura y artificiales para iniciar el método símplex). Mientras se lee esto, puede ser útil que el lector consulte la figura 5.1 para interpretar estas definiciones en dos dimensiones (n = 2)

Teoría del método Símplex

En el anterior capítulo se presentó la mécanica básica del método símplex. Ahora se profundizara un poco en este algoritmo al examinar parte de la teoría en que se apoya. En esta primera sección se estudian las propiedades algebraicas y geométricas generales que constituyen el fundamento del método símplex. Después se describe la forma matricial del método símplex (llamada método símplex revisado) que simplifica mucho el procedimiento y facilita su introducción a una computadora. En seguida se presenta la idea fundamental sobre la propiedad del método símplex que permite deducir de qué manera los cambios que se hacen al modelo original repercuten en al tabla del símplex final. Esta idea proporcionará la clave para los importantes temas de más adelante

Conclusiones del Método Símplex

El método símplex es un algoritmo eficiente y confiable para resolver problemas de programación líneal. También proporciona la base para llevar a cabo, en forma muy eficiente, las distintas etapas del análisis posóptimo.

Aunque tiene una interpretación geométrica útil, el método símplex es un procedimiento algebraico. En cada iteración se mueve de la solución básica factible actual a una adyacente mejor eligiendo tanto la variable básica entrante como la que sale y después usando la eliminación de Gauss para resolver el sistema de ecuaciones lineales. Cuando la solución actual no tiene una solución básica factible adyacente que sea mejor, la solución actual es óptima y el algoritmo se detiene.

Se presentó la forma algebraica completa del método símplex para establecer su lógica y se llevó el método a una forma tabular más conveniente. Para preparar el inicio del método símplex, algunas veces es necesario obtener una solución básica factible inicial para un problema revisado. En este caso se puede usar el método de la M, o bien, el método de las dos fases, para asegurar que el método símplex obtenga una solución óptima para el problema original.

Los paquetes de software para computadoras personales basados en el método símplex están ampliamente difundidos y al alcance, para manejar problemas de tamaño modesto. Los programas para computadoras grandes se usan por rutina para resolver y analizar problemas con muchos cientos y aun miles de funciones de restricción y variables.

El algoritmo de puntos interiores de Karmarkar proporciona una nueva herramienta poderosa para resolver problemas muy grandes.

Programación lineal paramétrica

El análisis de sensibilidad requiere el cambio de un parámetro a la vez en el modelo original para examinar su efecto sobre la solución óptima. Por el contrario, la programación líneal paramétrica (o programación paramétrica en forma más corta) se refiere al estudio sistemático de los cambios en la solución óptima cuando cambia el valor de muchos parámetros al mismo tiempo dentro de un intervalo. Este estudio proporciona una extensión muy útil al análisis de sensibilidad, por ejemplo, se puede verificar el efecto de cambios simultaneos en parámetros "correlacionados", causados por factores exógenos tales como el estado de la economía. Sin embargo, una aplicación más importante es la investigación de los trueques entre los valores de los parámetros. Por ejemplo, si la cj representa la ganancia unitaria de la actividad resprectiva es posible aumentar el valor de alguna xj a costa de disminuir el de otra mediante un intercambio apropiado de personal y equipo entre las actividades. De manera parecida, si las bi representan las cantidades disponibles de los respectivos recursos, puede ser posible aumentar alguna bi si se está de acuerdo en aceptar disminuciones en algunas otras.

En algunos casos, el propósito del estudio es determinar el trueque más apropiado entre  dos factorse básicos como costos y beneficios. La forma usual de hacerlo es expresar uno de estos factores en la función objetivo (como minimizar el costo total) e incorporar el otro a las restricciones (por ejemplo, beneficio ≥ nivel mínimo aceptable) como se hizo para el problema de contaminación de la Nori&Leets Co. en la sección 3.4. La programación lineal paramétrica permite entonces la investigación sistemática de lo que ocurre cuando se cambia una decisión inicial tentativa para mejorar un factor a costa de otro. Este enfoque se ejemplifica en la sección 8.5 con el estudio de un caso en el que los dos factores básicos son la distancia recorrida por los estudiantes y el grado de balance racial que se logra en sus escuelas.

La técnica algorítmica para programación líneal paramétrica es una extensión natural del análisis de sensibilidad, por lo que también está basada en el método símplex.

Como se identifican los parámetros sensibles? (II)

La manera más fácil de analizar la sensibilidad de cada uno de los parámetros aij es verificar si su restricción correspondiente es de atadura sobre la solución óptima. Como x1 ≤ 4 no es una restricción de atadura, cualquier cambio suficientemente pequeño en sus coeficientes (a11 = 1, a12 = 0) no cambiará la solución óptima, así que éstos no son parámetros sensibles. Poro otro lado, tanto 2x2 ≤ 12 como 3x1 + 2x2 ≤ 18, son restricciones de atadura, por lo que al cambiar cualquiera de sus coeficientes (a21 = 0, a22 = 2, a31 = 3, a32 = 2) tendrá que cambiar la solución óptima, y así, éstos son parámetros sensibles.

Es común que se preste más atención al análisis de sensibilidad sobre los parámetros bi y cj que sobre los aij. En los problemas reales con cientos o miles de restricciones y variables, el efecto al cambiar una aij por lo general es despreciable, mientras que el cambio en una bi o en una cj puede tener un impacto real. Aún más, en muchos casos, los valores de las aij se quedan determinados por la tecnología que se está usando (a veces se les da el nombre de coeficientes tecnológicos) por lo que puede que haya muy poca ( o ninguna) incertidumbre respecto de sus valores finales. Esto resulta ventajoso ya que existen muchos más parámetros aij que bi y cj en problemas grandes.

En problemas con más de dos variables, no se puede analizar la sensibilidad de los parámetros en una gráfica como se hizo con el problema de la Windor Glass Co. Sin embargo, se puede extraer el mismo tipo de información del método símplex. Para obtenerla es preciso usar la idea fundamental que se describe en la sección 5.3 para deducir los cambios que se generan en la tabla símplex final como resultado de cambiar el valor de un parámetro en el modelo original.

Como se identifican los parámetros sensibles?

En el caso de las bi, acaba de verse que esta información está dada por los precios sombra que proporciona el método símplex. En particular si  yi* > 0, entonces la solución óptima cambia si bi lo hace, por que bi es un parámetro sensible. Sin embargo; yi* = 0 indica que la solución óptima no es sensible al menos a cambios pequeños en bi. En consecuencia, si el valor que se usa para bi es una estimación de la cantidad de recursos que se tendrán disponibles (y no una decisión de la gerencia), las bi que se deben que se deben estimar con más cuidado son aquellas con precio sombra positivos, en especial las que tienen precios sombra grandes.

Cuando el problema es de dos variables, la sensibilidad de los distintos parámetros se puede analizar con una gráfica. Por ejemplo, en la figura 4.3 ( o en la figura 3.3) se puede observar que c1 = 3 se puede cambiar a cualquier otro valor dentro del intervalo de 0 a 7(1/2) sin que la solución óptima (2, 6) cambie. (La razón es que cualquier valor de c1 dentro de este intervalo mantiene la pendiente de Z = c1x1 + 5x2 entre las pendientes de las líneas 2x2 = 12 y 3x1 + 2x2 = 18). De igual manera, si c2 =5 es el único parámetro que se cambia, puede tomar cualquier valor mayor que 2 sin que afecte la solución óptima. Asi, ni c1 ni c2 son parámetros sensibles.

Análisis de sensibilidad

Cuando se examinó la suposición de certidumbre para la programación lineal al final de la sección 3.3, se hizo notar que los valores usados para los parámetros del modelo (las aij, bi y cj que se identifican en la tabla 3.3) casi siempre son estimaciones de las cantidades cuyos verdaderos valores no se conocerán hasta que el estudio de programación lineal se lleve a la práctica en el futuro. El propósito general del análisis de sensibilidad es identificar los parámetros sensibles (esto es, aquellos que no pueden cambiar mucho sin cambiar la solución óptima) para tratar de dar mejores estimaciones que no pueden cambiar mucho sin cambiar la solución óptima) para tratar de dar mejores estimaciones para estos parámetros, y después seleccionar una solución que sea buena para toda la escala de valores posibles de esos parámetros sensibles.

Precios Sombra (III)

Ahora obsérvese en la misma figura por qué y1* = 0. La restricción sobre el recurso 1, x1 ≤ 4, no tiene ingerencia en la solución óptima (2,6), ya que existe un superávit de este recurso. Por tanto, si b1 adquiere un valor mayor que 4, no se obtendrá una nueva solución óptima con un valor mayor para Z.

Por el contrario, las restricciones sobre los recursos 2 y 3, 2x2 ≤ 12 y 3x1 + 2x2 `≤ 18 son restricciones de atadura (en las que se cumple la igualdad para la solución óptima). Debido a que la disponibilidad limitada de estos recursos (b2 = 12, b3 = 18) ata a Z para que no pueda incrementarse, tienen precios sombra positivos. Los economistas se refieren a estos recursos como bienes escasos, mientras que los recursos disponibles con superávit (como el recurso 1) son bienes libres (con precios sombra de cero).

El tipo de información que proporcionan los precios sombra es valiosa para la gerencia cuando examina la posibilidad de reasignar recursos dentro de la organización. También resulta muy útil cuando un aumento en bi se puede lograr con sólo salir a comprar un poco más del recurso. Por ejemplo, supóngase que Z representa ganancias y que las ganancias unitarias de las actividades (las cj) incluyen costos (a precios normales) de todos los recursos que se consumen; entonces, un precio sombra positivo y*i, para el recurso i significa que la ganancia total Z se puede aumentar en la cantidad yi* al comprar una unidad más de este recurso a su precio normal. Así mismo, si se tiene que pagar un precio mayor al nominal por la cantidad adicional del recurso, yi* representará el mayor precio (cantidad adicional sobre el precio normal) que vale la pena pagar.

En el problema de la Wyndor Glass Co., la gerencia ha descartado por el momento cualquier posibilidad de expansión en la capacidad de producción de las tres plantas. No obstante, las capacidades asginadas a los dos productos nuevos se pueden aumentar si se disminuye un poco más la producción de la línea actual. El departamento de investigación de operaciones estudia esta posibilidad como parte del análisis de sensibilidad.

La teoria de dualidad proporciona el fundamento teórico de los precios sombra y se describe posteriormente.

Precios Sombra (II)

Se puede verificar que estos números son correctos al observar en las figuras 3.2 y 3.3 que, sí se incrementa por separado cada bi en una unidad, el valor óptimo de Z aumentará y*i. Por ejemplo, en la figura 4.3 se muestra un aumento así para el recurso 2 al reaplicar el procedimiento gráfico que se presentó en la sección 3.2. La solucion óptima (2,6) con Z = 36, cambia a (5/3, 13/2) con Z = 37(1/2) cuando se incrementa en uno el valor de b2 (de 12 a 13), de manera que:

y2* = ΔZ = 37(1/2) - 36 = 3/2

La figura 4.3 demuestra que y2* = 3/2 es la tasa a la que aumentaría Z si se incrementara un poco b2, pero también demuestra el fenómeno general de que esta interpretación es válida nada más para aumentar pequeños. Si b2 se aumenta a más de 18 unidades, la solución óptima se queda en el punto (0,9) sin que la Z siga aumentando.

Precios Sombra (I)

Recuérdese que los problemas más comunes de programación líneal (véanse las tablas 3.2 y 3.3) pueden interpretarse como la asignación de recursos a las actividades, donde bi representa la cantidad de los respectivos recursos disponibles para las actividades bajo estudio. En muchos casos, pueden haber dudas respecto a las cantidades que estarán disponibles. Si así es, la cantidad bi que se usa en el modelo inicial (validado), en realidad puede representar una decisión inicial tentativa del gerente sobre la cantidad de recursos de la organización que se asignarán a las actividades consideradas en el modelo y no a otras actividades que el gerente considere importantes. Desde esta amplia perspectiva, algunos valores de bi se pueden incrementar en un modelo revisado sólo cuando se presenten razones poderosas en cuanto a que esta revisión será bénefica.

En consecuencia, la información sobre la contribución económica de los recursos a la medida de desempeño (Z) para el estudio en curso casi siempre será en extremo útil. El método símplex proporciona esta información en forma de "precios sombra" para los recursos respectivos.

Los precios sombra para el recurso i (denotados por yi*) miden el valor marginal de este recurso, es decir, la tasa a la que Z puede aumentar si se incrementa (un poco) la cantidad que se proporciona de este recurso bi. El método símplex identifica este precio sombra como yi* = coeficiente de la i-esima variable de holgura en el renglón (0) de la tabla símplex final.

En el problema de la Wyndor Glass Co., la tabla símplex final en la tabla 4.8 da

y1* = 0 = precio sombra del recurso 1,

y2* = 3/2 = precio sombra del recurso 2,

y3* = 1 = precio sombra del recurso 3.

en donde estos recursos son las capacidades de producción disponibles en las plantas 1, 2 y 3, respectivamente (b1 = 4, b2 =12 y b3 = 18).

Reoptimización (II)

La gran ventaja de la técnica de reoptimización sobre el hecho de resolver el problema desde el principio, es que quizá la solución óptima para el problema revisado esté mucho más cerca de la solución óptima anterior que de una solución básica factible inicial construida como siempre. Así , si se supone que las revisiones del modelo fueran moderadas, se requerirán sólo unas cuantas iteraciones para reoptimizar en lugar de cientos o tal vez miles  que pueden llevarse a cabo cuando se comienza desde el principio en problemas grandes. De hecho, las soluciones del modelo anterior y del revisado con frecuencia son las mismas, en cuyo caso, la técnica de reoptimización requiere sólo una aplicación de la prueba de optimalidad y ninguna iteración.

Reoptimización (I)

Con frecuencia, después de encontrar una solución óptima para una versión de un modelo de programación líneal, el problema debe resolverse de nuevo para un modelo ligeramente diferente. Casi siempre se tiene que resolver varias veces durante la etapa de verificación de modelo, y por lo general se hace lo mismo un gran número de veces durante las etapas de análisis posóptimo.

Una manera de hacerlo es sencillamente aplicar el método símplex desde el principio a cada nueva versión del modelo, aunque cada corrida pueda requerir, en problemas grandes cientos o miles de operaciones. Sin embargo, una forma mucho más eficiente es la de reoptimizar. La reoptimización deduce los cambios que deben introducirse a la tabla símplex final como consecuencia de los cambios en el modelo y después usa la solución óptima del modelo anterior como solución básica inicial para resolver el nuevo modelo. Si esta solución es factible para el nuevo modelo, se puede aplicar el método símplex en la forma usual, a partir de esta solución básica factible inicial. Si la solución no es factible, tal vez se pueda aplicar un algoritmo similar llamado método símplex dual para encontrar la nueva solución óptima, tras comenzar con esta solución básica inicial.

Análisis posóptimo

En los anteriores articulos se hizo hincapié en que el análisis posóptimo, el análisis que se hace después de obtener una solución óptima para la versión inicial del modelo, constituye una parte muy importante de casi todos los estudios de investigación de operaciones. Este hecho es particularmente cierto para las aplicaciones comunes de programación líneal. Esta sección está dedicada a presentar el papel que juega el método símplex al realizar este análisis.

La tabla del siguiente post resumen los pasos que se deben seguir en un análisis posóptimo en estudios de programación líneal. La última columna de esta tabla identifica algunas técnicas que emplean el método símplex. Aquí se dará una introducción breve a estas técnicas y los detalles se dejan para capítulos posteriores.

Variables sin cotas sobre los valores negativos permitidos (III)

Desde un punto de vista computacional, este enfoque tiene la desventaja de que el nuevo modelo equivalente tiene más variables que el modelo original. De hecho, si ninguna variable tuviera restricción de cota inferior, el nuevo modelo tendria el doble de variables. Por fortuna esto se puede modificar un poco para que el número de variables aumente sólo en uno, sin importar cuántas variables orginales tengan que sustituirse. Esta modificación se hace al reemplazar cada variable de este tipo, xj por


xj = x'j - x'', donde x'j ≥ 0, x'' ≥ 0

donde x'' es la misma variable para toda j relevante. En este caso, la interpretación de x'' es que -x'' es el valor actual de la variable original negativa más grande (en términos de valor absoluto), entonces, x'j es la cantidad por la que xj excede este valor. Con esto, el método símplex puede hacer que algunas x'j adquieran valores mayores a cero aun cuando x'' >0.

Variables sin cotas sobre los valores negativos permitidos (II)

PAra ilustrar esto se usará el mismo ejemplo que el caso de la variable acotada, pero ahora supóngase que la restricción x1 ≥ -10 no está incluida en el modelo original, ya que es claro que no influye en la solución óptima. (En algunos problemas, ciertas variables no necesitan tener cotas inferiores explícitas cuando las restricciones funcionales impiden valores menores.) Entonces, antes de aplicar el métod símplex, x1 se reemplaza por la diferencia,

Variables sin cotas sobre los valores negativos permitidos (I)

En caso de que xj no tenga una cota inferior en el modelo formulado, se requiere un cambio distinto: xj se sustituye en todo el modelo por la diferencia de dos nuevas variables no negativas

Como xj(+) y xj(-) pueden tomar cualquier valor no negativo, esta diferencia (xj+ - xj-) puede ser cualquier valor (positivo o negativo), por lo que es una sustitución legítima para xj, después de estas sustituciones, el método símplex puede proceder con variables  que son no negativas.

Las nuevas variables xj+ y xj- tienen una interpretación sencilla. Por la definición geométrica de solución factible en un vértice, cada solución básica factible  para la nueva forma del modelo necesariamente tiene la propiedad de que o bien xj* = 0 o xj- (o ambas); por tanto, en la solución óptima obtenida por el método símplex, de manera que xj+ representa la parte positiva de xj y xj- su parte negativa (como lo sugieren los superíndices).

Variables con una cota sobre los valores permitidos (II)

Para ejemplificar, supóngase que la tasa de producción actual para el producto 1 en el problema de la Wyndor Glass Co. es 10. Con la definición que se acaba de dar para x1, el modelo completo en este punto es el mismo que el dado en la sección 3.1, salvo que la restricción de no negatividad x1 ≥ 0 se reemplaza por

x1 ≥ -10

Para obtener el modelo equivalente que se necesita para el método símplex, la variable de decisión se redefinirá como la tasa de producción total del producto 1

x1 = x1 + 10

lo que lleva a los siguientes cambios en la función objetivo y las restricciones:

Variables con una cota sobre los valores permitidos (I)

Considérese cualquier variable de decisión xj que puede tener varios negativos, pero nada más aquellos que satisfacen una restricción de forma

xj ≥ Lj

donde Lj es una constante negativa. Esta restricción se puede convertir en una de no negatividad haciendo el cambio de variables.

xí = xj - Lj de manera que xj ≥ 0.

Entonces (xj + Lj) sustituye a xj en el modelo y al nueva variable de decisión xj no puede ser negativa.

Variables que pueden ser negativas

En la mayor parte de los problemas prácticos, los valores negativos para las variables de decisión no tienen significado físico, por lo que es necesario incluir las restricciones de no negatividad en la formulación del módelo de programación líneal. Sin embargo, esto no ocurre siempre.

Como ejemplo, supóngase que en el problema de la Wyndor Glass Co. El producto 1 ya está en producción y que la primera variable de decisión x1 representa el incremento en la tasa de producción. Entonces, un valor negativo de x1 indicaría que debe disminuirse la producción más alta del nuevo producto 2, con lo que se permitirían valores negativos de x1 en el modelo.

Como el procedimiento para determinar la variable básica que sale requiere que todas las variables tengan restricción de no negatividad, cualquier problema que contanga variables que puedan adquirir valores negativos debe convertirse en un problema equivalente que emplee sólo variables no negativas. Por fortuna, se puede hacer esta conversión. La modificación que requiere cada variable depende de si tiene o no una cota inferior (negativa) sobre los valores permitidos. Se presentará cada caso.

Sin soluciones factibles (II)

Por fortuna, la técnica de las variables artificiales proporciona algunas señales que indican que esto ha ocurrido:

Si el problema original no tiene soluciones factibles, entonces cualquier solución óptima obtenida con el método de la M o en la fase 1 del método de las dos fases lleva a una solución final que contiene al menos una variable artificial mayor que cero. De otra manera,todas son iguales a cero.
con fines didácticos, cámbiese la primera restricción del ejemplo de terapia de radiación como sigue:

0.3x1 + 0.1x2 ≤ 2.7 → 0.3x1 + 0.1x2 ≤ 1.8

con lo que el problema ya no tiene soluciones factibles. Si se aplica el método de la M como antes (vease la tabla 4.12) se obtiene la tabla símplex que se muestra en la tabla 4.15 (La fase 1 del método de las dos faces conduce a la misma tabla símplex, excepto que cada expresión con M se reemplaza solo con el factor multiplicativo) En un caso normal el método de la M indicaría que la solución óptima es (3, 9, 0, 0, 0, 0.6). Sin embargo, como una variable artificial x6 = 0.6 > 0, el mensaje real aquí es que el problema no tiene soluciones factibles.

Sin soluciones factibles (I)

Hasta aquí, esta sección se ha ocupado más que nada del problema elemental de identificar la solución básica factible inicial cuando no se dispone de una obvia. Se ha visto que la técnica de la variable artificial construye un problema artificial y obtiene una solución básica factible inicial para este problema revisado. El método de la M o el de las dos fases permiten al método símplex comenzar su recorrido hacia las soluciones básicas factibles y por último hacia la solución óptima del problema original.

No obstante, se debe estar consciente d un obstáculo que se puede presentar. Puede no existir una elección obvia para la solución básica factible inicial por la poderosa razón de que no exista soluciones factibles!. Al construir una solución factible artificial, no hay nada que impida al método símplex proceder como siempre e incluso informar que encontró una supuesta solución óptima.

Resumen del método de las dos fases (VI)

DAdo que los términos Mx4 + Mx6, dominan a los términos 0.4x1 y 0.5x2 en la función objetivo para el método de la M, esta función objetivo es esencialmente equivalente a la de la fase 1 mientras x4 y/o x6 sean mayores que cero. Entonces, cuando tanto x4 = 0 como x6 = 0, la función objetivo del método de la M se vuelve completamente equivalente a la función objetivo de la fase 2.

Debido a estas equivalencias virtuales en la función objetivo, el método de la M y el de las dos fases tienen casi siempre la misma secuencia de soluciones básicas factibles. La única excepción posible ocurre cuando existe un empate para la variable básica entrante en la fase 1 del método de las dos fases, como sucedió en la tercera tabla símplex de la tabla 4.13 son casi idénticas con la única diferencia de que los factores multiplicativos de M en la tabla 4.12 se convierten en cantidades solas en los puntos correspondientes de la tabla 4.13. En consecuencia, no se contaba con los factores aditivos que rompieron el empate para la variable básica entrante en la tercera tabla símplex de la tabla 4.12 para romper este mismo empate de la tabla 4.13. El resultado en este ejemplo fue una iteración adicional en el método de las dos fases, aunque en general, la ventaja de contar con los factores aditivos es mínima.

El método de las dos fases sigue los pasos del método de la M usando sólo los factores multiplicativos en la fase 1 y eliminando las variables artificiales en al fase 2. (El método de la M puede combinar los factores multiplicativos y aditivos asignando un valor muy grande a M,pero esto podría crear problemas con inestabilidad númerica) Por estas razones es común que cuando se trate de paquetes de computadora se use el método de las dos fases.

Resumen del método de las dos fases (V)

Si el empate para la variable básica entrante que surgió en la penúltima tabla de la tabla 4.13 se hubiera roto de otra manera, entonces la fase 1 habría ido directamente de (8,3) a (7.5, 4.5). Después de utilizar (7.5, 4.5) para establecer la tabla símplex inicial para la fase 2, la prueba de optimalidad habría revelado que esta solución es óptima y no se habría realizado ninguna interacción.

Resulta interesante comparar los métodos de la M y de las dos fases. Se comenzará por sus funciones objetivo

Método de la M: Minimizar                Z = 0.4x1 + 0.5x2 + Mx4  + Mx6
Método de dos fases:

Fase 1: Minimizar                             Z = x4 + x6
Fase 2: Minimizar                             Z = 0.4x1 + 0.5x2

Resumen del método de las dos fases (IV)

Al principio de la tabla 4.14 se muestra la tabla símplex inicial que resulta para la fase 2. Al aplicar el método símplex se llega en una iteración a la solución óptima que se muestra en la segunda tabla símplex, (x1,x2,x3,x5) = (7.5, 4.5, 0 , 0.3).

Ahora obsérvese lo que el método de las dos fases ha hecho en la gráfica de la figura 4.2. Usando nada más (x1,x2), la secuencia de soluciones en un vértice que se obtuvieron en las tablas 4.13 y 4.14 es

Fase 1: (0,0) → (9,0) → (8,3) → (6,6)
Fase 2: (6,6) → (7.5, 4.5)

Notese que todas estas soluciones en la fase 1 son no factibles (excepto para el problema revisado) hasta la última. La fase 2 maneja entonces sólo soluciones factibles en un vértice.

Resumen del método de las dos fases (III)

Para la fase 2, se eliminan x4 y x6. Para comenzar con el método símplex a partir de la solución básica factible (x1,x2,x3,x5) = (6,6,0.3,0), los renglones 1-3 de la última tabla símplex en la tabla 4.13 están listos y en la forma apropiada de eliminación de Gauss. Sin embargo, ahora es necesario insertar en el renglón 0 la función objetivo del problema original en esta misma forma apropiada. La serie de pasos para obtener este nuevo renglón 0 (incluyendo el uso de los renglones 1 a 3 para eliminar x1 y x2 del renglón 0) se muestran a continuación.

Resumen del método de las dos fases (II)

La tabla 4.13 muestra el resultado de aplicar la fase 1 al ejemplo de terapia de radiación [El renglón 0 en la tabla  símplex inicial se obtiene al convertir  minimizar Z = x4 + x6 a maximizar (-Z) = -x4 -x6, y después usar la eliminación gaussiana para eliminar x4 y x6 de -Z + x4 + x6 =0] En la penúltma tabla símplex existe un empate para la variable básica entrante entre  x3 y x5 que se rompe arbitrariamente en favor de x3. La solución obtenida al final de al fase 1 es, entonces, (x1, x2, x3, x4, x5, x6) = (6, 6, 0.3, 0, 0, o) o despues de eliminar x4 y x6 (x1, x2,x3,x5) = (6,6,0.3,0)

Según se afirmó en el resumen, esta solución de la fase 1 es sin duda una solución básica factible para el problema original puesto que es la solución (después de hacer x5 = 0) a las restricciones originales en la formula aumentada.

(1)   0.3x1 + 0.1x2 + x3        =2.7
(2)   0.5x1   + 0.5x2              =6
(3)   0.6x1 + 0.4x2          -x5 = 6

Resumen del método de las dos fases (I)

Paso incial: 

revisión de la restricción del problema original introduciendo variables artificiales según se necesite para obtener una solución básica factible inicial obvia para el problema revisado.

Fase 1: uso del método símplex para resolver el problema de programación lineal:

Minimizar = Z = suma de las variables artificiales, sujeta a las restricciones revisadas.

La solución óptima que se obtiene para este problema (con Z = 0) será una solución básica  factible para el problema original.

Fase 2: eliminaciónde las variables artificiales ( de todas formas ahora todas valen cero) Comenzando con la solución básica factible que se obtuvo al final de la fase 1, usar el método símplex para resolver el problema original.

Método de las dos fases

Para el ejemplo de terapia de radiación que se acaba de resolver en la tabla 4.12, el método de la M utiliza la siguiente función objetivo ( o su equivalente en forma de minimización) a través de todo el procedimiento.

Método de la M: Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6

En contraste, el método de las dos fases puede eliminar la M usando dos funciones objetivo distintas.

Método de dos fases:

Fase 1: Minimizar Z = x4+ x6 (hasta que x4 = 0, x6 = 0)

Fase 2: Minimizar Z = 0.4x1 + 05x2 (con x4 = 0, x6 = 0)

Antes de resolver el ejemplo de esta manera se hará un resumen de las caracteristicas generales.

Detecta el lector algún problema en este sistema de ecuaciones para iniciar el método símplex (III)

En las primeras dos soluciones en un vértice, tanto x4 como x6 son mayores que cero, lo que indica que se violan tanto 0.5x1 + 0.5x2 = 6 como 0.6x1 + 0.4x2 ≥ 6. El método de la M tiene éxito en llevar x6 a nivel cero en (8,3) de manera que 0.6x1 + 0.4x2 ≥ 6 se satisface. Después, x4 también adquiere valor de cero en (7.5, 4.5), con lo que 0.5x1 + 0.5x2 =6 también se satisface y se obtiene la primera solución factible para el problema original. Por casualidad, esta primera solución factible es también óptima por lo que no es necesario realizar más iteraciones.

En otros problemas con variables artificiales, puede ser que haya que realizar iteraciones adicionales para llegar a una solución óptima después de obtener la primera solución factible para el problema original. Así, puede pensarse que el método de la M tiene dos fases. En la primera, todas las variables artificiales se hacen cero (debido a la penalización de M por unidad al ser mayores que cero) con el fin de obtener una solución básica factible inicial para el problema original. En la segunda fase todas las variables artificiales se mantienen en cero (por la misma razón) mientras que el método símplex genera una secuencia de soluciones básicas factibles que llevan a la solución óptima.

El método de las dos fases se describe a continuación es un procedimiento directo para realizar estas dos fases sin siquiera introducir M de una mera explicita.

Detecta el lector algún problema en este sistema de ecuaciones para iniciar el método símplex (II)

La tabla símplex inicial que resulta, lista para comenzar el método símplex se muestra en la tabla 4.12 Al aplicar el método símplex en la forma acostrumbrada se obtiene la secuencia de tablas símplex que se muestran en el resto de la tabla 4.12. En cuanto a la prueba de optimalidad y la elección de la variable básica entrante en cada iteración, las cantidades que incluyen M se trataron justo como se explicó para la tabla 4.11 En particular, siempre que M está presente, sólo se usa su factor multiplicativo a menos que haya un empate, en cuyo caso el empate se rompe usando los factores aditivos correspondientes. Un empate de este tipo ocurre en la última selección de la variable básica entrante en donde los coeficientes de x3 y x5 en el renglón 0 tienen el mismo factor multiplicativo, -(5/3) al comprar los factores aditivos, (11/6)<(7/3) se selecciona x5 como la variable básica entrante.

Ahora se puede observar lo que el método de la M ha hecho que la gráfica de la figura 4.2.

Al usar nada más las variables de decisión originales (x1, x2) la secuencia de soluciones en un vértice que se obtiene en la tabla 4.12 es:

(0,0) → (9,0) → (8,3) → (7.5, 4.5)

Detecta el lector algún problema en este sistema de ecuaciones para iniciar el método símplex (I)

Puede aplicarse a esta ecuación (0) la prueba de optimalidad y el procedimiento para elegir una variabla básica entrante? No! Ocurre que el sistema de ecuaciones todavia no está en la forma apropiada de eliminación de Gauss (en la que cada variable básica se elimina de todas las ecuaciones excepto de su propia ecuación en la que debe tener coeficiente +1). Las ecuaciones (1) a (3) están bien, pero todavía es necesario eliminar las variables básicas x4 y x6 de la ecuación (0) con la eliminación gaussiana. Como tanto x4 como x6 tienen coeficiente M, se tiene que restar de la ecuación (0) M veces la ecuación (2) y M veces la ecuación (3). Por ejemplo, el coeficiente de x1 en la ecuación (0) se convierte en 0.4 - 0.5M - 0.6M = -1.1M + 0.4M, de manera que M se maneja como un número real (muy grande) cuyo valor es fijo pero no especificado. A continuación se resumen los cálculos de todos los coeficientes (y el lado derecho), en donde los vectores son los renglones relevantes de la tabla símplex correspondiente al sistema de ecuaciones anterior

Solución del ejemplo de terapia de radiación

El ejemplo está casi listo para aplicarle el método símplex. Si se usa la forma de maximización que se acaba de obtener, el sistema de ecuaciones completo es:

(0) -Z + 0.4x1 + 0.5x2 + Mx4 +Mx6 = 0
(1) 0.3x1 + 0.1x2 + x3 = 2.7
(2) 0.5x1 + 0.5x2 + x4 = 6
(3) 0.6x1 + 0.4x2 -x5 +x6 = 6

Las variables básicas (x3,x4,x6) en la solución inicial básica factible (para este problema revisado) se muestran en negritas

Minimizacion (II)

Entonces, en el ejemplo de terapia de radiación se debe hacer el siguiente cambio en la formulación:

Minimizar Z = 0.4x1 + 0.5x2
→ Minimizar (-Z) = -0.4x1 - 0.5x2

Después de introducir las variables artificiales (x4,x6) y de aplicar el método de la M la conversión correspondiente es:

Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6
→ Minimizar (-Z) = -0.4x1 - 0.5x2 - Mx4 - Mx6

Minimizacion (I)

Una manera directa de Minimizar Z con el método símplex es cambiar los roles de los coeficientes negativos y positivos en el renglón 0, tanto para la prueba de optimalidad como para la parte 1 del paso iterativo. Sin embargo, en lugar de cambiar las instrucciones del método símplex se presentará una manera sencilla de convertir cualquier problema de minimización en un problema equivalente de maximización:

es decir, las dos formulaciones llevan a la (s) misma (s) solución(es) óptima(6)

La razón por la que las dos formulaciones son equivalentes es que entre más pequeña es Z, más grande es (-Z), así que la solución que da el menor valor de Z dentro de la región factible, también debe dar el mayor valor para (-Z) en esta región.

Lado derecho negativo (II)

Como siempre, al introducir variables artificiales, la región factible se amplia. La restricción original permitía sólo soluciones que estuvieran arriba de o sobre la frontera de restricción. 0.6x1 + 0.4x2 = 6. Ahora permite también soluciones que estén por debajo de la frontera de restricción, ya que tanto x5 como x6 tienen sólo la restricción de no negatividad, por lo que su diferencia (x6-x5) puede ser cualquier número positivo. Ninguna solución queda fuera, asi, el efecto temporal de introducir x6 es eliminar la restricción en el problema revisado. (La restricción se mantiene en el sistema de ecuaciones por que volverá a ser relevante más tarde, una vez que el método de la M haga que x6 sea cero).

Se ha revisado dos veces el problema original, ampliando su región factible, primero con la introducción de la variable artificial x4 en la restricción de igualdad (0.5x1 + 0.5x2 + x4 = 6), y ahora al introducir x6. En consecuencia, la región factible para el problema revisado es el poliedro completo de la figura 4.2 cuyos vértices son (0.0), (9,0) (7.5,4.5) y (0,12).

Quizá el lector observó que se tomó un camino con rodeos al convertir la tercera restricción de su forma original, 0,6x1 + 0.4x2 ≥6, a su version final 0.x1 + 0.4x2 - x5 + x6 = 6. De hecho, se multiplicó toda la ecuación por (-1) dos veces! Ahora que se ha visto la motivación que llevó a la forma final se puede establecer un camino corto:

0.6x1 + 0.4x2 ≥ 6
→ 0.6x1 + 0.4x2 -x5 = 6 (x5 ≥ 0)
→ 0.6x1 + 0.4x2 -x5 + x6 = 6 (x5 ≥ 0, x6 ≥ 0)

En esta forma, x5 se llama variable de superávit, puesto que resta lo que le sobra al lado izquierdo para convertir la desigualdad en una ecuación equivalente.

Lado derecho negativo

Se recordará que el método símplex se presentó bajo la suposición de que bi > 0 para toda i = 1,2,.....m. Esta suposición permitió elegir las variables de holgura como las variables básicas iniciales (iguales al lado derecho) y obtener una solución básica factible no degenerada.

Partiendo de esto, se hizo incapié en la sección 4.5 en que no es necesario evitar la degeneración (variables básicas igual a cero). Sin embargo, un lado derecho negativo como el de la tercera restricción.

- 0.6x1 - 0.4x2 + x5 = -6

daria un valor negativo para la variable de holgura (x5 = -6) en la solución inicial (donde x1 = 0, x2 = 0), lo que violaría la restricción de no negatividad para esta variable. Al multiplicar toda la ecuación (-1) el lado derecho se vuelve positivo:

-0.6x1 + 0.4x2 - x5 = 6,

pero también cambia el coeficiente de la variable de holgura -1, por lo que de todas formas la variable sería negativa. Sin embargo, en esta forma la restricción se puede considerar una restricción de igualdad con un lado derecho no negativo y se puede aplicar la técnica de la variable artificial justo como se describio. Sea x6 la variable artificial no negativa para esta restricción, su forma final es

0.6x1 + 0.4x2 - x5 +x6 = 6

en donde x6 se usa como la variable básica inicial (x6 = 6) para esta ecuación y x5 comienza como variable no básica. El método de la M se aplicará también en la misma forma que antes, como se verá más adelante.

Restricciones en forma de igualdad (VIII)

Muy pronto se mostrará la solución completa este problema con el método símplex  incluida la secuencia de soluciones en los vértices que se obtienen, pero primero ha de convertirse el modelo en la forma apropiada  para poder aplicarlo. Dos ajustes consisten en introducir una variable de holgura (x3 ≥0) en la primera restriccion.

0.3x1 + 0.1x2 ≤ 2.7 → 0.3x1 + 0.1x2 + x3 = 2.7,

y una variable artificial (x4 ≥ 0) enla restriccion de igualdad.

0.5x1 + 0.5x2 = 6 → 0.5x1 + 0.5x2 + x4 = 6

El efecto temporal al introducir x4 en esta restricción (antes de que el método de la M la obligue a tener valor de cero) es permitir las soluciones como 0.5x1 + 0.5x2 ≤6. Si también se toman en cuenta las otras restricciones, la región factible para el problema revisando se expande hasta incluir todo el triángulo cuyos vértices son (6,6), (7.5, 4.5) y (8,3).

Los ajustes que quedan para las otras formas no estándar en el modelo se describen a continuación.

Restricciones en forma de igualdad (VII)

En la figura 4.2 se repite también la solución gráfica de este ejemplo (presentada en la figura 3.7) en una forma un poco distinta. Las tres líneas en la figura, junto con los dos ejes constituyen las cinco restricciones del problema. los puntos dibujados en las intersecciones de cada par de líneas son las soluciones en los vértices. Las únicas dos soluciones factibles en un vértice son (6,6) y (7.5, 4.5) y la región factible es el segmento de línea que conecta a estos dos puntos. La solución óptima es (x1,x2) = 97.5,4.5) con Z = 5.25.