Guerreros

4.1.1 Solución única Un problema de programación lineal tiene solución única cuando
únicamente las variables básicas tiene valor de cero en los valores llamados Cj -Zj .

4.1.2 Solución óptima múltiple Un problema de programación lineal tiene solución óptima
múltiple cuando aparte de las variables básicas, hay por lo menos una variable no básica que
tiene valor de cero en el Cj -Zj.

4.1.3. Solución no acotada En este tipo de problemas, tal como se mencionó en el capítulo
anterior; la solución se presenta en el infinito. Para el método simplex, esto se establece
cuando no se puede determinar que variable sale de la base. Recordemos que la regla de
salida de la base es la siguiente: Min XB aJ , teniendo en cuenta que sólo se avalúan los
cocientes que satisfagan la condición aJ > 0, (solo se evalúan valores positivos). Con base en
esto, cuando no están dadas las condiciones de optimalidad y todos estos valores son
negativos indica que el problema tiene solución no acotada o ilimitada. Esto se aprecia
fácilmente con la aplicación del ejercicio 3.1.3 del capítulo anterior, cuya formulación y modelo
se transcriben en el ejercicio 4.1.3.

Recordando la definición de no acotamiento, se dice qué se da cuando no se puede determinar

que variable sale de la base.

4.1.4. Problema sin solución Se interpreta que un problema solucionado por el método
simplex no tiene solución cuando se llega a las condiciones de optimalidad (todos los Cj -Zj son
mayores o iguales a cero) y por lo menos una variable artificial que da en la base con valor
diferente de cero.

Vale la pena recordar que un problema no tiene solución si no hay un solo punto que satisfaga
la totalidad de restricciones del problema.

4.2.5. Solución degenerada Un problema de programación lineal genera solución básica

factible degenerada cuando dentro del mismo hay restricciones de carácter redundante; es
decir, hay más de una restricción que genera la misma área factible, por lo tanto la solución no
varia si se elimina una de estas restricciones (si hay más de dos restricciones que generen la
misma área factible, se pueden eliminar todas, menos una y la solución no cambiará). Lo
anterior en el método simplex se refleja en el hecho que una variable básica en la solución
tomará valor de cero. Mediante la realización del 3.2.5 que se resolvió en el capitulo anterior
se visualizará es hecho. En el ejercicio 4.2.5 se trae la formulación y planteamiento de dicho
ejercicio.

Existe solución degenerada cuando en el tablero óptimo aparece una variable

básica con cero.

SOLUCION UNICA
Ejercicio 4.2.1. Los Horses, una empresa dedicada al criadero de caballos de paso, ha
establecido que a cada uno de ellos se le debe suministrar diariamente un mínimo de 200
miligramos de vitamina A, un mínimo de 160 miligramos de vitamina B y un mínimo de 150
miligramos de vitamina C. Los caballos son alimentados con matas de pasto y mineral, las
cuáles le cuestan a la compañía $300 por mata de pasto y $500 por libra de mineral. ¿Qué
cantidad de cada alimento se le debe suministrar a cada caballo diariamente si se sabe que una
mata de pasto contiene 4 miligramos de vitamina A, 2 miligramos de vitamina B y 5 miligramos
de vitamina C; mientras que una libra de mineral contiene 5 miligramos de vitamina A, ¿8
miligramos de vitamina B y 3 miligramos de vitamina C?

SEA: MINIMIZAR

X1 = Matas de pasto que se debe suministrar a cada caballo diariamente.

X2 = Libras de mineral que se debe suministrar a cada caballo diariamente.

Min. Z = 300 X1 + 500 X2

S.A.

4 X1 + 5 X2 ≥ 200

2 X1 + 8 X2 ≥ 160

5 X1 + 3 X2 ≥ 150

X1, X2 ≥ 0

MODELO ESTANDARIZADO

Min. Z = 300 X1 + 500 X2 + MA1 + MA2 + MA3

S.A.

4 X1 + 5 X2 – S1 + A1 = 200

2 X1 + 8 X2 – S2 + A2 = 160

5 X1 + 3 X2 – S3 + A3 = 150

X1, X2, S1, S2, S3 ≥ 0

CJ 300 500 0 M 0 M 0 M
CI VB X1 X2 S1 A1 S2 A2 S3 A3 LD θ
M A1 4 5 -1 1 0 0 0 0 200
M A2 2 8 0 0 -1 1 0 0 160
M A3 5 3 0 0 0 0 -1 1 150
ZJ 11M 16M -M M -M M -M M 510M
CJ-ZJ
 Casos Especiales del Método Simplex
Los casos especiales que se pueden generar al aplicar el método simplex son cuatro:

 Degeneración.
 Solución Múltiple.
 Solución Infinita o no acotada.
 Sin solución o solución no factible.

DEGENERACION
En este tipo de casos, al realizar la optimización por medio del método simplex,
tenemos un empate a la hora de elegir la fila pivote, esto cuando realizamos la prueba
del cociente mínimo. Dicho empate al elegir la variable que sale se rompe
arbitrariamente. El problema ocurre en la siguiente iteración donde los valores de una o
más variables básicas llegan a ser cero, en cuyo caso se dice que la solución es
degenerada. En este punto no existe la seguridad de que el valor de la función objetivo
mejorará, ya que la nueva solución óptima puede permanecer degenerada de ser así, es
posible que las iteraciones del simplex entren en un circuito que repetirá las misma(as)
sucesión de iteraciones sin alcanzar nunca la óptima.
La grafica que podría ejemplificar este caso puede ser:

La degeneración puede hacer que las iteraciones simplex ocurran de forma indefinida en
ciclos, y que el algoritmo nunca acabe. La condición también revela que el modelo tiene
por lo menos una restricción redundante.

Ej. Max: Z=5 X 1 +7 X 2

Sujeto a:
X 1 +3 X 2 ≤ 15
 2 X 1 +4 X 2 ≤ 20

X 1 , X 2 ≥0

Modelo Estandarizado:

Max: Z=5 X 1 +7 X 2 +0 h1 +0 h 2
X 1 + 4 X 2 +h1 =24

3 X 1 +3 X 2 +h 2=18

X 1 , X 2 , h1 , h2 ≥ 0

Cj 5 7 0 0
Ci VB X1 X2 h1 h2 L.D PCM
0 H1 1 4 1 0 24 6
0 X2 3 3 0 1 18 6
Zj 0 0 0 0 0
Cj-Zj 5 7 0 0

1 F 2∗( 1/3 )−−−F 2

2 F 2∗(−4 ) + F 1−−−F 1

Como podemos ver, la solución aun no es óptima, por lo que tenemos que iterar,
sabiendo que según el criterio de la columna pivote entraría X 2 ya que es el mayor valor
de la última fila, pero al momento de realizar la prueba del cociente mínimo, se presenta
un empate, el cual se puede romper de manera arbitraria como dice la teoría, y escoger
una de las dos filas.
Para la primera iteración tomaremos la fila 2 (sale h2) y probaremos si la tabla es
óptima.
Iteración 1
Cj 5 7 0 0
Ci VB X1 X2 h1 h2 L.D PCM
0 h1 -3 0 1 -4/3 0
7 X2 1 1 0 1/3 6
Zj 7 7 0 7/3 42
Cj-Zj -2 0 0 -7/3

Como podemos observar, luego de una iteración la tabla ya es óptima según su criterio,
y la solución es: Z=42, X2= 6 y H1=0.
Como una de las variables básicas es cero (h1) concluimos que es un caso de solución
degenerada.
SOLUCIONES ÓPTIMAS MULTIPLES.
Existen problemas que tienen más de una solución óptima. En este caso se dice que se
tienen soluciones óptimas múltiples debido a que la solución óptima se encuentra en un
segmento de recta que es acotado por una de las restricciones.
Cuando la función objetivo es paralela a una restricción que se satisface en el sentido de
la igualdad a través de la solución óptima, la función objetivo tomará el mismo valor
óptimo en más de un punto de la solución. Por esta razón reciben el nombre de
Soluciones Óptimas Múltiples.
Estos problemas deben afrontarse de tal manera que prime al análisis de sensibilidad, es
decir, una vez encontrada múltiple solución igual se debe proceder al comportamiento
del consumo de los recursos y restricciones
Cuando en los coeficientes de las variables no básicas en el renglón z de la tabla óptima
existe una variable con valor de cero, lo que indica que esa variable no básica puede
entrar a la solución básica sin alterar el valor de z, pero provoca un cambio en el valor
de las variables.
Se detecta cuando luego de alcanzar una solución básica factible óptima, al menos una
variable no básica tiene costo reducido igual a cero. La siguiente imagen representa esta
situación donde la solución óptima (infinitas) se alcanza en el tramo entre los vértices B
y C.

Ej. Max:   Z=27 X 1 +81 X 2

Sujeto a:
3 X 1 +9 X 2 ≤ 21
4 X 1 +3 X 2 ≤12

X 1 , X 2 ,≥ 0

Modelo estandarizado:
Max:   Z=27 X 1 +81 X 2 +0 h1 +0 h2
Sujeto a:
3 X 1 +9 X 2+h 1=21

4 X 1 +3 X 2 +h2=12

x 1 , x 2 , h 1, h 2 ≥0
Cj 27 81 0 0
Ci VB X1 X2 h1 h2 L.D
0 h1 3 9 1 0 21
0 h2 4 3 0 1 12
Zj 0 0 0 0 0
Cj-Zj 27 81 0 0

1 F 1∗( 1/9 )−−−F1

2 F 1∗(−3 ) + F 2−−−F 2

Cj 27 81 0 0
Ci VB X1 X2 h1 h2 L.D
81 X1 1/3 1 1/9 0 21/9
0 h2 3 0 -1/3 1 5
Zj 27 81 9 0 189
Cj-Zj 0 0 -9 0

NOTA: En este ejemplo se puede evidenciar que hay una restricción paralela a la
función objetivo, por lo cual sería una característica de soluciones múltiples, además
cuando una variable no básica (no es solución) en su casilla Ci –Zj sea 0, en este caso es
la variable x1.

SOLUCIONES ÓPTIMAS NO ACOTADAS

Existen problemas para las cuales una o más de las variables puede aumentarse
indefinidamente mejorando en forma indefinida la función objetivo, de esta manera se
puede afirmar que en esta situación la solución óptima no es acotada, por lo que da paso
a que esta solución es infinita.
Como resultado, el valor de la función objetivo puede crecer o decrecer con respecto a
lo que nos piden en el ejercicio a realizar.

Función Objetivo Valor de la función Objetivo

 Maximización Crece en forma indefinida

Minimización Decrece en forma indefinida

La falta de explicación en un modelo puede señalar solo una cosa: el modelo está mal
construido. Evidentemente resulta irracional hacer que un modelo produzca una
ganancia " infinita". Las irregularidades más probables en estos modelos son:
I. No se toman en cuenta una o más
Restricciones redundantes.
II. No se determina correctamente los parámetros
(Constantes) de algunas restricciones
NOTA: Si existiera un elemento menor o igual a cero, no se realiza dicho cociente.
 En caso de que todos los elementos de la columna pivote fueran de esta
condición, se cumplirá la condición de parade y el problema tendrá una
solución no acotada
La regla general para reconocer la falta de acotación es la siguiente: Si en cualquier
iteración todos los coeficientes de restricción de toda variable no básica son cero o
negativos, entonces el espacio de soluciones no está acotado en esa dirección. Si además
el coeficiente objetivo de esa variable es negativo en caso de maximización, o positivo
en caso de minimización, entonces también el valor objetivo es no acotado.
Si resolvemos gráficamente dicho modelo nos podemos percatar que éste es no acotado.
Notar que el dominio de soluciones factibles (área sombreada o achurada) es no
acotado dado que crece indefinidamente en la dirección de la variable X2
El siguiente ejemplo muestra cómo se puede reconocer la no acotación, tanto del
espacio de soluciones como del valor objetivo, en la tabla simplex.

EJ. Max: Z=4 X 1+ 6 X 2

Sujeto a:
2 X 1−2 X 2 ≤6

4 X 1 ≤16

X 1 , X 2 ≥0

Modelo Estandarizado:

Max: Z=4 X 1+ 6 X 2 +0 h1 +0 h2

Sujeto a:
2 X 1−2 X 2 +h 1=6

4 X 1 +h2=16

X 1 , X 2 , , h1 , h2 ≥ 0

Para identificar este caso especial, llevamos el modelo a su forma estándar,

agregando h1 y h2 como variables de holgura de la restricción 1 y 2, respectivamente.
Lo anterior define la siguiente tabla inicial del método:

Cj 4 6 0 0
Ci VB X1 X2 h1 h2 L.D
0 h1 2 -2 1 0 6
0 h2 4 0 0 1 16
Zj 0 0 0 0 0
Cj-Zj -4 -6 0 0

Notar que X2 es la variable no básica con el costo reducido más negativo y siguiendo
ese criterio debería ser aquella que ingresamos a la base. Sin embargo, no es factible
hacer el criterio de factibilidad o mínimo cociente debido a que los elementos en la
columna de X2 son negativos o cero. En esta instancia ya se puede afirmar que
el problema es no acotado.

CASO INFACTIBLE

Si las restricciones no se pueden satisfacer en forma simultánea, se dice que el modelo

no tiene solución factible. Esta situación nunca puede ocurrir si todas las restricciones
son del tipo Menor igual (suponiendo valores positivos en el segundo miembro) ya que
las variables de holgura producen siempre una solución factible. Sin embargo, cuando
empleamos los otros tipos de restricciones, recurrimos al uso de variables artificiales,
que por su mismo diseño no ofrecen una solución factible al modelo original. Aunque se
hacen provisiones (a través del uso de penalizaciones) para hacer que estas variables
artificiales sean cero en el nivel óptimo, esto sólo puede ocurrir si el modelo tiene un
espacio factible. Si no lo tiene, cuando menos una variable artificial será positiva en la
iteración óptima

Ejemplo:

La compañía de galletas «CAROLA» desea planificar la producción de galletas que

tendrá que entregar a su cliente en dos semanas, el contrato indica que la compañía
«CAROLA» se compromete a entregar por lo menos 300 cajas de galletas cualquiera
sea su tipo (presentación D, presentación N o una combinación de ambas
presentaciones), cada caja de galletas presentación D tiene un tiempo de elaboración de
2 horas, y un tiempo de horneado de 3 horas, mientras cada caja de presentación N tiene
un tiempo de elaboración de 3 horas y un tiempo de horneado de 1 hora. La compañía
cuenta estas dos semanas con 550 horas para elaboración y con 480 horas de horneado.
Teniendo en cuenta que el margen de utilidad de cada caja de galletas presentación D y
N es de $8500 y $8100 respectivamente, determine mediante un modelo de
programación lineal el plan de producción que maximice las utilidades.
X = Cantidad de cajas de galletas presentación D a producir en 2 semanas
Y = Cantidad de cajas de galletas presentación N a producir en 2 semanas

Max: Z = 8500 x 1 + 8100 x 2

2 x 1 + 3 x 2 ≤ 550

3 x 1 + x 2 ≤ 480

x 1 + x 2 ≥ 300

x 1, x 2 ≥ 0

Modelo Estandarizado:

Z = 8500 x 1 + 8100 x 2 + 0h1 + 0h2 + 0 s1 + M A1

2 x 1 + 3 x 2 + h1 = 550

3 x 1 + x 2 + h2 = 480

x 1 + x 2 - s1 + A1 = 300

x 1, x 2, h1, h2 , s1, A1 ≥ 0

CJ 8500 8100 0 0 0 -M
Ci UB x1 x2 h1 h2 s1 A1 L.D θ
0 h1 2 3 1 0 0 0 550 275
0 h2 3 1 0 1 0 0 480 160
-M A1 1 1 0 0 -1 1 300 300
 ZJ -M -M 0 0 M -M
C J −Z J 8500+M 8100+M 0 0 -M 0

Columna pivote

CJ 8500 8100 0 0 0 -M
Ci UB x1 x2 h1 h2 s1 A1 L.D θ
0 h1 0 7 1 −2 0 0 230 98,57
3 3
8500 x1 1 1 0 1 0 0 160 480
3 3
-M A1 0 2 0 −1 -1 1 140 210
3 3
ZJ 8500 8500 2 0 8500 1 M -M 1360000-
− M + M 140M
3 3 3 3
C J −Z J 0 15800 2 0 −8500 1 -M 0
+ M − M
3 3 3 3
Columna pivote

1 F 2∗ ( 13 )−−−F 2

2 F 2 (−2 ) + F 1−−−F 1
3 F 2(-1) + F 3−−−F 3

CJ 8500 8100 0 0 0 -M
Ci UB x1 x2 h1 h2 s1 A1 L.D
8100 x2 0 1 3 −2 0 0 690
7 7 7
8500 x1 1 0 −1 3 0 0 890
7 7 7
-M A1 0 0 −2 −1 -1 1 520
7 7 7
ZJ 8500 8100 15800 2 9300 1 M -M 1879142.8
+ M + M 520
7 7 7 7 - M
7
C J −Z J 0 0 −15800 2 −9300 1 -M 0
− M − M
7 7 7 7

3 ( 37 )−−−F
F 1∗ 1

−1
F ∗(
3 )
4 1 −−−F 2

−2
F ∗(
3 )
5 1 −−−F 3
La mejor manera de identificar el caso de solución no factible, es ver la tabla optima, y
darse cuenta si una de las variables básicas o de respuesta es una variable artificial,
como sucedió en el ejemplo anterior.