INTRODUCTION
It may be desirable to find all optimal corner point feasible solutions when they exist for a variety of reasons. If more than one optimal solution exists, then maybe a constraint or cost was overlooked. What if an optimal solution containing onl y integer values exists, but the initial optimal solution contains fractions? By considering the convex combination of all optimal CPF's, this integer solution can be obtained. Such a solution would be of particular interest to manufacturers who do not create just part of an object. This paper explains an algorithm for finding all optimal corner point feasible solutions, code implementing the algorithm, and several examples demonstrating how the algorithm works.
When can multiple solutions exist and how can we find all of them?
Multiple solutions may exist when a nonbasic variable has a co-efficient of zero in row 0 of the final simplex tableau. If we enter this nonbasic variable, the value of the objective function will not change. This suggests the following recursive algorithm for finding ALL optimal corner point feasible solutions.
ALGORITHM
Input: a final simplex tableau for the linear programming problem in question
Output: a list of all optimal CPF solutions
STEP 1
Record the initial optimal solution and the combination of basic variables and nonbasic variables. Recording this combination of basic and nonbasic variables means recording the variables that are basic and those that are not.
STEP 2
For each nonbasic variable n with a co-efficient of zero in row zero do
{
For each basic variable b satisfying the minimum ratio test do
{
If the combination of basic variables and nonbasic variables when n enters and b
leaves has not been considered before then
{
Enter nonbasic variable n and have basic variable b leave
Record the optimal solution if it's new
Record this new combination of basic and nonbasic variables
Perform STEP 2
Back up a step by entering nonbasic variable b and having basic variable n leave
}
}
}
STEP 3
Print out the list of optimal CPF's
The algorithm mentioned above essentially performs a depth first search on the CPF solution space to find and record all optimal corner point feasible solutions. All optimal solutions can be found by considering the convex combination of optimal CPF's .
SOFTWARE
I wrote a program in C++ which implements the algorithm mentioned above. Prior to running the program, some information must be placed in a file called "test.txt". See appendix A for a full program listing.
SAMPLE INPUT FILE
3 6
0 1 0 1 0
0 0 0 0 8 0
1/3 0 1/3 1 2/3 2/3
-4/3 1 2/3 0 7/3 7/3
EXPLANATION OF INPUT FILE
The first line tells the program that the final simplex tableau contains 3 rows and 6 columns.
The second line tells the program which variables (in order) are basic (denoted by a 1) and nonbasic (denoted by a 0). In this instance x2 and x4 are basic whereas x1, x3, and x5 are not.
The remainder of the input file is the final simplex tableau for a linear programming problem. Entries must be integers and fractions only.
Example 1
Consider the linear programming problem below.
Maximize Z=x1 + x3 subject to
x1<=5
x2<=5
x3<=10
x1 + x3<=10
x1>=0, x2>=0, x3>=0
PROGRAM OUTPUT
START
Below is the original final simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 0 1 10
x4 0 0 0 1 0 1 -1 5
x5 0 1 0 0 1 0 0 5
x3 0 0 1 0 0 1 0 10
x1 1 0 0 0 0 -1 1 0
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,0,10,5,5,0,0)
Notice that the nonbasic variable x2 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 2, so consider entering nonbasic variable x2 and having x5 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x2 and have x5 leave to yield the simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 0 1 10
x4 0 0 0 1 0 1 -1 5
x2 0 1 0 0 1 0 0 5
x3 0 0 1 0 0 1 0 10
x1 1 0 0 0 0 -1 1 0
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,5,10,5,0,0,0)
Notice that the nonbasic variable x5 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 2, so consider entering nonbasic variable x5 and having x2 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
Notice that the nonbasic variable x6 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x6 and having x4 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x6 and have x4 leave to yield the simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 0 1 10
x6 0 0 0 1 0 1 -1 5
x2 0 1 0 0 1 0 0 5
x3 0 0 1 -1 0 0 1 5
x1 1 0 0 1 0 0 0 5
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(5,5,5,0,0,5,0)
Notice that the nonbasic variable x4 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x4 and having x6 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x4 and having x1 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x4 and have x1 leave to yield the simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 0 1 10
x6 -1 0 0 0 0 1 -1 0
x2 0 1 0 0 1 0 0 5
x3 1 0 1 0 0 0 1 10
x4 1 0 0 1 0 0 0 5
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,5,10,5,0,0,0)
Notice that the nonbasic variable x1 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x1 and having x4 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
Notice that the nonbasic variable x5 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 2, so consider entering nonbasic variable x5 and having x2 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x5 and have x2 leave to yield the simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 0 1 10
x6 -1 0 0 0 0 1 -1 0
x5 0 1 0 0 1 0 0 5
x3 1 0 1 0 0 0 1 10
x4 1 0 0 1 0 0 0 5
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,0,10,5,5,0,0)
Notice that the nonbasic variable x1 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x1 and having x4 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x1 and have x4 leave to yield the simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 0 1 10
x6 0 0 0 1 0 1 -1 5
x5 0 1 0 0 1 0 0 5
x3 0 0 1 -1 0 0 1 5
x1 1 0 0 1 0 0 0 5
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(5,0,5,0,5,5,0)
Notice that the nonbasic variable x2 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 2, so consider entering nonbasic variable x2 and having x5 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
Notice that the nonbasic variable x4 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x4 and having x6 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x4 and having x1 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
New possibilities for optimal solutions from
entering x1 and having x4 leave have been exhausted.
Hence back up a step by entering x4 and having x1 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 0 1 10
x6 -1 0 0 0 0 1 -1 0
x5 0 1 0 0 1 0 0 5
x3 1 0 1 0 0 0 1 10
x4 1 0 0 1 0 0 0 5
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,0,10,5,5,0,0)
Notice that the nonbasic variable x2 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 2, so consider entering nonbasic variable x2 and having x5 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
New possibilities for optimal solutions from
entering x5 and having x2 leave have been exhausted.
Hence back up a step by entering x2 and having x5 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 0 1 10
x6 -1 0 0 0 0 1 -1 0
x2 0 1 0 0 1 0 0 5
x3 1 0 1 0 0 0 1 10
x4 1 0 0 1 0 0 0 5
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,5,10,5,0,0,0)
New possibilities for optimal solutions from
entering x4 and having x1 leave have been exhausted.
Hence back up a step by entering x1 and having x4 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 0 1 10
x6 0 0 0 1 0 1 -1 5
x2 0 1 0 0 1 0 0 5
x3 0 0 1 -1 0 0 1 5
x1 1 0 0 1 0 0 0 5
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(5,5,5,0,0,5,0)
Notice that the nonbasic variable x5 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 2, so consider entering nonbasic variable x5 and having x2 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
New possibilities for optimal solutions from
entering x6 and having x4 leave have been exhausted.
Hence back up a step by entering x4 and having x6 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 0 1 10
x4 0 0 0 1 0 1 -1 5
x2 0 1 0 0 1 0 0 5
x3 0 0 1 0 0 1 0 10
x1 1 0 0 0 0 -1 1 0
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,5,10,5,0,0,0)
New possibilities for optimal solutions from
entering x2 and having x5 leave have been exhausted.
Hence back up a step by entering x5 and having x2 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 0 1 10
x4 0 0 0 1 0 1 -1 5
x5 0 1 0 0 1 0 0 5
x3 0 0 1 0 0 1 0 10
x1 1 0 0 0 0 -1 1 0
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,0,10,5,5,0,0)
Notice that the nonbasic variable x6 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x6 and having x4 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
This program has now located all optimal CPF's
To find all optimal solutions, simply take a convex combination
of the unique optimal CPF's listed above.
END
COMMENTS
The unique optimal CPF's are (0,0,10), (0,5,10), (5,0,5), and (5,5,5)
Taking the convex combination of those CPF's, we find that all solutions are of the form
(5c+5d,5b+5d,10a+10b+5c+5d) where a+b+c+d=1 and a>=0,b>=0,c>=0,d>=0
Example 2
Consider the linear programming problem below.
Maximize Z=x3 subject to
x1<=1
x2<=1
x3<=10
x1 + x2<=1
x1>=0, x2>=0, x3>=0
PROGRAM OUTPUT
START
Below is the original final simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x4 1 0 0 1 0 0 0 1
x5 0 1 0 0 1 0 0 1
x3 0 0 1 0 0 1 0 10
x7 1 1 0 0 0 0 1 1
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,0,10,1,1,0,1)
Notice that the nonbasic variable x1 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x1 and having x4 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x1 and have x4 leave to yield the simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x1 1 0 0 1 0 0 0 1
x5 0 1 0 0 1 0 0 1
x3 0 0 1 0 0 1 0 10
x7 0 1 0 -1 0 0 1 0
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(1,0,10,0,1,0,0)
Notice that the nonbasic variable x2 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x2 and having x7 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x2 and have x7 leave to yield the simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x1 1 0 0 1 0 0 0 1
x5 0 0 0 1 1 0 -1 1
x3 0 0 1 0 0 1 0 10
x2 0 1 0 -1 0 0 1 0
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(1,0,10,0,1,0,0)
Notice that the nonbasic variable x4 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x4 and having x1 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x4 and have x1 leave to yield the simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x4 1 0 0 1 0 0 0 1
x5 -1 0 0 0 1 0 -1 0
x3 0 0 1 0 0 1 0 10
x2 1 1 0 0 0 0 1 1
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,1,10,1,0,0,0)
Notice that the nonbasic variable x1 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x1 and having x4 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x1 and having x2 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x1 and have x2 leave to yield the simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x4 0 -1 0 1 0 0 -1 0
x5 0 1 0 0 1 0 0 1
x3 0 0 1 0 0 1 0 10
x1 1 1 0 0 0 0 1 1
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(1,0,10,0,1,0,0)
Notice that the nonbasic variable x2 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 2, so consider entering nonbasic variable x2 and having x5 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x2 and have x5 leave to yield the simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x4 0 0 0 1 1 0 -1 1
x2 0 1 0 0 1 0 0 1
x3 0 0 1 0 0 1 0 10
x1 1 0 0 0 -1 0 1 0
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,1,10,1,0,0,0)
Notice that the nonbasic variable x5 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x5 and having x4 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
A minimum ratio is achieved in row 2, so consider entering nonbasic variable x5 and having x2 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
Notice that the nonbasic variable x7 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x7 and having x1 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x7 and have x1 leave to yield the simplex tableau
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x4 1 0 0 1 0 0 0 1
x2 0 1 0 0 1 0 0 1
x3 0 0 1 0 0 1 0 10
x7 1 0 0 0 -1 0 1 0
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,1,10,1,0,0,0)
Notice that the nonbasic variable x1 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x1 and having x7 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
Notice that the nonbasic variable x5 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 2, so consider entering nonbasic variable x5 and having x2 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
New possibilities for optimal solutions from
entering x7 and having x1 leave have been exhausted.
Hence back up a step by entering x1 and having x7 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x4 0 0 0 1 1 0 -1 1
x2 0 1 0 0 1 0 0 1
x3 0 0 1 0 0 1 0 10
x1 1 0 0 0 -1 0 1 0
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,1,10,1,0,0,0)
New possibilities for optimal solutions from
entering x2 and having x5 leave have been exhausted.
Hence back up a step by entering x5 and having x2 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x4 0 -1 0 1 0 0 -1 0
x5 0 1 0 0 1 0 0 1
x3 0 0 1 0 0 1 0 10
x1 1 1 0 0 0 0 1 1
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(1,0,10,0,1,0,0)
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x2 and having x1 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
Notice that the nonbasic variable x7 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x7 and having x1 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
New possibilities for optimal solutions from
entering x1 and having x2 leave have been exhausted.
Hence back up a step by entering x2 and having x1 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x4 1 0 0 1 0 0 0 1
x5 -1 0 0 0 1 0 -1 0
x3 0 0 1 0 0 1 0 10
x2 1 1 0 0 0 0 1 1
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,1,10,1,0,0,0)
Notice that the nonbasic variable x7 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x7 and having x2 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
New possibilities for optimal solutions from
entering x4 and having x1 leave have been exhausted.
Hence back up a step by entering x1 and having x4 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x1 1 0 0 1 0 0 0 1
x5 0 0 0 1 1 0 -1 1
x3 0 0 1 0 0 1 0 10
x2 0 1 0 -1 0 0 1 0
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(1,0,10,0,1,0,0)
A minimum ratio is achieved in row 2, so consider entering nonbasic variable x4 and having x5 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
Notice that the nonbasic variable x7 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x7 and having x2 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
New possibilities for optimal solutions from
entering x2 and having x7 leave have been exhausted.
Hence back up a step by entering x7 and having x2 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x1 1 0 0 1 0 0 0 1
x5 0 1 0 0 1 0 0 1
x3 0 0 1 0 0 1 0 10
x7 0 1 0 -1 0 0 1 0
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(1,0,10,0,1,0,0)
Notice that the nonbasic variable x4 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x4 and having x1 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
New possibilities for optimal solutions from
entering x1 and having x4 leave have been exhausted.
Hence back up a step by entering x4 and having x1 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 x6 x7 RHS
--------------------------------------------------------
Z 0 0 0 0 0 1 0 10
x4 1 0 0 1 0 0 0 1
x5 0 1 0 0 1 0 0 1
x3 0 0 1 0 0 1 0 10
x7 1 1 0 0 0 0 1 1
The corresponding solution is
(x1,x2,x3,x4,x5,x6,x7)=(0,0,10,1,1,0,1)
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x1 and having x7 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
Notice that the nonbasic variable x2 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 2, so consider entering nonbasic variable x2 and having x5 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
A minimum ratio is achieved in row 4, so consider entering nonbasic variable x2 and having x7 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
This program has now located all optimal CPF's
To find all optimal solutions, simply take a convex combination
of the unique optimal CPF's listed above.
END
COMMENTS
The unique optimal CPF's are (0,0,10), (0,1,10), and (1,0,10)
Taking the convex combination of those CPF's, we find that all solutions are of the form
(c,b,10a+10b+10c) where a+b+c=1 and a>=0,b>=0,c>=0.
Example 3
Consider the linear programming problem below.
Maximize Z= -8x5 subject to
x1 + x3 + 3x4 + 2x5 =2
x2 + 2x3 + 4x4 + 5x5=5
x1>=0, x2>=0, x3>=0,x4>=0,x5>=0
PROGRAM OUTPUT
START
Below is the original final simplex tableau
x1 x2 x3 x4 x5 RHS
------------------------------------------
Z 0 0 0 0 8 0
x4 1/3 0 1/3 1 2/3 2/3
x2 -4/3 1 2/3 0 7/3 7/3
The corresponding solution is
(x1,x2,x3,x4,x5)=(0,7/3,0,2/3,0)
Notice that the nonbasic variable x1 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x1 and having x4 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x1 and have x4 leave to yield the simplex tableau
x1 x2 x3 x4 x5 RHS
------------------------------------------
Z 0 0 0 0 8 0
x1 1 0 1 3 2 2
x2 0 1 2 4 5 5
The corresponding solution is
(x1,x2,x3,x4,x5)=(2,5,0,0,0)
Notice that the nonbasic variable x3 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x3 and having x1 leave.
This combination of basic and nonbasic variables has not been tried before.
Therefore, enter x3 and have x1 leave to yield the simplex tableau
x1 x2 x3 x4 x5 RHS
------------------------------------------
Z 0 0 0 0 8 0
x3 1 0 1 3 2 2
x2 -2 1 0 -2 1 1
The corresponding solution is
(x1,x2,x3,x4,x5)=(0,1,2,0,0)
Notice that the nonbasic variable x1 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x1 and having x3 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
Notice that the nonbasic variable x4 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x4 and having x3 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
New possibilities for optimal solutions from
entering x3 and having x1 leave have been exhausted.
Hence back up a step by entering x1 and having x3 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 RHS
------------------------------------------
Z 0 0 0 0 8 0
x1 1 0 1 3 2 2
x2 0 1 2 4 5 5
The corresponding solution is
(x1,x2,x3,x4,x5)=(2,5,0,0,0)
Notice that the nonbasic variable x4 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x4 and having x1 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
New possibilities for optimal solutions from
entering x1 and having x4 leave have been exhausted.
Hence back up a step by entering x4 and having x1 leave.
This yields the following tableau encountered earlier:
x1 x2 x3 x4 x5 RHS
------------------------------------------
Z 0 0 0 0 8 0
x4 1/3 0 1/3 1 2/3 2/3
x2 -4/3 1 2/3 0 7/3 7/3
The corresponding solution is
(x1,x2,x3,x4,x5)=(0,7/3,0,2/3,0)
Notice that the nonbasic variable x3 has a co-efficient of zero in row 0.
A minimum ratio is achieved in row 1, so consider entering nonbasic variable x3 and having x4 leave.
This combination of basic and nonbasic variables has been considered before so there's no reason to try it again.
This program has now located all optimal CPF's
To find all optimal solutions, simply take a convex combination
of the unique optimal CPF's listed above.
END
COMMENTS
The unique optimal CPF's are (0,7/3,0,2/3,0), (2,5,0,0,0), and (0,1,2,0,0).
Taking the convex combination of those CPF's, we find that all solutions are of the form
(2b,7a/3+5b+c,2c,2a/3,0) where a+b+c=1 and a>=0,b>=0,c>=0.
APPENDIX A
In this appendix you will find software implementing the algorithm discussed in this paper. The four files needed to consider linear programming problems of your own are
A digital copy of this software can be obtained by contacting Bryan Cooley by email at
coolbry@cse.unl.edu.
FRACTION.H
//---------------------------------------------------------
//AUTHOR Bryan Cooley
//FILENAME fraction.h
//DATE 4/20/1999
//This is the header file for class fraction
//---------------------------------------------------------
#include <iostream.h>
#include <stdlib.h>
class fraction
{
public:
fraction(long n=0, long d=1): num(n), denom(d) {reduce();}
fraction(const fraction& f): num(f.num), denom(f.denom) {}
friend fraction operator+ (fraction f1, fraction f2);
friend fraction operator- (fraction f1, fraction f2);
friend fraction operator* (fraction f1, fraction f2);
friend fraction operator/ (fraction f1, fraction f2);
friend int operator< (fraction f1, fraction f2);
friend int operator== (fraction f1, fraction f2);
friend istream& operator >>(istream& ins, fraction &f);
friend ostream& operator << (ostream& outs, fraction f);
fraction reciprocal();
void reduce();
long Num() {return num;}
long Denom() {return denom;}
long isZero() {return (num==0);}
long isOne() {return ((num==1)&&(denom==1));}
private:
long num;
long denom;
};
FRACTION.CPP
//---------------------------------------------------------
//AUTHOR Bryan Cooley
//FILENAME fraction.cpp
//DATE 4/20/1999
//The fraction class provides an easy way to read, print,
//and manipulate fractions.
//---------------------------------------------------------
#include "fraction.h"
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
//a recursive algorithm for finding the greatest
//common divisor of two integers
long gcd(long j, long k)
{
if (k==0)
return j;
return gcd(k,j%k);
}
//overloads the + operator to ease fraction addition
fraction operator+ (fraction f1, fraction f2)
{
fraction f3;
f3.num=f1.num*f2.denom+f2.num*f1.denom;
f3.denom=f1.denom*f2.denom;
f3.reduce();
return f3;
}
//overloads the - operator to ease fraction subtraction
fraction operator- (fraction f1, fraction f2)
{
fraction f3;
f3.num=f1.num*f2.denom-f2.num*f1.denom;
f3.denom=f1.denom*f2.denom;
f3.reduce();
return f3;
}
//overloads the * operator to ease fraction multiplication
fraction operator* (fraction f1, fraction f2)
{
fraction f3;
f3.num=f1.num*f2.num;
f3.denom=f1.denom*f2.denom;
f3.reduce();
return f3;
}
//overloads the / operator to ease fraction division
fraction operator/ (fraction f1, fraction f2)
{
fraction f3;
if (f2.num==0)
{
cout << "division by zero\n";
f3.num=0;
f3.denom=0;
return f3;
}
f3.num=f1.num*f2.denom;
f3.denom=f1.denom*f2.num;
f3.reduce();
return f3;
}
//overloads the < operator to ease fraction comparisons
int operator< (fraction f1, fraction f2)
{
double d1=(1.0*f1.num)/(1.0*f1.denom);
double d2=(1.0*f2.num)/(1.0*f2.denom);
if (d1<d2)
return 1;
else
return 0;
}
//overloads the == operator to ease fraction comparisons
int operator== (fraction f1, fraction f2)
{
return ((f1.num==f2.num)&&(f1.denom==f2.denom));
}
//overloads the >> operator to ease fraction input
istream& operator >> (istream& ins, fraction &f)
{
long n,d;
char ch;
ins >> n;
ch=ins.peek();
if (ch=='/')
{
ins >> ch >> d;
}
else
d=1;
fraction f2(n,d);
f=f2;
return ins;
}
//overloads the << operator to ease fraction output
ostream& operator << (ostream& outs, fraction f)
{
outs << f.num;
if ((f.denom!=1)&&(f.denom!=-1))
outs << "/" << f.denom;
return outs;
}
//returns the reciprocal of a fraction
fraction fraction::reciprocal()
{
if (num==0)
cout << "reciprocal undefined - original frac was zero\n";
fraction f(denom,num);
return f;
}
//reduces a fraction to lowest terms
void fraction::reduce()
{
long d=(gcd(num,denom));
num/=d;
denom/=d;
if ((num>0)&&(denom<0))
{
num=-num;
denom=-denom;
}
}
TABLE.H
//---------------------------------------------------------
//AUTHOR Bryan Cooley
//FILENAME table.h
//DATE 4/20/1999
//This is the header file for class table
//---------------------------------------------------------
#include "fraction.h"
class table
{
public:
table(long num_of_rows, long num_of_cols);
void set(long row, long col, fraction f);
void swapbasicvars(long i, long j);
void mulrow(long row, fraction f);
void addrow(long row1, long row2);
void print();
void findcurrsol();
void printcurrsol();
fraction ratio(long row, long col);
fraction minratio(long col);
void findall(long i, long j);
int checkcombo();
void bvsetup();
fraction currsol[100];
int bvlist[100];
long bv[100];
long combos[100];
long combostried;
private:
fraction A[50][50];
long numrows;
long numcols;
};
TABLE.CPP
//---------------------------------------------------------
//AUTHOR Bryan Cooley
//FILENAME table.cpp
//DATE 4/20/1999
//This file contains the table class's definition.
//Essentially the table class allows one to read in
//the final simplex tableau for a linear programming
//problem and will find all optimal corner point feasible
//solutions. This class depends on class fraction,
//so be certain to keep a hold of that code as well.
//When reading code, remember that in C++ you start counting
//with 0. That means, for example, that information about
//variable x3 is stored in location 2.
//---------------------------------------------------------
#include "table.h"
#include <fstream.h>
#include <math.h>
//perform basic initializations
table::table(long num_of_rows, long num_of_cols)
{
numrows=num_of_rows;
numcols=num_of_cols;
combostried=0;
}
//print the current simplex tableau
void table::print()
{
cout << "\t";
for (long k=0;k<numcols-1;k++)
cout << "x" << k+1 << "\t";
cout << "RHS\n";
for (k=0;k<numcols;k++)
{
cout << "-------";
}
cout << "\n";
for (long i=0;i<numrows;i++)
{
if (i>0)
cout << "x" << bv[i]+1 << "\t";
else
cout << "Z\t";
for (long j=0;j<numcols;j++)
{
cout << A[i][j] << "\t";
}
cout << endl;
}
cout << "\nThe corresponding solution is\n";
printcurrsol();
}
//set the element of the simplex tableau at coordinate (row,col)
void table::set(long row, long col, fraction f)
{
A[row][col]=f;
}
//multiply an entire tableau row by a fraction
void table::mulrow(long row, fraction f)
{
for (long i=0;i<numcols;i++)
{
A[row][i]=A[row][i]*f;
}
}
//subtract row #row2 from row #row1
void table::addrow(long row1, long row2)
{
for (long i=0;i<numcols;i++)
{
A[row1][i]=A[row1][i]-A[row2][i];
}
}
//enter nonbasic x_(i+1) and have the basic var
// in row j leave
void table::swapbasicvars(long i, long j)
{
fraction quotient;
mulrow(j,(A[j][i]).reciprocal());
for (long k=0;k<numrows;k++)
{
if ((k!=j)&&(!A[k][i].isZero()))
{
fraction divisor=A[k][i]/A[j][i];
mulrow(j,divisor);
addrow(k,j);
mulrow(j,divisor.reciprocal());
}
}
}
fraction table::ratio(long row, long col)
{
fraction f;
f=A[row][numcols-1]/A[row][col];
return f;
}
//find the minimum ratio for an entering nonbasic variable
fraction table::minratio(long col)
{
fraction min(99999,1),f;
int minexists=0;
for (long i=1;i<numrows;i++)
{
fraction zero(0,10);
if (zero<A[i][col])
{
f=ratio(i,col);
if (minexists==0)
{minexists=1;
min=f;
}
else if (f<min)
min=f;
}
}
if (minexists==0)
cout << "no minimum ratio found" << endl;
return min;
}
//Takes the simplex tableau and finds the current solution
void table::findcurrsol()
{
for (long k=0;k<numcols-1;k++)
{
fraction f;
currsol[k]=f;
}
for (long j=0;j<numcols-1;j++)
{
if (bvlist[j]==1)
{
for (long i=0;i<numrows;i++)
if (A[i][j].isOne())
{
currsol[j]=A[i][numcols-1];
bv[i]=j;
}
}
}
}
//prints out the current solution in a pretty fashion
void table::printcurrsol()
{
findcurrsol();
cout << "(";
for (long i=1;i<numcols;i++)
{
cout << "x" << i;
if (i<numcols-1)
cout << ",";
else
cout << ")=(";
}
for (i=0;i<numcols-1;i++)
{
cout << currsol[i];
if (i<numcols-2)
cout << ",";
else
cout << ")\n\n";
}
}
//check to see if the combination of basic and nonbasic variables
//has been tried before
int table::checkcombo()
{
long sum=0;
int triedbefore=0;
for (long i=0;i<numcols-1;i++)
sum+=bvlist[i]*pow(2,i);
for (long j=0;j<combostried;j++)
if (sum==combos[j])
triedbefore=1;
if (!triedbefore)
{
combos[combostried]=sum;
combostried++;
cout << "This combination of basic and nonbasic variables has ";
cout << "not been tried before.\n";
}
else
{
cout << "This combination of basic and nonbasic variables has been considered ";
cout << "before so there's no reason to try it again.\n\n";
}
return triedbefore;
}
//Find all the optimal CPF's
//call as findall(-1,-1) to get started
void table::findall(long i, long j)
{
if ((i!=-1)&&(j!=-1)) // if the loop isn't being entered for
// the first time
{
swapbasicvars(i,j);
}
else
{
cout << "Below is the original final simplex tableau\n\n";
}
print();
for (int k=0;k<numcols-1;k++)
{
if ((bvlist[k]==0)&&(A[0][k].isZero()))
{
cout << "Notice that the nonbasic variable x" << k+1;
cout << " has a co-efficient of zero in row 0.\n";
fraction min=minratio(k);
for (int l=1;l<numrows;l++)
{
if (((!A[l][k].isZero()))&&(ratio(l,k)==min))
{
cout << "A minimum ratio is achieved in row " << l << ", ";
cout << "so consider entering nonbasic variable x" << k+1;
cout << " and having x" << bv[l]+1 << " leave.\n";
long oldbvl=bv[l];
bvlist[k]=1;
bvlist[bv[l]]=0;
long check=checkcombo();
if (!check)
{
cout << "Therefore, enter x" << k+1 << " and have x" <<
bv[l]+1 << " ";
cout << "leave to yield the simplex tableau.\n\n";
bv[l]=k;
findall(k,l);
}
bv[l]=oldbvl;
bvlist[k]=0;
bvlist[oldbvl]=1;
if (!check)
{
cout << "New possibilities for optimal solutions from\n";
cout << "entering x" << k+1 << " and having x";
cout << bv[l]+1 << " leave have been exhausted.\n";
cout << "Hence back up a step by entering x" << bv[l]+1;
cout << " and having x" << k+1 << " leave.\n";
cout << "This yields the following tableau encountered
earlier:\n\n";
swapbasicvars(bv[l],l);
print();
}
}
}
}
}
}
//records which basic variables go with each row of the
//simplex tableau
void table::bvsetup()
{
for (long j=0;j<numcols-1;j++)
if (bvlist[j]==1)
{
for (long i=1;i<numrows;i++)
if ((A[i][j]).isOne())
{
bv[i]=j;
}
}
}
//MAIN BODY - reads in the input and calls the main procedures
//responsible for finding all optimal CPF's
void main()
{
ifstream in_stream;
long num_rows, num_cols;
in_stream.open("test.txt");
if (in_stream.fail())
{
cout << "Input file opening failed";
}
in_stream >> num_rows >> num_cols;
table t(num_rows,num_cols);
for (long h=0;h<num_cols-1;h++)
{
in_stream >> t.bvlist[h];
}
for (long i=0;i<num_rows;i++)
for (long j=0;j<num_cols;j++)
{
fraction f;
in_stream >> f;
t.set(i,j,f);
}
t.checkcombo();
cout << "START" << endl;
t.bvsetup();
t.findall(-1,-1);
cout << "\nThis program has now located all optimal CPF's\n";
cout << "To find all optimal solutions, simply take a convex
combination\n";
cout << "of the unique optimal CPF's listed above.\nEND\n";
in_stream.close();
}