Scribd
Upload
37 views4 pages

7 Basicas No Les Variab 0 ,: Practica #4 Función Objetivo Restricciones

The document describes solving a linear programming problem with 4 constraints and 2 variables (x1 and x2) to maximize the objective function z=x1+2x2. It goes through the steps of converting to standard form, finding an initial infeasible solution, applying a two-phase method to find a feasible solution, and using the simplex method with branching to find the optimal solution. The optimal solution is x1=53/18 and x2=5/9, with z=73/18.

Uploaded by

adetico
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
37 views4 pages

7 Basicas No Les Variab 0 ,: Practica #4 Función Objetivo Restricciones

The document describes solving a linear programming problem with 4 constraints and 2 variables (x1 and x2) to maximize the objective function z=x1+2x2. It goes through the steps of converting to standard form, finding an initial infeasible solution, applying a two-phase method to find a feasible solution, and using the simplex method with branching to find the optimal solution. The optimal solution is x1=53/18 and x2=5/9, with z=73/18.

Uploaded by

adetico
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 4

Practica N 4

Funcin objetivo

z = x1 + 2 x 2 max

Restricciones

2 x1 + 2 x 2 7
4 x1 5 x 2 9
4 x1 5 x 2 9
x1 , x 2 0

Llevamos a la forma estndar


2 x1 + 2 x 2 + s1 = 7
4 x1 5 x 2 + s 2 = 9
4 x1 5 x 2 s 3 = 9

Sacando la solucin inicial

x1 , x 2 = 0 variables no basicas

s1 = 7

s 2 = 9 variables basicas
s 3 = 9
Solucin inicial inconsistente
Aplicamos el mtodo de dos fases
4 x1 5 x 2 s 3 + R1 = 9

x1 , x 2 , s 3 = 0 variables no basicas
s1 = 7

s 2 = 9 variables basicas
R1 = 9
Solucin inicial factible
r = Ri min

r = R1 min
r R1 = 0

r
R1

x1

x2

s1

s2

s3

R1

0
4

0
-5

0
0

0
0

0
-1

-1
1

Sol
0
9

x1

x2

s1

s2

s3

R1

4
2
4
4

-5
2
-5
-5

0
1
0
0

0
0
1
0

-1
0
0
-1

0
0
0
1

x1

x2

s1

s2

s3

R1

s1
s2
x1

0
1

0
9/2
0
-5/4

0
1
0
0

0
0
1
0

0
1/2
1
-1/4

-1
-1/2
-1
1/4

r
s1
s2
R1

Sol
9
7
9
9
Sol
0
5/2
0
9/4

Fase II

Z
x1

Z
s1
s1
x1

Z
x2
s2
x1

x1

x2

s1

s2

s3

-1
1

-2
-5/4

0
0

0
0

0
-1/4

sol
0
9/4

0
0
0
1

-13/4
9/2
0
-5/4

0
1
0
0

0
0
1
0

-1/4
1/2
1
-1/4

9/4
5/2
0
9/4

0
0
0
1

0
1
0
0

13/18
2/9
0
5/18

0
0
1
0

1/9
1/9
1
-1/9

73/18
5/9
0
53/18

Z = 73 / 18
x1 = 53 / 18
x2 = 5 / 9

Acotamiento
Establecemos la cota inferior:
Z*=-

Ramificacin
Z = 73 / 18
x1 = 53 / 18
x2 = 5 / 9

x1 [ 53 / 18] = 2
x1 2

x1 + s 4 = 2

x [ 53 / 18] + 1 = 3

1
X1 = 3
x1 3
X2 = 1/2
S2 = -1/2 x1 s ' 4 = 3
x1 + s ' 4 = 3
Z=4
Se sondea por la prueba dos

X1 = 2
X2 = -1/5
Z = 144/90

Se sondea por la prueba dos


Sub-problema 1

z
x2
s2
x1
s4

z
x2
s2
x1
s4

z
x2
s2
x1
s1

Sub-problema 2

x1

x2

s1

s2

s3

s4

0
0
0
1
1

0
1
0
0
0

13/18
2/9
0
5/18
0

0
0
1
0
0

1/9
1/9
1
-1/9
0

0
0
0
0
1

x1

x2

s1

s2

s3

s4

0
0
0
1
0

0
1
0
0
0

13/18
2/9
0
5/18
-5/18

0
0
1
0
0

1/9
1/9
1
-1/9
1/9

0
0
0
0
1

x1

x2

s1

s2

s3

s4

0
0
0
1
0

0
1
0
0
0

0
0
0
0
1

0
0
1
0
0

2/5
1/5
1
0
-2/5

13/5
4/5
0
1
-18/5

x1

x2

s1

s2

s3

s' 4

0
0
0
1
-1

0
1
0
0
0

13/18
2/9
0
5/18
0

0
0
1
0
0

1/9
1/9
1
-1/9
0

0
0
0
0
-1

Sol
73/18
5/9
0
53/18
2
Sol
73/18
5/9
0
53/18
-17/18
Sol
144/90
-1/5
0
2
17/5

Sub-problema 2

Z
x2
s2
x1
s' 4

Sol
73/18
5/9
0
53/18
-3

Z
x2
s2
x1
s' 4

Z
x2
s2
x1
s3

x1

x2

s1

s2

s3

s' 4

0
0
0
1
0

0
1
0
0
0

13/18
2/9
0
5/18
5/18

0
0
1
0
0

1/9
1/9
1
-1/9
-1/9

0
0
0
0
1

x1

x2

s1

s2

s3

s' 4

0
0
0
0
0

0
1
0
0
0

1
1/9
5/2
0
-5/2

0
0
1
0
0

0
0
0
0
1

1
1
9
-1
-9

Conclusin.

Sol
73/18
5/9
0
53/18
-1/18
Sol
4
1/2
-1/2
3
1/2

You might also like