PASOS DEL METODO SIMPLEX

Vista previa del material en texto

Pasos del Método Simplex.
Material preparado por Pedro Peña Carter
Docente Universitario Pregrado y Postgrados
Tipos de Resolución a través del Método Simplex
Método Simplex Estándar
Método de la M
Método de Dos Fases
Método de Dualidad
Método de Simplex Dual
Método Simplex
Método Simplex Estándar
Paso 1: Para poder aplicar el método simplex estándar (MSE) el problema original al cual llamaremos problema Primal P) debe cumplir con dos requisitos.
	1.1.- El problema original llamado primal P) debe ser un problema de maximización.	 En caso contrario aplicar otro método.
	1.2.- Todas las restricciones del primal (A excepción de las de no negatividad) deben ser de tipo ≤ desde las variables hacia los coeficientes numéricos en cada una de las restricciones del modelo (En algunos casos es necesario algo de algebra).
X1 + 2x2 ≤ 18 Si MSE
X1 + 2x2 ≥ 18 NO MSE
Método Simplex
Método Simplex Estándar
Paso 2: Completado el paso 1, se debe proceder a construir el formato estándar del método (FE) este consiste en dos pasos.
	2.1.- Como el MSE es un método de descenso necesariamente se trabaja 	como 	problema de minimización, por lo que se debe transformar la función 	objetivo original de Maximización a minimización.
	 Max f(x) será equivalente a Min – f(x)
 P) Max 15x1 + 20x2 FE) Min -15x1 - 20x2 
Método Simplex
Método Simplex Estándar
	2.2.- Como el resolución del MSE se hace a través de matrices, será necesario escribir las restricciones como ecuaciones lineales y no como desigualdades, por lo que se deben usar variables de holgura Si por cada restricción i del tipo ≤. Esto permitirá transformar la desigualdad en igualdad compensando en caso que la restricción no este activa con un valor de Si ≥ 0.
X1 + 2x2 ≤ 18 esta restricción se debe transformar a restricción de igualdad
X1 + 2x2 +S1 = 18 (x1=1; x2=1) ; (x1=6; x2=6) 
1 + 2 x 1 +15 =18 
6 + 2x6 + 0 =18	
Método Simplex
Método Simplex Estándar
Paso 3: Una vez construido el FE, se deben transferir los datos numéricos de dicho formato a la tabla inicial del método. La número de filas estará determinado por el número de restricciones del problema, más el vector de costos reducidos que corresponde a los valores numéricos que acompañan a las variables en la FO de FE (Será la última fila) y el número de columnas por el número de variables (Propias del modelo o de holgura) y el recurso disponible.
Método Simplex
Método Simplex Estándar
Paso 4: Proceso de aplicación del MSE.
	4.1.- Primero se debe explicar el concepto de base. Se define la base como 	todas aquellas variables del problema que asumen un valor ≠ 0. La base dice 	relación con el resultado. Una variable será parte de la base si aporta en la 	determinación del valor de la función objetivo. En caso contrario estará 	fuera de la base (No básica).
Notación: Variable básica Xb y una variable no básica Xnb o Xd
Método Simplex
Método Simplex Estándar
Paso 4: Proceso de aplicación del MSE.
	4.2.- Problema estándar: Se define como aquel problema que sólo tiene 	restricciones de recursos. En este caso, al inicio del problema y durante 	todas 	las iteraciones (Cálculos) hasta la tabla final las variables básicas 	siempre asumirán un valor real ≠ 0 y las no básicas serán iguales a cero.
Método Simplex
Método Simplex Estándar
Paso 4: Proceso de aplicación del MSE.
	4.3.- Problema Degenerado: Se define como aquel problema que tiene 	restricciones de recursos y de asociación. En este caso, al inicio del 	problema y durante todas 	las iteraciones (Cálculos) las variables básicas 	podrán asumir un valor igual o distinto de cero según sea el caso. No 	obstante, en la tabla final las variables básicas deben ser distintas de cero.
Método Simplex
Método Simplex Estándar
Paso 5: Conceptos generales
	5.1.- Se puede identificar una variable en la base en la tabla inicial, como la 	columna con un número 1 y las demás celdas con valor cero. De igual forma 	una variable básica, siempre debe tener en la última fila de los costos 	reducidos (CR) un valor cero.
	
Método Simplex
Método Simplex Estándar
Paso 5: Conceptos generales
	5.2.- El número de variables básicas del modelo en la tabla inicial corresponde al 	número de restricciones o variables de holgura del modelo.
	5.3.- El MSE siempre comienza con las variables originales del modelo (xi) con 	valor cero, 	dado que es un valor que siempre estará incluido como parte de las RPF. De igual 	forma las variables de holgura del modelo siempre comenzarán en la base con valor distinto 	de cero si el problema es estándar y con valores distintos o iguales a cero si es problema 	degenerado.
	
Método Simplex
Método Simplex Estándar
Paso 5: Conceptos generales
	5.4.- El método simplex consiste en un proceso de cambios de variables, de tal forma que se 	ingresa una variable que no esta en la base sacando una que si esta presente en la base, 	este cambio es 1 a 1, es decir, 	se puede ingresar en un calculo sólo una variable fuera de la 	base, para dejar salir de igual forma una sola variable de la base.
	5.5.- El número de bases iniciales que está determinado por el número de restricciones no 	puede cambiar, por lo que si al inicio del modelo hay M bases, en cada iteración se debe 	conservar este número sin alteraciones (Claramente no serán las mismas bases iniciales).
	
Método Simplex
Método Simplex Estándar
Paso 6: Aplicación del Método
	6.1.- El método simplex comienza cuando se debe elegir cuales de las variables 	que 	están fuera de la base, ingresarán a ser parte de esta última. Para ello se debe 	mirar la ultima fila de la tabla inicial donde están los costos reducidos. Para que 	una variable ingrese a la base el único requisito es que su CR sea <0. En caso que 	hayan más de una variable con CR<0, se recomienda elegir la más negativa.
	
Método Simplex
Método Simplex Estándar
Paso 6: Aplicación del Método
	6.2.- Una vez elegida la variable entrante se debe dibujar un rectángulo 	vertical sobre dicha variable. Para elegir la variable saliente de las que están en 	la base, se debe dividir el recurso de la última columna con el coeficiente de la 	variable entrante para cada una de las restricciones y se debe elegir el menor 	valor. 	Luego sobre dicha restricción se dibuja un rectángulo horizontal.
	
Método Simplex
Método Simplex Estándar
Paso 6: Aplicación del Método
	6.2.- Este rectángulo horizontal, tiene dos funciones.
	a. Primero indicar cual es la variable saliente, en este caso de todas las 	variables 	que están en la base, la variable cuyo 1 quede encerrado en el rectángulo 	horizontal será la variable saliente. 
	b. Segundo, la fila donde esta el rectángulo horizontal será la fila pivote para 	todos los cálculos de la iteración correspondiente.
	
Método Simplex
Método Simplex Estándar
Paso 6: Aplicación del Método
	6.3.- Una vez determinada la variable entrante y saliente, se debe 	proceder a realizar las iteraciones necesarias (Operaciones Elementales de 	matrices) que permitan transformar la variable entrante en la misma base 	que la variable saliente, es decir, debemos dejar la variable entrante igual 	a la variable saliente para que la base siga teniendo la misma estructura.
Método Simplex
Método Simplex Estándar
Paso 6: Aplicación del Método
	6.4.- El método termina cuando todos los CR de la última fila sean todos ≥ 	a cero. Esto nos indicará que estamos en presencia de la solución óptima 	del problema primal.
Método Simplex
P) Máx		40x + 60y
	S.A.:	 2x + y  70
			x + y  40
			x + 3y  90
			x , y  0
Método Simplex
Primeramente, se deben agregar 3 variables de holgura ( introducimos S1 , S2 , S3)
	FE) Min	 - 40x – 60y
	sa:	 2x + y + S1 = 70
		 x + y + S2 = 40
		 x + 3y + S3 = 90
		 x , y  0 , Si  0, i = 1, 2 y 3.
Método Simplex
Primeramente, se deben agregar 3 variables de holgura ( introducimos S1 , S2 , S3)
	FE) Min	 - 40x – 60ysa:	 2x + y + S1 = 70
		 x + y + S2 = 40
		 x + 3y + S3 = 90
		 x , y  0 , Si  0, i = 1, 2 y 3.
Método Simplex
Entra Y a la base, sale el
esto nos indica que sale S3. En este caso el 3, que es la intersección de fila y columna es el pivote. Se debe multiplicar por 1/3 dicha fila.
Método Simplex
Luego se debe dejar ceros sobre el 1 y bajo el. Por lo cual, se utilizarán operaciones elementales de matrices para lograr el objetivo. En este caso, se debe multiplicar la Fila 3 por -1 y sumar a la Fila 2 y 1 respectivamente, además se debe multiplicar la Fila 3 por 60 y sumar a la fila 4 
Método Simplex
Luego debo continuar porque aún hay un costos reducido negativo.
Entra X a la base, sale el
esto nos indica que sale S2. En este caso el 2/3, que es la intersección de fila y columna es el pivote. Se debe multiplicar por 3/2 dicha fila.
Método Simplex
Luego se debe dejar ceros sobre el 1 y bajo el. Por lo cual, se utilizarán operaciones elementales de matrices para lograr el objetivo. En este caso, se debe multiplicar la Fila 2 por -5/3 y sumar a la Fila 1, luego se debe multiplicar la Fila 2 por -1/3 y sumar a la Fila 3, además se debe multiplicar la Fila 2 por 20 y sumar a la fila 4 
En este caso como todos los costos reducidos son ≥ 0, entonces estamos en presencia de la sulsolución óptima.
PHP SIMPLEX
SE DEBE SELECCIONAR CONTINUAR
SE DEBE SELECCIONAR CONTINUAR
PHP SIMPLEX
SE DEBE SELECCIONAR CONTINUAR
PHP SIMPLEX
SE DEBE SELECCIONAR CONTINUAR
SE DEBE SELECCIONAR CONTINUAR
XYS1S2S3REC
2110070
1101040
1
3
00190
-40-600000
30
3
90
,
1
40
,
1
70
=
þ
ý
ü
î
í
ì
=
Min
ú
û
ù
ê
ë
é
=
ú
û
ù
ê
ë
é
=
0
0
Y
X
X
D
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
90
40
70
3
2
1
S
S
S
X
B
Sheet1
	X	Y	S1	S2	S3	REC				X	Y	S1	S2	S3	REC
	2	1	1	0	0	70		70		-	-	-	-	-	-
	1	1	0	1	0	40		40		-	-	-	-	-	-
	1	3	0	0	1	90		30	0	1/3	1	0	0	1/3	30
	-40	-60	0	0	0	0				-	-	-	-	-	-
	X	Y	S1	S2	S3	REC
	5/3	0	1	0	-1/3	40		24.00
	2/3	0	0	1	-1/3	10		15.00
	1/3	1	0	0	1/3	30		90.00
	-20	0	0	0	20	1,800
	X	Y	S1	S2	S3	REC
	0	0	1	-5/2	1/2	15
	1	0	0	3/2	-1/2	15
	0	1	0	-1/2	1/2	25
	0	0	0	30	10	2,100
Sheet2
	
Sheet3
	
XYS1S2S3REC
-1----
-1----
1/31001/330
--60----
XYS1S2S3REC
5/3010-1/340
2/3001-1/310
1/31001/330
-20000201,800
Sheet1
	X	Y	S1	S2	S3	REC				X	Y	S1	S2	S3	REC
	2	1	1	0	0	70		70		-	1	-	-	-	-
	1	1	0	1	0	40		40		-	1	-	-	-	-
	1	3	0	0	1	90		30	0	1/3	1	0	0	1/3	30
	-40	-60	0	0	0	0				-	-60	-	-	-	-
	X	Y	S1	S2	S3	REC				X	Y	S1	S2	S3	REC
	5/3	0	1	0	-1/3	40		24.00		-	-	-	-	-	-
	2/3	0	0	1	-1/3	10		15.00		1	0	0	3/2	-1/2	15
	1/3	1	0	0	1/3	30		90.00		-	-	-	-	-	-
	-20	0	0	0	20	1,800				-	-	-	-	-	-
	X	Y	S1	S2	S3	REC
	0	0	1	-5/2	1/2	15
	1	0	0	3/2	-1/2	15
	0	1	0	-1/2	1/2	25
	0	0	0	30	10	2,100
Sheet2
	
Sheet3
	
Sheet1
	X	Y	S1	S2	S3	REC				X	Y	S1	S2	S3	REC
	2	1	1	0	0	70		70		-	-	-	-	-	-
	1	1	0	1	0	40		40		-	-	-	-	-	-
	1	3	0	0	1	90		30	0	1/3	1	0	0	1/3	30
	-40	-60	0	0	0	0				-	-	-	-	-	-
	X	Y	S1	S2	S3	REC
	5/3	0	1	0	-1/3	40		24.00
	2/3	0	0	1	-1/3	10		15.00
	1/3	1	0	0	1/3	30		90.00
	-20	0	0	0	20	1,800
	X	Y	S1	S2	S3	REC
	0	0	1	-5/2	1/2	15
	1	0	0	3/2	-1/2	15
	0	1	0	-1/2	1/2	25
	0	0	0	30	10	2,100
Sheet2
	
Sheet3
	
XYS1S2S3REC
5/3010-1/340
2/3
001-1/310
1/31001/330
-20000201,800
15
)
3
/
1
(
30
,
)
3
/
2
(
10
,
)
3
/
5
(
40
=
þ
ý
ü
î
í
ì
=
Min
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
30
10
40
2
1
Y
S
S
X
B
ú
û
ù
ê
ë
é
=
ú
û
ù
ê
ë
é
=
0
0
3
S
X
X
D
Sheet1
	X	Y	S1	S2	S3	REC				X	Y	S1	S2	S3	REC
	2	1	1	0	0	70		70		-	-	-	-	-	-
	1	1	0	1	0	40		40		-	-	-	-	-	-
	1	3	0	0	1	90		30	0	1/3	1	0	0	1/3	30
	-40	-60	0	0	0	0				-	-	-	-	-	-
	X	Y	S1	S2	S3	REC
	5/3	0	1	0	-1/3	40		24.00
	2/3	0	0	1	-1/3	10		15.00
	1/3	1	0	0	1/3	30		90.00
	-20	0	0	0	20	1,800
	X	Y	S1	S2	S3	REC
	0	0	1	-5/2	1/2	15
	1	0	0	3/2	-1/2	15
	0	1	0	-1/2	1/2	25
	0	0	0	30	10	2,100
Sheet2
	
Sheet3
	
XYS1S2S3REC
5/3-----
1
003/2-1/215
1/3-----
-20-----
XYS1S2S3REC
00
1
-5/21/215
1
003/2-1/2
15
0
1
0-1/21/2
25
0003010
2,100
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
25
15
15
1
Y
X
S
X
B
ú
û
ù
ê
ë
é
=
ú
û
ù
ê
ë
é
=
0
0
3
2
S
S
X
D
Sheet1
	X	Y	S1	S2	S3	REC				X	Y	S1	S2	S3	REC
	2	1	1	0	0	70		70		-	1	-	-	-	-
	1	1	0	1	0	40		40		-	1	-	-	-	-
	1	3	0	0	1	90		30	0	1/3	1	0	0	1/3	30
	-40	-60	0	0	0	0				-	-60	-	-	-	-
	X	Y	S1	S2	S3	REC				X	Y	S1	S2	S3	REC
	5/3	0	1	0	-1/3	40		24.00		5/3	-	-	-	-	-
	2/3	0	0	1	-1/3	10		15.00		1	0	0	3/2	-1/2	15
	1/3	1	0	0	1/3	30		90.00		1/3	-	-	-	-	-
	-20	0	0	0	20	1,800				-20	-	-	-	-	-
	X	Y	S1	S2	S3	REC
	0	0	1	-5/2	1/2	15
	1	0	0	3/2	-1/2	15
	0	1	0	-1/2	1/2	25
	0	0	0	30	10	2,100
Sheet2
	
Sheet3
	
Sheet1
	X	Y	S1	S2	S3	REC				X	Y	S1	S2	S3	REC
	2	1	1	0	0	70		70		-	1	-	-	-	-
	1	1	0	1	0	40		40		-	1	-	-	-	-
	1	3	0	0	1	90		30	0	1/3	1	0	0	1/3	30
	-40	-60	0	0	0	0				-	-60	-	-	-	-
	X	Y	S1	S2	S3	REC				X	Y	S1	S2	S3	REC
	5/3	0	1	0	-1/3	40		24.00		5/3	-	-	-	-	-
	2/3	0	0	1	-1/3	10		15.00		1	0	0	3/2	-1/2	15
	1/3	1	0	0	1/3	30		90.00		1/3	-	-	-	-	-
	-20	0	0	0	20	1,800				-20	-	-	-	-	-
	X	Y	S1	S2	S3	REC
	0	0	1	-5/2	1/2	15
	1	0	0	3/2	-1/2	15
	0	1	0	-1/2	1/2	25
	0	0	0	30	10	2,100
Sheet2
	
Sheet3