NAMA : FAROUK ABDILLAH

NRP : 02411750012003
KONSENTRASI : MANAJEMEN KUALITAS DAN MANUFAKTUR
TUGAS SIMPLEX PROBLEM

Problem 4.5 Number 2 page 149

Use the simplex algorithm to solve the following LP:
max z = 2x1 + 3x2
s.t. x1 + 2x2 ≤ 6
2x1 + x2 ≤ 8
x1, x2 ≥ 0
Solution:
Trial1
Step 1 Convert the LP to standard form.
Canonical Form 0
Basic
Row
Variable
0 z - 2x1 - 3x2 + = 0 z
1 x1 + 2x2 + s1 = 6 s1
2 2x1 x2 + s2 = 8 s2
Basic Variables = {z, s1, s2} ; Non - Basic Variables = {x1, x2}

Step 2 Obtain a bfs from the standard from

If we set x1 = x2 = 0, then we get the value z = 0; s1 = 6; s2 = 8

Step 3 Determine whether the current bfs is optimal

 Determine entering variable
z = 2x1 + 3x2 → if x1 increased by 1, x2 set to 0, z increase by 2
if x2 increased by 1, x1 set to 0, z increase by 3
Because a unit increase in x2 causes the largest rate of increase in z, we choose to
increase x2 as the entering variable.
 Find the limit and ratio for each constraints
6 6
Row 1 2x2 + s1 = 6 → s1 ≥ 0 for x2 ≤ 2 = 3 ; ratio = 2 (most minimum)
8 8
Row 2 x2 + s2 = 8 → s2 ≥ 0 for x2 ≤ 1
= 8 ; ratio = 1
That mean if x2 > 3, s1 became negative and we will no longer have a feasible
solution. So the limit for x2 is 0 ≤ x2 ≤ 3
Step 4 Use EROs to find the new bfs with the better objective function value. Go back to step 3

1
ERO 1 Create a coefficient of 1 for x2 in row 1 by multiplying row 3 by 2
1 1
Row 1' 2
x1 + x2 + 2
s1 = 9

ERO 2 To create a zero coefficient for x2 in row 0, replace row 0 with 3(row 1’) + row 0
1 3
Row 0' Z - x1 + s1 = 3
2 2
ERO 3 To create a zero coefficient for x2 in row 2, replace row 2 with -(row 1’) + row 2
3 1
Row 2' 2
x1 - 2
s1 + s2 = 5

Canonical Form 1
Basic
Row
Variable
1 3
0’ Z - 2
x1 + 2
s1 = 3 Z=9
1 1
1’ 2
x1 + x2 + 2
s1 = 3 x2 = 3
3 1
2’ 2
x1 - 2
s1 + s2 = 5 s2 = 5

Basic Variables = {z, x2, s2} ; Non - Basic Variables = {s1, x1}
Canonical form 1 z-value = initial z-value + 3(3)
=0+9 = 9
Do trials on canonical form 1 by using same algorithm steps and repeat until satisfying result
found.
By Using Lindo:

Problem 4.6 Number 4 page 153

Use the simplex algorithm to solve the following LP:
min z = -3x1 + 8x2
s.t. 4x1 + 2x2 ≤ 12
2x1 + 3x2 ≤ 6
x1, x2 ≥ 0
Solution:
Trial1
The optimal solution to LP is the point (x1, x2) in the feasible region for LP that makes -z = 3x1 -
8x2 the smallest. Equivalently, we may say that the optimal solution to LP is the point in the feasible
region that makes -z = 3x1 - 8x2 the largest. This means that we can find the optimal solution to
LP by solving LP’:
max -z = 3x1 - 8x2
s.t. 4x1 + 2x2 ≤ 12
2x1 + 3x2 ≤ 6
x1, x2 ≥ 0
Determine entering variable
-z = 3x1 - 8x2 → if x1 increased by 1 when x2 set to 0, -z increase by 3
if x2 increased by 1 when x1 set to 0, -z increase by -8
Because a unit increase in x2 causes the largest rate of increase in z, we choose to increase x1
as the entering variable.
Initial Tableau for LP’
Basic
Row -z x1 x2 s1 s2 rhs Ratio
Variable
0 1 -3 8 0 0 0 -z = 0
12
1 0 4 2 1 0 12 s1 = 12 4
=3

6
2 0 2 3 0 1 6 s2 = 6 2
=3
1
ERO 1 Create a coefficient of 1 for x1 in row 2 by multiplying row 2 by 2
ERO 2 To create a zero coefficient for x1 in row 0, replace row 0 with 3(row 2’) + row 0
ERO 3 To create a zero coefficient for x2 in row 2, replace row 2 with -4(row 2’) + row 1

Optimized Tableau for LP’

Basic
Row -z x1 x2 s1 s2 rhs
Variable
3x1 25 3
1 0 0 9 -z = 9
+ 0’ 2 2
1’ 0 0 8 1 2 24 s1 = 24
3 1
2’ 0 1 0 3 x1 = 3
2 2
z-value = initial z-value + [-3(x1)]
= 0 + [– 3(3)] = -9
Do trial on optimize tableau by using same algorithm steps and repeat until satisfying result found.
By Using Lindo:
Problem 4.7 Number 3 page 155
Use the simplex algorithm to solve the following LP:
max z = x1 + x2
s.t. x1 + x2 + x3 ≤ 1
x1 + 3x3 ≤ 1
x1, x2 ≥ 0
Solution:
Trial1
Determine entering variable
z = x1 + x2 → if x1 increased by 1 when x2 set to 0, z increase by 1
if x2 increased by 1 when x1 set to 0, z increase by 1
Because a unit increase in x1 and x2 causes same rate of increase in z, we can choose between
x1 and x2 as the entering variable, resulting same z value but different optimal point.
Initial Tableau for LP (x1)
Basic
Row -z x1 x2 x3 s1 s2 rhs ratio
Variable
0 1 -1 -1 0 0 0 0 Z=0
1
1 0 1 1 1 1 0 1 s1 = 1 1
=1

1
2 0 1 0 3 0 1 1 s2 = 1 1
=1
ERO 1 Create a coefficient of 1 for x1 in row 2 by multiplying row 2 by 1
ERO 2 To create a zero coefficient for x1 in row 0, replace row 0 with (row 2’) + row 0
ERO 3 To create a zero coefficient for x2 in row 1, replace row 1 with (row 2’) + row 1

Optimized Tableau for LP (x1)

Basic
Row z x1 x2 x3 s1 s2 rhs
Variable
0 1 0 -1 3 0 1 1 Z=1
1 0 0 1 -2 1 -1 0 s1 = 1

2 0 1 0 3 0 1 1 x1 = 1
z-value = initial z-value + [1(x1)]
= 0 + [1(1)] = 1 (point at (1,0,0))
Do trial on optimize tableau by using same algorithm steps and repeat until satisfying result found.

Initial Tableau for LP (x2)

Basic
Row -z x1 x2 x3 s1 s2 rhs Ratio
Variable
0 1 -1 -1 0 0 0 0 Z=0
1
1 0 1 1 1 1 0 1 s1 = 1 1
=1

1
2 0 1 0 3 0 1 1 s2 = 1 0
= no feasible
ERO 1 Create a coefficient of 1 for x2 in row 1 by multiplying row 1 by 1
ERO 2 To create a zero coefficient for x1 in row 0, replace row 0 with (row 1’) + row 0
ERO 3 since coefficient of x2 at row 2 already 0, not needed to modify the row

Optimized Tableau for LP (x2)

Basic
Row z x1 x2 x3 s1 s2 rhs
Variable
0 1 0 0 1 1 0 1 Z=1
1 0 1 1 1 1 0 1 x2 = 1

2 0 1 0 3 0 1 1 s2 = 1
z-value = initial z-value + [1(x2)]
= 0 + [1(1)] = 1 (point at (0,1,0))
Result: z = 1 found at two optimum point (1,0,0) and (0,1,0)
By Using Lindo:

Problem 4.8 Number 5 page 160

Show that the following LP is unbounded:
max z = x1 + 2x2
s.t. -x1 + x2 ≤ 2
-2x1 + x2 ≤ 1
x1, x2 ≥ 0
Solution:
Trial1
Determine entering variable
z = x1 + 2x2 → if x1 increased by 1 when x2 set to 0, z increase by 1
if x2 increased by 1 when x1 set to 0, z increase by 2
Because a unit increase in x2 causes the largest rate of increase in z, we choose to increase x2
as the entering variable.

Initial Tableau for LP

Basic
Row z x1 x2 s1 s2 rhs Ratio
Variable
0 1 -1 -2 0 0 0 z=0
 2
1 0 -1 1 1 0 2 s1 = 2 1
=1

1
2 0 -2 1 0 1 1 s2 = 1 1
=1
ERO 1 Create a coefficient of 1 for x2 in row 2 by multiplying row 2 by 1
ERO 2 To create a zero coefficient for x2 in row 0, replace row 0 with 2(row 2’) + row 0
ERO 3 To create a zero coefficient for x2 in row 2, replace row 2 with -(row 2’) + row 1

Optimized Tableau for LP

Basic
Row z x1 x2 s1 s2 rhs
Variable
0’ 1 -5 0 0 2 2 z=2
1’ 0 -3 0 1 1 3 s1 = 3

2’ 0 -2 1 0 1 1 x2 = 1

Because the coefficient of x1 in all row of Optimized Tableau for LP is negative, it can be
concluded that solution of this problem is unbounded
By Using Lindo: