Introducción

Análisis Paramétrico

Programación Lineal Paramétrica

Docente: Rafael Asmat Uceda

Departamento de Matemáticas
Universidad Nacional de Trujillo

28 de diciembre de 2021

Uceda, R.A. Programación Lineal Paramétrica

 Introducción
Análisis Paramétrico

Introducción

El análisis paramétrico se utiliza con bastante frecuencia en

optimización a gran escala y optimización no lineal, donde, con
frecuencia, se encuentra una dirección hacia la la función objetivo
o las restricciones se perturbaron, y luego se intenta moverse en
esta dirección.

De este modo, buscamos soluciones óptimas a una clase de

problemas perturbando, ya sea el vector objetivo o el vector de
recursos, a lo largo de una dirección fija.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción
Análisis Paramétrico

Introducción

El análisis paramétrico se utiliza con bastante frecuencia en

optimización a gran escala y optimización no lineal, donde, con
frecuencia, se encuentra una dirección hacia la la función objetivo
o las restricciones se perturbaron, y luego se intenta moverse en
esta dirección.

De este modo, buscamos soluciones óptimas a una clase de

problemas perturbando, ya sea el vector objetivo o el vector de
recursos, a lo largo de una dirección fija.

Consideremos el siguiente problema:

Minimizar cT x
s.a. Ax = b
x≥0

Uceda, R.A. Programación Lineal Paramétrica

 Introducción
Análisis Paramétrico

Introducción

El análisis paramétrico se utiliza con bastante frecuencia en

optimización a gran escala y optimización no lineal, donde, con
frecuencia, se encuentra una dirección hacia la la función objetivo
o las restricciones se perturbaron, y luego se intenta moverse en
esta dirección.

De este modo, buscamos soluciones óptimas a una clase de

problemas perturbando, ya sea el vector objetivo o el vector de
recursos, a lo largo de una dirección fija.

Consideremos el siguiente problema:

Minimizar cT x
s.a. Ax = b
x≥0

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Supongamos que, B es una base óptima y que el vector de costos

0
c se perturba a lo largo de la dirección de costos c , es decir, se
0
reemplaza c por c + λc , con λ ≥ 0.

Nos interesa encontrar los puntos óptimos y los correspondientes

valores objetivos como función de λ ≥ 0.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Supongamos que, B es una base óptima y que el vector de costos

0
c se perturba a lo largo de la dirección de costos c , es decir, se
0
reemplaza c por c + λc , con λ ≥ 0.

Nos interesa encontrar los puntos óptimos y los correspondientes

valores objetivos como función de λ ≥ 0.
0 0 0
Descomponiendo A en [B N], c en (cB , cN ) y c en (cB , cN ),
tenemos:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Supongamos que, B es una base óptima y que el vector de costos

0
c se perturba a lo largo de la dirección de costos c , es decir, se
0
reemplaza c por c + λc , con λ ≥ 0.

Nos interesa encontrar los puntos óptimos y los correspondientes

valores objetivos como función de λ ≥ 0.
0 0 0
Descomponiendo A en [B N], c en (cB , cN ) y c en (cB , cN ),
tenemos:
0 0
z − (cB + λcB )xB − (cN + λcN )xN = 0

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Supongamos que, B es una base óptima y que el vector de costos

0
c se perturba a lo largo de la dirección de costos c , es decir, se
0
reemplaza c por c + λc , con λ ≥ 0.

Nos interesa encontrar los puntos óptimos y los correspondientes

valores objetivos como función de λ ≥ 0.
0 0 0
Descomponiendo A en [B N], c en (cB , cN ) y c en (cB , cN ),
tenemos:
0 0
z − (cB + λcB )xB − (cN + λcN )xN = 0

BxB + NxN = b

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Supongamos que, B es una base óptima y que el vector de costos

0
c se perturba a lo largo de la dirección de costos c , es decir, se
0
reemplaza c por c + λc , con λ ≥ 0.

Nos interesa encontrar los puntos óptimos y los correspondientes

valores objetivos como función de λ ≥ 0.
0 0 0
Descomponiendo A en [B N], c en (cB , cN ) y c en (cB , cN ),
tenemos:
0 0
z − (cB + λcB )xB − (cN + λcN )xN = 0

BxB + NxN = b
0 0
Actualizando la tabla y denotando cB yj por zj , tenemos:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Supongamos que, B es una base óptima y que el vector de costos

0
c se perturba a lo largo de la dirección de costos c , es decir, se
0
reemplaza c por c + λc , con λ ≥ 0.

Nos interesa encontrar los puntos óptimos y los correspondientes

valores objetivos como función de λ ≥ 0.
0 0 0
Descomponiendo A en [B N], c en (cB , cN ) y c en (cB , cN ),
tenemos:
0 0
z − (cB + λcB )xB − (cN + λcN )xN = 0

BxB + NxN = b
0 0
Actualizando la tabla y denotando cB yj por zj , tenemos:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

X 0 0 0
z+ [(zj − cj ) + λ(zj − cj )]xj = cB b + λcB b
j∈R
P
xB + j∈R yj xj = b,

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

X 0 0 0
z+ [(zj − cj ) + λ(zj − cj )]xj = cB b + λcB b
j∈R
P
xB + j∈R yj xj = b,

donde R es el actual conjunto de ı́ndices asociados con las

variables no básicas.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

X 0 0 0
z+ [(zj − cj ) + λ(zj − cj )]xj = cB b + λcB b
j∈R
P
xB + j∈R yj xj = b,

donde R es el actual conjunto de ı́ndices asociados con las

variables no básicas.

En la tabla actual se tiene λ = 0, lo cual nos da una solución

básica factible óptima del problema original sin perturbación.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

X 0 0 0
z+ [(zj − cj ) + λ(zj − cj )]xj = cB b + λcB b
j∈R
P
xB + j∈R yj xj = b,

donde R es el actual conjunto de ı́ndices asociados con las

variables no básicas.

En la tabla actual se tiene λ = 0, lo cual nos da una solución

básica factible óptima del problema original sin perturbación.

Nos gustarı́a saber hasta dónde podemos movernos en la dirección

c manteniendo al mismo tiempo la optimalidad del punto actual.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

X 0 0 0
z+ [(zj − cj ) + λ(zj − cj )]xj = cB b + λcB b
j∈R
P
xB + j∈R yj xj = b,

donde R es el actual conjunto de ı́ndices asociados con las

variables no básicas.

En la tabla actual se tiene λ = 0, lo cual nos da una solución

básica factible óptima del problema original sin perturbación.

Nos gustarı́a saber hasta dónde podemos movernos en la dirección

c manteniendo al mismo tiempo la optimalidad del punto actual.
0 0
Sea S = {j : (zj − cj ) > 0}. Si S = ∅, entonces la actual solución
es óptima para todo valor de λ ≥ 0. Caso contrario, calculamos λ̂
como sigue:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

X 0 0 0
z+ [(zj − cj ) + λ(zj − cj )]xj = cB b + λcB b
j∈R
P
xB + j∈R yj xj = b,

donde R es el actual conjunto de ı́ndices asociados con las

variables no básicas.

En la tabla actual se tiene λ = 0, lo cual nos da una solución

básica factible óptima del problema original sin perturbación.

Nos gustarı́a saber hasta dónde podemos movernos en la dirección

c manteniendo al mismo tiempo la optimalidad del punto actual.
0 0
Sea S = {j : (zj − cj ) > 0}. Si S = ∅, entonces la actual solución
es óptima para todo valor de λ ≥ 0. Caso contrario, calculamos λ̂
como sigue:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

( )
−(zj − cj ) −(zk − ck )
λ̂ = mı́n 0 0 = 0 0
j∈S zj − cj zk − ck

Sea λ1 = λ̂. Para λ ∈ [0, λ1 ] la actual solución es óptima y el valor

objetivo óptimo viene dado por:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

( )
−(zj − cj ) −(zk − ck )
λ̂ = mı́n 0 0 = 0 0
j∈S zj − cj zk − ck

Sea λ1 = λ̂. Para λ ∈ [0, λ1 ] la actual solución es óptima y el valor

objetivo óptimo viene dado por:
0 0
cB b + λcB b = cB B −1 b + λcB B −1 b

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

( )
−(zj − cj ) −(zk − ck )
λ̂ = mı́n 0 0 = 0 0
j∈S zj − cj zk − ck

Sea λ1 = λ̂. Para λ ∈ [0, λ1 ] la actual solución es óptima y el valor

objetivo óptimo viene dado por:
0 0
cB b + λcB b = cB B −1 b + λcB B −1 b

Para λ ∈ [0, λ1 ] los precios sombra en la tabla simplex son

sustituidos por:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

( )
−(zj − cj ) −(zk − ck )
λ̂ = mı́n 0 0 = 0 0
j∈S zj − cj zk − ck

Sea λ1 = λ̂. Para λ ∈ [0, λ1 ] la actual solución es óptima y el valor

objetivo óptimo viene dado por:
0 0
cB b + λcB b = cB B −1 b + λcB B −1 b

Para λ ∈ [0, λ1 ] los precios sombra en la tabla simplex son

sustituidos por:
0 0
(zj − cj ) + λ(zj − cj )

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

( )
−(zj − cj ) −(zk − ck )
λ̂ = mı́n 0 0 = 0 0
j∈S zj − cj zk − ck

Sea λ1 = λ̂. Para λ ∈ [0, λ1 ] la actual solución es óptima y el valor

objetivo óptimo viene dado por:
0 0
cB b + λcB b = cB B −1 b + λcB B −1 b

Para λ ∈ [0, λ1 ] los precios sombra en la tabla simplex son

sustituidos por:
0 0
(zj − cj ) + λ(zj − cj )
En λ = λ1 , xk se ingresa a la base (si existe un bloque de
variables). Luego de actualizar la tabla, el proceso se repite
recalculando S y λ̂ y haciendo λ2 = λ̂.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

( )
−(zj − cj ) −(zk − ck )
λ̂ = mı́n 0 0 = 0 0
j∈S zj − cj zk − ck

Sea λ1 = λ̂. Para λ ∈ [0, λ1 ] la actual solución es óptima y el valor

objetivo óptimo viene dado por:
0 0
cB b + λcB b = cB B −1 b + λcB B −1 b

Para λ ∈ [0, λ1 ] los precios sombra en la tabla simplex son

sustituidos por:
0 0
(zj − cj ) + λ(zj − cj )
En λ = λ1 , xk se ingresa a la base (si existe un bloque de
variables). Luego de actualizar la tabla, el proceso se repite
recalculando S y λ̂ y haciendo λ2 = λ̂.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Para λ ∈ [λ1 , λ2 ] la actual solución es óptima y su valor objetivo

viene dado por:
0 0
cB b + λcB b = cB B −1 b + λcB B −1 b,

donde B es la base actual.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Para λ ∈ [λ1 , λ2 ] la actual solución es óptima y su valor objetivo

viene dado por:
0 0
cB b + λcB b = cB B −1 b + λcB B −1 b,

donde B es la base actual.

El proceso se repite hasta que el conjunto S se vuelva vacı́o. Si no

hay un bloque de variables cuando xk ingresa a la base, entonces el
problema es no acotado para todos los valores de λ mayores que el
valor actual.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Para λ ∈ [λ1 , λ2 ] la actual solución es óptima y su valor objetivo

viene dado por:
0 0
cB b + λcB b = cB B −1 b + λcB B −1 b,

donde B es la base actual.

El proceso se repite hasta que el conjunto S se vuelva vacı́o. Si no

hay un bloque de variables cuando xk ingresa a la base, entonces el
problema es no acotado para todos los valores de λ mayores que el
valor actual.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ejemplo 1
Considere el siguiente problema:
Minimizar −x1 − 3x2
Sujeto a x1 + x2 ≤ 6
−x1 + 2x2 ≤ 6
x1 ≥ 0, x2 ≥ 0

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ejemplo 1
Considere el siguiente problema:
Minimizar −x1 − 3x2
Sujeto a x1 + x2 ≤ 6
−x1 + 2x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
Se desea encontrar las soluciones óptimas y los valores objetivos
óptimos de la clase de problemas cuya función objetivo es
(−1 + 2λ, −3 + λ) para λ ≥ 0; es decir, perturbando el vector de
costos a lo largo del vector (2, 1).

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ejemplo 1
Considere el siguiente problema:
Minimizar −x1 − 3x2
Sujeto a x1 + x2 ≤ 6
−x1 + 2x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
Se desea encontrar las soluciones óptimas y los valores objetivos
óptimos de la clase de problemas cuya función objetivo es
(−1 + 2λ, −3 + λ) para λ ≥ 0; es decir, perturbando el vector de
costos a lo largo del vector (2, 1).

Solución.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ejemplo 1
Considere el siguiente problema:
Minimizar −x1 − 3x2
Sujeto a x1 + x2 ≤ 6
−x1 + 2x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
Se desea encontrar las soluciones óptimas y los valores objetivos
óptimos de la clase de problemas cuya función objetivo es
(−1 + 2λ, −3 + λ) para λ ≥ 0; es decir, perturbando el vector de
costos a lo largo del vector (2, 1).

Solución.
Primero resolvemos el problema con λ = 0, donde x3 y x4 son
variables de holgura. La tabla óptima para λ = 0 es la siguiente:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ejemplo 1
Considere el siguiente problema:
Minimizar −x1 − 3x2
Sujeto a x1 + x2 ≤ 6
−x1 + 2x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
Se desea encontrar las soluciones óptimas y los valores objetivos
óptimos de la clase de problemas cuya función objetivo es
(−1 + 2λ, −3 + λ) para λ ≥ 0; es decir, perturbando el vector de
costos a lo largo del vector (2, 1).

Solución.
Primero resolvemos el problema con λ = 0, donde x3 y x4 son
variables de holgura. La tabla óptima para λ = 0 es la siguiente:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 35 − 23 −14
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para encontrar el rango de valores para el cual esta tabla es

0 0
óptima, primero hallamos cB B −1 N − cN :

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 35 − 23 −14
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para encontrar el rango de valores para el cual esta tabla es

0 0
óptima, primero hallamos cB B −1 N − cN :
0 0 0 0 0
cB B −1 N − cN = cB (y3 , y4 ) − (c3 , c4 )

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 35 − 23 −14
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para encontrar el rango de valores para el cual esta tabla es

0 0
óptima, primero hallamos cB B −1 N − cN :
0 0 0 0 0
cB B −1 N − cN = cB (y3 , y4 ) − (c3 , c4 )
!
2
3 − 31
= (2, 1) 1 1 − (0, 0)
3 3

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 35 − 23 −14
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para encontrar el rango de valores para el cual esta tabla es

0 0
óptima, primero hallamos cB B −1 N − cN :
0 0 0 0 0
cB B −1 N − cN = cB (y3 , y4 ) − (c3 , c4 )
!
2
3 − 31
= (2, 1) 1 1 − (0, 0)
 3 3
5 1
= 3, −3

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 35 − 23 −14
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para encontrar el rango de valores para el cual esta tabla es

0 0
óptima, primero hallamos cB B −1 N − cN :
0 0 0 0 0
cB B −1 N − cN = cB (y3 , y4 ) − (c3 , c4 )
!
2
3 − 31
= (2, 1) 1 1 − (0, 0)
 3 3
5 1
= 3, −3

Por tanto, S = {3}. Ahora calculamos λ̂:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 35 − 23 −14
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para encontrar el rango de valores para el cual esta tabla es

0 0
óptima, primero hallamos cB B −1 N − cN :
0 0 0 0 0
cB B −1 N − cN = cB (y3 , y4 ) − (c3 , c4 )
!
2
3 − 31
= (2, 1) 1 1 − (0, 0)
 3 3
5 1
= 3, −3

Por tanto, S = {3}. Ahora calculamos λ̂:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

−(z3 − c3 ) − (−5/3)
λ̂ = 0 0 = =1
z3 − c3 5/3
Ası́, λ1 = 1 y para λ ∈ [0, 1] la base (a1 , a2 ) permanece óptima.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

−(z3 − c3 ) − (−5/3)
λ̂ = 0 0 = =1
z3 − c3 5/3
Ası́, λ1 = 1 y para λ ∈ [0, 1] la base (a1 , a2 ) permanece óptima.

El valor objetivo óptimo z(λ) en este intervalo viene dado por:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

−(z3 − c3 ) − (−5/3)
λ̂ = 0 0 = =1
z3 − c3 5/3
Ası́, λ1 = 1 y para λ ∈ [0, 1] la base (a1 , a2 ) permanece óptima.

El valor objetivo óptimo z(λ) en este intervalo viene dado por:

0
z(λ) = cB b + λcB b

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

−(z3 − c3 ) − (−5/3)
λ̂ = 0 0 = =1
z3 − c3 5/3
Ası́, λ1 = 1 y para λ ∈ [0, 1] la base (a1 , a2 ) permanece óptima.

El valor objetivo óptimo z(λ) en este intervalo viene dado por:

0
z(λ) = cB b + λcB b !
2
= −14 + λ(2, 1) = −14 + 8λ
4

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

−(z3 − c3 ) − (−5/3)
λ̂ = 0 0 = =1
z3 − c3 5/3
Ası́, λ1 = 1 y para λ ∈ [0, 1] la base (a1 , a2 ) permanece óptima.

El valor objetivo óptimo z(λ) en este intervalo viene dado por:

0
z(λ) = cB b + λcB b !
2
= −14 + λ(2, 1) = −14 + 8λ
4

Los precios sombra de las variables no básicas x3 y x4 son:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

−(z3 − c3 ) − (−5/3)
λ̂ = 0 0 = =1
z3 − c3 5/3
Ası́, λ1 = 1 y para λ ∈ [0, 1] la base (a1 , a2 ) permanece óptima.

El valor objetivo óptimo z(λ) en este intervalo viene dado por:

0
z(λ) = cB b + λcB b !
2
= −14 + λ(2, 1) = −14 + 8λ
4

Los precios sombra de las variables no básicas x3 y x4 son:

0 0 5 5
(z3 − c3 ) + λ(z3 − c3 ) = − + λ
3 3

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

−(z3 − c3 ) − (−5/3)
λ̂ = 0 0 = =1
z3 − c3 5/3
Ası́, λ1 = 1 y para λ ∈ [0, 1] la base (a1 , a2 ) permanece óptima.

El valor objetivo óptimo z(λ) en este intervalo viene dado por:

0
z(λ) = cB b + λcB b !
2
= −14 + λ(2, 1) = −14 + 8λ
4

Los precios sombra de las variables no básicas x3 y x4 son:

0 0 5 5
(z3 − c3 ) + λ(z3 − c3 ) = − + λ
3 3

0 0 2 1
(z4 − c4 ) + λ(z4 − c4 ) = − − λ
3 3
Uceda, R.A. Programación Lineal Paramétrica
 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

−(z3 − c3 ) − (−5/3)
λ̂ = 0 0 = =1
z3 − c3 5/3
Ası́, λ1 = 1 y para λ ∈ [0, 1] la base (a1 , a2 ) permanece óptima.

El valor objetivo óptimo z(λ) en este intervalo viene dado por:

0
z(λ) = cB b + λcB b !
2
= −14 + λ(2, 1) = −14 + 8λ
4

Los precios sombra de las variables no básicas x3 y x4 son:

0 0 5 5
(z3 − c3 ) + λ(z3 − c3 ) = − + λ
3 3

0 0 2 1
(z4 − c4 ) + λ(z4 − c4 ) = − − λ
3 3
Uceda, R.A. Programación Lineal Paramétrica
 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Luego, la tabla óptima para cualquier λ en el intervalo [0,1] viene

dada por:

z x1 x2 x3 x4 RHS
z 1 0 0 − 53 + 35 λ − 23 − 13 λ −14 + 8λ
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Luego, la tabla óptima para cualquier λ en el intervalo [0,1] viene

dada por:

z x1 x2 x3 x4 RHS
z 1 0 0 − 53 + 35 λ − 23 − 13 λ −14 + 8λ
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para λ = 1, el coeficiente de x3 en la fila 0 es igual a cero y x3

ingresa a la base quedando la nueva tabla como sigue:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Luego, la tabla óptima para cualquier λ en el intervalo [0,1] viene

dada por:

z x1 x2 x3 x4 RHS
z 1 0 0 − 53 + 35 λ − 23− 13 λ −14 + 8λ
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para λ = 1, el coeficiente de x3 en la fila 0 es igual a cero y x3

ingresa a la base quedando la nueva tabla como sigue:

z x1 x2 x3 x4 RHS
z 1 0 0 0 −1 −6
3
x3 0 2 0 1 − 21 3
x2 0 − 12 1 0 1
2 3

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Luego, la tabla óptima para cualquier λ en el intervalo [0,1] viene

dada por:

z x1 x2 x3 x4 RHS
z 1 0 0 − 53 + 35 λ − 23− 13 λ −14 + 8λ
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para λ = 1, el coeficiente de x3 en la fila 0 es igual a cero y x3

ingresa a la base quedando la nueva tabla como sigue:

z x1 x2 x3 x4 RHS
z 1 0 0 0 −1 −6
3
x3 0 2 0 1 − 21 3
x2 0 − 12 1 0 1
2 3

Nos gustarı́a hallar el intervalo [1, λ2 ] en el cual la anterior tabla es

óptima. Notemos que:
Uceda, R.A. Programación Lineal Paramétrica
 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Luego, la tabla óptima para cualquier λ en el intervalo [0,1] viene

dada por:

z x1 x2 x3 x4 RHS
z 1 0 0 − 53 + 35 λ − 23− 13 λ −14 + 8λ
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para λ = 1, el coeficiente de x3 en la fila 0 es igual a cero y x3

ingresa a la base quedando la nueva tabla como sigue:

z x1 x2 x3 x4 RHS
z 1 0 0 0 −1 −6
3
x3 0 2 0 1 − 21 3
x2 0 − 12 1 0 1
2 3

Nos gustarı́a hallar el intervalo [1, λ2 ] en el cual la anterior tabla es

óptima. Notemos que:
Uceda, R.A. Programación Lineal Paramétrica
 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

!
3 5
z1 − c1 = cB y1 − c1 = (0, 3) 2 +1=
− 12 2
!
− 21 3
z4 − c4 = cB y4 − c4 = (0, 3) 1 −0=−
2 2

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

!
3 5
z1 − c1 = cB y1 − c1 = (0, 3) 2 +1=
− 12 2
!
− 21 3
z4 − c4 = cB y4 − c4 = (0, 3) 1 −0=−
2 2
!
0 0 0 0
3 5
z1 − c1 = cB y1 − c1 = (0, 1) 2 −2=−
1
−2 2

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

!
3 5
z1 − c1 = cB y1 − c1 = (0, 3) 2 +1=
− 12 2
!
− 21 3
z4 − c4 = cB y4 − c4 = (0, 3) 1 −0=−
2 2
!
0 0 0 0
3 5
z1 − c1 = cB y1 − c1 = (0, 1) 2 −2=−
1
−2 2
!
0 0 0 0 − 21 1
z4 − c4 = cB y4 − c4 = (0, 1) 1 −0=
2 2

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

!
3 5
z1 − c1 = cB y1 − c1 = (0, 3) 2 +1=
− 12 2
!
− 21 3
z4 − c4 = cB y4 − c4 = (0, 3) 1 −0=−
2 2
!
0 0 0 0
3 5
z1 − c1 = cB y1 − c1 = (0, 1) 2 −2=−
1
−2 2
!
0 0 0 0 − 21 1
z4 − c4 = cB y4 − c4 = (0, 1) 1 −0=
2 2
Por tanto, los precios sombra para las variables no básicas x1 y x4
serán:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

!
3 5
z1 − c1 = cB y1 − c1 = (0, 3) 2 +1=
− 12 2
!
− 21 3
z4 − c4 = cB y4 − c4 = (0, 3) 1 −0=−
2 2
!
0 0 0 0
3 5
z1 − c1 = cB y1 − c1 = (0, 1) 2 −2=−
1
−2 2
!
0 0 0 0 − 21 1
z4 − c4 = cB y4 − c4 = (0, 1) 1 −0=
2 2
Por tanto, los precios sombra para las variables no básicas x1 y x4
serán:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 5 5
(z1 − c1 ) + λ(z1 − c1 ) = − λ
2 2
0 0 3 1
(z4 − c4 ) + λ(z4 − c4 ) = − + λ
2 2

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 5 5
(z1 − c1 ) + λ(z1 − c1 ) = − λ
2 2
0 0 3 1
(z4 − c4 ) + λ(z4 − c4 ) = − + λ
2 2
De este modo, para λ ∈ [1, 3] los precios sombra son no positivos y
la base consistente de a3 y a2 es óptima.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 5 5
(z1 − c1 ) + λ(z1 − c1 ) = − λ
2 2
0 0 3 1
(z4 − c4 ) + λ(z4 − c4 ) = − + λ
2 2
De este modo, para λ ∈ [1, 3] los precios sombra son no positivos y
la base consistente de a3 y a2 es óptima.

Notemos que λ = 3 también puede determinarse como sigue:

S = {4} y

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 5 5
(z1 − c1 ) + λ(z1 − c1 ) = − λ
2 2
0 0 3 1
(z4 − c4 ) + λ(z4 − c4 ) = − + λ
2 2
De este modo, para λ ∈ [1, 3] los precios sombra son no positivos y
la base consistente de a3 y a2 es óptima.

Notemos que λ = 3 también puede determinarse como sigue:

S = {4} y
−(z4 − c4 ) 3/2
λ= 0 0 = =3
z4 − c4 1/2

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 5 5
(z1 − c1 ) + λ(z1 − c1 ) = − λ
2 2
0 0 3 1
(z4 − c4 ) + λ(z4 − c4 ) = − + λ
2 2
De este modo, para λ ∈ [1, 3] los precios sombra son no positivos y
la base consistente de a3 y a2 es óptima.

Notemos que λ = 3 también puede determinarse como sigue:

S = {4} y
−(z4 − c4 ) 3/2
λ= 0 0 = =3
z4 − c4 1/2
En el intervalo [1, 3] la función objetivo viene dada por:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 5 5
(z1 − c1 ) + λ(z1 − c1 ) = − λ
2 2
0 0 3 1
(z4 − c4 ) + λ(z4 − c4 ) = − + λ
2 2
De este modo, para λ ∈ [1, 3] los precios sombra son no positivos y
la base consistente de a3 y a2 es óptima.

Notemos que λ = 3 también puede determinarse como sigue:

S = {4} y
−(z4 − c4 ) 3/2
λ= 0 0 = =3
z4 − c4 1/2
En el intervalo [1, 3] la función objetivo viene dada por:
0
z(λ) = cB b + λcB b

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 5 5
(z1 − c1 ) + λ(z1 − c1 ) = − λ
2 2
0 0 3 1
(z4 − c4 ) + λ(z4 − c4 ) = − + λ
2 2
De este modo, para λ ∈ [1, 3] los precios sombra son no positivos y
la base consistente de a3 y a2 es óptima.

Notemos que λ = 3 también puede determinarse como sigue:

S = {4} y
−(z4 − c4 ) 3/2
λ= 0 0 = =3
z4 − c4 1/2
En el intervalo [1, 3] la función objetivo viene dada por:
0
z(λ) = cB b + λcB b ! !
3 3
= (0, −3) + λ(0, 1) = −9 + 3λ
3 3
Uceda, R.A. Programación Lineal Paramétrica
 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 5 5
(z1 − c1 ) + λ(z1 − c1 ) = − λ
2 2
0 0 3 1
(z4 − c4 ) + λ(z4 − c4 ) = − + λ
2 2
De este modo, para λ ∈ [1, 3] los precios sombra son no positivos y
la base consistente de a3 y a2 es óptima.

Notemos que λ = 3 también puede determinarse como sigue:

S = {4} y
−(z4 − c4 ) 3/2
λ= 0 0 = =3
z4 − c4 1/2
En el intervalo [1, 3] la función objetivo viene dada por:
0
z(λ) = cB b + λcB b ! !
3 3
= (0, −3) + λ(0, 1) = −9 + 3λ
3 3
Uceda, R.A. Programación Lineal Paramétrica
 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 5 5
(z1 − c1 ) + λ(z1 − c1 ) = − λ
2 2
0 0 3 1
(z4 − c4 ) + λ(z4 − c4 ) = − + λ
2 2
De este modo, para λ ∈ [1, 3] los precios sombra son no positivos y
la base consistente de a3 y a2 es óptima.

Notemos que λ = 3 también puede determinarse como sigue:

S = {4} y
−(z4 − c4 ) 3/2
λ= 0 0 = =3
z4 − c4 1/2
En el intervalo [1, 3] la función objetivo viene dada por:
0
z(λ) = cB b + λcB b ! !
3 3
= (0, −3) + λ(0, 1) = −9 + 3λ
3 3
Uceda, R.A. Programación Lineal Paramétrica
 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Luego, la tabla óptima para λ ∈ [1, 3] será:

z x1 x2 x3 x4 RHS
5
z 1 2 − 52 λ 0 0 − 23 + 12 λ −9 + 3λ
3
x3 0 2 0 1 − 12 3
x2 0 − 12 1 0 1
2 3

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Luego, la tabla óptima para λ ∈ [1, 3] será:

z x1 x2 x3 x4 RHS
5
z 1 2 − 52 λ 0 0 − 23 + 12 λ −9 + 3λ
3
x3 0 2 0 1 − 12 3
x2 0 − 12 1 0 1
2 3

En λ = 3, el coeficiente de x4 en la fila 0 es igual a cero y ası́, x4

ingresa a la base, quedando la siguiente tabla:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Luego, la tabla óptima para λ ∈ [1, 3] será:

z x1 x2 x3 x4 RHS
5
z 1 2 − 52 λ 0 0 − 23 + 12 λ −9 + 3λ
3
x3 0 2 0 1 − 12 3
x2 0 − 12 1 0 1
2 3

En λ = 3, el coeficiente de x4 en la fila 0 es igual a cero y ası́, x4

ingresa a la base, quedando la siguiente tabla:

z x1 x2 x3 x4 RHS
z 1 −5 0 0 0 0
x3 0 1 1 1 0 6
x4 0 −1 2 0 1 6

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Luego, la tabla óptima para λ ∈ [1, 3] será:

z x1 x2 x3 x4 RHS
5
z 1 2 − 52 λ 0 0 − 23 + 12 λ −9 + 3λ
3
x3 0 2 0 1 − 12 3
x2 0 − 12 1 0 1
2 3

En λ = 3, el coeficiente de x4 en la fila 0 es igual a cero y ası́, x4

ingresa a la base, quedando la siguiente tabla:

z x1 x2 x3 x4 RHS
z 1 −5 0 0 0 0
x3 0 1 1 1 0 6
x4 0 −1 2 0 1 6

Nos gustarı́a calcular el intervalo en el cual la tabla anterior es

óptima. Primero calculamos:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Luego, la tabla óptima para λ ∈ [1, 3] será:

z x1 x2 x3 x4 RHS
5
z 1 2 − 52 λ 0 0 − 23 + 12 λ −9 + 3λ
3
x3 0 2 0 1 − 12 3
x2 0 − 12 1 0 1
2 3

En λ = 3, el coeficiente de x4 en la fila 0 es igual a cero y ası́, x4

ingresa a la base, quedando la siguiente tabla:

z x1 x2 x3 x4 RHS
z 1 −5 0 0 0 0
x3 0 1 1 1 0 6
x4 0 −1 2 0 1 6

Nos gustarı́a calcular el intervalo en el cual la tabla anterior es

óptima. Primero calculamos:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 0 0
z1 − c1 = cB y1 − c1 = −2

0 0 0 0
z2 − c2 = cB y2 − c2 = −1

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 0 0
z1 − c1 = cB y1 − c1 = −2

0 0 0 0
z2 − c2 = cB y2 − c2 = −1

Por lo tanto, S = ∅ y ası́, la base (a3 , a4 ) es óptima para todo

λ ∈ [3, ∞).

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

0 0 0 0
z1 − c1 = cB y1 − c1 = −2

0 0 0 0
z2 − c2 = cB y2 − c2 = −1

Por lo tanto, S = ∅ y ası́, la base (a3 , a4 ) es óptima para todo

λ ∈ [3, ∞).

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Perturbación del Vector de Recursos

0
Supongamos que el vector de recursos b es sustituido por b + λb ,
con λ ≥ 0.

Esto significa que el vector de términos independientes es

0
perturbado a lo largo del vector b .

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Perturbación del Vector de Recursos

0
Supongamos que el vector de recursos b es sustituido por b + λb ,
con λ ≥ 0.

Esto significa que el vector de términos independientes es

0
perturbado a lo largo del vector b .

Como el vector de recursos del problema primal es el objetivo del

problema dual, la perturbación de este vector puede analizarse
como una perturbación de la función objetivo del problema dual.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Perturbación del Vector de Recursos

0
Supongamos que el vector de recursos b es sustituido por b + λb ,
con λ ≥ 0.

Esto significa que el vector de términos independientes es

0
perturbado a lo largo del vector b .

Como el vector de recursos del problema primal es el objetivo del

problema dual, la perturbación de este vector puede analizarse
como una perturbación de la función objetivo del problema dual.

Ahora manejaremos la perturbación considerando directamente el

problema primal. Supongamos que tenemos una base óptima B,
del problema original, es decir, λ = 0. La tabla correspondiente
viene dada por:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Perturbación del Vector de Recursos

0
Supongamos que el vector de recursos b es sustituido por b + λb ,
con λ ≥ 0.

Esto significa que el vector de términos independientes es

0
perturbado a lo largo del vector b .

Como el vector de recursos del problema primal es el objetivo del

problema dual, la perturbación de este vector puede analizarse
como una perturbación de la función objetivo del problema dual.

Ahora manejaremos la perturbación considerando directamente el

problema primal. Supongamos que tenemos una base óptima B,
del problema original, es decir, λ = 0. La tabla correspondiente
viene dada por:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z + (cB B −1 N − cN )xN = cB B −1 b
xB + B −1 NxN = B −1 b

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z + (cB B −1 N − cN )xN = cB B −1 b
xB + B −1 NxN = B −1 b

donde cB B −1 N − cN ≤ 0.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z + (cB B −1 N − cN )xN = cB B −1 b
xB + B −1 NxN = B −1 b

donde cB B −1 N − cN ≤ 0.
0
Si se sustituye b por b + λb , el vector cB B −1 N − cN no se
afectará; es decir, no se afecta la factibilidad dual.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z + (cB B −1 N − cN )xN = cB B −1 b
xB + B −1 NxN = B −1 b

donde cB B −1 N − cN ≤ 0.
0
Si se sustituye b por b + λb , el vector cB B −1 N − cN no se
afectará; es decir, no se afecta la factibilidad dual.
0
El único cambio es sustituir B −1 b por B −1 (b + λb ) y, en
consecuencia, el valor objetivo se convierte en

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z + (cB B −1 N − cN )xN = cB B −1 b
xB + B −1 NxN = B −1 b

donde cB B −1 N − cN ≤ 0.
0
Si se sustituye b por b + λb , el vector cB B −1 N − cN no se
afectará; es decir, no se afecta la factibilidad dual.
0
El único cambio es sustituir B −1 b por B −1 (b + λb ) y, en
consecuencia, el valor objetivo se convierte en
0
cB B −1 (b + λb )

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z + (cB B −1 N − cN )xN = cB B −1 b
xB + B −1 NxN = B −1 b

donde cB B −1 N − cN ≤ 0.
0
Si se sustituye b por b + λb , el vector cB B −1 N − cN no se
afectará; es decir, no se afecta la factibilidad dual.
0
El único cambio es sustituir B −1 b por B −1 (b + λb ) y, en
consecuencia, el valor objetivo se convierte en
0
cB B −1 (b + λb )
0
Mientras que B −1 (b + λb ) sea no negativo, la actual base sigue
siendo óptima.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z + (cB B −1 N − cN )xN = cB B −1 b
xB + B −1 NxN = B −1 b

donde cB B −1 N − cN ≤ 0.
0
Si se sustituye b por b + λb , el vector cB B −1 N − cN no se
afectará; es decir, no se afecta la factibilidad dual.
0
El único cambio es sustituir B −1 b por B −1 (b + λb ) y, en
consecuencia, el valor objetivo se convierte en
0
cB B −1 (b + λb )
0
Mientras que B −1 (b + λb ) sea no negativo, la actual base sigue
siendo óptima.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

El valor de λ en el cual otra base se vuelva óptima, puede

determinarse como sigue:
0 0 0
Sea S = {i : b i < 0}, donde b = B −1 b .

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

El valor de λ en el cual otra base se vuelva óptima, puede

determinarse como sigue:
0 0 0
Sea S = {i : b i < 0}, donde b = B −1 b .

Si S = ∅, la actual base es óptima para todos los valores de λ ≥ 0.

Caso contrario, hallamos:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

El valor de λ en el cual otra base se vuelva óptima, puede

determinarse como sigue:
0 0 0
Sea S = {i : b i < 0}, donde b = B −1 b .

Si S = ∅, la actual base es óptima para todos los valores de λ ≥ 0.

Caso contrario, hallamos:
( )
bi br
λ̂ = mı́n 0 = 0
i∈S −b i −b r

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

El valor de λ en el cual otra base se vuelva óptima, puede

determinarse como sigue:
0 0 0
Sea S = {i : b i < 0}, donde b = B −1 b .

Si S = ∅, la actual base es óptima para todos los valores de λ ≥ 0.

Caso contrario, hallamos:
( )
bi br
λ̂ = mı́n 0 = 0
i∈S −b i −b r

Sea λ1 = λ̂. Para λ ∈ [0, λ1 ] la actual base es óptima, siendo

0
xB = B −1 (b + λb ) y el valor objetivo óptimo es:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

El valor de λ en el cual otra base se vuelva óptima, puede

determinarse como sigue:
0 0 0
Sea S = {i : b i < 0}, donde b = B −1 b .

Si S = ∅, la actual base es óptima para todos los valores de λ ≥ 0.

Caso contrario, hallamos:
( )
bi br
λ̂ = mı́n 0 = 0
i∈S −b i −b r

Sea λ1 = λ̂. Para λ ∈ [0, λ1 ] la actual base es óptima, siendo

0
xB = B −1 (b + λb ) y el valor objetivo óptimo es:
0
cB B −1 (b + λb )

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

El valor de λ en el cual otra base se vuelva óptima, puede

determinarse como sigue:
0 0 0
Sea S = {i : b i < 0}, donde b = B −1 b .

Si S = ∅, la actual base es óptima para todos los valores de λ ≥ 0.

Caso contrario, hallamos:
( )
bi br
λ̂ = mı́n 0 = 0
i∈S −b i −b r

Sea λ1 = λ̂. Para λ ∈ [0, λ1 ] la actual base es óptima, siendo

0
xB = B −1 (b + λb ) y el valor objetivo óptimo es:
0
cB B −1 (b + λb )

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

En λ1 los términos independientes son sustituidos por

0
B −1 (b + λ1 b ), xBr es retirado de la base y una variable apropiada
(según el criterio del método dual simplex) ingresa a la base.

Luego de actualizar la tabla, el proceso se repite para poder

encontrar el rango [λ1 , λ2 ] en el cual la nueva base es óptima,
donde λ2 = λ̂ se obtiene con la fórmula anterior.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

En λ1 los términos independientes son sustituidos por

0
B −1 (b + λ1 b ), xBr es retirado de la base y una variable apropiada
(según el criterio del método dual simplex) ingresa a la base.

Luego de actualizar la tabla, el proceso se repite para poder

encontrar el rango [λ1 , λ2 ] en el cual la nueva base es óptima,
donde λ2 = λ̂ se obtiene con la fórmula anterior.

El proceso concluye cuando bien S es vacı́o, en cuyo caso la actual

base es óptima para todo valor de λ mayor o igual al último valor
de λ, o cuando todas las entradas de la fila cuyos términos
independientes se volvieron cero son no negativos.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

En λ1 los términos independientes son sustituidos por

0
B −1 (b + λ1 b ), xBr es retirado de la base y una variable apropiada
(según el criterio del método dual simplex) ingresa a la base.

Luego de actualizar la tabla, el proceso se repite para poder

encontrar el rango [λ1 , λ2 ] en el cual la nueva base es óptima,
donde λ2 = λ̂ se obtiene con la fórmula anterior.

El proceso concluye cuando bien S es vacı́o, en cuyo caso la actual

base es óptima para todo valor de λ mayor o igual al último valor
de λ, o cuando todas las entradas de la fila cuyos términos
independientes se volvieron cero son no negativos.

En este último caso, no existen soluciones factibles para todo valor

de λ mayor que el valor actual.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

En λ1 los términos independientes son sustituidos por

0
B −1 (b + λ1 b ), xBr es retirado de la base y una variable apropiada
(según el criterio del método dual simplex) ingresa a la base.

Luego de actualizar la tabla, el proceso se repite para poder

encontrar el rango [λ1 , λ2 ] en el cual la nueva base es óptima,
donde λ2 = λ̂ se obtiene con la fórmula anterior.

El proceso concluye cuando bien S es vacı́o, en cuyo caso la actual

base es óptima para todo valor de λ mayor o igual al último valor
de λ, o cuando todas las entradas de la fila cuyos términos
independientes se volvieron cero son no negativos.

En este último caso, no existen soluciones factibles para todo valor

de λ mayor que el valor actual.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ejemplo 2
Considere el siguiente problema:
Minimizar −x1 − 3x2
Sujeto a x1 + x2 ≤ 6
−x1 + 2x2 ≤ 6
x1 ≥ 0, x2 ≥ 0

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ejemplo 2
Considere el siguiente problema:
Minimizar −x1 − 3x2
Sujeto a x1 + x2 ≤ 6
−x1 + 2x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
Se desea encontrar la solución óptima y las bases óptimas cuando
se perturba el vector de recursos a lo largo de la dirección
(−1, 1)T , es decir, si b = (6, 6)T se sustituye por
0
b + λb = (6, 6)T + λ(−1, 1)T .

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ejemplo 2
Considere el siguiente problema:
Minimizar −x1 − 3x2
Sujeto a x1 + x2 ≤ 6
−x1 + 2x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
Se desea encontrar la solución óptima y las bases óptimas cuando
se perturba el vector de recursos a lo largo de la dirección
(−1, 1)T , es decir, si b = (6, 6)T se sustituye por
0
b + λb = (6, 6)T + λ(−1, 1)T .

Solución.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ejemplo 2
Considere el siguiente problema:
Minimizar −x1 − 3x2
Sujeto a x1 + x2 ≤ 6
−x1 + 2x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
Se desea encontrar la solución óptima y las bases óptimas cuando
se perturba el vector de recursos a lo largo de la dirección
(−1, 1)T , es decir, si b = (6, 6)T se sustituye por
0
b + λb = (6, 6)T + λ(−1, 1)T .

Solución.
La solución óptima para λ = 0 se muestra a continuación, siendo
x3 y x4 variables de holgura.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ejemplo 2
Considere el siguiente problema:
Minimizar −x1 − 3x2
Sujeto a x1 + x2 ≤ 6
−x1 + 2x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
Se desea encontrar la solución óptima y las bases óptimas cuando
se perturba el vector de recursos a lo largo de la dirección
(−1, 1)T , es decir, si b = (6, 6)T se sustituye por
0
b + λb = (6, 6)T + λ(−1, 1)T .

Solución.
La solución óptima para λ = 0 se muestra a continuación, siendo
x3 y x4 variables de holgura.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 35 − 23 −14
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para encontrar el rango en el cual la base anterior es óptima,

0
primero calculamos b :

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 35 − 23 −14
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para encontrar el rango en el cual la base anterior es óptima,

0
primero calculamos b :
! ! !
2
0
−1 0
3 − 31 −1 −1
b =B b = 1 1 =
3 3 1 0

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 35 − 23 −14
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para encontrar el rango en el cual la base anterior es óptima,

0
primero calculamos b :
! ! !
2
0
−1 0
3 − 31 −1 −1
b =B b = 1 1 =
3 3 1 0

Por tanto, S = {1}. Ahora calculamos λ1 :

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 35 − 23 −14
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para encontrar el rango en el cual la base anterior es óptima,

0
primero calculamos b :
! ! !
2
0
−1 0
3 − 31 −1 −1
b =B b = 1 1 =
3 3 1 0

Por tanto, S = {1}. Ahora calculamos λ1 :

b1 2
λ1 = 0 = =2
−b 1 −(−1)

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 35 − 23 −14
2
x1 0 1 0 3 − 13 2
1 1
x2 0 0 1 3 3 4

Para encontrar el rango en el cual la base anterior es óptima,

0
primero calculamos b :
! ! !
2
0
−1 0
3 − 31 −1 −1
b =B b = 1 1 =
3 3 1 0

Por tanto, S = {1}. Ahora calculamos λ1 :

b1 2
λ1 = 0 = =2
−b 1 −(−1)

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ası́, la base (a1 , a2 ) permanece óptima en el intervalo [0, 2]. En

particular, para cualquier λ ∈ [0, 2] el valor objetivo y los términos
independientes vienen dados por:
0
z(λ) = cB b + λcB b

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ası́, la base (a1 , a2 ) permanece óptima en el intervalo [0, 2]. En

particular, para cualquier λ ∈ [0, 2] el valor objetivo y los términos
independientes vienen dados por:
0
z(λ) = cB b + λcB b
! !
2 −1
= (−1, −3) + λ(−1, −3) .
4 0

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ası́, la base (a1 , a2 ) permanece óptima en el intervalo [0, 2]. En

particular, para cualquier λ ∈ [0, 2] el valor objetivo y los términos
independientes vienen dados por:
0
z(λ) = cB b + λcB b
! !
2 −1
= (−1, −3) + λ(−1, −3) .
4 0
= −14 + λ.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ası́, la base (a1 , a2 ) permanece óptima en el intervalo [0, 2]. En

particular, para cualquier λ ∈ [0, 2] el valor objetivo y los términos
independientes vienen dados por:
0
z(λ) = cB b + λcB b
! !
2 −1
= (−1, −3) + λ(−1, −3) .
4 0
= −14 + λ.
! ! !
0 2 −1 2−λ
b + λb = +λ =
4 0 4

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ası́, la base (a1 , a2 ) permanece óptima en el intervalo [0, 2]. En

particular, para cualquier λ ∈ [0, 2] el valor objetivo y los términos
independientes vienen dados por:
0
z(λ) = cB b + λcB b
! !
2 −1
= (−1, −3) + λ(−1, −3) .
4 0
= −14 + λ.
! ! !
0 2 −1 2−λ
b + λb = +λ =
4 0 4

Reemplazando estos valores tenemos la siguiente tabla:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

Ası́, la base (a1 , a2 ) permanece óptima en el intervalo [0, 2]. En

particular, para cualquier λ ∈ [0, 2] el valor objetivo y los términos
independientes vienen dados por:
0
z(λ) = cB b + λcB b
! !
2 −1
= (−1, −3) + λ(−1, −3) .
4 0
= −14 + λ.
! ! !
0 2 −1 2−λ
b + λb = +λ =
4 0 4

Reemplazando estos valores tenemos la siguiente tabla:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 53 − 23 −14 + λ
2
x1 0 1 0 3 − 13 2−λ
1 1
x2 0 0 1 3 3 4

En λ = 2, xBr = x1 se vuelve cero. Se efectúa un pivoteo dual

simplex para que x1 deje la base y x4 ingrese obteniendo la
siguiente tabla:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 53 − 23 −14 + λ
2
x1 0 1 0 3 − 13 2−λ
1 1
x2 0 0 1 3 3 4

En λ = 2, xBr = x1 se vuelve cero. Se efectúa un pivoteo dual

simplex para que x1 deje la base y x4 ingrese obteniendo la
siguiente tabla:

z x1 x2 x3 x4 RHS
z 1 −2 0 −3 0 −12
x4 0 -3 0 −2 1 0
x2 0 1 1 1 0 4

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 53 − 23 −14 + λ
2
x1 0 1 0 3 − 13 2−λ
1 1
x2 0 0 1 3 3 4

En λ = 2, xBr = x1 se vuelve cero. Se efectúa un pivoteo dual

simplex para que x1 deje la base y x4 ingrese obteniendo la
siguiente tabla:

z x1 x2 x3 x4 RHS
z 1 −2 0 −3 0 −12
x4 0 -3 0 −2 1 0
x2 0 1 1 1 0 4

Para encontrar el rango [2, λ2 ] en el cual la tabla es óptima,

0
primero hallamos b y b :

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

z x1 x2 x3 x4 RHS
z 1 0 0 − 53 − 23 −14 + λ
2
x1 0 1 0 3 − 13 2−λ
1 1
x2 0 0 1 3 3 4

En λ = 2, xBr = x1 se vuelve cero. Se efectúa un pivoteo dual

simplex para que x1 deje la base y x4 ingrese obteniendo la
siguiente tabla:

z x1 x2 x3 x4 RHS
z 1 −2 0 −3 0 −12
x4 0 -3 0 −2 1 0
x2 0 1 1 1 0 4

Para encontrar el rango [2, λ2 ] en el cual la tabla es óptima,

0
primero hallamos b y b :

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

! ! !
−2 1 6 −6
b= B −1 b = =
1 0 6 6
! ! !
0 0 −2 1 −1 3
b = B −1 b = =
1 0 1 −1

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

! ! !
−2 1 6 −6
b= B −1 b = =
1 0 6 6
! ! !
0 0 −2 1 −1 3
b = B −1 b = =
1 0 1 −1

Ası́, S = {2} y λ2 viene dado por:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

! ! !
−2 1 6 −6
b= B −1 b = =
1 0 6 6
! ! !
0 0 −2 1 −1 3
b = B −1 b = =
1 0 1 −1

Ası́, S = {2} y λ2 viene dado por:

b2 6
λ2 = = =6
−b 2 −(−1)

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

! ! !
−2 1 6 −6
b= B −1 b = =
1 0 6 6
! ! !
0 0 −2 1 −1 3
b = B −1 b = =
1 0 1 −1

Ası́, S = {2} y λ2 viene dado por:

b2 6
λ2 = = =6
−b 2 −(−1)

Para λ ∈ [2, 6] el valor objetivo óptimo y los términos

independientes vienen dados por:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

! ! !
−2 1 6 −6
b= B −1 b = =
1 0 6 6
! ! !
0 0 −2 1 −1 3
b = B −1 b = =
1 0 1 −1

Ası́, S = {2} y λ2 viene dado por:

b2 6
λ2 = = =6
−b 2 −(−1)

Para λ ∈ [2, 6] el valor objetivo óptimo y los términos

independientes vienen dados por:
0
z(λ) = cB b + λcB b

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

! ! !
−2 1 6 −6
b= B −1 b = =
1 0 6 6
! ! !
0 0 −2 1 −1 3
b = B −1 b = =
1 0 1 −1

Ası́, S = {2} y λ2 viene dado por:

b2 6
λ2 = = =6
−b 2 −(−1)

Para λ ∈ [2, 6] el valor objetivo óptimo y los términos

independientes vienen dados por:
0
z(λ) = cB b + λcB b
! !
−6 3
= (0, −3) + λ(0, −3) = −18 + 3λ.
6 −1

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

! ! !
−2 1 6 −6
b= B −1 b = =
1 0 6 6
! ! !
0 0 −2 1 −1 3
b = B −1 b = =
1 0 1 −1

Ası́, S = {2} y λ2 viene dado por:

b2 6
λ2 = = =6
−b 2 −(−1)

Para λ ∈ [2, 6] el valor objetivo óptimo y los términos

independientes vienen dados por:
0
z(λ) = cB b + λcB b
! !
−6 3
= (0, −3) + λ(0, −3) = −18 + 3λ.
6 −1

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

! ! !
0 −6 3 −6 + 3λ
b + λb = +λ =
6 −1 6−λ

La tabla óptima para el intervalo [2, 6] se muestra a continuación:

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

! ! !
0 −6 3 −6 + 3λ
b + λb = +λ =
6 −1 6−λ

La tabla óptima para el intervalo [2, 6] se muestra a continuación:

z x1 x2 x3 x4 RHS
z 1 −2 0 −3 0 −18 + 3λ
x4 0 -3 0 −2 1 −6 + 3λ
x2 0 1 1 1 0 6−λ

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

! ! !
0 −6 3 −6 + 3λ
b + λb = +λ =
6 −1 6−λ

La tabla óptima para el intervalo [2, 6] se muestra a continuación:

z x1 x2 x3 x4 RHS
z 1 −2 0 −3 0 −18 + 3λ
x4 0 -3 0 −2 1 −6 + 3λ
x2 0 1 1 1 0 6−λ

En λ = 6, x2 se vuelve cero. Como todas las entradas en la fila x2

son no negativas, nos detenemos con la conclusión de que para
λ > 6, no existen soluciones factibles.

Uceda, R.A. Programación Lineal Paramétrica

 Introducción Vector de Costos
Análisis Paramétrico Vector de Recursos

! ! !
0 −6 3 −6 + 3λ
b + λb = +λ =
6 −1 6−λ

La tabla óptima para el intervalo [2, 6] se muestra a continuación:

z x1 x2 x3 x4 RHS
z 1 −2 0 −3 0 −18 + 3λ
x4 0 -3 0 −2 1 −6 + 3λ
x2 0 1 1 1 0 6−λ

En λ = 6, x2 se vuelve cero. Como todas las entradas en la fila x2

son no negativas, nos detenemos con la conclusión de que para
λ > 6, no existen soluciones factibles.

Uceda, R.A. Programación Lineal Paramétrica