Investigación de Operaciones 37

5. Casos especiales

5.1 Soluciones no acotadas

Hay programas lineales cuya solución óptima no está conformada por números finitos.
Gráficamente, esta situación se puede representar de la siguiente manera:

x2

a
ent
a um
Z

Recinto de
posibles
soluciones
x1

Como se ve en la figura, el recinto de posibles soluciones se prolonga hacia la derecha (zo-

na más sombreada); por lo tanto la solución será óptima lo más a la derecha posible.
Cuando se presenta esta situación, al aplicar el método Simplex, una vez definida una co-
lumna a j que entra a la base, todos los Ykj ≤ 0, y no se puede elegir la variable de salida.

5.2 Soluciones óptimas alternativas

¿Cómo se identifica esta situación durante la aplicación del método Simplex?
Ya se ha visto que:

Z ' = Z − (z j − c j )
x Br
Yrj

Si a j es una columna no básica tal que su zj - cj = 0; entonces Z’= Z. Por lo tanto, se podría
obtener una nueva solución óptima (con el mismo valor de la F.O.), introduciendo a la base
la variable cuyo zj - cj = 0, y sacando de la base la variable que corresponda.

5.3 Adición de variables artificiales: métodos de penalización y de dos fases

Hasta el momento se ha aplicado el método Simplex a un P.L. donde ninguna restricción
tiene signo de desigualdad del tipo “mayor o igual que” (≥). Si se tuviese al menos una res-
tricción de este tipo, no será recomendable cambiar de signo toda la inecuación, con el
propósito de conseguir el signo “menor o igual que” (≤), y así pasar a la forma canónica,
pues el término independiente resultaría negativo, ¡y la solución inicial no sería factible!
Cuando se presente esta situación, se debe añadir una variable artificial, además de una va-
riable superflua, para conseguir de esta manera la base inicial, conformada por vectores
Investigación de Operaciones 38

unitarios. Por ejemplo, si al problema de la página 23 se le añade una restricción con signo
de desigualdad (≥), se tendría el siguiente P.L:
Max. Z = 400x1 + 500x2
2x1 + 3x2 ≤ 100
3x1 + 2x2 ≤ 120
x1 + 2x2 ≤ 60
x2 ≥ 15
x1, x2 ≥ 0

Al convertir las desigualdades en igualdades, añadiendo una variable artificial en la última

restricción, se tendría:
Max Z = 400 x1 + 500 x2 – Mx7 aB cB 400 500 0 0 0 0 -M xB
2x1 + 3x2 + x3 = 100
a3 0 2 3 1 0 0 0 0 100
3x1 + 2x2 + x4 = 120
a4 0 3 2 0 1 0 0 0 120
x1 + 2x2 + x5 = 60
a5 0 1 2 0 0 1 0 0 60
x2 - x6 + x7 = 15
a7 -M 0 1 0 0 0 -1 1 15
-400 -M-500 0 0 0 M 0

Como se puede apreciar, el propósito de la variable artificial es conseguir la base inicial, de

orden 4 × 4, para poder tener una solución inicial básica. Pero esta variable artificial no
tiene ninguna interpretación real; así que, en la tabla óptima no debe figurar como variable
básica. Esto se evita asignándole un beneficio marginal muy grande y negativo, que se re-
presenta con –M. A partir de este momento, se puede aplicar el método Simplex para con-
seguir la solución óptima. A este método se le denomina Método de penalización, pues pe-
naliza las variables artificiales en la función objetivo. Además, los elementos de la última
fila de la tabla inicial se deben recalcular mediante las operaciones: c B B -1A - c , como se
muestra en el siguiente apartado. Otro método empleado para resolver este tipo de proble-
mas donde se incluyen variables artificiales es el método de dos fases.

6. Problemas de minimización
Los programas lineales de minimización no se pueden resolver aplicando el método Sim-
plex, pues este tipo de problemas tiene por lo menos una restricción con signo de desigual-
dad “mayor o igual que” (≥). Por lo tanto será necesario el empleo de variables artificiales,
y será necesario también penalizar dichas variables en la función objetivo. Como ahora se
trata de minimizar, para que las variables artificiales salgan de la base inicial se les penali-
za con coeficientes M positivos. Una vez introducidas estas variantes, ya se puede aplicar
el método Simplex, cambiando previamente la F.O., que pasa de (Min. Z) a (Max. –Z),
como se ve en el siguiente ejemplo:
Min. Z = 2x1 + x2
3 x1 + x2 ≥ 3
4 x1 + 3 x2 ≥ 6

Max -Z = -2 x1 - x2 – Mx5 – Mx6 aB cB -2 -1 0 0 -M -M xB

3x1 + x2 - x3 + x5 = 3
a3 -M 3 1 -1 0 1 0 3
4x1 + 3x2 - x4 + x6 = 6
a4 -M 4 3 0 -1 0 1 6
2-7M 1-4M 0 0 0 0
Investigación de Operaciones 39

Para resolver este tipo de problemas empleando softwares de Programación Lineal, no ha-
ce falta preocuparse de la introducción de variables artificiales, pues el mismo software se
encarga de ello.

7. Dualidad
A cada P.L. con variables x1, x2, …, xn le corresponde otro con variables y1, y2, …, yn, lla-
mado su dual.
Dado el P.L. primario: su dual es:
Max. Z = c X Min. G = b T Y
AX ≤ b AT Y ≥ c T
X≥0 Y ≥0

7.1 Interpretación del problema dual

Una empresa se propone realizar una alimentación económica para ganado, la cual debe
contener obligatoriamente cuatro tipos de componentes: A, B, C y D. La industria alimen-
ticia produce dos alimentos M y N, que contienen dichos componentes. La siguiente tabla
resume las condiciones para la alimentación:
Consumo mínimo (kg)
M (1 kg) N (1 kg)
por animal cada día
A 0.1 0 0.4
B 0 0.1 0.6
C 0.1 0.2 2
D 0.2 0.1 1.7
Costo $10 $4

¿Qué cantidades de los alimentos M y N se deben utilizar diariamente, por cada animal,
para realizar la alimentación de la forma menos costosa?
Considerando las siguientes variables de decisión:
x1 = kg. del alimento M
x2 = kg. del alimento N
se plantea el siguiente P.L:
Min. Z = 10x1 + 4x2
0.1 x1 ≥ 0.4
0.1 x2 ≥ 0.6
0.1 x1 + 0.2 x2 ≥ 2
0.2 x1 + 0.1 x2 ≥ 1.7

cuya solución es:

x1 = 4 kg. del alimento M
x2 = 9 kg. del alimento N Z = $76.
Investigación de Operaciones 40

¿Qué problema se plantea un competidor de los alimentos M y N que vende los alimen-
tos A, B, C y D?
Este competidor debe determinar a qué precio debe vender cada kg. de dichos componen-
tes, de tal manera que su ganancia sea máxima, por día y por cabeza de ganado.
Variables de decisión
y1 = $ / kg. del alimento A.
y2 = $ / kg. del alimento B.
y3 = $ / kg. del alimento C.
y4 = $ / kg. del alimento D.

El P.L. que se plantea el competidor de alimentos es el siguiente:

Max. G = 0.4 y1 + 0.6y2 + 2y3 + 1.7y4
y1 + 0.1 y3 + 0.2 y4 ≤ 10
0.1 y2 + 0.2 y3 + 0.1 y4 ≤ 4
cuya solución es:
y1 = $20 / kg. del alimento A.
y2 = $0 / kg. del alimento B.
y3 = $0 / kg. del alimento C.
y4 = $40 / kg. del alimento D. G = $76

Conviene ahora que el lector haga un análisis comparativo de los dos problemas plantea-
dos, que corresponden al problema primario y su dual.

7.2 Formas de dualidad

La siguiente tabla muestra los posibles problemas primarios y sus correspondientes duales:
Problema primario Problema dual

Max. Z = cX Min. G = bT Y
AX ≤ b AT Y ≥ c T
X ≥0 Y ≥0
Min. Z = cX Max. G = bT Y
AX ≥ b AT Y ≤ c T
X ≥0 Y ≥0

Max. Z = cX Min. G = bT Y
AX = b AT Y ≥ c T
X ≥0 Y no restringida
Max. Z = cX Min. G = bT Y
AX ≥ b AT Y ≥ c T
X ≥0 Y ≤0
Investigación de Operaciones 41

Ejemplo:
Max. Z = 6x1 + 4x2 Min. G = 12y1 + 24y2 + 4y3
3x1 + 2x2 ≤ 12 3y1 + 4y2 + y3 ≥ 6
4x1 – x2 = 24 ⇒ 2y1 – y2 + y3 ≥ 4
x1 + x2 ≥ 4 y1 ≥ 0
x1, x2 ≥ 0 y2 no restringido
y3 ≤ 0

7.3 Solución del dual

Dado el problema dual en la forma canónica:
Min. G = b T ⋅ Y
AT Y ≥ c T
Y ≥0
La ecuación matricial que representa el conjunto de restricciones se puede expresar de la
siguiente forma:
B T Y = c BT
Por lo tanto:
Y T ⋅ B = cB

Y T = c B ⋅ B −1

Se ve que la solución del problema dual corresponde con los zj – cj de las variables de hol-
gura del problema primario, por eso, a estos valores se les denomina precios sombra o pre-
cios duales.

7.4 Función objetivo del dual

Teorema: Si X y Y son soluciones factibles de un P.L. primario y su correspondiente dual,
respectivamente, entonces:
Z = c X ≤ bT Y = G
Demostración:

AX ≤ b AT Y ≥ c T
Y T AX ≤ Y T b X T AT Y ≥ X T c T
Y T AX ≤ b T Y Y T AX ≥ c X

c X ≤ bT Y

Z ≤ G
Cuando Z alcanza su máximo valor, G alcanza su mínimo valor, y éstos coinciden.
Investigación de Operaciones 42

7.6 El método Dual-Simplex

Este método fue deducido a partir de las formulaciones duales que se van obteniendo de
cada uno de los problemas primarios que resultan al aplicar el método Simplex.
Se puede aplicar para resolver problemas de minimización en donde todas las restricciones
tienen el signo (≥).
Algoritmo Dual-Simplex
1. Comience sólo si todos los zj – cj ≥ 0, es decir, si hay factibilidad dual.
2. Si todos los elementos de X B ≥ 0, entonces la tabla es óptima. En caso contrario,
seleccionar como variable de salida a aquella que tome el valor más negativo.
3. Seleccione como variable de entrada a aquella cuyo cociente (zj – cj)/Ykj sea el mayor,
con Ykj ≤ 0. Si todos los Ykj ≥ 0 , entonces el problema no tiene solución.
4. Aplique las operaciones elementales con el pivote, para convertir la columna a j en un
vector unitario.
5. Regrese al paso 2.

Cuando se aplica el método Simplex se cuida que haya factibilidad primaria (xBk ≥ 0); con
el método Dual-Simplex se cuida que haya factibilidad dual (zj – cj ≥ 0).
Ejemplo:
Min. Z = 2x1 + x2 Max. –Z = –2x1 – x2
3 x1 + x2 ≥ 3 ⇒ –3 x1 – x2 ≤ –3
4 x1 + 3 x2 ≥ 6 –4 x1 – 3x2 ≤ –6
x1 + 2 x2 ≥ 3 – x1 – 2x2 ≤ –3

Agregando las variables de holgura se obtiene la tabla inicial, y aplicando el método Dual-
Simplex se obtiene la tabla óptima:
Tabla inicial
aB cB -2 -1 0 0 0 xB
a3 0 -3 -1 1 0 0 -3
a4 0 -4 -3 0 1 0 -6
a5 0 -1 -2 0 0 1 -3
2 1 0 0 0

Tabla óptima
aB cB -2 -1 0 0 0 xB aB cB -2 -1 0 0 0 xB
a3 0 -5/3 0 1 -1/3 0 -1 a1 -2 1 0 -3/5 1/5 0 3/5
a4 -1 4/3 1 0 -1/3 0 2 ⇒ a2 -1 0 1 4/5 -3/5 0 6/5
a5 0 5/3 0 0 -2/3 1 1 a5 0 0 0 1 -1 1 0
2/3 0 0 1/3 0 -2 0 0 2/5 1/5 0 -2.4

Solución óptima: x1 = 3/5; x2 = 6/5; Z = 2.4

Investigación de Operaciones 43

8. Análisis de sensibilidad

8.1 Análisis de sensibilidad de los coeficientes de la función objetivo

Supóngase que se ha aplicado el método Simplex a un P.L. y se ha encontrado la solución
óptima. Si luego se produce un cambio en uno de los coeficientes de la función objetivo, es
decir, en uno de los elementos del vector c , ¿será posible determinar si la solución óptima
va a cambiar? La respuesta a esta pregunta no es inmediata. Quizá haya que hacer algún
cálculo. Lo que sí podemos afirmar es que el cambio de un coeficiente ci origina cambios
en la tabla óptima.
Rango de sensibilidad de los coeficientes de las variables básicas.
Si cambia el coeficiente de una variable básica, cambiarán los zj – cj de las variables no bá-
sicas. Recuérdese que:

zj – cj = c B B −1 a j − c j

Para que la solución actual no cambie, los zj – cj de las variables no básicas deben seguir
siendo mayores o iguales que cero:

zj – cj = c B B −1 a j − c j ≥ 0

Considérese el ejemplo desarrollado en la solución gráfica, apartado 2, de los autos y tre-

nes de madera. A continuación se presenta la formulación, la tabla inicial y la tabla óptima
de dicho problema:
Z = 3x1 + 2x2 aB cB 3 2 0 0 0 xB
2x1 + x2 + x3 = 10000
a3 0 2 1 1 0 0 10000
x1 + x2 + x4 = 8000
a4 0 1 1 0 1 0 8000
x1 + x5 = 4000
a5 0 1 0 0 0 1 4000
-3 -2 0 0 0

Tabla óptima
aB cB c1 2 0 0 0 xB
a2 2 0 1 -1 2 0 6000
a5 0 0 0 -1 1 1 2000
a1 c1 1 0 1 -1 0 2000
0 0 1 1 0

Para determinar el rango de sensibilidad de c1 = 3, se plantean las siguientes inecuaciones,

que expresan la no negatividad de los zj – cj no básicos:

 − 1 2
   
(2, 0, c1)  − 1 – 0 ≥ 0 (2, 0, c1)  1  – 0 ≥ 0
1  −1
   
Resolviendo este sistema de dos inecuaciones resulta:
2 ≤ c1 ≤ 4
que indica que la solución del P.L. no cambiará mientras el coeficiente c1 = 3 varíe dentro
de este rango.
Investigación de Operaciones 44

Para determinar el rango de sensibilidad de c2 = 2, se sigue el mismo procedimiento:

 − 1 2
   
(c2, 0, 3)  − 1 – 0 ≥ 0 (c2, 0, 3)  1  – 0 ≥ 0
1  −1
   
Resolviendo este nuevo sistema de dos inecuaciones resulta:
1.5 ≤ c2 ≤ 3
que indica que la solución del P.L. no cambiará mientras el coeficiente c2 = 2 varíe dentro
de este rango.
Rango de sensibilidad de los coeficientes de las variables no básicas.
Si cambia el coeficiente de una variable no básica, cambiará sólo el zj – cj de dicha variable
no básica:
zj – cj = c B B −1 a j − c j

Considérese el mismo ejemplo de los autos y trenes de madera con una ligera modifica-
ción: el beneficio marginal de los autos de madera es $1. A continuación se presenta la
formulación, la tabla inicial y la tabla óptima de este nuevo problema:
Z = x1 + 2x2 aB cB 1 2 0 0 0 xB
2x1 + x2 + x3 = 10000
a3 0 2 1 1 0 0 10000
x1 + x2 + x4 = 8000
a4 0 1 1 0 1 0 8000
x1 + x5 = 4000
a5 0 1 0 0 0 1 4000
-1 -2 0 0 0

Tabla óptima
aB cB c1 2 0 0 0 xB
a2 2 1 1 0 1 0 8000
a5 0 1 0 0 0 1 4000
a3 0 1 0 1 -1 0 2000
1 0 0 2 0

Para determinar el rango de sensibilidad de c1 = 1, se plantea la siguiente inecuación:

1
 
(2, 0, 0) 1 – c1 ≥ 0
1
 
Resolviendo esta desigualdad resulta:
c1 ≤ 2
que indica que la solución del P.L. no cambiará mientras el coeficiente c1 = 1 varíe dentro
de este rango.
Se deduce que si el beneficio marginal de los autos aumenta en $1 ó más, la solución del
problema cambiará. Justamente, el zj – cj de dicha variable, 1, expresa lo mínimo que debe
aumentar su beneficio marginal para que pase a ser una variable básica.
Investigación de Operaciones 45

Cambios discretos en los coeficientes de la función objetivo

Si cambia un coeficiente de la función objetivo a un valor que se encuentra fuera del rango
de sensibilidad, cambiará la solución óptima. ¿Cómo encontrarla? Será necesario calcular
los zj – cj que cambien, y, a partir de esta tabla, aplicar el método Simplex hasta restablecer
la optimalidad. Lógicamente, se comenzará escogiendo la variable de entrada, pues por lo
menos uno de los zj – cj se ha hecho negativo.

8.2 Análisis de sensibilidad de los recursos

Supóngase que se ha aplicado el método Simplex a un P.L. y se ha encontrado la solución
óptima. Si luego se produce un cambio en uno de los recursos, es decir, en uno de los ele-
mentos del vector b , se espera que la solución cambie. Como ya se ha discutido cuando se
hizo el análisis de sensibilidad gráficamente (apartado1), la solución cambiará si el recurso
que cambia es escaso, o si el recurso es abundante pero el cambio es tal que éste deja de ser
abundante. Si el recurso que cambia es abundante y el cambio es tal que éste sigue siendo
abundante, la solución óptima no cambiará. Sólo cambiará la variable de holgura que re-
presenta dicha abundancia.
Cambios discretos en los recursos
Si cambia algún recurso, la nueva solución puede hallarse a partir de la ecuación matricial:
X ' B = B −1 b '
Pero, este producto puede como resultado una solución no factible, en cuyo caso será nece-
sario aplicar el método Dual-Simplex para restablecer la factibilidad.
Supóngase que, en el taller de autos y trenes de madera, se cuenta con 10 horas-hombre
adicionales en el departamento de acabados. La nueva solución sería:

 − 1 2 0  10010   5990   x 2 
      
X ' B =  − 1 1 1   8000  =  1990  =  x5 
 1 − 1 0   4000   2010   x 
      1
Es decir: x1 = 2010 autos; x2 = 5990 trenes; x5 = 1990 (holgura en la demanda de autos)
Si se contase con 2100 horas-hombre adicionales en acabados, la nueva solución sería:

 − 1 2 0  12100   3900 
    
X ' B =  − 1 1 1   8000  =  − 100 
 1 − 1 0   4000   4100 
    
Esta solución no es factible. Fíjese que no es posible producir 4100 autos, si se quiere
cumplir la restricción de demanda. Para determinar la nueva solución se introduce, en pri-
mer lugar, el vector hallado y se aplica el método Dual-Simplex:
aB cB 3 2 0 0 0 xB aB cB 3 2 0 0 0 xB
a2 2 0 1 -1 2 0 3900 a2 2 0 1 0 1 -1 4000
a5 0 0 0 -1 1 1 -100 a3 0 0 0 1 -1 -1 100
a1 3 1 0 1 -1 0 4100 a1 3 1 0 0 0 1 4000
0 0 1 1 0 0 0 0 2 1

La solución óptima resulta: x1 = x2 = 4000.

Investigación de Operaciones 46

Supóngase que la demanda de autos cambia a 2500 unidades. La nueva solución sería:

 − 1 2 0  10000   6000   x 2 
      
X ' B =  − 1 1 1   8000  =  500  =  x5 
 1 − 1 0   2500   2000   x 
      1
Como se ve, sólo ha cambiado la holgura en la restricción de la demanda de autos.
¿Y si la demanda de autos disminuye a 1500 unidades? La nueva solución sería:

 − 1 2 0  10000   6000   x 2 
      
X ' B =  − 1 1 1   8000  =  − 500  =  x5 
 1 − 1 0   1500   2000   x 
      1
Como esta solución no es factible, se debe aplicar el método Dual-Simplex para restablecer
la factibilidad.
Rango de sensibilidad de los recursos
Tiene mucha importancia la determinación del rango en que puede variar cualquiera de los
recursos, de tal manera que la solución siga siendo factible. Si un recurso varía dentro de
este rango, la nueva solución tiene la misma base B, y por lo tanto los precios duales no
cambian. De esta manera es posible hallar cuánto cambia la F.O. si un recurso varía dentro
de su rango de sensibilidad.
Para determinar el rango de sensibilidad del primer recurso (b1 = hs-h en acabados) se
plantean las siguientes desigualdades:

 − 1 2 0   b1   16000 − b1   0 
      
X ' B =  − 1 1 1   8000  =  − b1 + 12000  ≥  0 
 1 − 1 0   4000   b − 8000   0 
    1   
de donde resulta:
8000 ≤ b1 ≤ 12000
Para determinar el rango de sensibilidad de b2 se plantea:

 − 1 2 0  10000   − 10000 + 2b2   0 

      
X ' B =  − 1 1 1   b2  =  − 6000 + b2  ≥  0 
 1 − 1 0   4000   10000 + b   0 
    2   

Y para determinar el rango de sensibilidad de b3:

 − 1 2 0  10000   − 10000 + 2b2   0 

      
X ' B =  − 1 1 1   8000  =  − 6000 + b2  ≥  0 
 1 − 1 0   b   10000 + b   0 
  3   2   

Se deja al alumno, a manera de ejercicio, la determinación de los rangos de sensibilidad de

los dos últimos recursos.
Investigación de Operaciones 47

8.3 Cambio en la columna a j de una variable no básica

Si cambia al menos un elemento de la columna a j , entonces cambiará su correspondiente

zj – cj, ya que éste es igual a: c B B −1 a j − c j . Si el zj – cj sigue siendo positivo, la solución
actual no cambia; pero si el zj – cj resulta negativo, la tabla deja de ser óptima. Para resta-
blecer la optimalidad se debe aplicar el método Simplex, ingresando a la base justamente la
variable cuyo zj – cj se ha hecho negativo.
Ejemplo:
Considérese el ejemplo de los autos y trenes de madera. A continuación se presenta la for-
mulación, la tabla inicial y la tabla óptima:
Z = x1 + 2x2 aB cB 1 2 0 0 0 xB
2x1 + x2 + x3 = 10000
a3 0 2 1 1 0 0 10000
x1 + x2 + x4 = 8000
a4 0 1 1 0 1 0 8000
x1 + x5 = 4000
a5 0 1 0 0 0 1 4000
-1 -2 0 0 0
Tabla óptima
aB cB 1 2 0 0 0 xB
a2 2 1 1 0 1 0 8000
a5 0 1 0 0 0 1 4000
a3 0 1 0 1 -1 0 2000
1 0 0 2 0

Supóngase que un auto requiere ahora de 24 minutos en el departamento de carpintería, en

vez de una hora. La primera columna de la tabla óptima sería:

 0 1 0   2   0.4 
−1
    
a1 ' ' = B a1 ' =  0 0 1   0.4  =  1 
 1 − 1 0   1   1.6 
    
Por lo tanto:
 0.4 
 
zj – cj = (2, 0, 0)  1  – 1 = -0.2
 1.6 
 
La tabla óptima cambiaría, y se tendría lo siguiente:
aB cB 1 2 0 0 0 xB
a2 2 0.4 1 0 1 0 8000
a5 0 1 0 0 0 1 4000
a3 0 1.6 0 1 -1 0 2000
-0.2 0 0 2 0

Aplicando el método Simplex se determina la nueva tabla óptima:

aB cB 1 2 0 0 0 xB
a2 2 0 1 -1/4 5/4 0 7500
a5 0 0 0 -5/8 5/8 1 2750
a1 1 1 0 5/8 -5/8 0 1250
0 0 1/8 15/8 0
La solución óptima sería entonces: x1 = 7500 autos; x2 = 1250 autos.
¿Qué se puede hacer si ocurre un cambio en una columna básica?
Investigación de Operaciones 48

Si cambia una columna básica, cambia la matriz básica B, y cambia por lo tanto la matriz
inversa B-1; por lo tanto cambiará la tabla óptima. Por lo tanto, ante un cambio en una co-
lumna básica no se puede resolver el problema a partir de la tabla óptima, y no queda más
remedio que resolver el problema nuevamente.

8.4 Adición de nuevas variables

Dado un P.L. cuya solución ya ha sido determinada, si se añade una nueva variable, es de-
cir, si se añade una nueva actividad, se puede determinar si la base actual sigue siendo óp-
tima. En primer lugar se tendrían que conocer los coeficientes tecnológicos de la columna
que corresponde a la nueva variable xj. Así se podría determinar la columna que le corres-
pondería en la tabla óptima: B-1 a j , y su zj – cj = c B B −1 a j − c j

• Si zj – cj ≥ 0 ⇒ La tabla óptima no cambia, es decir, no conviene desarrollar la

nueva actividad.
• Si zj – cj ≤ 0 ⇒ La tabla final ha dejado de ser óptima. Para restablecer la opti-
malidad se debe aplicar el método Simplex.
Ejemplo:
Supóngase que, además de los autos y trenes, se decide producir unos camiones de madera
que compiten en el mercado con los autos (los clientes eligen entre uno u otro).Un camión
consume $11 y $14 por materia prima y mano de obra, y requiere una hora-hombre de aca-
bados y 1.5 horas-hombre de carpintería. ¿A qué precio tendría que vender estos camiones,
como mínimo, para que valga la pena producirlos?
El nuevo problema sería:
Z= 3x1 + 2x2 + c6x6 aB cB 3 2 c6 0 0 0 xB
2x1 + x2 + x6 + x3 = 10000
a3 0 2 1 1 1 0 0 10000
x1 + x2 + 1.5x6 + x4 = 8000
a4 0 1 1 1.5 0 1 0 8000
x1 + x6 + x5 = 4000
a5 0 1 0 1 0 0 1 4000
-1 -2 -c6 0 0 0

La nueva columna de la tabla óptima se obtiene mediante el producto:

 −1 2 0 1   2 
−1
    
B a 6 =  − 1 1 1  1.5  =  1.5 
 1 − 1 0   1   − 0.5 
    
Insertando esta columna en la tabla óptima, y calculando su z6 – c6:
aB cB 3 2 c6 0 0 0 xB
a2 2 0 1 2 -1 2 0 6000
a5 0 0 0 1.5 -1 1 1 2000
a1 3 1 0 -0.5 1 -1 0 2000
0 0 2.5-c6 1 1 0
Para que valga la pena producir camiones, su z6 – c6 debe ser negativo, por lo tanto:
c6 ≥ 2.5

8.5 Adición de nuevas restricciones

Dado un P.L. cuya solución ya ha sido determinada, si se añaden nuevas restricciones, en
primer lugar se debe verificar si la solución obtenida las satisface. Si las satisface, la solu-
Investigación de Operaciones 49

ción encontrada es óptima; en caso contrario se deben añadir dichas restricciones a la tabla
óptima, incluyendo sus correspondientes variables de holgura. Como consecuencia de esta
inserción, las columnas básicas de la tabla óptima dejan de ser vectores unitarios. Para que
estos vectores vuelvan a ser unitarios será necesario aplicar operaciones matriciales ele-
mental. Finalmente será necesario aplicar el método Dual-Simplex para restablecer la fac-
tibilidad.
Ejemplo:
Supóngase que, por cuestiones de marketing, conviene producir al menos 2500 autos de
madera, es decir:
x1 ≥ 2500 ⇒ -x1 ≤ -2500
Como la solución óptima no satisface esta nueva restricción, es necesario añadirla a la ta-
bla óptima:
aB cB 3 2 0 0 0 0 xB
a2 2 0 1 -1 2 0 0 6000
a5 0 0 0 -1 1 1 0 2000
a1 3 1 0 1 -1 0 0 2000
a6 0 -1 0 0 0 0 1 -2500
0 0 1 1 0

Restableciendo los vectores unitarios:

aB cB 3 2 0 0 0 0 xB
a2 2 0 1 -1 2 0 0 6000
a5 0 0 0 -1 1 1 0 2000
a1 3 1 0 1 -1 0 0 2000
a6 0 0 0 1 -1 0 1 -500
0 0 1 1 0

Aplicando el método Dual-Simplex se obtiene: x1 = 2500 autos; x2 = 5000 trenes.

8.6 Problemas propuestos

Problema 8.1
Un agricultor cultiva trigo y maíz en una chacra de 45 acres. Por restricciones del mercado,
puede vender, como máximo, 140 sacos de trigo, y, como máximo, 120 sacos de maíz. Ca-
da acre cultivado produce 5 sacos de trigo o 4 sacos de maíz. El trigo se vende a 30 dólares
el saco y el maíz a 50 dólares el saco. Se necesitan 6 horas de mano de obra para cosechar
un acre de trigo, y 10 horas de mano de obra para cosechar un acre de maíz. Se pueden ad-
quirir hasta 350 horas de mano de obra a 10 dólares la hora. Para maximizar sus utilidades,
el agricultor se plantea el siguiente P.L, cuya tabla óptima se muestra a continuación:

TABLA OPTIMA:
Max Z = 150X + 200Y - 10H 150 200 -10 0 0 0 0 0
X + Y ≤ 45 a2 200 0 1 0 -1.5 0.25 0.25 0 0 20
6 X + 10 Y - H ≤ 0 a1 150 1 0 0 2.5 -0.25 -0.25 0 0 25
H ≤ 350 a7 0 0 0 0 -12.5 1.25 1.25 1 0 15
5 X ≤ 140 a3 -10 0 0 1 0 0 1 0 0 350
4 Y ≤ 120 a8 0 0 0 0 5 -1 -1 0 1 40
0 0 0 75 12.5 2.5 0 0

Conteste las siguientes preguntas, cada una referida al planteamiento inicial.

Investigación de Operaciones 50

1. Diga qué solución le conviene al agricultor. Interprete los 5 valores de la última colum-
na de la tabla óptima.
2. Determine el rango de sensibilidad de los recursos e interprételos.
3. Determine la tabla óptima (completa) para el caso en que el saco de maíz se venda a 23
dólares el saco
Para esta situación, ¿en cuánto podría variar las horas de mano de obra necesarias para
producir un saco de maíz sin que cambie la solución?
4. ¿Existe alguna relación entre los precios duales de los recursos b2 y b3? Explique.
5. ¿Hasta cuánto estaría dispuesto a pagar por una hora adicional de mano de obra?
6. El agricultor está considerando la posibilidad de cultivar cebada, cuya demanda no tiene
límites. Un acre produce 4 sacos de cebada y requiere de 3 horas de mano de obra. ¿A
cuánto se tendría que vender el saco de cebada para que valga la pena sembrarla?
7. Suponga que el agricultor decide sembrar por lo menos el doble de trigo que de maíz.
¿Qué solución propondría?

Problema 8.2
Una empresa manufactura dos productos A y B. Cada producto A aporta un beneficio de
$300 y cada producto B aporta $400. Los recursos que requiere la manufactura de ambos
productos se muestran en la siguiente tabla:
Días en la máquina 1 Días en la máquina 2 Toneladas de acero
A 0.8 0.6 2
B 1.2 0.7 3

Actualmente la empresa cuenta con 32 máquinas tipo 1 y 88 máquinas tipo 2; pero cada
día puede alquilar hasta 98 máquinas tipo 1 a $50 por máquina y tiene disponible 270 tone-
ladas de acero. El gerente de marketing dice que se deben producir, como mínimo, 88 uni-
dades de A y 20 unidades de B. Para determinar cuánto producir de A y B, y decidir si al-
quila maquinaria tipo 1, se plantea el siguiente P.L:
MAX 300 X1 + 400 X2 - 50 X3
SUJETO A:
0.8 X1 + 1.2 X2 - X3 ≤ 32
X3 ≤ 98
0.6 X1 + 0.7 X2 ≤ 88
2 X1 + 3 X2 ≤ 270
X1 ≥ 88
X2 ≥ 20

TABLA OPTIMA:
X1 X2 X3 X4 X5 X6 X7 X8 X9
300 400 -50 0 0 0 0 0 0
X1 300 1 0 0 0 0 0 0.5 0 1.5 105
X5 0 0 0 0 1 1 0 -0.4 0 0 22
X6 0 0 0 0 0 0 1 -0.2 0 0.2 30
X8 0 0 0 0 0 0 0 0.5 1 1.5 17
X3 -50 0 0 1 -1 0 0 0.4 0 0 76
X2 400 0 1 0 0 0 0 0 0 -1 20
0 0 0 50 0 0 130 0 50 35700

Conteste las siguientes preguntas, cada una referida al planteamiento inicial.

1. Diga qué solución le conviene a la empresa.
2. Determine el rango de sensibilidad de los precios y de los 4 primeros recursos.
3. Si una unidad de B aportase un beneficio de $310, ¿qué propondría usted a la empresa?
Investigación de Operaciones 51

4. ¿Hasta cuánto estaría dispuesto a pagar por el alquiler de 7 máquinas tipo1 por un día?
5. ¿Hasta cuánto estaría dispuesto a pagar por 50 toneladas adicionales de acero?
6. Si se dispusiera de 50 toneladas de acero adicionales, ¿qué propondría a la empresa? ¿Y
si se dispusiera de 60 toneladas adicionales?
7. Dé la solución gráfica al problema para el caso en que no se disponga de alquiler de
máquinas tipo 1. Trace el recinto de posibles soluciones.

Problema 8.3
Una panadería elabora dos tipos de pan: A y B. Cada pan A se puede vender en 87 ptas. y
cada pan B en 80 ptas. Un pan A requiere medio paquete de levadura y 3.5 onzas de hari-
na, y un pan B requiere medio paquete de levadura y 2.5 onzas de harina. Mensualmente,
la panadería puede adquirir hasta un máximo de 120 paquetes de levadura y 700 onzas de
harina, a 60 ptas./paquete y 2 ptas./onza, respectivamente. El planteamiento del P.L. y la
inversa de la base óptima se muestran a continuación:
MAX 50 X1 + 45 X2
S.A: 0.5 X1 + 0.5 X2 <= 120 7 -1
3.5 X1 + 2.5 X2 <= 700 -5 1

Determine la tabla óptima y conteste cada una de las siguientes preguntas en forma inde-
pendiente, referidas al problema original
1. Supóngase que el dueño de la panadería decide aumentar el precio del pan A en 10 pe-
setas, a pesar de que sus costos no han variado. Con este nuevo precio, ¿valdrá la pena
variar la producción?
2. Si el dueño quisiera elaborar la misma cantidad de panes A y B, ¿qué producción le
convendría?
3. ¿Qué producción recomendaría si le reducen la cuota mensual de levadura a 105 paque-
tes?
4. Supóngase que, un determinado mes, le ofrecen a la panadería 50 onzas adicionales de
harina a un precio de 4 ptas./onza. ¿Aceptaría la oferta?
5. Supóngase que la demanda de pan es limitada. Si el dueño decide producir hasta un
máximo de 195 panes, ¿qué producción le convendría?

Problema 8.4
Picard es una empresa que ensambla autos deportivos, mon-tando carrocerías originales,
partes especiales del armazón y motores, que adquiere de una gran empresa automovilísti-
ca. Ensambla dos modelos de auto: uno normal y otro de lujo. Actualmente el proceso pro-
duc-tivo está dividido en cinco departamentos: estampado, pintu-ras y acabados, montaje
de moto-res y partes mecánicas, montaje del modelo normal y montaje del modelo de lujo.
Los tres primeros sirven a ambos modelos, y los dos últimos a uno solo. El tiempo que re-
quiere cada producto en cada departamento y la capacidad máxima de cada uno de éstos,
vienen dados en la siguiente tabla. Al final de ésta se muestran los costos de cada modelo.
Si los precios de venta son de $2200 y $ 2590 para los modelos normal y de lujo, respecti-
vamente, y no existen problemas con la demanda, el P.L. que determina el plan de produc-
ción óptimo es:
MAX 1110 X1 + 1220 X2
S.A: 2) 8 X1 + 8 X2 ≤ 320
3) 7 X1 + 8.4 X2 ≤ 294
4) 46.5 X1 + 93 X2 ≤ 2883
5) 100 X1 ≤ 3600
6) 150 X2 ≤ 4500
Investigación de Operaciones 52

y la tabla óptima es la siguiente:

X1 X2 X3 X4 X5 X6 X7
aB cB 1110 1220 0 0 0 0 0 XB
X2 1220 0 1 -0.625 0.714 0 0 0 10
X6 0 0 0 -75 71.429 0 1 0 600
X5 0 0 0 23.25 -33.214 1 0 0 558
X1 1110 1 0 0.75 -0.714 0 0 0 30
X7 0 0 0 93.75 -107.143 0 0 1 3000
0 0 70 78.571 0 0 0 45500
Conteste las siguientes preguntas, cada una referida al planteamiento inicial
1. Trace el recinto de posibles soluciones, indique cuál es la solución óptima y determine,
a partir del gráfico, el rango de sensibilidad de los beneficios de cada modelo.
2. Determine el rango de sensibilidad de los beneficios de cada modelo a partir de la tabla
óptima.
3. Determine el rango de sensibilidad de los recursos a partir de la tabla óptima.
4. Identifique dónde aparecen los reduced cost en la tabla óptima y demuéstrelo para el ca-
so general.
5. Identifique dónde aparecen los dual prices en la tabla óptima y demuéstrelo para el caso
general.
6. Si los costos se mantuvieran invariables, ¿cuánto tendría que bajar el precio del modelo
normal para que no se justifique su producción?
7. ¿En qué departamentos no se emplea la capacidad máxima? ¿Cuánto deja de utilizarse
en cada uno de éstos?
8. Supóngase que, por desperfectos en el departamento de pintura y acabados, sólo se dis-
pone de 295 horas al mes. ¿Cuál sería el beneficio óptimo?
9. Suponga que, por sugerencia del gerente de Marketing, se decide producir al menos 15
autos del modelo de lujo. ¿Cuánto le convendría producir de cada modelo? ¿A qué pre-
cio tendría que venderse el modelo de lujo para obtener el mismo beneficio inicial?
[Link] que la demanda del modelo normal es de 18 unidades. ¿Hasta cuánto pagaría
por una campaña publicitaria que asegure una demanda de hasta 25 unidades?

Problema 8.5
Gepbab Production Company utiliza mano de obra y materia prima para producir tres pro-
ductos. En la siguiente tabla se muestran los requerimientos de los recursos y los precios de
venta para los tres productos:
Producto 1 Producto 2 Producto 3
Mano de obra (horas) 3 4 6
Materia prima (unidades) 2 2 5
Precio de venta ($) 80 100 130

Actualmente, Gepbab dispone de 90 unidades de materia prima y de 70 horas de mano de

obra (costo fijo que no se incluye en la F.O.); pero puede comprar hasta 120 horas adicio-
nales a una empresa de servicios, a $10 la hora. Para maximizar sus ganancias, Gepbab se
plantea el siguiente P.L. y obtiene la siguiente tabla óptima:
x1 x2 x3 L x4 x5 x6
MaxZ = 80x1 + 100x2 + 130x3 - 10L 80 100 130 -10 0 0 0 XB
s.a: 3x1 + 4x2 + 6x3 – L ≤ 70 a2 100 1 1 2.5 0 0 0.5 0 45
2x1 + 2x2 + 5x3 ≤ 90 aL -10 1 0 4 1 -1 2 0 110
L ≤ 120 a6 0 -1 0 -4 0 1 -2 1 10
10 0 80 0 10 30 0
Los rangos de sensibilidad para los precios y los recursos son:
Investigación de Operaciones 53

0 ≤ c1 ≤ 90 ; c2 ≥ 90 ; 0 ≤ c3 ≤ 210 ; -20 ≤ cL ≤ 0
60 ≤ b1 ≤ 180 ; 35 ≤ b2 ≤ 95 ; b3 ≥ 110

Conteste las siguientes preguntas referidas al problema original:

1. Explique lo que representan cada una de las siete variables que emplea el P.L.
2. ¿Qué valores toman las variables de holgura? ¿Qué representan dichos valores?
3. ¿Cuál es la matriz básica óptima (B) ?
4. ¿Qué representa el rango de sensibilidad de b3?
5. ¿Qué representa el rango de sensibilidad de c3?
6. ¿Qué representa el z3 – c3 = 80?
7. Si le ofrecen materia prima adicional $10/unidad, ¿aceptaría? ¿Hasta cuántas unidades?
8. Si la empresa de servicios subiera el precio de la mano de obra a $ 15 la hora, ¿cuál se-
ría el plan de producción que le convendría?
9. Si la empresa de servicios sólo ofreciera 105 horas de mano de obra, ¿cuál sería el plan
de producción que le convendría?
[Link] que el departamento de comercialización de Gepbab informa que difícilmente
se venderán más de 40 unidades de los productos 1 y 3, en total. ¿Cuánto dejarían de
ganar si se ajustan a este requerimiento?

Problema 8.6
Wivco fabrica dos productos: P1 y P2. La siguiente tabla muestra los datos pertinentes.
Cada semana se pueden comprar hasta 400 unidades de materia prima, a un costo de $1.50
la unidad. La compañía tiene 4 trabajadores, cada uno de los cuales trabaja 40 horas a la
semana (sus salarios se consideran como un costo fijo). Se puede pedir a los obreros que
trabajen tiempo extra, y se les paga $6 cada hora extra. Cada semana se dispone de 320
horas de máquina. Sin publicidad, la demanda semanal de P1 es de 50 unidades, y de P2 de
60 unidades. Se puede usar la publicidad para estimular la demanda de cada producto.

Cada dólar que se gasta en la publicidad P1 P2

para P1 aumenta la demanda en 10 unida- Precio $15 $8
des. Cada dólar que se gasta en la publi- Trabajo 0.75 hora 0.50 hora
cidad para P2 aumenta la demanda en 15 Tiempo de máquina 1.50 horas 0.80 hora
unidades. Se pueden gastar hasta $100 en Materia prima 2 unidades 1 unidad
publicidad.
Para maximizar sus utilidades, Wivco se Max Z = 15 P1 + 8 P2 – 6 HE – 1.5 MP – GP1
plantea el siguiente P.L, cuya solución – GP2
s.a: P1 – 10 GP1 ≤ 50
óptima se muestra a continuación.
P2 – 15 GP2 ≤ 60
Conteste las siguientes preguntas, cada 0.75 P1 + 0.5 P2 – HE ≤ 160
2 P1 + P2 – MP ≤ 0
una referida al planteamiento inicial.
MP ≤ 400
GP1 + GP2 ≤ 100
1.5 P1 + 0.8 P2 ≤ 320

1. Si el tiempo extra costara sólo $4 la hora, ¿utilizaría Wivco tiempo extra?

2. Si cada unidad de P1 se vendiera a $15.50, ¿cuál sería la ganancia óptima?
3. ¿Hasta cuánto debería pagar Wivco por una unidad de materia prima?
4. ¿Hasta cuánto debería pagar Wivco por otra hora de tiempo máquina?
Investigación de Operaciones 54

5. Si se exigiera a cada trabajador a trabajar 45 horas semanales (como parte de la semana

normal de trabajo), ¿cuál sería ahora la ganancia de la compañía?
6. Wivco considera producir un nuevo producto P3. Cada 3unidades se venden a $17. Una
unidad de P3 requiere 2 horas de trabajo, una unidad de materia prima y 2 horas de
tiempo de máquina. ¿Le conviene a Wivco producir P3?

Optimal solution found

MAX Z = 2427.6667

DECISION VARIABLES
PLAIN VARIABLES

Variable Name Activity Reduced Cost

------------------------------------------------------
P1 160.0000 0.0000
P2 80.0000 0.0000
HE 0.0000 -2.1333
MP 400.0000 0.0000
GP1 11.0000 0.0000
GP2 1.3333 0.0000
------------------------------------------------------

CONSTRAINTS
PLAIN CONSTRAINTS

Constraint Name Slack Shadow Price

------------------------------------------------------
c1 0.0000 -0.1000
c2 0.0000 -0.0667
c3 0.0000 -3.8667
c4 0.0000 -6.0000
c5 0.0000 -4.5000
c6 87.6667 0.0000
c7 16.0000 0.0000
------------------------------------------------------

RANGES OBJECTIVE
PLAIN VARIABLES

Variable Name Coefficient Lower Bound Upper Bound

--------------------------------------------------------------------
P1 15.0000 14.4667 15.9667
P2 8.0000 7.5167 8.2667
HE -6.0000 -1E+020 -3.8667
MP -1.5000 -6.0000 1E+020
GP1 -1.0000 -6.3333 0.0000
GP2 -1.0000 -8.2500 0.0000
--------------------------------------------------------------------

RANGES RHS
PLAIN CONSTRAINTS

Constraint Name RHS Value Lower Bound Upper Bound

--------------------------------------------------------------------
c1 50.0000 -826.6667 160.0000
c2 60.0000 -1255.0000 80.0000
c3 160.0000 157.5000 187.5000
c4 0.0000 -55.0000 6.6667
c5 400.0000 345.0000 406.6667
c6 100.0000 12.3333 1E+020
c7 320.0000 304.0000 1E+020
--------------------------------------------------------------------