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 = 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. 
 
 

Topic III
The Simplex Method
Setting up the Method
Tabular Form
Chapter(s): 4

Key Concepts
The simplex method focuses solely on CPF solutions
For any problem with at least one optimal solution, finding one only requires finding a best CPF solution
The simplex method is an iterative algorithm
Initialization
Optimality Test
If no, perform an iteration to find a better solution
If yes, stop
Whenever possible, the initialization of the simplex method chooses the origin to be initial CPF solution

Key Concepts
Given a CPF solution, it is much quicker computationally to gather information about its adjacent CPF solutions that about other solutions
After the current CPF solution is identified, the method identifies the rate of improvement in Z that would be obtained by moving along an edge to an adjacent solution
Chooses to move along the one with the largest rate of improvement in Z
If none of the edges give a positive rate of improvement, then the current CPF solution is optimal

Setting up the Simplex Method
Convert the functional inequality constraints to equivalent equality constraints
Accomplished by introducing slack variables
An augmented solution is a solution for the original (decision) variables that has been augmented by the corresponding values of the slack variables
Example
x1 ≤ 4

Adding slack variable gives x1 + x3 = 4
Note that these are equivalent iff x3 ≥ 0

Setting up the Simplex Method
Original Model (from Topic II)
Maximizing Total profit, Z
Maximize Z = 3×1 + 5×2

Constraints
x1 ≤ 4
2×2 ≤ 12
3×1 + 2×2 ≤ 18

Other constraints
x1 ≥ 0
x2 ≥ 0

Setting up the Simplex Method
Augmented form of the model
Maximizing Total profit, Z
Maximize Z = 3×1 + 5×2

Constraints
x1 + x3 = 4
2×2 + x4 = 12
3×1 + 2×2 + x5 = 18

Other constraints
xj ≥ 0, for j = 1, 2, 3, 4, 5

Setting up the Simplex Method
The system of functional constraints has 5 variables and 3 equations
Number of variables – number of equations = 5 – 3 = 2
2 Degrees of freedom in solving the system (as long as there aren’t any redundant equations)
Set any two variables to an arbitrary value to solve the three equation system
The simplex method uses zero for this arbitrary value
The two variables set to zero are the nonbasic variables
The other three variables are the basic variables

Basic Solution
A basic solution is an augmented corner-point solution
Properties of a basic solution
Each variable is designated as either a nonbasic variable or a basic variable
The number of basic variables equals the number of functional constraints
The number of nonbasic variables equals the total number of variables minus the number of functional constraints

Basic Solution
A basic solution is an augmented corner-point solution
Properties of a basic solution
The nonbasic variables are set to zero
The values of the basic variables are obtained as the simultaneous solution of the system of equations (functional constrains in augmented form)
The set is often referred to as the basis
If the basic variables satisfy the nonnegativity constraints, the basic solution is a BF solution
A basic feasible (BF) solution is an augmented CPF solution

Basic Feasible (BF) Solutions
Two BF solutions are adjacent if all but one of their nonbasic variables are the same
Note that all but one of their basic variables are also the same
Moving from the current BF solution to an adjacent one involves switching one variable from nonbasic to basic (and vice versa for one other variable)
Adjust the values of the basic variables to satisfy the system of equations

The Simplex Method
Step 1: Initialization
Choose x1 and x2 to be the nonbasic variables (the variables set to zero)
Using system of equations, x3, x4, x5 equal 4, 12, 18
Thus, the initial BF solution is (0, 0, 4, 12, 18)

The Simplex Method
Step 2: Optimality Test
The objective function is Z = 3×1 + 5×2
Z = 0 for the initial BF solution
Rate of improvement for x2 is more than x1 (5 > 3)
Increase x2

Minimum Ratio Test
Step 2: Optimality Test
Minimum Ratio Test
Objective is to determine which basic variable drops to zero first as the entering basic variable is increased
The system of equations
x1 + x3 = 4
No upper bound on increasing x2
2×2 + x4 = 12
x4 = 12 – 2×2
Thus, x2 ≤ 6
3×1 + 2×2 + x5 = 18
x5 = 18 – 2×2
Thus, x2 ≤ 9

Since the 2nd equation restricts x2 to 6, x4 is the leaving basic variable for this iteration

Solve for New Solution
Step 3: Solving for the new BF Solution
Original System
Z – 3×1 – 5×2 = 0
x1 + x3 = 4
2×2 + x4 = 12
3×1 + 2×2 + x5 = 18

x2 has replaced x4 as the basic variable
The pattern of coefficients of x4 (0, 0, 1, 0) need to become the coefficients of x2

Solve for New Solution
Step 3: Solving for the new BF Solution
How
Divide constraint equation 2 by 2
x2 + ½x4 = 6

Add 5 times this new equation to the objective function
Z – 3×1 + 5/2 x4 = 30

Subtract 2 times new equation to constraint equation 3
3×1 – x4 + x5 = 6

Solve for New Solution
Step 3: Solving for the new BF Solution
New System
Z – 3×1 + 5/2 x4 = 30
x1 + x3 = 4
x2 + ½x4 = 6
3×1 – x4 + x5 = 6

New BF Solution
(0, 6, 4, 0, 6)

Next Iteration
Next Iteration: Return to Step 2
Z = 30 + 3×1 – 5/2 x4
Z can be increased by increasing x1, but not x4
Thus, x1 needs to be the next entering basic variable
Minimum Ratio Test
x1 + x3 = 4
x1 ≤ 4
x2 + ½x4 = 6
No upper bound on x1
3×1 – x4 + x5 = 6
x1 ≤ 2

x5 is the leaving basic variable

Next Iteration
The pattern of coefficients of x5 (0, 0, 0, 1) needs to become the pattern for x1
Divide constraint equation 3 by 3
x1 – 1/3 x4 + 1/3 x5 = 2

Add 3 times this equation to objective function
Z + 3/2 x4 + x5 = 36

Subtract new equation from constraint equation 1
x3 + 1/3 x4 – 1/3 x5 = 2

Next Iteration
The pattern of coefficients of x5 (0, 0, 0, 1) needs to become the pattern for x1
New System
Z + 3/2 x4 + x5 = 36
x3 + 1/3 x4 – 1/3 x5 = 2
x2 + ½x4 = 6
x1 – 1/3 x4 + 1/3 x5 = 2

New BF Solution
(2, 6, 2, 0, 0)

Final Iteration
Next iteration
Z = 36 – 3/2 x4 – x5

If either nonbasic variable x4 or x5 is increased, Z would decrease
Thus, the current BF solution is optimal
Original variables: x1 and x2
x1 = 2
x2 = 6

Maximum value of Z: 36

Tabular Form
Start with initial equations
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

Tabular Form
Iterations
Determine entering basic variable
Select variable with negative coefficient with largest absolute value
If none, the algorithm is finished
Draw box around column below this variable as the pivot column

Tabular Form
Iterations
Minimum ratio test
Select each coefficient in pivot column that is positive
Divide each coefficient into corresponding right side entry
Identify smallest ratio
Basic variable for that row is leaving basic variable
Replace it by entering basic variable column of table
Box the row and call it the pivot row
The number in both pivot row and pivot column is pivot number

Tabular Form
Iterations
New BF solution
Divide pivot row by pivot number (use this total in next two steps)
For each other row (including row 0) that has a negative coefficient in the pivot column
Add to this row the product of absolute value of this coefficient and new pivot row
For each other row that has a positive coefficient in the pivot column
Subtract from this the product of its coefficient and the new pivot row