Método Algebraico

Hallar la solución óptima por el método algebraico de los siguientes

modelos matemáticos:

a) Max Z = 4X1 + 3X2

S.A.: 3X1 + 5X2 ≤ 15

5X1 + 2X2 ≤ 10

X1, X2 ≥0

Solución:

Llevamos a la forma canónica del modelo a la forma estándar.

Max Z = 4X1 + 3X2 + 0X3 + 0X4

S.A.: 3X1 + 5X2 + X3 = 15

5X1 + 2X2 + X4 = 10

X1, X2, X3, X4 ≥0

Escribimos la matriz y vectores correspondientes al modelo

 Vector fila de costo: c(c1, c2, c3, …, cn)

c = (4, 3, 0, 0)
𝑎11 𝑎12 𝑎13 … 𝑎1𝑛
𝑎21 𝑎22 𝑎23 … 𝑎2𝑛
.
 Matriz de coeficientes: A =
.
.
(𝑎𝑚1 𝑎𝑚2 𝑎𝑚3 … 𝑎𝑚𝑛)
 a1 a2 a3 a4

3 5 1 0
A=( )
5 2 0 1

De la matriz se desprende los siguientes vectores:

3
a1 = ( )
5
5
a2 = ( )
2
1
a3 = ( )
0
0
a4 = ( )
1
𝑏1
𝑏2
𝑏3
 Vector columna de requerimientos o disponibilidades: b = .
.
.
(𝑏𝑚)

15
b=( )
10

𝑥1
𝑥2
𝑥3
 Vector columna de variables: x = .
.
.
(𝑥𝑛)

𝑥1
𝑥2
x=( )
𝑥3
𝑥4
Posibles bases:

3 5
B1 = (a1, a2) = [ ]
5 2
3 1
B2 = (a1, a3) = [ ]
5 0
3 0
B3 = (a1, a4) = [ ]
5 1
5 1
B4 = (a2, a3) = [ ]
2 0
5 0
B5 = (a2, a4) = [ ]
2 1
1 0
B6 = (a3, a4) = [ ]
0 1

B6 = Matriz de identidad: esta matriz es la que tiene inicialmente las

variables básicas o sea X3 Y X4, mientras que inicialmente en el modelo
estándar, X1 Y X2 constituyen las variables no básicas.

B6 = (a3, a4)

Su inversa sería B6-1

B6-1 = Adj Bij/|𝐵𝑖𝑗|

Adj Bij = ‖𝐵𝐼𝐽‖T

1 0T
B6-1 =
1
=[ ]
1𝑋1−0𝑋0 0 1

Luego tenemos que

1 0
B6-1 =
1
[ ]
1 0 1
 𝟏 𝟎
B6-1 = [ ]
𝟎 𝟏

Calculo de xB y Z

xB = B-1b

Z = cB xB

𝟏 𝟎 𝟏𝟓
xB = [ ]( )
𝟎 𝟏 𝟏𝟎

15x1 + 10x0 = 15

15x0 + 10x1 = 10

𝟏𝟓 𝒙𝟑
xB = ( ) = ( )
𝟏𝟎 𝒙𝟒

CB = (c3, c4)

𝟏𝟓
Z = (0, 0) ( )
𝟏𝟎

Z = 15x0 + 10x0 = 0

Z = 0

Determinamos que variable entra y que variable sale (que variable no

básica pasa a ser básica)

Yj = Bk-1aj

Y1 = B6-1x a1

𝟏 𝟎 𝟑
Y1 = [ ]( )
𝟎 𝟏 𝟓

3x 1 + 5x0 = 3

3x0 + 5x1 = 5
 𝟑
Y1 = ( )
𝟓

Y2 = B6-1x a2

𝟏 𝟎 𝟓
Y2 = [ ]( )
𝟎 𝟏 𝟐

5x1 + 2x0 = 5

5x0 + 2x1 = 2

𝟓
Y2 = ( )
𝟐

z1 – c1 = cBy1 –c1

𝟑
z1 – c1 = (0, 0) ( ) – 4
𝟓

0x3 + 0x5 - 4 = 0

z1 – c1 = - 4

z2 – c2 = cBy2 –c2

𝟓
z2 – c2 = (0, 0) ( ) - 3
𝟐

0x5 + 0x2 – 3 = 0

z2 – c2 = - 3

Para maximización el valor que entra es el menor de los negativos, es

decir, se debe cumplir la siguiente condición: zj – cj < 0

Variable que entra: a1 (z1 – c1 = -4)

Variable que entra: a1

Variable que sale: ?

Xbi/yik; yik > 0

𝟏𝟓 𝟑
xB = ( ); Y1 = ( )
𝟏𝟎 𝟓

Por qué y1?

Porque la variable que entró fue a1.

15/3 = 5

XB/y1:

10/5 = 2 b2

En maximización el valor que sale es el menor de los positivos, es decir

se debe cumplir con la siguiente condición:

xBr/yrk = mini xBi/yik; yik > 0

Variable que sale: b2 a4

Variable que sale: a4

Nueva base
𝟏 𝟎
Teníamos B6 = [ ] sale a4, entra a1
𝟎 𝟏
𝟏 𝟑
Ahora la nueva base es B1, B1 = [ ]
𝟎 𝟓
 B1 = (a3, a1)

Inversa de B1

5 0T
B1-1 =
1
[ ]
1𝑋5−3𝑋0 −3 1

Luego tenemos que

5 −3
B1-1 =
1
[ ]
5 0 1
𝟏 −𝟑/𝟓
B1-1 = [ ]
𝟎 𝟏/𝟓

Calculamos xB y z

XB = B1-1 b
𝟏 −𝟑/𝟓 𝟏𝟓
XB = [ ]( )
𝟎 𝟏/𝟓 𝟏𝟎

1x15 + (-3/5) (10) = 15 – 6 = 9

0x15 + 1/5x 10 = 2

𝟗 𝒙𝟑
xB = ( ) = ( )
𝟐 𝒙𝟏

Z = cB xB

cB = (c3, c1) = (0, 4)

𝟗
Z = (0, 4) ( )
𝟐

Z = 0x9 + 4x2

Z = 8
Qué variable entra?

Y4 = B1-1x a4

𝟏 −𝟑/𝟓 𝟎
Y4 = [ ]( )
𝟎 𝟏/𝟓 𝟏

1x0 - 3/5x1 = -3/5

0x0 + 1/5x1 = 1/5

−𝟑/𝟓
Y4 = ( )
𝟏/𝟓

Y2 = B1-1x a2

𝟏 −𝟑/𝟓 𝟓
Y2 = [ ]( )
𝟎 𝟏/𝟓 𝟐

5x1 -3/5x2 = 19/5

5x0 + 1/5x2 = 2/5

𝟏𝟗/𝟓
Y2 = ( )
𝟐/𝟓

z4 – c4 = cBy4 – c4

cB = (c3, c1) = (0, 4)

c4 = 0

−𝟑/𝟓
z4 – c4 = (0, 4) ( )-0
𝟏/𝟓

-3/5x0 + 1/5x4 -0 = 4/5 ≈ 0,8

z4 – c4 = 4/5 ≈ 0,8

z2 – c2 = cBy2 – c2
c2 = 3
𝟏𝟗/𝟓
z2 – c2 = (0, 4) ( ) - 3
𝟐/𝟓

0x19/5 + 4x2/5 – 3

0 + 8/5 – 3 = (8 – 15)/5 = -7/5

z2 – c2 = -7/5
Variable que entra: a2

¿Qué variable sale?

Xbi/yik; yik > 0

𝟗 𝟏𝟗/𝟓
xB = ( ); Y2 = ( )
𝟐 𝟐/𝟓

Por qué y2?

Porque la variable que entró fue a2.

9/19/5 = 45/19 ≈ 1.9 b1

XB/y2:

2/2/5 = 5

Variable que sale: b1 a3

Variable que sale: a3

Nueva base
𝟏 𝟑
Teníamos B1 = [ ] sale a3 y entra a2
𝟎 𝟓

Ahora tenemos: B2 = (a2, a1)

𝟓 𝟑
B2 = [ ]
𝟐 𝟓

La inversa de B2 seria B2-1

5 −2 T
B2-1 =
1
[ ]
5𝑋5−3𝑋2 −3 5
5 −3
B2-1 =
1
[ ]
25−6 −2 5
5 −3
B2-1 =
1
[ ]
19 −2 5
5 −3
B2-1 =
1
=[ ]
19 −2 5
5/19 −3/19
B2-1 = [ ]
−2/19 5/19

Calculamos xB y z nuevamente

xB = B2-1b

𝟓/𝟏𝟗 −𝟑/𝟏𝟗 𝟏𝟓
XB = [ ]( )
−𝟐/𝟏𝟗 𝟓/𝟏𝟗 𝟏𝟎

5/19x15 -3/19x10 = 75/19 -30/19 = 45/19

-2/19x15 + 5/19x10 = -30/19 + 50/19 = 20/19

𝟒𝟓/𝟏𝟗 𝒙𝟐
xB = ( ) = ( )
𝟐𝟎/𝟏𝟗 𝒙𝟏

Z = cBxB
 𝟒𝟓/𝟏𝟗
Z = (3, 4) ( )
𝟐𝟎/𝟏𝟗

Z = 3x45/19 + 4x20/19 = (135 + 80)/19

Z = 215/19

¿Entrará y saldrá otra variable?; ¿cómo saberlo?

Y4 = b2-1 a4

𝟓/𝟏𝟗 −𝟑/𝟏𝟗 𝟎
Y4 = [ ]( )
−𝟐/𝟏𝟗 𝟓/𝟏𝟗 𝟏

5/19x0 - 3/19x1 = -3/19

-2/19x0 + 5/19x1 = 5/19

𝟑
−
Y4 = [ 𝟏𝟗
𝟓 ]
𝟏𝟗

Y3 = B2-1a3

𝟓/𝟏𝟗 −𝟑/𝟏𝟗 𝟏
Y3 = [ ]( )
−𝟐/𝟏𝟗 𝟓/𝟏𝟗 𝟎

5/19x1 - 3/19x0 = 5/19

-2/19x1 + 5/19x0 = -2/19

𝟓

Y3 = [ 𝟏𝟗
𝟐 ]
−
𝟏𝟗

z4 – c4 = cBy4 – c4
𝟑
−
z4 – c4 = (3, 4) [ 𝟏𝟗
𝟓 ]
- 0
𝟏𝟗
z4 – c4 = 3x(-3/19) + 4x(5/19) - 0

z4 – c4 = 11/19

z3 – c3 = cBy3 – c3
𝟓

z3 – c3 = (3, 4) [ 𝟏𝟗
𝟐 ] - 0
−
𝟏𝟗

z3 – c3 = 3x5/19 + 4 x (-2/19) - 0

z3 – c3 = 7/19

No entra ninguna variable ya que ambos valores son positivos. Por lo

tanto no sale ninguna variable. Por lo tanto:

Solución optima

Z = 215/19

X1 = 20/19

X2 = 45/19
b) Min Z = -X1 -3X2

S.A. X1 – X2 ≤ 4

-X1 + X2 ≤ 3

X 1 , X2 ≥ 0

Solución

Llevamos a la forma canónica del modelo a la forma estándar.

Min Z = -X1 - 3X2 + 0X3 + 0X4

S.A.: X1 -2X2 + X3 = 4

-X1 + X2 + X4 = 3

X1, X2, X3, X4 ≥0

Escribimos la matriz y vectores correspondientes al modelo

 Vector fila de costo: c(c1, c2, c3, …, cn)

c = (-1, -3, 0, 0)
𝑎11 𝑎12 𝑎13 … 𝑎1𝑛
𝑎21 𝑎22 𝑎23 … 𝑎2𝑛
.
 Matriz de coeficientes: A =
.
.
(𝑎𝑚1 𝑎𝑚2 𝑎𝑚3 … 𝑎𝑚𝑛)

a1 a2 a3 a4

1 −2 1 0
A=( )
−1 1 0 1
De la matriz se desprende los siguientes vectores:
1
a1 = ( )
−1
−2
a2 = ( )
1
1
a3 = ( )
0
0
a4 = ( )
1
𝑏1
𝑏2
𝑏3
 Vector columna de requerimientos o disponibilidades: b = .
.
.
(𝑏𝑚)

4
b=( )
3

𝑥1
𝑥2
𝑥3
 Vector columna de variables: x = .
.
.
(𝑥𝑛)

𝑥1
𝑥2
x=( )
𝑥3
𝑥4
Posibles bases:

3 −1
B1 = (a1, a2) = [ ]
−1 1
1 1
B2 = (a1, a3) = [ ]
−1 0
1 0
B3 = (a1, a4) = [ ]
−1 1
−2 1
B4 = (a2, a3) = [ ]
1 0
−2 0
B5 = (a2, a4) = [ ]
1 1
1 0
B6 = (a3, a4) = [ ]
0 1

B6 = Matriz de identidad: esta matriz es la que tiene inicialmente las

variables básicas o sea X3 Y X4, mientras que inicialmente en el modelo
estándar, X1 Y X2 constituyen las variables no básicas.

B6 = (a3, a4)

Su inversa sería B6-1

B6-1 = Adj Bij/|𝐵𝑖𝑗|

Adj Bij = ‖𝐵𝑖𝑗‖T

1 0T
B6-1 =
1
=[ ]
1𝑋1−0𝑋0 0 1

Luego tenemos que

1 0
B6-1 =
1
[ ]
1 0 1
𝟏 𝟎
B6-1 = [ ]
𝟎 𝟏
Calculo de xB y Z

xB = B-1b

Z = cB xB

𝟏 𝟎 𝟒
xB = [ ]( )
𝟎 𝟏 𝟑

4x1 + 3x0 = 4

4x0 + 3x1 = 3

𝟒 𝒙𝟑
xB = ( ) = ( )
𝟑 𝒙𝟒

cB =(c3, c4)

𝟒
Z = (0, 0) ( )
𝟑

Z = 4x0 + 3x0 = 0

Z = 0

Determinamos que variable entra y que variable sale (que variable no

básica pasa a ser básica)

Yj = Bk-1aj

Y1 = B6-1x a1

𝟏 𝟎 𝟏
Y1 = [ ]( )
𝟎 𝟏 −𝟏

1x 1 + 0x(-1) = 1

0x1 + 1x(-1) = -1

𝟏
Y1 = ( )
−𝟏
Y2 = B6-1x a2

𝟏 𝟎 −𝟐
Y2 = [ ]( )
𝟎 𝟏 𝟏

1x(-2) + 0x1 = -2

0x(-2) + 1x1 = 1

−𝟐
Y2 = ( )
𝟏

Luego se tiene que:

z1 – c1 = cBy1 –c1

𝟏
z1 – c1 = (0, 0) ( ) – (-1)
−𝟏

0x1 + 0x(-1) + 1 = 0

z1 – c1 = 1

z2 – c2 = cBy2 –c2

−𝟐
z2 – c2 = (0, 0) ( ) – (-3)
𝟏

0x(-2) + 0x1 + 3

z2 – c2 = 3

Para minimización el valor que entra es el mayor de los positivos, es

decir, se debe cumplir la siguiente condición: zj – cj > 0

Variable que entra: a2 (z1 – c2 = 3)

Variable que entra: a2

¿Variable que sale: ?

Xbi/yik; yik > 0

𝟒 −𝟐
xB = ( ); Y2 = ( )
𝟑 𝟏

¿Por qué y2?

Porque la variable que entró fue a2.

4/(-2) = -2

XB/y2:

3/1 = 3 b2

En minimización el valor que sale es el menor de los positivos, es decir

se debe cumplir con la siguiente condición:

xBr/yrk = mini xBi/yik; yik ≥ 0

Variable que sale: b2 a4

Variable que sale: a4

Nueva base
𝟏 𝟎
Teníamos B6 = [ ] , sale a4, entra a2
𝟎 𝟏

Ahora la nueva base es B1 = (a3, a2)

 𝟏 −𝟐
B1 = [ ]
𝟎 𝟏

Su inversa sería B1-1

B1-1 = Adj Bij/|𝐵𝑖𝑗|

Adj Bij = ‖𝐵𝑖𝑗‖T

1 0T
B1-1 =
1
x[ ]
1𝑋1−0𝑋(−2) 2 1
𝟏 𝟐
B1-1 = [ ]
𝟎 𝟏

Calculamos xB y Z

XB = B1-1 b
𝟏 𝟐 𝟒
XB = [ ]( )
𝟎 𝟏 𝟑

1x4 + 2x 3 = 10

0x4 + 1x 3 = 3

𝟏𝟎 𝒙𝟑
xB = ( ) = ( )
𝟑 𝒙𝟐

Z = cB xB

cB = (c3, c2) = (0, -3)

𝟏𝟎
Z = (0, -3) ( )
𝟑

Z = 0x10 + (-3)x3

Z = -9

Qué variable entra?

Y1 = B1-1x a1

𝟏 𝟐 𝟏
Y1 = [ ]( )
𝟎 𝟏 −𝟏

1x1 + 2x (-1) = -1

0x1 + 1x (-1) = -1

−𝟏
Y1 = ( )
−𝟏

Y4 = B1-1x a4

𝟏 𝟐 𝟎
Y4 = [ ]( )
𝟎 𝟏 𝟏

1x0 + 2x1 = 2

0x0 + 1x1 = 1

𝟐
Y4 = ( )
𝟏

Luego se tiene que:

z1 – c1 = cBy1 – c1

cB = (c3, c2) = (0, -1)

−𝟏
z1 – c1 = (0, -3) ( )- (-1)
−𝟏

0x (-1) + (-3) x (-1) + 1 = 4

z1 – c1 = 4

z4 – c4 = cBy4 – c4

𝟐
z4 – c4 = (0, -3) ( ) - 0
𝟏
0x2 + (-3)x1 – 0 = -3

z4 – c4 = -3
Variable que entra: a1

¿Qué variable sale?

Xbi/yik; yik > 0

𝟏𝟎 −𝟏
xB = ( ); Y1 = ( )
𝟑 −𝟏

Por qué y1?

Porque la variable que entró fue a1.

10/(-1) = -10

XB/y1:

3/(-1) = -3

No sale ninguna variable ya que ambos valores son negativos, por tanto
se tiene que:

Solución óptima

Z = -9

X3 = 10

X2 = 3

Solución no acotada