Allen Only

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 = 3x1 + 5x2  x1 ≤ 4  2x2 ≤ 12  3x1 + 2x2 ≤ 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 – 3x1 – 5x2 = 0  x1 + x3 = 4  2x2 + x4 = 12  3x1 + 2x2 + 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.