Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Unit 8: Linear Programming

Introduction and Terminology

Linear Programming (LP) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.

Common terminology used:

  • Decision Variables: The variables whose values we seek to determine (e.g., \( x \) and \( y \)).
  • Constraints: The linear inequalities or equations representing resource limitations or conditions.
  • Objective Function: The linear function \( Z \) that needs to be maximized or minimized (e.g., \( Z = 5x + 3y \)).
  • Non-negative Constraints: The condition that decision variables cannot be negative (e.g., \( x \ge 0, y \ge 0 \)).
  • Feasible Region: The common region determined by all the constraints, including the non-negative constraints.
  • Optimal Solution: Any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function.
x y Feasible Region Optimal Point

Mathematical Formulation

To formulate a real-life situation mathematically into a linear programming problem:

  1. Identify the decision variables and denote them as \( x \), \( y \), etc.
  2. Identify the objective function and express it mathematically as a linear function. State whether it is to be maximized or minimized.
  3. Identify the constraints or restrictions from the given conditions and express them as linear inequalities.
  4. Add the non-negative constraints.

Types of Linear Programming Problems

Common application types:

  • Manufacturing Problems: To determine the number of units of different products which should be produced to maximize profit.
  • Diet Problems: To determine the minimal cost of a diet which contains a certain minimum amount of each nutrient.
  • Transportation Problems: To determine a transportation schedule that minimizes the total cost of transporting a commodity from various sources to various destinations.

Graphical Solution Method

The Graphical Method is used when there are only two decision variables.

  1. Plot each constraint line on a graph.
  2. Identify the feasible region satisfying all inequalities simultaneously.
  3. Determine the coordinates of the corner points of the feasible region.
  4. Evaluate the objective function at each corner point to find the maximum or minimum value.

Competency-Based Questions

Q1. A furniture manufacturer has 200 units of wood and 150 hours of labor labor available per week. He produces tables and chairs. Each table requires 4 units of wood and 2 hours of labor, yielding a profit of ₹ 800. Each chair requires 2 units of wood and 3 hours of labor, yielding a profit of ₹ 500. Formulate this LP problem mathematically.

Q2. Identify the objective function \( Z \) from Q1. Is it a maximization or minimization function?

Q3. Graphically solve the formulated LP problem from Q1 to determine how many tables and chairs should be produced to maximize total profit. State the corner points and the optimal profit.

Q4. A nutritionist is designing a diet plan for an athlete using two food sources, A and B. Source A costs ₹ 30/kg and Source B costs ₹ 40/kg. Discuss what happens to the optimal solution if the price of Food Source A increases significantly, causing the objective function slope to change relative to the constraint slopes.

Answers

Ans 1. Let \( x \) be tables and \( y \) be chairs. Maximize \( Z = 800x + 500y \). Constraints: \( 4x + 2y \le 200 \) (wood), \( 2x + 3y \le 150 \) (labor), \( x,y \ge 0 \).

Ans 2. The objective function is \( Z = 800x + 500y \). It is a maximization function (maximizing profit).

Ans 3. Feasible region corners: \( (0,0), (50,0), (0,50), (37.5, 25) \). Evaluating \( Z \) at (37.5, 25) gives \( 800(37.5) + 500(25) = 30000 + 12500 = 42500 \). Maximum profit is ₹ 42,500 by producing 37.5 tables and 25 chairs (or 37 and 25 practically for integer values).

Ans 4. If the cost of Food Source A increases significantly, the slope of the objective function (cost line) steepens. The optimal solution might shift along the boundaries of the feasible region towards a vertex that relies less on Food Source A and more on Food Source B.