Control 4

ILN250 - Gestión de Investigación de Operaciones Semestre

CCC 001 y 002 - CSV 100 y 101 - CSSJ 200 y 201 2026-1

[40] 1. PARTE CONCEPTUAL

Analice y argumente cada uno de los juicios presentados, precisando si corresponden a
afirmaciones verdaderas o falsas.
Para todos los incisos de la parte conceptual, considere el problema de optimización lineal
en forma estándar (P) minn {c⊤ x : Ax = b, x ≥ 0}, donde c ∈ Rn , A ∈ Rm×n y b ∈ Rm .
x∈R
Denote por p⋆ el valor óptimo de (P).

(a) Si (P) es un problema factible, entonces (P) tiene al menos una solución óptima.

Solución:
FALSO.
El problema (P) puede ser no acotado. En cuyo caso no hay soluciones óptimas.

(b) Dos bases distintas de (P) pueden representar un mismo vértice del conjunto factible
de (P).

Solución:
VERDADERO.
En presencia de degenerancia, dos bases distintas pueden representar el mismo
punto factible. Esto ocurre porque una SBF degenerada tiene más de n − m
variables iguales a cero, por lo que puede haber más de una forma de escoger las
m variables básicas que generan el mismo vector x.

(c) Si (P) tiene exactamente dos vértices óptimos distintos x(1) y x(2) , entonces (P) tiene
infinitas soluciones óptimas.

Solución:
VERDADERO.
Aunque existan exactamente dos vértices óptimos, el segmento que los une también
es factible y óptimo. Por tanto, hay infinitas soluciones óptimas, aunque no nece-
sariamente infinitos vértices óptimos.
En otras palabras, si hay dos vértices distintos que son solución, para todo λ ∈ [0, 1]
el punto
zλ = λx(1) + (1 − λ)x(2)
es óptimo, pues

c⊤ zλ = c⊤ λx(1) + (1 − λ)x(2)

= |λc⊤{zx(1)} + (1 − λ)c⊤ x(2)

⋆
| {z }
=λp =(1−λ)p⋆
⋆
=p

(d) Dependiendo de los valores de A y b, el conjunto factible de (P) podrı́a tener infinitos
vértices.

Solución:
FALSO.
 ILN250 Gestión de Investigación de Operaciones 2026-1

El poliedro factible puede tener infinitos puntos, o incluso ser no acotado, pero
al estar descrito por un número finito de restricciones y variables, tiene a lo más
un número finito de vértices. Para construir un vértice en forma estándar, como

activar n − m de las
las m restricciones de igualdad siempre están activas, falta
n
n restricciones de no-negatividad. Por lo que hay n−m opciones. No todas las
combinaciones necesariamente son bases, y no todas las bases generan soluciones
factibles, pero en cualquier caso el número de SBF, y por tanto de vértices, es
finito.

(e) Si desde un punto factible de (P) existe una dirección en la que es posible moverse
indefinidamente sin salir del conjunto factible, entonces (P) es no acotado.

Solución:
FALSO.
La existencia de una dirección en la que se puede avanzar indefinidamente sin salir
del conjunto factible implica que el conjunto factible es no acotado. Sin embargo,
esto no significa necesariamente que el valor de la función objetivo tienda a −∞.
Para concluir que (P) es no acotado inferiormente, la dirección factible debe además
disminuir la función objetivo. Es decir, si r es una dirección factible de no aco-
tamiento, se necesitarı́a que
c⊤ r < 0.

[60] 2. PROBLEMA
Para este problema, considere el problema de programación lineal (P) escrito en forma
estándar:

min −3x1 − x2 − 2x3 + 2x4

x∈R6
s.t. x1 + x2 + x3 − x4 + x5 =4
x1 + 2x2 − x3 + x4 − x6 = 4
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0
(a) [10] Si se sabe que el problema en forma estándar (P) proviene de un problema de
maximización equivalente (Q), formulado en términos de tres variables originales y1 ,
y2 e y3 , donde
y1 ≥ 0, y2 ≤ 0, y3 ∈ R
Escriba el problema original (Q) e identifique qué representan las variables x1 , x2 , x3 ,
x4 , x5 y x6 con respecto a las variables y restricciones de (Q).

Solución: El problema (Q) es:

max3 3y1 − y2 + 2y3

y∈R
s.t. y1 − y2 + y3 ≤ 4
y1 − 2y2 − y3 ≥ 4
y1 ≥0
y2 ≤0

Las variables x representan:

• x1 = y1

Página 2 de 4
ILN250 Gestión de Investigación de Operaciones 2026-1

• x2 = −y2 .
• x3 = y3+ .
• x4 = y3− .
• x5 : variable de holgura de la primera restricción.
• x6 : variable de exceso de la segunda restricción.

(b) [25] Considere la base B = {1, 6}. Obtenga el valor de todas las variables x del vértice
asociado a dicha base. Luego, realice una iteración del algoritmo Simplex para el
problema (P). A partir de dicha iteración, concluya que el problema es no acotado.

Solución: Considerando la base B = {1, 6} se tiene N = {2, 3, 4, 5}:

     
1 0 −1 1 0 −1 4
AB = ; AB = ; b̄ = AB b =
1 −1 1 −1 0
   
1 1 −1 1 −1 1 1 −1 1
AN = ; ĀN = AB AN =
2 −1 1 0 −1 2 −2 1

Por lo tanto como xB = b̄ y xN = 0, se tiene:

x1 4
   
x2  0
x  0
   
x =  3 =  
x4  0
x  0
5
x6 0

Se calculan los costos reducidos:

c̄⊤ ⊤ ⊤
N = cN − cB ĀN
 


1 1 −1 1
= −1 −2 2 0 − −3 0
−1 2 −2 1



= −1 −2 2 0 − −3 −3 3 −3


= 2 1 −1 3

Como c̄N ̸≥ 0, no se está en el óptimo. La variable que entra a la base es x4 , pues

es la única variable con costo reducido negativo.
Se observa que si d4 = −A−1 B A4 → dB4 = −āi4
   
−1 1
āi4 = < 0 → dB4 = >0
−2 2

Por lo tanto, se obtuvo una dirección de no acotamiento o dirección extrema. Es

decir, el problema es no acotado y su valor óptimo es p⋆ = −∞.

Página 3 de 4
ILN250 Gestión de Investigación de Operaciones 2026-1

(c) [25] Suponga que en (P) se modifica la función objetivo por

αx1 − x2 − 2x3 + 2x4

donde α ∈ R. Determine todos los valores de α para los que la base B = {2, 3} es
óptima.
Si aparecen números fraccionarios, manéjelos como fracción, no como dec-
imal.

Solución: Considerando la base B = {2, 3} se tiene N = {1, 4, 5, 6}:

     
1 1 −1 1/3 1/3 8/3
AB = ; AB = ; b̄ =
2 −1 2/3 −1/3 4/3
   
1 −1 1 0 2/3 0 1/3 −1/3
AN = ; ĀN =
1 1 0 −1 1/3 −1 2/3 1/3

c̄⊤ ⊤ ⊤
N = cN − cB ĀN
 


2/3 0 1/3 −1/3
= α 2 0 0 − −1 −2
1/3 −1 2/3 1/3



= α 2 0 0 − −4/3 2 −5/3 −1/3


= α + 4/3 0 5/3 1/3

Para que la base sea óptima, se debe tener c̄N ≥ 0. Los costos reducidos asociados
a las variables x4 , x5 y x6 ya son no-negativos. Para que el costo reducido asociado
a la variable x1 sea no-negativo se debe tener α + 4/3 ≥ 0. Es decir, el rango de
valores para el costo de la variable x1 debe ser

α ∈ [−4/3, ∞) .

Página 4 de 4