Content Curator
Linear programming is a mathematical technique for increasing the efficiency and effectiveness of operations under certain constraints. The main purpose of linear programming is to optimize or minimize a numerical value. It is made up of linear functions with linear equations or inequalities restricting variables. Several linear functions are subjected to restrictions in the form of linear equations or linear inequalities. When a linear function is subjected to various constraints, linear function is minimized through linear programming. It is used to optimize the output of a function in the field of mathematics.
| Table of Contents |
Key Terms: integer linear programming, linear programming problem, integer programming, graphical method of linear programming, linear programming simplex method
Explanation to Linear Programming
[Click Here for Sample Questions]
The graph of any linear equation has two variables. To verify the equation, we need to plot coordinate points. Besides, in linear programming, we have two or more simultaneous linear equations, and then we need to find the range of the solutions from the given conditions. Let’s try to find the range from the given condition using the linear programming method.
For Example: The problem is to maximize the profit function z = 40x + 15y with respect to the constraints
x + 2y less than or equal to 100
x + 2y less than or equal to 70
x greater than or equal to 0, y
Solution Step-1: We can find that the above equation has x greater than or equal to 0, and y greater than or equal to 0. Hence, we need to focus only on the first quadrant.
Solution Step-2: First, we will try to plot the equation x + 2y = 100 from the given coordinate points (0, 50) and (100, 0). Then, let's plot the equation x + y = 70 using the coordinate point (70, 0) and (0, 70).
Linear Programming Graph 1
Plotting the two equations produced the above mentioned graph.
Now, we need to identify the feasible region of the graph which is nothing but the common region determined through all the given constraints. So, the feasible region is shown in the below graph
Linear Programming Graph 2
So, every point within the feasible region will satisfy all the given conditions of the linear programming. On the other hand, any point outside the given feasible region is an infeasible solution and will not satisfy all the conditions.
In addition, we know that the coordinates x and y will satisfy the given conditions of the problem. So, the graphical solutions can be used to optimize the solution of the given problem. Here, the optimal solution is nothing but the maximum and minimum value of the objective function. Further, we can find that there are more infinite points. So, there is a challenge in resolving the solutions to the given function z = 40x + 15y?
So, to find out the exact solution, we will follow the below given mathematical problem.
-
Theorem 1
Let’s consider “R” to be the feasible region of a linear programming problem. Then, let z = Ax + B be the objective function of the given problem. So, the optimal value of Z will appear at the corner point (vertex) of the feasible region. Hence, the optimal value (maxima or minima) Z exists along the x and y variables which are described by the linear inequalities.
-
Theorem 2
Let’s consider “R” to be the feasible region of a linear programming problem. Then, z = Ax + By is an objective function. So, if “R” is bounded, then the Z has both minimum and maximum value over R, and each of these occur at vertex points (corner).
Similarly, if the “R” is unbounded. Then, the maximum and minimum value of Z won’t exist at R. In some special cases, if it exists then it will appear at the corner (vertex) points of the R region.
So, from the above given linear programming problem, we have the following corner points (0, 0), (70, 0), (40, 30), and (0, 50).
Then, substituting the above coordinate point in the equation of objective function z = 40x + 15y, we get
For (0, 0) we get Z = 0
For (70, 0), we get Z = 2800
For (40, 30), we get Z = 2050
For (0, 50), we get Z = 750
Henceforth, the maximum value of Z appears at (70, 0) and the minimum value appears at (0, 0).
This is the required solution of the linear programming problem.
Characteristics of Linear Programming
[Click Here for Sample Questions]
- Decision Variables: This is the first step which will decide the output. It provides the ultimate solution to the problem.
- Constraints: The mathematical form in which limitations are expressed, regarding the resource.
- Data: They are placeholders for known numbers to make writing complex models easier. They are represented by upper-case letters.
- Objective Functions: In a mathematical problem, the objective function should be quantitatively described.
- Linearity: The function's relation between two or more variables must be linear. It signifies that the variable's degree is one.
- Finiteness: Input and output numbers should be finite and infinite. The best solution is not possible if the function contains infinite components.
- Non-negativity: The value of the variable should be either positive or 0. It can't be a negative number.
Solving Linear Programming Problems: Graphical Method
[Click Here for Sample Questions]
The two-variable linear programming is optimized using the graphical technique. If the problem contains two decision variables, the best way for finding the optimum solution is to use a graphical method. The set of inequalities is subjected to constraints in this manner.
The inequalities are then plotted on an XY plane. Once all of the inequalities have been shown on the XY graph, the intersecting region will assist in determining the feasible region. The feasible area will not only give the best solution, but it will also explain what values our model can take.
Steps:-
- Formulate the Linear programming problem
To begin, we must first identify the decision variables and determine the objective function to be maximized or reduced, which we must then describe as a linear function of decision variables. Then, in terms of the decision variables, identify the set of constraint conditions and describe them as linear inequalities or equations.
- Construct a graph and plot the constraint lines
The graph must have 'n' dimensions, with 'n' being the number of decision variables. This should give you a sense of how complicated this phase will get as the number of decision variables increases.
- Determine the valid side of each constraint line
This is used to identify the available space's domain. A basic way is to insert the origin (0,0) coordinates into the problem and see if the objective function has a physical solution or not. If yes, the valid side of the constraint lines is the one on which the origin is located. Otherwise, it's on the other side.
- Identify the feasible solution region
On the graph, the feasible solution region is the one that is satisfied by all of the constraints. It might also be considered as the intersection of each constraint line's valid regions. A suitable solution for our objective function might be found at any point in this area.
- Plot the objective function on the graph
Because we're working with linear equations, it'll obviously be a straight line. To avoid confusion, it must be drawn differently from the constraint lines. Choose the constant value in the objective function's equation at random to make it easily identifiable.
- Find the optimum point
An optimal point is always found at one of the feasible region corners. Make sure this ruler is oriented correctly in space. We simply need to know the direction of the objective function in a straight line. Begin sliding the graph towards the origin, starting from the far corner.
Find the point of contact of the ruler with the feasible region that is closest to the origin if the purpose is to minimize the objective function. This is the optimal function minimization point.
Find the point of contact of the ruler with the feasible region that is the farthest from the origin if the purpose is to maximize the objective function. This is the most efficient way to maximize the function.
- Calculate the coordinates of the optimum point
You'll need to find the coordinates of the optimum point once you've found it. Drawing two perpendicular lines from the point onto the coordinate axes and noting down the coordinates is a simple way to achieve this. To determine the optimized objective function, just plug the values of these parameters into the objective function's equation.
Things to Remember
- Linear programming is used to optimize the numerical value of a problem.
- Linear programming is widely used in quantitative decisions, business planning, and industrial engineering.
- Linear programming has characteristics such as decision variables, constraints, data, objective functions, finiteness, and non-negativity.
- Graphical methods are used to solve linear programming problems.
Sample Questions
Ques. Solve the following equation by linear programming’s graphical method. Minimize z = 200x+500y, the constraints were x + 2y ≥ 10, 3x + 4y ≤ 24, x ≥ 0, y ≥ 0. (3 Marks)
Ans. The objective of the function is z = 200x+500y, where the constraints are x + 2y ≥ 10, 3x + 4y ≤ 24, x ≥ 0, y ≥ 0
The solution for the equation is shown in the below graph:
The region between ABC is the feasible region defined through the constraints.
Therefore, the coordinates of the vertex points of the feasible region are A, B, C where the points can be defined as (0, 5), (4, 3), and (0, 6) respectively.
(0, 5) =>200 × 0 + 500 × 5 = 0 + 2500 = 2500
(4, 3) =>200 × 4 + 500 × 3 = 800 + 1500 = 2300 (minimum value)
(0, 6)=> 200 × 0 + 500 × 6 = 0 + 3000 = 3000
Substituting the above coordinate points in the given equation gives the minimum value of Z which is 2300 at the point (4, 3).
Ques. A calculator company produces a scientific calculator and a graphing calculator. Long-term projections indicate an expected demand of at least 100 scientific and 80 graphing calculators each day. Because of limitations on production capacity, no more than 200 scientific and 170 graphing calculators can be made daily. To satisfy a shipping contract, a total of at least 200 calculators must be shipped each day. (3 Marks)
Ans. How many of each type should be created daily to maximize net earnings if each scientific calculator sold generates a $2 loss but each graphing calculator generates a $5 profit?
x: number of scientific calculators produced
y: number of graphing calculators produced
Because they can't make calculators with negative values,we have two constraints: x > 0 and y > 0. But in this case, we can ignore these limits because x > 100 and y > 80 are already present. Maximums are also given in the exercise: x 200 and y 170. x + y > 200 is the minimum shipping requirement; in other words, y > –x + 200. Our optimization equation for the profit relation will be P = –2x + 5y. As a result, the overall system is:
P = –2x + 5y, the equation when exposed to constraints, we get:
100 < x < 200
80 < y < 170
y > –x + 200
The feasibility region of the graphs is shown below
Ques. You'll have to get some filing cabinets. Cabinet X costs $10 per unit, takes up six square feet of floor space, and holds eight cubic feet of files, as you already know. Cabinet Y costs $20 per unit and holds twelve cubic feet of files. It takes up eight square feet of floor space. You have been allocated $140 to spend on this transaction, albeit you are not required to do so. Cabinets can only take up 72 square feet in the office. In order to optimize storage volume, how many of each model should you purchase? (4 Marks)
Ans. The question asks how many cabinets I need to buy, thus these are the variables we'll use:
x: number of model X cabinets purchased
y: number of model Y cabinets purchased
Naturally, x and y are both greater than zero. Costs and floor space (each unit's "footprint") must be considered while optimizing storage capacity, therefore costs and floor space will be our restrictions, and volume will be our optimization equation.
cost: 10x + 20y < 140, or y < –( 1/2 )x + 7
space: 6x + 8y < 72, or y < –( 3/4 )x + 9
volume: V = 8x + 12y
This system along with the first constraints shown below in the graph:
If you buy eight of model X and three of model Y and test the corner points at (8, 3), (0, 7), and (12, 0), you should get a maximum volume of 100 cubic feet.
Ques. Maximize the following equation Z = 3x + 4y. (3 Marks)
Ans. From the above equation, the feasible region can be determined by the constraints such as x + y ≤ 4, x ≥ 0, y ≥ 0, where the feasible region can be seen from the below graph:
Then, the points O, A, and B are the vertex points of the shaded region. The points are (0, 0), (4, 0), (0, 4). Hence the maximum value of the Z is equal to 16 at point B (0, 4).
Ques. Minimize the given following equation Z = −3x + 4y, where the subjective constraints are x + 2y ≤ 8, 3x + 2y ≤ 12, x ≥ 0, y ≥ 0. (3 Marks)
Ans. Subject to the above given constraints, the feasible region is shown in the below graph:
Therefore, the vertex points of the shaded region are O (0, 0), A(4,0), B(2, 3), C(0, 4). Then, solving the given equation using the vertex (corner) points gives -12 as minimum value.
Hence, the minimum value of Z is equal to -12 at the point of A (4, 0).
Ques. Maximize the following equation Z = 5x + 3y with constraints 3x + 5y ≤ 15, 5x + 2y ≤ 10, x ≥ 0, y ≥ 0. (3 Marks)
Ans. The feasible region of the above equation is shown below:
Then, solving the equation using the corner points O (0, 0), A (2, 0), B (0, 3) and C (20 / 19, 45 / 19) identified from the feasible region. Then, the maximum value of the region is z = 235/19 at the respective point (2./19, 45/19).
Ques. Minimize the following equation Z = 3x + 5y through the given constraints x + 3y ≥ 3, x + y ≥ 2, x ≥ 0, y ≥ 0. (3 Marks)
Ans. The feasible region of the given equation is shown below:
The feasible region is unbounded here, so the coroner points are A (3, 0), B (3 / 2, 1 / 2) and C (0, 2).
Solving the equation suing the corner points gives the minimum value of Z = 7 at the appropriate point B (3 / 2, 1 / 2)
Ques. Maximize the following equation Z = 3x + 2y through the given constraints x + 2y ≤ 10, 3x + y ≤ 15, x ≥ 0, y ≥ 0. (3 Marks)
Ans. So, the feasible region of the found by the given constraints is shown below:
The corner points of the feasible region are A (5, 0), B (4, 3), C (0, 5) and D (0, 0).
Then, solving for the equation using the corner points gives Z = 18 at the point (4,3).
Ques. Minimize the following equation Z = x + 2y through the given constraint 2x + y ≥ 3, x + 2y ≥ 6, x ≥ 0, y ≥ 0. (3 Marks)
Ans. The feasible region of the equation identified through the constraint is shown below:
Then, the corner points are A (6, 0) and B (0, 3). Finally, solving the equation for the determined corner points gives Z = 6.
Ques. Maximize the following equation Z = x + y through the given constraints x-y ≤ -1, -x+y ≤0, x ≥ 0, y ≥ 0. (3 Marks)
Ans. The region identified from the equation is shown below:
In the above graph, we can find that there is no feasible region hence Z has no maximum value.
Read Also:
Comments