Assignment #3 (80 Points) – COSC 5390 –Dr. Leonard BrownDue: April 4, 2013 (atthe beginning of class)Problem DescriptionWrite a java…

Assignment #3 (80 Points) – COSC 5390 –Dr. Leonard Brown Due: April 4, 2013 (atthe beginning of class) Problem Description Write a java program that will implement the Simplex algorithm discussed in class that will solve a systemof equationsin the following form. Maximize Z = c 1x 1 +…+ c nx n Subjectto a 11x 1 +…+ a 1nx n ≤ b1 a 21x 1 +…+ a 2nx n ≤ b2 … a m1x 1 +…+ a mnx n ≤ b m and xi  ≥ 0 fori=1,…,n Input The input programwill be a systemof inequalities augmented with slack variablesso thatitisin a formsuitable forthe “table”method. So, ifthe goal wasto solve the following system: Maximize Z = 3×1 + 5×2 x 1 ≤ 4 2×2 ≤ 12 3×1 + 2×2 ≤ 18 xj  ≥ 0,forj = 1, 2 Then the input to the program will be represented by the following system of equations (with the slack variablesincluded). Z – 3x 1 – 5x 2 = 0 x 1 + x 3 = 4 2×2 + x 4 = 12 3×1 + 2×2 + x 5 = 18 More specifically,the inputto the programwould be the following lines oftext 1 -3 -5 0 0 0 0 0 1 0 1 0 0 4 0 0 2 0 1 0 12 0 3 2 0 0 1 18 Which comesfromthe shaded area in the following table: Basic Var Eq Z x 1 x 2 x 3 x 4 x 5 Right Side Z 0 1 ‐3 ‐5 0 0 0 0 x 3 1 0 1 0 1 0 0 4 x 4 2 0 0 2 0 1 0 12 x 5 3 0 3 2 0 0 1 18

Assignment #3 (80 Points) – COSC 5390 – Dr. Leonard Brown 
Due:  April 4, 2013 (at the beginning of class) 

Problem Description 
Write  a  java  program  that  will  implement  the  Simplex  algorithm  discussed  in  class  that  will 
solve a system of equations in the following form. 

Maximize 
Z = c1x1 + … + cnxn 

Subject to 
a11x1 + … + a1nxn ≤ b1 
a21x1 + … + a2nxn ≤ b2 
… 
am1x1 + … + amnxn ≤ bm 

and 
xi ≥ 0 for i=1,…,n 

 
 
Input 
The input program will be a system of inequalities augmented with slack variables so that it is in 
a form suitable for the “table” method.  So, if the goal was to solve the following system: 

Maximize Z = 3×1 + 5×2 
x1 ≤ 4 
2×2 ≤ 12 
3×1 + 2×2 ≤ 18 
xj ≥ 0, for j = 1, 2 

 
Then the input to the program will be represented by the following system of equations (with 
the slack variables included). 

Z – 3×1 – 5×2 = 0 
x1 + x3 = 4 
2×2 + x4 = 12 
3×1 + 2×2 + x5 = 18 

 
More specifically, the input to the program would be the following lines of text 
1 -3 -5 0 0 0 0
0 1 0 1 0 0 4
0 0 2 0 1 0 12
0 3 2 0 0 1 18
 
Which comes from the shaded area in the following table: 
Basic Var  Eq  Z  x1  x2  x3  x4  x5  Right Side

Z  0  1  ‐3  ‐5  0  0  0  0 

x3  1  0  1  0  1  0  0  4 

x4  2  0  0  2  0  1  0  12 

x5  3  0  3  2  0  0  1  18 

Output 
The  program  should  display  the  simplex  table  after  each  iteration  of  the  algorithm.    There 
should be at  least one blank  line between each pair of tables.   After the optimal solution  is 
found, the program should print at least one blank link followed by the optimal solution.  In the 
given example, the optimal solution is (2, 6, 2, 0, 0). 
 
 
 
Assumptions 

 All constraints will be of the form a11x1 + … + a1nxn ≤ b1.  Thus, you will not have to solve 
greater than or greater than inequality constraints. 

 In  addition  to  the  objective  function,  there  will  be  three  inequalities  in  the  system.  
Thus, the input will be a grid with four rows. 

 There will be at most 10 total columns in the input grid. 
 The  last column  in the  input grid represents the right hand side.   The three columns 

immediately preceding this last column represent the slack variables. 
 
 
Submission 
Submit  your  assignment  through  Blackboard.    If  your  assignment  contains  multiple  files,  zip 
them into a single folder before submitting. 
 
 
 
Notes 
Points  can  be  deducted  from  your  assignment  based  on  the  quality  of  its  presentation.  
Handwritten assignments will not be accepted.