EL ALGORITMO SIMPLEX o METODO SIMPLEX

METODO SIMPLEX – DOS FASES

Cuando tenemos restricciones con >= o con igualdad =

A = Variable artificial. Es la variable básica para restricciones con >= y =

W = Función objetivo sumatorias variables artificiales
Min W = ∑ 𝐴𝑘

Signo S A
holgura Artificial
<= +S -
>= -S +A
= - +A

EJERCICIO DE MINIMIZACION

En una granja de pollos se da una dieta, para engordar, con una composición
mínima de 15 unidades de una sustancia A y otras 15 de una sustancia B. En el
mercado sólo se encuentra dos clases de compuestos: el tipo X con una
composición de una unidad de A y 5 de B, y el otro tipo, Y, con una composición de
cinco unidades de A y una de B. El precio del tipo X es de $30.000 y del tipo Y es
de $90.000. ¿Qué cantidades se han de comprar de cada tipo para cubrir las
necesidades con un coste mínimo?

Compuesto X Compuesto Y Requerimiento

mínimo
Sustancia A 1 5 15 unidades
Sustancia B 5 1 15 unidades
Costo $30000 $90000
$/unidad

X1= # unidades del compuesto X a comprar

X2= # unidades del compuesto Y a comprar

Min Z(Costos)= 30000X1 +90000X2 Max (-Z)= -30X1 -90X2

s.a (1) X1 + 5X2 >= 15 unidades de la sustancia A
(2) 5X1 + X2 >= 15 unidades de la sustancia B
X1,X2>=0
FORMA ESTANDAR Y FORMA BASICA MinW=A1 +A2 Max(-W)=-A1-A2

(1) X1 + 5X2 -S1 +A1 = 15

(2) 5X1 + X2 -S2 +A2= 15
(0) -Z +30X1 +90X2 =0
(0)` -W +A1+A2 = 0

(0)”=(0) `-(1)-(2)

(0)` -W +A1+A2 = 0
-(1) - X1 - 5X2 +S1 -A1 = -15
-(2) -5X1 - X2 +S2 -A2= -15
---------------------------------------------------------------
(0)”-W -6X1 -6X2 +S1 +S2 = -30

(1) X1 + 5X2 -S1 +A1 = 15

(2) 5X1 + X2 -S2 +A2= 15
(0) -Z +30X1 +90X2 =0
(0)”-W -6X1 -6X2 +S1 +S2 = -30

Tabla 1
BI/aij VB B X1 X2 S1 S2 A1 A2
15/1=15 A1 15 1 5 -1 0 1 0
15/5= 3 A2 15 5 1 0 -1 0 1
XXXXXX -Z 0 30 90 0 0 0 0
XXXXXX -W -30 -6 -6 1 1 0 0

Variable que entra X1 Variable que sale A2 # Pivote 5

Tabla 2
BI/aij VB B X1 X2 S1 S2 A1 A2
12 24 15 A1 12 0 24/5 -1 1/5 1 -1/5
/ =
1 5 6
3 1
/ = 15 X1 3 1 1/5 0 -1/5 0 1/5
1 5
XXXXXX -Z -90 0 84 0 6 0 -6
XXXXXX -W -12 0 -24/5 1 -1/5 0 6/5

Variable que entra X2 Variable que sale A1 # Pivote 24/5

FILA NUEVA 1
FPN2 Fila pivote nueva 2 3 1 1/5 0 -1/5 0 1/5 -1
(+) FA1 Fila antigua 1 15 1 5 -1 0 1 0
(=) FN1 Fila nueva 1 12 0 24/5 -1 1/5 1 -1/5
1 25 24
-5+ =5
5

FILA NUEVA 0
FPN2 Fila pivote nueva 2 3 1 1/5 0 -1/5 0 1/5 -30
(+) FA0 Fila antigua 0 0 30 90 0 0 0 0
(=) FN0 Fila nueva 0 -90 0 84 0 6 0 -6

FILA NUEVA 0”
FPN2 Fila pivote nueva 2 3 1 1/5 0 -1/5 0 1/5 6
(+) FA0” Fila antigua 0” -30 -6 -6 1 1 0 0
(=) FN0” Fila nueva 0” -12 0 -24/5 1 -1/5 0 6/5

6 30 24
- =−
5 5 5

6 5 1
-5 + 5=− 5

Tabla 3
BI/aij VB B X1 X2 S1 S2 A1 A2
X2 5/2 0 1 -5/24 1/24 5/24 -1/24
X1 5/2 1 0 1/24 -5/24 -1/24 5/24
XXXXXX -Z -300 0 0 35/2 5/2 -35/2 -5/2
XXXXXX -W 0 0 0 0 0 1 1

24 5
# Pivote = * 24= 1
5

1 5 1
* 24= 24
5

FILA NUEVA 2
FPN1 Fila pivote nueva 1 5/2 0 1 -5/24 1/24 5/24 -1/24 -1/5
(+) FA2 Fila antigua 2 3 1 1/5 0 -1/5 0 1/5
(=) FN2 Fila nueva 2 5/2 1 0 1/24 -5/24 -1/24 5/24

1 5 5 1 6 5
− 5* 2+ 3= - +3 =- + =
10 2 2 2

1 1 1 1 1 1 24 25 5
− 5* 24 − 5 = - - =- - = -120= −24
120 5 120 120

1 1 1 1 1 1 24 25 5
− 5* − 24 + 5 = + = 120 + = 120= 24
120 5 120
 FILA NUEVA 0
FPN1 Fila pivote nueva 1 5/2 0 1 -5/24 1/24 5/24 -1/24 -84
(+) FA0 Fila antigua 0 -90 0 84 0 6 0 -6
(=) FN0 Fila nueva 0 -300 0 0 35/2 3/2 -35/2 -3/2

420 105
=
24 6

84 144 60 15
- + 24 = 24=
24 6

84 144 − 60 15
- = =−
24 24 24 6

FILA NUEVA 0”
FPN1 Fila pivote nueva 1 5/2 0 1 -5/24 1/24 5/24 -1/24 24/5
(+) FA0” Fila antigua 0” -12 0 -24/5 1 -1/5 0 6/5
(=) FN0” Fila nueva 0” 0 0 0 0 0 1 1

Tabla 3 FASE I
BI/aij VB B X1 X2 S1 S2 A1 A2
X2 5/2 0 1 -5/24 1/24 5/24 -1/24
X1 5/2 1 0 1/24 -5/24 -1/24 5/24
XXXXXX -Z -300 0 0 35/2 5/2 -35/2 -5/2
XXXXXX -W 0 0 0 0 0 1 1

Tabla3 FASEII Tabla optima

BI/aij VB B X1 X2 S1 S2
X2 5/2 0 1 -5/24 1/24
X1= 5/2 1 0 1/24 -5/24
XXXXXX -Z -300 0 0 35/2 5/2

X1*=Se deben comprar 2,5 unidades del compuesto X

X2*=Se deben comprar 2,5 unidades del compuesto Y
S1*=0 No hay excedente de la sustancia A
S2*=0 No hay excedente de la sustancia B
Z*= El costo mínimo de compra es de $300.000
 Tipos de solución:

I- Solución única. Ejemplo en la Tabla optima

VB B X1 X2 S1 S2
X2 5/2 0 1 -5/24 1/24
X1= 5/2 1 0 1/24 -5/24
-Z -300 0 0 35/2 5/2

II- Solución múltiple. Ejemplo en la Tabla optima

VB B X1 X2 S1 S2
X2 5/2 0 1 -5/24 1/24
X1= 5/2 1 0 1/24 -5/24
Z 300 0 0 35/2 0

Cuando el coeficiente de una variable no básica es cero en la tabla optima, se trata de

una solución múltiple.

III- Solución No acotada

Min VB B X1 X2 S1 S2
BI/AIJ >=0
& ---- X2 5/2 0 1 -5/24 0
=-12 ---- X1 5/2 1 0 1/24 -5/24
XXXXXX Z 300 0 0 35/2 -5/2

Maximización

Identifica variable que entra S2 No identifica variable a salir

Cuando se identifica la variable que entra, pero no se identifica la variable que sale se
trata de una solución No acotada. Solución sin limita.

IV- Solución no factible. Solución infactible.

VB B X1 X2 S1 S2 A1 A2
A1 12 0 24/5 -1 1/5 1 -1/5
X1 3 1 1/5 0 -1/5 0 1/5
-Z -90 0 84 0 6 0 6
-W -12 0 24/5 1 1/5 0 6/5

Cuando en la función objetivo W los coeficientes de las variables no básicas son

positivos y permanecen variables artificiales como variables básicas se dice que la
solución es No Factible.
 EL ALGORITMO SIMPLEX o METODO SIMPLEX

METODO SIMPLEX – DOS FASES

Cuando tenemos restricciones con >= o con igualdad =

A = Variable artificial. Es la variable básica para restricciones con >= y =

W = Función objetivo sumatorias variables artificiales
Min W = ∑ 𝐴𝑘

Signo S A
holgura Artificial
<= +S -
>= -S +A
= - +A

EJERCICIO DE MINIMIZACION

La compañía Delta recibió una orden de una mezcla de 2.000 Kg. de una mezcla de
cereales y carne de res como alimentos de los perros policía del estado. El cereal
cuesta $20 el Kg. y la carne de res $40 el Kg., solamente hay disponibles 800 Kg.
de cereal y hay que usar al menos 600 Kg. de carne en la mezcla. Que cantidad de
cada ingrediente se deberá utilizar, de tal manera que se minimice el costo y cumplir
con los requerimientos al mismo tiempo. (La mezcla está compuesta de cereal más
carne).

X1= # Kg de cereal a mezclar

X2=# Kg de carne a mezclar

MIN Z (costos) = 20X1 + 40X2 MAX (-Z) = -20X1 -40X2

s.a. (1) X1 + X2 = 2000 Kg de mezcla

(2) X1 <= 800 Kg cereal
(3) X2 >= 600 kg de carne
X1,X2>=0

MIN Z (costos) = 20X1 + 40X2

MIN Z= MAX(-Z)
MAX (-Z) = -20X1 -40X2

MIN W= A1+A3
MINW = MAX(-W)
MAX(-W) = -A1-A3
FORMA ESTANDAR ó FORMA BASICA

(1) X1 + X2 +A1 = 2000

(2) X1 +S2 = 800
(1) X2 -S3 +A3 = 600
(0) (-Z) +20X1+40X2 = 0
(0)´ (-W) +A1+A3= 0

(0)´´ = (0)´- (1) –(3)

(0)´ (-W) +A1 +A3 = 0

- (1) -X1 - X2 -A1 = -2000

-(3) - X2 +S3 -A3 = -600

---------------------------------------------------------------------------
(0)´´ (-W) -X1 -2X2 +S3 = -2600

(1) X1 + X2 +A1 = 2000

(2) X1 +S2 = 800
(3) X2 -S3 +A3 = 600
(0) (-Z) +20X1+40X2 = 0
(0)´´ (-W) -X1 -2X2 +S3 = -2600

Tabla 1

Min Bi/Aij VB Bi X1 X2 S2 S3 A1 A3
2000/1=2000 A1 2000 1 1 0 0 1 0
------------- S2 800 1 0 1 0 0 0
600/1 =600 A3 600 0 1 0 -1 0 1
XXXXXXX -Z 0 20 40 0 0 0 0
XXXXXXX -W -2600 -1 -2 0 1 0 0

Variable que entra X2 Variable que sale A3 Numero Pivote 1

Tabla2
Min Bi/Aij VB Bi X1 X2 S2 S3 A1 A3
1400 /1=1400 A1 1400 1 0 0 1 1 -1
800/0 =& --- S2 800 1 0 1 0 0 0
 600/-1 = -600---- X2 600 0 1 0 -1 0 1
XXXXXXX -Z -24000 20 0 0 40 0 -40
XXXXXXX -W -1400 -1 0 0 -1 0 2

Variable que entra S3 Variable que sale A1 #Pivote = 1

FILA NUEVA 1

FPN3 Fila pivote nueva 3 600 0 1 0 -1 0 1 -1

(+) FA1 Fila antigua 1 2000 1 1 0 0 1 0
(=) FN1 Fila nueva 1 1400 1 0 0 1 1 -1
FILA NUEVA 0

FPN3 Fila pivote nueva 3 600 0 1 0 -1 0 1 -40

(+) FA0 Fila antigua 0 0 20 40 0 0 0 0
(=) FN0 Fila nueva 0 -24000 20 0 0 40 0 -40

FILA NUEVA 0”

FPN3 Fila pivote nueva 3 600 0 1 0 -1 0 1 2

(+) FA0” Fila antigua 0” -2600 -1 -2 0 1 0 0
(=) FN0” Fila nueva 0” -1400 -1 0 0 -1 0 2

Tabla 3

Min Bi/Aij VB Bi X1 X2 S2 S3 A1 A3
S3 1400 1 0 0 1 1 -1
S2 800 1 0 1 0 0 0
X2 2000 1 1 0 0 1 0
XXXXXXX -Z -80000 -20 0 0 0 -40 0
XXXXXXX -W 0 0 0 0 0 1 1

Termina la FASE I: No hay variables artificiales como básicas. Todos los coeficientes son
ceros en la ecuación 0” excepto en las artificiales que tienen coeficiente +1.

FILA NUEVA 3

FPN1 Fila pivote nueva 1 1400 1 0 0 1 1 -1 1

(+) FA3 Fila antigua 3 600 0 1 0 -1 0 1
(=) FN3 Fila nueva 3 2000 1 1 0 0 1 0

FILA NUEVA 0

FPN1 Fila pivote nueva 1 1400 1 0 0 1 1 -1 -40

(+) FA0 Fila antigua 0 -24000 20 0 0 40 0 -40
(=) FN0 Fila nueva 0 -80000 -20 0 0 0 -40 0
 FILA NUEVA 0”

FPN1 Fila pivote nueva 1 1400 1 0 0 1 1 -1 1

(+) FA0” Fila antigua 0” -1400 -1 0 0 -1 0 2
(=) FN0” Fila nueva 0” 0 0 0 0 0 1 1

Tabla 3 FASE 1

Min Bi/Aij VB Bi X1 X2 S2 S3 A1 A3
S3 1400 1 0 0 1 1 -1
S2 800 1 0 1 0 0 0
X2 2000 1 1 0 0 1 0
XXXXXXX -Z -80000 -20 0 0 0 -40 0
XXXXXXX -W 0 0 0 0 0 1 1

Tabla 3 FASE II

Min Bi/Aij VB Bi X1 X2 S2 S3
1400/1 =1400 S3 1400 1 0 0 1
800/1 =800 S2 800 1 0 1 0
2000/1 =2000 X2 2000 1 1 0 0
XXXXXXX -Z -80000 -20 0 0 0

Variable que entra X1 Variable que sale S2 # Pivote 1

Tabla 4 Tabla optima

Min Bi/Aij VB Bi X1 X2 S2 S3
S3 600 0 0 -1 1
X1 800 1 0 1 0
X2 1200 0 1 -1 0
-Z -64000 0 0 20 0

FILA NUEVA 1

FPN2 Fila pivote nueva 2 800 1 0 1 0 -1

(+) FA1 Fila antigua 1 1400 1 0 0 1
(=) FN1 Fila nueva 1 600 0 0 -1 1

FILA NUEVA 3

FPN2 Fila pivote nueva 2 800 1 0 1 0 -1

(+) FA3 Fila antigua 3 2000 1 1 0 0
(=) FN3 Fila nueva 3 1200 0 1 -1 0
 FILA NUEVA 0

FPN2 Fila pivote nueva 2 800 1 0 1 0 20

(+) FA0 Fila antigua 0 -80000 -20 0 0 0
(=) FN0 Fila nueva 0 -64000 0 0 20 0

Tabla optima

Min Bi/Aij VB Bi X1 X2 S2 S3
S3= 600 0 0 -1 1
X1= 800 1 0 1 0
X2= 1200 0 1 -1 0
-Z -64000 0 0 20 0

X1*= Se deben mezclar 800 Kg de cereal

X2*= Se deben mezclar 1200 Kg de carne
S2*= Son sobran Kg de cereal (<=)
S3*= Se excede en 600 Kg de carne (>=)
Z* = El costo mínimo es de $64000

Max -Z=-64000 *(-1)

Min Z=64000

X2>=600 Kg de carne
X2 – S3 = 600
1200- 600 =600
En una granja de pollos se da una dieta, para engordar, con una composición
mínima de 15 unidades de una sustancia A y otras 15 de una sustancia B. En el
mercado sólo se encuentra dos clases de compuestos: el tipo X con una
composición de una unidad de A y 5 de B, y el otro tipo, Y, con una composición de
cinco unidades de A y una de B. El precio del tipo X es de $30.000 y del tipo Y es
de $90.000. ¿Qué cantidades se han de comprar de cada tipo para cubrir las
necesidades con un coste mínimo?

Compuesto X Compuesto Y Requerimiento

mínimo
Sustancia A 1 5 15 unidades
Sustancia B 5 1 15 unidades
Costo $30000 $90000
$/unidad

X1= # unidades del compuesto X a comprar

X2= # unidades del compuesto Y a comprar

Min Z= 30000X1 +90000X2 Max (-Z)= -30X1 -90X2

s.a (1) X1 + 5X2 >= 15 unidades de la sustancia A
(2) 5X1 + X2 >= 15 unidades de la sustancia B
X1,X2>=0

FORMA ESTANDAR Y FORMA BASICA MinW=A1 +A2 Max(-W)=-A1-A2

(1) X1 + 5X2 -S1 +A1 = 15

(2) 5X1 + X2 -S2 +A2= 15
(0) -Z +30X1 +90X2 =0
(0)` -W +A1+A2 = 0

(0)”=(0) `-(1)-(2)

(0)` -W +A1+A2 = 0
-(1) - X1 - 5X2 +S1 -A1 = -15
-(2) -5X1 - X2 +S2 -A2= -15
---------------------------------------------------------------
(0)”-W -6X1 -6X2 +S1 +S2 = -30
(1) X1 + 5X2 -S1 +A1 = 15
(2) 5X1 + X2 -S2 +A2= 15
(0) -Z +30X1 +90X2 =0
(0)”-W -6X1 -6X2 +S1 +S2 = -30

Tabla 1
BI/aij VB B X1 X2 S1 S2 A1 A2
15/1=15 A1 15 1 5 -1 0 1 0
15/5= 3 A2 15 5 1 0 -1 0 1
XXXXXX -Z 0 30 90 0 0 0 0
XXXXXX -W -30 -6 -6 1 1 0 0

Variable que entra X1 Variable que sale A2 # Pivote 5

Tabla 2
BI/aij VB B X1 X2 S1 S2 A1 A2
12 24 15 A1 12 0 24/5 -1 1/5 1 -1/5
/ =
1 5 6
3 1
/ = 15 X1 3 1 1/5 0 -1/5 0 1/5
1 5
XXXXXX -Z -90 0 84 0 6 0 6
XXXXXX -W -12 0 -24/5 1 -1/5 0 6/5

Variable que entra X2 Variable que sale A1 # Pivote 24/5

FILA NUEVA 1
FPN2 Fila pivote nueva 2 3 1 1/5 0 -1/5 0 1/5 -1
(+) FA1 Fila antigua 1 15 1 5 -1 0 1 0
(=) FN1 Fila nueva 1 12 0 24/5 -1 1/5 1 -1/5

1 25 24
-5+ =5
5

FILA NUEVA 0
FPN2 Fila pivote nueva 2 3 1 1/5 0 -1/5 0 1/5 -30
(+) FA0 Fila antigua 0 0 30 90 0 0 0 0
(=) FN0 Fila nueva 0 -90 0 84 0 6 0 6

FILA NUEVA 0”
FPN2 Fila pivote nueva 2 3 1 1/5 0 -1/5 0 1/5 6
(+) FA0” Fila antigua 0” -30 -6 -6 1 1 0 0
(=) FN0” Fila nueva 0” -12 0 -24/5 1 -1/5 0 6/5

6 30 24
- =−
5 5 5

6 5 1
-5 + 5=− 5
 EL ALGORITMO SIMPLEX o METODO SIMPLEX

METODO SIMPLEX – DOS FASES

Cuando tenemos restricciones con >= o con igualdad =

A = Variable artificial. Es la variable básica para restricciones con >= y =

W = Función objetivo sumatorias variables artificiales
Min W = ∑ 𝐴𝑘

Signo S A
holgura Artificial
<= +S -
>= -S +A
= - +A

METODO SIMPLEX – DOS FASES

Cuando tenemos restricciones con >= o con igualdad =

MAX Z( utilidad) = 3X1 + 2X2

s.a. (1) X1 + X2 >= 4
(2) 3X1 + 4X2 <= 24
X1,X2>=0

FORMA ESTANDAR

(1) X1 + X2 -S1 = 4
(2) 3X1 + 4X2 +S2 = 24
(0) Z -3X1 -2 X2 =0

FORMA BASICA o FORMA CANONICA:

(1) X1 + X2 -S1 +A1 = 4
(2) 3X1 + 4X2 +S2 = 24
(0) Z -3X1 - 2X2 =0
(0)´ (-W) +A1 = 0

Min W = A1
Min W = Max (-W)
Max (-W) = - A1

(0)´´ = (0)´- (1)

 (0)´ (-W) +A1 = 0
- (1) -X1 - X2 + S1 -A1 = -4
-----------------------------------------------------
(0)´´ (-W) -X1 -X2 +S1 = -4

(1) X1 + X2 -S1 +A1 = 4

(2) 3X1 + 4X2 +S2 = 24
(0) Z -3X1 - 2X2 =0
(0)´´ (-W) -X1 - X2 +S1 = -4

FASE 1 FUNCIÓN OBJETIVO W

Primera tabla simplex:

Min Bi/Aij VB Bi X1 X2 S1 S2 A1
4/1 =4 A1 4 1 1 -1 0 1
24/4 =6 S2 24 3 4 0 1 0
xxxxxxxxxxx Z 0 -3 -2 0 0 0
xxxxxxxxxxx -W -4 -1 -1 1 0 0

Variable que entra X2 Variable que sale A1 Numero Pivote 1

segunda tabla simplex:

Min Bi/Aij VB Bi X1 X2 S1 S2 A1
X2 4 1 1 -1 0 1
S2 8 -1 0 4 1 -4
Z 8 -1 0 -2 0 2
-W 0 0 0 0 0 1
 FILA NUEVA 2

FPN1 Fila pivote nueva 1 4 1 1 -1 0 1 -4

(+) FA2 Fila antigua 2 24 3 4 0 1 0
(=) FN2 Fila nueva 2 8 -1 0 4 1 -4

FILA NUEVA 0

FPN1 Fila pivote nueva 1 4 1 1 -1 0 1 2

(+) FA0 Fila antigua 0 0 -3 -2 0 0 0
(=) FN0 Fila nueva 0 8 -1 0 -2 0 2

FILA NUEVA 0´´

FPN1 Fila pivote nueva 1 4 1 1 -1 0 1 1

(+) FA0´´ Fila antigua 0´´ -4 -1 -1 1 0 0
(=) FN0 ´´ Fila nueva 0´´ 0 0 0 0 0 1

FASE 2 FUNCIÓN OBJETIVO Z

Min Bi/Aij VB Bi X1 X2 S1 S2
4/-1 = -4 X2 4 1 1 -1 0
8/4 =2 S2 8 -1 0 4 1
xxxxxxxxxx Z 8 -1 0 -2 0

Entra S1 Sale S2 # Pivote = 4

Tercera Tabla

Min Bi/Aij VB Bi X1 X2 S1 S2
6/1 / ¾ =8 X2 6 3/4 1 0 1/4
2/1 / -1/4 = -8 S1 2 -1/4 0 1 1/4
XXXXXXXXX Z 12 -3/2 0 0 1/2

Entra X1 Sale X2 Pivote 3/4

FILA NUEVA 1

FPN2 Fila pivote nueva 2 2 -1/4 0 1 1/4 1

(+) FA2 Fila antigua 1 4 1 1 -1 0
(=) FN2 Fila nueva 1 6 3/4 1 0 1/4
 FILA NUEVA 0

FPN2 Fila pivote nueva 2 2 -1/4 0 1 1/4 2

(+) FA2 Fila antigua 0 8 -1-1 0 -2 0
(=) FN2 Fila nueva 0 12 -3/2 0 0 1/2

-2/4 -1 = -1/2 -2/2 = - 3/2

Cuarta Tabla

Min Bi/Aij VB Bi X1 X2 S1 S2
X1 8 1 4/3 0 1/3
S1 4 0 1/3 1 1/3
Z 24 0 2 0 1

FILA NUEVA 2

FPN1 Fila pivote nueva 1 8 1 4/3 0 1/3 1/4

(+) FA2 Fila antigua 2 2 -1/4 0 1 1/4
(=) FN2 Fila nueva 2 4 0 1/3 1 1/3

1/12 + 1/4 = 1/12 + 3/12 = 4/12 =1/3

FILA NUEVA 0

FPN1 Fila pivote nueva 1 8 1 4/3 0 1/3 3/2

(+) FA0 Fila antigua 0 12 -3/2 0 0 1/2
(=) FN0 Fila nueva 0 24 0 2 0 1

3/2*1/3 + ½ = ½ +1/2 = 2/2 = 1

Tabla Optima

Min Bi/Aij VB Bi X1 X2 S1 S2
X1 8 1 4/3 0 1/3
S1 4 0 1/3 1 1/3
Z 24 0 2 0 1
Solución Optima

X1* =8
X2*= 0
S1*=4
S2*= 0
Z*=24 El valor máximo

EJERCICIO DE MINIMIZACION

La compañía Delta recibió una orden de una mezcla de 2.000 Kg. de una mezcla de
cereales y carne de res como alimentos de los perros policía del estado. El cereal
cuesta $20 el Kg. y la carne de res $40 el Kg., solamente hay disponibles 800 Kg.
de cereal y hay que usar al menos 600 Kg. de carne en la mezcla. Que cantidad de
cada ingrediente se deberá utilizar, de tal manera que se minimice el costo y cumplir
con los requerimientos al mismo tiempo. (La mezcla está compuesta de cereal más
carne).

X1= # Kg de cereal a mezclar

X2=# Kg de carne a mezclar

MIN Z (costos) = 20X1 + 40X2 MAX (-Z) = -20X1 -40X2

s.a. (1) X1 + X2 = 2000 Kg de mezcla

(2) X1 <= 800 Kg cereal
(3) X2 >= 600 kg de carne
X1,X2>=0

MIN Z (costos) = 20X1 + 40X2

MIN Z= MAX(-Z)
MAX (-Z) = -20X1 -40X2

MIN W= A1+A3
MINW = MAX(-W)
MAX(-W) = -A1-A3

FORMA ESTANDAR ó FORMA BASICA

(1) X1 + X2 +A1 = 2000

(2) X1 +S2 = 800
(3) X2 -S3 +A3 = 600
(0) (-Z) +20X1+40X2 = 0
(0)´ (-W) +A1+A3= 0
(0)´´ = (0)´- (1) –(3)

(0)´ (-W) +A1 +A3 = 0

- (1) -X1 - X2 -A1 = -2000

-(3) - X2 +S3 -A3 = -600

---------------------------------------------------------------------------
(0)´´ (-W) -X1 -2X2 +S3 = -2600

(1) X1 + X2 +A1 = 2000

(2) X1 +S2 = 800
(3) X2 -S3 +A3 = 600
(0) (-Z) +20X1+40X2 = 0
(0)´´ (-W) -X1 -2X2 +S3 = -2600

Tabla 1

Min Bi/Aij VB Bi X1 X2 S2 S3 A1 A3
2000/1=2000 A1 2000 1 1 0 0 1 0
------------- S2 800 1 0 1 0 0 0
600/1 =600 A3 600 0 1 0 -1 0 1
XXXXXXX -Z 0 20 40 0 0 0 0
XXXXXXX -W -2600 -1 -2 0 1 0 0

Variable que entra X2 Variable que sale A3 Numero Pivote 1

Tabla2
Min Bi/Aij VB Bi X1 X2 S2 S3 A1 A3
A1
S2 800 1 0 1 0 0 0
X2 600 0 1 0 -1 0 1
-Z
-W
 EL ALGORITMO SIMPLEX o METODO SIMPLEX
Una compañía de TV produce dos tipos de equipos para televisión, el Astro y el Cosmo.
Hay dos líneas de producción, uno para cada tipo de televisor y dos departamentos, que
intervienen ambos en la producción de cada aparato. La capacidad de la línea de
producción Astro es de 140 televisores diarios y la de la línea Cosmo es de 100 por día. En
el departamento A se fabrican los cinescopios. En este departamento los televisores Astro
requieren dos horas de trabajo y los Cosmo, 4 horas. Actualmente, en el departamento A
se puede asignar un máximo de 240 horas de trabajo por día a la producción de ambos
tipos de aparatos. En el departamento B se construye el chasis. En este departamento los
televisores Astro requieren 2 horas de trabajo, igual que los Cosmo. En la actualidad se
puede asignar un máximo de 180 horas de trabajo diarias al departamento B para la
producción de ambos tipos de televisores. La utilidad por aparato es de 40 y 20 dólares,
respectivamente, por cada aparato Astro y Cosmo. Resuelva por simplex e interprete.

Recurso TV Astro TV Cosmo Disponibilidad

Capacidad Max 140 Max 100
Producción unidades Unidades
Departamento A 2h 4h 240 horas
Departamento B 2h 2h 180 horas
Utilidad $/unidad $40 $20

X1 = Nro de equipos para TV Astro a producir

X2 = Nro de equipos para TV Cosmo a producir

Max Z(Utilidad) = 40X1 + 20X2

s.a
(1) X1 <= 140 unidades de Astro
(2) X2 <= 100 unidades Cosmo
(3) 2X1 + 4X2 <= 240 horas Depto A
(4) 2X1 + 2X2 <= 180 horas Depto B
X1, X2>=0

Forma Estándar: Paso

(1) X1 +S1 = 140
(2) X2 +S2 = 100
(3) 2X1 + 4X2 +S3 = 240
(4) 2X1 + 2X2 +S4 = 180
(0) Z- 40X1 -20X2 = 0
 S1 S2 S3 S4 Z
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
5X5

Variables básicas = S1,S2,S3,S4,Z

Variables No básicas = X1,X2

Tabla 1. PASO1

Min Bi/Aij VB Bi X1 X2 S1 S2 S3 S4
140/1=140 S1= 140 1 0 1 0 0 0
100/0 = & S2 100 0 1 0 1 0 0
240/2 = 120 S3 240 2 4 0 0 1 0
180/2 =90 S4 180 2 2 0 0 0 1
XXXXXXXX Z 0 -40 -20 0 0 0 0

SOLUCION INICIAL (X1,X2, S1,S2,S3,S4,Z) =(0,0,140,100,240,180,0)

PASO 2: Bi/Aij>=0

Variable q entra X1 Variable que sale S4 Numero Pivote = 2

S1 S2 S3 X1 Z
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
5X5

Tabla 2

Min Bi/Aij VB B X1 X2 S1 S2 S3 S4
S1 50 0 -1 1 0 0 -1/2
S2 100 0 1 0 1 0 0
S3 60 0 2 0 0 1 -1
X1 90 1 1 0 0 0 1/2
Z 3600 0 20 0 0 0 20
 Nota: Si en la columna pivote aparece un cero, los coeficientes correspondientes a
esta fila pasan igual a la tabla siguiente.

FILA NUEVA 1

FPN4 Fila pivote nueva 4 90 1 1 0 0 0 1/2 -1

(+) FA1 Fila antigua 1 140 1 0 1 0 0 0
(=) FN1 Fila nueva 1 50 0 -1 1 0 0 -1/2

FILA NUEVA 2

FPN4 Fila pivote nueva 4 90 1 1 0 0 0 1/2 0

(+) FA2 Fila antigua 2 100 0 1 0 1 0 0
(=) FN2 Fila nueva 2 100 0 1 0 1 0 0

FILA NUEVA 3

FPN4 Fila pivote nueva 4 90 1 1 0 0 0 1/2 -2

(+) FA3 Fila antigua 3 240 2 4 0 0 1 0
(=) FN3 Fila nueva 3 60 0 2 0 0 1 -1

FILA NUEVA 0

FPN4 Fila pivote nueva 4 90 1 1 0 0 0 1/2 40

(+) FA0 Fila antigua 0 0 -40 -20 0 0 0 0
(=) FN0 Fila nueva 0 3600 0 20 0 0 0 20
 Tabla OPTIMA

Min Bi/Aij VB B X1 X2 S1 S2 S3 S4
S1= 50 0 -1 1 0 0 -1/2
S2= 100 0 1 0 1 0 0
S3= 60 0 2 0 0 1 -1
X1= 90 1 1 0 0 0 1/2
Z $3600 0 20 0 0 0 20

X1*= Se deben fabricar 90 equipos para TV Astro

X2*= No se deben fabricar equipos TV Cosmo
S1* = Se dejan de fabricar 50 equipos para TV Astro
S2* = Se dejan de fabricar 100 equipos para TV Cosmo
S3* = Se dejan de usar 60 horas del Departamento A
S4* = No sobra tiempo en el Departamento B
Z* = La máxima utilidad es de $3600

METODO SIMPLEX – DOS FASES

Cuando tenemos restricciones con >= o con igualdad =

A = Variable artificial. Es la variable básica para restricciones con >= y =

W = Función objetivo sumatorias variables artificiales
Min W = ∑ 𝐴𝑘

Signo S A
holgura Artificial
<= +S -
>= -S +A
= - +A
 METODO SIMPLEX – DOS FASES

Cuando tenemos restricciones con >= o con igualdad =

MAX Z( utilidad) = 3X1 + 2X2

s.a. (1) X1 + X2 >= 4
(2) 3X1 + 4X2 <= 24
X1,X2>=0

FORMA ESTANDAR

(1) X1 + X2 -S1 = 4
(2) 3X1 + 4X2 +S2 = 24
(0) Z -3X1 -2 X2 =0

FORMA BASICA o FORMA CANONICA:

(1) X1 + X2 -S1 +A1 = 4
(2) 3X1 + 4X2 +S2 = 24
(0) Z -3X1 - 2X2 =0
(0)´ (-W) +A1 = 0

Min W = A1
Min W = Max (-W)
Max (-W) = - A1

(0)´´ = (0)´- (1)

(0)´ (-W) +A1 = 0

- (1) -X1 - X2 + S1 -A1 = -4
-----------------------------------------------------
(0)´´ (-W) -X1 -X2 +S1 = -4
 (1) X1 + X2 -S1 +A1 = 4
(2) 3X1 + 4X2 +S2 = 24
(0) Z -3X1 - 2X2 =0
(0)´´ (-W) -X1 - X2 +S1 = -4

FASE 1 FUNCIÓN OBJETIVO W

Primera tabla simplex:

Min Bi/Aij VB Bi X1 X2 S1 S2 A1
4/1 =4 A1 4 1 1 -1 0 1
24/4 =6 S2 24 3 4 0 1 0
xxxxxxxxxxx Z 0 -3 -2 0 0 0
xxxxxxxxxxx -W -4 -1 -1 1 0 0

Variable que entra X2 Variable que sale A1 Numero Pivote 1

segunda tabla simplex:

Min Bi/Aij VB Bi X1 X2 S1 S2 A1
X2 4 1 1 -1 0 1
S2 8 -1 0 4 1 -4
Z 8 -1 0 -2 0 2
-W 0 0 0 0 0 1

FILA NUEVA 2

FPN1 Fila pivote nueva 1 4 1 1 -1 0 1 -4

(+) FA2 Fila antigua 2 24 3 4 0 1 0
(=) FN2 Fila nueva 2 8 -1 0 4 1 -4

FILA NUEVA 0

FPN1 Fila pivote nueva 1 4 1 1 -1 0 1 2

(+) FA0 Fila antigua 0 0 -3 -2 0 0 0
(=) FN0 Fila nueva 0 8 -1 0 -2 0 2

FILA NUEVA 0´´

FPN1 Fila pivote nueva 1 4 1 1 -1 0 1 1

(+) FA0´´ Fila antigua 0´´ -4 -1 -1 1 0 0
 (=) FN0 ´´ Fila nueva 0´´ 0 0 0 0 0 1

FASE 2 FUNCIÓN OBJETIVO Z

Min Bi/Aij VB Bi X1 X2 S1 S2
4/-1 = -4 X2 4 1 1 -1 0
8/4 =2 S2 8 -1 0 4 1
xxxxxxxxxx Z 8 -1 0 -2 0

Entra S1 Sale S2 # Pivote = 4

 METODO SIMPLEX – DOS FASES

Cuando tenemos restricciones con >= o con igualdad =

A = Variable artificial. Es la variable básica para restricciones con >= y =

W = Función objetivo sumatorias variables artificiales

Min W = ∑ 𝐴𝑘

Signo S A
holgura Artificial
<= +S -
>= -S +A
= - +A

EJERCICIO;

MAX Z = 3X1 + 2X2

s.a. (1) 2X1 + 3X2 <= 6
(2) X1 - X2 >= 2
X1,X2>=0

FORMA ESTADAR

(1) 2X1 + 3X2 +S1 = 6

(2) X1 - X2 -S2 = 2
(0) Z-3X1-2X2 = 0

FORMA BASICA
(1) 2X1 + 3X2 +S1 = 6
(2) X1 - X2 -S2 +A2 = 2
(0) Z-3X1 -2X2 = 0
(0)´(-w) +A2 = 0

(0)´Min W=A2 Max (-W)=-A2

NUEVA (0)´´= ANTIGUA (0)´-(2)

(0)´ (-w) +A2 = 0

-(2) -X1 +X2 +S2 -A2 = -2
_----------------------------------------------------
(0)´´(-W) -X1 +X2 +S2 =-2
(1) 2X1 + 3X2 +S1 = 6
(2) X1 - X2 -S2 +A2 = 2
(0) Z-3X1 -2X2 = 0
(0)´´(-W) -X1 +X2 +S2 =-2

S1 A2 Z W
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

Tabla simplex 1
Bi/Aij VB B X1 X2 S1 S2 A2
6/2= 3 S1 6 2 3 1 0 0
2/1=2 A2 2 1 -1 0 -1 1
Z 0 -3 -2 0 0 0
-W -2 -1 1 0 1 0

Variable que entra: X1 Variable que sale: A2

Tabla simplex 2
Bi/Aij VB B X1 X2 S1 S2 A2
S1 2 0 5 1 2 -2
X1 2 1 -1 0 -1 1
Z 6 0 -5 0 -3 3
-W 0 0 0 0 0 1

FILA NUEVA 1

FPN2 Fila pivote nueva 2 2 1 -1 0 -1 1 -2

(+) FA1 Fila antigua 1 6 2 3 1 0 0
(=) FN1 Fila nueva 1 2 0 5 1 2 -2

FILA NUEVA 0

FPN2 Fila pivote nueva 2 2 1 -1 0 -1 1 3

(+) FA0 Fila antigua 0 0 -3 -2 0 0 0
(=) FN0 Fila nueva 0 6 0 -5 0 -3 3

FILA NUEVA 0´´

FPN2 Fila pivote nueva 2 2 1 -1 0 -1 1 1

(+) FA0´´ Fila antigua 0´´ -2 -1 1 0 1 0
(=) FN0´´ Fila nueva 0´´ 0 0 0 0 0 1
Tabla simplex 2
Bi/Aij VB B X1 X2 S1 S2 A2
S1 2 0 5 1 2 -2
X1 2 1 -1 0 -1 1
Z 6 0 -5 0 -3 3
-W 0 0 0 0 0 1

La fase 1
- termina cuando no aparecen en las variables basicas variables artificiales
- Cuando los coeficientes en la fila de W son cero (0) excepto afrtificiales que
tienen coeficiente +1-

Tabla para iniciar la fase 2.

Tabla 1 fase2
Bi/Aij VB B X1 X2 S1 S2
2/5 =0,4 S1 2 0 5 1 2
----------- X1 2 1 -1 0 -1
Z 6 0 -5 0 -3

Variable que entra X2 variable que sale S1 N umero povote 5

Tabla 2 fase 2
Bi/Aij VB B X1 X2 S1 S2
X2 2/5 0 1 1/5 2/5
X1 12 /5 1 0 1/5 -3/5
Z 8 0 0 1 -1

FILA NUEVA 2

FPN1 Fila pivote nueva 1 2/5 0 1 1/5 2/5 1

(+) FA2 Fila antigua 2 2 1 -1 0 -1
(=) FN2 Fila nueva 2 12 /5 1 0 1/5 -3/5

2 2+10 12
+2 = =5
5 5

2 2−5 −3
-1 = =
5 5 5

FILA NUEVA 0

FPN1 Fila pivote nueva 1 2/5 0 1 1/5 2/5 5

(+) FA0 Fila antigua 0 6 0 -5 0 -3
(=) FN0 Fila nueva 0 8 0 0 1 -1
Tabla 2 fase 2
Bi/Aij VB B X1 X2 S1 S2
1 X2 2/5 0 1 1/5 2/5
------ X1 12 /5 1 0 1/5 -3/5
Z 8 0 0 1 -1

ENTRA S2 SALE X2 # PIVOTE= 2/5

Tabla 3 fase 2
Bi/Aij VB B X1 X2 S1 S2
S2 1 0 5/2 1/2 1
------ X1 3 1 3/2 1/2 0
Z 9 0 5/2 3/2 0

FILA NUEVA 2

FPN1 Fila pivote nueva 1 1 0 5/2 1/2 1 3/5

(+) FA2 Fila antigua 2 12 /5 1 0 1/5 -3/5
(=) FN2 Fila nueva 2 3 1 3/2 1/2 0

3 | | 3+2 5
∗ 2+5 = 10 =10
5

FILA NUEVA 0

FPN1 Fila pivote nueva 1 1 0 5/2 1/2 1 1

(+) FA0 Fila antigua 0 8 0 0 1 -1
(=) FN0 Fila nueva 0 9 0 5/2 3/2 0

Tabla optima
Bi/Aij VB B X1 X2 S1 S2
S2 1 0 5/2 1/2 1
------ X1 3 1 3/2 1/2 0
Z 9 0 5/2 3/2 0

X1*=3
X2*=0
S1*=0
S2*=1
Z*=9
 EL ALGORITMO SIMPLEX o METODO SIMPLEX
EJEMPLO:

La Smith Motors, Inc, vende automoviles normales y vagonetas. La Compañía

obtiene $400 de utilidad sobre cada automovil que vende y $600 por cada vagoneta.
El fabricante no puede proveer mas de 300 automoviles ni màs de 200 vagonetas
por mes. El tiempo de preparaciòn para los distribuidores es de 2 horas para cada
automovil y 3 horas para cada vagoneta. La compañía cuenta con 900 horas de
tiempo de taller disponible cada mes para la preparaciòn de automoviles nuevos.
Plantee el problema de PL, resuelva por simplex e intreprete variables.

Recursos Automoviles Vagonetas Disponibilidad

requeridos
Utilidad Unitaria $400 $600
$/unidad
Provision Maximo 300 Maximo 200
fabricante autos vagonetas
Tiempo de 2 hr 3 hr 900 hrs
distribuciòn (hr)

X1= # de automoviles a vender

X2= # de vagonetas a vender

Max Z(Utilidad) = 400X1 +600X2

S,a
(1) X1 <= 300 automoviles
(2) X2 <= 200 vagonetas
(3) 2X1 + 3X2 <= 900 horas de taller
X1,X2 >=0
Aplicando metodo simplex:

Paso 0: Forma Estandar

(1) X1 +S1 =300

(2) X2 +S2 =200
(3) 2X1 + 3X2 +S3=900
(0) Z -400X1 -600X2 =0
Paso 1: Solucion basica factible inicial - Tabla simplex 1

Bi/Aij VB Bi X1 X2 S1 S2 S3
300/0 = & S1= 300 1 0 1 0 0
200/1 =200 S2= 200 0 +1 0 1 0
900/3 =300 S3= 900 2 3 0 0 1
Z= 0 -400 -600 0 0 0

X1=0 X2=0 S1=300 S2=200 S3=900 Z=0

Variables de holgura (S1,S2 y S3)

m= 4 ecuaciones n=6 variables

S1 S2 S3 Z
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1 4X4

Variables basicas = S1,S2,S3, Z

Variables No básicas = X1,X2

Paso 2: Variable a entrar y variable a salir

Variable a entrar min Cj (-400,-600) X2 Columna Pivote

Variable a salir min Bi/Aij (&,200,300) Bi/Aij>=0 y Aij>0 S2 Fila Pivote

Numero Pivote 1

S1 X2 S3 Z
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1 4X4

Paso 3: Encontrar una nueva solución

Tabla simplex 2
Bi/Aij VB Bi X1 X2 S1 S2 S3
S1 300 1 0 1 0 0
X2 200 0 +1 0 1 0
S3 300 2 0 0 -3 1
Z 120000 -400 0 0 600 0
 FILA 1

F2NP Fila 2 nueva pivote 200 0 +1 0 1 0 0

(+) FA1 Fila antigua 1 300 1 0 1 0 0
(=) FN1 Fila nueva 1 300 1 0 1 0 0

Nota: Cuando en una columna pivote aparece 0 los coeficientes de la fila en la siguiente
tabla son iguales.

FILA 3

F2NP Fila 2 nueva pivote 200 0 +1 0 1 0 -3

(+) FA3 Fila antigua 3 900 2 3 0 0 1
(=) FN3 Fila nueva 3 300 2 0 0 -3 1

FILA 0

F2NP Fila 2 nueva pivote 200 0 +1 0 1 0 600

(+) FA0 Fila antigua 0 0 -400 -600 0 0 0
(=) FN0 Fila nueva 0 120000 -400 0 0 600 0

Tabla simplex 2
Bi/Aij VB Bi X1 X2 S1 S2 S3
300/1 = 300 S1 300 1 0 1 0 0
200/0=& = - X2 200 0 +1 0 1 0
300/2=150 S3 300 2 0 0 -3 1
Z 120000 -400 0 0 600 0

Variable que entra X1 Variable que sale S3 Numero Pivote: 2

Tabla simplex 3
Bi/Aij VB Bi X1 X2 S1 S2 S3
S1 150 0 0 1 3/2 -1/2
X2 200 0 +1 0 1 0
X1 150 1 0 0 -3/2 1/2
Z 180000 0 0 0 0 200

FILA 1

F3NP Fila 3 nueva pivote 150 1 0 0 -3/2 1/2 -1

(+) FA1 Fila antigua 1 300 1 0 1 0 0
(=) FN1 Fila nueva 1 150 0 0 1 3/2 -1/2
 FILA 0

F3NP Fila 3 nueva pivote 150 1 0 0 -3/2 1/2 400

(+) FA0 Fila antigua 0 120000 -400 0 0 600 0
(=) FN0 Fila nueva 0 180000 0 0 0 0 200

Tabla Optima
Bi/Aij VB Bi X1 X2 S1 S2 S3
150 3 S1= 150 0 0 1 3/2 -1/2
/ 2= 100
1
200/1=200 X2= 200 0 +1 0 1 0
--------- X1= 150 1 0 0 -3/2 1/2
Z= 180000 0 0 0 0 200
Solución óptima:

X1*=Se deben vender 150 automóviles

X2*=Se deben vender 200 vagonetas
S1*= Se dejan de vender 150 automóviles
S2*=0 No se dejan den vender vagonetas
S3*= 0 No sobra tiempo de taller para la distribución
Z*= La máxima utilidad es de $180.000

Solución optima múltiple: Se presenta cuando en la tabla optima en la función objetivo

(Ecuación 0) una variable no básica tiene el valor de cero (0).

Variable que entra S2

Variable que sale S1
Numero pivote 3/2
𝟑 𝟐
∗ 𝟑=1
𝟐

Tabla optima múltiple:

Bi/Aij VB Bi X1 X2 S1 S2 S3
S2 100 0 0 2/3 1 -1/3
X2 100 0 1 -2/3 0 1/3
X1 300 1 0 1 0 0
Z 180000 0 0 0 0 200

FILA 2

F1NP Fila 1 nueva pivote 100 0 0 2/3 1 -1/3 -1

(+) FA2 Fila antigua 2 200 0 +1 0 1 0
(=) FN2 Fila nueva 2 100 0 1 -2/3 0 1/3
FILA 3

F1NP Fila 1 nueva pivote 100 0 0 2/3 1 -1/3 3/2

(+) FA3 Fila antigua 3 150 1 0 0 -3/2 1/2
(=) FN3 Fila nueva 3 300 1 0 1 0 0

𝟑 −𝟏 𝟏 𝟏 𝟏
∗ +𝟐 = − 𝟐 + 𝟐= 0
𝟐 𝟑

FILA 0

F1NP Fila 1 nueva pivote 100 0 0 2/3 1 -1/3 0

(+) FA0 Fila antigua 0 180000 0 0 0 0 200
(=) FN0 Fila nueva 0 180000 0 0 0 0 200

Tabla optima múltiple 2:

Bi/Aij
VB Bi X1 X2 S1 S2 S3
S2 100 0 0 2/3 1 -1/3
X2 100 0 1 -2/3 0 1/3
X1 300 1 0 1 0 0
Z 180000 0 0 0 0 200
Z*=La máxima utilidad es de $180000
X1*=Se deben vender 300 automóviles
X2*= Se deben vender 100 vagonetas
S1*= 0 No se dejan de vender automóviles
S2*= Se dejan de vender 100 vagonetas
S3*=0. No sobra tiempo de taller de distribución
 METODO SIMPLEX – DOS FASES

Cuando tenemos restricciones con >= o con igualdad =

A = Variable artificial. Es la variable básica para restricciones con >= y =

W = Función objetivo sumatorias variables artificiales

Min W = ∑ 𝐴𝑘

Signo S A
holgura Artificial
<= +S -
>= -S +A
= - +A

EJERCICIO;

MAX Z = 3X1 - 2X2

s.a. (1) 2X1 + 3X2 <= 6
(2) X1 - X2 >= 2
X1,X2>=0
Restricción 1
X1 X2
0 2
3 0

Restricción 2
X1 X2
0 -2
2 0
 EL ALGORITMO SIMPLEX o METODO SIMPLEX
EJEMPLO:

La Smith Motors, Inc, vende automoviles normales y vagonetas. La Compañía

obtiene $400 de utilidad sobre cada automovil que vende y $600 por cada vagoneta.
El fabricante no puede proveer mas de 300 automoviles ni màs de 200 vagonetas
por mes. El tiempo de preparaciòn para los distribuidores es de 2 horas para cada
automovil y 3 horas para cada vagoneta. La compañía cuenta con 900 horas de
tiempo de taller disponible cada mes para la preparaciòn de automoviles nuevos.
Plantee el problema de PL, resuelva por simplex e intreprete variables.

Recursos Automoviles Vagonetas Disponibilidad

requeridos
Utilidad Unitaria $400 $600
$/unidad
Provision Maximo 300 Maximo 200
fabricante autos vagonetas
Tiempo de 2 hr 3 hr 900 hrs
distribuciòn (hr)

X1= # de automoviles a vender

X2= # de vagonetas a vender

Max Z(Utilidad) = 400X1 +600X2

S,a
(1) X1 <= 300 automoviles
(2) X2 <= 200 vagonetas
(3) 2X1 + 3X2 <= 900 horas de taller
X1,X2 >=0
Aplicando metodo simplex:

Paso 0: Forma Estandar

(1) X1 +S1 =300

(2) X2 +S2 =200
(3) 2X1 + 3X2 +S3=900
(0) Z -400X1 -600X2 =0
Paso 1: Solucion basica factible inicial - Tabla simplex 1

Bi/Aij VB Bi X1 X2 S1 S2 S3
300/0 = & S1= 300 1 0 1 0 0
200/1 =200 S2= 200 0 +1 0 1 0
900/3 =300 S3= 900 2 3 0 0 1
Z= 0 -400 -600 0 0 0

X1=0 X2=0 S1=300 S2=200 S3=900 Z=0

Variables de holgura (S1,S2 y S3)

m= 4 ecuaciones n=6 variables

S1 S2 S3 Z
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1 4X4

Variables basicas = S1,S2,S3, Z

Variables No básicas = X1,X2

Paso 2: Variable a entrar y variable a salir

Variable a entrar min Cj (-400,-600) X2 Columna Pivote

Variable a salir min Bi/Aij (&,200,300) Bi/Aij>=0 y Aij>0 S2 Fila Pivote

Numero Pivote 1

S1 X2 S3 Z
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1 4X4

Paso 3: Encontrar una nueva solución

Tabla simplex 2
Bi/Aij VB Bi X1 X2 S1 S2 S3
S1 300 1 0 1 0 0
X2 200 0 +1 0 1 0
S3 300 2 0 0 -3 1
Z 120000 -400 0 0 600 0
 FILA 1

F2NP Fila 2 nueva pivote 200 0 +1 0 1 0 0

(+) FA1 Fila antigua 1 300 1 0 1 0 0
(=) FN1 Fila nueva 1 300 1 0 1 0 0

Nota: Cuando en una columna pivote aparece 0 los coeficientes de la fila en la siguiente
tabla son iguales.

FILA 3

F2NP Fila 2 nueva pivote 200 0 +1 0 1 0 -3

(+) FA3 Fila antigua 3 900 2 3 0 0 1
(=) FN3 Fila nueva 3 300 2 0 0 -3 1

FILA 0

F2NP Fila 2 nueva pivote 200 0 +1 0 1 0 600

(+) FA0 Fila antigua 0 0 -400 -600 0 0 0
(=) FN0 Fila nueva 0 120000 -400 0 0 600 0

Tabla simplex 2
Bi/Aij VB Bi X1 X2 S1 S2 S3
300/1 = 300 S1 300 1 0 1 0 0
200/0=& = - X2 200 0 +1 0 1 0
300/2=150 S3 300 2 0 0 -3 1
Z 120000 -400 0 0 600 0

Variable que entra X1 Variable que sale S3 Numero Pivote: 2

Tabla simplex 3
Bi/Aij VB Bi X1 X2 S1 S2 S3
S1 150 0 0 1 3/2 -1/2
X2 200 0 +1 0 1 0
X1 150 1 0 0 -3/2 1/2
Z 180000 0 0 0 0 200

FILA 1

F3NP Fila 3 nueva pivote 150 1 0 0 -3/2 1/2 -1

(+) FA1 Fila antigua 1 300 1 0 1 0 0
(=) FN1 Fila nueva 1 150 0 0 1 3/2 -1/2
 FILA 0

F3NP Fila 3 nueva pivote 150 1 0 0 -3/2 1/2 400

(+) FA0 Fila antigua 0 120000 -400 0 0 600 0
(=) FN0 Fila nueva 0 180000 0 0 0 0 200

Tabla Optima
Bi/Aij VB Bi X1 X2 S1 S2 S3
S1= 150 0 0 1 3/2 -1/2
X2= 200 0 +1 0 1 0
X1= 150 1 0 0 -3/2 1/2
Z= 180000 0 0 0 0 200
Solución óptima:

X1*=Se deben vender 150 automóviles

X2*=Se deben vender 200 vagonetas
S1*= Se dejan de vender 150 automóviles
S2*=0 No se dejan den vender vagonetas
S3*= 0 No sobra tiempo de taller para la distribución
Z*= La máxima utilidad es de $180.000
 EL ALGORITMO SIMPLEX o METODO SIMPLEX

EJEMPLO:

Una empresa produce dos tipos de comedor americano Virginia y Massachusett,

logrando una utilidad unitaria de $200 y $240 respectivamente. Los comedores
requieren tiempo de construccion y pintura según informacion dada en la siguiente
tabla:
Recursos Comedor Comedor Disponibilidad
requeridos Virginia Massachusett
Tiempo de 6 12 120 h
construccion (hr)
Tiempo de 8 4 64 h
Pintura (hr)
Utilidad Unitaria $200 $240
$/unidad

- Formule el modelo de Programacion Lineal

- Resuelva por el metodo simplex
- Interprete variables

X1= # de comedores Virginia a producir

X2= # de comedores Massachusett a producir

Max Z(Utilidad) = 200X1 +240X2

S,a
(1) 6X1 +12X2 <= 120 hrs construcción
(2) 8X1 + 4X2 <= 64 hrs pintura
X1,X2 >=0

Paso 0: Forma Estandar

(1) 6X1 +12X2 +S1 = 120

(2) 8X1 + 4X2 +S2 = 64
(0) Z -200X1-240X2 = 0

Paso 1: Solucion basica factible inicial - Tabla simplex 1

Bi/Aij VB B X1 X2 S1 S2 Z
S1= 120 6 12 1 0 0
S2= 64 8 4 0 1 0
 Z= 0 -200 -240 0 0 1

X1=0 X2=0 S1=120 S2=64 Z=0

Variables de holgura (S1 y S2)

m= 3 ecuaciones n=5 variables

S1 S2 Z
1 0 0
0 1 0
0 0 1 3x3

Variables basicas = S1,S2,Z

Variables No básicas = X1,X2

Paso 1; Solucion basica factible inicial

(X1,X2,S1,S2,Z) = (0,0,120,64,0)

Paso 2: Variable a entrar y variable a salir

Variable a entrar min Cj (-200,-240) X2 Columna Pivote

Variable a salir min Bi/Aij (10,16) Bi/Aij>=0 y Aij>0 S1 Fila Pivote

Tabla 1
Bi/Aij VB Bi X1 X2 S1 S2
120/12=10 S1= 120 6 12 1 0
64/4=16 S2= 64 8 4 0 1
Z= 0 -200 -240 0 0

X2 S2 Z
1 0 0
0 1 0
0 0 1 3x3

# Pivote es la imntrerseccion entre la columna y la fila =12

Paso 3: Encontrar una nueva solución

Tabla 2
 Bi/Aij VB Bi X1 X2 S1 S2
X2 10 1/2 1 1/12 0
S2 24 6 0 -1/3 1
Z 2400 -80 0 20 0

FILA 2

F1NP Fila 1 nueva pivote 10 1/2 1 1/12 0 -4

(+) FA2 Fila antigua 2 64 8 4 0 1
(=) FN2 Fila nueva 2 24 6 0 -1/3 1

1
*- 4 = -2
2

−4 −1
=3
12

FILA 0

F1NP Fila 1 nueva pivote 10 1/2 1 1/12 0 240

(+) FA0 Fila antigua 0 0 -200 -240 0 0
(=) FN0 Fila nueva 0 2400 -80 0 20 0

Tabla 2

Bi/Aij VB Bi X1 X2 S1 S2
1𝟎 1 X2 10 1/2 1 1/12 0
/ = 20
𝟏 2
24/6 =4 S2 24 6 0 -1/3 1
Z 2400 -80 0 20 0

Variable que entra =X1

Variable que sale = S2 MIN(20,4)
Numero Pivote = 6
X2 X1 Z
1 0 0
0 1 0
0 0 1 3x3
Tabla 3
Bi/Aij VB Bi X1 X2 S1 S2
X2 8 0 1 1/9 -1/12
X1 4 1 0 -1/18 1/6
Z 2720 0 0 140/9 40/3
FILA 1
 F2NP Fila 2 nueva pivote 4 1 0 -1/18 1/6 -1/2
(+) FA1 Fila antigua 1 10 1/2 1 1/12 0
(=) FN1 Fila nueva 1 8 0 1 1/9 -1/12

−1 −1 1 1 1 1+3 4 1
* 18 + 12 =36+12¨= =36=9
2 36

FILA 0

F2NP Fila 2 nueva pivote 4 1 0 -1/18 1/6 80

(+) FA0 Fila antigua 0 2400 -80 0 20 0
(=) FN0 Fila nueva 0 2720 0 0 140/9 40/3

80 −1 −80 −40 −40+180 140

* 18 + 20 = 18 +20 = +20= =
1 9 9 9

Tabla Optima
Bi/Aij VB Bi X1 X2 S1 S2
X2 8 0 1 1/9 -1/12
X1 4 1 0 -1/18 1/6
Z 2720 0 0 140/9 40/3

Interpretar variables:
X1*= Se deben fabricar 4 comedores virginia
X2*= Se deben fabricar 8 comedores massachusett
S1*=0 No sobran horas de construcción
S2*=0 No sobran horas de pintura
Z*=$2720 La máxima utilidad es de $2720
 EL ALGORITMO SIMPLEX o METODO SIMPLEX

Procedimiento iterativo que da una solución óptima a un problema de programación lineal. El

método consiste en encontrar el valor de la función objetivo donde se optimice.

MAX Z = ∑ CjXj

s.a. ∑ ∑ AijXj <= Bi

Xj>=0
i=1….m contador de restricción.

j=1….n contador de variables.

Cj = beneficio por unidad de j

Xj = Variable de decisión j o nivel de actividad

Z =f(Xj)= Función objetivo

Bi = disponibilidad del recurso i

Aij =Cantidad del recurso i para realizar la actividad j

Variable de holgura S: Es el valor que se suma a una restricción con signo <= para convertirla en
igualdad.

(1) A11 X1 + A12 X2 + ….+ A1n Xn <= B1

(1) A11 X1 + A12 X2 + ….+ A1n Xn + S1 = B1

10 <= 15

10 + 5 = 15

Variable superflua (Holgura S que resta): Es el valor que se resta a una restricción con signo >=,
para convertirla en igualdad.

(1) A11 X1 + A12 X2 + ….+ A1n Xn >= B1

(1) A11 X1 + A12 X2 + ….+ A1n Xn - S1 = B1

EJ:
18 >=14
18 - 4 =14
Matriz identidad o canónica 0 BASE

X1 X2 X3 X4
1 0 0 0
0 1 0 0
0 0 1 0 4x4
0 0 0 1

Variable básica (m): Es cada una de las m ecuaciones y su valor siempre será igual al termino
independiente(Bi).

Variable no básica (n-m): Es cada una de las n-m variables y su valor siempre será igual a cero.

m = # Ecuaciones

n= # de Variables

EJEMPLO: Sistema de ecuaciones

(1) X1 + 3X2 +X3 = 500

(2) 6X1 -3X2 + X4 =400
(3) 4X1 + 6X2 +X5 =200
(4) 2X1- 3X2 +X6=100

Tabla Simplex
VB B X1 X2 X3 X4 X5 X6
X3= 500 1 3 1 0 0 0
X4= 400 6 -3 0 1 0 0
X5= 200 4 6 0 0 1 0
X6= 100 2 -3 0 0 0 1

Bi = Termino independiente
VB = Variable básica

m= 4 ecuaciones

n= 6 variables

X3 X4 X5 X6
1 0 0 0
0 1 0 0
0 0 1 0 4x4
0 0 0 1
Variables básicas. Son las que pertenecen a la matriz identidad (X3,X4,X5,X6)

Variables NO básicas: Las que no pertenecen la matriz identidad.

n-m = 6-4= 2 variables NO básicas (X1,X2)

Solución básica factible (punto extremo de la región factible)

Vector solución (X1,X2,X3,X4,X5,X6) =(0,0,500,400,200,200)

Modelo de Programación Lineal:

MAX Z = ∑ CjXj MAX Z =C1X1+C2X2 (0) Z-C1X1-C2X2=0

s.a. ∑ ∑ AijXj <= Bi

Xj>=0
i=1….m contador de restricción.

j=1….n contador de variables

PASO O. Forma Estándar: Convertir desigualdades a igualdades.

Adicione las variables de holgura o de excedente a todas las inecuaciones. (Bi >= 0)
Para hallar un canónico se requiere que en cada una de las ecuaciones exista una variable
con coeficiente (+1) y en las otras ecuaciones haya como coeficiente cero (0).
Matriz identidad o canónico: BASE

S1 S2 Z
1 0 0
0 1 0
0 0 1 3x3

X1 X2 VNB variables no básicas

Bi/Aij VB B X1 X2 S1 S2 Z
B1/A12 S1 B1 A11 A12 1 0 0
B2/A22 S2 B2 A21 A22 0 1 0
Z 0 -C1 -C2 0 0 1

Entra X2 y sale S1

VB = Variable básica
Bi termino independiente

PASO 1.
Encontrar una solución básica factible inicial.

(X1,X2,S1,S2,Z) = (0,0,B1,B2,0)

PASO 2.
Encontrar una S.B.F. mejor que aporte mayor utilidad.

2.1 Variable a entrar: Escogemos una variable no básica que se convertirá en variable
básica entrante; con el coeficiente más negativo en la función objetivo. (Min Cj Cj >0).
Esta columna se llama columna Pivote: Columna de coeficientes asociados con la
variable no básica que se convertirá en variable básica entrante.

2.2 Variable a salir:

2.2.1 Seleccione en la columna Pivote cada coeficiente que sea estrictamente positivo
(Ai j>0).

2.2.2 Dividir el segundo miembro (Bi) de cada fila entre cada uno de estos coeficientes de
su misma fila (Aij). (Bi/Aij).

2.2.3 Identificar la fila que tenga la menor de estas razones

(Min Bi/Aij Bi>=0 y Aij>0).
2.2.4 Sale la variable básica de esta fila y entra una variable básica que tome un valor más
grande.
La fila de la variable básica saliente con la menor razón la llamaremos Fila Pivote.
El coeficiente que está en la intersección de la columna y Fila Pivote lo llamamos
número Pivote.

PASO 3:
Resuelva la nueva solución factible.
3.1 El número Pivote debe ser convertido a+1 y la variable básica entrante reemplaza la
variable básica saliente.

3.2 Cada uno de los coeficientes restantes en la columna Pivote tiene que ser convertido
a cero.

3.3 Encontrar una nueva tabla:

FILA PIVOTE NUEVA * (-) NUMERO DE LA COLUMNA PIVOTE

(+) FILA ANTIGUA
-------------------------------
(=) FILA NUEVA

3.4 Si analizamos Cj - Si es menor que cero vaya al paso 2

- Si es mayor que cero (o igual), vaya al paso 4.

PASO 4. La solución básica factible es la óptima y se puede determinar el resultado.

EJEMPLO:

Una empresa produce dos tipos de comedor americano Virginia y Massachusett,

logrando una utilidad unitaria de $200 y $240 respectivamente. Los comedores
requieren tiempo de construccion y pintura según informacion dada en la siguiente
tabla:
Recursos Comedor Comedor Disponibilidad
requeridos Virginia Massachusett
Tiempo de 6 12 120 h
construccion (hr)
Tiempo de 8 4 64 h
Pintura (hr)
Utilidad Unitaria $200 $240
$/unidad

- Formule el modelo de Programacion Lineal

- Resuelva por el metodo simplex
- Interprete variables

X1= # de comedores Virginia a producir

X2= # de comedores Massachusett a producir

Max Z(Utilidad) = 200X1 +240X2

S,a
(1) 6X1 +12X2 <= 120 hrs construcción
(2) 8X1 + 4X2 <= 64 hrs pintura
X1,X2 >=0

Paso 0: Forma Estandar

(1) 6X1 +12X2 +S1 = 120

(2) 8X1 + 4X2 +S2 = 64
(0) Z -200X1-240X2 = 0

Variables de holgura (S1 y S2)

m= 3 ecuaciones n=5 variables

S1 S2 Z
1 0 0
0 1 0
0 0 1 3x3

Variables basicas = S1,S2,Z

Variables No básicas = X1,X2

Paso 1; Solucion basica factible inicial

(X1,X2,S1,S2,Z) = (0,0,120,64,0)