Chapter 5.2, Problem 8P

(a)

Program Plan Intro

• Let us consider on the following Linear programming;
• max z=9x₁+8x₂+5x₃+4x₄
• Such that
  • x₁+x₄≤200
  • x₂+x₃≤150
  • x₁+x₂+x₃≤350
  • 2x₁+x₂+x₃+x₄≤550
  • x₁,x₂,x₃,x₄≥0
• The LINDO output for this Linear Programming is given below:
• Max 9x₁+8x₂+5x₃+4x₄
• Subject to constraints:
  • x₁+x₄≤200
  • x₂+x₃≤150
  • x₁+x₂+x₃≤350
  • 2x₁+x₂+x₃+x₄≤550
• End
• LP optimum found at step 4
• Objective function value: 3000.000

Variable	Value	Reduced Cost
x1	200.000000	0.000000
x2	150.000000	0.000000
x3	0.000000	3.000000
x4	0.000000	0.000000

• Number of iterations=4
• Ranges in which the basis is unchanged:

Variable	Current Coefficient	Obj Coefficient ranges allowable increase	Allowance Decrease
x1	9.000000	7.000000	1.000000
x2	8.000000	Infinity	3.000000
x3	5.000000	3.000000	Infinity
x4	4.000000	0.500000	Infinity

Row	Current RHS	Righthand side ranges allowable increase	Allowance decrease
2	200.000000	Infinity	0.000000
3	150.000000	0.000000	0.000000
4	350.000000	Infinity	0.000000
5	550.000000	0.000000	400.000000

(b)

Explanation of Solution

• Here, three oddities that may occur when the optimal solution found by LINDO is degenerate.
• Oddity 1: In the ranges in which the basis is unchanged, at least one constraint will have a 0. Allowable increase or Allowable decrease.
• This means that for at least one constraint, the dual price can tell us about the new z-value for either an increase or decrease in the right-hand side, but not both.
• To understand Oddity 1, consider the second constraint. Its allowable increase is 0.
• This means that the second constraint’s dual price of 3 cannot be used to determine a new z-value resulting from any increase in the first constraint’s right-hand side.
• Oddity 2: For a non-basic variable to become positive, its objective function coefficient may have to be improved by more than it reduced cost...