a.

Algoritmos de Solución

Algebraicos

Los siguientes dos algoritmos se basan en el principio 1; sus soluciones requieren cierto
esfuerzo al no tener criterio de finalización (optimalidad) y orden de explorar los puntos
extremos (factibilidad)

Los algoritmos de este tipo buscan explorar y evaluar todos los puntos extremos factibles
y no factibles. Selecciona el punto extremo en donde se obtiene el mayor valor de la
función objetivo cuando se esté maximizando y el menor valor cuando se esté
minimizando.

Punto Extremo: Serecorre sólo los puntos extremos de la región factible, y evalúa en cual
se obtiene el mayor valor de la función objetivo cuando se esta maximizando y cual se
obtiene el menor valor cuando se esta minimizando.

Ejemplo de Algoritmos Ingenuos

Forma canónica del sistema

Maximizar z= 50x+20y

s.a

x+ 2y ≤ 200
2x+y ≤ 160
x ≤ 60

x, y ≥ 0

Forma estándar

Maximizar z= 50x+20y

x+2y+s1 = 200
2x + y +s2 = 160
x +s3= 60

x, y, s1,s2,s3 ≥ 0

n=5 variables de decisión y holgura

m= 3 numero de restricciones sin incluir las de no negatividad.

Máximo número de puntos extremos = 10

El número de variables básica es igual al número de restricciones.

Lo que se pretende, es resolver un sistema de tres restricciones con tres incógnitas en
cada iteración o cada vez que se determina un punto extremo. En la siguiente tabla se
muestra todas las combinaciones posibles.

A
B

Variables Punto extremo Valor de las Variables Valor de Valor de

Básicas variables no Básicas las función
variables objetivo
s1,s2,s3 A 200,160,60 x, y 0,0 0
s1,s2, x B 140,40,60 s3,y 0,0 3000
s1,s2, y No Factible s3,x 0,0
s1,x, y C 60,60,40 s2,s3 0,0 3800
x, s2,s3 No Factible s1, y 0,0
x, s2, y No Factible s1, s3 00
s2,s3,y E 60,60,100 s1,x 0,0 2000
x, y , s3 D 40,80.20 s1,s2 00 3600
x, s1,s3 No Factible s2,y 0,0
s1, y, s3 No Factible s2,x 0,0

Valor de la solución óptima es de 3800 y se localiza en el punto extremo C.

max Z = x1+2x2+2x3

2x1+x2 ≤8

x3≤10
 Algoritmo de Puntos extremos

Variables Vértice
Básicas Solución Básica Factible Correspondiente
______________________________________________________________
x1 , x3 x1 = 4, x3 = 10, x2 = s1 = s2 = 0 D
s1 , s2 s1 = 8, s2 = 10, x1 = x2 = x3 = 0 F
s1 , x3 s1 = 8, x3 = 10, x1 = x2 = s2 = 0 E
x2 ; x3 x2 = 8, x3 = 10, x1 = s1 = s2 = 0 C
x2 , s2 x2 = 8, s2 = 10, x1 = x3 = s1 = 0 B
x1 ; s2 x1 = 4, s2 = 10, x2 = x3 = s1 = 0 A

Tomado del libro de Winston.

b. El método Simplex

Fue creado en 1947 y se le atribuye a George Bernard Dantzig (Estados Unidos). El

método simplex analiza los puntos extremos de una región factible de forma inteligente.
Para esto se basa en dos criterios o condiciones:

1. Optimalidad: permite saber que variable no básica entrar y en que iteración se

alcanza el optimo. La variable de entrada en un problema de maximización
(minimización) es aquella, no básica, que tenga el coeficiente más negativo
(positivo) en el renglón z o renglón cero. Los empates se rompen arbitrariamente.
Se llega al óptimo en la iteración cuando los coeficientes de las variables no
básicas en el renglón z son positivos (negativos), esto se debe a que ya no se
pueden mejorar los valores de las variables para que aumente la función objetivo.

2. Condición de factibilidad: En los problemas de maximización y minimización la

variable de salida es la básica asociada con la mínima razón no negativa entre el
lado derecho y el coeficiente positivo de la variable no básica, que va entrante,
seleccionada bajo la condición de optimalidad (con denominador estrictamente
positivo). Los empates se rompen arbitrariamente.
 El Algoritmo Simplex

Con la forma estándar determine una solución inicial

básica factible

Si
Se alcanzó el óptimo? Fin

No

Seleccionar variable entrante entre las variables no

básicas usando Condición de Optimidad

Seleccionar variable saliente entre las variables básicas

usando Condición de Factibilidad

Determine los valores de las nuevas variables básicas

haciendo la variable entrante básica y la saliente no
básica
Fuente: Diapositivas profesor Sergio Hernández
Miminizar z= x1 + 2x2 - 4x3

s.t.x1+ x2 + 2x3 < 9

x1+ x2 - x3 < 2
- x1+ x2 + x3 < 4
x1 , x2 , x3 > 0

z x1 x2 x3 x4 x5 x6 LD

z 1 -1 -1 4 0 0 0 0

0 1 1 2 1 0 0 9

x4 0 1 1 -1 0 1 0 2

0 -1 1 1 0 0 1 4

x5

x6
 z x1 x2 x3 x4 x5 x6 LD

z 1 3 -5 0 0 0 -4 -16

0 3 -1 0 1 0 -2 1

x1 0 0 2 0 0 1 1 6

0 -1 1 1 0 0 1 4

x5

z x1 x2 x3 x4 x5 x6 LD
x3
1 0 -4 0 -1 0 -2 -17
z
0 1 -1/3 0 1/3 0 -2/3 1/3

0 0 2 0 0 1 1 6
x1
0 0 2/3 1 1/3 0 1/3 13/3

x5
Ejemplo (tomado del Bazaaraa)

x3
Tipos de Soluciones

No degenerada: En esta solución las variables básicas que son iguales al número de
restricciones (m) tienen valores distintos de cero. Existen menos de m hiperplanos
activos, con lo cual alguna de las restricciones es no activa y su variable de holgura
asociada tiene algún valor distinto de cero.

Degenerada: Alguna de las variables básicas tiene valor igual a cero. Existen al menos
(m) hiperplanos activos; al ser las restricciones activas, sus variables de holgura
asociadas tienen valor de cero. Cuando en una iteración en simplex dos variables pueden
salir de la base (criterio de factibilidad) es porque existe una solución degenerada. Una de
las causas de las soluciones degeneradas es la sobre especificación en el punto óptimo.

Posibles resultados

 No Acotado
En el método simplex se sabe que el problema es no acotado cuando todo los
coeficientes en la columna pivote son negativos o cero, la columna pivote está
relacionada con la variable que entra. En otras palabras todos los coeficientes de la
columna pivote deben ser estrictamente positivos.

 No factible

Cuando todas las restricciones son ≤ 0, siempre el problema tendrá solución ya que una
base factible para estos problemas es que todas las variables de decisión valgan cero.

Cuando las restricciones ≥ o = se utiliza el método de las dos fases o el método de la

gran M (penalización) para encontrar una base factible. En el método de las dos fases un
problema es no factible si al finalizar la primera fase las variables artificiales no
desaparecen. En el método de la gran M el problema será factible cuando al llegar a la
tabla final (última iteración) existen variables artificiales positivas.

La no factibilidad se da porque existen restricciones mutuamente excluyentes. Por

ejemplo, cuando se tiene que producir una demanda de 1000 unidades pero su capacidad
máxima instalada es de 800 unidades.

Soluciones Múltiples

Un problema de programación lineal tiene soluciones múltiples si una de las restricciones

es paralela a la función objetivo. Esto es fácil de observar con el método gráfico si solo se
tienen dos variables de decisión. Cuando los problemas tienen más de dos variables de
decisión, una alternativa es resolverlos utilizando el algoritmo simplex.

Las soluciones múltiples se identifican en el tableau final del algoritmo simplex en el

renglón cero si existen variables no básicas con coeficientes iguales a 0. Esto significa
que si estas variables entran a la base, la función objetivo no cambia o permanece igual;
por lo tanto existen óptimos alternos.

Procedimiento para encontrar óptimos alternos.

1. Confirmar si la tabla final, realmente lo es. En la tabla final cuando se está

maximizando todas las variables en el renglón cero deben ser positivas y cuando
se está minimizando deben ser negativas.
2. Si es la tabla final, observar si existen variables no básicas con coeficiente de 0
en el renglón cero.
3. Si existen variables no básicas con coeficiente 0, existen óptimos alternos.

 Alternativa (1) (otra iteración simplex)

4. Introducir a la base, la variable no básica que tiene coeficiente 0 en el renglón

cero y realizar una iteración más del método simplex.
  Alternativa (2) (realizar solo cálculos necesarios).

5. Introducir a la base la variable no básica que tiene coeficiente 0. Aplicar

condición de factibilidad que permite saber que variable sale y con qué valor entra
la variable no básica. Como el valor de la función objetivo no cambia, utilizar esta
información para obtener el valor de la otra variable de decisión que debe ser
básica.

Después de obtener la otra solución óptima, se aplica una combinación lineal para
obtener todas las otras soluciones. Recuerde que las dos soluciones óptimas deben estar
en dos puntos extremos adyacentes.

Principio 2

Dos soluciones óptimas se encuentran en dos puntos extremos adyacentes.

Combinación lineal: αX1+ (1-α) X2. Es como un promedio ponderado, donde la suma de
los α debe ser igual a 1. Comprobación α + (1- α) = 1. También es importante anotar
que α es un escalar y los puntos extremos son vectores formados por los valores de las
variables de decisión.

Ejemplo, ejercicio taller clase viernes

max z= 60x1+35x2+20x3

8x1+6x2+1x3 <= 48
4x1+2*x2+1.5x3<=20
2x1+1.5x2+0.5x3 <=8
x2<=5

Este es la tabla final del método simplex del problema

VB Z x1 x2 X3 s1 s2 s3 s4 P.R
Renglón 0
cero 1 0 0 0 10 10 0
s1 0 1.6 0 0 1 1.2 -5.6 0 27.2 27.2/1.6
x3 0 1.6 0 1 0 1.2 -1.6 0 11.2 11.2/1.6
x2 0 0.8 1 0 0 -0.4 1.2 0 1.6 1.6/0.8
s4 0 -0.8 0 0 0 0.4 -1.2 1 3.4 3.4/-0.8
P.R = prueba de la razón.

1. Es la tabla final porque todas las variables son positivas en el renglón cero.
2. La variable no básica x1 tiene coeficiente de 0 en el renglón cero, luego existen
óptimos alternos.
3. Condición de factibilidad: prueba de la razón; la variable x2 sale, mientras, la
variable x1 entra a la base con el valor igual a la prueba de la razón que en este
caso es de 2.
4. Valor de la función objetivo con la solución óptima de la tabla ( primer punto
extremo)

X1 =0
X2 =1.6
X3=11.2

Valor de la función objetivo: 60(0) +35(1.6)+20(11.2) = 280.

La función objetivo no cambia cuando entra x1 a la base y la variable x2 toma el valor 0 ya

que salió de la base, y puede a través de la función objetivo obtener el valor de x3.

Valor de la función objetivo: 60(2) +35(0)+20x3 = 280

Despejando x3 tenemos. 20x3: 280-120 = 160/20= 8

Así se tiene la segunda solución factible, con estos valores de las variables de decisión:

x1= 2, x2 = 0(sale de la base), x3 =8

Múltiples soluciones (combinación lineal) con dos variables es trazar una línea entre los
dos puntos extremos.

Multiplicación del escalar por cada componente de cada uno de los puntos extremos.

Primer punto: 0*α + 1.6* α +11.2* α

Segundo punto: 2*(1- α) + 0*(1- α) + 8 *(1- α)

Suma componente a componente: 2-2* α +1.6* α + 8 + 3.2* α

Recordando que el máximo valor de α =1.0

Valores α Puntos extremos

X1 X2 X3
0 2 0 8
0.1 1.8 0.16 8.32
0.2 1.6 0.32 8.64
0.3 1.4 0.48 8.96
0.4 1.2 0.64 9.28
0.5 1.0 0.8 9.6
0.6 0.8 0.96 9.92
 0.7 0.6 1.12 10.24
0.8 0.4 1.28 10.56
0.9 0.2 1.44 10.88
1.0 0 1.6 11.2

Interpretación de resultados (tabla final)

Max z= 3x1+2x2

x1+ 2x2 ≤6 ( recurso A)

2x1 + x2 ≤8 (recurso B)
-x1+x2 ≤1 (demanda)
x2≤2 (demanda)

Tabla explicación de las variables

Solución Costo de oportunidad Renglones diferentes Recursos y Numero de

(renglón cero) cero restricciones variables
Variables Tiene algún valor en 0
Básicas la solución.
Igual al
Decisión
numero de
Variables básica Tiene algún valor que 0 Se utilizan los Recursos
restricciones
holgura representa lo que se coeficientes para el abundantes.
m
dejo utilizar el análisis de sensibilidad Restricciones
recurso. no activas.
Variables no Su valor en la Diferentes de cero, si
Básicas solución es de cero es igual a cero existe
Decisión (no pertenecen a la un optimo alterno.
base)
Variables no Su valor en la Diferente de cero, Se utilizan los Recursos n-m
básica holgura solución es de cero precio sombra. Entre coeficientes análisis de escasos.
(no pertenecen a la mas escasos sea el sensibilidad Restricciones
base) recurso mayor es su activas
precio sombra

De la tabla final del método simplex o de las salidas de cualquier programa de

programación lineal es importante entender el significado de estos términos:

Variables

1. Variables Básicas

Recuerden que las variables de holgura y de decisión que están en la base tienen un
valor distinto de cero. Cualquier variable básica tiene este nombre por que todos sus
coeficientes en la tabla final de Simplex son cero exceptuando el renglón donde aparece
la variable en el cual tiene un coeficiente de1. Su valor corresponde al lado derecho de la
restricción del renglón donde su coeficiente es 1.

Como las variables de holgura tienen un valor distinto de cero, su recurso asociado es
abundante. El valor de la variable de holgura es lo que se dejo de utilizar de ese recurso.

2. Variables no Básicas

Las variables no básicas tiene un valor de cero (no pertenecen a la solución optima).
Cuando es una variable decisión tiene un coeficiente en el reglón cero que representa su
costo de oportunidad. Esto significa que su coeficiente en la función objetivo debe
aumentar marginalmente (ε) por encima de su costo de oportunidad; para que entre a la
base Si se aumenta el coeficiente en la función objetivo de la variable de decisión no
básica hasta su costo de oportunidad y se presenta un óptimo alterno (ver britto óptimos
alternos)

Supongamos que se tienen m restricciones y n variables.

Recursos

Recursos Abundantes: Se sabe que comprar más de un recurso abundante no produce

ninguna modificación en el valor de la función objetivo; si esto fuera cierto lo primero que
sería utilizar todo lo que se tiene disponible y después se compraría algo de este recurso.
Se puede hablar de abundancia solo hasta un límite. La pregunta que nos debemos hacer
es ¿Cuál es lo máximo que puedo disminuir el recurso abundante hasta que se vuelva
escaso?

La respuesta es sencilla: los recursos abundantes se convierten en escaso cuando se

utiliza o desperdicia el valor de sus variables de holgura asociado a ellos. En otras
palabras, los recursos abundantes solo se pueden desperdiciar en la holgura de sus
variables asociadas. Por lo tanto, el valor de Las variables de holgura que están
asociadas con recursos abundantes pueden disminuir hasta su valor y aumentar
infinitamente conservando las variables que forman la base factible óptima.

Recursos Escasos: Están asociados con las variables no básicas de holgura. Las
restricciones asociadas con las variables de holgura no básicas son activas.

Hay dos consideraciones de un recurso escaso:

 Como es escaso, se deben realizar todo los esfuerzos para no desperdiciarlo; si se

llega a desperdiciar el valor de su función objetivo disminuye.
 Si se tuviera más de ese recurso, la función objetivo aumentaría

Para todo recurso escaso conocer:

¿Cuánto me aumenta la función objetivo si adquiero una unidad de los recursos

escasos?

La primera respuesta se obtiene con el coeficiente en el renglón cero de la variable

asociada a ese recurso. En este caso, que el renglón cero son los costos de oportunidad.

Renglón Cero

Precio sombra: Es el coeficiente en el renglón cero de la tabla final con las variables de
holgura o exceso que son no básicas. Se define con tasa a la cual aumentaría o
disminuiría la función objetivo por contar con cantidades adicionales o desperdiciar
cantidades del recurso escaso.
.

cambio en el valor óptimo

Precio sombra 
cambio en el lado derecho

Es importante mencionar que la función objetivo no crece indefinidamente sino hasta que
la restricción pase de ser activa a no activa. Es decir, cuando el recurso se vuelve
abundante debido a la compra que se realiza de ese recurso.

Interpretaciones de Precio Sombra

Costo de oportunidad: por que es lo que le está dejando de ganar por no disponer o no
contar con una unidad mas de ese recurso.

Precio sombra: por que equivale a lo máximo que se estaría dispuesto a pagar por una
unidad más de ese recurso, ya que su función objetivo crece en ese valor. Es la tasa a la
cual aumenta la función objetivo por la compra de una unidad adicional del recursos
escaso) siempre se mantendrá dentro del intervalo permitido para que se conserve la
base optima

Los precios sombras se mantienen dentro de los rangos o límites del análisis de
sensibilidad.

Es importante resaltar que entre mas escaso es un recurso, mayor es su precio sombra.

Cálculos del Precio sombra

Max z= 3x1+2x2

x1+ 2x2 ≤6 ( recurso A)

2x1 + x2 ≤8 (recurso B)
-x1+x2 ≤1 (demanda)
x2≤2 (demanda)

Cuando se resuelva el problema completamente las restricciones activas son las

correspondientes al recurso A y recurso B y el valor óptimo de la función objetivo es
12.66667

x1+ 2x2 +s1 =7

2x1 + x2 +s2 =8

s1, s2 no están en la base porque sus restricciones son activas, por lo tanto su valor es
cero.

Al aplicar la definición de precio sombra, aumento en 0.5 la disponibilidad del recurso A.

x1+ 2x2=7 (1)

2x1+ x2 =8 (2)

Por eliminación o sustitución se obtienen los valores de x1 y x2.

-2x1-4x2= -14
2x1+x2= 8
-3x2= -6, x2 =2 Reemplazando en (2) x1 = 3

Valor del función objetivo= 3 (3) + 2(2)= 13

13.00  12.66 1
Precio sombra  
7-6 3

Precio sombra del recurso B.

Al aplicar la definición de precio sombra, aumento en 1.0 la disponibilidad del recurso B.

x1+ 2x2=6 (1)

2x1+ x2 = 9 (2)

por eliminación se obtienen los valores de x1y x2.

-2x1-4x2= -12
2x1+x2= 9

-3x2=-3, x2 =1. Reemplazando en (1) el valor de x1 = 4.

Valor de la función objetivo= 3 (4) + 2(1)= 14

14  12.66 4
Precio sombra   1.3333 
9-8 3

¿Cuantas unidades de los recursos escasos se deben comprar?

El límite de compra será hasta que estos recursos se vuelvan abundantes. Esto quiere
decir, una cantidad por encima de un valor determinado con lo que un recurso que antes
era escaso se vuelve abundante. Si el recurso se disminuye por encima del intervalo
permitido, la base cambia y el recurso escaso se vuelva muy apremiante por lo tanto su
precio sombra aumenta. Si se aumenta la cantidad de recurso por encima del intervalo
permitió se convierte en un recurso abundante y su precio sombra será de cero.

Usos de precios sombra

 PricingOut: cuando se desea fabricar un nuevo producto para el mercado se

puede conocer cuál debe ser su precio mínimo para que sea atractivo a la
empresa. Para obtener el precio mínimo por unidad de este nuevo producto es
necesario conocer la cantidad que consume de cada uno de los recursos. El
precio del nuevo producto debe compensar el costo de oportunidad de unos
recursos escasos que pueden ser utilizados en la producción de otros bienes.
n
Precio nuevo Producto: a
j 1
ij PSi

Donde PSi es el precio sombra de los recursos y aij(coeficiente en las restricciones) es el

consumo de cada variable de decisión sobre los recursos disponibles. Esta es una forma
más general de los que se presenta en el “a note on linear programming” sin embargo,
recordemos que solo los recurso escasos tienen un precio sombra.
Costos de Oportunidad (costo reducido) de Variables de Decisión No Básicas

Cuando una variable decisión no se considera en la en solución óptima, tiene un costo de

oportunidad que representa el aumento que debe tener su coeficiente en la función
objetivo para que esta variable sea atractiva. Si se aumenta su coeficiente exactamente
en su costo reducido se presentan óptimos alternos, si se aumenta un delta por encima
del costos reducido su coeficiente en la función objetivo esta variable entraría a la base.

El costo reducido es la diferencia del costo de los recursos que requiere una variable de
decisión menos su aporte (coeficiente) en la función objetivo. Si una variable aporta
menos a los recursos de gasta en recurso no se tendrá en cuenta en la solución óptima,
por lo tanto es una variable no básica.

n
Costos reducido=  ai j PSi -Cj
j 1

Donde se Cj es el coeficiente de la variable en la función objetivo

Análisis de sensibilidad

El análisis de sensibilidad permite conocer los cambios permitidos de incremento o

disminución tanto en los coeficientes de las variables de decisión en la función objetivo
como en el lado derecho de restricciones para que las variables que se encuentran en la
solución básica óptima no cambien; o sea, para que la base se conserve. Esto es
importante puesto que un proveedor puede suministrar en un período determinado,
menor cantidad de materias primas; la empresa se ve obligada a reducir sus precios por
la entrada de un nuevo competidor.

Un operario desperdicio uno de los recursos de la empresa, usted como gerente le

interesa saber sus variables que formaba su solución óptima aún son las mismas después
de estas hechos.

Max z= 3x1+2x2

x1+ 2x2 ≤6 ( recurso A)

2x1 + x2 ≤8 (recurso B)
-x1+x2 ≤1 (demanda)
x2≤2 (demanda)
 precios sombras Variables asociadas a recursos escasos

Bàsica z x1 x2 S1 S2 S3 S 4 Solución
z 1 0 0 1/3 4/3 0 0 38/3
x2 0 0 1 2/3 - 1/3 0 0 4/3

x1 0 1 0 - 1/3 2/3 0 0 10/3

S3 0 0 0 -1 1 1 0 3

S4 0 0 0 - 2/3 1/3 0 1 2/3

Variables asociadas
a recursos abundantes Analisis de sensibilidad
cantidad de los
recursos(demanada) no utilizados

E D

C
F

A B

La Solución óptima está localizada en el punto extremo C.

Coeficientes Variables de decisión

Cuando se cambian los coeficientes de las variables de decisión en la función objetivo sin
realizar cambios en la región factible (restricciones), lo que se está buscando, si lo
visualiza en dos dimensiones, es cuanto puede variar la dirección del gradiente para que
siga encontrando el mismo punto extremo. Es decir, en este caso se dan unos valores en
los que pueden aumentar ò disminuir los coeficientes de la función objetivo sin cambiar la
base ni su valor (en otras palabras, se mantiene como solución óptima los mismos valores
de las variables).

Coeficientes Lado derecho

En el caso del análisis de sensibilidad para los coeficientes del lado derecho,
manteniendo constantes los coeficientes de la función objetivo, se obtienen valores en los
que estos pueden aumentar o disminuir manteniendo la base. Es decir, se mantienen las
mismas variables en la solución óptima pero su valor cambia con respecto a la solución
original (debido a que se están haciendo modificaciones a la región factible).

Cuando se están obteniendo los límites para los recursos es importante diferenciarlos en
los recursos abundantes y los recursos escasos.

El cambio del lado derecho solo afecta nuestra región factible; se contrae con disminución
de un recurso escaso y se expande si es aumentado. Se puede afirmar que un cambio
del lado derecho solo afecta la factibilidad de la solución. Por consiguiente si se asume un
cambio de Δ del lado derecho de una restricción en particular se tiene que seguir
manteniendo que todas las variables son no negativas. El aumento y la disminución
permitida en el lado derecho (disponibilidad de un recurso) para que la solución actual se
mantenga, esta dado por la satisfacción simultanea de un número de inecuación igual a
las variables básicas, es decir la intersección de estas inecuaciones. Las inecuaciones se
obtienen de los coeficientes de los reglones distintos de cero de las variables de holgura
no básicas de la tabla final y el lado derecho de la tabla final.

A continuación se dan las inecuaciones con el tabla final que aparece al comienzo del
tema de análisis de sensibilidad, para cada uno de los recursos escasos.

Recurso A
4 2
X1=    0 Δ ≥-2
3 3
10 2
X2=    0 Δ ≤ 10
3 3
S3 = 3- Δ ≥ 0 Δ≤3
2 2
S4=    0Δ ≤ 1
3 3

Intersección de las soluciones esta dada por :

-2 ≤ Δ ≤ 1

Incremento permito del recurso A es 1 y la disminución 2.

 D C

A B

La Solución óptima está localizada en el punto extremo C con un valor igual a 13 (¿cómo
se obtiene este nuevo valor de esta función objetivo a partir del valor de la función objetivo
anterior?

Al incrementar la disponibilidad del recurso A de 6 a 7.5, en 0.5 por encima de su

aumento permitido; la gráfica muestra que se vuelve un recurso abundante luego su
variable de holgura asociada S1 entra a la base y demanda 2 (cuarta restricción) se
vuelve un recurso escaso y su variable asociada s4 sale de la base.

Recurso B
4 1
X1=  0 Δ≤4
3 3
10 2
X2=  0 Δ ≥ -5
3 3
S3 = 3 +Δ ≥ 0 Δ ≥ -3
2 1
S4=    0 Δ ≥- 2
3 3

-2 ≤ Δ ≤ 4
 D C

A B

La Solución óptima está localizada en el punto extremo C con un valor igual a 18

Al incrementar la disponibilidad del recurso A de 8 a 13, en 1 por encima de su aumento

permitido, la gráfica muestra que se vuelve un recurso abundante luego su variable de
holgura asociada S2 entra a la base. La única restricción que es activa es la 1 y la
variable de x2 sale de ala base.

Vision Alternativa

Los coeficientes de las variables no básicas de holgura se pueden ver como la relación de
estos recurso con los otros recursos, en donde el signo (+) representa lo que tiene en
exceso con respecto a los otros recursos .es decir lo que puede disminuir y signo (–) lo
que tiene en déficit con respecto a otro recurso, o sea, lo que puede aumentar; Así debe
calcular las relaciones tanto de aumento y disminución y escoger la más pequeña de cada
una.

Este método tiene la ventaja que se sigue aplicando un criterio de factibilidad.

 Lado derecho del tableau 

Aumento permitido= min  
 coeficiente negativos de la columna de recursos escasos 

 Lado derecho del tableau 

Disminución permitida  min  
 coeficiente positivos de la columna de recursos escasos 
Recurso A

 Aumento permitido.

10 2
3  10 3  1 3  3 el mínimo de estos es 1, luego el aumento permitido es 1.
1 2 1
3 3
 Disminución permitida

4
3 2
2
3

Ejemplo

Salidas de Lingo
Global optimal solution found.
Objective value: 12.666
Total solver iterations: 2

Variable Value Reduced Cost

X1 3.333 0.000000
X2 1.333 0.000000

Row Slack or Surplus Dual Price

1 12.666 1.000
2 0.000 0.333
3 0.000 1.333
4 3.000 0.000
5 0.667 0.000

Ranges in which the basis is unchanged:

Objective Coefficient Ranges

Current Allowable Allowable
Variable Coefficient Increase Decrease
X1 3.000 1.000000 2.000
X2 2.000 4.000000 0.500
Righthand Side Ranges
Row Current Allowable Allowable
RHS Increase Decrease
2 6.000 1.000 2.00
3 8.000 4.000 2.000
4 1.000 INFINITY 3.000
5 2.000 INFINITY 0.667

Las dos demandas son abundantes por lo tanto su incremento es infinito y su disminución
es igual al valor de su holgura, 3.000 y 0.667 respectivamente.

El recurso A es escaso y la compra de una unidad adicional de este producto aumenta la

función objetivo en 0.3333 .Se deben comprar máximo una unidad adicional, por encima
de este valor se vuelve abundante y no trae ningún beneficio a la empresa.

El valor de la función objetivo es de 13 cuando se compra cuatro unidades de este

recurso. (13-12.666)/1 =0.33, el precio sombra se mantiene en el intervalo del análisis de
sensibilidad. Si se disminuye en dos unidades, el valor de la función objetivo es de 12.
(12.66 -12)/2 = 1.33, el precio sombra se mantiene en el intervalo. Si el recurso se
disminuye en 3 unidades, la base cambia y el precio sombra pasa de 0.33 a 3. Si se
aumenta en 2 unidades, la base cambia y el precio sombra es cero ya que se convierte en
un recurso abundante.

Restricciones.

Restricción activa es la que se cumple como una igualdad. Las variables de holgura o
exceso son cero.

Restricciones no activas son las que son inecuaciones. Las variables de exceso o holgura
tiene un valor diferente a cero.

Adición de restricciones: cuando se adiciona una restricción la región factible se contrae

(si es una restricción activa) o no sufre ninguna consecuencia.

Supresión de restricciones: cuando se quitan restricciones la región factible se expande o

no sufre ningún efecto.
Resumen

Análisis sensibilidad Valores de las variables que Valor de la solución objetivo

forman la Base óptima
Lado derecho
Para saber los cambios permitidos se debe garantizar que las variables sigan siendo no
negativas, es decir se cumpla el criterio de factibilidad por que es la región factible la que
se modifica.
Recursos Cambian Cambia: este cambio esta
Escasos dado por lo precios sobra.
Recursos abundantes No cambian. No cambian
Coeficientes función Objetivos
La región factible no sufre modificación, lo que cambia es la dirección del gradiente. Sólo
se permite un cambio de gradiente en el cual el punto extremo es el mismo
Variables de decisión No cambia: la región factible se Cambia, ya que los
básicas conserva porque las coeficientes de las variables
restricciones no sufren se modifican.
modificaciones.
Variables de decisión No cambia, la región factible se No cambia, pero se presenta
no básicas conserva porque las la posibilidad de óptimos
restricciones no sufren alternos cuando la variable se
modificaciones. incrementa su coeficiente
hasta su aumento permitido.