Chapter 12 Linear Programming (Class 12 - Maths NCERT Concept Notes)
Welcome to Chapter 12: Linear Programming! This chapter introduces Linear Programming Problems (LPP), a powerful mathematical optimization technique used to achieve the best outcome, such as maximizing profit or minimizing cost, within specific limitations. It is a cornerstone of operations research, applied widely in business, economics, and engineering.
An LPP consists of three key parts: the Objective Function ($Z = ax + by$), Decision Variables ($x$ and $y$), and Constraints. These constraints are linear inequalities representing resource limits like time, raw materials, or budget. We also include non-negativity constraints ($x \ge 0, y \ge 0$) since physical quantities cannot be negative in real-world scenarios.
For problems with two variables, we use the graphical method. By plotting constraints on a coordinate plane, we identify the Feasible Region—the common area where all conditions are met simultaneously. This region is always a convex polygon. According to the Corner Point Theorem, the optimal solution must occur at one of the vertices (corner points) of this region.
To enhance the understanding of these concepts, this page includes images for visualisation, flowcharts, mindmaps, and practical examples of manufacturing, diet, and transportation problems. This page is prepared by learningspot.co to provide a structured and comprehensive learning experience for every student.
| Content On This Page | ||
|---|---|---|
| Introduction to Linear Programming | Formation of an L.P.P in Two Variables x and y | Graphical Method of Solving an L.P.P |
Introduction to Linear Programming
Linear Programming (L.P.) is a mathematical modeling technique used to achieve the best outcome, such as maximum profit or lowest cost, in a mathematical model whose requirements are represented by linear relationships.
In various fields such as industry, military, and personal finance, the primary goal is to optimize resources. This involves maximizing benefits like profits or damage to an enemy, while minimizing liabilities like costs, losses, or tax burdens.
The term "Linear" implies that all the mathematical relationships in the problem are of the first degree (the variables have a power of 1). The word "Programming" refers to the process of planning or choosing the best alternative from available options, rather than computer coding.
This subject was significantly developed by the American economist George Dantzig, who introduced the Simplex Method for solving optimization problems.
Fundamental Components of an L.P.P.
To define a Linear Programming Problem, certain mathematical elements are required:
1. Decision Variables
These are the unknown quantities that need to be determined to solve the problem. In two-dimensional problems, these are usually represented as $x$ and $y$.
2. Objective Function
This is a linear function that we aim to maximize (e.g., profit) or minimize (e.g., cost). It is typically denoted by $Z$.
$Z = ax + by$
[Function to be optimized]
3. Constraints
These are the limitations or restrictions on the resources, expressed as linear inequalities or equations.
$a_1x + b_1y \leq k_1$
(Example: Availability of Raw Materials)
$a_2x + b_2y \geq k_2$
(Example: Minimum Production Target)
4. Non-negative Restrictions
In real-world applications, the values of decision variables cannot be negative. For example, a factory cannot produce a negative number of chairs.
$x \geq 0, y \geq 0$
Classical Linear Programming Problems (L.P.P.)
Linear programming is widely applied in various scenarios. Three of the most common types are detailed below:
(i) Manufacturing Problems
These problems involve a firm deciding the production mix of different products. Each product requires fixed resources like manpower, machine hours, and warehouse space.
The goal is to determine the quantity of each product to produce to maximize profit while staying within the limits of available resources.
(ii) Diet Problems
These involve determining the quantities of different types of foods to include in a diet so that it meets minimum nutritional requirements (vitamins, minerals, etc.) while minimizing the total cost.
Consider a simple data table for a diet problem involving two food items:
| Nutrient | Food $x$ (units/kg) | Food $y$ (units/kg) | Min. Requirement |
|---|---|---|---|
| Vitamin A | 2 | 1 | 8 units |
| Vitamin C | 1 | 2 | 10 units |
| Cost per kg | $\textsf{₹} 50$ | $\textsf{₹} 70$ | Minimize $Z$ |
From the table above, the cost function would be:
$Z = 50x + 70y$
(iii) Transportation Problems
These deal with finding the most cost-effective way to transport products from several sources (like factories or godowns) to various destinations (like retail shops or markets).
The objective is to minimize total transportation costs while ensuring that the supply from each factory is utilized and the demand of each market is satisfied.
Key Definitions in Linear Programming
To formulate and solve a problem using Linear Programming, it is essential to understand the fundamental mathematical components that constitute the model. These components translate physical limitations and business goals into a mathematical framework.
1. Decision Variables
The first step in any L.P.P. is to identify the Decision Variables. These represent the quantities that the decision-maker can control and wants to determine. For example, in a manufacturing unit, the decision variables could be the number of units of "Product A" and "Product B" to be produced.
In a standard two-variable L.P.P., these are denoted as $x$ and $y$. In a more general case involving $n$ variables, they are denoted as $x_1, x_2, \dots, x_n$.
2. Objective Function
The Objective Function is a linear mathematical expression that represents the goal of the problem. This goal is either to maximize a certain value (like Total Profit, Revenue, or Efficiency) or to minimize a certain value (like Total Cost, Time, or Waste).
If $c_1, c_2, \dots, c_n$ are the constants representing the cost or profit per unit of the respective variables, the objective function $Z$ is expressed as:
$Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$
In the context of two variables $x$ and $y$, the objective function is simplified as:
$Z = ax + by$
[To be optimized]
It is important to note that the objective function must be linear, meaning all variables are raised to the power of 1 and are not multiplied by each other.
3. Constraints
In real-world scenarios, we cannot produce infinite goods or spend infinite money. There are always limitations. These limitations are called Constraints. Constraints are expressed as linear inequalities or, occasionally, linear equations.
Common types of constraints include:
(a) Resource Constraints (Upper Limits)
When there is a maximum limit on resources like raw materials, labor hours, or budget, we use the $\leq$ (less than or equal to) sign.
$a_1x + b_1y \leq k_1$
[Available budget or raw material]
(b) Requirement Constraints (Lower Limits)
When there is a minimum requirement to be met, such as minimum nutritional value in a diet or a minimum production target, we use the $\geq$ (greater than or equal to) sign.
$a_2x + b_2y \geq k_2$
[Minimum requirement]
(c) Specific Condition Constraints
If a resource must be used exactly to its full capacity, we use the $=$ (equal to) sign.
$a_3x + b_3y = k_3$
[Exact usage constraint]
4. Non-negative Restrictions
This is a critical set of constraints in any practical L.P.P. Since decision variables often represent physical quantities (like number of machines, kilograms of food, or number of workers), they cannot be negative.
Mathematically, for a two-variable problem, this is written as:
$x \geq 0, y \geq 0$
The significance of non-negative restrictions is that they limit the Feasible Region to the First Quadrant of the Cartesian plane. Any solution that falls in the second, third, or fourth quadrant is physically impossible and is therefore ignored.
5. Optimal Solution
A Feasible Solution is any set of values for the variables $x$ and $y$ that satisfies all the given constraints and the non-negative restrictions. However, the Optimal Solution is that specific feasible solution which provides the best possible value (maximum or minimum) for the Objective Function $Z$.
In a linear programming problem, if an optimal solution exists, it will always be found at one of the vertices (corner points) of the feasible region. This principle is what allows us to solve L.P.P. using the graphical method.
Feasible Region and Optimal Solution
Once the constraints of a Linear Programming Problem are plotted on a graph, we identify the area that satisfies all the conditions simultaneously. This geometric space is the foundation for finding the solution to the problem.
The Feasible Region
The Feasible Region (or solution space) is the set of all points $(x, y)$ that satisfy all the given constraints, including the non-negative restrictions $x \geq 0$ and $y \geq 0$. This region represents the collection of all possible choices available to the decision-maker.
Mathematically, it is the intersection of all the half-planes defined by the linear inequalities of the L.P.P. If a point $(x, y)$ lies within or on the boundary of this region, it is called a Feasible Solution. Any point outside this region is termed an Infeasible Solution, as it violates at least one constraint.
Characteristics of the Feasible Region
1. Convexity: The feasible region of any L.P.P. is always a Convex Set. Geometrically, a set is convex if, for any two points $P_1$ and $P_2$ belonging to the set, every point on the line segment joining $P_1$ and $P_2$ also lies within the set.
If $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$ are in the feasible region, then the point $P$ defined by the following expression is also in the region for any $0 \leq \lambda \leq 1$:
$P = \lambda P_1 + (1 - \lambda)P_2$
[Convex Combination Formula]
2. Bounded vs. Unbounded: A feasible region is said to be Bounded if it can be enclosed within a circle of finite radius. In such cases, the objective function $Z$ will always have both a maximum and a minimum value. If the region extends infinitely in any direction, it is called Unbounded. In an unbounded region, a maximum or minimum value for $Z$ may or may not exist.
Optimal Solution
The Optimal Solution is a feasible solution that results in the best possible value of the objective function $Z$. Depending on the problem, "best" means either the maximum value (e.g., for profit) or the minimum value (e.g., for cost).
An L.P.P. can have different types of optimal solutions:
• Unique Optimal Solution: Only one point in the feasible region gives the maximum/minimum value of $Z$.
• Multiple (Infinite) Optimal Solutions: If two corner points produce the same optimal value of $Z$, then every point on the line segment connecting these two corner points is also an optimal solution.
• No Optimal Solution: This occurs if the feasible region is empty (no points satisfy all constraints) or if the objective function can be increased/decreased infinitely in an unbounded region.
The Corner Point Theorem
The most important theorem used to identify the optimal solution is the Corner Point Theorem (also known as the Extreme Point Theorem). It states:
"If an optimal solution to an L.P.P. exists, it must occur at one of the vertices or corner points of the feasible region."
This theorem simplifies the problem significantly. Instead of testing thousands of points inside the region, we only need to calculate the value of $Z$ at the finite number of points where the boundary lines intersect.
Procedure to find Optimal Solution
1. Identify the corner points of the feasible region by solving the equations of the intersecting lines.
2. Substitute the coordinates of each corner point into the objective function $Z = ax + by$.
3. Compare the resulting values. The highest value is the Maximum, and the lowest is the Minimum.
$Z_{max} = \text{max}\{Z(P_1), Z(P_2), \dots, Z(P_n)\}$
[For bounded regions]
If the feasible region is unbounded, we must check if there is any point $(x, y)$ such that $ax + by > M$ (for maximization) or $ax + by < m$ (for minimization) outside the current region before confirming the result.
Basic Requirements of Linear Programming
For a problem to be solved using Linear Programming (L.P.), it must satisfy the following fundamental conditions:
1. Well-Defined Objective
There must be a clearly identified objective that needs to be achieved. This objective must be capable of being expressed as a linear function. Generally, this involves the maximization of profit or the minimization of cost or resources.
2. Limited Resources (Constraints)
There must be constraints or restrictions on the availability of resources, such as capital, labor, raw materials, or machine capacity. Without limitations, there would be no optimization problem to solve, as one could produce infinite goods.
3. Finiteness
The problem must have a finite number of decision variables and a finite number of constraints. If the variables or constraints are infinite, the problem cannot be solved using standard L.P. methods.
4. Linearity and Quantifiability
All elements of the problem—both the objective function and the constraints—must be quantifiable in numerical terms. Furthermore, the relationships between the variables must be linear, meaning they must follow the general form:
$f(x, y) = ax + by$
[Linearity Requirement]
5. Alternative Courses of Action
There must be several alternative ways to utilize the resources. If there is only one way to achieve a goal, there is no need for "programming" or planning to find the best option.
6. Non-Negative Variables
The variables must assume non-negative values. In practical applications, this means:
$x \geq 0, y \geq 0$
Advantages of Linear Programming
Linear Programming offers several benefits in the field of management and resource allocation, particularly in an Indian economic context where resource optimization is crucial.
1. Selection of Best Alternative
L.P. provides a logical and mathematical basis for choosing the best alternative from a set of feasible solutions, ensuring that the firm achieves the highest possible profit or the lowest possible cost.
2. Media Mix and Advertising
It is used to determine the most effective Media Mix. For example, a company with a fixed budget of $\textsf{₹} 10,00,000$ can use L.P. to decide how much to spend on Television, Radio, and Social Media ads to maximize its reach.
3. Logistics and Transportation
L.P. helps in determining the shortest and most cost-effective routes for traveling salesmen and delivery fleets, thereby saving fuel and time.
4. Agricultural Planning
In India, a farmer can use L.P. to decide the best crop mix. By considering constraints like land size, water availability, and seed cost, the farmer can maximize yield while minimizing financial risk.
5. Identifying Bottlenecks
It helps in identifying "bottlenecks" (limitations) in the production process. When a constraint is binding, it indicates that increasing that specific resource will lead to a direct increase in the objective value.
Limitations of Linear Programming
Despite its many advantages, Linear Programming has certain limitations that should be kept in mind:
1. Single Objective Focus
L.P. usually focuses on optimizing a single objective (e.g., maximize profit). However, in real-world business, a manager might have multiple conflicting objectives, such as maximizing profit while also maximizing employee satisfaction and environmental safety.
2. Assumption of Linearity
The model assumes that the relationship between inputs and outputs is strictly linear. In reality, economies of scale often exist—producing more units might decrease the average cost per unit, which makes the relationship non-linear.
3. Divisibility (Continuity) Problem
L.P. assumes that decision variables are continuous. This means the solution could suggest buying $2.75$ machines or hiring $4.5$ workers. Since machines and humans must be whole numbers (integers), the L.P. solution must often be rounded, which may not always result in the most optimal feasible point.
4. Proportionality and Additivity
L.P. assumes that the total requirement of resources is the sum total of resources required for individual activities. It ignores synergies where combining two activities might require fewer resources than the sum of the two individually.
5. Static Parameters
L.P. assumes that factors like market demand, prices of raw materials, and labor costs remain constant during the period of study. In a volatile market, these values can change rapidly, making the original solution outdated.
Formation of an L.P.P in Two Variables x and y
The process of converting a real-world optimization problem into a mathematical structure is known as the formulation of a Linear Programming Problem (L.P.P.). When dealing with two variables, usually denoted as $x$ and $y$, we can visualize the problem on a two-dimensional Cartesian plane. This formulation is the most critical step, as the accuracy of the final solution depends entirely on the correct representation of the objective and constraints.
There are three primary steps involved in the mathematical formulation and subsequent solution of an L.P.P.:
Step I: Identification and Construction of the Model
The first and most fundamental step in solving any Linear Programming Problem is the identification of the variables and the construction of the mathematical model. This step is divided into three essential parts:
1. Identification of Decision Variables
The first task is to identify the quantities whose values are to be determined. These are called Decision Variables. In most classroom problems, we deal with two variables, usually denoted as $x$ and $y$.
For example, in a manufacturing unit in India producing two types of electronics—Fans and Tubelights—we would let:
$x = $ Total number of Fans produced
$y = $ Total number of Tubelights produced
These variables are the "decisions" that the manager needs to make to optimize the business outcome.
2. Construction of the Objective Function
The Objective Function is a linear mathematical expression that defines the goal of the problem. It is a linear combination of the decision variables $x$ and $y$, multiplied by their respective contribution coefficients (like profit per unit or cost per unit).
If $a$ represents the profit/cost per unit of $x$, and $b$ represents the profit/cost per unit of $y$, the total objective $Z$ is formulated as:
Maximize (or minimize) $Z = ax + by$
In a business scenario, $Z$ usually represents Total Profit (which we want to maximize) or Total Cost (which we want to minimize). The coefficients $a$ and $b$ are always constants determined by the market conditions or internal production data.
3. Formulation of Constraints
Resources such as labor, raw materials, machine capacity, and capital are always limited. These limitations are expressed mathematically as Constraints. Constraints are linear inequalities or equations that the decision variables must satisfy.
A typical problem will have several constraints (say $n$ constraints). Each constraint $i$ is represented as:
$a_i x + b_i y \leq c_i$
[Resource Constraint]
Or in some cases, such as diet problems where minimum requirements must be met:
$a_i x + b_i y \geq c_i$
[Requirement Constraint]
In these expressions, $a_i$ and $b_i$ are the amount of resource $i$ required per unit of $x$ and $y$ respectively, and $c_i$ is the total availability or requirement of that resource.
4. Non-negative Restrictions
This is a logical requirement of any physical system. Since $x$ and $y$ represent physical quantities (like number of items, amount of food, or hectares of land), they cannot be negative. We cannot produce "$-10$" tubelights.
Therefore, we must always add the following conditions to our model:
$x \geq 0, y \geq 0$
These restrictions ensure that our Feasible Region (the set of all possible solutions) is located exclusively in the First Quadrant of the coordinate system.
Step II: Finding the Feasible Region
The determination of the feasible region involves the following technical steps:
1. Conversion of Inequalities into Equations
To plot the boundary of a constraint, we first treat the inequality as a linear equation. For a constraint like $ax + by \leq c$, we consider the equation of the straight line:
$ax + by = c$
[Boundary Line Equation]
To draw this line on a graph, we find the intercepts on the $x$ and $y$ axes:
• For $x$-intercept, put $y = 0 \implies x = \frac{c}{a}$. The point is $(\frac{c}{a}, 0)$.
• For $y$-intercept, put $x = 0 \implies y = \frac{c}{b}$. The point is $(0, \frac{c}{b})$.
By joining these two points, we obtain the boundary line for that specific constraint.
2. Identifying the Half-Plane (Shading)
Every linear equation $ax + by = c$ divides the Cartesian plane into two half-planes. The inequality ($<$ or $>$) determines which side of the line represents the solution set. To identify the correct side, we perform the Origin Test.
The Origin Test: Substitute the coordinates of the origin $(0, 0)$ into the inequality.
• If the inequality holds true (e.g., $0 \leq 10$), then the feasible half-plane is the one that contains the origin.
• If the inequality is false (e.g., $0 \geq 15$), then the feasible half-plane is the one away from the origin.
Note: If the line passes through the origin ($c = 0$), the origin test cannot be used. In such cases, we pick any other point like $(1, 0)$ or $(0, 1)$ to test the side.
3. Intersection of Regions (The Common Area)
The Feasible Region is the intersection of all the individual half-planes defined by the constraints. We shade only the area that is common to all plotted inequalities.
Because of the non-negative restrictions ($x \geq 0, y \geq 0$), the feasible region is always restricted to the First Quadrant. This means the region is bounded on the left by the $y$-axis and at the bottom by the $x$-axis.
Types of Feasible Regions
Based on the constraints, the resulting common region can take two forms:
(a) Bounded Feasible Region
A region is Bounded if it can be enclosed within a circle of some finite radius. It usually looks like a closed polygon. In such regions, both a maximum and a minimum value of the objective function $Z$ are guaranteed to exist at the corner points.
(b) Unbounded Feasible Region
An Unbounded region extends infinitely in at least one direction. For such regions, an optimal value (maximum or minimum) might not exist. If the objective is to maximize $Z$ and the region is unbounded in the positive direction, $Z$ might increase infinitely.
Corner Points (Vertices)
The points where the boundary lines intersect to form the vertices of the feasible region are called Corner Points. These points are mathematically significant because, according to the Fundamental Theorem of Linear Programming, the optimal solution must occur at one of these vertices.
To find the coordinates of a corner point where two lines $L_1$ and $L_2$ intersect, we solve the two corresponding linear equations simultaneously using methods like substitution or elimination.
Step III: Determining the Optimal Solution
The final stage in solving a Linear Programming Problem is the identification of the Optimal Solution. After the feasible region has been mapped and the corner points (vertices) identified, we must determine which of these points provides the "best" value for the objective function $Z$. In the context of business and economics, this usually means the maximum profit or the minimum cost.
This process is governed by the Fundamental Theorem of Linear Programming, which simplifies the search for an optimum from the infinite points within the feasible region to just a few specific points on the boundary.
The Corner Point Method
The Corner Point Method is the standard procedure for finding the optimal solution in a graphical L.P.P. It is based on the principle that if an optimal solution exists, it must occur at one of the vertices of the feasible region. If the feasible region is a convex polygon, the optimum value will be found at one of its corners.
Step-by-Step Procedure:
1. Identify Vertices: List the coordinates of all corner points $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ of the feasible region. These are found by solving the simultaneous equations of the lines that intersect at each corner.
2. Calculate Objective Values: Substitute the coordinates of each corner point into the objective function:
$Z = ax + by$
3. Comparison: Compare the values of $Z$ obtained at each vertex. If the objective is to maximize, select the largest value; if the objective is to minimize, select the smallest value.
4. Verification (For Unbounded Regions): If the feasible region is unbounded, the value obtained from the corner point is only a candidate for the optimal solution. To confirm:
• For Maximization: Check if the open half-plane $ax + by > M$ has any point in common with the feasible region (where $M$ is the max value from the corner points).
• For Minimization: Check if the open half-plane $ax + by < m$ has any point in common with the feasible region (where $m$ is the min value from the corner points).
If there are common points, the L.P.P. has no optimal solution. If there are no common points, then $M$ (or $m$) is the optimal value.
Special Case: Multiple Optimal Solutions
In some Linear Programming Problems, there is not just one, but infinitely many optimal solutions. This occurs when the objective function line is parallel to one of the boundary lines of the feasible region.
If two adjacent corner points, say $P$ and $Q$, yield the same maximum (or minimum) value of $Z$, then every single point on the line segment joining $P$ and $Q$ is an optimal solution. This means the decision-maker has multiple ways to achieve the same best possible outcome.
$Z(P) = Z(Q) = Z_{opt}$
[Condition for Multiple Optima]
Summary of Outcomes
Depending on the constraints and the objective function, an L.P.P. can result in one of the following four outcomes:
1. Unique Optimal Solution
Exactly one corner point provides the maximum or minimum value of $Z$.
2. Multiple Optimal Solutions
Two or more corner points provide the same optimal value, making all points on the connecting boundary line optimal.
3. No Feasible Solution
This occurs when the constraints are contradictory, leaving no common region (empty feasible region). In this case, there is no way to satisfy all the requirements at once.
4. Unbounded Solution
This happens in some unbounded feasible regions where the objective function can be increased (or decreased) infinitely. In such cases, the problem is said to have an unbounded solution, and no finite maximum (or minimum) exists.
Example 1. (Manufacturing Problem) A small-scale industrialist in Ludhiana produces two types of items: A and B. Each unit of item A requires 3 hours of labor and 2 hours of machine time. Each unit of item B requires 2 hours of labor and 3 hours of machine time. There are 60 hours of labor and 60 hours of machine time available per week. The profit on item A is $\textsf{₹} 40$ per unit and on item B is $\textsf{₹} 50$ per unit. Formulate the L.P.P. to maximize the weekly profit.
Answer:
Step 1: Identify Decision Variables
Let $x$ be the number of units of item A produced per week.
Let $y$ be the number of units of item B produced per week.
Step 2: Construct Objective Function
The total profit $Z$ is derived from the profit on individual items:
$Z = 40x + 50y$
[To be Maximized]
Step 3: Formulate Constraints
The usage of labor and machine hours must not exceed the available capacity.
Labor Constraint:
$3x + 2y \leq 60$
... (i)
Machine Time Constraint:
$2x + 3y \leq 60$
... (ii)
Step 4: Non-negative Restrictions
Since the production cannot be negative:
$x \geq 0, y \geq 0$
... (iii)
The final formulation is: Maximize $Z = 40x + 50y$ subject to constraints (i), (ii), and (iii).
Example 2. (Diet Problem) A nutritionist in Delhi wants to find the cheapest mix of two foods, $F_1$ and $F_2$, to meet the minimum daily requirement of Vitamin A and Vitamin C. The following table provides the data:
| Nutrient | Food $F_1$ (units/kg) | Food $F_2$ (units/kg) | Min. Requirement |
|---|---|---|---|
| Vitamin A | 2 | 1 | 8 units |
| Vitamin C | 1 | 2 | 10 units |
| Cost per kg | $\textsf{₹} 50$ | $\textsf{₹} 70$ | - |
Formulate and find the corner points of the feasible region.
Answer:
Let $x$ kg of $F_1$ and $y$ kg of $F_2$ be used in the diet.
Objective Function: Minimize total cost $Z = 50x + 70y$.
Constraints:
Vitamin A: $2x + y \geq 8$
Vitamin C: $x + 2y \geq 10$
Non-negativity: $x \geq 0, y \geq 0$
Finding Corner Points:
To find the vertices, we convert inequations into equations:
$L_1: 2x + y = 8$ (Points: $(4, 0)$ and $(0, 8)$)
$L_2: x + 2y = 10$ (Points: $(10, 0)$ and $(0, 5)$)
The intersection of $L_1$ and $L_2$ is found by solving them simultaneously:
Multiply $L_1$ by 2: $4x + 2y = 16$
Subtract $L_2$: $(4x + 2y) - (x + 2y) = 16 - 10$
$3x = 6 \implies x = 2$
Substitute $x=2$ in $L_1$: $2(2) + y = 8 \implies y = 4$
The corner points of the unbounded feasible region are: $A(0, 8)$, $B(2, 4)$, and $C(10, 0)$.
Example 3. (Allocation Problem) A farmer has a plot of 10 hectares in Punjab. He can grow Wheat and Barley. The profit per hectare for Wheat is $\textsf{₹} 5,000$ and for Barley is $\textsf{₹} 4,000$. He has only 20 units of fertilizer available. Wheat requires 4 units/hectare and Barley requires 1 unit/hectare. Find the crop mix for maximum profit.
Answer:
Let $x$ be the area for Wheat and $y$ be the area for Barley (in hectares).
Maximize: $Z = 5000x + 4000y$
Constraints:
$x + y \leq 10$
(Land Limit) ... (i)
$4x + y \leq 20$
(Fertilizer Limit) ... (ii)
$x \geq 0, y \geq 0$
Corner Points calculation:
1. Origin: $(0, 0) \implies Z = 0$
2. Intercept of (i): $(10, 0)$ and $(0, 10)$
3. Intercept of (ii): $(5, 0)$ and $(0, 20)$
4. Intersection of (i) and (ii): Subtract (i) from (ii): $(4x+y)-(x+y) = 20-10 \implies 3x = 10 \implies x = 3.33, y = 6.67$.
Evaluating $Z$ at Corner Points:
• At $(0, 10)$: $Z = 4000(10) = 40,000$
• At $(5, 0)$: $Z = 5000(5) = 25,000$
• At $(3.33, 6.67)$: $Z = 5000(3.33) + 4000(6.67) \approx 16650 + 26680 = 43,330$
Optimal Solution: Maximum profit is approximately $\textsf{₹} 43,330$ by planting 3.33 hectares of Wheat and 6.67 hectares of Barley.
Example 4. (Investment Problem) An investor in Mumbai wants to invest $\textsf{₹} 12,000$ in two types of bonds, Bond A and Bond B. Bond A yields $8\%$ interest and Bond B yields $10\%$ interest. He wants to invest at least $\textsf{₹} 2,000$ in Bond A and at least $\textsf{₹} 4,000$ in Bond B. Also, the investment in Bond A should be at least equal to Bond B. Formulate the L.P.P.
Answer:
Let $x$ be the investment in Bond A and $y$ be the investment in Bond B.
Maximize Interest: $Z = 0.08x + 0.10y$
Subject to:
$x + y \leq 12000$
[Total Capital]
$x \geq 2000$
[Min. Bond A]
$y \geq 4000$
[Min. Bond B]
$x \geq y \implies x - y \geq 0$
[Comparative Constraint]
Example 5. (Transportation) A company has two godowns $G_1$ and $G_2$ with capacities of 100 and 50 units respectively. It needs to supply a dealer who requires 60 units. Let $x$ be the units sent from $G_1$ and $y$ be the units sent from $G_2$. If the transport cost from $G_1$ is $\textsf{₹} 5$ per unit and from $G_2$ is $\textsf{₹} 8$ per unit, formulate the minimization problem.
Answer:
Objective Function: Minimize $Z = 5x + 8y$
Constraints:
Demand constraint: $x + y = 60$
$G_1$ Capacity: $x \leq 100$
$G_2$ Capacity: $y \leq 50$
Non-negativity: $x, y \geq 0$
Since $x + y = 60$, we can substitute $y = 60 - x$ into the objective function to solve it as a single variable problem if needed.
Graphical Method of Solving an L.P.P.
The graphical method is a visual approach to solving Linear Programming Problems involving two variables. This method relies on fundamental mathematical theorems that link the geometry of the feasible region to the optimal value of the objective function.
The graphical method of solving a Linear Programming Problem (L.P.P.) is supported by two fundamental theorems of mathematics. These theorems allow us to narrow down our search for the optimal solution from an infinite number of points within the feasible region to just a few specific corner points.
Theorem 1: The Corner Point Theorem
This theorem is the cornerstone of linear programming. It states that the search for an optimal solution does not require checking every point in the feasible region.
Statement
Let $R$ be the feasible region (which is always a convex polygon) for a linear programming problem, and let $Z = ax + by$ be the objective function. When $Z$ has an optimal value (maximum or minimum), subject to the constraints described by linear inequalities, this optimal value must occur at a corner point (vertex) of the feasible region.
The feasible region $R$ contains infinitely many points. If we were to test every point $(x, y)$ inside the region, the task would be impossible. However, Theorem 1 guarantees that we only need to look at the "corners" where the boundary lines intersect. Even if there are multiple optimal solutions, at least one of them will be a corner point.
If the objective function is represented as:
$Z = ax + by$
The theorem ensures that the maximum or minimum of $Z$ is reached at the extreme boundaries of the set $R$.
Theorem 2: Existence of Max and Min in Bounded Regions
While Theorem 1 tells us where the optimal solution is located, Theorem 2 tells us when we are guaranteed to find one.
Statement
Let $R$ be the feasible region for a linear programming problem and let $Z = ax + by$ be the objective function. If $R$ is bounded, then the objective function $Z$ has both a maximum and a minimum value on $R$, and each of these occurs at a corner point (vertex) of $R$.
A bounded region is one that can be enclosed within a circle of a certain radius; it does not extend to infinity in any direction. Because the region is closed and finite, the linear function $Z$ is guaranteed to hit a highest point (maximum) and a lowest point (minimum) within that boundary.
Most manufacturing and allocation problems result in bounded regions, ensuring that a solution for maximum profit or minimum cost always exists at the vertices of the shaded region.
Remark on Unbounded Feasible Regions
The situation changes when the feasible region is unbounded (i.e., it extends infinitely in one or more directions). This often happens in Diet Problems where we only have "greater than or equal to" ($\geq$) constraints.
1. Existence: In an unbounded region, the objective function may or may not have a maximum or minimum value. For instance, if you want to maximize profit but the region allows $x$ and $y$ to grow to infinity, there is no finite maximum profit.
2. Location: However, the theorem still holds in a conditional sense: If an optimal value exists in an unbounded region, it must occur at a corner point. This is why we still calculate values at corner points for unbounded regions, but we must perform an additional verification step (the open half-plane test) to confirm if that value is truly the optimum.
3. Convexity: Regardless of whether the region is bounded or unbounded, it is always a convex set, meaning the segment joining any two feasible solutions stays within the feasible region.
The Corner Point Method
To solve an L.P.P. graphically, the Corner Point Method is employed. The systematic steps are as follows:
Step 1: Graphing the Constraints
Convert the given linear inequalities into linear equations (equalities). Draw their graphs on the $xy$-plane. These will be straight lines. Identify the half-plane for each inequality to determine the intersection area.
Step 2: Finding the Feasible Region
Identify the common region $R$ that satisfies all constraints and the non-negative restrictions ($x \geq 0, y \geq 0$). Determine the coordinates of all the corner points (vertices) of this region $R$.
Step 3: Evaluating the Objective Function
Evaluate the objective function at each corner point. Suppose there are $n$ corner points. Calculate $Z$ for each:
$Z = ax + by$
... (i)
Let $M$ be the largest value and $m$ be the smallest value obtained from these points.
Step 4: Conclusion for Bounded Regions
If the feasible region $R$ is bounded, then $M$ is the absolute maximum value and $m$ is the absolute minimum value of $Z$.
Special Case: Unbounded Feasible Region
If the feasible region $R$ is unbounded, we must perform an additional check to confirm the optimality of $M$ and $m$:
(a) For Maximum Value: $M$ is the maximum value of $Z$ only if the open half-plane determined by the inequality $ax + by > M$ has no points in common with the feasible region. If there are common points, $Z$ has no maximum value.
(b) For Minimum Value: $m$ is the minimum value of $Z$ only if the open half-plane determined by the inequality $ax + by < m$ has no points in common with the feasible region. If there are common points, $Z$ has no minimum value.
Multiple Optimal Solutions
If two corner points of the feasible region result in the same optimal value (either both give $M$ or both give $m$), then the problem has infinitely many solutions. In this case, every point on the line segment joining these two optimal corner points will also provide the same maximum or minimum value for the objective function.
For example, if points $P(x_1, y_1)$ and $Q(x_2, y_2)$ both give $Z = 100$, then any point $(x, y)$ on the segment $PQ$ will also yield $Z = 100$.
Example 1. A small-scale industrialist in Ludhiana produces two types of items: A and B. Profit on item A is $\textsf{₹} 40$ and on item B is $\textsf{₹} 50$. Constraints: $3x + 2y \leq 60$ (Labor), $2x + 3y \leq 60$ (Machine), $x, y \geq 0$. Find the maximum profit.
Answer:
To solve this, we first plot the lines corresponding to the constraints.
For $3x + 2y = 60$, the intercepts are $(20, 0)$ and $(0, 30)$.
For $2x + 3y = 60$, the intercepts are $(30, 0)$ and $(0, 20)$.
Solving these two equations simultaneously to find the intersection point:
$3(2x + 3y) - 2(3x + 2y) = 3(60) - 2(60)$
(Elimination method)
$5y = 60 \implies y = 12$
... (i)
Substituting $y = 12$ in $3x + 2y = 60$ gives $x = 12$. The intersection point is $(12, 12)$.
The corner points of the bounded feasible region are $O(0, 0)$, $A(20, 0)$, $B(12, 12)$, and $C(0, 20)$. Evaluating $Z = 40x + 50y$:
• At $O(0, 0)$: $Z = 0$
• At $A(20, 0)$: $Z = 40(20) + 50(0) = 800$
• At $C(0, 20)$: $Z = 40(0) + 50(20) = 1000$
• At $B(12, 12)$: $Z = 40(12) + 50(12) = 480 + 600 = 1080$
The maximum profit is $\textsf{₹} 1,080$ at $x = 12, y = 12$.
Example 2. Minimize cost $Z = 50x + 70y$ subject to $2x + y \geq 8$, $x + 2y \geq 10$, $x, y \geq 0$.
Answer:
The boundary lines are $2x + y = 8$ and $x + 2y = 10$.
Since both constraints are $\geq$, the feasible region is unbounded and lies away from the origin.
The intersection point of the two lines is $(2, 4)$.
Corner Points are $A(0, 8)$, $B(2, 4)$, and $C(10, 0)$. Evaluating $Z = 50x + 70y$:
• At $A(0, 8)$: $Z = 50(0) + 70(8) = 560$
• At $C(10, 0)$: $Z = 50(10) + 70(0) = 500$
• At $B(2, 4)$: $Z = 50(2) + 70(4) = 100 + 280 = 380$
The minimum cost is $\textsf{₹} 380$ at $x = 2, y = 4$.
Example 3. Maximize profit $Z = 5000x + 4000y$ subject to $x + y \leq 10$, $4x + y \leq 20$, $x, y \geq 0$.
Answer:
Boundary lines: $x + y = 10$ and $4x + y = 20$.
The intersection point is $(\frac{10}{3}, \frac{20}{3})$ or approximately $(3.33, 6.67)$.
Evaluating $Z$ at corner points:
• At $(0, 0)$: $Z = 0$
• At $(5, 0)$: $Z = 25000$
• At $(0, 10)$: $Z = 40000$
• At $(3.33, 6.67)$: $Z = 5000(3.33) + 4000(6.67) = 16650 + 26680 = 43330$
The maximum profit is $\textsf{₹} 43,330$.
Example 4. Maximize interest $Z = 0.08x + 0.10y$ subject to $x + y \leq 12000$, $x \geq 2000$, $y \geq 4000$, and $x \geq y$.
Answer:
We plot the lines $x + y = 12000$, $x = 2000$, $y = 4000$, and $x = y$.
The feasible region is a small polygon in the first quadrant where all conditions are met.
Corner points: $P(4000, 4000)$, $Q(8000, 4000)$, and $R(6000, 6000)$.
Evaluating $Z$:
• At $P(4000, 4000)$: $Z = 320 + 400 = 720$
• At $Q(8000, 4000)$: $Z = 640 + 400 = 1040$
• At $R(6000, 6000)$: $Z = 480 + 600 = 1080$
Maximum interest is $\textsf{₹} 1,080$ at $x=6000, y=6000$.
Example 5. Minimize transportation cost $Z = 5x + 8y$ subject to $x + y = 60$, $x \leq 100$, $y \leq 50$, $x, y \geq 0$.
Answer:
Since $x + y = 60$ is an equality, the feasible region is a line segment.
Substituting $x = 60 - y$ into $y \leq 50$ gives $60 - x \leq 50 \implies x \geq 10$.
Also, from $x, y \geq 0$ and $x + y = 60$, the max $x$ can be is $60$ (where $y=0$).
So, $x$ ranges from $10$ to $60$.
The corner points are $(10, 50)$ and $(60, 0)$.
Evaluating $Z = 5x + 8y$:
• At $(10, 50)$: $Z = 5(10) + 8(50) = 50 + 400 = 450$
• At $(60, 0)$: $Z = 5(60) + 8(0) = 300$
The minimum cost is $\textsf{₹} 300$ at $x = 60, y = 0$.