Assignment #7

For this assignment you are going to do some linear programming and write code that can solve linear programs using the simplex algorithm. As with all the assignments, you can write this in whatever language you want, but I have to be able to compile and run it under Linux on the lab machines. What you turn in will be graded for correctness and speed.

Basically you are going to be writing code to do the simplex algorithm. You will also have to write code to take a linear program in standard form and convert it to a format that can go into the simplex algorithm.

The interface for this program will be all text. You will read from standard input and write to standard output. The input will consist of multiple linear programs. Each linear program will begin with a line telling you how many constraints there are. That will be followed with one line for the objective function and then the proper number of lines with constraints.

The objective function and constraints will be given as strings where the linear equations have the form of sums or differences of multiples of x#. So a valid objective function would be 2*x1-3*x2+x3-4*x4-x5. The constraints will have a linear equation followed by <= or >= and a number. You can assume the non-negative constraints on all variables. You should keep reading linear programs until the end of input.

For each linear program you should output a single line that displays one of the following. If there is no feasible solution you should output "No feasible solution." If the feasible region is unbounded you should output "Region unbounded." Otherwise there is a solution and you should output "z=#, x1=#, x2=#, ..." where the # has the maximum value of the objective function as well as the values of the variables that give that maximum variable.

Small input : small output

Large input : large output