Content Curator
Optimization is the method of solving a mathematical problem in a way that the solution is the best-case scenario from the set of all solutions. Thus, optimization problems can involve maximizing or minimizing a quantity with respect to certain constraints. One of the types of optimization problems is linear programming problems. An optimization problem minimizes or maximizes the value of a given linear function with respect to certain constraints.
| Table of Content |
Key Words: Maximizing or minimizing, linear programming, optimization, quantities, variables, equation, function, calculations
Also Read: Binary Operations
Mathematical Optimization Problems
[Click Here for Sample Questions]
The constraint may be determined in the form of an equation. So, optimization is determining the best possible solution to a given problem within these specified constraints from the set of all other alternate solutions. You’ll be looking for either the highest value or the lowest value for a function. The constraint will be represented in the form of an equation.
No matter the solution, the constraint needs to be satisfied. One of the quantities will be constant throughout the problem. You need to determine the quantity that needs to be optimize. Once that is done, you can move on with the further calculations.
Mathematical Optimization
Let us look at how such mathematical problems are formulated.
If x and y are the number of bats and balls a shopkeeper purchases, then x ≥ 0 and y ≥ 0. And if they have a storage capacity of 50 units in total, then
x + y ≤ 50
Now, if the cost of a bat and a ball is ?350 and ?50 respectively and the total money the shopkeeper can invest is ?5000, then
350x + 50y ≤ 5000
7x + y ≤ 100
When the shopkeeper sells a bat and a ball, the profit earned on each is Π50 and Π15, respectively.
Z = 50x + 15y
So, the problem comes down to
Maximize Z = 50x + 15y
with respect to the constraints
x ≥ 0
y ≥ 0
x + y ≤ 50
7x + y ≤ 100
Also Read: Linear equation
Why do we use Mathematical Optimization?
[Click Here for Previous Year Questions]
Optimization is the process of coming to the best solution in a given situation. This enables us to understand all the factors affecting the solution, which leads to a better decision-making strategy. Mathematical Optimization is beneficial as it can help maximize profit, limit resources, minimize cost, increase efficiency and help to understand the changes in the output for varied input.
The three main components of mathematical optimization are Decision Variables, Objective Function, and Constraints.
- Decision Variables
A decision variable is a physical quantity represented by a mathematical symbol. The decision variables, as it suggests, can vary and are chosen by the decision-maker. An example of a decision variable is the number of units to be produced by a company.
- Objective Function
A mathematical function is that which consists of decision variables and is a numerical representation of the solution. The objective function can represent profit or the cost based on the products included.
- Constraints
Constraints are the limitations on the value that decision variables can have. An example of a constraint is the number of hours a machine can work each day.
Mathematical Optimization in Day-to-Day Life
[Click Here for Sample Questions]
Mathematical Optimization is used by businesses to increase production and to increase their profit margins. Some places where mathematical optimization is applied are:
- It is used by GPS systems and by shipping companies to deliver packages.
- It is also used by businesses to improve various functions, like manufacturing rates, supply chain, transportation, logistics, and inventory control.
- It is applied in the fields of medicine, finance, artificial intelligence, physics, economics, operations research, etc.
Also Read:
Things to Remember
- Optimization is the method of finding the best possible solution in any given situation.
- The three components involved in mathematical optimization are decision variables, objective function, and constraints.
- Decision variables are physical quantities that can vary and are chosen by the decision-maker.
- An objective function is the numerical representation of the solution consisting of decision variables.
- Constraint is the limiting factor for decision variables and should be fulfilled for any solution, no matter what.
- Businesses use mathematical optimization to increase their profit and reduce the cost, which is to find the most optimum way to work through any scenario.
Previous Year Questions
- If x+y≤2,x≥0,y≥0 the point at which maximum value of 3x + 2y3x+2y attained will be….[KCET 2014]
- The feasible region of an LPP is shown in the figure . If z = 3x + 9y ,z=3x+9y, then the minimum value of z occurs at..[KCET 2018]
- For the given LPP (Linear Programming Problem) the optimal solution set is...[JKCET 2013]
- The objective function z=4x1+5x2, subject to
- The objective function of LPP defined over the convex set attains its optimum value at….[MHT CET 2017]
- A basic solution is called non-degenerate, if…..
- The solution set of constraints x+2y≥11,3x+4y≤30,2x+5y≤30
- What quantities should wheat and rice be mixed in the daily diet to provide minimum daily requirement of proteins and carbohydrates at minimum cost
- The maximum value of z=3x+4y..
- If refinery A costs ? 400 per day and refinery B costs ? 300 per day to operate, then the days should each be run to minimize costs while satisfying requirement are..
- Which of these terms is not used in a linear programming problem?
Sample Questions
Ques. Define linear constraints and objective function. (2 Marks)
Ans. Linear Constraints - The limiting conditions in the form of equations or inequations of an LPP that are to be fulfilled under which optimization is accomplished are called linear constraints.
Objective Function - In an LPP, a linear function of the form Z = ax + by that is to be optimized is called an objective function. (a and b are constants)
Ques. State the two theorems used to solve linear programming problems. (3 Marks)
Ans. The two fundamental theorems used to solve LPP are stated below:
Theorem I:
If an optimal solution of LPP exists, it occurs at one of the corner points of the feasible region.
Theorem II:
For a bounded feasible region, there exist both maximum and minimum values of the objective function (Z) which occur at the corner points of the feasible region.
For an unbounded feasible region, the maximum and minimum values of the objective function may or may not exist. If any of it exists, it occurs at the corner points of the feasible region.
Ques. Find the maximum value of Z = 4x + 3y, if the corner points of the feasible region determined by the linear constraints are (0, 0), (0, 40), (20, 40), (60, 20) and (60, 0). (3 Marks)
Ans.
| Corner Points | Value of Z (Z = 4x + 3y) |
|---|---|
| (0, 0) | 0 |
| (0, 40) | 120 |
| (20, 40) | 200 |
| (60, 20) | 300 |
| (60, 0) | 240 |
So, the maximum value of Z is 300, which occurs at (60, 20).
Ques. Find the maximum value of the objective function, if Z = 4x + 3y for the feasible solution represented by the below graph. (5 Marks)
Ans. Z = 4x + 3y
| Corner Points | Value of Z (Z = 4x + 3y) |
|---|---|
| (0, 0) | 0 |
| (0, 6) | 18 |
| (3, 6) | 30 |
| (5, 4) | 32 |
| (4, 0) | 16 |
The maximum value of Z is 32, which occurs at (5, 4).
Ques. Find the minimum value for Z = 6x + 4y for the feasible solution shown in the below graph. (5 Marks)
Ans. Objective function Z = 6x + 4y
| Corner points | Value of Z (Z = 6x + 4y) |
|---|---|
| (0, 4) | 16 |
| (3, 7) | 46 |
| (6, 5) | 56 |
| (7, 3) | 54 |
| (7, 2) | 50 |
| (6, 0) | 36 |
The minimum value of Z is 16, which occurs at (0, 4).
Ques. A rectangular field is to be fenced on three sides so as to have the largest field possible. If the wire available for fencing is 400 m, then find the area covered by the field. (5 Marks)
Ans. If we denote the length and breadth of the rectangular field as x and y respectively, then the area can be determined by
A = x⋅y
Here, the constraint is
2x + y = 400
y = 400 - 2x
Substituting the value of y in the previous equation,
A(x) = x(400-2x) = 400x - 2x2
Now, we know that x > 0 and y > 0 and for y = 400 - 2x to be true, x < 200. So, we have that x is (0, 200).
From the extreme value theorem, we know that a continuous function within a closed interval has a maximum and a minimum value. So, if we consider x to be [0, 200], then for x = 0 or 200, A = 0, which is the minimum value.
According to the extreme value theorem, the maximum value of A then occurs at a critical point. Differentiating A(x),
A’(x) = 400 - 4x
To find the critical points, equate the first derivative to zero.
400 - 4x = 0
x = 100
To verify if this is the maximum value,
A’’(x) = -4
As the second derivative is less than 0, for x = 100, A(x) has the maximum value.
A = x(400-2x) = 100(400 - 200) = 20,000 m2
The largest possible area for the field is 20,000 m2.
Ques. The sum of two numbers is 50. What are the two numbers if their product is maximum? (5 Marks)
Ans. If the two numbers are a and b, then
a + b = 50
Their product ab is maximum. Let P = ab.
a = 50 - b
P(b) = (50 - b)b = 50b - b2
Now, their sum is positive and for their products to be maximum, a > 0 and b > 0. And as a = 50 - b, b < 50. So, the value of b is between (0, 50).
From the extreme value theorem, we know that a continuous function within a closed interval has a maximum and a minimum value. So, if we consider x to be [0, 50], then for x = 0 or 50, the product is 0, which is the minimum value.
So, the maximum value occurs at a critical point. Differentiating A(x),
A’(x) = 50 - 2b
Equating the first derivative to zero, to find the critical points
50 - 2b = 0
b = 25
To verify if this is the maximum value, find the second derivative.
A’’(x) = -2
As the value of the second derivative is less than 0, the value of A(x) is maximum at x = 25.
For x = 25, y = 25 as well.
Hence, the two numbers for their product to be maximum are 25 and 25.
Ques. Solve this linear programming problem using the graphical method:
Maximize Z = 5x + 3y with respect to 3x + 5y ≤ 15, 5x + 2y ≤ 10 and x, y ≥ 0. (5 Marks)
Ans. Converting the constraints into equations to plot the graph,
3x + 5y = 15, 5x + 2y = 10, x = 0, y = 0
The line 3x + 5y = 15 intersects the axes at points A1(5, 0) and B1(0, 3). And (0, 0) satisfies 3x + 5y ≤ 15, so the region, including the origin, is the solution.
The line 5x + 2y = 10 intersects the axes at points A2(2, 0) and B2(0, 5). Again, (0, 0) satisfies 5x + 2y ≤ 10, so the region, including the origin, is the solution.
Now, the region common to both these lines includes the origin and is limited to the first quadrant, as x, y ≥ 0 is the feasible region. From the graph, we have this region as OA2PB2, where P is the intersection point between the two lines.
From the two equations, 3x + 5y = 15 and 5x + 2y = 10, we get P as (\(\frac {20}{19}\), \(\frac{45}{19}\)).
According to the theorem, we have that within an enclosed feasible region, the maximum and minimum values occur at corner points.
We will check the values of Z for each of the corner points to determine the maximum value.
| Corner Points | Value of Z (Z = 5x + 3y) |
|---|---|
| (0, 0) | 0 |
| (2, 0) | 10 |
| \((\frac {20}{19}\), \(\frac{45}{19})\) | \((\frac {235}{19})\) |
| (0, 3) | 9 |
So, Z is maximum at (\(\frac {20}{19}\), \(\frac{45}{19}\)). And its optimal value is \(\frac {235}{19}\).
For Latest Updates on Upcoming Board Exams, Click Here: https://t.me/class_10_12_board_updates
Check-More:
Comments