07/06/2017
INVESTIGACIÓN OPERACIONES
SOLUCION DE MODELOS DE PROGRAMACION LINEAL
METODO SIMPLEX
Mg. Paul Linares Ortega
Ingeniero Industrial
MÉTODO SIMPLEX
Para resolver en la práctica problemas de más de dos dimensiones, se emplea el
llamado Método Simplex, basada en el álgebra matricial y en el empleo de espacios
de “n” dimensiones.
El Método Simplex es un procedimiento o conjunto de restricciones con el cual se
examinan los puntos en las esquinas de una manera metódica hasta conseguir la
mejor solución: la mayor utilidad ó el menor costo.
En teoría, el método Simplex puede resolver un problema que consiste en
cualquier número de variable y restricciones; aunque en el caso de problemas que
tienen más de tres variables o restricciones, es mejor que los cálculos sean hechos
en el computador a través de un software (WINQSB, SOLVER, LINDO, TORA, etc.).
Sin embargo, para poder comprender totalmente la programación lineal, construir
las ecuaciones para desarrollar el programa y poder integrar sus resultados, es
necesario seguir manualmente el Método Simplex.
1
07/06/2017
Los pasos que comprende el Método simplex son:
1.- Formular el problema, planteado la función objetivo, las restricciones y las
condiciones de no negatividad.
2.- Introducir variables de holgura (S) ó variables artificiales (A) en las restricciones:
- Si la restricción es “menor o igual que” ( ≤ ) genera la inclusión de una variable
de holgura (S) al lado izquierdo de la desigualdad, para convertirla en ecuación.
- Si la restricción es “igual que” ( = ) genera la inclusión de una variable artificial
(A) al lado izquierdo.
- Si la restricción es “mayor o igual que” ( ≥ ) se debe restar una variable de
holgura (S) y sumar una variable artificial (A) al lado izquierdo de la desigualdad,
para convertirla en ecuación.
Variables de Holgura (S):
Una variable de holgura representa la cantidad no utilizando u ociosa de cada recurso.
Se introducen las variables de holgura necesaria en cada restricción; ya que estas
convierten dichas restricciones en igualdades.
La función objetivo también refleja la suma de las variables de holgura; pero como esta
no genera utilidad su coeficiente es “0”.
Variables Artificiales (A):
Una variable artificial es una variable que no tiene significado físico en términos de un
problema de programación lineal, permitiendo crear una solución factible básica para
iniciar el algoritmo simplex.
Cuando se tienen variables artificiales, su solución puede ser por el Método de la Gran
M o por el Método de las dos Fases (Este método elimina el uso de la M y resuelve el
problema en dos fases)
2
07/06/2017
3. Elaborar la tabla inicial simplex donde todos los coeficientes numéricos de la
función objetivo y de las restricciones son ubicados en la tabla.
Contribución de la variable j
Variables Reales
Variables Artificiales
Variables de Holgura
Mezcla
Solución
Cj X1 X2 S1 S2 A1 A2 Disponible
Zj
Zj - Cj
Costo de introducir la variable j
Contribución neta de la variable j
4.- Se ingresan los coeficientes y las cantidades de las función objetivo y de las
restricciones a la tabla inicial simplex y se calcula el costo de introducir la variable (Zj) y
la contribución neta de la variable (Zj-Cj).
5.- Partiendo del calculo de la contribución neta de la variable (Zj-Cj) se escoge entre las
restricciones un punto de apoyo (Pivote) para lo cual se determina una columna pivote,
eligiendo entre la columna de variables a aquella que tenga el menor valor si se trata de
maximización y el mayor valor si se trata de minimización.
6.- Se determina una fila pivote, dividiendo la columna disponible entre la columna
pivote, tomando como referencia el menor valor positivo; la intercepción de ambas es el
punto pivote. El punto Pivote por su ubicación indica que variable de holgura sale y que
variables real ingresa.
7.- El Pivote, debe ser 1; si no es así tendrá que operarse ya sea multiplicando o
dividiendo con la finalidad de obtener 1. Una vez que el punto Pivote es la unidad, se
convierte en ceros todos los elementos de su columna.
3
07/06/2017
8.- El método simplex es un método iterativo (repetitivo), han de repetirse los pasos
hasta encontrar la solución óptima, es decir cuando se cumpla la condición:
Para la maximización que Zj-Cj sea ceros o positivos
Para la minimización que Zj-Cj sea ceros o negativos
Método Simplex para
Maximización
4
07/06/2017
1.- Resolver
Zmax = 40X1 + 60X2 + 50X3
s.a. 10X1 + 4X2 + 2X3 ≤ 950
2X1 + 2X2 ≤ 410
X1 + 2X3 ≤ 610
X1, X2, X3 ≥ 0
Función Objetivo:
Zmax= 40X1 + 60X2 + 50X3 + 0S1 + 0S2 + 0S3
Restricciones:
10X1 + 4X2 + 2X3 + S1 = 950
2X1 + 2X2 + 0X3 + S2 = 410
X1 + 0X2 + 2X3 + S3 = 610
Condición de no negatividad:
X1, X2, X3, S1, S2, S3 ≥ 0
5
07/06/2017
Tabla inicial simplex
Cj Variable 40 60 50 0 0 0
solución X1 X2 X3 S1 S2 S3 Disponible
0 S1 10 4 2 1 0 0 950
0 S2 2 2 0 0 1 0 410
0 S3 1 0 2 0 0 1 610
Zj 0 0 0 0 0 0 0
Zj - Cj -40 -60 -50 0 0 0
PIVOTE
Fila PIVOTE
El PIVOTE debe ser 1 e indica la variable
Menor valor positivo
que sale y la variable que ingresa.
Tabla 1
Cj Variable 40 60 50 0 0 0
Solución X1 X2 X3 S1 S2 S3 Disponible
0 S1 10 4 2 1 0 0 950 237.5
0 S2 2 2 0 0 1 0 410 205
0 S3 1 0 2 0 0 1 610 Error
Zj 0 0 0 0 0 0 0
Zj - Cj - 40 -60 -50 0 0 0
Columna PIVOTE
Menor valor
6
07/06/2017
Una vez que el punto Pivote es 1 se PIVOTE Fila PIVOTE
convierte en ceros todos los elementos
Menor valor positivo
de su columna.
Tabla 2
Cj Variable 40 60 50 0 0 0
Solución X1 X2 X3 S1 S2 S3 Disponible
0 S1 6 0 2 1 -2 0 130 65
60 X2 1 1 0 0 1/2 0 205 Error
0 S3 1 0 2 0 0 1 610 305
Zj 60 60 0 0 30 0 12300
Zj - Cj 20 0 -50 0 30 0
¿Son todos los Zj-Cj ceros o positivos?
No se cumple la condición, se debe
repetir el proceso.
Columna PIVOTE
Menor valor
Una vez que el punto Pivote es 1 se PIVOTE Fila PIVOTE
convierte en ceros todos los elementos Menor valor positivo
de su columna.
Tabla 3
Cj Variable 40 60 50 0 0 0
Solución X1 X2 X3 S1 S2 S3 Disponible
50 X3 3 0 1 1/2 -1 0 65 -65
60 X2 1 1 0 0 1/2 0 205 410
0 S3 -5 0 0 -1 2 1 480 240
Zj 210 60 50 25 -20 0 15550
Zj - Cj 170 0 0 25 -20 0
¿Son todos los Zj-Cj ceros o positivos?
No se cumple la condición, se debe
repetir el proceso.
Columna PIVOTE
Menor valor
7
07/06/2017
Una vez que el punto Pivote es 1 se
convierte en ceros todos los elementos
de su columna.
Tabla 4
Cj Variable 40 60 50 0 0 0
Solución X1 X2 X3 S1 S2 S3 Disponible
50 X3 1/2 0 1 0 0 1/2 305
60 X2 9/4 1 0 1/4 0 -1/4 85
0 S2 -5/2 0 0 -1/2 1 1/2 240
Zj 160 60 50 15 0 10 20350
Zj - Cj 120 0 0 15 0 10
¿Son todos los Zj-Cj ceros o positivos?
Si, se cumple la condición, se ha X1 = 0
llegado a la solución óptima.
X2 = 85
X3= 305
Zmax = 20 350
Método Simplex para
Minimización
8
07/06/2017
1.- Resolver:
Zmin = 6X1 + 8X2 + 16X3
s.a. 2X1 + X2 ≥5
X2 + 2X3 ≥ 4
X1, X2, X3 ≥ 0
MÉTODO DE LA GRAN M
Función Objetivo:
Zmin = 6X1 + 8X2 + 16X3 + 0S1 + 0S2 + MA1 + MA2
Restricciones:
2X1 + X2 + 0X3 - S1 + A1 =5
0X1 + X2 + 2X3 - S2 + A2 = 4
Si la restricción tiene signo:
Condición de no negatividad: ≤ “menor o igual que” sumar una variable de holgura (S)
= “igual que” sumar una variable de artificial (A)
≥ “mayor o igual que” restar una variable de holgura (S)
X1, X2, X3, S1, S2, A1, A2 ≥ 0 y sumar una variable de artificial (A)
Variable Artificial
Cuando se Maximiza se le resta una M
Cuando se Minimiza se le suma una M
9
07/06/2017
Tabla inicial simplex
Cj Variable 6 8 16 0 0 M M
Solución Cantidad
X1 X2 X3 S1 S2 A1 A2
M A1 2 1 0 -1 0 1 0 5
M A2 0 1 2 0 -1 0 1 4
Zj 2M 2M 2M -M -M M M 9M
Zj - Cj 2M-6 2M-8 2M-16 -M -M 0 0
Ingresamos todos los coeficientes de la función objetivo y de las restricciones,
calculando Zj y Zj - Cj
3.- Encontramos el PIVOTE 2.- Determinamos Fila PIVOTE
El PIVOTE debe ser 1 e indica la variable (Menor valor positivo)
que sale y la variable que ingresa.
Tabla 1
Cj Variable 6 8 16 0 0 M M
Solución Cantidad
X1 X2 X3 S1 S2 A1 A2
M A1 2 1 0 -1 0 1 0 5 2.5
M A2 0 1 2 0 -1 0 1 4 Error
Zj 2M 2M 2M -M -M M M 9M
Zj - Cj 2M-6 2M-8 2M-16 -M -M 0 0
4.- Calculamos Zj y ZJ-Cj Zj- Cj se expresan como una función
lineal:
aM ± b
1.- Determinamos la Columna PIVOTE donde:
(Mayor valor para minimización) a= factor multiplicativo
Existe empate en los factores multiplicativos. M= valor numérico (muy grande)
Se recurre al factor aditivo b= factor aditivo
1.- Siempre que M está presente, se
usa el mayor factor multiplicativo.
2.-Si existe empate entre los factores
multiplicativos, se recurre al factor
aditivo:
Menor valor para Maximización
Mayor valor para Minimización
10
07/06/2017
Una vez que el punto Pivote es 1 se
convierte en ceros todos los elementos Fila PIVOTE
PIVOTE
de su columna. Menor valor positivo
Tabla 2
Cj Variable 6 8 16 0 0 M
Solución X1 X2 X3 S1 S2 A2 Cantidad
6 X1 1 1/2 0 -1/2 0 0 2.5 Error
M A2 0 1 2 0 -1 1 4 2
Zj 6 M+3 2M -3 -M M 4M+15
Zj - Cj 0 M-5 2M-16 -3 -M 0
¿Son todos los Zj-Cj ceros o negativos?
No se cumple la condición, se debe
repetir el proceso.
Columna PIVOTE
Siempre que M está presente,
se usa el mayor factor multiplicativo.
Una vez que el punto Pivote es 1 se
Fila PIVOTE
convierte en ceros todos los elementos
Menor valor positivo
de su columna.
Tabla 3 PIVOTE
Cj Variable 6 8 16 0 0
Solución Cantidad
X1 X2 X3 S1 S2
6 X1 1 1/2 0 -1/2 0 2.5 5
16 X3 0 1/2 1 0 -1/2 2 1
Zj 6 11 16 -3 -8 47
Zj - Cj 0 3 0 -3 -8
¿Son todos los Zj-Cj ceros o negativos?
No se cumple la condición, se debe
repetir el proceso.
Columna PIVOTE
Mayor valor
11
07/06/2017
Una vez que el punto Pivote es 1 se
convierte en ceros todos los elementos
de su columna.
Tabla 4
Cj Variable 6 8 16 0 0
Solución X1 X2 X3 S1 S2 Cantidad
6 X1 1 0 -1 -1/2 1/2 0.5
8 X2 0 1 2 0 -1 4
Zj 6 8 10 -3 -5 35
Zj - Cj 0 0 -6 -3 -5
¿Son todos los Zj-Cj ceros o negativos?
Si, se cumple la condición, se ha X1= 1/2
llegado a la solución óptima.
X2= 4
X3= 0
Zmin = 35
2.- Resolver:
Zmin = 75X1 + 50X2 + 30X3
s.a. 4X1 + 3X2 + X3 ≥ 5
2X1 + 3X2 + X3 ≥ 20
X1 + X2 + 5X3 ≤ 50
X1, X2, X3 ≥ 0
X1= 0
X2= 6.66
X3= 0
Zmin = 333.33
12
07/06/2017
Casos Especiales
3.- Resolver:
Zmin = 0.4X1 + 0.5X2
s.a. 0.3X1 + 0.1X2 ≤ 2.7
0.5X1 + 0.5X2 = 6
0.6X1 + 0.4X2 ≥ 6
X1, X2 ≥ 0
Función Objetivo:
Zmin= 0.4X1 + 0.5X2 + 0S1 + 0S2 + MA1 + MA2
Restricciones:
0.3X1 + 0.1 X2 + S1 = 2.7
0.5X1 + 0.5 X2 + A1 = 6
0.6X1 + 0.4 X2 - S2 + A2 = 6
Condición de no negatividad:
X1, X 2, S1, S2, A1, A2 ≥ 0
Variable Artificial
Cuando se Maximiza se le resta una M
Cuando se Minimiza se le suma una M
13
07/06/2017
Tabla inicial simplex
Cj Mezcla 0.4 0.5 0 0 M M
Solución Cantidad
X1 X2 S1 S2 A1 A2
0 S1 0.3 0.1 1 0 0 0 2.7
M A1 0.5 0.5 0 0 1 0 6
M A2 0.6 0.4 0 -1 0 1 6
Zj 1.1M 0.9M 0 -M M M 12M
Zj – C j 1.1M-6 0.9M-8 0 -M 0 0
Siempre que M está presente,
se usa el mayor factor multiplicativo.
X1= 7.5
X2= 4.5
S3= 0.3
Zmin = 5.25
4.- Resolver:
Zmax = 100X1 + 90X2
s.a. 6X1 + 4X2 ≥ 24
20X1 + 8X2 ≤ 160
3X1 + 5X2 ≥ 15
X2 ≤ 5
X1, X2 ≥ 0
14
07/06/2017
Función Objetivo:
Zmax= 100X1 + 90X2 + 0S1 + 0S2 + 0S3 + S4 - MA1 - MA2
Restricciones:
6X1 + 4 X2 - S1 + A1 = 24
20X1 + 8X2 + S2 = 160
3X1 + 5X2 - S3 + A2 = 15
X2 + S4 = 5
Condición de no negatividad:
X1, X2, S1, S2, S3, S4, A1, A2 ≥ 0 Variable Artificial
Cuando se Maximiza se le resta una M
Cuando se Minimiza se le suma una M
Tabla inicial simplex
Cj 100 90 0 0 0 0 -M -M
Variable Cantidad
Solución X1 X2 S1 S2 S3 S4 A1 A2
-M A1 6 4 -1 0 0 0 1 0 24
0 S2 20 8 0 1 0 0 0 0 160
-M A2 3 5 0 0 -1 0 0 1 15
0 S4 0 1 0 0 0 1 0 0 5
Zj -9M -9M M 0 M 0 -M -M -39M
Zj – Cj -9M-100 -9M-90 M 0 M 0 0 0
X1= 6
Existe empate en los factores multiplicativos.
Se recurre al factor aditivo
X2= 5
(Menor valor para maximización) S1=32
S3=28
Zmax = 1,050
15
