Important note: all code submitted must be your original work. If you use code taken from the internet, an API, or other sources and submit it as your own work you will not get credit for this assignment. Further if your source is not acknowledged, you are subject to the department policies for plagiarism. You may use the java standard libraries for input and output.
Your programs should be uploaded to connex. Please follow the instructions precisely: code that does not compile or that does not work correctly will not be awarded any marks.
It is important to understand the Simplex method well enough that you can program it. Your code can be used later in the course to avoid many tedious algebraic computations.
The input format is:
n m
c1 c2 ... cn
b1 a11 a12 ... a1n
b m am1 am2 ... amn
Your program should be sufficiently flexible to handle arbitrary spacing and also should not make any assumptions regarding how the values are divided onto lines. The code should accept input from the standard input (the user should not type in a file name).
At each iteration, output (in an easily readable format)
If the linear program does not have an initial feasible origin (that is, one of the bi's is strictly less than zero), you should handle this for now by printing out the initial dictionary and a message: ERROR- LP does not have a feasible origin.
Internally,
(i)
Use a tableau as your data structure,
the update procedure is described on pp. 23-25
(think carefully about where to store the
bi's and the objective function so that
the pivoting is simple),
(ii)
The pivoting should be done in place
(do not make a copy of the tableau each time you
pivot).
(iii)
Make the code very modular
(e.g. write one routine for selecting the pivot column,
one routine for selecting the pivot row, ...).
Do not include the detailed code for reading
the input or solving using the Simplex method
as part of the main- call an appropriate method
or function instead to do these things so
your code has a better design.
Your main should adhere to the following pseudocode:
while (read_problem) solve using the Simplex method.
Your program must be able to handle
more than one input problem with
one invocation (not one per input).
(iv)
use epsilon = 10-7 in testing for
positive coefficients in the z row,
(v)
apply the largest coefficient rule to decide
where to pivot, break ties by selecting
the variable with the smallest index.
As a bare minimum for testing,
make an input file called in.txt which has the following 5 problems
and use it to test your program:
Technical note: to use a file
in.txt in place of standard input
and to place the output in a file
out.txt
on a unix machine you would type something like:
a.out < in.txt > out.txt
if you are programming in C/C++ or
java Simplex < in.txt > out.txt
if you are programming in java
(and your main is in Simplex.java).
If you are running on a Microsoft type of machine,
and you have cygwin. then it is similar to the
directions for unix except that the executable for
a C program is usually called ./a.exe instead of a.out.
Otherwise,
first find DOS. On my machine, I can get to it
by using the "Start" menu, selecting "All Programs"
and then under "Accessories" there is an
option "Command Prompt" which gives me the DOS window.
Change to the directory where you have already
compiled your program (maybe using some IDE).
Then type (where the name prog_name depends on your IDE)
prog_name.exe < in.txt > out.txt
if you are programming in C/C++ and
java Simplex < input_file > output_file
if you are programming in java.
You will find this much easier than repeatedly typing
in the same inputs as you are debugging.
Please come for help if you are having problems
with this or need more detailed directions.
For full marks, your code must be well designed, and extensively commented. Include a detailed explanation of the data structures you are using in the comments.
In order to facilitate marking, please follow these instructions when uploading: