UNIDAD II

MÉTODO SIMPLEX
2.2 Método simplex.

Introducción.

La mayoría de los problemas reales de programación lineal tienen más de dos

variables y por ende, demasiado grandes para resolverse por el método gráfico. Un
procedimiento llamado método simplex puede ser utilizado para encontrar la
solución óptima de los problemas con multivariables. El método simplex es en
realidad un algoritmo con él cual se examinan los puntos en las esquinas de manera
metódica hasta conseguir la mejor solución, ya sea mayor utilidad o de menor costo.
En la actualidad ya existen programas por computadoras que resuelven problemas
de programación lineal con miles de variables, pero es útil el entendimiento de la
mecánica del algoritmo.

De una forma muy resumida el método Simplex consiste en:

1. Debe partirse de una solución básica factible inicial.

2. Si dicha solución básica no es óptima, entonces encontrar otra que haga
que el valor de la función objetivo aumente o disminuya, dependiendo del
problema de max o de min.
3. Repetir el paso anterior hasta encontrar una solución básica factible que
sea óptima.

Variables básicas. Son las variables que se encuentran en la base

Variables no básicas. Son las variables que no están en la base y se les asigna el
valor de cero.
Solución factible. Es aquella solución que satisface las restricciones del problema.
Espacio de soluciones factibles. Es el conjunto de todas las soluciones factibles
para un problema de programación lineal.

2.2.2 Transformación de un programa lineal a su forma estándar

Todo programa lineal, independientemente de la forma en la que esté dado, puede

plantearse en la forma estándar.

Las características de la forma estándar son:

1. Todas las restricciones son ecuaciones, excepto las restricciones de no
negatividad que permanecen como desigualdades (≥ 0).
2. Los elementos del lado derecho de cada ecuación son no negativos.
3. Todas las variables son no negativas.
4. La función objetivo es del tipo maximización o minimización.
Las restricciones de desigualdad pueden cambiarse a ecuaciones introduciendo
(sumando o restando) en el lado izquierdo de cada una de las restricciones una
variable no negativa.

Si la restricción es de la forma (≤) la variable que se introduce se llama variable de

holgura y se suma a la restricción (+S1).

Si la restricción es de la forma (≥) la variable que se introduce se llama variable de

exceso y se resta a la restricción(-S1).

Ejercicio 1

Sea el problema siguiente, transformar a su forma estándar.

Max Z = 2X1 + 4X2 + 3X3

S.a:
3X1 + 4X2 + 2X3 ≤ 60
2X1 + X2 + 2X3 ≤ 40
X1 + 3X2 + 2X3 ≤ 80
X1, X2, X3 ≥ 0

FORMA ESTANDAR

Max Z = 2X1 + 4X2 + 3X3 + 0S1 + 0S2 + 0S3

S.a:
3X1 + 4X2 + 2X3 + S1 = 60
2X1 + X2 + 2X3 + S2 = 40
X1 + 3X2 + 2X3 + S3 = 80
X1, X2, X3, S1, S2, S3 ≥ 0 NO NEGATIVIDAD
Ejercicio 2

Sea el problema siguiente, transformar a su forma estándar.

Min Z = 4X1 + 8X2 + 2X3

S.a:
4X1 + 5X2 + 6X3 = 100
3X1 + 3X2 + 8X3 ≥ 150
2X1 + X2 + 6X3 ≤ 90
X1, X2, X3 ≥ 0
FORMA ESTANDAR

Min Z = 4X1 + 8X2 + 2X3 - 0S1 + 0S2

S.a:
4X1 + 5X2 + 6X3 = 100
3X1 + 3X2 + 8X3 - S1 = 150
2X1 + X2 + 6X3 + S2 = 90
X1, X2, X3, S1, S2 ≥ 0
Pasa a su forma estándar los siguientes ejercicios:
EJERCICIO 3

Min. Z= 16X1 + 14X2 + 12X3

Sujeto a:
200X1 + 160X2 + 80X3 ≥ 4500
X1 ≤ 10
X2 ≤ 12
X3 ≤ 20
X1, X2, X3 ≥ 0
FORMA ESTANDAR

Min. Z= 16X1 + 14X2 + 12X3 - 0S1+0S2 +0S3 +0S4

Sujeto a:
200X1 + 160X2 + 80X3 -S1 = 4500
X1 +S2 = 10
+S3 = 12
X2
+S4 = 20
X3
X1, X2, X3, S1, S2, S3 ,S4≥ 0
EJERCICIO 4
Max. Z= 50X1 + 75X2
Sujeto a:
3.6X1 + 4.8X2 ≤ 4800
1.6X1 + 1.8X2 ≤ 1980
0.6X1 + 0.6X2 ≤ 900
X1 ≥ 300
X2 ≥ 180
X1, X2 ≥ 0
FORMA ESTANDAR
Max. Z= 50X1 + 75X2 +OS1+0S2+0S3-0S4-0S5
Sujeto a:
3.6X1 + 4.8X2 +S1 = 4800
1.6X1 + 1.8X2 +S2 = 1980
0.6X1 + 0.6X2 +S3 = 900
X1 -S4 = 300
¤ X2 -S5= 180
X1, X2, S1, S2, S3, S4, S5 ≥ 0
EJERCICIO 5
Max. Z = 40X1 + 60X2
Sujeto a:

X1 + X2 ≤ 200
X1 + 4X2 ≤ 320
10X1 + 20X2 ≤ 2200
X1, X2 ≥ 0
FORMA ESTANDAR
Max. Z = 40X1 + 60X2 +0S1+0S2+0S3
Sujeto a:

X1 + X2 + S1 = 200
X1 + 4X2 + S2= 320
10X1 + 20X2+ S3= 2200
X1, X2 , S1, S2, S3≥ 0

Pasos que se utiliza en el método simplex.

1. Transformar el problema a su forma estándar.

2. Igualar la función objetivo a cero: Z   C j X j  0
3. Construir una tabla con los coeficientes del programa lineal.(tabular)
4. Seleccionar como variable de entrada aquella cuya Z j  C j sea la más negativa.
5. Una vez seleccionada la variable que entrará a la base, seleccionar la variable
XBi
de salida, utilizando la siguiente regla: mínimo de
aij
Donde: aij  0 XB i = elemento del lado derecho de la restricción i ( i = 1,
2,….,m)
j = variable que entra a la base ( j = 1,2,….,n)

6. La intersección en la tabla de variable que entra y de la variable que sale,

al elemento se le denomina pivote; al que se deberá convertir en uno y al
resto de la columna en ceros, mediante el uso de operaciones matriciales
elementales.
7. Prueba de optimalidad: la solución será óptima cuando el renglón Z j  C j ≥ 0
EJERCICIO 6
Max. Z= X1 + 1.25X2
Sujeto a:
5X1 + 7X2 ≤ 4480
3X1 + X2 ≤ 2080
2X1 + 2X2 ≤ 1600
X1, X2 ≥ 0
PASO 1 Forma estandar

Max. Z= X1 + 1.25X2 +0S1 +0S2 +0S3

Sujeto a:
5X1 + 7X2 +S1 = 4480
3X1 + X2 +S2 = 2080
2X1 + 2X2 +S3 = 1600
X1, X2, S1, S2, S3 ≥ 0

PASO 2 Igualar Función Objetivo a cero

Z – X1-1.25X2 - 0S1 - 0S2 - 0S3= 0

PASO 3 CONTRUCCION DE TABLA

TABLA 1
V.E
VAR. X1 X2 S1 S2 S3 SOLUCIÓN DETERMINAR
BASICAS [Link]
Z -1 -1.25 0 0 0 0
S1 5 7 1 0 0 4480 4480/7=640 VS
S2 3 1 0 1 0 2080 2080/1=2080
S3 2 2 0 0 1 1600 1600/2=800
PASO 4 DETERMINAR VARIABLES DE ENTRADA

MAXIMIZANDO MAS NEGATIVA DEL RENGLON DE Z

MINIMIZANDO MAS POSITIVA DEL RENGLON DE Z

PASO 5 DETERMINAR VARIABLE DE SALIDA

COLUMNA SOLUCIÓN
COLUMNA V. ENTRADA

EL RESULTADO MÁS PEQUEÑO POSITIVO SERA VARIABLE DE SALIDA.

PASO 6 DETERMINAR MI PIVOTE

INTERSECCION ENTRE LA VARIABLE ENTRADA Y LA VARIABLE DE SALIDA. AL PIVOTE
SE CONVIERTE EN UNO Y RESTO DE LA COLUMNA EN CERO CON OPERACIONES
MATRICIALES.

TABLA 1

VAR. X1 X2 S1 S2 S3 SOLUCIÓN DETERMINAR

BASICAS [Link]
Z -1 -1.25 0 0 0 0 F1
S1 5 7 1 0 0 4480 4480/7=640 VS
F2
S2 3 1 0 1 0 2080 2080/1=2080 F3
S3 2 2 0 0 1 1600 1600/2=800 F4

OBTENER G1=1.25G2+F1
5/7 1 1/7 0 0 640 1.25
25/28 1.25 5/28 0 0 800 RESULTADO
-1 -1.25 0 0 0 0 SUMA
-3/28 0 5/28 0 0 800

OBTENER G3=-G2+F3
5/7 1 1/7 0 0 640 -1
-5/7 -1 -1/7 0 0 -640 RESULT
3 1 0 1 0 2800 SUMA
16/7 0 -1/7 1 0 2160

OBTENER G4=-2G2+F4
5/7 1 1/7 0 0 640 -2
-10/7 -2 -2/7 0 0 -1280 RESULTA
2 2 0 0 1 1600
4/7 0 -2/7 0 1 320

TABLA 2
V.E.
VAR. X1 X2 S1 S2 S3 SOLUCION DET.V. SALIDA
BASICAS
Z -3/28 0 5/28 0 0 800 G11.25G2+F1
X2 5/7 1 1/7 0 0 640 640/5/7=896 G2=F2/7
S2 16/7 0 -1/7 1 0 2160 2160/16/7=945 G3=-G2+F3
S3 4/7 0 -2/7 0 1 320 320/4/7=560 G4= -2G2+F4
PIVOTE V.S

TABLA 3

VAR. X1 X2 S1 S2 S3 SOLUCION VAR.

BASICAS SALIDA
Z 0 0 1/8 0 3/16 860 H1=3/28H4+F1
X2 0 1 ½ 0 -5/4 240 H2=-5/7H4+F2
S2 0 0 1 1 -4 160 H3=-16/7H4+G3
X1 1 0 -1/2 0 7/4 560 H4=G4/4/7
SOLUCION FINAL

Z= 860
X1=560
X2=240
S2=1660

COMPROBAMOS SUSTITUYENDO LOS VALORES EN SU FORMA ESTANDAR

Max. Z= X1 + 1.25X2 +0S1 +0S2 +0S3

Sujeto a:
5X1 + 7X2 +S1 = 4480
3X1 + X2 +S2 = 2080
2X1 + 2X2 +S3 = 1600

MAX Z= 560 + 1.25(240) + 0 + 0 *160+0 =860

5*560 + 7*240 + 0 = 4480
3*560 +240 +160 =2080
2*560 + 2*240+0 =1600

TAREA

RESUELVE LOS SIGUIENTES EJERCICIOS A MANO:

EJERCICIO 7
Función objetivo: Maximizar. Z = 40X1 + 60X2
Sujeto a:

X1 + X2 ≤ 200
X1 + 4X2 ≤ 320
10X1 + 20X2 ≤ 2200
X1, X2 ≥ 0

EJERCICIO 8

Max. Z = 4X1 + 7X2 + 6X3 + 5X4 + 4X5

Sujeto a:
5X1 + 8X2 + 3X3 + 2X4 + 7X5 ≤ 112
X1 + 8X2 + 6X3 + 5X4 + 4X5 ≤ 109
X1, X2,X3,X4, X5 >= 0;