Mathematics Test - 32

Explanation:

Linear Programming:

• Linear programming is used for the optimization of our limited resources when there are several alternatives solution possible for the problem.
• It is a mathematical technique and the term linear is used for the variable in the problem and it simply means that the relationship between the variable can be represented in the form of a straight line.
• The general LPP (Linear programming problems) calls for optimizing (maximizing/minimizing) a linear function for variables called the Constraints or restrictions.
• The standard form of LPP is:

\(Max.~Z~=~C_1 x_1~+~C_2 x_2 ~+......+~C_n x_n\) .............. (Objective function)................................... (1)

Subjected to:

 \(a_{11} x_1~+~a_{12} x_2~.......~x_{n~+~1}~=~b_1\\ a_{21} x_1~+~a_{22} x_2~.......~x_{n~+~2} ~=~b_2 \\.\\.\\.\\ a_{m1} x_1~+~a_{m2} x_1~......x_{n~+~m}~=~b_m\) .........................................................................(Constraints) (2)

Where, \(x_1~≥~0,~x_2~≥~0~.......~x_n~≥~0,~x_{n~+~1}~≥~0~........~x_{n~+~m}~≥~0\) ..................................(3)

And x₁, x₂, ......... x_n are called Decision variables.

x_{n + 1}, x_{n + 2}, ......... x_{n + m} are called slack variables.

C₁, C₂, ............C_n is called cost factors.

• The coefficient of slack variables xn + 1, xn + 2, ......... x_{n + m} in the objective function is assumed to be zero.
• Since in the case of (≥ 0) constraints, the substracted variables represent the surplus of the left side over the right side, it is commonly referred to as Surplus variables.
• The solution to LPP: Any set \(x\){\(x_1,~x_2,~............,~x_{n~+~m}\)} of variables is called a solution to LPP If it satisfies the set of constraints (2) only.
• The feasible solution: Any set \(x\){\(x_1,~x_2,~............,~x_{n~+~m}\)} of variables is called a feasible solution, if it satisfies the set of constraint (2) and non-negativity restrictions (3).
• Basic Solution: A basic solution is a solution obtained by setting n variables (Among m + n variables) equal to zero and solving for the remaining m variables provided the determinants of the coefficients of these m variables are non-zero. Such m variables are basic variables and the remaining n non-zero variables are called non-basic variables.
• The number of the basic solution thus obtained will be at most:

\(\frac{(m ~+~ n)!}{m!~n!}\)

• A basic feasible solution is a basic solution that satisfies (3), i.e., all basic variables are non-negative.

Linear scale:

• A linear scale also called a bar scale, scale bar, graphic scale, or graphical scale is a means of visually showing the scale of a map, nautical chart, engineering drawing, or architectural drawing.

Explanation:

Solution of a LPP. A set of values of the variables x₁, x₂,...,n satisfying the constraints of a LPP is called a solution of the LPP.

Feasible Solution of a LPP. A set of values of the variables x₁, x₂,.. x_n satisfying the constraints and non-negative restrictions of a LPP is called feasible solution of the LPP.

Optimal Solution of a LPP. A feasible solution of a LPP is said to be optimal (or optimum) if it also optimizes (i.e., maximizes or minimizes as the case may be) the objective function of the problem.

Graphical Solution of a LPP. The solution of a LPP obtained by graphical method i.e., by drawing the graphs corresponding to the constraints and the non-negative restrictions is called the graphical solution of a LPP.

Unbounded Solution. If the value of objective function can be increased or deceased indefinitely, such solutions are called unbounded solutions.

Fundamental Extreme Point Theorem. An optimum solution of a LPP, if it exists, occurs at one of the extreme points (i.e., corner points) of the convex of the set of all feasible solutions.

Concept: 

• Inequality: Two real expressions and numbers related by symbols ≥, ≤, < or > are inequalities.
• Examples: x - y ≥ 0 and x + y < 5.
• A linear inequation in two variables represents a line that divides the plane into two halves. A vertical line will divide the plane into left half-plane and right half-plane. A nonvertical line will divide the plane into the upper half plane and lower half plane. 

Calculation:

Given:

The pair of inequations are :

x - y ≥ 0 ....(1)

x + y < 5 ....(2)

• To draw the line of inequation (1), we need to find two points for the corresponding equation. Putting x = 0 in 1 gives y = 0. Similarly putting x = 1, gives y = 1. Hence the two points on the line are (0, 0) and (1, 1). Join the points as well as extended them to either side to get a decent outlook of the line.
• Similarly, a line for inequation (2) will be made.  
• The lines of their respective equations are shown in the figure below:
• For x - y ≥ 0, x will always be greater than or equal to y which is only possible if we choose the region below the y = x line or the lower half plane.
• Similarly for x + y < 5, the sum of x and y should always be lesser than 5 which is only possible if we take the region below x + y = 5 line or the lower half plane,

• The overlapped region or the feasible region under the blue and orange regions will represent the region containing the solution to the inequations which is shown in red in the figure below:

So, the correct answer is option 4.

Additional Information

How to draw the inequalities:

• It is important to know the technique to solve linear inequations. Suppose there are two inequations represented by,

x - 2y ≥ 5

x + 2y ≤ 6

• The lines are shown below in the figure:

• For the inequation, x - 2y ≥ 5, the points on the line x - 2y = 5 will only satisfy the equation. The tilted line divides the X-Y plane in an upper and lower half-plane,hence y will be the important parameter since its impact on the inequation will decide which half plane needs to be chosen to reach the solution. Since we need the value greater than 5 according to the inequation, we have to decrease the value of y and go down. Hence area under the line x - 2y = 5, the lower half plane as well as points on the line will contain the solution of inequation along with the line as shown in the figure below with blue shaded region.

• Similarly, for inequation x + 2y ≤ 6, the points on equation line x + 2y = 6 will represent will satisfy the equation. Again, the tilted line divide the X-Y plane in upper and lower half plane, hence y will be the important parameter. Since we need the value less than 6 according to the inequation, we have to decrease the value of y. Hence area under the line x + 2y = 6, the lower half plane as well as points on the line will contain the solution of inequation as shown in the figure below with orange shaded region.

• The shaded regions in the above two figures shows show the solution for individual inequations. The overall solution for both the inequations will be the overlapped area of the shaded regions of the two figures along with a portion of lines in the overlapped regions. The overlapped region is also called the feasible region.

•  It is important to note that the region of the solution is unbounded, that means it will extend when we go further left, right or downwards under the lines, but only small portion of it have been shown in the figure due to space constraints.

Explanation:  

Linear Programming is a mathematical technique for finding the optimal allocation of resources

• In a graphical solution of solving linear programming problems to convert inequalities into equations, it is essential to use them to be equations.
• linear programming is used for the optimization of limited resources when there is a number of alternate solutions possible of the problem.
• In this linear term is used for variables and it simply means that the relationship between different variable can be represented in form of a straight line.

Requirement of Linear Programming

• Objective Function: It is the main function; clearly identifiable and measurable in quantity.
• Constraints: These are limited resources within which we have to obtain the objective.

Explanation:

Zmax = 2000x + 3000y

Subjected to

3x + 2y ≤ 90   ⇒ \(\frac{x}{{30}} + \frac{y}{{45}} \le 1\)

x + 2y ≤ 100   ⇒ \(\frac{x}{{100}} + \frac{y}{{50}} \le 1\)

Zmax = 2000x + 3000y

Corner points satisfying both the constraints are A(30 , 0)  B(0 , 45)

ZA = 2000 × 30 + 3000 × 0 = 60,000

ZB = 2000 × 0 + 3000 × 45 = 1,35,000

So, the correct answer will be option 2.

Calculation:

Given:

• Objective function Z = 7x + 3y needs to be maximized subject to the constraints,

x, y ≥ 0 ....(1), x + 2y ≤ 5 ....(2) and x + y ≤ 4 ....(3). 

• The first thing needed to be done is to plot all the constraints on the X-Y axis and then find the feasible region if it exists. Plotting inequalities (1), (2), and (3) on the X-Y axis gives the following graph: 

• The red shaded area represents the feasible region. Now, it is needed to determine the corner points of the feasible region. It will be done one by one. We will refer to the figure to find each corner point.
• One of the corner points is the origin (0,0)
• One point is the intersection of line x + 2y = 5 with y-axis where x = 0. At x = 0, y is equal to 5/2. Hence the corner point is (0, 5/2)
• One point is the intersection of line x + y = 4 with an x-axis where y = 0. At y = 0, x is equal to 4. Hence the third corner point is (4, 0)
• Final point is the intersection point of lines x + y = 4 and x + 2y = 5. Solving the two equations. we get x = 3 and y = 1. The final corner point is (3, 1)
• Below is the table showing different corner points along with the value of the objective function at those points:

• Clearly, the value of Z is maximum at (4, 0).
• Hence x = 4, y = 0 is the only optimal solution to the problem where the optimal value of the function is 28.
• Hence this linear programming problem has only one solution.
• So, the correct answer is option 2.  

Additional Information

Corner point method:

•  As per the method, the coordinates of all corner points of the feasible region are determined and the value of the objective function at these points is computed since the optimal value of the objective function lies at one of the corner points as per the LP theory.
• The first step to find the solution of an LP problem is to determine the feasible region. It is obtained by drawing the X-Y coordinates and plotting all the constraints.
• The common region on the graph obtained that satisfies all the constraints will be the feasible region.
• If no feasible region is obtained via plotting the constraints, then the linear program is infeasible.
• All the possibilities are summarized below: 

Concept:

Let the quantity of food X be x kg and the quantity of food Y be y kg.

Go with the table data for the analysis.

Calculation:

Given:1 kg of food X costs Rs. 6 and 1 kg of food Y costs Rs. 10.

∴ the objective function is to minimize,

Z = 6x + 10y.

• Two kinds of food, X and Y are mixed in such a way that the mixture contains at least 10 units of vitamin A, 12 units of vitamin B, and 8 units of vitamin C. 

So, referring to the table,

• The constraint for vitamin A (At least 10 units of vitamin A),

⇒ x + 2y ≥ 10           ------ i)

• The constraint for vitamin B (At least 12 units of vitamin B),

⇒ 2x + 2y ≥ 12         -----ii)

• The constraint for vitamin C (At least 8 units of vitamin B),

⇒ 3x + y ≥ 8             -----iii)

• Non-negativity constraints,

⇒ x , y ≥ 0                  -----iv)

So, the correct answer is option 3.

Concept:

• Here, for solving this LPP problem, converting all inequality constraints to equality constraints.

x = 4, y = 6 3x + 2y = 18

• Now, we will be plotting these equations on the graph considering the inequalities of each constraint.

Calculation:

Given:

The shaded region will be the optimum region. Referring to the feasible region we can say that there will be a total 5 number of corner points in the feasible region.

Additional Information

• We can also find the value of objective function at all corner points

Z(0) = 0 + 0 = 0

Z(A) = Z(4, 0) = 6 × 4 + 0 = 24

Z(B) = Z(4, 3) = 6 × 4 + 10 × 3 = 54

Z(C) = Z(2, 6) = 2 × 6 + 6 × 10 = 72

Z(D) = Z(0, 6) = 0 + 6 × 10 = 60

• So, the maximum value of the objective function is 72.

Concept:

Corner point method:

•  As per the method, the coordinates of all corner points of the feasible region are determined and the value of the objective function at these points is computed since the optimal value of the objective function lies at one of the corner points as per the LP theory.
• The first step to find the solution of an LP problem is to determine the feasible region. It is obtained by drawing the X-Y coordinates and plotting all the constraints.
• The common region on the graph obtained that satisfies all the constraints will be the feasible region.
• If no feasible region is obtained via plotting the constraints, then the linear program is infeasible.
• All the possibilities are summarized below: 

Calculation:

Given:

Objective function Z = 7x + 3y needs to be maximized subject to the constraints:

x, y ≥ 0 ....(1), x + 2y ≥ 5 ....(2) and x + y ≥ 4 ....(3). 

• The first thing needed to be done is to plot all the constraints on the X-Y axis and then find the feasible region if it exists.
• Plotting inequalities (1), (2), and (3) on the X-Y axis gives the following graph:

• The red shaded area represents the feasible region. It may be noted that the feasible region is unbounded.

The number of corners points:

• Now, it is needed to determine the corner points of the feasible region.
• We will refer to the figure to find each corner point.
• One point is the intersection of line x + 2y = 5 with x-axis where y = 0. At y = 0, x is equal to 5. Hence the corner point is (5, 0)
• One point is the intersection of line x + y = 4 with the y-axis where x = 0. At x = 0, y is equal to 4. Hence another corner point is (0, 4)
• Final point is the intersection point of lines x + y = 4 and x + 2y = 5. Solving the two equations. we get x = 3 and y = 1. Hence the final corner point will be (3, 1)
• So, there will be three corner points  (5, 0), (0, 4), and (3, 1).
• So, the correct answer is option 3.

Additional Information

Examples for all possible results in LP using the Graphical method:

• The LP problem with no region satisfying all the constraints is shown below graphically:          

• Subsequently, a feasible and bounded region (closed) is shown in the figure below:

• The feasible and unbounded region is shown in the graph below. Here the value of y and x has no bound unlike the previous examples:

• When the feasible region is obtained, first the corners of the same are determined.
• Subsequently, the value of the objective function Z is calculated at all the points.
• The point where the objective function attains maximum or minimum value is the optimal solution of the problem.  
• If the feasible bounded region has been formed, then for this case, the objective function has both maximum and minimum value at a corner point of the given feasible region.
• However, if the region is feasible and unbounded, then things become a little complicated. Here also, the objective function will have a maximum and minimum value at a corner point of the feasible region. But to check whether Z has maximum or minimum values in this unbounded region case, we have to draw this region also.

Concept:

Corner point method:

•  As per the method, the coordinates of all corner points of the feasible region are determined and the value of the objective function at these points is computed since the optimal value of the objective function lies at one of the corner points as per the LP theory.
• The first step to find the solution of an LP problem is to determine the feasible region. It is obtained by drawing the X-Y coordinates and plotting all the constraints.
• The common region on the graph obtained that satisfies all the constraints will be the feasible region.
• If no feasible region is obtained via plotting the constraints, then the linear program is infeasible.
• All the possibilities are summarized below: 

Calculation:

Given:

• Objective function Z = 7x + y needs to be maximized subject to the constraints,

 x, y ≥ 0 ....(1), x - y ≥ 2 ....(2) and x - y ≤ -3 ....(3). 

• The first thing needed to be done is to plot all the constraints on the X-Y axis and then find the feasible region if it exists. Plotting inequalities (1), (2), and (3) on the X-Y axis gives the following graph:

• To draw the constraints, a line of respective equations has been formed by calculating the points on the line.
• For example, to draw in equation (2), points on line x - y = 2 are calculated by putting x = 0 and calculating y as - 2. Hence one point on the line is calculated.
• Similarly, putting y = 0 and calculating x as 2. Hence one other point on the line is calculated.
• Then the two points will be joined via a straight line and extended further on both sides to get a better perspective of the line.
• A similar process will be done for another constraint to form its line.
• Constraint (2) will solution will lie in the lower half plane to maintain the inequality while constraint (3) will lie in the upper half plane.
• Constraint (1) will play its role, as it can be seen that the orange area represents the area satisfying constraint (3) while y ≥ 0 and the blue area represents the area satisfying constraint (2) and x ≥ 0.
• However, since no area in the plane is satisfying constraints (2) and (3) due to the different half-planes of their solutions, there is no area on the graph which is satisfying all the constraints. Hence, this problem will have no solution, in other words, the problem is infeasible.     
• So, the correct answer is option 3.

Additional Information 

Examples for all possible results in LP using the Graphical method:

• The LP problem with no region satisfying all the constraints is shown below graphically:          

• Subsequently, a feasible and bounded region (closed) is shown in the figure below:

• The feasible and unbounded region is shown in the graph below. Here the value of y and x has no bound unlike the previous examples:

• When the feasible region is obtained, first the corners of the same are determined.
• Subsequently, the value of the objective function Z is calculated at all the points.
• The point where the objective function attains maximum or minimum value is the optimal solution of the problem.  
• If the feasible bounded region has been formed, then for this case, the objective function has both maximum and minimum value at a corner point of the given feasible region.
• However, if the region is feasible and unbounded, then things become a little complicated. Here also, the objective function will have a maximum and minimum value at a corner point of the feasible region. But to check whether Z has maximum or minimum values in this unbounded region case, we have to draw this region also.