COMP572 -- Fall 2004
You should implement the standard simplex algorithm as taught in class. The input is read from standard input or a file (your documentation should indicate which)
The first line contains two integers m, n where m is the number equations in
the LP and n is the number of variables in the LP. The next m lines of the input
will be the description of an LP in general form. The i-th line contains ai1,
ai2, …, ain, si, bi where ai1 to ain and bi are numbers and si is one of “==”,
“<=” or “>=”. This line means ai1x1 + ai2x2 +…+ ainxn = bi if si is “==”.The
last line contains the cost function s, c1, c2, …, cn where s is either
“maximize” or “minimize” and c1 to cn is numbers. You can assume m, n are at
most 30. Your code does not have to worry about underflow/overflow.
Note that you will NOT be given an original BFS and therefore need to
implement the two-phase method.
Output:
If there is a bounded feasible solution:
i)
Print out the minimum/maximum value of the cost function of the LP with 3
decimal digits in the first line.
ii)
Print out the solution x1 to xn with 3 decimal digits in next line.
Note that the solution may not be unique. You just need to output one of them.
Follow the format as sample output. Don’t print any other text character. Always
use space to separate two values.
Sample input: (Linear Programming - Simplex part 3, page 6)
3 5 3.0 2.0 1.0 0.0 0.0 == 1.0 5.0 1.0 1.0 1.0 0.0 == 3.0 2.0 5.0 1.0 0.0 1.0 == 4.0 minimize 1.0 1.0 1.0 1.0 1.0
Sample output:
4.500 0.000 0.500 0.000 2.500 1.500
If there are feasible solutions but objective is unbounded
i) Print out the word "unbounded" on the first line
ii) Print out "any" feasible solution on next line (using same format as above)
Sample output:
UNBOUNDED 0.000 0.500 0.000 2.500 1.500
If there is no feasible solution
Print out the single word "infeasible" and stop
Sample output:
INFEASIBLE
B: (2 person) implement part (A) and a GUI for simplex, showing tableaus
Your program should also include a GUI that includes
Note that during phase 1 you might encounter redundant constraints and have to throw them away. This would require changing the tableau.
Note too, that, even with the GUI, your program should also permit inputting text data via standard input or from a file following the specifications from part (A).
For the GUI part, you may assume that m, n <=20.
C: (3 person) implement part (B) and, for n-m=2, draws 2D polygon and shows correspondence of tableaus and polygon
Implement everything in part B. In addition, for n-m-2, once the second phase starts, it draws the 2D polygon associated with the problem and then, for every pivot, indicates the correspondence between the pivot and movement on the polygon. Your GUI should permit the user to decide which two variables should be used to define the drawing plane.
D: (3 person) implements part (B) and another GUI that allows entering a max-flow problem and then uses simplex to solve max flow.
Implement everything in part B. In addition, implement another GUI (could be linked to the first one) that allows
For your GUI you may assume that there are at most n=20 vertices in the graph.
This page was released on November 19, 2004 and last revised on 11/19/2004 10:37 +0800