MAX: Z = 4 x1 + 3 x2 Sujeto a: siendo: 6 x1 + 16 x2 ≤ 48000 12 x1 + 6 x2 ≤ 42000 9 x1 + 9 x2 ≤ 36000 x1, x2 ≥ 0 y con
Views 190 Downloads 10 File size 781KB
MAX: Z = 4 x1 + 3 x2 Sujeto a:
siendo:
6 x1 + 16 x2 ≤ 48000 12 x1 + 6 x2 ≤ 42000 9 x1 + 9 x2 ≤ 36000 x1, x2 ≥ 0
y continuas
6 x1 + 16 x2 + x3 12 x1 + 6 x2
= 48000 + x4
9 x1 + 9 x2
= 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 x2
= 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 x2
= 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 x2
= 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 x2
= 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 x2
= 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 = ∑ ck ⋅ x k
1 1
bi/aij
6 x1 + 16 x2 + x3
= 48000
12 x1 + 6 x2
+ x4
9 x1 + 9 x2
= 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 = ∑ c k 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/2
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/2
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/2
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
1
x1 x2 Z
1.000
1 0
0
3.500 1
1
x3
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 x 2
SISTEMA DE ECUACIONES 6 x1 + 16 x2 + x3 12 x1 + 6 x2 9 x1 + 9 x2
= 48000 + x4
= 42000 + x5 = 36000
Z = 4 x1 + 3 x 2 + 0 x 3 + 0 x 4 + 0 x 5
FORMULACIÓN MATRICIAL DE LAS CONDICIONES DE VÍNCULO 6 x1 + 16 x2 + x3 12 x1 + 6 x2
= 48.000 + x4
9 x 1 + 9 x2
= 42.000 + x5 = 36.000
Z = 4 x 1 + 3 x 2 + 0 x 3 + 0 x 4 + 0 x5
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 x 1 + 9 x2
= 42.000 + x5 = 36.000
Z = 4 x 1 + 3 x 2 + 0 x 3 + 0 x 4 + 0 x5
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 x 1 + 9 x2
= 48.000 + x4
= 42.000 + x5 = 36.000
Z = 4 x 1 + 3 x 2 + 0 x 3 + 0 x 4 + 0 x5
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 x 1 + 9 x2
= 48.000 + x4
= 42.000 + x5 = 36.000
Z = 4 x 1 + 3 x 2 + 0 x 3 + 0 x 4 + 0 x5
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 x 1 + 9 x2
= 48.000 + x4
= 42.000 + x5 = 36.000
Z = 4 x 1 + 3 x 2 + 0 x 3 + 0 x 4 + 0 x5
48.000
A1 · x + A2 · x + A3 · x + A4 · x + A · x = 5 1 2 3 4 5
42.000 36.000
FORMULACIÓN VECTORIAL 6 x1 + 16 x2 + x3 12 x1 + 6 x2
= 48.000 + x4
9 x 1 + 9 x2
= 42.000 + x5 = 36.000
Z = 4 x 1 + 3 x 2 + 0 x 3 + 0 x 4 + 0 x5
∑A
j
⋅xj = B
= b1
x 3
x4
= 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 3 5 m
B = ∑ Ak xk 1
Z = c1x1 + c 2 x 2 + c3 x 3 + c 4 x 4 + c 5 x 5
Z
(1)
= c3 x 3 + c4 x 4 + c5 x 5 m
Z
(1)
= ∑ ck x k 1
a 11 1 0 0 A1 = a 21 = a 11 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 ijA k 1
Cambio de base = b1 a11x1 + x 3 = b2 a 21x1 + x 4 a x + x 5 = b3 31 1 b1 x ≤ 1 a 11 b2 x1 ≤ a 21 b3 x1 ≤ a 31
x 3 = b1 − a11x1 ≥ 0 x 4 = b 2 − a 21x1 ≥ 0 x = b − a x ≥ 0 3 31 1 5
bi x1 = min = θ a ij
Nueva base = b1 a11θ + x 3 = b2 a 21θ + x 4 a θ + x 5 = b3 31
m
A j = ∑ a ijA k 1
m
B = ∑ Ak xk 1
m
θ A j = θ ∑ a ijA k 1
m
m
1
1
B = ∑ A k x k + θ A j − θ ∑ a ijA 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
( 2)
= Z(1)
m − θ ∑ c k a ij − c j 1
( 2)
=Z
− θ ⋅ (z j − c j )
Z
Z
(1)
Z
( P +1)
=Z
(P)
− θ⋅( zj − cj)