6. (20 points) Suppose we are solving a linear program formulated as a minimization prob- lem...

Transcribed Image Text:

6. (20 points) Suppose we are solving a linear program formulated as a minimization prob- lem using the simplex method. When selecting the entering variable, there are at least three different approaches that could be used: Method 1: Dantzig's (Greedy) Rule reduced cost, breaking ties arbitrarily. - select the variable with the most negative Method 2: Largest Decrease Rule - select the variable that would bring about the largest decrease in the objective function, breaking ties arbitrarily. Method 3: Smallest Subscript Rule - when reading the tableau from left to right, select the eligible variable positioned farthest left. (a) Explain why each of these rules are in fact heuristics (in terms of solving the LP via the simplex method by using the fewest number of pivots). (b) Give 1 advantage and 1 disadvantage for each rule. 6. (20 points) Suppose we are solving a linear program formulated as a minimization prob- lem using the simplex method. When selecting the entering variable, there are at least three different approaches that could be used: Method 1: Dantzig's (Greedy) Rule reduced cost, breaking ties arbitrarily. - select the variable with the most negative Method 2: Largest Decrease Rule - select the variable that would bring about the largest decrease in the objective function, breaking ties arbitrarily. Method 3: Smallest Subscript Rule - when reading the tableau from left to right, select the eligible variable positioned farthest left. (a) Explain why each of these rules are in fact heuristics (in terms of solving the LP via the simplex method by using the fewest number of pivots). (b) Give 1 advantage and 1 disadvantage for each rule.

Answer rating: 100% (QA)

a Each of the rules mentioned Dantzigs Rule Largest Decrease Rule and Smallest Subscript Rule are heuristics because they provide a practical and intu... View the full answer