# A-4

# Module A

# The Simplex Solution Method

Then, solve for s_{2 }in the second equation:

s 2 = 6 0 3 ( 2 0 ) + s 2 = 1 2 0 3 x 2 + s 2 = 1 2 0

A basic feasible solution satisfies the model constraints and has the same number of variables with nonnegative values as there are constraints.

This solution corresponds to point A in Figure A-1. The graph in Figure A-1 shows that at point A, x_{1 }= 0, x_{2 }= 20, s_{1 }= 0, and s_{2 }= 60, the exact solution obtained by solving simultaneous equations. This solution is referred to as a basic feasible solution. A feasible solution is any solution that satisfies the constraints. A basic feasible solution satisfies the constraints and contains as many variables with nonnegative values as there are model constraints—that is, m variables with nonnegative values and n - m values set equal to zero. Typically, the m variables have positive nonzero solution values; however, when one of the m variables equals zero, the basic feasible solution is said to be degenerate. (The topic of degeneracy will be discussed at a later point in this module.)

Figure A-1 Solutions at points A, B, and C

x_{2 }

40

30

20

10

0

x + 2x + s = 40

1

2

1

2 x = 20

1 x = 24

1 s =0

2 x =8

2 s = 60

1 s =0

A

4 x 1 + 3 x 2 + s 2 = 1 2 0

x 1 = 0

s 2 = 0

10

B

x 1 = 3 0 x 2 = 0 s 1 = 1 0 s 2 = 0

40

x_{1 }

20

C 30

Consider a second example where x_{2 }= 0 and s_{2 }= 0. These values result in the follow- ing set of equations:

4 x 1 + 3 x 2 + s 2 = 1 2 0 x 1 + 2 x 2 + s 1 = 4 0

and

x_{1 }+ 0 + s_{1 }= 40 4x_{1 }+ 0 + 0 = 120

Solve for x_{1}:

x 1 = 3 0 4 x 1 = 1 2 0

# Then solve for s_{1}:

s 1 = 1 0 3 0 + s 1 = 4 0

This basic feasible solution corresponds to point C in Figure A-1, where x_{1 }= 30, x_{2 }= 0, s_{1 }= 10, and s_{2 }= 0.