COMP572 -- Fall 2004

SIMPLEX Project Specifications

A: (1 person) implement the simplex algorithm

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 a_i1, a_i2, …, a_in, s_i, b_i where a_i1 to a_in and b_i are numbers and s_i is one of “==”, “<=” or “>=”. This line means a_i1x₁ + a_i2x₂ +…+ a_inx_n = b_i if s_i is “==”.The last line contains the cost function s, c₁, c₂, …, c_n where s is either “maximize” or “minimize” and c₁ to c_n 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

• A screen based method for inputting the constraints and objective functions  that
• then transforms the problem into a two-phase tableau for phase 1.
• A method for walking through the tableaus step-by-step, always indicating pivots.
• When phase 1 ends you should either indicate infeasibility or create a tableau using only the original variables that starts at a BFS and then walks through the tableau step by step, always indicating pivots.

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

• A graphical method for inputting/editing a flow network,  e.g., vertices, edges, capacities, denoting the source and sink
• Showing the LP that corresponds to the flow network
• Solving the LP to derive max-flow (it is not necessary to walk through the tableau steps graphically for this one)
• graphically illustrates the derived max-flow and associated min-cut on the flow network.

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

Return to main project page