01 · Explore
Introduction to Optimization Problems
Optimization problems are a general class of mathematical problems that seek to find the best possible outcome, such as maximum profit or minimum cost, under a given set of constraints.
In real-world scenarios, resources like money, time, and space are often limited. For instance, a furniture dealer might have a fixed budget and limited storage space. To maximize profit, the dealer must decide how many units of different items to purchase. This decision-making process, when expressed through linear relationships, is known as Linear Programming (LP).
Linear Programming is widely used in industry, commerce, and management science. It involves a linear objective function that needs to be optimized (maximized or minimized) subject to a set of linear inequalities or equations called constraints. The variables involved, such as the number of items to buy, are called decision variables and must be non-negative.
Pause & Try
Think it through first. Writing and checking your answer is free with an account.
Question
What defines a problem as a 'Linear Programming Problem'?
Sign in to see the answer
Write your own answer and compare it with ours. It’s free.
Sign inNew here? Sign up freeNCERT reference: chapter PDF pages 1, 2, 3.
02 · Explore
Mathematical Formulation of LP Problems
Formulating an LP problem involves translating real-world constraints and goals into mathematical expressions.
The first step in formulation is identifying the decision variables, usually denoted as x and y. These represent the quantities we need to determine. Because we cannot have a negative number of physical items, we always include non-negative constraints: x ≥ 0 and y ≥ 0.
Next, we define the objective function, Z = ax + by, where 'a' and 'b' are constants representing profit or cost per unit. Finally, we write the constraints as linear inequalities. For example, if a table costs 2500 and a chair costs 500, and the total budget is 50000, the constraint is 2500x + 500y ≤ 50000.
Formulating a Production Problem
Maximize Z = 40x + 50y subject to x + 2y ≤ 10, 3x + y ≤ 15, x ≥ 0, y ≥ 0
Here, x and y are units of two products. Z represents total profit with 40 and 50 being profit per unit. The inequalities represent resource limits like labor hours or raw materials.
Pause & Try
Think it through first. Writing and checking your answer is free with an account.
Question
Why are x ≥ 0 and y ≥ 0 called non-negative restrictions?
Sign in to see the answer
Write your own answer and compare it with ours. It’s free.
Sign inNew here? Sign up freeNCERT reference: chapter PDF pages 2, 3.
03 · Explore
Feasible Region and Feasible Solutions
The feasible region is the set of all points that satisfy all the given constraints simultaneously.
When we graph the system of linear inequalities, the area where all the shaded half-planes overlap is the feasible region. Any point (x, y) located within this region or on its boundary is a feasible solution, meaning it satisfies all the rules of the problem.
Points outside this region are called infeasible solutions because they violate at least one constraint. If the feasible region can be enclosed within a circle, it is called a bounded region. If it extends infinitely in any direction, it is called an unbounded region.
| Term | Definition |
|---|---|
| Feasible Region | The common region determined by all constraints including x, y ≥ 0. |
| Feasible Solution | Any point within or on the boundary of the feasible region. |
| Optimal Solution | A feasible solution that gives the maximum or minimum value of Z. |
| Infeasible Region | Any region outside the feasible region. |
Pause & Try
Think it through first. Writing and checking your answer is free with an account.
Question
If a point satisfies three out of four constraints, is it a feasible solution?
Sign in to see the answer
Write your own answer and compare it with ours. It’s free.
Sign inNew here? Sign up freeNCERT reference: chapter PDF pages 4, 5.
04 · Explore
Fundamental Theorems of Linear Programming
Two key theorems provide the mathematical basis for solving LP problems using the graphical method.
Theorem 1 states that if an optimal value (maximum or minimum) exists for a linear objective function Z over a feasible region R (a convex polygon), then that optimal value must occur at a corner point (vertex) of the region.
Theorem 2 states that if the feasible region R is bounded, then the objective function Z has both a maximum and a minimum value on R, and each occurs at a corner point. If the region is unbounded, an optimal value might not exist, but if it does, it will still be at a corner point.
Pause & Try
Think it through first. Writing and checking your answer is free with an account.
Question
Where does the optimal value of an objective function always occur in a bounded feasible region?
Sign in to see the answer
Write your own answer and compare it with ours. It’s free.
Sign inNew here? Sign up freeNCERT reference: chapter PDF page 5.
05 · Explore
The Corner Point Method
The Corner Point Method is a systematic procedure to find the optimal solution of an LP problem graphically.
The method begins by graphing all constraints to find the feasible region. Once the region is identified, we determine the coordinates of all its corner points. These coordinates are found either by looking at the graph or by solving the equations of the intersecting lines.
We then evaluate the objective function Z = ax + by at each corner point. For a bounded region, the largest value obtained is the maximum, and the smallest is the minimum. For unbounded regions, additional verification is required to ensure the value is truly the optimum.
Steps of the Corner Point Method
- 1
Graph Constraints
Draw the lines for each inequality and identify the common shaded feasible region.
- 2
Identify Vertices
Find the coordinates (x, y) for every corner point of the feasible region.
- 3
Evaluate Z
Substitute the coordinates of each vertex into the objective function Z = ax + by.
- 4
Select Optimum
Identify the maximum or minimum value from the calculated results.
Sequential process for solving a linear programming problem graphically.
Pause & Try
Think it through first. Writing and checking your answer is free with an account.
Question
What is the next step after finding the corner points?
Sign in to see the answer
Write your own answer and compare it with ours. It’s free.
Sign inNew here? Sign up freeNCERT reference: chapter PDF page 6.
06 · Explore
Worked Example: Bounded Feasible Region
Let's solve a maximization problem where the feasible region is enclosed.
Consider the problem: Maximise Z = 3x + 4y subject to x + y ≤ 4, x ≥ 0, y ≥ 0. The boundary lines are x + y = 4, x = 0, and y = 0.
The corner points of the resulting triangle are (0, 0), (4, 0), and (0, 4). We test these in the objective function to find the maximum profit.
Maximizing Z = 3x + 4y
At (0,0): Z=0; At (4,0): Z=3(4)+0=12; At (0,4): Z=3(0)+4(4)=16
Comparing the values 0, 12, and 16, the maximum value is 16.
The maximum value of Z is 16, which occurs at the point (0, 4).
Pause & Try
Think it through first. Writing and checking your answer is free with an account.
Question
If Z = 5x + 2y and corner points are (0,0), (2,0), and (0,5), what is the maximum value?
Sign in to see the answer
Write your own answer and compare it with ours. It’s free.
Sign inNew here? Sign up freeNCERT reference: chapter PDF pages 6, 7, 10.
07 · Explore
Multiple Optimal Solutions
Sometimes, an LP problem can have more than one point that produces the same optimal value.
If two corner points of the feasible region produce the same maximum (or minimum) value, then every single point on the line segment joining these two corner points will also produce that same optimal value.
This happens when the objective function line is parallel to one of the constraint boundary lines. In such cases, the problem is said to have infinite or multiple optimal solutions.
Pause & Try
Think it through first. Writing and checking your answer is free with an account.
Question
If Z = 100 at corner points (2, 4) and (5, 4), what is the value of Z at (3.5, 4)?
Sign in to see the answer
Write your own answer and compare it with ours. It’s free.
Sign inNew here? Sign up freeNCERT reference: chapter PDF pages 8, 10.
08 · Explore
Unbounded Regions and Infeasible Problems
Not every LP problem has a simple solution; some regions are infinite, and some constraints are contradictory.
In an unbounded feasible region, a maximum or minimum value might not exist. To check if a value 'M' is the maximum in an unbounded region, we graph the inequality ax + by > M. If this open half-plane has any points in common with the feasible region, then Z has no maximum value.
In some cases, the constraints are contradictory, such as x + y ≥ 8 and x + y ≤ 3. When graphed, there is no overlapping area. In this situation, there is no feasible region and therefore no feasible solution.
Pause & Try
Think it through first. Writing and checking your answer is free with an account.
Question
What does it mean if an LP problem has no feasible region?
Sign in to see the answer
Write your own answer and compare it with ours. It’s free.
Sign inNew here? Sign up freeNCERT reference: chapter PDF pages 9, 10.