MÓDULO 2: El Método Simplex
MÓDULO 2:
MÉTODO SIMPLEX
1
MÓDULO 2: El Método Simplex
2. 1 INTRODUCCION:
El método simplex corresponde a una solución algebraica, desarrollada en 1947 por
George B. Dantzing (1914-2005)
Su algoritmo de solución permite solucionar PPL de más de dos variables a
diferencia del método gráfico, sin embargo su enfoque geométrico corresponde al de
una solución gráfica.
La solución óptima obtenida por el método simplex, permite además de conocer el
valor óptimo de las variables, hacer interpretaciones importantes en un análisis de
sensibilidad.
Su algoritmo de solución se realiza por medio de iteraciones, que nos lleva hasta la
solución óptima.
2
MÓDULO 2: El Método Simplex
2.2 Forma Estándar para un PPL:
Recordemos que:
1. PPL puede ser del tipo Maximizar ó Minimizar.
2. Sus restricciones pueden ser del tipo ; = ó
3. Sus variables de decisión deben ser no negativas.
Para utilizar el método simplex necesitamos una notación común que llamaremos
forma o formato estándar, la cual tiene las siguientes ventajas:
1. Todas las restricciones son ecuaciones con segundo miembro no negativo.
2. Todas las variables son no negativas.
3. El problema puede ser de maximizar o minimizar.
3
MÓDULO 2: El Método Simplex
2.2 Forma Estándar para un PPL:
Restricciones:
Si la restricción es del tipo sumamos una variable de holgura:
i.e.: X1 + 2X2 6 X1 + 2X2 + S1 = 6 (S1 0)
Si la restricción es del tipo restamos una variable de exceso:
i.e.: 3x1 + 2X2 – 3X3 5 3x1 + 2X2 – 3X3 – S2 = 5 (S2 0)
Si el segundo miembro de la desigualdad es negativo, multiplicamos por -1 para
dejarlo positivo (modificando el sentido de la desigualdad)
i.e: 2X1 – X2 -5 -2X1 + X2 5
4
MÓDULO 2: El Método Simplex
2.3 Algoritmo del Método Simplex:
Al igual que en la solución gráfica, la solución óptima, está siempre asociada a un
punto extremo de la RSF.
A pesar de carecer de una representación gráfica, el método simplex emplea un
proceso iterativo que parte de un punto extremo factible, normalmente el origen, y se
desplaza sistemáticamente de un punto extremo factible a otro, hasta llegar al punto
óptimo.
El algoritmo difiere en su etapa inicial (solución básica inicial) dependiendo del tipo
de problema formulado. El caso más sencillo y directo corresponde al de maximizar,
sujeto a restricciones del tipo , por lo tanto utilizaremos el caso Reddy Mikks
Company para desarrollar el método.
5
MÓDULO 2: El Método Simplex
Modelo matemático
(Caso Reddy Mikks Company)
Representación solución gráfica
F.O. : Max I = 3Xe + 2Xi (M$/día) Xi
S.A.:
Xe + 2Xi 6 (ton/día) 1 E 4 D
2Xe + Xi 8 (ton/día) 2
3
1
C
-Xe + Xi 1 (ton/día) 3
F RSF
Xi 2 (ton/día) 4 2
Xe, Xi 0 Xe
A B
6
MÓDULO 2: El Método Simplex
2.4 Solución Simplex Caso Reddy Mikks Co.
Modelo matemático Forma Estándar
Max I= 3Xe + 2Xi Max I =3Xe + 2Xi +0S1+0S2+0S3+0S4
S.A.: S.A.:
Xe + 2Xi 6 Xe + 2Xi +S1 =6
2Xe + Xi 8 2Xe + Xi +S2 =8
-Xe + Xi 1 -Xe + Xi +S3 =1
Xi 2 Xi +S4 =2
Xe, Xi 0 Xe, Xi,S1,S2,S3,S4 0
7
MÓDULO 2: El Método Simplex
2.4 Solución Simplex Caso Reddy Mikks Co.
Forma Estándar
El modelo consta de 4 ecuaciones
(restricciones) y 6 incógnitas . En
Max I - 3Xe - 2Xi - 0S1 -0S2 -0S3 -0S4 =0 general hablaremos de m ecuaciones
y n incógnitas (m<n).
S.A.: Para determinar los puntos
extremos, geométricamente
Xe + 2Xi +S1 =6 corresponde a la intersección de los
2Xe + Xi +S2 =8 planos frontera. Como la forma
estándar tiene más incógnitas que
-Xe + Xi +S3 =1 ecuaciones, los puntos extremos se
identifican haciendo (n-m) variables
Xi +S4 =2 iguales a cero, y después resolver el
Xe, Xi,S1,S2,S3,S4 0 resto de incógnitas.
Las soluciones únicas resultantes de
hacer (n-m) variables igual a cero se
denominan soluciones básicas.
8
MÓDULO 2: El Método Simplex
2.4 Solución Simplex Caso Reddy Mikks Co.
Xi Si una solución básica satisface las
restricciones de no negatividad, se le
llama, solución básica factible. Las
E 4 D variables que se hacen igual a cero
1 se llaman variables no básicas, las
3
C
restantes se conocen como
variables básicas.
F RSF
2
Pto. A: No básicas: Xe,Xi
Xe Básicas: S1,S2,S3,S4
A B
Pto B: No básicas: S2, Xi
Básicas: S1,Xe,S3,S4
Al pasar del pto. A al pto. B, hacemos que la variable no básica Xe, pase a ser una
variable básica, y a su vez la variable básica S2 pasa a ser una variable no básica.
9
MÓDULO 2: El Método Simplex
2.4 Solución Simplex Caso Reddy Mikks Co.
Algoritmo:
Paso 0: Determinar solución factible básica inicial.
Paso 1: Seleccionar una variable que entra (pasa de no básica a básica),
dentro de las variable con valor cero, que al incrementar su valor, mejoran la
F.O.(para el caso de max). Si no existe, detenerse ya que es la solución
óptima.
Paso 2: Seleccionar una variable que sale (pasa de básica a no básica).
Paso 3: Determinar la nueva solución básica.
La aplicación del algoritmo suele desarrollarse en un Tabla Simplex, que
representa en forma matricial la forma estándar del problema.
10
MÓDULO 2: El Método Simplex
2.4 Solución Simplex Caso Reddy Mikks Co.
Forma Estándar
Max I - 3Xe - 2Xi - 0S1 -0S2 -0S3 -0S4 =0
S.A.: Llevamos el formato
estándar a una matriz o
Xe + 2Xi +S1 =6 Tabla Simplex, en orden
con las variables
2Xe + Xi +S2 =8 (columnas) y restricciones
(filas)
-Xe + Xi +S3 =1
Xi +S4 =2
Xe, Xi,S1,S2,S3,S4 0
11
MÓDULO 2: El Método Simplex
2.4 Solución Simplex Caso Reddy Mikks Co.
TABLA SIMPLEX
Iteración 0
(Solución factible básica inicial)
Paso 0:
Básica I Xe Xi S1 S2 S3 S4 Sol Razón Solución básica inicial
I 1 -3 -2 0 0 0 0 0 Paso 1:
S1 0 1 2 1 0 0 0 6 6/1=6 Condición de optimidad
S2 0 2 1 0 1 0 0 8 8/2=4 Paso 2:
Condición de factibilidad
S3 0 -1 1 0 0 1 0 1
Paso 3:
S4 0 0 1 0 0 0 1 2 Calcular nueva solución
Calculo tipo 1: Nueva ecuación pivote
Calculo tipo 2: Nuevas ecuaciones restantes
12
MÓDULO 2: El Método Simplex
2.4 Solución Simplex Caso Reddy Mikks Co.
TABLA SIMPLEX
Iteración 1
Básica I Xe Xi S1 S2 S3 S4 Sol Razón
I 1 0 -1/2 0 3/2 0 0 12
Paso 1:
S1 0 0 3/2 1 -1/2 0 0 2 4/3 Condición de optimidad
Xe 0 1 1/2 0 1/2 0 0 4 8 Paso 2:
Condición de factibilidad
S3 0 0 3/2 0 1/2 1 0 5 10/3
Paso 3:
S4 0 0 1 0 0 0 1 2 2 Calcular nueva solución
Calculo tipo 1: Nueva ecuación pivote
Calculo tipo 2: Nuevas ecuaciones restantes
13
MÓDULO 2: El Método Simplex
2.4 Solución Simplex Caso Reddy Mikks Co.
TABLA SIMPLEX
Iteración 2
Básica I Xe Xi S1 S2 S3 S4 Sol
1 0 0 1/3 8/6 0 0 38/3 Paso 1:
I
Condición de optimidad:
Xi 0 0 1 2/3 -1/3 0 0 4/3 No existe una variable no
básica que mejore la
Xe 0 1 0 -1/3 4/6 0 0 10/3
solución. Por lo tanto la
S3 0 0 0 -1 1 1 0 3 solución es óptima.
S4 0 0 0 -2/3 1/3 0 1 2/3
Xe= 10/3 (ton)
Xi = 4/3 (ton)
Max I = 38/3 ($M/día)
14
MÓDULO 2: El Método Simplex
2.5 Caso Solución inicial artificial:
Cuando el PPL incluye restricciones del tipo “=“ ó “” , la solución básica
inicial no es tan obvia, ya que hacer cero las variables de decisión no entrega
una solución factible.
Para estos casos, que pueden ser los más generales, se necesita crear una
solución inicial artificial, que consiste en agregar ciertas variables artificiales a
las restricciones que no son de holgura (“=“ ó “” )
Analizaremos el procedimiento con un nuevo ejemplo.
15
MÓDULO 2: El Método Simplex
2.5 Caso Solución inicial artificial:
Modelo matemático Forma estándar
F.O. : Min C = 4X1 + X2 ($/día) F.O. : Min C = 4X1 + X2 ($/día)
S.A.: S.A.:
3X1 + X2 = 3 1 3X1 + X2 = 3
4X1 + 3X2 6 2 4X1 + 3X2 - X3 = 6
X1 + 2X2 4 3 X1 + 2X2 + X4 = 4
X1, X2 0 X1, X2,X3,X4 0
En el formato estándar se le deben
agregar variables artificiales a las
restricciones de exceso y de
igualdad 16
MÓDULO 2: El Método Simplex
2.6 Técnica M (método de penalización):
Forma Estandar c/var. artificiales
En la función objetivo
F.O. : Min C = 4X1 + X2 + MR1 + MR2 ($/día) debo penalizar las
variables artificiales
S.A.: agregando un valor M
(coeficiente muy alto),
3X1 + X2 + R1 = 3 con signo positivo (+)
en el caso de Min y
4X1 + 3X2 - X3 + R2 = 6 con signo negativo (-)
en el caso de Max
X1 + 2X2 + X4 = 4
X1, X2,X3,X4 0 Para darle solución, reemplazo el
valor alternativo de R1 y R2 en la
F.O., obtenida de sus respectivas
restricciones.
17
MÓDULO 2: El Método Simplex
2.6 Técnica M (método de penalización):
Reemplazando en
la Función Objetivo
R1 = 3 – 3X1 – X2
R2 = 6 – 4X1 – 3X2 + X3 C=4X1+X2+M(3-3X1-X2)+M(6-4X1-3X2+X3)
Factorizando por cada C= (4-7M)X1 + (1-4M)X2 + MX3 + 9M
variable
Los coeficientes de las
variables X1 y X2 son C= - (7M-4)X1 - (4M-1)X2 + MX3 + 9M
negativos, por lo tanto Si nos damos cuenta los coeficientes
es mejor factorizarlos de las variables X1 y X2 son los que
por -1 para distinguir mejoran el objetivo de minimizar la
mejor su signo. función C.
Ahora lo llevamos al formato estándar
de la tabla simplex 18
MÓDULO 2: El Método Simplex
2.6 Técnica M (método de penalización):
Tabla Simplex
El algoritmo de
C + (7M-4)X1 + (4M-1)X2 –MX3 = 9M solución se aplica de
la misma forma vista
S.A.: anteriormente,
pasando por los
3X1 + X2 + R1 = 3
pasos 0,1,2,y3
4X1 + 3X2 - X3 + R2 = 6
X1 + 2X2 + X4 = 4
X1, X2,X3,X4,R1,R2 0
19
MÓDULO 2: El Método Simplex
2.6 Técnica M (método de penalización):
TABLA SIMPLEX
Iteración 0
(Solución factible básica inicial)
Paso 0:
Básica C X1 X2 X3 X4 R1 R2 Sol Razón Tenemos 6 var. Y 3
restricciones, por lo
C 1 7M-4 4M-1 -M 0 0 0 9M tanto necesitamos
hacer 3 var. (6-3)
R1 0 3 1 0 0 1 0 3 1 igual a cero (no
básicas)
R2 0 4 3 -1 0 0 1 6 6/4
X1=0
4 X2=0
X4 0 1 2 0 1 0 0 4
X3=0
Paso 1: Paso 2: Paso 3:
Condición de optimidad Condición de factibilidad Calcular nueva solución
20
MÓDULO 2: El Método Simplex
2.6 Técnica M (método de penalización):
TABLA SIMPLEX
Iteración 1
Básica C X1 X2 X3 X4 R1 R2 Sol Razón
C 1 0 (1+5M)/3 -M 0 (4-7M)/3 0 4+2M
X1 0 1 1/3 0 0 1/3 0 1 3
R2 0 0 5/3 -1 0 -4/3 1 2 6/5
X4 0 0 5/3 0 1 -1/3 0 3 9/5
Paso 1: Paso 2: Paso 3:
Condición de optimidad Condición de factibilidad Calcular nueva solución
21
MÓDULO 2: El Método Simplex
2.6 Técnica M (método de penalización):
TABLA SIMPLEX
Iteración 2
Básica C X1 X2 X3 X4 R1 R2 Sol Razón
C 1 0 0 1/5 0 8/5-M -1/5-M 18/5
X1 0 1 0 1/5 0 3/5 -1/5 3/5 3
X2 0 0 1 -3/5 0 -4/5 3/5 6/5
X4 0 0 0 1 1 1 -1 1 1
Paso 1: Paso 2: Paso 3:
Condición de optimidad Condición de factibilidad Calcular nueva solución
22
MÓDULO 2: El Método Simplex
2.6 Técnica M (método de penalización):
TABLA SIMPLEX
Iteración 3: SOLUCION OPTIMA
Básica C X1 X2 X3 X4 R1 R2 Sol
C 1 0 0 0 -1/5 7/5-M -M 17/5
X1 0 1 0 0 -1/5 2/5 0 2/5
X2 0 0 1 0 3/5 -1/5 0 9/5
X3 0 0 0 1 1 1 -1 1
La iteración 3 es óptima porque no X1= 2/5
existen coeficientes en la función objetivo Min C = 17/5
X2 = 9/5
que la mejoren, ya que son todos
negativos. 23
