6 x1 + 16 x2 + x3 12 x1 + 6 x2

= 48000 + x4

9 x1 + 9 x 2

= 42000 + x5 = 36000

Z = 4 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5

cj ck

xk

Z

B

A1

A2

A3

A4

A5

bi/aij

6 x1 + 16 x2 + x3 12 x1 + 6 x2

= 48000 + x4

9 x1 + 9 x 2

= 42000 + x5 = 36000

Z = 4 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5

ck

xk

Z

cj

4

3

0

0

0

B

A1

A2

A3

A4

A5

bi/aij

6 x1 + 16 x2 + x3 12 x1 + 6 x2

= 48000 + x4

9 x1 + 9 x 2

= 42000 + x5 = 36000

Z = 4 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5

ck

xk x3 x4 x5 Z

cj

4

3

0

0

0

B

A1

A2

A3

A4

A5

bi/aij

6 x1 + 16 x2 + x3 12 x1 + 6 x2

= 48000 + x4

9 x1 + 9 x 2

= 42000 + x5 = 36000

Z = 4 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5

cj

4

3

0

0

0

A1

A2

A3

A4

A5

ck

xk

B

0

x3

48.000

0

x4

42.000

0

x5

36.000

Z

bi/aij

6 x1 + 16 x2 + x3 12 x1 + 6 x2

= 48000 + x4

9 x1 + 9 x 2

= 42000 + x5 = 36000

Z = 4 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

Z

1 1

bi/aij

6 x1 + 16 x2 + x3 12 x1 + 6 x2

= 48000 + x4

9 x1 + 9 x 2

= 42000 + x5 = 36000

Z = 4 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

Z=0

Z=

∑c

k

⋅xk

1 1

bi/aij

6 x1 + 16 x2 + x3

= 48000

12 x1 + 6 x2

+ x4

9 x1 + 9 x 2

= 42000 + x5 = 36000

Z = 4 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0

z j − c j = ∑ck a ij − c j

1 1 0

0

0

bi/aij

x2

x4 = 0

x5 = 0

4

3

2

x3 = 0

1

1

2

3

4

x1

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0

1 1 0

0

0

bi/aij

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0

1 1 0

0

0

bi/aij

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0

bi/aij

1 1 0

x2

0

0

x4=0 x5=0

x3=0

x1

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0

8.000 1

3.500 1

0

bi/aij

0

0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0

bi θ = min a ij

8.000 1

3.500 1

0

bi/aij

0

0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0

8.000 1

3.500 1

0

bi/aij

0

0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0 x3 x1 x5

8.000 1

3.500 1

0

bi/aij

0

0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0 0

x3

4

x1

0

x5

8.000 1

3.500 1

0

bi/aij

0

0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0 0

x3

4

x1

0

x5

8.000 1

3.500 1

0

0

0

1 1 1 0

0

bi/aij

0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0 0

x3

4

x1

0

x5

8.000 1

3.500 1

0

0

0

1 3.500

1

1/2

1/12 1

0

0

bi/aij

0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0 0

x3

27.000

4

x1

3.500

0

x5

3.500 1

0

0

1 1

1/12

1/12 1

0

48.000 - 6 · 42.000 12

8.000 1

0

0

bi/aij

0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

13

1

Z=0 0

x3

27.000

4

x1

3.500

0

x5

1

8.000 1

3.500 1

1/12

0

0

1/12 1

0

16 - 6 · 6 12

0

bi/aij

0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

Z=0 0

x3

27.000

4

x1

3.500

0

x5

1

8.000 1

3.500 1

1/12

0

1/12 1

0

0

0

bi/aij

0 - 1·6 12

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

1

3.500 1 0

1/12 1

0

36.000 - 9 · 42.000 12

8.000 1

1/2 0

bi/aij

0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

1

9 - 6·9 12

3.500 1 0

1/12

9/2 0

8.000 1

1/2

1 0

bi/aij

0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

1

8.000 1

3.500 1

1/2

1/12

9/2

-3/4

0

0

0

bi/aij

0

1 0

- 1·9 12

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000

1 0

8.000 1

3.500 1

1/2

1/12

9/2

-3/4 0

bi/aij

0

1 0

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000

1 0

8.000 1

3.500 1 0

1/2

1/12

9/2

-3/4

1

1/3

0

-1

0

bi/aij

4.000

x2

x4 = 0

x5 = 0

4

3

2

x3 = 0

1

1

2

3

4

x1

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000

1 0

8.000 1

3.500 1 0

1/2

1/12

9/2

-3/4

1

1/3

0

-1

0

bi/aij

4.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000

1 0

8.000 1

3.500 1 0

1/2

1/12

9/2

-3/4

1

1/3

0

-1

0

bi/aij

4.000

x2

x4 = 0

x5 = 0

4

3

2

x3 = 0

1

1

2

3

4

x1

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

2.077

1/2

1/12

7.000

9/2

-3/4

1

1/3

0

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000

1 0

-1

8.000 1

3.500 1

0

bi/aij

4.000

0

1.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

2.077

1/2

1/12

7.000

9/2

-3/4

1

1/3

0

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000

1 0

-1

8.000 1

3.500 1

0

bi/aij

4.000

0

1.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

2.077

1/2

1/12

7.000

9/2

-3/4

1

1/3

0

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000

1 0

-1

8.000 1

3.500 1

0

bi/aij

4.000

0

1.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

2.077

1/2

1/12

7.000

9/2

-3/4

1

1/3

0

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000

1 0

-1

x3 x2 Z

1 1.000

1 0

0

3.500 1

1

x1

8.000 1

0

0

bi/aij

4.000

0

1.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

2.077

1/2

1/12

7.000

9/2

-3/4

1

1/3

0

-1/6

2/9

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000 0

x3

4

x1

3

x2 Z

1 0

-1

8.000 1

3.500 1

0

1 1 0

0

0

4.000

0

1 1.000

bi/aij

1.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

2.077

1/2

1/12

7.000

9/2

-3/4

1

0

1/3

0

1

5/3

-26/9

1/6

-1/9

-1/6

2/9

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000 0

x3

14.000

4

x1

3.000

3

x2

1.000

Z

1 0

-1

0

3.500 1

1 0

8.000 1

1 0

bi/aij

4.000

0

1.000

cj

4

3

0

0

0

A4

A5

ck

xk

B

A1

A2

A3

0

x3

48.000

6

16

1

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

0

0

13

1

-1/2

2.077

1/2

1/12

7.000

9/2

-3/4

1

0

1/3

0

1

5/3

-26/9

1/6

-1/9

-1/6

2/9

1/6

2/9

Z=0 0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000 0

x3

14.000

4

x1

3.000

3

x2

1.000

Z = 15.000

1 0

-1

0

3.500 1

1 0

8.000 1

1 0

bi/aij

4.000

0

1.000

x2

x4 = 0

x5 = 0

4

3

2

x3 = 0

1

1

2

3

4

x1

x2

0

x3

14.000

4

x1

3.000

3

x2

1.000

Z = 15.000

x5 = 0

4

1 1 1 0

0

0

5/3

-26/9

1/6

-1/9

-1/6

2/9

1/6

2/9

x4 = 0

3

2

x3 = 0

1

1

2

3

4

x1

PROCEDIMIENTO “SIMPLEX” 1.

PARTE DE UNA BASE FACTIBLE, Y CALCULA EL Z

2.

SE PREGUNTA SI LA SOLUCIÓN ES ÓPTIMA. SI LO ES SE TERMINA EL PROCEDIMIENTO.

3.

SI NO LO ES, SE PASA A LA BASE VECINA QUE MEJORE MÁS A “Z”, SELECCIONANDO UNA VARIABLE QUE INGRESE A LA BASE Y OTRA QUE SALGA.

4.

SE VUELVE AL PUNTO 2.

x2

0

x3

48.000

6

16

0

x4

42.000

12

6

0

x5

36.000

9

9

-4

-3

Z=0

x5 = 0

4

1 1 1 0

0

0

x4 = 0

3

2

x3 = 0

1

1

2

3

4

x1

x2

0

x3

27.000

4

x1

3.500

0

x5

4.500

Z = 14.000

x5 = 0

4

13 1 0

1

-1/2

1/2

1/12

9/2

-3/4

1

1/3

0

-1

0

x4 = 0

3

2

x3 = 0

1

1

2

3

4

x1

x2

0

x3

14.000

4

x1

3.000

3

x2

1.000

Z = 15.000

x5 = 0

4

1 1 1 0

0

0

5/3

-26/9

1/6

-1/9

-1/6

2/9

1/6

2/9

x4 = 0

3

2

x3 = 0

1

1

2

3

4

x1

x2

x4 = 0

x5 = 0

4

3

2

x3 = 0

1

0

1

2

3

4

x1

SISTEMA DE INECUACIONES 6 x1 + 16 x2 ≤ 48000 12 x1 + 6 x2 ≤ 42000 9 x1 + 9 x2 ≤ 36000 Z = 4 x1 + 3 x2

SISTEMA DE ECUACIONES 6 x1 + 16 x2 + x3 12 x1 + 6 x2 9 x1 + 9 x2

= 48000 + x4

= 42000 + x5 = 36000

Z = 4 x 1 + 3 x 2 + 0 x 3 + 0 x 4 + 0 x5

FORMULACIÓN MATRICIAL DE LAS CONDICIONES DE VÍNCULO 6 x1 + 16 x2 + x3 12 x1 + 6 x2

= 48.000 + x4

9 x1 + 9 x2

= 42.000 + x5 = 36.000

Z = 4 x1 + 3 x2 + 0 x 3 + 0 x4 + 0 x 5

6

16

12

6

9

9

1 1

.

1

x1 x2 x3 x4 x5

48.000 =

42.000 36.000

FORMULACIÓN MATRICIAL DEL FUNCIONAL 6 x1 + 16 x2 + x3 12 x1 + 6 x2

= 48.000 + x4

9 x1 + 9 x2

= 42.000 + x5 = 36.000

Z = 4 x1 + 3 x2 + 0 x 3 + 0 x4 + 0 x 5

Z

=

4

3

0

0

0

.

x1 x2 x3 x4 x5

DEFINICIÓN DE VECTORES 6 x1 + 16 x2 + x3 12 x1 + 6 x2 9 x1 + 9 x2

= 48.000 + x4

= 42.000 + x5 = 36.000

Z = 4 x1 + 3 x2 + 0 x 3 + 0 x4 + 0 x 5

6

A1= 12 9

A2=

16

1

6

A3= 0

9

0

A4=

0

0

1

A5= 0

0

1

FORMULACIÓN VECTORIAL 6 x1 + 16 x2 + x3 12 x1 + 6 x2 9 x1 + 9 x2

= 48.000 + x4

= 42.000 + x5 = 36.000

Z = 4 x1 + 3 x2 + 0 x 3 + 0 x4 + 0 x 5

6

16

12 · x + 1 9

6 9

1

0

0

· x2 + 0 · x3 + 1 · x4 + 0 ·x5 = 0

0

1

48.000 42.000 36.000

FORMULACIÓN VECTORIAL 6 x1 + 16 x2 + x3 12 x1 + 6 x2 9 x1 + 9 x2

= 48.000 + x4

= 42.000 + x5 = 36.000

Z = 4 x1 + 3 x2 + 0 x 3 + 0 x4 + 0 x 5

48.000

A1 · x + A2 · x + A3 · x + A4 · x + A · x = 1 2 3 4 5 5

42.000 36.000

FORMULACIÓN VECTORIAL 6 x1 + 16 x2 + x3 12 x1 + 6 x2

= 48.000 + x4

9 x1 + 9 x2

= 42.000 + x5 = 36.000

Z = 4 x1 + 3 x2 + 0 x 3 + 0 x4 + 0 x 5

∑A ⋅ x j

j

=B

x 3    

x4

= b1 = b2 x 5 = b3

 x3   b1  1  0  0           B =  x 4  =  0  x 3 + 1  x 4 +  0  x 5 =  b 2  x  b   0 0 1         5  3 m

B = ∑ Akxk 1

Z = c1x1 + c 2 x 2 + c3 x 3 + c 4 x 4 + c5 x 5

Z

(1)

= c 3 x 3 + c 4 x 4 + c5 x 5 m

Z

(1)

= ∑ ck x k 1

 a 11  1   0 0         A1 =  a 21  = a11  0  + a 21 1  + a 31  0  a  0  0 1         31   a12  1  0 0         A 2 =  a 22  = a12  0  + a 22 1  + a 32  0  a  0 0 1         32  m

A j = ∑ a ij A k 1

Cambio de base = b1 a 11x 1 + x 3  = b2 a 21x1 + x 4 a x + x 5 = b3  31 1   x1 ≤    x1 ≤    x1 ≤ 

 x 3 = b1 − a11x1 ≥ 0   x 4 = b 2 − a 21x1 ≥ 0 x = b − a x ≥ 0 3 31 1  5

b1 a11 b2 a 21 b3 a 31

bi x1 = min = θ a ij

Nueva base = b1 a 11θ + x 3  = b2 a 21θ + x 4 a θ + x 5 = b3  31

m

A j = ∑ a ij A k 1

m

B = ∑ Ak x k 1

m

θ A j = θ ∑ a ij A k 1

m

m

1

1

B = ∑ A k x k + θ A j − θ ∑ a ij A k m

B = A j θ + ∑ A k ( x k − θ a ij ) 1

m

Z

( 2)

= c j θ + ∑ c k ( x k − θ a ij ) 1

m

Z( 2) = c j θ + ∑ c k ( x k − θ a ij ) 1

m

m

1

1

Z ( 2) = c j θ + ∑ c k x k − ∑ θ c k a ij m

Z ( 2 ) = c j θ + Z (1) − ∑ θ c k a ij 1

Z

Z

( 2)

(2)

m   (1) = Z − θ ∑ c k a ij − c j  1 

=Z

(1 )

− θ ⋅ (z j − c j )

Z

( P +1 )

=Z

(P)

− θ ⋅( zj − cj)