21 Special cases of linear programming problem-Degeneracy

Operation Research: Special cases of linear programming problem-degeneracy

​Learning Objective

​Special Case of Linear Programming Solution

Degenerate Linear Programming Solution

Finding the solution to degenerate Linear Programming

​Learning Objective

1. Understand the concept of degeneracy.

2. Identify the causes of degeneracy.

3. Describe the impact of degeneracy on the simplex method.

4. Recognize the practical implication of degeneracy.

5. Apply problem-solving skills.

TIE BREAKING IN THE SIMPLEX METHOD

TIE BREAKING IN THE SIMPLEX METHOD

TIE BREAKING IN THE SIMPLEX METHOD

TIE BREAKING IN THE SIMPLEX METHOD

Degenerate LP Problem Solution

Degenerate LP Problem Solution

Degenerate LP Problem Solution

Degenerate LP Problem Solution

Degenerate LP Problem Solution

Degenerate LP Problem Solution

Degenerate LP Problem Solution

Degenerate LP Problem Solution

Multiple Choice

What is degeneracy in linear programming?

• A) A situation where the objective function is not linear

• B) A situation where one or more basic variables have a value of zero

• C) A situation where the constraints are not linear

• D) A situation where the optimal solution is not unique

Multiple Choice

What is a cause of degeneracy in linear programming?

• A) Having too many constraints

• B) Having too few constraints

• C) Having a redundant constraint

• D) Having a non-linear objective function

Multiple Choice

What happens when a linear program has degeneracy?

• A) The simplex method terminates quickly

• B) The simplex method becomes more complex

• C) The solution is not unique

• D) The model has no solution

Multiple Choice

What is the impact of degeneracy on the simplex method?

• A) It slows down the algorithm

• B) It makes the algorithm more efficient

• C) It does not affect the algorithm

• D) It causes the algorithm to terminate early

Multiple Choice

What happens when there is a tie between two slack variables?

• A) Select the slack variable with the smallest value

• B) Select the slack variable with the largest value

• C) Select an arbitrary slack variable

• D) Select neither of the slack variables

Multiple Choice

What is the practical implication of degeneracy?

• A) The model has at least one redundant constraint

• B) The model has no solution
  

• C) The model has multiple solutions

• D) The model has no constraints

Multiple Choice

What happens when there is a tie between a slack variable and an artificial variable?

• A) Select the slack variable to leave the basis

• B) Select the artificial variable to leave the basis

• C) Select neither of the variables

• D) Select an arbitrary variable

Multiple Choice

What is the purpose of dividing the coefficients of slack variables in the simplex table when degeneracy is detected?

• A) To find the optimal solution

• B) To resolve degeneracy

• C) To select the entering variable

• D) To select the leaving variable

Multiple Choice

What happens when there is a cycle in the simplex method due to degeneracy?

• A) The algorithm terminates quickly

• B) The algorithm becomes more complex

• C) The algorithm repeats indefinitely without arriving at the optimal solution

• D) The algorithm does not solve any problem

Multiple Choice

What is the key step to resolve degeneracy in linear programming?

• A) Divide the coefficients of slack variables in the simplex table by their corresponding positive numbers in the key column

• B) Select an arbitrary slack variable to leave the basis

• C) Select an arbitrary basic variable to enter into the basis

• D) Repeat iterations of the simplex method until degeneracy is resolved

Multiple Choice

What is a degenerate solution in linear programming?

• • A) A solution where all decision variables are zero

• • B) A solution where at least one basic variable is zero

• • C) A solution with negative coefficients

• • D) A solution that does not satisfy all constraints

Multiple Choice

Which of the following can cause degeneracy in a linear programming problem?

• • A) Redundant constraints

• • B) Incorrect formulation

• • C) Too many variables

• • D) All of the above

Multiple Choice

How does degeneracy affect the simplex method?

• • A) It speeds up the computation

• • B) It has no effect

• • C) It can lead to cycling

• • D) It simplifies the problem

Multiple Choice

What is the practical implication of degeneracy?

• • A) The problem is unsolvable

• • B) The model has redundant constraints

• • C) The solution is always optimal

• • D) The simplex method becomes graphical

Multiple Choice

In the simplex method, if there is a tie for the entering variable, which one should you choose?

• • A) Slack variable

• • B) Surplus variable

• • C) Decision variable

• • D) Any variable arbitrarily

Multiple Choice

What happens if there is a tie between two slack variables for the leaving variable?

• What happens if there is a tie between two slack variables for the leaving variable?

• • B) The decision variable is chosen

• • C) The choice is made arbitrarily

• • D) The simplex method restarts

Multiple Choice

During the simplex method, what indicates a degenerate next iteration?

• • A) All variables have positive values

• • B) The objective function value decreases

• • C) More than one variable is eligible to leave the basis

• • D) The coefficients of the objective function become zero

Multiple Choice

What should you do if the minimum ratio test results in a tie during the simplex method?

• • A) Stop the computation

• • B) Choose the variable with the highest index

• • C) Divide the coefficients of slack variables by the corresponding positive numbers of the key column

• • D) Randomly select a row to be the key row

Multiple Choice

A company is optimizing its production mix of two products. During the simplex method, it finds that one of the products has a production level set to zero in the basic feasible solution. This is an example of:

• • A) Non-degeneracy

• • B) Degeneracy

• • C) Unbounded solution

• • D) Infeasibility

Multiple Choice

A transportation company is determining the most efficient route for shipping goods. If the simplex tableau shows a basic variable representing one route with a value of zero, this indicates:

• A) An error in calculations

• B) A need for more constraints

• C) Degeneracy

• D) An optimal solution has been found

Multiple Choice

In a resource allocation problem, if two different sets of allocations lead to the same cost, and one of the allocations is zero, this is a case of:

• A) Multiple optimal solutions

• B) Degeneracy

• C) Duality

• D) Feasible solution space

Multiple Choice

A farmer is deciding on the mix of crops to plant. If the simplex method results in one crop having zero acreage in the solution, this is an instance of

• A) Maximization problem

• B) Minimization problem

• C) Degeneracy

• D) Redundant constraint

Multiple Choice

An urban planner is designing a layout for a new park. If the simplex method shows that one of the areas of the park is allocated zero space in the solution, this could be due to:

• A) Incorrect objective function

• B) Degeneracy

• C) Lack of demand for that area

• D) Insufficient data

Multiple Choice

A logistics company uses linear programming to minimize transportation costs. They notice that one route’s shipment quantity is zero in the optimal solution. This scenario is an example of:

• A) Optimal routing

• B) Degeneracy

• C) Efficient utilization of resources

• D) Suboptimal planning

Multiple Choice

A dietitian formulates a diet plan to minimize cost while meeting nutritional requirements. If a particular food item’s recommended serving size is zero in the solution, this represents:

• A) A balanced diet

• B) A diversified diet

• C) Degeneracy

• D) An incomplete diet

Multiple Choice

In a factory, a manager is scheduling production runs for different products using linear programming. If the schedule suggests not producing a certain product (quantity zero), it is a case of:

• A) Production efficiency

• B) Product discontinuation

• C) Degeneracy

• D) Market saturation

Multiple Choice

An investment firm uses linear programming for portfolio optimization. If the solution includes a zero investment in a particular asset, this is an instance of:

• A) Risk aversion

• B) Asset diversification

• C) Degeneracy

• D) Strategic investment

Multiple Choice

A city planner is using linear programming to allocate land for different types of buildings. If the solution allocates zero land to commercial buildings, this could be due to:

• A) Zoning regulations

• B) Degeneracy

• C) Residential preference

• D) Land scarcity

Multiple Choice

A refinery is optimizing its operations to minimize costs. If the solution to the linear programming model suggests zero production for a high-demand product, this could indicate

• A) A market surplus

• B) A calculation error

• C) Degeneracy

• D) A strategic decision to cut production

Multiple Choice

An airline uses linear programming for crew scheduling. If the optimal solution assigns zero flights to a highly qualified pilot, this might be due to:

• A) The pilot’s unavailability

• B) Degeneracy

• C) A preference for less experienced pilots

• D) A system error

Multiple Choice

A manufacturing company is using linear programming to determine the optimal product mix. If the solution includes zero production for a profitable item, this could be an instance of:

• A) Product discontinuation

• B) Degeneracy

• C) Market analysis

• D) Cost-cutting measures

Multiple Choice

A telecommunications company is optimizing network flow. If the linear programming model suggests zero data flow through a major node, this could indicate:

• A) Network redundancy

• B) Degeneracy

• C) A technical fault

• D) An upgrade in progress

Multiple Choice

A hospital is optimizing the allocation of staff to various departments. If the linear programming model results in zero allocation to a critical department, this might be a case of:

• A) Staff shortage

• B) Degeneracy

• C) Department closure

• D) Administrative oversight

Multiple Choice

A telecommunications company is optimizing network flow. If the linear programming model suggests zero data flow through a major node, this could indicate:

• A) Network redundancy

• B) Degeneracy

• C) A technical fault

• D) An upgrade