jueves, 11 de julio de 2013
ENLACES
http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/dualidad-en-programaci%C3%B3n-lineal/
http://miblogdeinvestigaciondeoperaciones.blogspot.com/2013/02/la-dualidad-en-programacion-lineal.html http://www.slideshare.net/eukitaa/dualidad-11256504
http://www.programacionlineal.net/resolucion_grafica.html
https://sites.google.com/site/tfio1joseyu/analisis-de-sensibilidad/importancia-del-analisis-de-sensibilidad
http://miblogdeinvestigaciondeoperaciones.blogspot.com/2013/02/la-dualidad-en-programacion-lineal.html http://www.slideshare.net/eukitaa/dualidad-11256504
http://www.programacionlineal.net/resolucion_grafica.html
https://sites.google.com/site/tfio1joseyu/analisis-de-sensibilidad/importancia-del-analisis-de-sensibilidad
INTRODUCCION
INTRODUCCIÓN
El trabajo del equipo de
investigación de operaciones recién se inicia cuando se ha aplicado con éxito
el método símplex para identificar una solución óptima. Una suposición de
programación lineal es que todos los parámetros del modelo (aij, bi y cj ) son constantes conocidas. En realidad, los valores de los
parámetros que se usan en este modelo son sólo estimaciones basadas en una predicción de las
condiciones futuras. Los datos obtenidos para
desarrollar estas estimaciones con frecuencia son bastante imperfectos o no
existen, es por esta razón que los parámetros de la formulación original pueden
representar poco más que algunas pequeñas reglas proporcionadas por el personal
de línea el que tal vez se sintió presionado para dar su opinión. Los datos
pueden incluso representar estimaciones optimistas o pesimistas que protegen
los intereses de los estimadores.
Por todo esto, un gerente
razonable y el personal de investigación de operaciones mantendrán cierto
escepticismo respecto a los valores originales entregados por el computador y,
en los muchos casos, los considerarán solamente como un punto de inicio para el
análisis posterior del problema. Una solución "óptima" es óptima nada
más en lo que se refiere al modelo específico que se está usando para
representar el problema real, y tal solución no se convierte en una guía
confiable para la acción hasta que se verifica que su comportamiento es bueno
para otras representaciones razonables del problema. Aún más, algunas veces los
parámetros del modelo (en particular bi) se establecen como
resultado de decisiones por políticas gerenciales, y estas decisiones deben
revisarse después de detectar sus consecuencias.
DUALIDAD EN PROGRAMACIÓN LINEAL
DUALIDAD EN PROGRAMACIÓN LINEAL
Dado un modelo lineal determinado, podemos definir otro modelo lineal
que nos permitirá obtener propiedades interesantes del primero y que será su
dual. La solución del modelo dual, permite obtener interesantes
resultados, relativos al análisis de sensibilidad de los términos
independientes más concretamente, para los rangos de valores de los
términos independientes para los que se mantiene la base optima (que podemos
conocer mediante el análisis de sensibilidad). La solución del dual nos permite
conocer el precio sombra de la restricción, que será la variación de la función
objetivo por unidad incrementada del termino independiente de la
restricción.
REGLAS DE OBTENCIÓN DEL DUAL
Si el modelo está escrito en la forma canónica, el dual resulta
singularmente fácil de obtener. Por ejemplo, partiendo de la forma canónica del
modelo de máximo:
Primal Dual
[MIN] z= c’. x [MAX]
w= b’. u
A . x
≥ b A’. u ≤
c
xj ≥
0 ui ≥ 0
INTERPRETACIÓN DE LAS VARIABLES DUALES.
El
significado de las variables duales es el mismo que en el caso de los
multiplicadores de Lagrange, es decir miden la sensibilidad de la función
objetivo respecto a cambios (infinitesimales) de los términos independientes de
cada restricción.
Max F =
ct x
s.a:
A x = b
x ≥ 0
Donde
asumimos que x ∈
Rn, c ∈
Rn, b ∈
Rm y A ∈
Μ(n,m).
Si
suponemos que x* es una solución factible básica no degenerada y óptima del
problema anterior, es decir, verifica que: x* = B-1 b ≥ 0 ; b ≥ 0; A x* =
b y que para una variación del vector de términos independientes b, cuando este
vector pasa a ser (b+Δb), siendo (b+Δb) ≥ 0, y que esta variación deje
inalterada las variables básicas de la solución, es decir que se cumpla que:
x* = B-1
(b + Δb) ≥ 0; (b + Δb) ≥ 0
A x* = (b
+ Δb)
En estas
condiciones la derivada de la función de Lagrange:
L(x,λ) = cx + λ ( b - Ax
)
∂ L
- = λ
∂ b este valor de λ nos
indica en cuanto varia la función objetivo ante una variación (infinitesimal)
de b, y que mantenga la factibilidad de la solución.
OBTENCIÓN DE LA SOLUCIÓN DEL DUAL
El dual de un modelo lineal es otro modelo lineal, que puede
solucionarse (después de las oportunas transformaciones, si algunas de las
variables resultantes es no negativa o no restringida en signo) del mismo modo
que el primal. Sin embargo, en general puede obtenerse la solución del dual
resolviendo el primal.
DUALES SIMÉTRICOS
Son los que se obtienen de un problema primal en forma canónica y “normalizada”,
es decir, cuando llevan asociadas desigualdades de la forma mayor o igual en
los problemas de minimización, y desigualdades menores o igual para los
problemas de maximización. Es decir, si el problema original es de la siguiente
forma:
Máx Z(x) = ct x
S.A:
A x ≤ b
x ≥ 0
El problema dual (dual simétrico) es:
Mín G (λ) = λ b
S. A:
λ A ≥ c
λ ≥ 0
DUAL ASIMÉTRICO
Son los restantes tipos de combinaciones de problema. Como por
ejemplo:
Máx Z(x) = ct x
S. A:
A x = b
X ≥ 0
El problema dual (dual asimétrico) es:
Mín G (λ) = λ b
S. A:
λ A ≥ c
λ >< 0, es decir, variables libres.
CARACTERÍSTICAS DE LAS SOLUCIONES DEL DUAL Y DEL PRIMAL
Si el primal tiene solución
óptima acotada x*, el dual también tendrá solución óptima acotada u* ambas
soluciones darán el mismo valor de la función objetivo.
C’. x*=b’. u*
Si uno de los dos problemas tiene
optimo no acotado, el otro no tendrá solución (la región factible será un
conjunto vacío)
Si uno de los dos problemas no tiene
solución, el otro puede tener optimo no acotado o no tener tampoco solución.
RELACIONES PRIMAL-DUAL
Asociado a cada problema lineal existe
otro problema de programación lineal denominado problema dual que posee
importantes propiedades y relaciones notables con respecto al problema lineal
original, problema que para diferencia del dual se denomina entonces como
problema primal (PP).
Las relaciones las podemos enumerar como siguen:
El problema dual tiene tantas variables
como restricciones tiene el programa primal.
El problema dual tiene tantas
restricciones como variables tiene el programa primal
Los coeficientes de la función objetivo
del problema dual son los términos independientes de las restricciones o RHS
del programa primal.
Los términos independientes de las
restricciones o RHS del dual son los coeficientes de la función objetivo del
problema primal.
La matriz de coeficientes técnicos del
problema dual es la traspuesta de la matriz técnica del problema primal.
El sentido de las desigualdades de las
restricciones del problema dual y el signo de las variables del mismo problema,
dependen de la forma de que tenga el signo de las variables del problema primal
y del sentido de las restricciones del mismo problema.
CONDICIONES DE KUHN-TUCKER
Condiciones de
Kuhn-Tucker en los problemas lineales (primales y duales).
Consideremos el
siguiente programa lineal, que denominaremos PRIMAL:
Máx Z(x) = ct x
s.a:
A x ≤ b
x ≥ 0
La función
lagrangiana de esta programa será:
L(x,λ) = c x +
λ ( b - Ax
) donde λ = ( λ1, λ2,....,λm )
representa el vector de los multiplicadores de Lagrange asociados a las
restricciones.
Las condiciones
de optimalidad de este problema (Condiciones de Kuhn-Tucker) respecto de las
variables, son:
∂L
= c - λ A ≤ 0
∂x
∂L
x = ( c - λ A ) x = 0
∂x
x ≥ 0
Respecto a los multiplicadores,
son:
∂L
= b - Ax ≥ 0
∂λ
∂L
λ = λ ( b - Ax ) = 0
∂λ
λ ≥ 0
Asociado a este programa primal tenemos otro problema lineal
denominado DUAL (posteriormente
explicaremos las relaciones entre ambos):
Mín G(λ) = λ b
s.a:
λ A ≥ c
λ ≥ 0
La función lagrangiana de este programa será:
L(λ,x) = λ b + ( c - λA ) x en donde el
vector x = ( x1, x2, ..., xn ) representa los multiplicadores asociados a las
restricciones del dual.
Obteniendo las
condiciones de Kuhn-Tucker respecto de las variables son:
∂L
= b - Ax ≥ 0
∂λ
∂L
λ = λ ( b - Ax ) = 0
∂λ
λ ≥ 0
Respecto a los multiplicadores, son:
∂L
= c - λ A ≤ 0
∂x
∂L
x = ( c - λ A ) x = 0
∂x
x ≥ 0
Como puede
observarse, ambas condiciones de optimalidad son las mismas para los dos
problemas. A la misma consideración se puede llegar sin más que comparar la
función de Lagrange de los dos problemas y ver que son iguales:
L(x,λ) = c x + λ ( b - Ax )
L(λ,x) = λ b +( c - λA )x = λ b + cx-λAx = cx + λ( b - Ax )
Por lo tanto,
asociado a todo problema de programación lineal existe otro problema de
programación lineal denominado programa
dual que tiene importantes relaciones con el problema original
denominado programa primal. Como
acabamos de ver, es evidente, que el programa dual de un programa dual
proporciona el programa primal original.
TEOREMAS DE DUALIDAD.
TEOREMA
DE EXISTENCIA.
La
condición necesaria y suficiente para que un problema de programación lineal
tenga solución es que, tanto el conjunto de oportunidades del primal (S) como
en conjunto de oportunidades del dual (S’) no sean vacíos, es decir, que ambos problemas
sean factibles.
∃ ( x* , λ* ) ←→ S ≠ ∅ ∧ S’ ≠ ∅
Corolario del teorema de existencia.
Una vez
analizadas las condiciones que han de cumplirse para que exista solución
optima, vamos a ver los diferentes casos posibles:
S ≠ ∅ ∧ S’ ≠ ∅ Ambos problemas tienen solución optima
finita.
S = ∅ ∧ S’ ≠
∅ El programa primal es infactible, y el programa dual es no
acotado.
S ≠ ∅ ∧ S’ = ∅ El
programa dual es infactible, y el programa primal es no acotado.
S = ∅ ∧ S’ = ∅ Ambos problemas son infactibles.
TEOREMA
DE LA DUALIDAD.
La
condición necesaria y suficiente para que exista solución óptima del primal (
x* ), es que exista una solución óptima para el dual ( λ* ) y que
valor de la función objetivo de ambos programas sea igual, es decir Z(x*) = G(λ*).
∃ x* ←→
∃ λ* / Z(x*) = G(λ*)
TEOREMA
DEL HOLGURA COMPLEMENTARIA.
La
condición necesaria y suficiente para que (x*, λ*) sean soluciones óptimas del
programa primal y dual, es que satisfagan las condiciones de holgura
complementaria:
(c - λ* A) x* =
0λ* ( b - A
x* ) = 0
IMPORTANCIA DE DUALIDAD DE PROGRACMACION LINEAL
La dualidad permite realizar importantes interpretaciones económicas de
los problemas de programación lineal y así como también generar métodos como el
método dual del simplex de gran importancia en el análisis de post-optimización
y en la programación lineal paramétrica.
La resolución de los problemas duales respecto a los primales se
justifica dada la facilidad que representan dados problemas, donde el número de
restricciones supere al número de variables. Además de tener gran aplicación en
el análisis económico del problema.
Otra de las ventajas que presenta es que dado al número de restricciones
y variables entre problema dual y primal es inverso, se pueden resolver
gráficamente problemas que presenten dos restricciones sin importar el número
de variables. Sin embargo cada vez que se plantea y resuelve un problema
lineal, existe otro problema incitante planteado y que puede ser resuelto, es
el considerado problema dual, el cual tiene unas importantes relaciones y
propiedades respecto al problema primal que pueden ser de gran beneficio para
la toma de decisiones.
VENTAJAS Y DESVENTAJAS DE LA DUALIDAD:
VENTAJAS:
Una de las ventajas de la existencia
del problema dual es la posibilidad de reducir el esfuerzo computacional al
resolver ciertos modelos de Programación Lineal. Pero más importante aún es la
relación que existe entre la dualidad y el análisis de sensibilidad, tema del
próximo capítulo, el cual estudia el efecto que las variaciones en los
parámetros de un modelo tienen en la solución óptima de este. Además, los
valores óptimos de las variables del modelo dual suministran información
económica muy importante acerca del valor implícito de los recursos que se
utilizan en el problema que se está resolviendo.
El matemático norteamericano John Von
Neumann (1991) fue el primero en destacar la existencia de la dualidad en la
programación lineal y a partir de allí el concepto se ha usado en una gran
variedad de áreas teóricas y prácticas de la misma
Las grandes distancias que impiden
asistir a la escuela ya no es un problema con esta modalidad educativa. Hoy en
día la población puede acceder a este tipo de educación desde dónde resida.
Es una excelente herramienta para
mejorar el desarrollo académico y profesional de la población adulta.
La educación a distancia permite
concluir los estudios postergados.
Flexibilidad de horarios, lo que
facilita la organización del tiempo del alumnado respetando la vida familiar y
las obligaciones laborales.
Supone bajo costo.
Se cuenta con un docente muy
participativo desde antes de abrirse el curso (escribiendo contenidos
acompañado de especialistas en diseño gráfico y pedagógico) y durante el curso.
Atención personalizada pues el tutor
acompaña, supervisa y corrige de manera individual.
Es un método que le enseña al alumno a
aprender. Le instruye en las técnicas del auto aprendizaje y la autoformación
las cuales reforzadas con la tecnología de la información permiten un
aprovechamiento más completo en lo que a contenidos se refiere.
DESVENTAJAS:
Dificultad de transmitir y conservar
determinados valores sociales.
La flexibilidad de horarios a veces
está limitada a ciertos cursos que exigen participación en línea en horarios o
espacios específicos.
Como no hay una comunicación constante
entre el tutor y el alumno se crea desconfianza en aspectos como el proceso de
aprendizaje y evaluación académica del alumno.
Contribuye en cierta medida al
aislamiento de la persona para lo cual es necesaria una intervención activa del
tutor.
Una formación académica distinta a la
tradicional requiere de cierto nivel de adaptación que puede resultar difícil
para algunas personas.
ANALISIS DE SENSIBILIDAD
El análisis de sensibilidad es una herramienta especialmente útil cuando
no tenemos una certeza absoluta sobre los valores que se han dado a los términos
independientes de las restricciones (en muchas ocasiones asociados a la
limitación de los recursos) o los coeficientes de la función objetivo
(coeficientes de coste). Para estos casos el análisis de sensibilidad consiste
en estudiar cómo evoluciona el óptimo y el valor de la función objetivo en el
óptimo ante variaciones de dichos términos independientes y coeficientes.
El análisis de sensibilidad propiamente dicho estudia los intervalos
para los cuales la modificación de un valor (coeficiente de la función objetivo
o término independiente) en el programa lineal, de forma individualizada, no
cambia las variables que componen la base de nuestra solución. Hallando, para
el rango de valores definido en el intervalo, la evolución de la función
objetivo (expresado a través de los precios sombra).
OBJETIVO DE ANALISIS DE SENSIBILIDAD
El objetivo fundamental del análisis de sensibilidad es identificar los
parámetros sensibles, (por ejemplo, los parámetros cuyos valores no pueden
cambiar sin que cambie la solución óptica). Para ciertos parámetros que no
están clasificados como sensibles, también puede resultar de gran utilidad determinar
el intervalo de valores del parámetro para el que la solución óptima no cambie.
Este intervalo de valores se conoce como intervalo permisible para permanecer
óptimo. En algunos casos cambiar el valor de un parámetro puede afectar la
factibilidad de la solución BF óptima con los valores ajustados de las
variables básicas seguirá siendo factible.
CARACTERISTICAS DEL ANALISIS DE SENCIBILIDAD
CARACTERISTICAS DEL ANALISIS DE SENCIBILIDAD
ü El análisis de sensibilidad prácticamente elimina
el esfuerzo computacional.
ü Los problemas reales ocurren en un medio ambiente
dinámico.
ü Identifica los parámetros sensibles.
ANÁLISIS DE SENSIBILIDAD (SOLUCION GRÁFICA)
a)
Coeficientes de la función objetivo
Solo es
necesario hacerlo para las variables originales.
a.1)
Variables básicas
- Las
variables x e y son básicas ya que figuran en la base (aunque x valga cero).
- La
variable x saldrá de la base cuando algún coste reducido sea menor o igual a
cero.
- Solo
debemos examinar la columna S(1). El resto no sufren modificaciones al variar
el coeficiente asocia do a x (C x)
Cx – Zx =
0 – [2 + ?Cx(1/3) – 3*(1/3) – 0*(2/3)] = 0
Por
tanto: ?Cx = 1
Puesto
que no hay otras columnas a examinar, concluimos que el coeficiente Cx podrá
aumentar en 1 (de 2 hasta 3) y podrá disminuir todo lo que se quiera.
Análogamente , para la sensibilidad de Cy tendremos:
Cy – Zy = 0 – [2*(1/3) – (3 + ?Cy)*(1/3) – 0*(2/3) = 0
Por
tanto: ?Cy = -1
Concluimos que el coeficiente y podrá disminuir en 1 (de 3 hasta
2) y podrá aumentar todo lo que se quiera.
a.2)
Variables no básicas
No hay variables originales no básicas.
ANÁLISIS DE SENSIBILIDAD MEDIANTE PROGRAMAS
INFORMÁTICOS
Los programas informáticos que resuelven modelos de programación lineal,
como el LINDO, suelen incorporar la posibilidad de realizar el análisis de
sensibilidad de los coeficientes de coste c y de los términos
independientes de las restricciones b, el
resultado de este análisis es el intervalo de valores de estos parámetros para
el que se mantiene la base.
Aplicación del análisis de sensibilidad
Este análisis casi siempre comienza con la investigación de los cambios
en los valores de las bi, la
cantidad del recurso i (i = 1, 2,. . . , m) que se encuentra disponible para las actividades bajo
consideración. La razón es que en general existe mayor flexibilidad al
establecer y ajustar estos valores que los otros parámetros del modelo. La
interpretación económica de las variables duales (las yi) como precios sombra
es extremadamente útil para decidir cuáles son los cambios que se deben
estudiar.
Primer caso: Cambios en las
b i (columna lado derecho)
Supongamos que los únicos cambios al modelo actual consisten en el
cambio de uno o más de los parámetros bi (i = 1, 2, . . . , m). En este caso, los únicos cambios que resultan en la tabla símplex final se
encuentran en la columna del lado derecho, por lo cual, se pueden omitir del
procedimiento general tanto la conversión a la forma apropiada de eliminación
de Gauss como la prueba optimalidad.
Como se muestró en la tabla 1.1, cuando el vector de valores bi se
cambia de b a b, las fórmulas para calcular la nueva columna del lado derecho en la tabla símplex final son
Lado derecho del renglón 0 final: Z* =
y* b
Lado derecho de los renglones 1, 2, . . . , m: b* = S* b
(Vea al final de la tabla 1.1 la localización del vector y* y la matriz
S* que no cambiaron, en la tabla símplex final.)
EJEMPLO
El análisis de sensibilidad para el problema original de la Wyndor Glass
Co. comienza por examinar los valores óptimos de las variables duales yi (Y1* = 0, Y2*
=3/2, Y3* = 1). Estos precios sombra dan el valor marginal de cada
recurso i para las actividades (dos nuevos productos) bajo consideración, donde
el valor marginal se expresa en las unidades de Z (miles de dólares de ganancia
por semana). Se puede aumentar la ganancia total debida a estas actividades en
$1500 semanales (y2* multiplicado por $1000 por semana) por cada unidad
adicional del recurso 2 (hora de producción a la semana en la planta 2) que
quede disponible. Este aumento en la ganancia es válido para cambios
relativamente pequeños que no afecten la factibilidad de la solución básica
actual (y por tanto, que no afecten los valores de yi*).
En consecuencia, el equipo de 10 ha investigado la ganancia marginal
posible debida a los otros usos actuales de este recurso para determinar si
alguna es menor que $1500 semanales. Esta investigación puso de manifiesto que
uno de los productos antiguos es mucho menos redituable. La tasa de producción
para este producto ya se redujo a la cantidad mínima que justifica sus gastos
de comercialización, pero se puede descontinuar, lo que proporcionaría 12
unidades adicionales del recurso 2 para los nuevos productos. Entonces, el
siguiente paso es determinar la ganancia que se podría obtener de los nuevos
productos si se hiciera esta transferencia. Esto cambia b2 de 12 a 24 en el
modelo de programación lineal. La figura 2 muestra el efecto gráfico de este
cambio incluyendo el cambio en la solución en un vértice final de (2, 6) a (-2,
12). (Observe que esta figura es distinta a la 1 porque la restricción 3x1 +
2X2 < 18, no cambió en este caso.)
El cambio en el vector de los valores de bi es
4 _ 4
b = 12 b = 24
18 18
Por lo tanto, cuando se aplica la idea fundamental (tabla 1.1), se
encuentra que el efecto de este cambio sobre la tabla símplex final original
(parte media de la tabla 1.2) es que los elementos de la columna del lado
derecho cambian a los siguientes valores:
4
Z* = y* b = (0,3/2,1) 24 = 54,
18
_ 1 1/3 -1/3 4 6 X3 6
b* = S* b = 0 ½ 0 24 = 12 , de modo que X2 = 12
0 -1/3 1/3 18 -2 X1 -2
De manera similar, como el único cambio en el modelo original es
b2 = 24 - 12 = 12, se puede usar el análisis incremental para calcular estos mismos valores con mayor rapidez. El análisis incremental involucro el cálculo de los incrementos en los valores de la tabla causados por el cambio (o cambios) en el modelo original, y después la suma de estos incrementos a los valores originales. En este caso, los incrementos en Z* y b* son
_
b1 0
Z* = y*
b = y*
b2 = y* 12 ,
b3 0
_
b1 0
b* =S*
b =S*
b2 = S* 12
b3 0
Figura 2: Región factible para el problema
de la Window Glass Co. Después de cambiar sólo b2 a 24.
Por lo tanto la segunda componente de y* y la segunda columna de S* ,
los únicos calculos que se necesitan son
Z* = 3/2(12) = 18, así
Z* = 36 +18 = 54,
b1*
= 1/3(12) = 4, así b1* = 2+ 4=6,
b2* =1/2( 12) = 6, así b2* = 6 + 6 = 12,
b3* = 1/3( 12) = -4, así b3*= 2-4=-2,
En donde los valores originales de estas cantidades se obtienen de la
columna del lado derecho en la tabla símplex final original (parte media de la
tabla 1.2). La tabla símplex final revisada corresponde por completo a la tabla
símplex final original, excepto por la columna del lado derecho que tiene estos
nuevos valores.
Por lo tanto, la solución básica actual (antes óptima) se ha convertido
en
(X1, X2, X3, X4, X5) =
(-2, 12, 6, 0, 0).
Que no pasa la prueba de factibilidad porque tiene un valor negativo. Ahora
se puede aplicar el método símplex dual a partir de esta tabla revisada, para
encontrar la nueva solución óptima. Este método conduce, en una sola iteración,
a la nueva tabla símplex final que se muestra en la tabla 1.3. (En forma
alternativa, se pudo haber aplicado el método símplex desde el principio y en
este caso, también se hubiera llegado a esta tabla final en una sola
iteración.) Esta tabla símplex indica que la nueva solución óptima es
(X1, X2, X3, X4, X5) = (0, 9, 4, 6, 0)
con Z = 45, proporcionando así un incremento en la ganancia de 9
unidades ($9000 semanales) sobre el valor anterior Z = 36. El hecho de que X4 = 6 indica que 6 de las 12
unidades adicionales del recurso 2 quedan sin usarse con esta solución.
Aunque
b2 = 12 resultó ser un incremento de b2 demasiado grande para mantener la factibilidad (y por ende la optimalidad) con la solución básica en la que X1, X2, X3 las variables básicas (parte media de la tabla 1.2), el análisis incrementar anterior muestra qué tan grande puede ser el incremento para seguir siendo factible. En particular, se observa que
b1* = 2 + 1/3
b2,
b2* = 6 + -1/2 b2,
b3* = 2 - 1/3
b2,
En donde estas tres cantidades son los valores de X3, X2 y X1, respectivamente, para
esta solución básica. La solución permanece factible y, por lo tanto, óptima,
siempre y cuando las tres cantidades sigan siendo no negativas.
Tabla 1.3 Datos revisados para el problema de la Wyndor Glass Co. después de
cambiar sólo b2
|
Tabla simplex final después de la reoptimización
|
|||||||||
|
Coeficiente de
|
|||||||||
|
Var básica
|
Ec. Núm.
|
Lado derecho
|
|||||||
|
Z
|
x1
|
x2
|
x3
|
x4
|
x5
|
||||
|
Z
|
0
|
1
|
9/2
|
0
|
0
|
0
|
5/2
|
45
|
|
|
x3
|
(1)
|
0
|
1
|
0
|
1
|
0
|
0
|
4
|
|
|
x2
|
(2)
|
0
|
3/2
|
1
|
0
|
0
|
1/2
|
9
|
|
|
x4
|
(3)
|
0
|
-3
|
0
|
0
|
1
|
-1
|
6
|
|
|
Parametros del modelo:
|
|||||||||
|
c1=3
|
c2=5
|
(n=2)
|
|||||||
|
a11=1
|
a12=0
|
b1=4
|
|||||||
|
a21=0
|
a22=2
|
b2=24
|
|||||||
|
a31=3
|
a32=2
|
b3=18
|
|||||||
Para cualquier bi, su intervalo permisible para permanecer
factible es el intervalo de valores sobre el que la solución BF óptima
(con los valores ajustados para las variables básicas) permanece factible. (Se
supone que el cambio en el valor de esta bi es el único cambio en el modelo)
Los valores ajustados para las variables básicas se obtienen a partir de la
fórmula b* = S*b. El cálculo del intervalo permisible para permanecer factibles
está basado en el hecho de encontrar el intervalo de valores de bi tales que
b* > 0.
Con base en estos resultados, b2 = 24, se descontinuará el producto
antiguo, relativamente no redituable y las 6 unidades no utilizadas del recurso
2 se guardarán para algún uso futuro. Como Y3* todavía es positivo, se hace un
estudio similar de la posibilidad de cambiar la asignación del recurso 3, pero
la decisión a la que se llega es conservar la asignación actual. Por lo tanto,
el modelo de programación lineal en este punto tiene los valores de los
parámetros y la solución óptima que se muestran en la tabla 1.3.
Segundo caso:
a) Cambios en los coeficientes de una
variable no básica
Considere una variable específica xj (j fija) que sea no básica en la solución óptima
dada en a tabla símplex final. El caso 2a es aquel en el que los únicos cambios
al modelo actual ocurren en uno o más de los coeficientes de esta variable, cj,
a1j, a2j........, amj.
Entonces, si cj y aij,
denotan los nuevos valores de estos parámetros con Aj, (columna j de la matriz
A) como el vector que contiene a aij, se tiene para el modelo revisado.
_ _
cj cj, Aj Aj
Si la solución óptima cambió y si se desea encontrar la nueva, se puede
hacer de una manera bastante sencilla. Sólo debe aplicarse la idea fundamental
a la columna xj revisada (la única que cambia) en la tabla simplex final. En
particular, las fórmulas de la tabla 1.1 se reducen de la siguiente manera:
Coeficiente de Xj en el reglón 0 final: zj - cj = x* Aj - cj,
Coeficiente de Xj en los reglones 1 a m finales: A*j = S* Aj.
Con la solución básica actual que ya no es óptima, el nuevo valor de z*j
- cj será ahora el que tiene coeficiente negativo en el renglón 0, así que se
inicia el método símplex con xj como la variable básica entrante inicial.
EJEMPLO
Como x1 es no básica en la solución óptima actual (vea la tabla 1.3)
para el problema de la Wyndor Glass Co., el siguiente paso en el análisis de
sensibilidad es comprobar si cualquier cambio razonable en la estimación de los
coeficientes de x1 puede aconsejar que se introduzca el producto 1. El conjunto
de cambios que pueden ser realistas para hacer el producto 1 más atractivo
sería restablecer c1 = 4
y a31= 2. En lugar de
explorar cada uno de estos cambios en forma independiente (como se hace con
frecuencia en el análisis de sensibilidad), los cambios bajo consideración son:
_ 1 _ 1
c1 = 3 c1 = 4, A1 = 0 A1 = 0
3 2
Este cambio en a31 hace que la región factible cambie de la que se
muestra en la figura 2 a la región correspondiente de la figura 1, cuando
3x1 + 2X2 = 18 se sustituye por 2x1 + 2x2
= 18. El cambio en c1 hace que la función objetivo Z = 3x1 + 5x2 cambie a Z =
4x1 + 5x2. Si se dibuja la recta de la función objetivo Z = 45 = 4x1 + 5x2 en
la figura 1 que pasa con la solución óptima actual (0,9) se puede verificar que
este punto sigue siendo óptimo después de los cambios en a31 y c1.
Esta restricción revisada como la y* actual (coeficientes de las
variables de holgura en el reglón 0 de la tabla 1.3) se muestra a continuación:
y*1 = 0, y*2 = 0, y*3 = 5/2
y1 + 3y3 " 3 y1 + 2y3 " 4.
0 + 2(5/2) " 4.
Como y* todavía satisface
la restricción revisada, la solución primal actual (tabla 61.3) todavía es
óptima.
Debido a que esta solución todavía es óptima, no existe la necesidad de
revisar la columna de xj, en la tabla símplex final (paso 2).
INTERVALO PERMITIDO PARA PERMANECER ÓPTIMA:
Se acaba de describir e ilustrar la forma de analizar cambios simultáneos en los coeficientes de una
variable no básica xj. Es una práctica común en el análisis de sensibilidad
poner atención también en el efecto de cambiar sólo un parámetro, cj. Esto
incluye simplificar el enfoque anterior para encontrar el intervalo de valores
permitidos para permanecer óptima para cj.
Para cualquier cj, su intervalo permitido para
permanecer óptima es el intervalo de valores para el que la solución
óptima actual (obtenida por el método símplex para el modelo actual antes de
cambiar cj) permanece óptima. (Se supone que el cambio en esta
única cj, es el único cambio al modelo actual.) Cuando xj, es una variable no
básica para esta solución, la solución permanece óptima mientras z*j -cj "
0, donde z*j = y*Aj es una constante a la que no afecta el cambio
en el valor de cj. Entonces, el intervalo permitido para permanecer óptima para
cj, se puede calcular como cj " y*Aj .
Por ejemplo, considere el modelo actual para el problema de la Wyndor
Glass Co. que se resume en el lado izquierdo de la tabla 1.3, donde la solución
óptima actual (con C1 = 3)
está dada en el lado derecho. Cuando sólo se cambia C1, esta solución permanece
óptima siempre que
1
c1 " y*A1 = (0, 0, 5/2) 0 = 7 ½,
3
De manera que C1 " 7 ½ es el intervalo permitido
para permanecer óptima.
Una alternativa para realizar esta multiplicación de vectores es
observar en la tabla 1.3 que z*1 - c1 = 9/2 ( el coeficiente de x1 en el reglón
0) cuando c1 = 3, de manera que z*1 = 3 + 9/2 = 7 ½. Como z1 = y*A1, de
inmediato se llega al mismo intervalo permitido.
Para cualquier variable de decisión no básica cj, en
ocasiones se hace referencia al valor z*j - cj como el costo
reducido para xj, porque es la cantidad mínima en la que
tendría que reducirse el costo unitario de la actividad j para hacer que valga
la pena realizar esa actividad j (aumentar el valor de xj a más de cero). Al
interpretar cj como la ganancia unitaria de la actividad j (lo que reduce el incremento
en el costo unitario cj por la misma cantidad), el valor de z*j -
cj es entonces el incremento máximo permitido en cj para conservar óptima
la solución BF actual.
b) Introducción de una nueva variable
Ya obtenida la solución óptima se puede descubrir que la formulación de
programación lineal no tomó en cuenta todas las actividades que pudieran ser
atractivas. Considerar una nueva actividad requiere introducir una nueva
variable con los coeficientes apropiados, a la función objetivo y a las
restricciones del modelo actual, éste es el caso 2b.
La manera conveniente de manejar este caso es tratarlo como si fuera el
2a! Para realizar esto se presume que la nueva variable xj ya formaba parte del
modelo original con todos sus coeficientes iguales a cero (por lo que todavía
son cero en la tabla símplex final) y que xj es una variable no básica en la
solución BF actual. Entonces, si se cambian estos coeficientes cero a sus
valores actuales para la nueva variable, sin duda el procedimiento (que incluye
la reoptimización) se vuelve idéntico al del caso 2a.
De hecho, todo lo que se tiene que hacer para comprobar si la solución
actual es todavía óptima es verificar si la solución básica complementaria y*
satisface la nueva restricción dual que corresponde a la nueva variable en el
problema primal.
Tercer caso: Cambios en los coeficientes
de una variable básica
Ahora suponga que la variable xj (con j fija) que se está estudiando es
una variable básica en la solución óptima que se muestra en la tabla símplex
final. El caso 3 supone que los únicos cambios al modelo actual se hacen en los
coeficientes de esta variable.
El caso 3 difiere del 2a debido al requisito de que la tabla símplex
debe estar en la forma apropiada de eliminación de Gauss. Esta forma permite
que los elementos en la columna de una variable no básica tengan cualquier
valor, así que no afecta en el caso 2a. Sin embargo, para el caso 3 la variable
básica xj debe tener coeficiente 1 en su renglón de la tabla símplex y
coeficiente 0 en todos los
demás renglones (incluyendo el renglón 0). Por lo tanto, una vez que se han
calculado los cambios en la columna xj de la tabla símplex final, es probable
que sea necesario aplicar la eliminación de Gauss para restaurar la forma
apropiada. Este paso, a su vez, quizá cambie los valores de la solución básica
actual, y puede hacerla no factible o no óptima (con lo que puede ser necesario
reoptimizar).
Antes de aplicar la eliminación de Gauss, se resumen las fórmulas para
revisar que la columna de xj sea la misma que para el caso 2b.
Coeficiente de xj en el renglón 0 final: z*j - cj = y*Aj - cj
Coeficiente de xj en los renglones 1 a m finales: A*j = S*Aj.
EJEMPLO
Como x2 es una variable básica en la tabla 1.3 para el problema de la
Wyndor Glass Co., el análisis de sensibilidad sobre sus coeficientes se ajusta
al caso 3. Dada la solución óptima actual (x1= 0, x2 = 9), el producto 2 es el
único producto nuevo que
debe introducirse, y su tasa de producción será relativamente grande. Por
ello,, la pregunta importante es si las estimaciones iniciales que llevaron a
los coeficientes de x2 en el modelo actual pudieron haber sobreestimado tanto
las cualidades del producto 2 que invaliden esta conclusión. Para responder a
esta pregunta se debe verificar el conjunto más pesimista de estimaciones razonables para
estos coeficientes, que resulta ser c2 = 3, a22 = 3 y a32 =4. En consecuencia,
los cambios que han de investigarse son
_ 0 _ 0
c2 = 5 c2 = 3, A2 = 2 A2 = 3
2 4
El efecto gráfico de estos cambios es la modificación en la región
factible según la figura 3 respecto a la que se muestra en la figura 2. La
solución óptima en la figura 2 es (x1, x2)= (0, 9), que corresponde a la solución en el vértice en
donde se cruzan las fronteras de restricción x1= 0 y 3x1 + 2x2 = 18. Al revisar las restricciones, la
solución en un vértice correspondiente en la figura 3 es (0,9/2). No obstante,
esta solución ya no es óptima, puesto que la función objetivo revisada, Z = 3x1 + 3x2, conduce ahora a la nueva solución óptima
(x1,x2) = (4 , 3/2).
Ahora veamos cómo se puede llegar a estas mismas conclusiones
algebraicamente. Dado que los únicos cambios en el modelo ocurren en los
coeficientes de x2, las únicas modificaciones
que resultan en la tabla símplex final (tabla 1.3) están en la columna de x2.
Entonces, se usan las fórmulas anteriores para volver a calcular nada más esta
columna.
Figura 3: Región factible para el ejemplo del
caso 3: cambios en los coeficientes de una variable básica.
_ _ 0
z2 - c2 = y*A2 - c2 = (0, 0, 5/2) 3 - 3 = 7
4
_ 1 0 0 0 0
A*2 = S*A2 = 0 0 ½ 3 = 2
0 1 -1 4 -1
(De manera equivalente, se puede usar el análisis incremental con
c2 =-2,
a22 = 1 y
a32 = 2 para obtener esta columna.)
La tabla final revisada que resulta se muestra en la parte superior de
la tabla 1.4. Note que los nuevos coeficientes de esta variable básica x2 no
tienen los valores requeridos y se tiene que aplicar la conversión a la forma
apropiada con eliminación de Gauss. Este paso exige dividir el renglón 2 entre
2, restar el nuevo renglón 2 multiplicado por 7 del renglón 0 y sumar el nuevo
renglón 2 al renglón 3.
La segunda tabla símplex de la tabla 1.4 da los nuevos valores de la
solución básica actual, a saber, x3 = 4, x2 = 9/2, x4 = 21/2 (x1 = 0, x5 = O). Como todas estas
variables son no negativas, la solución todavía es factible. Sin embargo, el
coeficiente negativo de x1, en el renglón 0 indica que la solución ya no es
óptima. Se aplicará el método simplex a esta tabla, con esta solución como
solución BF inicial, para encontrar la nueva solución óptima. La variable
entrante básica inicial es x1, con x3 como la variable básica que
sale. Se necesita sólo una iteración en este caso para llegar a la nueva
solución óptima: x1 = 4, x2 = 3/2, x4 = 39/2 (x3 = 0, x5 = 0), como se muestra
en la tabla 1.4.
Este análisis sugiere que c2, a22, y a32 son parámetros relativamente
sensibles. Sin embargo, los datos adicionales para estimarles con más cuidado
sólo pueden obtenerse si se realiza una prueba piloto. Por lo tanto, el equipo
de IO recomienda que inicie de inmediato la producción del producto 2 en
pequeña escala (x2 =3/2) y que se use esta experiencia como guía para la
decisión acerca de si la capacidad restante debe asignarse al producto 2 o al
1.
Tabla 1.4 : Procedimiento del análisis de
sensibilidad aplicado al ejemplo del tercer caso.
|
Coeficiente de
|
|||||||||
|
Var bàsica
|
Ec. Núm.
|
Lado derecho
|
|||||||
|
Z
|
1
|
2
|
3
|
4
|
x5
|
||||
|
Tabla simplex final revisada
|
Z
|
0
|
1
|
/2
|
7
|
0
|
0
|
5/2
|
45
|
|
x3
|
(1)
|
0
|
1
|
0
|
1
|
0
|
0
|
4
|
|
|
x2
|
(2)
|
0
|
/2
|
2
|
0
|
0
|
1/2
|
9
|
|
|
x4
|
(3)
|
0
|
3
|
1
|
0
|
1
|
-1
|
6
|
|
|
Convertida a la forma apropiada
|
Z
|
(0)
|
1
|
3/4
|
0
|
0
|
0
|
3/4
|
27/2
|
|
x3
|
(1)
|
0
|
1
|
0
|
1
|
0
|
0
|
4
|
|
|
x2
|
(2)
|
0
|
3/4
|
1
|
0
|
0
|
1/4
|
9/2
|
|
|
x4
|
(3)
|
0
|
-9/4
|
0
|
0
|
1
|
3/4
|
21/2
|
|
|
Reoptimizacion de la tabla simplex
|
Z
|
(0)
|
1
|
0
|
0
|
/4
|
0
|
3/4
|
33/2
|
|
x1
|
(1)
|
0
|
1
|
0
|
1
|
0
|
0
|
4
|
|
|
x2
|
(2)
|
0
|
0
|
3/4
|
0
|
1/4
|
3/2
|
||
|
x4
|
(3)
|
0
|
0
|
0
|
9/4
|
1
|
-3/4
|
39/2
|
|
INTERVALO PERMITIDO PARA PERMANECER ÓPTIMA:
Ya se describió para el segundo caso como encontrar el intervalo
permisible para permanecer óptima para cualquier cj tal que xj es una variable
no básica para la solución óptima actual (antes de cambiar cj) Cuando xj es una
variable básica, el procedimiento se complica un poco por la necesidad de
convertir a la forma apropiada de eliminación de Gauss antes de probar la
optimalidad.
Para ilustrar el procedimiento, considere la nueva versión del modelo de
la Wyndor Glass Co. (con c2 = 3, a22 = 3, a23 = 4) cuya gráfica se muestra en
la figura 3 y que se resuelve en la tabla 1.4. Como x2 es una variable básica
para la solución óptima dada al final de la tabla (con c2 = 3), los pasos necesarios para
encontrar el intervalo de valores permitidos para permanecer óptima para c2 son
los siguientes:
Como x2 es una variable básica,
observe que su coeficiente en el nuevo renglón 0 final automáticamente es Z*2 -
c2 = 0 antes de cambiar el valor actual de 3 para c2.
Ahora se incremento c2 = 3 en
c2 (de manera que c2 = 3 +
c2). Esto cambia el coeficiente indicado en el paso 1 a Z*2 - c2 = -
c2.
Con este coeficiente ahora
diferente de cero, deben realizarse operaciones elementales para restaurar la
forma apropiada de eliminación de Gauss. En particular, se suma al renglón 0 el
renglón 2 multiplicado por
c2, lo que da el nuevo renglón cero [0, 0, ¾ - ¾
c2, ¾ + ¼
c2 : 33/2 + 3/2
c2)
Usando este nuevo renglón 0, se
calcula el intervalo de valores de
c2 que mantiene no negativos a los coeficientes de las variables no básicas (x3 Y x5).
¾ - ¾
c2 " 0 ¾ " ¾
c2
c2 " 1.
¾ + ¼
c2 " 0 ¼
c2 " - ¾
c2 " 1.
Como c2 = 3 +
c2, se suma 3 a este intervalo de valores, lo que da como el intervalo de valores permitido para permanecer óptima para c2.
0 " c2 " 4
Con sólo dos variables de decisión, este intervalo permitido se puede
verificar gráficamente usando la figura 3 con una función objetivo de Z = 3x1 +
c2x2 Con el valor actual
c2 = 3, la solución óptima es (4, 3/2). Cuando se incrementa c2, esta solución
permanece óptima sólo para c2 " 4. Para c2 " 4, (0, 9/2) se convierte
en óptima (con un empate en c2 = 4),
debido a la frontera de restricción 3x1 + 4x2 = 18. Cuando por el contrario, C2 disminuye, (4,3/2)
sigue siendo óptima sólo para c2 " 0- Si c2 " 0, (4, 0) se vuelve óptima
debido a la frontera de restricción x1 = 4.
De forma similar, el intervalo de valores permitidos para permanecer
óptima para c1 (con c2 fijo en 3) se puede obtener algebraica o gráficamente
como c1 " 9/4.
Cuarto caso: Introducción de una nueva
restricción de desigualdad
Este es el último caso en el cual debe introducirse al modelo una nueva
restricción, después de que ya se ha resuelto. Este caso puede ocurrir porque
se pasó por alto la restricción en un principio o porque surgieron nuevas consideraciones
después de formular el modelo. Otra posibilidad es que a propósito se haya
eliminado la restricción para disminuir el esfuerzo computacional por parecer
menos restrictiva que otras ya planteadas en el modelo, pero ahora es necesario
verificar esta impresión con la solución óptima que se obtuvo.
Para ver si la nueva restricción afecta a la solución óptima actual,
todo lo que tiene que hacerse es verificar directamente si esa solución óptima
satisface la restricción. Si es así, todavía sería la mejor solución básica factible (es decir, sería la solución
óptima), aun cuando se agregara la restricción al modelo. La razón es que una
nueva restricción sólo puede eliminar algunas de las soluciones factibles
anteriores sin agregar ninguna.
Si la nueva restricción elimina la solución óptima actual, y si se
quiere encontrar la nueva solución, se introduce esta restricción a la tabla
símplex final (como un renglón adicional ) justo como si fuera la tabla
inicial, en la que se designa la variable usual (de holgura o artificial) como
la variable básica que corresponde a este nuevo renglón. Como éste tal vez
tenga coeficientes distintos de cero para algunas otras variables básicas, se debe aplicar la
conversión a la forma apropiada de eliminación de Gauss y después el paso de
reoptimización en la forma usual.
EJEMPLO
Como ejemplo de este caso, suponga que se introduce la nueva
restricción, al modelo dado en la tabla 1.3. El efecto gráfico se muestra en la
figura 4. La solución óptima anterior (0, 9) viola la nueva restricción, por lo
que la solución óptima cambia a (0, 8).
2x1 + 3x2 " 24,
Para analizar este ejemplo algebraicamente, observe que (0, 9) lleva a
que 2x1 + 3x2 = 27 >
24, entonces esta solución óptima anterior ya no es factible. Para encontrar la
nueva solución óptima, se agrega esta restricción a la tabla símplex final
actual, tal como se describió, con la variable de holgura x6 como su variable
básica inicial. Esto lleva a la primera tabla que se muestra en la tabla 1.5.
El paso de conversión a la forma apropiada de eliminación de Gauss requiere
restar el renglón 2 multiplicado por 3, del nuevo renglón, con lo que se
identifica la solución básica actual: x3 = 4, x2 = 9, x4 = 6,
x6 = -3 (x1 = 0, x5 = 0), como se muestra en la
segunda tabla símplex.
Figura 4: Región factible para el
ejemplo del caso cuatro, introducción de una nueva desigualdad.
|
Coeficiente de
|
||||||||||
|
Var bàsica
|
Ec. Núm.
|
Lado derecho
|
||||||||
|
Z
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
||||
|
Tabla simplex final revisada
|
Z
|
0
|
1
|
9/2
|
0
|
0
|
0
|
5/2
|
0
|
45
|
|
x3
|
(1)
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
4
|
|
|
x2
|
(2)
|
0
|
3/2
|
1
|
0
|
0
|
1/2
|
0
|
9
|
|
|
x4
|
(3)
|
0
|
-3
|
0
|
0
|
1
|
-1
|
0
|
6
|
|
|
x6
|
nueva
|
0
|
2
|
3
|
0
|
0
|
0
|
1
|
24
|
|
|
Convertida a la forma apropiada
|
Z
|
(0)
|
1
|
9/2
|
0
|
0
|
0
|
5/2
|
0
|
45
|
|
x3
|
(1)
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
4
|
|
|
x2
|
(2)
|
0
|
3/2
|
1
|
0
|
0
|
1/2
|
0
|
9
|
|
|
x4
|
(3)
|
0
|
-3
|
0
|
0
|
1
|
-1
|
0
|
6
|
|
|
x6
|
nueva
|
0
|
-5/2
|
0
|
0
|
0
|
-3/2
|
1
|
-3
|
|
|
nueva tabla simplex final después
|
Z
|
(0)
|
1
|
1/3
|
0
|
0
|
0
|
0
|
5/3
|
40
|
|
de reoptimizar
|
x3
|
(1)
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
4
|
|
x2
|
(2)
|
0
|
2/3
|
1
|
0
|
0
|
0
|
1/3
|
8
|
|
|
x4
|
(2)
|
0
|
-4/3
|
0
|
0
|
1
|
0
|
-2/3
|
8
|
|
|
x5
|
nueva
|
0
|
5/3
|
0
|
0
|
0
|
1
|
-2/3
|
2
|
|
Importancia del Análisis de la Sensibilidad
La importancia del
análisis de sensibilidad se manifiesta en el hecho de que los valores de las
variables que se han utilizado para llevar a cabo la evaluación del proyecto
pueden tener desviaciones con efectos de consideración en la medición de sus
resultados.
La evaluación del proyecto
será sensible a las variaciones de uno o más parámetros si, al incluir estas
variaciones en el criterio de evaluación empleado, la decisión inicial cambia.
El análisis de sensibilidad, a través de los diferentes modelos, revela el
efecto que tienen las variaciones sobre la rentabilidad en los pronósticos de
las variables relevantes.
Es importante visualizar qué variables tienen
mayor efecto en el resultado frente a distintos grados de error, en su
estimación permite decidir acerca de la necesidad de realizar estudios más
profundos de esas variables, para mejorar las estimaciones y reducir el grado
de riesgo por error.
Suscribirse a:
Entradas (Atom)