viernes, 28 de febrero de 2014

Propiedad de las soluciones básicas complementarias

Cada solución básica en el problema primal tiene una solución básica complementaria en el problema dual, en donde los valores respectivos de la función objetivo (Z y yo) son iguales. Dado el reglón 0 de la tabla símplex para la solución básica primal, la solución básica dual complementaria (y, z- c) se encuentra como se muestra en la tabla 6.4.

jueves, 27 de febrero de 2014

Soluciones básicas complementarias (II)

Gracias a la propiedad de simetría que se mencionó en la sección 6.1 (y a la asociación directa entre las variables que se muestran en la tabla 6.7), la correspondencia entre las soluciones básicas en el primal y el dual es simétrica. Aún más, un par de soluciones básicas complementarias tiene el mismo valor para la función objetivo; este valor corresponde a yo en la tabla 6.4.

Se resumirán las conclusiones sobre la correspondencia entre las soluciones básicas del primal y el dual, en donde la primera propiedad amplía la propiedad de soluciones complementarias de la sección 6.1 a las formas aumentadas de los dos problemas y después a cualquier solución básica (factible o no) en el problema primal.

miércoles, 26 de febrero de 2014

Soluciones básicas complementarias (I)

Una de las relaciones más importantes ente los problemas primal y dual es la correspondencia directa entre sus soluciones básicas. La clave de esta correspondencia es el renglón 0 de la tabla símplex para la solución básica primal, como se muestra en las tablas 6.4 o 6.5. Se puede obtener ese renglón 0 a partir de cualquier solución básica primal, factible o no, empleando las fórmulas dadas en la parte inferior de la tabla 5.7.


Obsérvese de nuevo en las tablas 6.4 y 6.5 cómo se puede leer, directamente en el renglón 0, la solución completa para el problema dual (inclusive las variables de superávit). Entonces, debido a su coeficiente en el renglón 0, cada variable del problema primal tiene una variable asociada en el problema dual; esto se resume en la tabla 6.7.

Un concepto importante es que la solución del dual que se lee en el renglón 0 también debe ser una solución básica!. Esto se debe a que las m variables básicas del problema primal necesita tener coeficiente cero en el renglón 0, lo que significa que el valor de las m variables duales asociadas debe ser cero, es decir, deben ser variables no básicas en el problema dual. Los valores de las n variables (básicas) restantes serán entonces la solución simultánea del sistema de ecuaciones dado al principio de la sección 5.3 identifica su solución para los valores de z-c y y como elementos correspondientes en el renglón 0.

martes, 25 de febrero de 2014

Relaciones primal-dual

Como el problema dual es de programación lineal, también tiene soluciones en los vértices. Aún más, empleando la forma de igualdades del problema, estas soluciones se pueden expresar como soluciones básicas. Puesto que las restricciones funcionales tiene la forma ≥, la forma de igualdades se obtiene al restar el superávit (en lugar de agregar la holgura) del lado izquierdo de cada restricción j (j= 1,2,....,n)^1. Este superávit es:

Así, (zj-cj) asume el papel de variable de superávit para la restricción j (o su variable de holgura si la restricción se multiplica por -1). Por tanto, cada solución en un vértice (y1, y2,...., ym) conduce a una solución básica (y1, y2, ....., ym, z1 - c1, z2 - c2, ....., zn - cn) al usar esta expresión para (zj - cj). Puesto que la forma de igualdades tiene n restricciones funcionales y (n+m) variables, cada solución básica tiene n variables básicas y m variables no básicas. (Nótese que los papeles de m y n se han invertido, como lo indica la tabla 6.3, porque las restricciones duales corresponden a las variables primales y las variables duales a las restricciones primales.).

lunes, 24 de febrero de 2014

Interpretación del método símplex (II)

De igual manera, si la variable de holgura x(n+1) es no básica, de forma que la asignación total bi del recurso i se está usando, entonces yi es la contribución actual a la ganancia por parte de este recurso sobre una base marginal. Así, si yi < 0, la ganancia se puede aumentar al disminuir el uso de este recurso (es decir, al aumentar x(n+i)). Si yi ≥ 0, vale la pena continuar con el uso total de este recurso.

En efecto, lo que hace el método símplex es examinar todas las variables no básicas para ver cuáles pueden proporcionar un uso más ventajoso de los recursos al aumentarlos. Si ninguna puede, es decir, si ningín cambio o reducción factible en la asignación actual propuesta de los recursos puede aumentar la ganancia, la solución actual será óptima. Si una o más variables pueden aumentarla, el método símplex selecciona aquella que, si se aumenta en una unidad, es la que da el mayor incremento a la ganancia. Después, el valor de esta variable (la variable básica entrante) realmente aumenta tanto como puede hasta que los valores marginales de los recursos cambian. El resultado de este incremento es una nueva solución básica factible con un nuevo renglón 0 (solución dual), y se repite el proceso completo.

Para reafirmar la comprensión de esta interpretación del método símplex, se sugiere al lector que lo aplique al problema de la Wyndor Glass Co., y recurra tanto a la figura 3.2 como a la tabla 4.8 (Véase el problema 6)

La interpretación económica del problema dual expande en forma considerable la habilidad para analizar el problema primal. Sin embargo, ya se vio en la sección 6.1 que esta interpretación es sólo una ramificación de las relaciones entre los dos problemas. En la sección siguiente se profundizará en estas relaciones

domingo, 23 de febrero de 2014

Interpretación del método símplex (I)

La interpretación del problema dual proporciona también una interpretación económica de lo que hace el método símplex en el problema dual. La meta del símplex es encontrar cómo usar los recursos disponibles en la forma más redituable posible. Para alcanzar esta meta, deberá llegarse a una solución básica factible que satisfaga todos los requisitos sobre el uso provechoso de los recursos (las restricciones del problema dual). Estos requisitos comprenden la condición de optimalidad en el algoritmo. Para cualquier solución básica factible dada, los requerimientos (restricciones duales) asociados con las variables básicas se satisfacen en forma automática (con la igualdad). Sin embargo, aquellos asociados con las variables no básicas pueden o no quedar satisfechos.

En particular, si una variable original xj es no básica y por ende la actividad j no se está realizando, la contribución actual a la ganancia debida a esos recursos, que se requeriría para emprender cada unidad de la actividad j,


puede ser más pequeña (<) o más grande (≥) que la ganancia unitaria cj que puede obtenerse de dicha actividad. Si es menor, de manera que (zj - cj) < 0 en el renglón 0 de la tabla símplex, entonces estos recursos se pueden usar en forma más ventajosa si se inicia con esta actividad. Si es mayor, estos recursos ya habrán sido asignados en otra parte con mayor provecho, por lo que no deben distraerse de la actividad j.

sábado, 22 de febrero de 2014

Interpretación del problema dual (VI)

(Ésta es una versión de la propiedad de holgura complementaria que se estudiara en la siguiente sección.) La interpretación económica de la primera afirmación es que siempre que una actividad j opere a un nivel estrictamente positivo (xj > 0), el valor marginal de los recursos que consume debe ser igual (en contraposición a exceder ) a la ganancia unitaria de esta actividad. La segunda afirmación indica que el valor marginal del recurso i es cero (yi =0) siempre que las actividades (x(n+i) >0 ) no se acaben la reserva de este recurso. En terminología económica, un recurso de este tipo es un "bien gratis"; el precio de los bienes que tienen una sobre disponibilidad debe ser cero por la ley de la oferta y la demanda. Este hecho justifica la interpretació de la función objetivo para el problema dual como la minización del valor de los recursos consumidos, en lugar de los asignados.

viernes, 21 de febrero de 2014

Interpretación del problema dual (V)

El objetivo

puede verse como la minización del valor total implícito de los recursos consumidos por las actividades.

Esta interpretación se puede afinar un poco si se toma en cuenta la diferencia entre las variables básicas y las no básicas en el problema primal para cualquier solución básica factible dada (x1, x2, ........,x(m+n) ). Recuérdese que las variables básicas ( las únicas que pueden tomar valores distintos de cero) siempre tiene coeficiente cero en el renglón 0. Entonces, haciendo referencia de nuevo a la tabla 6.4 y a la ecuación correspondiente zj.


jueves, 20 de febrero de 2014

Interpretación del problema dual (IV)

De igual manera, la interpretación de las restricciones de no negatividad es la siguiente:

yi ≥ 0 dice que la contribución a la ganancia por parte del recurso i(i = 1,2,...., m) debe se no negativa, de lo contrario sería mejor no usar este recurso en absoluto.

miércoles, 19 de febrero de 2014

Interpretación del problema dual (III)

Esta misma mezcla de recursos (y más) tal vez se pueda usar en otras formas, pero no debe considerarse ningún otro uso si es menos redituable que una unidad de la actividad j. Al interpretar cj como la ganancia unitaria debida a la actividad j, cada restricción funcional en el problema dual se intercepta como sigue:

Σ^m(i=1) aijyi ≥ cj dice que la contribución actual a la ganancia de la mezcla anterior de recursos debe ser, por lo menos, tanto como si fuera utilizada por una unidad de la actividad j; de otra manera no se estaría llevando a cabo la mejor utilización de estos recursos.

Interpretación del problema dual (II)

En otras palabras, las yi (o yi* en la solución óptima) no son otra cosa que los precios sombra presentados en la sección 4.7.

Esta interpretación de las variables duales lleva a la interpretación del problema dual completo. En especial, como cada unidad de ala actividad j en el problema primal consume aij unidades del recurso i,



Σ(i=1)^ aijyi se interpreta como la contribución actual a la ganancia de esa mezcla de recursos que se consumiría si se usara una unidad de laactividad j (j = 1,2,...., n)

lunes, 17 de febrero de 2014

Interpretación del problema dual

Para ver cómo la interpretación del problema primal conduce a una interpretación económica del problema dual, nótese en la tabla 6.4 que yo es el valor de Z (ganancia total) en la iteración actual. Como

yo = b1y1 + b2y2 + ........+ bmym

cada biyi puede interpretarse como la contribución a la ganancia por disponer de bi unidades del recurso i para el problema primal. Así.
yi se interpreta como la contribución a al ganancia por unidad del recurso i(i = 1,2,.....m), cuando se usa el conjunto actual de variables básicas para obtener la solución primal.



domingo, 16 de febrero de 2014

Interpretación económica de dualidad

La interpretación económica de la dualidad se basa directamente en la interpretación más frecuente del problema primal (problema de programación lineal en nuestra forma estándar) presentada en la sección 3.2. Para refrescar la memoria, se ha resumido esta interpretación en la tabla 6.6.

sábado, 15 de febrero de 2014

Aplicaciones Teoría Dual (II)

En la sección 9.2 se presenta el método símplex, que es una de las aplicaciones más importantes de la propiedad de soluciones complementarias. Este algoritmo opera sobre el problema primal como si estuviera aplicando el método símplex en forma simultánea al problema dual, lo que puede realizarse gracias a esta propiedad. Debido a que en la tabla símplex se invierten los papeles del renglón 0 y la columna del lado derecho, el método dual símplex requiere que el renglón 0 comience y permanezca no negativo mientras que el lado derecho comienza con algunos valores negativos (las iteraciones subsecuentes procuran alcanzar la no negatividad en el lado derecho). Por tanto, en ocasiones se usa este algoritmo por resultar más conveniente establecer la tabla inicial en esta forma que en la requerida por el método símplex. Lo que es más, con frecuencia se usa para la reoptimización (presentada en la sección 4.7) pues algunos cambios en el modelo original conducen a una tabla final revisada que se ajusta a esta forma. Esta situación es común en cierto tipo de análisis de sensibilidad, como se verá más adelante en este capítulo.

En términos generales, la teoría de dualidad juega un papel central en el análisis de sensibilidad. Su importancia es el tema de la sección 6.5.

Otra aplicación importante es su uso en la interpretación económica del problema dual y la visión que se obtiene para el análisis del problema primal. Ya se dio un ejemplo cuando se presentaron los precios sombra en la sección 4.7. La siguiente sección describe cómo se extiende esta interpretación a todo el problema dual y después al método símplex.

viernes, 14 de febrero de 2014

Aplicaciones Teoría Dual (I)

Como acaba de establecerse, una aplicación importante de la teoría de dualidad es que puede resolverse directamente el problema dual mediante el método símplex, con el fin de identificar una solución óptima para el problema primal. En la sección 4.8 se vio que el número de restricciones funcionales afecta mucho más el esfuerzo computacionales del método símplex que el número de variables. Si m > n, de manera que el problema dual tiene menos restricciones funcionales (n) que el problema primal (m), entonces, si se aplica el método símplex al problema dual y no al primal, tal vez se logre una considerable reducción del esfuerzo computacional.

Las propiedades de dualidad débil y fuerte describen las relaciones clave entre los problemas primal y dual. Una aplicación útil es la evaluación de una solución propuesta para el problema primal. Por ejemplo, supóngase que x es una solución factible que se ha propuesto factible y tal que cx = yb. En este caso, x debe ser óptimo, !sin que sea necesario aplicar el método símplex!


Aun cuando cx < yb, de todas maneras yb proporciona una cota superior sobre el valor óptimo de Z, de manera que si (yb - cx) es pequeño, los factores intangibles que favorecen a x pueden conducir a que ésta se elija sin dedicarle más esfuerzo.

jueves, 13 de febrero de 2014

Resumen de las relaciones primal-dual (V)

Propiedad de simetría: para cualquier problema primal y su problema dual, las relaciones entre ellos deben ser simétricas debido a que el dual de este problema dual es este problema primal.

Así, todas las propiedades anteriores se cumplen sin importar cúal de los dos problemas se etiqueta como problema primal. (La propiedad de dualidad débil requiere que el problema primal se exprese o reexprese en la forma de maximización y el problema dual en la forma de minimización.) En consecuencia, el método símplex se puede aplicar a cualquiera de los dos problemas e identificará al mismo tiempo las soluciones complementarias (y en últimas instancia una solución complementaria óptima) para el otro problema.

miércoles, 12 de febrero de 2014

Resumen de las relaciones primal-dual (IV)

Propiedad de soluciones complementarias óptimas: al final de cada iteración, el método símplex identifica simultáneamente una solución óptima x* para el problema primal y una solución óptima complementaria y* para el problema dual (que se encuentra en el renglón 0 como los coeficientes de las variables de holgura), en donde:

cx* = y*b

Los valores de yi*son los precios sombra para el problema primal.

Por ejemplo, la iteración final da x* = [2,6]^T y y* = [0,3/2,1], con cx* = 36 = y*b.

En la sección 6.3 se analizarán con la más detenimiento algunas de estas propiedades. Se verá que la propiedad de soluciones complementarias se puede extender mucho más. En particular, después de introducir las variables de holgura y de superávit en ambos problemas, toda solución básica en el problema primal tiene una solución básica complementaria en el problema dual, en donde el método símplex identifica los valores de las variables de superávit en el problema dual como (zj - cj) en la tabla 6.4. Este resultado conduce después a la propiedad adicional de holgura complementaria que relaciona las variables básicas de un problema con las no básicas del otro (tablas 6.7 y 6.8) pero después se estudiará más al respecto.

En la sección 6.4 después de describir cómo se construye el problema dual cuando el problema primal no se encuentra en nuestra forma estándar, se analizará otra propiedad útil que se resume.

martes, 11 de febrero de 2014

Resumen de las relaciones primal-dual (III)

Propiedad de soluciones complementarias: en cada iteración, el método símplex identifica simultáneamente una solución factible en un vértice, x, para el problema primal y una solución complementaria y para el problema dual (que se encuentra en el renglón 0, como los coeficientes de las variables de holgura), donde

cx = yb

Si x no es óptima para el problema, primal, entonces y no es factible para le problema dual.

Para ilustrar la propiedad de soluciones complementarias, después de una iteración es el problema e la Wyndor Glass Co, x = [0,6]^T y y = [0, 5/2, 0], con cx = 30 = yb

lunes, 10 de febrero de 2014

Resumen de las relaciones primal-dual (II)

Propiedad de dualidad fuerte: si x* es una solución óptima para el problema primal y y* es una solución óptima para el problema dual, entonces

cx* = y*b

domingo, 9 de febrero de 2014

Resumen de las relaciones primal-dual (I)

En seguida se dará un resumen de estas importantes relaciones entre los problemas primal y dual apenas descubiertas.

Propiedad de dualidad débil: si x es una solución factible para el problema primal y y es una solución factible para el problema dual, entonces.
cx ≤ yb

Por ejemplo, en del problema de la Wyndor Glass Co., una solución factible  es (empleando el superíndice T para denotar la transpuesta como se describe en el apéndice 3) x = [3,3]^T, lo que lleva a Z = cx = 24, y una solución factible del problema dual es y = [1,1,2], que de un valor más grande de la función objetivo, yo = yb =52. Para cualquier par de soluciones factibles, esta desigualdad debe cumplirse debido a que el valor factible máximo de Z = cx (36) es igual al valor factible mínimo de la función objetivo dual yo = yb, que es la siguiente propiedad.

sábado, 8 de febrero de 2014

Origen del problema dual (V)

Para el renglón 0 inicial, la tabla 6.5 muestra que la solución dual correspondiente, (y1, y2, y3) = (0,0,0), es no factible ya que las dos variables de superávit son negativas. La primera iteración logra eliminar uno de estos dos valores negativos, pero no el otro. Después de dos iteraciones se satisface la prueba de optimalidad para el problema primal puesto que todas las variables duales y las variables de superávit son negativas. Esta solución dual, (y1*, y2*, y3*) = (0,3/2,1), es óptima (como puede verificarse aplicando el método símplex directamente al problema dual), entonces el valor óptimo de Z y de yo es Z* = 36 =yo*.

viernes, 7 de febrero de 2014

Origen del problema dual (IV)

A manera de ilustración, la tabla 6.5 muestra el renglón 0 para las iteraciones respectivas al aplicar el método símplex al ejemplo de la Wyndor Glass Co. En cada caso, se dividió el renglón en tres partes: los coeficientes de las variables originales (x1, x2), los coeficientes de las variables de holgura (x3, x4, x5) y el lado derecho (valor de Z). Cada renglón 0 identifica una solución para el problema dual, que se muestra en la columna de la derecha. Se incluyen los valores de:
las variables de superávit para las restricciones funcionales del problema dual, y1 + 3y3 ≥ 3 y 2y2 + 2y3 ≥ 5. Así, un valor negativo para cualquier variable de superávit indica que se está violando la restricción correspondiente. También se incluye el valor de la función objetivo dual yo = 4y1 + 12y2 + 18y3. Tal y como se mostró en la tabla 6.4 todas etas cantidades se identifican en el renglón 0.

jueves, 6 de febrero de 2014

Origen del problema dual (III)

Pero, excepto porque no se ha establecido un objetivo para la función yo, este problema es precisamente el problema dual! Para completar la formulación, se explorará cuál debe ser ese objetivo que falta.

Como yo es sencillamente el valor de Z, y como el objetivo del problema primal es maximizar Z, una reacción natural sería que yo se maximizara también. Sin embargo, esto no es correcto debido a una razón bastante sutil: las únicas soluciones factibles para este nuevo problema son aquellas que satisfacen la condición de optimalidad para el problema primal. Por tanto, nada más la solución óptima para el problema primal corresponde a la solución factible para este nuevo problema. En consecuencia, el valor óptima de Z en el problema primal es el valor mínimo factible de yo en el nuevo problema, de manera que yo debe minimizarse. (Las relaciones que se desarrollan en la sección 6.3 proporcionan la justificación completa para esta conclusión.) Si se agrega este objetivo de minimizar yo, se obtiene el problema dual completo.


De este modo, el problema dual se puede ver como otra forma de establecer, en términos de programación lineal, la meta del método símplex, a saber, alcanzar una solución para el problema primal que cumpla con la prueba de optimalidad. Antes de alcanzar esta meta, la y correspondiente en el renglón 0 (los coeficientes de las variables de holgura) de la tabla símplex final debe ser no factible para el problema dual. No obstante, cuando ya se alcanzó la meta, la y correspondiente debe ser una solución óptima (indicada por y*) para el problema dual, ya que se trata de una solución factible que adquiere el valor factible más pequeño de yo. La solución óptima (y1*, y2*,....., ym*) proporciona los precios sombra para el problema primal que se describieron en la sección 4.7. Aún más, esta yo óptima no es otra cosa que el valor óptimo de Z, de manera que los valores de la función objetivo son iguales para los dos problemas. Este hecho también significa que cx ≤ yb para cualquier x y y factibles para los problemas primal y dual, respectivamente.

miércoles, 5 de febrero de 2014

Origen del problema dual (II)

La clave ahora, estriba en expresar lo que el método símplex trata de lograr (según la prueba de optimalidad) en términos de estos símbolos. En particular, busca un conjunto de variables básicas y la solución básica factible correspondiente, tal que todos los coeficientes en el renglón 0 sean no negativos. Cuando esta condición se cumple, se detiene con esta solución óptima. Esto se expresa simbólicamente como sigue.


martes, 4 de febrero de 2014

Origen del problema dual (I)

La teoría de dualidad se basa directamente en la idea fundamental (en particular con respecto al renglón 0) que se presentó en la sección 5.3. Para ver por qué, se seguirá usando la notación, que se introdujo en la tabla 5.9 para el renglón 0 de la tabla símplex final, pero se reemplazará Z* por yo y se quitarán los asteriscos de z* y y* al hacer referencia a cualquier tabla símplex. Entonces, en cualquier iteración dada del método símplex para el problema primal los números actuales del renglón 0 se denotan como se muestra en la tabla (parcial) dada en la tabla 6.4. Recuérdese que la idea fundamental conducía a la siguientes relaciones entre las cantidades y los parámetros del modelo original:

lunes, 3 de febrero de 2014

Esencia de la teoría de dualidad (IV)

Notese en particular que en la tabla 6.2: 1) los parámetros para una restricción en cualquier problema son los coeficientes de una variable en el otro y 2) los coeficientes de la función objetivo en un problema son los valores del lado derecho del otro. Entonces, existe una correspondencia directa entre los elementos de los dos problemas, tal y como se resume en la tabla 6.3. Esta correspondencia es la clave de algunas implicaciones de la teoría de dualidad entre las que se encuentra el análisis de sensiblidad.


domingo, 2 de febrero de 2014

Esencia de la teoría de dualidad (III)

A manera de ilustración, en la tabla 6.1 se muestran los problemas primal y dual para el ejemplo de la Wyndor Glass Co. de la sección 3.1, en forma matricial.

La tabla primal-dual para programación líneal ayuda también a subrayar la correspondencia entre los dos problemas. Muestra todos los parámetros de programación lineal (las aij, bi y cj) y cómo se usan para construir los dos problemas. Todos los encabezados de problema primal están en posición horizontal, mientras que para leer los del problema dual se necesita dar un cuarto de vuelta al libro. Se sugiere comenzar a observar cada problema.
en forma individual tapando con la mano los encabezados del otro. Una vez que se haya visto lo que dice la tabla para cada uno, deberán comparse.

sábado, 1 de febrero de 2014

Esencia de la teoría de dualidad (II)

Entonces, el problema dual usa exactamente los mismos parámetros que el problema primal, pero en diferentes lugares. Para recalcar esta comparación, obsérvese ahora estos mismos problemas en la notación matricial (tal y como se introdujo al principio de la sección 5.2), en donde e y y = [y1, y2,.............ym] son vectores renglón, pero b y x son vectores columna.