Scribd
Upload
54 views6 pages

Tutorial Exercises (Sheet 4) : Two-Phase Algorithm and Goal Programming

The document contains solutions to 4 exercises involving linear programming problems: 1) The first exercise solves a linear program to maximize an objective function subject to constraints. The optimal solution is found to be x1 = 4/5, x2 = 2/5, with an optimal value of 10.4. 2) The second exercise solves a similar linear program but with an additional constraint, arriving at the same optimal solution and value. 3) The third exercise attempts to solve another linear program but finds there is no feasible solution. 4) The fourth exercise formulates and solves a linear program to minimize the sum of absolute values of expressions subject to constraints, finding the optimal solution is x1 = 0, x2

Uploaded by

lolka
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
54 views6 pages

Tutorial Exercises (Sheet 4) : Two-Phase Algorithm and Goal Programming

The document contains solutions to 4 exercises involving linear programming problems: 1) The first exercise solves a linear program to maximize an objective function subject to constraints. The optimal solution is found to be x1 = 4/5, x2 = 2/5, with an optimal value of 10.4. 2) The second exercise solves a similar linear program but with an additional constraint, arriving at the same optimal solution and value. 3) The third exercise attempts to solve another linear program but finds there is no feasible solution. 4) The fourth exercise formulates and solves a linear program to minimize the sum of absolute values of expressions subject to constraints, finding the optimal solution is x1 = 0, x2

Uploaded by

lolka
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Tutorial Exercises (Sheet 4)

Two-Phase Algorithm and Goal Programming


Exercise 1 Solve the following LP problem:
max y = 4x1 + 3x2
subject to:
3x1
3x1
4x1

+ 4x2
+ 3x2
+ 2x2

12
10

and
x1 0, x2 0.
Solution

Standard Form:
min z = 4x1 3x2

subject to:
3x1
3x1
4x1

+ 4x2
+ 3x2
+ 2x2

+ x3
+

x4
+

x5

= 12
= 10
= 8

and
x1 0, x2 0x3 0, x4 0, x5 0.
Simplex Algorithm:
BV
z
x3
x4
x5
z

x1
4
3
3
4
0

x2
3
4
3
2
1

x3
0
1
0
0
0

x4
0
0
1
0
0

x5
0
0
0
1
1

RHS
0
12
10
8
8

x3

5
2
3
2
1
2

34

1
0
0
0
1
0

43
1
4
7
10
3
10
3
10
2
5

4
2

x4
x1
z
x2
x4
x1

0
1
0
0
0
1

0
0

0 25
2
1
5
0 35
0 15
1

10 25
2 25
2
5
4
5

The optimal BS is thus given by:



(x1 , x2 , x3 , x4 , x5 ) =


4 12
2
, , 0, , 0 .
5 5
5

and the optimal value (for the max problem) is 10.4.


Exercise 2 Consider the following LP problem:
max y = 4x1 + 3x2
subject to:
3x1
3x1
4x1
x1

+ 4x2
+ 3x2
+ 2x2
+
x2

12
10

and
x1 0, x2 0.
Solution

Standard Form:
min z = 4x1 3x2

subject to:
3x1
3x1
4x1
x1

+ 4x2
+ 3x2
+ 2x2
+
x2

x3
+

x4
+ x5
x6

= 12
= 10
= 8
= 1

and
x1 0, x2 0x3 0, x4 0, x5 0, x6 0.
Introducing artificial variables:
min 4x1 3x2
subject to:
3x1
3x1
4x1
x1

+ 4x2
+ 3x2
+ 2x2
+
x2

+ x3
+ x4
+

x5
x6

= 12
= 10
= 8
= 1

and
x1 0, x2 0x3 0, x4 0, x5 0, x6 0, 0.
Phase I: Introduce

x1
x1

x6
x6

+ x2
+ x2
2

= 0
= 1
= 1

min = 1 x1 x2 x6 .
Simplex Algorithm:
BV

x3
x4
x5

x3
x4
x5
x1

x1
1
3
3
4
1
0
0
0
0
1

x2 x3 x4
1
0
0
4
1
0
3
0
1
2
0
0
1
0
0
0
0
0
1
1
0
0
0
1
2
0
0
1
0
0

x5
0
0
0
1
0
0
0
0
1
0

x6
1
0
0
0
1
0
3
3
4
1

RHS
0
1
0
12
0
10
0
8
1
1
1
0
3
9
3
7
4
4
1
1

Found min = 0.
Phase II: Drop column for and replace row for by original objective
function.
We cannot take simply:
BV
z
x3
x4
x5
x1

x1
4
0
0
0
1

x2 x3 x4
3
0
0
1
1
0
0
0
1
2
0
0
1
0
0

x5
0
0
0
1
0

x6
0
3
3
4
1

RHS
0
9
7
4
1

as this is not a basic representation! Eliminate x1 (as it is basis for Phase I)


from z:
z + 4x1 + 3x2
= 0
x1 +
x2 x6 = 1 4
or better:
z
z

+ 4x1
4x1

3x2
4x2
x2

+ 4x6
+ 4x6

=
0
= 4
= 4

Proceed with Simplex Algorithm:


BV
z
x3
x4
x5
x1
z

x1
0
0
0
0
1
0

x2
1
1
0
2
1
1

x3

x4
x6
x1
z
x2
x4
x6
x1

0
0
1
0
0
0
0
1

5
2
3
2
12
1
2

x3 x4
0
0
1
0
0
1
0
0
0
0
0
0

RHS
4
9
7
4
1
8

34

0
0
0

1
0
0
0
0
1
0
0

34

0
1
0
0
0
0
1
0

4
1
2

25

0
1
0
0
0

x5 x6
0
4
0
3
0
3
1 4
0 1
1
0

2
5
35
1
5
15

1
4
1
4
7
10
3
10
3
10
1
10
2
5

10 52
2 25
2
5
2 15
4
5

As expected: The optimal BS is the same as before:




2
4 12
, , 0, , 0 .
(x1 , x2 , x3 , x4 , x5 ) =
5 5
5
and the optimal value (for the max problem) is 10.4.
Exercise 3 Solve the following LP problem:
max y = 4x1 + 3x2
subject to:
3x1
5x1
x1

+ 4x2
+ 2x2
+
x2

12

and
x1 0, x2 0.
Solution
min z = 4x1 3x2
subject to:
3x1
5x1
x1

+ 4x2
+ 2x2
+ x2

x3
+ x4
x5

=
=
=

and
x1 0, x2 0, x3 0, x4 0, x5 0, 0.
4

12
8
5

Two-Phase Simplex Algorithm:


= = x1 x2 + x5 + 5
BV

x3
x4

x1
1
3
5
1
0

x2

x4

x2
x1

1
0
0
0
1
0

x2
1
4
2
1
3
5
14
5
2
5
3
5

0
1
0
0

x3
0
1
0
0
0

x4
0
0
1
0

x5
1
0
0
1
1

1
5
53
1
5
1
5
1
14
3
14
2
7
1
14

1
0
0
3
14
5
14
71
3
14

RHS
0
5
0
12
0
8
1
5
17
0
5
0

0 0
1 1
1 0
0 0
0 0
1 1

36
5
8
5
17
5
13
7
18
7
4
7
13
7

After Phase I, we see: The minimum of reached is non-zero. Therefore


there is no feasible solution!
Exercise 4 (a) Write a linear program for finding x1 and x2 satisfying:
2x1 + x2 10
and
x1 0, x2 0
and having |x1 2x2 | + | 3x1 x2 | as small as possible (with |.| denoting the
absolute value).
(b) Solve the resulting linear program.
Solution (a) Since x 0: | 3x1 x2 | = 3x1 + x2 . Let x1 2x2 = u v with
u 0 and v 0. Then |x1 2x2 | = |u v| |u| + | v| = u + v. Therefore we
investigate the LP problem:
min u + v + 3x1 + x2
subject to:
2x1 + x2 + x3

10

u v x1 + 2x2

and
x1 , x2 , x3 , u, v 0.

(b) The simplex method results in the following:


x1
3
2
1
x1
4
2
1
x1
72
5
2
12

x2
1
1
2
x2
1
1
2
x2
0
0
1

x3
0
1
0
x3
0
1
0
x3
0
1
0

u
1
0
1

v RHS
1
0
10
0
1
0

u v
0 2
0 0
1 1
u
1
2
12
1
2

The optimum is thus x1 = 0 and x2 = 0.

v
23
1
2
21

RHS
0
10
0
RHS
0
10
0

You might also like