Optimal Solution : Values of Non-Zero Variables

The optimal solution maximizes the objective function and satisfies the given constraints and default contraints: all variables must be greater than or equal to 0.

In this sample problem, ShowSimplex found the (x1, x2, x3, x4) that maximizes the objective function and satisfies the constraints Cons 1, Cons 2, Cons 3, Cons 4, as well as the default constraints x1>=0, x2>=0, x3>=0, x4>=0. The maximum (optimum) value of the objective function z is 6650; the values for (x1, x2, x3, x4) that maximizes the objective and satisfies the constraints is x1=0, x2=400, x3=150, x4= 400. The non-zero variables x2, x3,x4 are called basic variables.

Reduced Cost for Non-Basic Variables

The reduced costs are the objective function coefficients for the original variables at the optimum solution. It is an estimate of how much the objective function will change if you make a zero-valued variable (like x1) non-zero. Note that in this case the objective function value will always decrease.   Reduced Cost is the amount by which the objective function coefficient for the variable needs to change before that variable becomes non-zero. Reduced costs are also called reduced gradients and opportunity costs.

The Reduced Costs = Change in optimal objective function value per unit increase of a corresponding variable currently at a value of zero.  

In this sample problem, suppose we make a new Constraint 6: x1 = 2. This increases x1 from 0 to 2. When we re-solve the problem we expect that the objective function currently valued at 6650 will decrease (by 2*Reduced Cost = 2*1 = 2 ) to 6648. In fact, in this case, the new optimal solution is x1=2, x2=396, x3=152, x4=400.

Slack Values for Constraints

The shadow prices are the objective function coefficients for the slack or surplus variables at the optimum solution. The rate that the objective changes if the Right Hand Side of a constraint is changed. Shadow prices are also called Lagrange multipliers. For each constraint, the shadow price tells how much the objective function will change if we change the Right Hand Side of the constraint within the Allowable Increase and Decrease limits.

The Shadow Price = Change in optimal objective function value per unit increase of a corresponding RHS coefficient.

In this sample problem,  if you change the RHS of Constraint 4 from 950 to 955 and re-solve the problem we expect that the objective function currently valued at 6650 to increase (by 5*Shadow Price = 5*3 =15) to 6665.  In fact, in this case, the new optimal solution is x1=0, x2=420, x3=135, x4=400.

Sensitivity: Constraint Constants (RHS)

This table shows the range of the Right Hand Side (RHS) Coefficients that maintains the current basic solution variables: any RHS change that is greater or less than these values will change the non-zero (basic) variable set.  Note that the values of the basic variables will change. 

In this sample problem, suppose the coefficient of Constraint 4 changes from 950 to 955.  We expect the current basic solution set (x2, x3, x4) to be the same since the allowable interval is [950-100, 950+50].  When we re-solve the problem, the new optimal solution is x1=0, x2=420, x3=135, x4=400 -- the basic variable set is the same (x2, x3, x4). 

If the RHS of Constraint 4 changes from 950 to 1100,  expect the current basic solution set (x2, x3, x4) to be different since the to RHS is outside the allowable interval [950-100, 950+50].  When we re-solve the problem, the new optimal solution is x1=300, x2=400, x3=0, x4=400 -- the basic solution set is now (x1, x2,  x4). 

Sensitivity:Objective Coefficients (Costs)

Final Simplex Tableau