Description
Write a Java program for solving LP by implementing Simplex algorithm
discussed in the lecture. The number n of variables and the number m of
constrains are up to 100 each.
Assume that a given LP is always to maximize the objective function. For each
iteration of the algorithm, use the following rules:
• Choose the variable with the largest coefficient in the objective
function.
• If two or more constraints become tight at the same time, then
choose the constraint that appears on top of other constraint(s); that
is, if we label the constraints as , , , … from top to bottom (like
in the textbook), choose the constraint with the smallest label as
below.
Input
The test cases consist of the following format. In the first line, the number of
test cases is given. From the next line, each test case is provided in m+1 lines.
The first line consists of coefficients of the objective function. From the second
line, each line has coefficients of a constraint and then a constant, assuming
that each constraint has a form of LHS ≤ RHS. Note that the n non-negativity
constraints for n variables are not given in each test case.
2
Sample Input
20
2 3
2 5
2 -1 4
1 2 9
-1 1 3
2 2
1 1
2 -3 5
4 -1 3
…
// the no of test cases.
// n=2, m=3, test case #1
// objective function, max 2𝑥1 + 5𝑥2
// constraint , 2𝑥1 − 𝑥2 ≤ 4
// constraint , 𝑥1 + 2𝑥2 ≤ 9
// constraint ,−𝑥1 + 𝑥2 ≤ 3
// n=2, m=2, test case #2
Output
For each test case, print out a sequence of the objective values obtained from
the iterations of the simplex algorithm in single line. Each real value should be
rounded from the third digit under the decimal point; e.g., for 5/3 = 1.666⋯,
print 1.67.
If the input LP is unbounded, output “unbounded”.
Sample Output
0 15 22 // testcase #1
unbounded // testcase #2
…
