Post on 09-Mar-2015
GESTIÓN DE INVESTIGACIÓN DE OPERACIONES (GIO) – ILN250
PROF. FRANCISCO YURASZECK E.INGENIERO COMERCIAL UTFSMMAGÍSTER EN MARKETING UAI
E-MAIL: FRANCISCO.YURASZECK@USM.CL
DEPARTAMENTO DE INDUSTRIASUNIVERSIDAD TÉCNICA FEDERICO SANTA MARÍA
GESTIÓN DE INVESTIGACIÓN DE OPERACIONES
Primer Semestre 2011
Temario:
II.1. Introducción.
II.2. Resolución gráfica de problemas.
II.3. Modelos de Programación Lineal.
II.4. El Método Simplex.
II.5. Dualidad en Programación Lineal.
II.6. Análisis de Sensibilidad o Post-Optimal
1) ¿Qué ocurre con las actuales variables básicas si se
cambia algún coeficiente del lado derecho (b)?
Si calculamos: y se cumple:
Las mismas variables básicas lo son también de la
nueva solución óptima, calculada con el nuevo .
Si lo anterior no se cumple, se puede aplicar el Método
Simplex Dual.
bBx 1B
0xB
b
Ejemplo: Modificación Lado Derecho
Max 2x1 + 7x2 - 3x3
sa: x1 + 3x2 + 4x3 30
x1 + 4x2 - x3 10
x1,x2,x3 0
Sin resolver nuevamente el
problema, se desea saber si las
actuales variables básicas óptimas
del problema también lo son del
mismo problema, donde los lados
derechos corresponde al vector
b=(20,30)
x1 x2 x3 x4 x5
0 -1 5 1 -1 20
1 4 -1 0 1 10
0 1 1 0 2 20
Max 9x1 + 12x2
sa: 4x1 + 3x2 180
2x1 + 3x2 150
4x1 + 2x2 160
x1,x2 0
Encuentre un intervalo devariación para b1=180 queconserve la actual base óptimadel problema.
Sol: 150 b1 195
x1 x2 x3 x4 x5
1 0 1/2 -1/2 0 15
0 1 -1/3 2/3 0 40
0 0 -4/3 2/3 1 20
0 0 1/2 7/2 0 615
Calcule el intervalo para b2 y b3
Ejemplo: Intervalo variación Lado Derecho
Ejemplo: Intervalo variación Lado Derecho
2) ¿Qué ocurre con la actual solución óptima si se
agrega una nueva variable al problema ?
Para decidir si la actual solución básica es óptima
para el nuevo problema, calculamos el costo reducido
de la nueva variable mediante la formula:
k1T
Bkk ABccr
donde k es el índice de la nueva variable y Ak su
respectiva columna en la matriz de coeficientes. Si se
cumple que rk0 se conserva la actual solución óptima.
En caso contrario, se puede seguir con el Método
Simplex agregando a la tabla una nueva columna con
entradas B-1Ak y rk y tomando como variable entrante
a la nueva base la que acabamos de introducir al
problema.
Ejemplo: Nueva Variable
Max 9x1 + 12x2
sa: 4x1 + 3x2 180
2x1 + 3x2 150
4x1 + 2x2 160
x1,x2 0
Se desea estudiar la posibilidad deelaborar un nuevo producto conbeneficio neto igual a 8 y que requiere4, 2 y 5 unidades de los recursosasociados a cada restricción.
Sin resolver nuevamente el problema,¿Conviene elaborar el producto?
x1 x2 x3 x4 x5
1 0 1/2 -1/2 0 15
0 1 -1/3 2/3 0 40
0 0 -4/3 2/3 1 20
0 0 1/2 7/2 0 615
3) ¿Qué ocurre con la actual solución óptima del problema P) si
se cambian los coeficientes que definen la función objetivo ?
Supongamos que el vector de coeficientes en la función objetivo
cambia a un vector
La actual solución óptima también lo es para con:
nIRc
P
0x
bAx:sa
xcMin)PT
Siempre que los nuevos costos reducidos sean mayores o igualesa cero (notar que también cambia el valor de la función objetivoen la actual solución óptima). Es decir se debe cumplir que:
En caso contrario, se aplica el Método Simplex a partir de latabla final de P) con los nuevos costos reducidos y nuevo valor dela actual solución básica.
j0ABccr
ementeequivalento0DBccr
j1T
Bjj
1TBDD
Veamos los cambios que tienen lugar cuando sólo varía un
coeficiente del vector c de la función objetivo.
a) Cambio de un coeficiente asociado a una variable no-básica
xJ:
Se conserva la misma solución óptima del problema P) ssi. para
esa variable xJ:
j0ABccr j1T
Bjj
Consideremos :
Por lo tanto se conserva la misma solución ssi:
jccjj
jjjjrccrj
Ejemplo: Cambio Parámetros Función Objetivo
Max 2x1 + 7x2 - 3x3
sa: x1 + 3x2 + 4x3 30
x1 + 4x2 - x3 10
x1,x2,x3 0
Sin resolver nuevamente el
problema, se desea saber que
sucede si el beneficio del producto 2
aumenta de 7 a 9 ¿Entra X2 a la
base? ¿Cuál es el punto de
indiferencia?
x1 x2 x3 x4 x5
0 -1 5 1 -1 20
1 4 -1 0 1 10
0 1 1 0 2 20
b) Cambio en un coeficiente de la función objetivo asociado a
una variable básica:
En este caso para tener la misma solución óptima, se debe
cumplir que el costo reducido de todas las variables. cero.
0ABccr j1T
Bjj
iB
0
1
0
BBiiieciccicc
Si el incremento es cualquiera en el siguiente intervalo, se
conserva la misma solución óptima:
donde rj es el costo reducido de la respectiva variable no básica
en la actual solución óptima y los coeficientes yij denotan las
entradas en la tabla final del Simplex asociadas a la variable
básica xi (cuyo costo cambia) y la respectiva variable no básica
xj
0y/y
rMini0y/
y
rMax
ij
ij
j
ij
ij
j
Ejemplo: Cambio Parámetros Función Objetivo
Max 20x1 + 15x2
sa: 2x1 + 2x2 8
2x1 + x2 6
x1,x2 0
Encontrar un intervalo devariación para C1 y C2 queconserven la actual soluciónóptima.
Sol: -30 C1 -15
-20 C2 -10
x1 x2 x3 x4
0 1 1 -1 2
1 0 -1/2 1 2
0 0 5 5 70
Ejemplo: Cambio Parámetros Función Objetivo
Max 2x1 + 7x2 - 3x3
sa: x1 + 3x2 + 4x3 30
x1 + 4x2 - x3 10
x1,x2,x3 0
Sin resolver nuevamente el
problema, se desea saber que
sucede si se modifica los
parámetros de la función
objetivo, quedando éstos de la
siguiente forma:
Z = x1 + 5x2 - 2x3
x1 x2 x3 x4 x5
0 -1 5 1 -1 20
1 4 -1 0 1 10
0 1 1 0 2 20
Ejemplo: Nueva Restricción
Max 2x1 + 7x2 - 3x3
sa: x1 + 3x2 + 4x3 30
x1 + 4x2 - x3 10
x1,x2,x3 0
Sin resolver nuevamente elproblema, se desea saber quesucede si se considera unanueva restricción de la forma:
3x1 + 2x2 + 3x3 25
x1 x2 x3 x4 x5
0 -1 5 1 -1 20
1 4 -1 0 1 10
0 1 1 0 2 20
Ejercicio: Cambio «lado derecho»
Max 2x1 + 7x2 - 3x3
sa: x1 + 3x2 + 4x3 30
x1 + 4x2 - x3 10
x1,x2,x3 0
Sea ahora b=(30+3e,10-e) epuede ser positivo o negativo.Determinar los valores de eque hacen infactible a laactual solución básica(óptima) del problemaoriginal.
x1 x2 x3 x4 x5
0 -1 5 1 -1 20
1 4 -1 0 1 10
0 1 1 0 2 20
Actividad en Clases
Actividad en Clases