Select a result to preview

#article #full

Handling Multiple, Unbounded, and Infeasible Solutions in Linear Programming • SLM (Self Learning Material) for MBA

Source: slm.mba

#LinearProgramming #Optimization #InfeasibleSolutions #UnboundedSolutions

Skip to content

Linear programming doesn’t always give us neat, single answers wrapped in a bow. Sometimes we encounter situations where problems have multiple optimal solutions, solutions that stretch to infinity, or worse yet, no solutions at all. These special cases – multiple, unbounded, and infeasible solutions – might seem like mathematical oddities, but they’re actually common in real-world business scenarios. Understanding these cases is crucial for anyone working with optimization problems, as they can reveal important insights about your business constraints and objectives.

Table of Contents

When one solution isn’t enough: Multiple optimal solutions

Imagine you’re running a bakery and trying to maximize profit from selling cookies and cakes. After setting up your linear programming model, you discover something interesting – there isn’t just one way to achieve maximum profit, but infinitely many ways! This happens when we encounter multiple optimal solutions.

Multiple optimal solutions occur when the objective function line is parallel to one of the constraint lines that forms the boundary of the feasible region. Think of it like this: instead of the objective function touching the feasible region at just one corner point, it lies flat against an entire edge of the region. Every point along this edge gives the same optimal value.

Recognizing multiple solutions graphically

When you’re solving a linear programming problem graphically, multiple solutions reveal themselves quite clearly. As you move the objective function line toward the optimal position, you’ll notice it becomes parallel to one of the constraint boundaries. Instead of touching at a single point, the objective function line coincides with an entire edge of the feasible region.

For example, consider a company producing two products with the objective of maximizing profit. If the profit per unit for both products creates an objective function that’s parallel to a binding constraint, then any combination of products along that constraint line will yield the same maximum profit.

Real-world implications of multiple solutions

Multiple solutions aren’t just mathematical curiosities – they offer valuable flexibility in decision-making. When you have multiple optimal solutions, you can choose the one that best fits other considerations not captured in your model. Maybe one solution requires less labor overtime, or another solution uses more environmentally friendly processes. This flexibility can be a significant advantage in practical business applications.

When solutions reach for infinity: Unbounded problems

Sometimes linear programming problems seem to suggest that you can achieve infinite profit or minimize costs to negative infinity. These are called unbounded solutions, and while they might sound like a business owner’s dream, they actually indicate a problem with your model formulation.

An unbounded solution occurs when the feasible region extends infinitely in the direction that improves the objective function. Graphically, this means there’s no constraint preventing you from moving as far as you want in the direction of improvement.

Understanding unbounded solutions through examples

Consider a manufacturing problem where you want to maximize profit from two products. If your constraints don’t properly limit production capacity, raw materials, or market demand, you might end up with an unbounded solution. The mathematical model would suggest you can produce infinite quantities and earn infinite profit – clearly unrealistic!

For instance, if a company’s linear programming model for production planning doesn’t include capacity constraints or market demand limits, the solution might suggest producing unlimited quantities of the most profitable product. This unbounded result signals that important real-world limitations haven’t been captured in the model.

Dealing with unbounded solutions in practice

When you encounter an unbounded solution, it’s time to revisit your problem formulation. Ask yourself: What constraints am I missing? In the real world, there are always limitations – production capacity, available materials, market size, labor hours, or budget restrictions. An unbounded solution is your model’s way of telling you that these realistic constraints need to be included.

The key is to identify and add the missing constraints that reflect real-world limitations. Once you include these forgotten constraints, your unbounded problem typically becomes a well-defined optimization problem with a finite optimal solution.

When no solution exists: Infeasible problems

Perhaps the most frustrating situation in linear programming is discovering that your problem has no feasible solution at all. This happens when the constraints are so restrictive or contradictory that no point can satisfy all of them simultaneously. We call this an infeasible problem.

Infeasibility occurs when the intersection of all constraint regions is empty – there’s literally no point that satisfies every constraint. Graphically, you’ll see constraint lines that don’t overlap in any common area, leaving no feasible region where a solution could exist.

Common causes of infeasibility

Infeasible problems often arise from conflicting constraints that contradict each other. For example, imagine a production scenario where one constraint requires producing at least 100 units of a product, while another constraint limits production to no more than 50 units of the same product. These constraints directly contradict each other, making the problem infeasible.

Another common cause is overly restrictive constraints that, while not directly contradictory, combine to eliminate all possible solutions. This might happen when quality requirements, budget limitations, and production capacities are all set so strictly that no production plan can satisfy them all.

Real-world example of infeasibility

Consider a logistics company trying to optimize delivery routes with the following constraints: all deliveries must be completed within 4 hours, each truck can carry a maximum of 10 packages, fuel costs must not exceed $50, and all 100 packages must be delivered using only 2 trucks. These constraints might be infeasible because 2 trucks carrying 10 packages each can only handle 20 packages, not 100.

Resolving infeasible problems

When faced with infeasibility, you have several options. First, examine your constraints carefully to identify conflicts or overly restrictive conditions. You might need to relax some constraints, perhaps accepting slightly lower quality standards or increasing budget limits. Alternatively, you might need to reconsider your objectives or add more resources to make the problem feasible.

Sometimes infeasibility reveals important insights about your business situation. It might highlight unrealistic expectations, insufficient resources, or the need for operational changes. In this sense, discovering infeasibility can be just as valuable as finding an optimal solution.

Practical tips for handling special cases

When working with linear programming problems, always be prepared for these special cases. Start by carefully examining your problem formulation to ensure all relevant constraints are included and realistic. If you encounter multiple solutions, consider additional criteria to help choose among the alternatives. When facing unbounded solutions, look for missing constraints that reflect real-world limitations. For infeasible problems, systematically examine constraints to identify conflicts or unrealistic restrictions.

Remember that these special cases often provide valuable insights into your business situation. Multiple solutions offer flexibility, unbounded solutions reveal missing constraints, and infeasible problems highlight unrealistic expectations or insufficient resources. Each case teaches us something important about the problem we’re trying to solve.

What do you think? Have you encountered situations in your studies or work where constraints seemed impossible to satisfy simultaneously? How might understanding these special cases help you better formulate and solve real-world optimization problems?

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

PDF

Comments

Leave a Reply

Operations Research

1 Operations Research-An Overview

  1. Introduction
  2. History of O.R.
  3. Approach, Techniques and Tools
  4. Phases and Processes of O.R. Study
  5. Typical Applications of O.R.
  6. Limitations of Operations Research
  7. Models in Operations Research
  8. O.R. in the Real World

2 Linear Programming- Formulation and Graphical Method

  1. Introduction
  2. General Formulation of Linear Programming Problem
  3. Optimisation Models
  4. Basics of Graphic Method
  5. Important Steps to Draw the Graph
  6. Multiple, Unbounded Solution, and Infeasible Problems
  7. Solving Linear Programming Graphically Using Computer
  8. Application of Linear Programming in Business and Industry

3 Linear Programming-Simplex Method

  1. Principle of Simplex Method
  2. Computational Aspect of Simplex Method
  3. Simplex Method with Several Decision Variables
  4. Two Phase and M-method
  5. Multiple Solution, Unbounded Solution and Infeasible Problem
  6. Sensitivity Analysis
  7. Dual Linear Programming Problem

4 Transportation Problem

  1. Basic Feasible Solution of a Transportation Problem
  2. Modified Distribution Method
  3. Stepping Stone Method
  4. Unbalanced Transportation Problem
  5. Degenerate Transportation Problem
  6. Transhipment Problem
  7. Maximisation in a Transportation Problem

5 Assignment Problem

  1. Solution of the Assignment Problem
  2. Unbalanced Assignment Problem
  3. Problem with Some Infeasible Assignments
  4. Maximization in an Assignment Problem
  5. Crew Assignment Problem

6 Application of Excel Solver to Solve LPP

  1. Building Excel model for solving LPP: An Illustrative Example
  2. Sensitivity Analysis in Excel Solver

7 Goal Programming

  1. Concepts of Goal Programming
  2. Goal Programming Model Formulation
  3. Graphical Method of Goal Programming
  4. The Simplex Method of Goal Programming
  5. Using Excel Solver to Solve Goal Programming Models
  6. Application Areas of Goal Programming

8 Integer Programming

  1. Introduction
  2. Some Integer Programming Formulation Techniques
  3. Binary Representation of General Integer Variables
  4. Unimodularity
  5. Cutting Plane Method
  6. Branch and Bound Method
  7. Solver Solution

9 Dynamic Programming

  1. Introduction
  2. Dynamic Programming Methodology: An Example
  3. Definitions and Notations
  4. Dynamic Programming Applications

10 Non-Linear Programming

  1. Introduction
  2. Solution of a Non-Linear Programming Problem
  3. Convex and Concave Functions
  4. Kuhn-Tucker Conditions for Constrained Optimisation
  5. Quadratic Programming
  6. Separable Programming
  7. NLP Models with Solver

11 Introduction to game theory and its Applications

  1. Introduction
  2. Definitions and Explanation of Some Important Terms
  3. Saddle Points
  4. Dominance
  5. Mixed Strategies: Games Without Saddle Points
  6. 2xn Games
  7. Exploiting an Opponent’s Mistakes

12 Monte Carlo Simulation

  1. Reasons for using simulation
  2. Monte Carlo simulation
  3. Limitations of simulation
  4. Steps in the simulation process
  5. Some practical applications of simulation
  6. Two typical examples of hand-computed simulation
  7. Computer simulation

13 Queueing Models

  1. Characteristics of a Queueing Model
  2. Notations and Symbols
  3. Statistical Methods in Queueing
  4. The M/M/1 System
  5. The M/M/C System
  6. The M/Ek/1 System
  7. Decision Problems in Queueing
  8. Solved Problems