Part A

1. Explain briefly on degeneracy in the simplex method

Degeneracy in the simplex method occurs when a basic variable in the solution takes a
value of zero. Even though the simplex table gives a valid basic feasible solution, the
method does not improve the objective function at that iteration because the entering
variable replaces a zero-valued basic variable. This situation typically appears when
multiple constraints intersect at the same corner point of the feasible region.

Degeneracy is significant because it may slow down the progress of the simplex method.
In some cases, it can cause the algorithm to cycle, meaning it may return to a previously
visited solution repeatedly. Anti-cycling rules such as Bland’s rule are used to avoid this
issue and ensure convergence.

2. Define an unbounded solution in the simplex method.

An unbounded solution occurs when the objective function can increase or decrease
infinitely without violating any constraints. This happens when no limiting constraint
exists in the direction of improvement, allowing the simplex method to move indefinitely
along that direction.

In practice, unboundedness indicates that the mathematical model is incomplete. Some

essential constraint is missing or incorrectly formulated. Since there is no finite optimum,
the simplex method terminates and reports that the solution is unbounded.

3. Differentiate between unbounded solution and infeasible solution in simplex.

An unbounded solution means that the feasible region exists and extends infinitely in a
direction that improves the objective function. Thus, the objective can grow without
limit, and no finite optimum exists.

An infeasible solution means no point satisfies all constraints simultaneously. The

feasible region does not exist at all. This situation arises from conflicting or contradictory
constraints, making the model unsolvable.

4. Define one consequence of degeneracy in simplex solutions.

One major consequence of degeneracy is cycling, where the simplex method keeps
repeating the same set of basic feasible solutions without progressing toward the
optimum. This wastes computational effort and may prevent finding the optimal solution.

Another consequence is that degeneracy slows down convergence. Because the objective
function does not improve in some iterations, the simplex method may require more steps
to reach the optimum, increasing the time needed for computation.

5. Explain briefly on alternative optima in the simplex method.

Alternative optima occur when more than one solution yields the same optimal value of
the objective function. This happens when a non-basic variable in the optimal tableau has
a reduced cost of zero, indicating that introducing it into the basis does not change the
objective value.

Such situations arise when the feasible region has a flat boundary along which many
points give the same optimum. While any of these solutions is mathematically optimal,
managers may choose one based on practical factors like cost, resource utilization, or
ease of implementation.

6. Define the dual of a Linear Programming Problem (LPP).

The dual of an LPP is another linear programming model derived from the original
(primal) problem. Each constraint in the primal becomes a variable in the dual, and the
primal’s objective (maximize/minimize) becomes the opposite type in the dual.

The dual problem provides valuable economic interpretation, resource valuation, and a
different perspective on feasibility and optimality. The primal and dual solutions are
closely linked, and studying the dual often simplifies analysis.

7. List out one advantage of the dual simplex method over the simplex method.

One advantage of the dual simplex method is that it can start with an optimal but
infeasible solution and work toward feasibility. This is useful in situations where small
changes in constraints violate feasibility.

Because of this property, the dual simplex method is especially efficient for problems that
undergo frequent updates, such as operational planning and real-time scheduling. It
avoids restarting the simplex method from the beginning.
8. Explain the feasibility condition in the dual simplex method.

The dual simplex method requires that all reduced costs satisfy the optimality condition.
However, the current solution may be infeasible because one or more basic variables are
negative.

As iterations progress, the method selects leaving variables that help restore feasibility
while preserving optimality. Once all basic variables become non-negative, the solution
becomes both feasible and optimal.

9. Explain the significance of dual variables in LPP.

Dual variables represent the “shadow price” or marginal value of resources in the primal
problem. They show how much the objective function improves if the availability of a
resource increases by one unit.

These values help decision-makers identify which resources are scarce or critical.
Resources with positive dual values are valuable and limiting, while resources with zero
dual values are surplus and do not influence the optimal solution.

10. List any two properties of primal–dual relationships.

One important property is weak duality, which states that the dual objective value is
always a bound for the primal objective value. This ensures that feasible solutions to
either problem cannot violate the optimality of the other.

Another key property is strong duality, which states that if both the primal and dual have
feasible solutions, their optimal objective values are equal. This guarantees consistency
and allows checking optimality using the dual.

11. Explain the economic interpretation of duality in LPP.

Duality provides an economic viewpoint by assigning value to resources and constraints.

It helps interpret constraints as limited resources and variables as activities requiring
those resources.

Through duality, managers can evaluate the profitability or cost-effectiveness of

increasing resource availability. It links mathematical optimization to real-world
decision-making by quantifying resource scarcity and efficiency.
12. Define the value of a dual variable indicate in economics.

In economics, the value of a dual variable indicates how much the objective function
changes when the corresponding resource increases by one unit. It represents the
marginal worth of that resource.

A positive value means the resource is scarce and increasing it will benefit the objective.
A zero value means the resource is plentiful, and increasing it provides no improvement.

13. State the economic meaning of the primal constraints in duality.

Primal constraints represent the limits on available resources such as labor, materials, or
budget. They restrict how many units of different activities can be performed.

Economically, these constraints show how resources are allocated among competing
activities. They indicate which resources are scarce and how they shape the optimal
production or planning strategy.

14. Explain duality in LPP.

Duality is a concept that associates every linear programming problem with another
related problem called the dual. While the primal focuses on maximizing or minimizing a
function, the dual evaluates resource values and constraint efficiency.

Studying the dual provides insights that the primal alone cannot reveal, such as resource
scarcity and economic trade-offs. Duality strengthens the understanding of optimality and
supports sensitivity analysis.

15. List any two limitations of duality.

One limitation is that duality applies only to linear problems. Real-world problems that
involve nonlinear relationships cannot directly use duality principles.

Another limitation is that interpreting dual variables requires skill. If the primal model is
not formulated correctly, the dual interpretation may be misleading or economically
meaningless.
16. Explain sensitivity analysis.

Sensitivity analysis studies how changes in coefficients, constraints, or resource limits

affect the optimal solution. It helps determine how stable or robust the current solution is
when conditions vary.

This analysis is essential for decision-making because real-world environments are

uncertain. By understanding how much change the system can tolerate, managers can
plan more effectively and reduce risk.

17. Explain the term “shadow price” indicate in sensitivity analysis.

Shadow price represents the improvement in the objective function when a resource limit
increases by one unit. It shows the economic value of a tight or scarce resource.

If a resource is fully utilized and scarce, its shadow price will be positive. If the resource
is not fully used, the shadow price will be zero because additional availability does not
improve the objective.

18. State two key purposes of performing sensitivity analysis.

One key purpose is to check how stable the optimal solution is when input parameters
change. This helps managers understand whether the solution remains reliable under
different conditions.

Another purpose is to identify critical parameters that significantly affect the outcome.
This helps prioritize which resources or coefficients need the most attention in planning.

19. List two parameters commonly tested during sensitivity analysis in linear
programming problems.

One commonly tested parameter is the objective function coefficient, which affects the
contribution of each activity to profit or cost. Changing this helps evaluate the robustness
of the optimal solution.

Another parameter is the right-hand side of constraints, representing resource availability.

Adjusting these values helps assess how much benefit comes from adding or removing
resources.
20. Give one real-world example where sensitivity analysis is used to support
managerial decisions.

A common example is manufacturing planning, where sensitivity analysis helps

managers study how profit changes if the supply of raw materials varies. By examining
shadow prices, they can decide whether buying additional resources is worthwhile.

It is also used in scheduling and budgeting, where changes in labor hours, machine time,
or demand conditions are evaluated. This allows managers to adjust plans efficiently and
make informed decisions.

Part B

21. Explain briefly on special cases in the simplex method

Special cases in the simplex method are situations where the normal path of finding an
optimal solution is disrupted by unusual behaviour in the model. These cases highlight
structural issues in the linear programming formulation. They are important because they
indicate that a problem may not behave in a standard way and may need special attention
or corrections. Some of the well-known special cases include unbounded solutions,
infeasible solutions, degeneracy, and alternate optimal solutions.

These special cases occur because the feasible region or the mathematical relationships
within the constraints may have special characteristics. For example, missing limits on
variables can make the objective function go to infinity, resulting in an unbounded
solution. Conflicting constraints can make it impossible to find any solution that satisfies
all conditions, leading to an infeasible situation.

Understanding these cases helps analysts diagnose issues in the model. It also helps
ensure that solutions are meaningful and reflect real-world possibilities. By recognizing
special cases early, one can take corrective action—such as refining constraints, revising
assumptions, or using alternate algorithmic rules to ensure valid and stable results.

22. Define the following special cases in the simplex method: unbounded solution,
infeasible solution, degeneracy, alternate optima. Provide an example of each.

An unbounded solution occurs when the objective function can increase or decrease
without limit. This happens because the model lacks a constraint that restricts movement
in the improving direction. For example, in a maximization problem with the constraint x
– y ≥ 0 and no limits on x, the objective maximize z = x + y can become infinitely large as
x increases. The simplex method detects this when a column chosen to enter the basis has
no positive pivot elements.

An infeasible solution occurs when no set of variable values satisfies all constraints
simultaneously. For example, the constraints x + y ≤ 3 and x + y ≥ 10 cannot both be true
at once. The simplex method detects infeasibility during Phase I, when artificial variables
cannot be driven to zero. Infeasibility indicates flawed or inconsistent modelling
assumptions.

Degeneracy occurs when one or more basic variables take a value of zero. For example,
in a constraint such as x + y ≤ 5 and x ≤ 0, the feasible region touches a corner where the
solution has zero basic value. Degeneracy can cause the simplex method to stall or cycle
without progress.​
Alternate optima exist when more than one feasible solution gives the same optimal
objective value. For example, maximizing z = x + y subject to x + y = 10 and x, y ≥ 0
results in an entire line segment of optimal solutions. In simplex tables, alternate optima
appear when a nonbasic variable has zero reduced cost at optimality.

23. Discuss the special case of infeasibility in the simplex method.

Infeasibility arises when the constraints in the linear programming problem contradict
each other, making it impossible to find even a single feasible solution. This is common
when the model includes strict conditions or unrealistic limitations. In real-world terms, it
means the available resources or rules do not allow any workable plan.

The simplex method detects infeasibility during the Phase I procedure, where artificial
variables are added to force an initial feasible solution. If these artificial variables cannot
be eliminated (returned to zero), the method concludes that the original constraints do not
form a feasible region. Thus, infeasibility is recognized before attempting to optimize the
objective function.

The implications of infeasibility are significant because it suggests that the real-world
assumptions behind the model may be incorrect. For example, a production plan
demanding more raw materials than available will always be infeasible. Detecting
infeasibility helps managers revisit constraints, adjust expectations, or modify the
problem formulation to create a workable realistic model.
24. Explain the concept of unbounded solutions in linear programming. Illustrate
with an example.

An unbounded solution occurs when the objective function grows indefinitely without
violating any constraints. This means the feasible region extends infinitely in a direction
where improvement continues. In maximization, it implies profit can grow without limit;
in minimization, cost can fall endlessly.

During the simplex method, unboundedness is detected when a column with a positive
reduced cost (in a maximization problem) has no positive pivot entries. This means there
is no constraint blocking movement in that direction. As a result, the method correctly
concludes that the problem has no finite optimal solution.

For example, consider maximizing z = 5x + 3y subject to x − y ≥ 0 and x, y ≥ 0. Without

an upper limit on x, the objective increases without bound as x increases. Such a situation
indicates missing constraints—something that is unrealistic in most real settings. In
practice, unboundedness means the model needs correction because real-world systems
always have limits.

25. Define degeneracy in the simplex method. Analyze its effects and strategies to
overcome it.

Degeneracy happens when a basic variable in the simplex method takes the value zero.
This means the current corner point is not unique, often because multiple constraints
intersect at that point. Although the solution is feasible, it provides no improvement in the
objective function, causing a stall.

This stall can lead to cycling, where the algorithm keeps visiting the same solutions
repeatedly without progress. Cycling wastes computation time and may prevent reaching
the optimal solution. Although rare, it is a serious issue in large or complex models.

To overcome degeneracy, special rules are used. Bland’s rule, for example, ensures a
consistent and deterministic choice of entering and leaving variables, preventing cycling.
Other strategies include perturbation methods that slightly adjust the coefficients to avoid
zero basic variables. These methods keep the algorithm moving steadily toward
optimality.
26. Discuss the concept of duality in linear programming.

Duality is a powerful concept in linear programming that associates every LPP (the
primal) with another related LPP called the dual. While the primal focuses on optimizing
decision variables, the dual focuses on valuing resources. The strength of duality lies in
the relationship between these two perspectives.

The dual is constructed by converting each primal constraint into a variable and each
primal variable into a constraint. The direction of optimization (maximization or
minimization) also reverses. These dual formulations reveal deeper insights into the
structure and economics of the problem.

Duality is significant because it helps verify optimality. If the optimal values of the
primal and dual match, both solutions are correct. Duality also helps interpret resource
scarcity, determine shadow prices, and perform sensitivity analysis. Thus, it forms a
foundational pillar in optimization theory.

27. Examine the primal–dual relationships in linear programming. Discuss

complementary slackness.

Primal–dual relationships link the solutions of the primal and dual problems. If both
problems have feasible solutions, their optimal objective values are equal. This link helps
in verifying correctness and understanding the economics behind constraints and
resources.

A key concept connecting the two is complementary slackness, which states that for
each primal constraint, either the constraint is tight (binding) or the corresponding dual
variable is zero. Similarly, for each dual constraint, either it is fully used or the
corresponding primal variable is zero. This rule helps determine which resources are fully
utilized and which decision variables actively contribute to the optimal solution.

Complementary slackness provides a systematic way of moving from a primal solution to

a dual one and vice versa. It also offers insight into which resources are valuable, which
constraints are active, and how the optimal solution structure behaves. Understanding it
helps both analysts and managers interpret solutions meaningfully.
28. Explain the economic meaning of dual variables (shadow prices).

Dual variables represent the economic value of resources. Specifically, they show how
much the objective function will improve if one unit of a particular resource is added.
These values are also known as shadow prices because they reflect the hidden economic
worth of constraints.

For example, if increasing machine hours by one unit increases profit by ₹50, then the
dual variable associated with machine hours is 50. This means the resource is scarce and
valuable, and the business may consider investing to increase its availability. If the dual
value is zero, the resource is abundant and adding more provides no benefit.

Shadow prices help managers prioritize investments, identify bottlenecks, and understand
which resources are most critical. They turn abstract mathematical results into practical
economic insights, improving strategic decision-making.

29. Evaluate the role of duality in sensitivity analysis.

Duality plays an essential role in sensitivity analysis by revealing how changes in

resource limits and coefficients affect the optimal solution. The dual variables directly
indicate the marginal value of resources, making it easy to assess the effect of increasing
or decreasing resource availability.

Through duality, one can determine the allowable range within which resource values or
objective function coefficients may change without altering the optimal basis. This helps
maintain stability in long-term planning. Decision-makers can test various scenarios and
predict the impact quickly.

In summary, duality simplifies sensitivity analysis and turns complex mathematical

questions into easily interpretable results. Managers can make informed decisions about
resource allocation, pricing, budgeting, and planning using these insights.

30. Discuss how duality helps managers in resource allocation. Provide an example.

Duality helps managers allocate resources by identifying which resources are most
valuable and how changes in resource availability affect profits or costs. The shadow
prices provided by dual variables show which constraints are binding and which
resources are underutilized.
For example, consider a factory producing chairs and tables with limited wood and labor.
If the dual value for labor is high, it indicates that labor is a bottleneck. Managers may
hire additional workers or improve training. If the dual value for wood is zero, it means
wood is plentiful and does not limit production.

By analyzing the dual solution, managers can decide where to invest, what to expand, and
which resources to prioritize. This leads to efficient planning, better budgeting, and
improved overall productivity.