Programação Linear: Métodos de Solução

Vista previa del material en texto

1 
 
 
 
 
2.2 PROGRAMACION LINEAL: 
 
METODOS DE SOLUCION 
 
 
 
 
 
 
 
 
1. METODO GRAFICO 
 
 
2. METODO SIMPLEX - ALGEBRAICO 
 
 
3. METODO SIMPLEX - TABULAR 
 
 
4. METODO SIMPLEX - MATRICIAL 
 
 2 
2.2.1 METODO GRAFICO 
(modelos con 2 variables) 
 
1. TRAZAR EN UN PLANO LAS RESTRICCIONES 
 
2. IDENTIFICAR LA REGION FACTIBLE 
 
3. TRAZAR LA DIRECCIóN DE MAX ASCENSO 
 
4. IDENTIFICAR EL PUNTO OPTIMO 
 
NOTAS: 
 
- En modelos con 2 variables: 
 - Una restricción de exacta igualdad se representa por una recta 
 - Una restricción “mayor igual” ó “menor igual” divide el espacio de 
 soluciones en dos semiplanos 
 
- La Región factible es el conjunto de puntos que satisfacen todas las 
 restricciones 
 
- Los Vértices ocurren en la intersección de 2 ó mas restricciones 
 
- Los Vértices siempre estan localizados en la frontera de la region 
factible 
 
- Toda función lineal f(x1,x2,. . .) se puede expresar como el producto escalar 
del vector de coeficientes c = (c1, c2, … ) y el vector de variables de 
decisión x = (x1, x2, … ). Es decir f(x1,x2) = c1x1 + c2x2 = c⋅x 
 
- La dirección de max ascenso sobre la función objetivo f es la dirección 
del vector c 
 
- El punto óptimo es aquel en la región factible asociado con el vector que 
tiene la mayor proyección sobre el vector c. 
 
- De existir, una solucion óptima de un modelo de PL siempre ocurre 
 en un vértice de la región factible.
 3 
 
METODO GRAFICO 
 
 
 
Ejemplo: 
 
Máx X1 + 2X2 
sa. 
 4X1 + 2X2 ≤ 16 
 
 3X1 + 3X2 ≥ 18 
 
 X2 ≥ 3 X1, X2 ≥ 0 
 
 
 
a) Determinar la solución óptima 
 
b) Deteminar las restricciones activas y las inactivas 
 
c) En el punto óptimo, determinar los valores de holgura y excedente para 
cada restricción 
 
d) Determinar las restricciones redundantes 
 
e) Determinar la solución óptima si la F.O. fuese Min 
 
f) Determinar la solución óptima si además la 2da restricción cambia a 
3X1 + 6X2 ≥ 18 
 
g) Determinar la solución óptima si además la 1ra restricción cambia a 
X1 + X2 ≤ 2 
 
 
 
 
 4 
Modelo en forma estándar 
 
Máx X1 + 2X2 
sa. 
 4X1 + 2X2 + S1 = 16 
 
 3X1 + 3X2 - S2 = 18 
 
 X2 - S3 = 3 
 
 X1, X2 , S1, S2 ,S3 ≥ 0 
 
§ La solución básica de un sistema de ecuaciones lineales de n por m, si 
existe, es una solución en la que se forza a que (n-m) variables tomen 
valor igual a cero. 
§ A las (n-m) variables forzadas a tomar valor igual a cero se les llama 
variables no básicas. 
§ El valor de las variables restantes resulta de resolver el sistema de 
ecuaciones lineales. A estas variables se les llama variables básicas. 
§ El máximo número de soluciones BASICAS es igual al número de 
parejas que se pueden formar con 5 variables: 
 
 
10)!25(!2
!5
2
5 =−=






 
 
 
Solución Variables Función objetivo Z 
Básica No. X1 X2 S1 S2 S3 
1 0 0 No factible 
2 0 0 
3 0 0 
4 0 0 No factible 
5 0 0 No factible 
6 0 0 No factible 
7 0 0 No factible 
8 0 0 
9 0 0 No factible 
10 0 0 No factible 
 5 
2.2.2 ANÁLISIS POSTERIOR A LA RESOLUCIÓN 
 
Una vez resuelto un modelo de PL se debe distinguir entre: 
 
 
RESTRICCIONES ACTIVAS 
 
Son aquellas que se cumplen con exacta igualdad en la solución óptima 
 
 
 
RESTRICCIONES INACTIVAS 
 
Son aquellas que tiene holgura o excedente 
 
 
 
Las restricciones activas son las que impiden el obtener una solución mejor 
que la solución óptima ya encontrada 
 
 
 
RESTRICCIONES REDUNDANTES 
 
 Son aquellas que de no estar presentes en el modelo, no modificarían 
la región factible ni la solución óptima. 
 
 
 
 6 
MÉTODO GRÁFICO con 3 variables 
 
 
 
 X3 
 
 
 
 
 
 
 
 5 
 3 
 
 
 
 
 
 
 1 2 
 
 X1 
 
 
 4 
 
 
 
 X2 
 
 
 
 
 7 
 
2.2.3 CASOS ESPECIALES 
 
 
1. MULTIPLES OPTIMOS (óptimos alternos) 
 
 Una restricción es paralela a la función objetivo 
 
Máx -3X1 + 6X2 
sa. 
 5X1 + 7X2 ≤ 35 
 -X1 + 2X2 ≤ 2 X1, X2 ≥ 0 
 
 
2. SOLUCION OPTIMA ILIMITADA (no acotada) 
 
 La región factible se extiende sin límites en alguna dirección 
 
Máx 2X1 + X2 
sa. 
 X1 - X2 ≤ 10 
 2X1 - X2 ≤ 40 X1, X2 ≥ 0 
 
(y si la función objetivo fuese Máx 2X1 - 1.5 X2 ? ) 
 
 
3. NO EXISTE SOLUCION (inconsistencia) 
 
 No existe región factible 
 
Máx 3X1 + 2X2 
sa. 
 2X1 + X2 ≤ 2 
 3X1 + 4X2 ≥ 12 X1, X2 ≥ 0 
 
 8 
2.2.4 ANÁLISIS GRÁFICO 
 
 
Sea la restricción : a1 x1 + a2 x2 ≤ b 
 
 
que se puede escribir como: x2 ≤ 
b
a2
 - a
a
1
2
 x1 
 
 
y graficar como: 
 
 X2 
 
 
 b
a2
 
 
 
 
 
 
 
 
b
a1
 X1 
 
 
Del gráfico se puede concluir que: 
 
 
1. Si únicamente cambia el valor de b la recta se mueve paralelamente 
 
2. Si sólo cambia el valor a2 la recta rota girando alrededor de 
b
a1
 
3. Si sólo cambia el valor a1 la recta rota girando alrededor de 
b
a2
 
 
 
 9 
EJERCICIO 
 
 
Considere el siguiente modelo de PL: 
 
 
Máx Z = 600 X1 + 1000 X2 
 
s.a. 100 X1 + 60 X2 ≤ 21,000 
 
 4000 X1 + 800 X2 ≤ 680,000 
 
 X1 + X2 ≤ 290 
 
 12 X1 + 30 X2 ≤ 6,000 X1 , X2 ≥ 0 
 
 
 
a) Determine la solución óptima 
 
b) Determine las restricciones activas, inactivas y redundantes. 
 
c) Cuál es el cambio mínimo del lado derecho de cada restricción redundante 
que la convierte en restricción activa ? 
 
d) El coeficiente de X1 en la tercera restricción es igual a uno. Cual es el 
cambio mínimo de este coeficiente que la convertiría en activa ? 
 
e) Suponga que el coeficiente de X1 en la función objetivo cambiase mientras 
que el coeficiente de X2 permanece inalterable. Cual es el cambio mínimo del 
coeficiente de X1 que ocasiona que existan multiples optimos en la solución ? 
 
 
 
 
 10 
2.2.5 FORMA ESTANDARD 
(Se usa para resolver un modelo por medio del algoritmo Simplex) 
 
 
- Todas las variables son NO negativas 
 
- Los elementos del lado derecho de cada restricción son No negativos 
 
 Si el lado derecho es negativo debe multiplicarse toda la 
 restricción por (-1) invirtiendo el sentido de la desigualdad 
 
- Todas las restricciones se convierten a ecuaciones, agregando variables de 
 holgura ó de excedente (excepto las restricciones de No negatividad) 
 
 Si la restricción es del tipo ≤ se debe sumar una 
 variable de holgura al lado izquierdo de la restricción 
 
 Si la restricción es del tipo ≥ se debe restar una 
 variable de excedente al lado izquierdo de la restricción 
 
 
EJEMPLO 
 
Modelo Original Modelo en Forma Estándar 
 
Min Z = 5x1 + 2x2 - x3 Min Z = 5x1 - 2x2 - x3 + 0s1 + 0 s2 + 0s3 
sujeto a sujeto a 
 -x1 + x2 - x3 ≤ 16 -x1 - x2 - x3 + s1 = 16 
 2x1 - 2x3 ≥ 30 2x1 - 2x3 -s2 = 30 
 x1 + 2x2 ≥ -8 -x1 + 2x2 +s3 = 
8 
 
 x1 , x3 ≥ 0 x2 ≤ 0 x1 , x2 , x3 , s1 , s2, s3 ≥ 0 
 
 
El convertir el modelo a forma estándar aumenta el número de variables, 
manteniendo el número de restricciones. 
 
 11 
EJEMPLO 
 
 Máx Z = 18.5x1 + 20 x2 
sujeto a 
 0.05x1 + 0.05 x2 ≤ 1100 
 0.05x1 + 0.10 x2 ≤ 1800 
 0.10x1 + 0.05 x2 ≤ 2000 x1 , x2 ≥ 0 
 
este modelo tiene n = 2 variables de decisión 
 y m = 3 restricciones 
 (sin considerar las de no negatividad) 
 
 
Este modelo convertido a forma estándar es: 
 
 
 Máx Z = 18.5x1 + 20x2 + 0s1 + 0s2 + 0s3 
sujeto a 
 0.05x1 + 0.05 x2 + s1 = 1100 
 0.05x1 + 0.10 x2 +s2 = 1800 
 0.10x1 + 0.05 x2 +s3 = 2000 
 x1 , x2 , s1 , s2 , s3 ≥ 0 
 
ahora el modelo tiene n = 5 variables 
 y m = 3 restricciones 
 
Forma matricial de las restricciones del modelo en forma estándar: 
 
 
 0.05 0.05 1 0 0 X1 1100 
 0.05 0.10 0 1 0 X2 = 1800 
 0.10 0.05 0 0 1 S1 2000 
 3x5 S2 3x1 
 S3 
 5x1
 12 
Al expresar un modeloen forma estándar se convierte el conjunto de restricciones de un 
modelo de programación lineal a un sistema de ecuaciones lineales simultáneas. 
 
Si denotamos por n el número de variables en el modelo en forma estándar y por m el número 
de restricciones, decimos que el modelo en forma estándar es de dimensiones n por m. Esto 
porque el modelo incluye m ecuaciones lineales simultaneas en n variables. 
 
Un sistema de ecuaciones lineales simultaneas de m por n puede tener solución o no. En general 
puede ocurrir uno de tres situaciones. Que el sistema 
 
1. Tenga una solución única 
2. Tenga infinitas soluciones 
3. No tenga solución 
 
Si el sistema no tiene solución se dice que es un sistema inconsistente. 
 
En un modelo de programacion lineal en forma estándar siempre se cumple que m < n. Y salvo 
casos excepcionales, supondremos que el sistema de ecuaciones del modelo tendrá infinitas 
soluciones. Cada una de éstas corresponde a un punto de la región factible. 
 
DEFINICION 
Se denomina punto extremo de la región factible a aquel punto que no puede 
expresarse como una combinación lineal convexa de otros puntos en esta 
región. 
 
En términos sencillos un punto extremo se representa como un vértice de la región factible 
 
PROPOSICION 
La solución óptima de un modelo de programación lineal, si existe y no es 
ilimitada, siempre corresponde a un punto extremo de la región factible. 
 
Esta proposición es muy importante. Con base en ella, basta solo con tener un método que 
evalúe la función objetivo de un modelo de programacion lineal en los puntos extremos de la 
región factible. 
 
DEFINICION 
La solución básica de un sistema de ecuaciones lineales de n por m, si existe, es 
una solución en la que se forza a que (n-m) variables tomen valor igual a cero. 
 
A las (n-m) variables forzadas a tomar valor igual a cero se les llama variables no básicas. 
 
El valor de las variables restantes resulta de resolver el sistema de ecuaciones lineales. A estas 
variables se les llama variables básicas. 
 13 
 
DEFINICION 
La solución básica de un sistema de ecuaciones lineales de n por m existe si al 
eliminar (n-m) variables el sistema resultante de m por m es consistente. 
 
Esta definición indica que al forzar a que (n-m) variables tomen valor igual a cero puede ocurrir 
que las m ecuaciones lineales resulten en un sistema sin solución (inconsistente). 
 
 
Por ejemplo en el siguiente sistema 2x1 + 4 x2 + 3x3 = 8 
 3x1 + 6 x2 + 3x3 = 17 
 
si se consideran variable no basica a la variable x3 entonces el sistema resultante mostrado no 
tiene solución. 
2x1 + 4 x2 = 8 
 3x1 + 6 x2 = 17 
 
DEFINICION 
La solución básica de un sistema de ecuaciones lineales de n por m se dice 
factible (y se denota por SBF) si todas las variables toman valor no negativo. 
 
En nuestro ejemplo: n-m = 5 - 3 = 2 variables 
 
S2 = 0 X1 = 14,666.66 
S3 = 0 ⇒ X2 = 10,666.66 Esta es una Solucion BASICA No Factible 
 S1 = - 166.66 
 
Si: 
X2 = 0 X1 = 20,000 
S3 = 0 ⇒ S2 = 800 Esta es una Solución BASICA Factible 
 S1 = 100 
 
Se llama BASE al conjunto de VARIABLES BASICAS. 
 
PROPOSICION 
Cada SBF de un modelo de programación lineal corresponde a un punto 
extremo de su región factible. 
 
Por tanto la solución optima de un modelo de programación lineal, si existe y no es ilimitada, 
correponde a una solución básica factible. En otras palabras, cada SOLUCION BASICA 
FACTIBLE representa un vértice de la región factible. 
 
 14 
 
En el ejemplo, el máximo número de soluciones BASICAS es igual al número de parejas que 
se pueden formar con 5 variables: 
 
10)!25(!2
!5
2
5 =−=






 
 
En general, el máximo número de soluciones BASICAS es igual al número de conjuntos de m 
elementos, que se pueden formar con n variables, es decir 
 
 
)!(!
!
mnm
n
m
n
−
=




 
 15 
SOLUCIONES BÁSICAS 
 
Solución Variables Función objetivo 
No. X1 X2 S1 S2 S3 Z 
1 0 0 1,100 1,800 2,000 $0 
2 0 22,000 0 -400 900 No factible 
3 0 18,000 200 0 1,100 $360,000 
4 0 40,000 -900 -2,200 0 No factible 
5 36,000 0 -700 0 -1,600 No factible 
6 20,000 0 100 800 0 $370,000 
7 22,000 0 0 900 -200 No factible 
8 8,000 14,000 0 0 500 $428,000 
9 18,000 4,000 0 500 0 $413,000 
10 14,666.6 10,666.6 -166.61 0 0 No factible 
 
 
X2 
 4 Máx Z = 18.5x1 + 20 x2 
 40 sa. 
 0.05x1 + 0.05 x2 ≤ 1100 
 0.05x1 + 0.10 x2 ≤ 1800 
 0.10x1 + 0.05 x2 ≤ 2000 x1 , x2 ≥ 0 
 30 
 
 
 2 
 
 20 
 8 
 3 
 10 
 10 
 Región 
 
 Factible 9 
 
 X1 
 1 6 7 5 
 10 20 30 
 16 
EJEMPLO 
 
 
Considere el siguiente modelo de PL 
 
 
 Máx Z= 5x1 -6x2 +3x3 -5x4 +12x5 
 
 sujeto a 
 
 x1 + 3x2 + 5x3 +6x4 +3x5 ≤ 90 x1 , x2 , x3 , x4 , x5 ≥ 0 
 
 
 
a) Cuántas varibales básicas tiene ? 
 
b) Cuántas soluciones básicas existen ? 
 
c) Cuáles son las soluciones básicas? 
 
d) Cuál es la solución óptima ? 
 
 
 17 
Modelo en Forma Estándar 
 
 
Máx Z= 5x1 -6x2 +3x3 -5x4 +12x5 + 0 s 
 
sujeto a 
 
x1 + 3x2 + 5x3 +6x4 +3x5 + s = 90 x1 , x2 , x3 , x4 , x5 , s ≥ 0 
 
 
 
 
a) Cuántas variables básicas tiene ? m = 1 variable básica 
 
 
 
b) Cuántas soluciones básicas existen ? Cm
n = C1
6 = 6 soluciones 
básicas 
 
 
 
c) Cuáles son las soluciones básicas ? 
 
 
 
Sol.Bas X1 X2 X3 X4 X5 S Z 
1 90 0 0 0 0 0 450 
2 0 30 0 0 0 0 -180 
3 0 0 16 0 0 0 90 
4 0 0 0 15 0 0 -75 
5 0 0 0 0 30 0 360 
6 0 0 0 0 0 90 0 
 
 18 
2.2.6 METODO SIMPLEX (George Dantzig, 1947) 
 
Existen varias formas de resolver un modelo de programación lineal. El 
metodo mas comunmente usado es el metodo simplex. Este metodo 
encuentra la solución óptima de un modelo de PL, evaluando la función 
objetivo, en cada vértice de la región factible. 
 
METODOLOGIA 
 
 Nótese que en modelos de dos variables en cualquier intersección de 
dos restricciones, hay dos variables que toman valor igual a cero. Por tanto 
para conocer el valor de las otras variables se debe resolver el sistema de m 
restricciones con m variables. 
 
 Una manera sencilla de encontrar una SOLUCION BASICA 
FACTIBLE es identificar una matriz identidad en las restricciones del modelo 
escrito en forma estándar. Las variables asociadas con esta matriz identidad 
son las VARIABLES BASICAS 
 
 X1 X2 S1 S2 S3 
 
 0.05 0.05 1 0 0 X1 1100 
 0.05 0.10 0 1 0 X2 = 1800 
 0.10 0.05 0 0 1 S1 2000 
 3x5 S2 3x1 
 S3 
 5x1 
 
 En cada paso del algoritmo se resuelven simultáneamente las m 
ecuaciones que conforman un vértice para identificarlo. Se verifica si el 
vértice es el óptimo, si no lo es, se pasa a otro vértice adyacente. 
 
 El algoritmo asegura que en el siguiente vértice, la funcion objetivo no 
tendrá un valor peor que en el vértice anterior 
 19 
 
2.2.6.1 METODO SIMPLEX -ALGEBRAICO 
 
 
PROCEDIMIENTO 
 
 
1. Encontrar una Solucion Basica Factible inicial 
 Expresando el modelo en forma estándar 
 identificando las columnas de una matriz identidad de m x m. 
 
 
2. Expresar las variables basicas y la funcion objetivo en funcion de las 
 variables No basicas 
 
 
3. Verificar Optimalidad 
 
 La solución es óptima si: 
 La función objetivo no puede mejorar de valor al incrementar 
 el valor de cualquiera de las Variables No Basicas 
 
4. Identificar Nuevas variables básica y No básica 
 
 Nueva VB : la VNB que mejora más la función objetivo. 
 
 Nueva VNB: la VB que se hace igual a 0 
 al tomar la nueva VB el máximo valor posible. 
 
 
5. Regresar al paso 2. 
 
 
 
 20 
EJEMPLO 
 
En forma original: En Forma estándar: 
 
Máx Z = 10x1 + 14x2 Máx Z = 10x1 + 14x2 + 0s1 + 0s2 
sujeto a: sujeto a: 
 4x1 + 6x2 ≤ 24 4x1 + 6x2 + 1s1 + 0s2 = 24 
 2x1 + 6x2 ≤ 20 2x1 + 6x2 + 0s1 + 1s2 = 20 
 x1 , x2 ≥ 0 x1 , x2 , s1, s2 ≥ 0 
 
 
Inicio: 
 
 Base (VB’s) VNB’s 
 s1 = 24 x1 = 0 Z = 0 
 s2 = 20 x2 = 0 
 
 
Expresar VB’s y Z en función de VNB (del modelo en forma estándar ) 
 
S1 = 24 - 4x1 - 6x2 
S2 = 20 - 2x1 - 6x2 (1) 
Z = 0 + 10x1 + 14x2 No estamos sobre el vértice óptimo ! 
 Variable que entra a la base es x2 
 
 
Variable que sale de la base es: 
 
S1 = 24 - 6x2 ≥ 0 x2 ≤ 4 
S2 = 20 - 6x2 ≥ 0 x2 ≤ 3.33 x2 entra a la base con valor x2 = 
3. 33 
 ( s2 = 0 es la variable que sale ) 
 
 
 
 
 
 
 21 
 
1ra iteración: 
 
 Base (VB’s) VNB’s 
 s1 = 4 x1 = 0 Z = 46.66 
 x2 = 3.33 s2 = 0 
 
 
Expresar VB’s y Z en función de VNB (comenzar de (1) ) 
 
 
X2 = (20 - 2x1 - s2 ) / 6 = 3.33 - 0.33x1 - 0.166s2 
S1 = 24 - 4x1 - 6 (
1/6 (20 - 2x1 - s2 )) = 4 - 2x1 + s2 
Z = 0 + 10 x1 + 14 (
1/6 (20 - 2x1 - s2 )) = 46.6 + 5.33 x1 - 2.33 s2 
 
 No estamos sobre el vértice óptimo ! 
 Variable que entra a la base es x1 
 
Variable que sale de la base es: 
 
X2 = 3.33 - 0.33x1 ≥ 0 X1 ≤ 10 
S1 = 4 - 2x1 ≥ 0 X1 ≤ 2 x1 entra a la base con valor x1 = 2 
 ( s1 = 0 es la variable que sale ) 
 
 
 22 
2da iteración: 
 
 Base (VB’s) VNB’s 
 x1 = 2 s1 = 0 Z = 57.33 
 x2 = 2.66 s2 = 0 
 
 
Expresar VB’s y Z en función de VNB 
 
X1 = (4 + s2 - s1 ) / 2 = 2 + 0.50s2 - 0.5s1 
X2 = 3.33 - 0.33 ( 2 +.50s2 - 0.5s1 )-0.16s2 = 2.66 - 0.33s2 + 0.16s1 
Z = 46.66 + 5.33 (2 +0.50s2 - 0.5s1) -2.33s2 = 57.3 + 0.33s2 - 2.66 s1 
 
 No estamos sobre el vértice óptimo ! 
 Variable que entra a la base es s2 
Variable que sale de la base: 
 
X1 = 2 + 0.50s2 ≥ 0 s2 ≥ - 4 
X2 = 2.66 - 0.33s2 ≥ 0 s2 ≤ 8 s2 entra a la base con valor s2 = 8 
 ( X2 = 0 es la variable que sale ) 
 
 
3ra iteración: 
 
 
 Base (VB’s) VNB’s 
 x1 = 6 s1 = 0 Z = 60 
 s2 = 8 x2 = 0 
 
 
Expresar VB’s y Z en función de VNB 
 
S2 = (2.66 - x2 + 0.166s1 ) / 0.33 = 8 - 3x2 + 0.50 s1 
X1 = 2 + 0.50 (8 - 3x2 + 0.5s1 ) - 0.5s1 = 6 - 1.5x2 - 0.25 s1 
Z = 57.33 + 0.33 (8 - 3x2 + 0.5s1) - 2.66s1 = 60 - x2 - 2.50 s1 
 
 estamos sobre el vértice óptimo! 
 
 23 
 
 
2.2.6.1 METODO SIMPLEX - MATRICIAL 
 
El método simplex matricial se puede aplicar siguiendo los siguientes pasos 
 
1. Encontrar una Solucion Basica Factible inicial 
 Expresando el modelo en forma estándar 
 identificando las columnas de una matriz identidad de m x m. 
 (esto define a XB, CB y B) 
 
2. Calcular B-1 , B-1b y B-1N 
3. Expresar XB y Z en función de las variables no básicas. 
XB = B
-1b - B-1N XN 
Z = CB
T B-1 b + [CN
T - CB
T B-1 N ] XN 
 
4. Verificar la condición de optimalidad ([CN
T - CB
T B-1N ] ≤ 0 para max Z) 
 
5. Si la condición de optimalidad no se cumple se debe seleccionar 
§ la nueva variable básica NVB 
 (aquella con el mejor valor en [CN
T - CB
T B-1N] 
§ la nueva variable no básica 
 (la que toma valor cero cuando la NVB toma el max valor posible) 
 24 
2.2.6.2 METODO SIMPLEX -TABULAR 
 
PROCEDIMIENTO 
 
 
1. Encontrar una Solucion Basica Factible inicial 
 Convirtiendo las m restricciones en igualdades e identificando las 
 columnas de una matriz identidad de m x m. 
 
2. Construir la Tabla Inicial y verificar Optimalidad (ver paso 5) 
 
3. Identificar Nuevas Variable Básica (NVB) y Nueva variable No Básica 
 
 NVB : máx valor positivo de Cj - Zj (maximizacion) 
 
 NVNB: dividir bj entre los coeficientes positivos de la columna de NVB. 
 La NVNB se encuentra en el renglón que tiene el menor cociente. 
 
4. Actualizar la Tabla 
 
 - Identificar elemento Pivote 
 
- Nuevos valores en el renglón de NVB se obtienen al dividir el renglón 
que sale entre el pivote 
 
 - Otros renglones se obtienen por: 
 Nuevo renglon = Renglon anterior - 
 [elemento en columna del pivote] x renglon de NVB 
 
 - Calcular Zj como la suma de productos de CB por las tasas de sustitucion 
 
5. Verificar Optimalidad (maximización) 
 
 La base es óptima si todos los valores de Cj - Zj son cero o negativos. 
 
6. Volver al paso 3 
 25 
TABLA INICIAL 
 En Forma estándar: 
 
Máx Z = 10x1 + 14x2 Máx Z = 10x1 + 14x2 + 0s1 + 0s2 
sujeto a: sujeto a: 
 4x1 + 6x2 ≤ 24 4x1 + 6x2 + 1s1 + 0s2 = 24 
 2x1 + 6x2 ≤ 20 2x1 + 6x2 + 0s1 + 1s2 = 20 
 x1 , x2 ≥ 0 x1 , x2 , s1 , s2 ≥ 0 
 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
0 S1 24 4 6 1 0 
0 S2 20 2 6 0 1 
 Zj 
 Cj - Zj 
 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
0 S1 24 4 6 1 0 
0 S2 20 2 6 0 1 
 Zj 0 0 0 0 0 
 Cj - Zj 10 14 0 0 
 
 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
0 S1 24 4 6 1 0 4 
0 S2 20 2 6 0 1 3.33 
 Zj 0 0 0 0 0 
 Cj - Zj 10 14 0 0 
 
pivote cocientes 
 la tabla no es óptima! 
 
x2 entra a la base con valor x2 = 3. 33 ( s2 = 0 es la variable que sale ) 
 26 
1ra iteración: 
 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
0 S1 
14 X2 3.33 0.33 1 0 0.166 
 Zj 
 Cj - Zj 
 se divide el renglón 
 del pivote entre él 
 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
0 S1 4 2 0 1 -1 
14 X2 3.33 0.33 1 0 0.166 
 Zj 
 Cj - Zj 
 
 
renglon anterior 24 4 6 1 0 
- valor asociado -6 (3.33 0.33 1 0 0.166) 
 al pivote por el renglón actualizado del pivote 
 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
0 S1 4 2 0 1 -1 2 
14 X2 3.33 0.33 1 0 0.166 10 
 Zj 46.66 4.66 14 0 2.33 
 Cj - Zj 5.33 0 0 -2.33 
 
 pivote cocientes 
 
x1 entra a la base con valor x2 = 2 ( s1 = 0 es la variable que sale ) 
 27 
2da iteración: 
 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
10 X1 2 1 0 0.5 -0.5 
14 X2 
 Zj 
 Cj - Zj 
 se divide el renglon 
 del pivote entre él 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
10 X1 2 1 0 0.5 -0.5 
14 X2 2.66 0 1 -.166 0.33 
 Zj 
 Cj - Zj 
 
 
 
renglon anterior 3.33 0.33 1 0 0.166 
- valor asociado -.33( 2 1 0 0.5 -0.5 ) 
al pivote x 
renglón actualizado del pivote 
 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
10 X1 2 1 0 0.5 -0.5 
14 X2 2.66 0 1 -.166 0.33 
 Zj 57.24 10 14 2.66 -.33 
 Cj - Zj 0 0 -2.66 0.33 
 
 pivote 
S2 entra a la base con valor S2 = 8 (X2 = 0 es la variable que sale ) 
 28 
3ra iteración: 
 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
10 X1 
0 S2 8 0 3 -0.5 1 
 Zj 
 Cj - Zj 
 se divide el renglon 
 del pivote entre él 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
10 X1 6 1 1.5 0.25 0 
0 S2 8 0 3 -0.5 1 
 Zj 
 Cj - Zj 
 
 
renglon anterior 2 1 0 0.5 -0.5 
- valor asociado +.5(8 0 3 -0.5 1 ) 
al pivote x renglón actualizado del pivote 
 
 
 Cj 10 14 0 0 
CB base bj X1 X2 S1 S2 
10 X1 6 1 1.5 0.25 0 
0 S2 8 0 3 -0.5 1 
 Zj 60 10 15 2.5 0 
 Cj - Zj 0 -1 -2.5 0 
 
 Esta tabla es la óptima ! 
 
 
 29 
 
2.2.6.2 METODO SIMPLEX -TABULAR SIMPLIFICADO 
 
Para simplificar el procedimiento anterior se va a trabajar con una tabla más sencilla en la que 
en cada renglón se representa a las variables básicas y en cada columna se representa a las 
variables no básicas. En esta tabla las celdas sombreadas no se utilizan durante el 
procedimiento. 
 
 
 
 CN 
 BASE bj XN 
CB XB 
Valor de las 
variables 
básicas 
tasas de sustitución 
 ZJ 
 CJ - ZJ 
 
Donde: 
 
XB = conjunto de nombres de las variables básicas 
XN = conjunto de nombres de las variables no básicas 
CB = vector de coeficientes de las variablesbásicas en la función objetivo 
CN = vector de coeficientes de las variables no básicas en la función objetivo 
bj = valor de las variables básicas 
 
El renglón marcado como Zj resulta de multiplicar cada valor en la columna CB por cada valor 
de la columna bj y por cada valor de la columna XN. 
 
El renglón marcado como Cj – Zj resulta de restar cada valor en el renglon Zj de cada valor en 
el renglón CN. 
 
En cada iteración del procedimiento, una variable que reemplaza a otra ocupa el lugar que ésta 
tenía. 
 
 30 
 
 31 
PROCEDIMIENTO 
 
1. Encontrar una Solucion Basica Factible inicial 
 Convirtiendo las m restricciones en igualdades e identificando las 
 columnas de una matriz identidad de m x m. 
 
2. Construir la Tabla Inicial y verificar Optimalidad (ver paso 5) 
 
3. Identificar Nueva Variable Básica (NVB) y Nueva Variable No Básica (NVNB) 
 
 NVB : aquella con el mayor valor positivo de Cj - Zj (maximizacion) ó 
aquella con el mayor valor negativo de Cj - Zj (minimizacion) 
 
 NVNB: obtener cocientes al dividir bj entre los coeficientes positivos de la columna 
de NVB. La NVNB es aquella ubicada en el renglón con el menor cociente. 
 
 
4. Actualizar la Tabla 
 
- Reemplazar el nombre de la columna de la NVB por el nombre de la NVNB 
 
- Identificar elemento Pivote 
 
- Invertir el valor númerico del Pivote 
 
- El renglón actualizado de NVB se obtiene al dividirlo entre el pivote 
 
- La columna actualizada de NVNB se obtiene al dividirla entre (-pivote) 
 
- Otros renglones se obtienen por: 
 Nuevo renglon = Renglon anterior - 
 [elemento en columna del pivote] x renglon de NVB 
 
- Calcular Zj como la suma de productos de CB por cada una de las columnas de la tabla. 
 
 
5. Verificar Optimalidad 
 
Si el modelo es de maximización: 
 La base es óptima si todos los valores de Cj - Zj son cero o negativos. 
Si el modelo es de minimización: 
 La base es óptima si todos los valores de Cj - Zj son cero o positivos. 
 
 32 
 
6. Volver al paso 3 
 33 
EJEMPLO 
 En Forma estándar: 
 
Máx Z = 10x1 + 14x2 Máx Z = 10x1 + 14x2 + 0s1 + 0s2 
sujeto a: sujeto a: 
 4x1 + 6x2 ≤ 24 4x1 + 6x2 + 1s1 + 0s2 = 24 
 2x1 + 6x2 ≤ 20 2x1 + 6x2 + 0s1 + 1s2 = 20 
 x1 , x2 ≥ 0 x1 , x2 , s1 , s2 ≥ 0 
 
 
 Cj 10 14 
CB base bj X1 X2 
0 S1 24 4 6 
0 S2 20 2 6 
 Zj 
 Cj - Zj 
 
 
 Cj 10 14 
CB base bj X1 X2 
0 S1 24 4 6 
0 S2 20 2 6 
 Zj 0 0 0 
 Cj - Zj 10 14 
 
 
 Cj 10 14 
CB base bj X1 X2 
0 S1 24 4 6 4 
0 S2 20 2 6 3.33 
 Zj 0 0 0 
 Cj - Zj 10 14 
 
pivote cocientes 
 la tabla no es óptima! 
 
x2 entra a la base con valor x2 = 3. 33 ( s2 = 0 es la variable que sale ) 
 34 
1ra iteración: 
 
Primero se divide el renglon del pivote entre él 
 
 Cj 10 0 
CB base bj X1 S2 
0 S1 
14 X2 3.33 0.33 0.166 
 Zj 
 Cj - Zj 
 
 
 Cj 10 0 
CB base bj X1 S2 
0 S1 4 2 -1 
14 X2 3.33 0.33 0.166 
 Zj 
 Cj - Zj 
 
 
renglon anterior 24 4 
- valor asociado -6 (3.33 0.33 ) 
 al pivote por el renglón actualizado del pivote 
 
 
 Cj 10 0 
CB base bj X1 S2 
0 S1 4 2 -1 2 
14 X2 3.33 0.33 0.166 10 
 Zj 46.66 4.66 2.33 
 Cj - Zj 5.33 -2.33 
 
 pivote cocientes 
 
x1 entra a la base con valor x2 = 2 ( s1 = 0 es la variable que sale ) 
 35 
2da iteración: 
 
Primero se divide el renglon del pivote entre él 
 
 Cj 0 0 
CB base bj S1 S2 
10 X1 2 0.5 -0.5 
14 X2 
 Zj 
 Cj - Zj 
 
 
 Cj 0 0 
CB base bj S1 S2 
10 X1 2 0.5 -0.5 
14 X2 2.66 -.166 0.33 
 Zj 
 Cj - Zj 
 
 
 
renglon anterior 3.33 0.166 
- valor asociado -.33( 2 -0.5 ) 
al pivote x renglón actualizado del pivote 
 
 
 Cj 0 0 
CB base bj S1 S2 
10 X1 2 0.5 -0.5 
14 X2 2.66 -.166 0.33 
 Zj 57.24 2.66 -.33 
 Cj - Zj -2.66 0.33 
 
 pivote 
S2 entra a la base con valor S2 = 8 (X2 = 0 es la variable que sale ) 
 36 
3ra iteración: 
 
Primero se divide el renglon del pivote entre él 
 
 Cj 0 14 
CB base bj S1 X2 
10 X1 
0 S2 8 -0.5 3 
 Zj 
 Cj - Zj 
 
 
 Cj 0 14 
CB base bj S1 X2 
10 X1 6 0.25 1.5 
0 S2 8 -0.5 3 
 Zj 
 Cj - Zj 
 
 
renglon anterior 2 0.5 
- valor asociado +.5 (8 -0.5 ) 
al pivote x renglón actualizado del pivote 
 
 
 Cj 0 14 
CB base bj S1 X2 
10 X1 6 0.25 1.5 
0 S2 8 -0.5 3 
 Zj 60 2.5 15 
 Cj - Zj -2.5 -1 
 
 Esta tabla es la óptima ! 
 
 
 37 
Ahora comparemos esta tabla óptima ya encontrada, con la solución del 
método SIMPLEX con matrices. 
 
Sean las variables básicas X1 y S2 entonces 
 
XB = [X1 S2] XN = [S1 X2] 
 
CB
T = [10 0] CN
T = [0 14] 
 
B = [4 0] N = [1 6] 
 [2 1] [0 6] 
 
 
Determinamos B-1, B-1N y B-1b, 
 
¦ B ¦ = 4(1) – 0 (2) = 4 
 
B-1 = [¼ 0] 
 [-½ 1] 
 
B-1N = [¼ 0] [1 6] = [ ¼ 3/2 ] 
 [-½ 1] [0 6] [ -½ 3 ] 
 
B-1b = [¼ 0] [24] = [6] 
 [-½ 1] [20] [8] 
 
 
Y expresamos XB y Z en función de XN 
 
XB = [X1] = [6] - [ ¼ 
3/2] [S1 ] = [ 6 - ¼S1 - 
3/2 X2 ] 
 [S2 ] [8] [-½ 3 ] [X2] [ 8 + ½S1 – 3X2 ] 
 
 
 38 
Por tanto si comparamos ambas soluciones óptimas encontramos lo 
siguiente 
 
 
 CN
T 
 BASE bj XN
T 
CB XB B
-1b B-1N 
 ZJ CB
T B-
1b 
CB
T B-1N 
 CJ - ZJ CN
T - CB
T B-1N 
 
 
Y ya sea de la tabla o de las operaciones matriciales podemos obtener 
 
 XB = B
-1b – B-1N 
 
 Z = CN
T - CB
T B-1N 
 
es decir 
 
X1 = 6 - ¼ S1 – 3/2 X2 
 
S2 = 8 + ½ S1 – 3 X2 
 
Z = 60 – 5/2 S1 – X2 
 
Estas son expresiones de las variables básicas y de la variable de resultado en función de las 
variables no básicas. Los coeficientes de las variables no básicas en estas expresiones 
corresponden a los coeficientes de la matriz B-1N y se les llama tasas de sustitución porque 
representan las tasas a las que una variable aumenta o disminuye cuando una variable no básica 
la reemplaza. Por ejemplo si X2 toma valor unitario la variable X1 debe reducir su valor en 1.5 
unidades. 
 
 39 
La condición de optimalidad para un modelo de PL del tipo maximizar, establece que si los 
coeficientes de [CNT - CBT B-1N ] son todos negativos, como por ejemplo en 
 
Z = 60 – 5/2 S1 – X2 
 
entonces el aumentar de valor a una variable básica no mejorará el valor de la variable de 
resultado Z y por tanto la última solución básica encontrada es la óptima. 
 
Qué establecen las ecuaciones ? 
 
Supongamos que la variable no básica X2 incrementase su valor de 0 a 1. Entonces ocurrirían 
simultáneamente los siguiente 
 
§ La var. de respuesta Z aumentaría en 4 unidades (ya que Z = 10X1 + 14X2 ) 
§ La var. X1 disminuiría en 1.5 unidades 
§ La var. S2 disminuiría en 3 unidades 
§ La var. de respuesta Z disminuiría en 1.5(10) = 15 unidades 
 
El efecto neto en Z resultaría 14 – 15 = -1. 
 
El método simplex matricial se puede aplicar siguiendo los siguientes pasos 
 
6. Seleccionar un conjunto de variables básicas (la base). Esto define a XB. 
7. Especificar las matrices CBT , CNT , B y N 
8. Calcular B-1 , B-1b y B-1N 
9. Expresar XB y Z en función de las variables no básicas. 
10. Verificar la condición de optimalidad ( [CNT - CBT B-1N ] = 0 para max Z) 
11. Si la condición de optimalidad no se cumple se debe seleccionar 
§ la nueva variable básica NVB (aquella con el mejor valor en CNT - CBT B-1N) 
§ la nueva variable no básica (aquella que toma el valor cero cuando la NVB toma el 
max valor posible) 
 
 
 
 40 
2.2.6.3 METODO SIMPLEX -CASOS ESPECIALES 
 
 
MULTIPLES OPTIMOS 
 
Ocurre si para una(s) variable(s) No Básica(s) 
 
 1. Cj - Zj =0 ; y 
 2. Existe alguna tasa de sustitución positiva en la tabla óptima 
 
 
MINIMIZACION 
 
1. La reglapara la variable que entra a la Base cambia: 
 elegir la que tiene el valor Cj - Zj más negativo 
 
2. La tabla óptima se identifica cuando todos los valores de Cj - Zj son 
 cero o pósitivos. 
 
Alternativamente se puede multiplicar Z por (-1) 
 
 
 41 
MODELOS CON RESTRICCIONES ≥ y = 
 
 
En los modelos con restricciones ≥ y =, al añadir variables de holgura o de 
excedente no obtenemos una solución básica factible inicial 
 
Para encontrar una, agregamos al modelo en forma estándar, VARIABLES 
ARTIFICIALES a cada restriccion de ≥ y = . Estas variables formarán 
parte de la base inicial 
 
Existen dos métodos para resolver modelos de PL con variables Artificiales: 
 
 
Método de las M 
 
Se asignan números negativos grandes "M" a los coeficientes de las 
 variables artificiales en la función objetivo. (Maximizar) 
 
Si en la solución básica óptima existen variables artificiales con valor 
diferente de cero entonces el modelo de PL no tiene solución 
 
 
 
 42 
EJEMPLO MÉTODO DE LAS Ms 
 
- Minimización 
- Todo tipo de restricción 
- Optimo en vértice degenerado 
 
Modelo Original: 
 
 
Min 4X1 + X2 
sa. 
 3X1 + X2 = 3 
 4X1 + 3X2 ≥ 6 
 X1 + 2X2 ≤ 3 X1, X2 ≥ 0 
 
 
Modelo en forma estándar: 
 
 
Min 4X1 + X2 + 0S1 + 0S2 + MA1 + MA2 
sa. 
 3X1 + X2 + A1 = 3 
 4X1 + 3X2 - S1 + A2 = 6 
 X1 + 2X2 + S2 = 3 
 
 X1, X2 , S1, S2 , A1 , A2 ≥ 0 
 
 
 
 
 
 
 
 
 
 
 
 43 
Método de las 2 Fases 
 
 Se divide la solución en dos etapas. 
 
 En la primera etapa se resuelve el modelo de PL con f.objetivo (MIN ) 
igual a la suma de todas las variables artificiales. Como resultado de esta 
etapa, se encuentra una solución básica factible (SBF). 
 
 En la segunda etapa se eliminan del modelo las variables artificiales, se 
restaura la f.o. original y se aplica el método simplex con la solución básica 
factible (SBF) encontrada en la primera etapa. 
 
 
NOTAS 
 
Si en la solución básica óptima de la primera etapa existen variables 
artificiales con valor diferente de cero entonces el modelo original de PL no 
tiene solución. 
 
Si en la solución básica óptima de la primera etapa existen variables 
artificiales con valor igual a cero entonces se deben intercambiar por 
variables no basicas que no sean artificiales (aun si el pivote resultase 
negativo). Esto con la intención que en la base no hayan variables artificiales. 
Si aun así, permanecen variables artificiales, entonces representan 
restricciones redundantes y a estas restricciones se las elimina del modelo. 
 44 
EJEMPLO MÉTODO DE LAS DOS FASES 
 
- Minimización 
- Todo tipo de restricción 
- Optimo en vértice degenerado 
 
Modelo Original: 
 
Min 4X1 + X2 
sa. 
 3X1 + X2 = 3 
 4X1 + 3X2 ≥ 6 
 X1 + 2X2 ≤ 3 X1, X2 ≥ 0 
 
Modelo en forma estándar para la primera fase 
 
Min A1 + A2 
sa. 
 3X1 + X2 + A1 = 3 
 4X1 + 3X2 - S1 + A2 = 6 
 X1 + 2X2 + S2 = 3 
 
 X1, X2 , S1, S2 , A1 , A2 ≥ 0 
 
Modelo en forma estándar para la segunda fase 
 
Min 4X1 + X2 + 0S1 + 0S2 
sa. 
 3X1 + X2 = 3 
 4X1 + 3X2 - S1 = 6 
 X1 + 2X2 + S2 = 3 
 
 X1, X2 , S1, S2 , ≥ 0 
 
 45 
EJEMPLO 2 MÉTODO DE LAS DOS FASES 
 
 
Modelo Original: 
 
Min 2X1 + X2 
sa. 
 X1 + 2X2 ≤ 2 
 X2 ≤ 2 
 3X1 + X2 = 6 X1, X2 ≥ 0 
 
 
Modelo en forma estándar para la primera fase 
 
Min 0X1 + 0X2 + 0S3 + 0S4 + 0S5 + A6 
sa. 
 X1 + 2X2 + S3 = 2 
 X2 + S4 = 2 
 3X1 + X2 - S5 + A6 = 6 
 
 X1, X2 , S3, S4, S5 , A6 ≥ 0 
 
 
Modelo en forma estándar para la segunda fase 
 
Min 2X1 + X2 + 0S3 + 0S4 + 0S5 
sa. 
 X1 + 2X2 + S3 = 2 
 X2 + S4 = 2 
 3X1 + X2 - S5 = 6 
 
 X1, X2 , S3, S4, S5 ≥ 0 
 
 
 46 
Primera Fase: 
 
 Cj 0 0 0 
CB base bj X1 X2 S5 
0 S3 2 1 2 0 2 
0 S4 2 0 1 0 
1 A6 6 3 1 -1 2 
 Zj 6 3 1 -1 
 Cj - Zj -3 -1 1 
 
 
 Cj 1 0 0 
CB base bj A6 X2 S5 
0 S3 0 -
1/3 
5/3 
1/3 
0 S4 2 0 1 0 
0 X1 2 
1/3 
1/3 -
1/3 
 Zj 0 0 0 0 
 Cj - Zj 1 0 0 tabla optima ! 
 
 
 
Segunda Fase: 
 
 Cj 1 0 
CB base bj X2 S5 
0 S3 0 
5/3 
1/3 
0 S4 2 1 0 
2 X1 2 
1/3 -
1/3 
 Zj 4 
2/3 -
2/3 
 Cj - Zj 
1/3 
2/3 tabla optima ! 
 
 
 47 
2.2.7. METODO SIMPLEX - PROBLEMAS SIN SOLUCION 
 
 
1. PROBLEMAS NO ACOTADOS 
 
 - La región factible carece de frontera; y 
 - La funcion objetivo puede ser mejorada sin límites 
 
En la tabla simplex se detecta cuando las tasas de sustitucion de la columna 
de la variable que debe entrar a la base tienen valor cero ó negativo. 
Por tanto no podria calcularse la siguiente base. 
 
2. INCONSISTENCIA 
 
Cuando las restricciones identifican areas mutuamente exclusivas. 
No existe entonces un conjunto de valores para las variables de decisión que 
satisfaga simultaneamente todas las restricciones. 
 
En la tabla simplex se detecta cuando existen variables artificiales con valor 
diferente de cero en el óptimo. 
 
 
2.2.8 PROBLEMAS DEGENERADOS 
 
Ocurre cuando un vertice está definido por "demasiadas" restricciones. 
 
En un caso No-degenerado: cada solucion Basica Factible tendría m 
variables basicas positivas diferentes de cero. 
 
En un caso Degenerado existen una ó mas variables en la base con valor 
cero. 
 
La degeneración puede ocurrir en cualquier vertice, no necesariamente en el 
vertice de la solución optima. 
 
La degeneracion no impide que exista solucion óptima. Optima