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.

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.