Paso 1.
Convertir las desigualdades en igualdades al sumarles una variable de
holgura hi . Esta variable representa la cantidad que le falta a la desigualdad para
ser igualdad.
Paso 2. Escribir la función objetivo como una igualdad a cero sumando las
variables de holgura
Paso 3. Formar la tabla símplex o tabla inicial.
Paso 4. Vericamos si todos los coecientes asociados al renglón de Z son mayores
o iguales a cero. Si es así, entonces la solución en la tabla es la óptima y el proceso
termina. Si no es así, se continúa.
Paso 5. De los coecientes del renglón Z se toma el que tenga el mayor valor
negativo (número menor) y se selecciona toda la columna. La variable de esta
columna es la que entra al sistema (pasa a ser básica).
Paso 6. Se divide el término de la columna “Solución” entre el elemento
correspondiente de la columna seleccionada en el punto anterior, y de los
resultados de la división se selecciona el menor valor positivo y todo el renglón
asociado a este valor. Ésta es la variable que sale
Paso 7. La celda que se encuentra en la intersección de la columna con el renglón
seleccionado contiene un elemento al que, por medio de operaciones elementales
entre renglones, se convierte en elemento pivote y los demás elementos de
su columna, en ceros; con esto se obtiene una nueva columna de la matriz
identidad.
Paso 8. Se repite el proceso desde el Paso 4 operando sobre matrices hasta obtener todos los
coecientes del renglón Z, con valores mayores o iguales a cero.
En el siguiente ejemplo se presenta la aplicación del algoritmo del método
símplex.
problema
Paso1 x1+x2+h1+0h2+0h3 =200
X1+4x2+h2=320
10X1+20x2+h3=2200
Paso 2.- igualar a cero la Z
z-40x1-60x2+0h1+0h2+0h3=0
paso 3.-
v.basica z X1 X2 H1 H2 H3 sol
s
z 1 -40 -60 0 0 0 0
H1 0 1 1 1 0 0 200
H2 0 1 4 0 1 0 320
H3 0 10 20 0 0 1 2200
Paso 4.- los coeficientes no son mayores que cero si
termina, no continua
Paso 5.- variable entrada (mayor negativo)
v.basica z X1 X2 H1 H2 H3 sol
s
z 1 -40 -60 0 0 0 0
H1 0 1 1 1 0 0 200
H2 0 1 4 0 1 0 320
H3 0 10 20 0 0 1 2200
Paso 6.- identificar la variable de salida diviendo la columna
solución entre la columna de entrada
v.basicas z X1 X2 H1 H2 H3 sol Div
z 1 -40 -60 0 0 0 0 Menor positivo
H1 0 1 1 1 0 0 200 200/1=200
H2 0 1 4 0 1 0 320 320/4=80
H3 0 10 20 0 0 1 2200 2200/20=110
Paso 7.-nueva matriz con pivote
v.basica z X1 X2 H1 H2 H3 sol oper
s
z 1 -25 0 0 15 0 4800 Z+60x2
H1 0 3/4 0 1 -1/4 0 120 H1-x2
x2=h2/4 0 1/4 1 0 1/4 0 80
H3 0 5 0 0 -4 0 600 H3-
20x2
A la fila z se le suma 60 veces la fila x2 para generar cero
extra
z 1 -40 -60 0 0 0 0 Menor
positivo
60x2 0 15 60 0 15 0 4800
Paso 8 regresa alpaso 4
v.basica z X1 X2 H1 H2 H3 sol oper
s
z 1 -25 0 0 15 0 4800 Z+60x2
H1 0 3/4 0 1 -1/4 0 120 H1-x2
x2=h2/4 0 1/4 1 0 1/4 0 80
H3 0 5 0 0 -4 0 600 H3-
20x2
No termina continua
Paso 5 mayor negativo
v.basica z X1 X2 H1 H2 H3 sol
s
z 1 -25 0 0 15 0 4800
H1 0 3/4 0 1 -1/4 0 120
x2=h2/4 0 1/4 1 0 1/4 0 80
H3 0 5 0 0 -4 0 600
Paso 6 variable de salida
v.basica z X1 X2 H1 H2 H3 sol División
s
z 1 -25 0 0 15 0 4800 Menor +
H1 0 3/4 0 1 -1/4 0 120 160
x2=h2/4 0 1/4 1 0 1/4 0 80 320
H3 0 5 0 0 -4 0 600 120
Paso 7 Z+25x1 15+25(-4/5) -1/4+3/5 = (-5+12)/20
v.basica z X1 X2 H1 H2 H3 sol División
s
z 1 0 0 0 -5 0 7800 Z+25x1
H1 0 0 0 1 7/20 0 30 H1-3/4x1
x2 0 0 1 0 9/20 0 50 X2-1/4x1
X1=h3/5 0 1 0 0 -4/5 0 120
Paso 8 todos los coecientes del renglón Z con valores mayores o iguales a cero.
v.basica z X1 X2 H1 H2 H3 sol División
s
z 1 0 0 0 -5 0 7800 Z+25x1
H1 0 0 0 1 7/20 0 30 H1-3/4x1
x2 0 0 1 0 9/20 0 50 X2-1/4x1
X1=h3/5 0 1 0 0 -4/5 0 120
Paso 4 continuamos con el valor negativo
Paso 5 variable de entrada y paso 6 variable de salida
v.basica z X1 X2 H1 H2 H3 sol División
s
z 1 0 0 0 -5 0 7800 Menor +
H1 0 0 0 1 7/20 0 30 85.71
x2 0 0 1 0 9/20 0 50 111.111
X1=h3/5 0 1 0 0 -4/5 0 120 negativo
Se actualiza la tabla con el nuevo pivote
v.basicas z X1 X2 H1 H2 H3 sol División
z 1 0 0 100/7 0 0 8228.57 Z+5h2
H2 0 0 0 20/7 1 0 600/7 H1*20/7
x2 X2-9/20h2
X1=h3/5 X1+4/5h2
terminarlo
