Xxx Economia

CAPÍTULO 5

ANÁLISIS POST-ÓPTIMO Y ANÁLISIS DE LA SENSIBILIDAD

5.1.- Introducción al Análisis Post-Óptimo
En los modelos de programación lineal los coeficientes de la función objetivo, de las variables y de las restricciones se dan como datos de entrada o como parámetros fijos del modelo. En los problemas reales los datos de entrada no son exactos sino aproximados. Puesto que los datosreales suelen ser aproximados podemos preguntarnos ¿cómo variará la solución óptima de un problema de programación lineal al modificar los coeficientes del modelo?. La respuesta a esto nos la proporciona el Análisis Post-Óptimo. En el procedimiento de resolución siempre se partirá de una solución óptima al problema original. Supongamos resuelto el problema siguiente: Min z = cTX st AX = b X0

(5.1)Queremos investigar los cambios que experimenta la solución óptima cuando alguno de los datos del problema es modificado, a partir de la última tabla del simplex. En todo el desarrollo del análisis post-óptimo los cálculos se han de realizar en la última tabla del simplex. Supongamos que el método del simplex nos proporciona una base óptima B, que está formada por los m primeros vectores y,por tanto, podemos conocer B-1. Recopilando una serie de relaciones ya vistas en temas anteriores:

137

138 XB = B-1 b, Xj = B-1 Aj zj = cBT Xj = cBT B-1 Aj (zj - cj )= cBT B-1 Aj - cj (j=1, 2, …, n)

Investigación Operativa

Las modificaciones que estudiaremos en el análisis post-óptimo son: i) Modificación de los coeficientes de la función objetivo. ii) Modificación de las constantes derestricción. iii) Modificación de los coeficientes técnicos. Pasemos a analizar cada una de estas modificaciones.

5.2. Modificación de los coeficientes de la función objetivo
Supongamos que el coeficiente de la función objetivo modificado sea ck pasando a valer c' k . Veamos cómo afecta este cambio a la solución óptima del problema 5.1. La base óptima B se forma con los m primeros vectores, B= { A1, A2,…, Am}, es decir, la base final será B = { X1, X2,…, Xm}. Pueden ocurrir dos casos: 5.2.1. Modificación de un coeficiente básico de la función objetivo Sea ckcB, tenemos zj = cBT Xj = cBT B-1 Aj (j=1, 2, ..., n), luego la variación de un coeficiente afecta a todos los zj, pasando a valer z' j :

z’j = c’BT B-1 Aj (j=1, 2, ..., n) con c’B = cB excepto la componente k-ésima. Operandoz’j - cj = c’BT B-1 Aj - cj= c’BT Xj -cj =  c'i  ij  c j =
i 1 m

=  ci  ij  c j  (c'k  kj  ck kj ) = ( z j  c j )  (c'k ck ) kj
i 1

m

Análisis Post-óptimo y Análisis de la Sensibilidad

139

Veamos qué ocurre para los casos en los que j pertenezca a la base y no pertenezca a la base B. Caso 1: jB, es decir, (j=1, 2, …, m). En este caso tenemos (zj - cj) = 0 y kk=1,kj= 0 luego z’k – ck = ( z k  ck )  (c'k ck ) z’k – c’k = ( z k  ck ) = 0 y, por tanto, no se modifica la solución óptima inicial. Caso 2: jB, es decir, (j = m+1, m+2, …, n). En este caso tenemos
' z’j - cj = ( z j  c j )  (ck  ck ) kj

 0  Puede ocurrir que z ' j c j sea  0  0 

Para el último caso (> 0) se continúa con el método simplex modificando ' solamente la últimatabla del simplex al cambiar ck por ck . En este caso habrá una modificación de la solución óptima del problema planteado inicialmente. Ejercicio 5.1. Dado el problema siguiente: Max z = -x1 + 2 x2 st 3x1 + 4x2  12 2x1 - x2  2 x1, x2 0 a) Obtener la última tabla del simplex. b) Suponiendo que la última tabla del simplex es

140

Investigación Operativa

Base A2 A4

cB -2 0 z, zj, j

cjb 3 5 -6 zj-cj j(zj-cj)

1 A1 3/4 11/4 -6/4 -5/2

-2 A2 1 0 -2 0 -

0 A3 1/4 1/4 -2/4 -1/2 -

0 A4 0 1 0 0 -

c) Compruebe que si hacemos el cambio c2 =-2 por c'2 =-3, se mantiene z =-9. d) Compruebe que, si hacemos el cambio c2 = -2 por c'2 = 1, el valor de la función objetivo cambia (aumenta) a z = 0. e) Compruebe que, si hacemos el cambio c1 = 1 por c'1 = -3, el valor de la...