- Last updated
- Save as PDF
- Page ID
- 40134
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Learning Objectives
In this section, you will learn to:
- Recognize the typical form of a linear programming problem.
- Formulate maximization linear programming problems.
- Graph feasible regions for maximization linear programming problems.
- Determine optimal solutions for maximization linear programming problems.
Prerequisite Skills
Before you get started, take this prerequisite quiz.
1. Graph this system of inequalities:
\(\left\{\begin{array} {l} 2x+4y\leq 10\\3x−5y<15\end{array}\right.\)
- Click here to check your answer
-
If you missed this problem, review Section 4.2. (Note that this will open in a new window.)
2. Graph this system of inequalities:
\(\left\{\begin{array} {l} y\leq 2x+1\\y\leq-3x+6\\x\geq0\\y\geq0\end{array}\right.\)
- Click here to check your answer
-
(The solution is in the center region.)
If you missed this problem, review Section 4.2. (Note that this will open in a new window.)
Application problems in business, economics, and social and life sciences often ask us to make decisions on the basis of certain conditions. The conditions or constraints often take the form of inequalities. In this section, we will begin to formulate, analyze, and solve such problems, at a simple level, to understand the many components of such a problem.
A typical linear programming problem consists of finding an extreme value of a linear function subject to certain constraints. We are either trying to maximize or minimize the value of this linear function, such as to maximize profit or revenue, or to minimize cost. That is why these linear programming problems are classified as maximization or minimization problems, or just optimization problems. The function we are trying to optimize is called an objective function, and the conditions that must be satisfied are called constraints.
When we graph all constraints, the area of the graph that satisfies all constraints is called the feasible region. The Fundamental Theorem of Linear Programming states that the maximum (or minimum) value of the objective function always takes place at the vertices of the feasible region. We call these vertices critical points. These are found using any methods from Chapter 3 as we are looking for the points where any two of the boundary lines intersect.
A typical example is to maximize profit from producing several products, subject to limitations on materials or resources needed for producing these items; the problem requires us to determine the amount of each item produced. Another type of problem involves scheduling; we need to determine how much time to devote to each of several activities in order to maximize income from (or minimize cost of) these activities, subject to limitations on time and other resources available for each activity.
In this chapter, we will work with problems that involve only two variables, and therefore, can be solved by graphing. Here are the steps we'll follow:
The Maximization Linear Programming Problems
- Define the unknowns.
- Write the objective function that needs to be maximized.
- Write the constraints.
- For the standard maximization linear programming problems, constraints are of the form: \(ax + by ≤ c\)
- Since the variables are non-negative, we include the constraints: \(x ≥ 0\); \(y ≥ 0\).
- Graph the constraints.
- Shade the feasible region.
- Find the corner points.
- Find the value of the objective function at each corner point to determine the corner point that gives the maximum value.
Example \(\PageIndex{1}\)
Niki holds two part-time jobs, Job I and Job II. She never wants to work more than a total of 12 hours a week. She has determined that for every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation.
If Niki makes $40 an hour at Job I, and $30 an hour at Job II, how many hours should she work per week at each job to maximize her income?
Solution
We start by defining our unknowns.
- Let the number of hours per week Niki will work at Job I = \(x\).
- Let the number of hours per week Niki will work at Job II = \(y\).
Now we write the objective function. Since Niki gets paid $40 an hour at Job I, and $30 an hour at Job II, her total income I is given by the following equation.
\[I = 40x + 30y \nonumber\]
Our next task is to find the constraints. The second sentence in the problem states, "She never wants to work more than a total of 12 hours a week." This translates into the following constraint:
\[x + y \leq 12 \nonumber \]
The third sentence states, "For every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation." The translation follows.
\[2x + y \leq 16 \nonumber\]
The fact that \(x\) and \(y\) can never be negative is represented by the following two constraints:
\[x \geq 0 \text{, and } y \geq 0 \nonumber.\]
Well, good news! We have formulated the problem. We restate it as
\[\begin{array}{ll}
\textbf { Maximize } & \mathrm{I}=40 \mathrm{x}+30 \mathrm{y} \\
\textbf { Subject to: } & \mathrm{x}+\mathrm{y} \leq 12 \\
& 2 \mathrm{x}+\mathrm{y} \leq 16 \\
& \mathrm{x} \geq 0 ; \mathrm{y} \geq 0
\end{array}\nonumber\]
In order to solve the problem, we graph the constraints and shade the region that satisfies all the inequality constraints.
Any appropriate method can be used to graph the lines for the constraints. However often the easiest method is to graph the line by plotting the x-intercept and y-intercept.
The line for a constraint will divide the plane into two region, one of which satisfies the inequality part of the constraint. A test point is used to determine which portion of the plane to shade to satisfy the inequality. Any point on the plane that is not on the line can be used as a test point.
- If the test point satisfies the inequality, then the region of the plane that satisfies the inequality is the region that contains the test point.
- If the test point does not satisfy the inequality, then the region that satisfies the inequality lies on the opposite side of the line from the test point.
In the graph below, after the lines representing the constraints were graphed, the point (0,0) was used as a test point to determine that
- (0,0) satisfies the constraint \(x + y \leq 12\) because \(0 + 0 < 12\)
- (0,0) satisfies the constraint \(2x + y \leq 16\) because \(2(0) + 0 < 16\)
Therefore, in this example, we shade the region that is below and to the left of both constraint lines, but also above the x axis and to the right of the y axis, in order to further satisfy the constraints \(x \geq 0\) and \(y \geq 0\).
The shaded region where all conditions are satisfied is the feasible region or the feasible polygon.
The Fundamental Theorem of Linear Programming states that the maximum (or minimum) value of the objective function always takes place at the vertices of the feasible region.
Therefore, we will identify all the vertices (corner points) of the feasible region. These are found using any methods from Chapter 3 as we are looking for the points where any two of the boundary lines intersect.They are listed as (0, 0), (0, 12), (4, 8), (8, 0). To maximize Niki's income, we will substitute these points in the objective function to see which point gives us the highest income per week. We list the results below.
| Critical Points | Income |
|---|---|
| (0, 0) | 40(0) + 30(0) = $0 |
| (0, 12) | 40(0) + 30(12) = $360 |
| (4, 8) | 40(4) + 30(8) = $400 |
| (8, 0) | 40(8) + 30(0) = $320 |
Clearly, the point (4, 8) gives the most profit: $400.
Therefore, we conclude that Niki should work 4 hours at Job I, and 8 hours at Job II.
Example \(\PageIndex{2}\)
A factory manufactures two types of gadgets, regular and premium. Each gadget requires the use of two operations, assembly and finishing, and there are at most 12 hours available for each operation. A regular gadget requires 1 hour of assembly and 2 hours of finishing, while a premium gadget needs 2 hours of assembly and 1 hour of finishing. Due to other restrictions, the company can make at most 7 gadgets a day. If a profit of $20 is realized for each regular gadget and $30 for a premium gadget, how many of each should be manufactured to maximize profit?
Solution
We define our unknowns:
- Let the number of regular gadgets manufactured each day = \(x\).
- and the number of premium gadgets manufactured each day = \(y\).
The objective function is
\[P = 20x + 30y \nonumber\]
We now write the constraints. The fourth sentence states that the company can make at most 7 gadgets a day. This translates as
\[x + y \leq 7 \nonumber\]
Since the regular gadget requires one hour of assembly and the premium gadget requires two hours of assembly, and there are at most 12 hours available for this operation, we get
\[x + 2y \leq 12 \nonumber\]
Similarly, the regular gadget requires two hours of finishing and the premium gadget one hour. Again, there are at most 12 hours available for finishing. This gives us the following constraint.
\[2x + y \leq 12 \nonumber \]
The fact that \(x\) and \(y\) can never be negative is represented by the following two constraints:
\[x \geq 0 \text{, and } y \geq 0 \nonumber.\]
We have formulated the problem as follows:
\[\begin{array}{ll}
\textbf { Maximize } & \mathrm{P}=20 \mathrm{x}+30 \mathrm{y} \\
\textbf { Subject to: } & \mathrm{x}+\mathrm{y} \leq 7 \\
& \mathrm{x}+2\mathrm{y} \leq 12 \\
& 2\mathrm{x} +\mathrm{y} \leq 12 \\
& \mathrm{x} \geq 0 ; \mathrm{y} \geq 0
\end{array} \nonumber\]
In order to solve the problem, we next graph the constraints and feasible region.
Again, we have shaded the feasible region, where all constraints are satisfied.
Since the extreme value of the objective function always takes place at the vertices of the feasible region, we identify all the critical points. They are listed as (0, 0), (0, 6), (2, 5), (5, 2), and (6, 0). To maximize profit, we will substitute these points in the objective function to see which point gives us the maximum profit each day. The results are listed below.
| Critical Point | Income |
|---|---|
| (0, 0) | 20(0) + 30(0) = $0 |
(0, 6) | 20(0) + 30(6) = $180 |
(2, 5) | 20(2) + 30(5) = $190 |
(5, 2) | 20(5) + 30(2) = $160 |
| (6,0) | 20(6) + 30(0) = $120 |
The point (2, 5) gives the most profit, and that profit is $190.
Therefore, we conclude that we should manufacture 2 regular gadgets and 5 premium gadgets daily to obtain the maximum profit of $190.
So far we have focused on “standard maximization problems” in which
- The objective function is to be maximized
- All constraints are of the form \(ax + by \leq c\)
- All variables are constrained to by non-negative (\(x ≥ 0\), \(y ≥ 0\))
We will next consider an example where that is not the case. Our next problem is said to have “mixed constraints”, since some of the inequality constraints are of the form \(ax + by ≤ c\) and some are of the form \(ax + by ≥ c\). The non-negativity constraints are still an important requirement in any linear program.
Example \(\PageIndex{3}\)
Solve the following maximization problem graphically.
\[\begin{array}{ll}
\textbf { Maximize } & \mathrm{P}=10 \mathrm{x}+15 \mathrm{y} \\
\textbf { Subject to: } & \mathrm{x}+\mathrm{y} \geq 1 \\
& \mathrm{x}+2\mathrm{y} \leq 6 \\
& 2\mathrm{x} +\mathrm{y} \leq 6 \\
& \mathrm{x} \geq 0 ; \mathrm{y} \geq 0
\end{array} \nonumber\]
Solution
The graph is shown below.
The five critical points are listed in the above figure. The reader should observe that the first constraint \(x + y ≥ 1\) requires that the feasible region must be bounded below by the line \(x + y =1\); the test point (0,0) does not satisfy \(x + y ≥ 1\), so we shade the region on the opposite side of the line from test point (0,0).
| Critical point | Income |
|---|---|
| (1, 0) | 10(1) + 15(0) = $10 |
| (3, 0) | 10(3) + 15(0) = $30 |
| (2, 2) | 10(2) + 15(2) = $50 |
| (0, 3) | 10(0) + 15(3) = $45 |
| (0,1) | 10(0) + 15(1) = $15 |
Clearly, the point (2, 2) maximizes the objective function to a maximum value of 50.
It is important to observe that that if the point (0,0) lies on the line for a constraint, then (0,0) could not be used as a test point. We would need to select any other point we want that does not lie on the line to use as a test point in that situation.
Finally, we address an important question. Is it possible to determine the point that gives the maximum value without calculating the value at each critical point?
The answer is yes.
We summarize:
The Maximization Linear Programming Problems
- Define the unknowns.
- Write the objective function that needs to be maximized.
- Write the constraints.
- For the standard maximization linear programming problems, constraints are of the form: \(ax + by ≤ c\)
- Since the variables are non-negative, we include the constraints: \(x ≥ 0\); \(y ≥ 0\).
- Graph the constraints.
- Shade the feasible region.
- Find the corner points.
- Find the value of the objective function at each corner point to determine the corner point that gives the maximum value.
FAQs
How do you solve maximization problems in linear programming? ›
- Write the objective function.
- Write the constraints. ...
- Graph the constraints.
- Shade the feasibility region.
- Find the corner points.
- Determine the corner point that gives the maximum value.
Abstract Linear programming is an operation research technique which is widely used in finding solutions to managerial decision making problems of allocating scarce resources in order to maximize profit and minimize cost. This paper deals with the application of the optimization principle .
What is the application of linear programming in daily life maximization? ›Linear programming is heavily used in microeconomics and company management, such as planning, production, transportation, technology and other issues, either to maximize the income or minimize the costs of a production scheme. In the real world the problem is to find the maximum profit for a certain production.
How do you solve linear programming with 4 constraints? ›- Step 1 - Identify the decision variables. ...
- Step 2 - Write the objective function. ...
- Step 3 - Identify Set of Constraints. ...
- Step 4 - Choose the method for solving the linear programming problem. ...
- Step 5 - Construct the graph. ...
- Step 6 - Identify the feasible region.
Updated On: 27-06-2022
An L.P.P. has a unique solution. If an L.P.P. has two optimal solutions, then it has infinitely many optimal solutions.
- Set up the problem. ...
- Convert the inequalities into equations. ...
- Construct the initial simplex tableau. ...
- The most negative entry in the bottom row identifies the pivot column.
- Calculate the quotients. ...
- Perform pivoting to make all other entries in this column zero.
If a linear programming problem can be optimized, an optimal value will occur at one of the vertices of the region representing the set of feasible solutions. For example, the maximum or minimum value of f(x,y)=ax+by+c over the set of feasible solutions graphed occurs at point A,B,C,D,E or F .
How do you find the minimum and maximum value in linear programming? ›The maximum and minimum values are found at the vertices, or if the vertices are not on whole numbers, then at the points inside the polygon which are closest to the vertices.
What is profit maximization with example? ›In other words, the profit-maximizing quantity and price can be determined by setting marginal revenue equal to zero, which occurs at the maximal level of output. Marginal revenue equals zero when the total revenue curve has reached its maximum value. An example would be a scheduled airline flight.
What are the application of linear programming in real life examples? ›LPP applications may include production scheduling, inventory policies, investment portfolio, allocation of advertising budget, construction of warehouses, etc.
What are examples of real life application of linear equations? ›
Applications of Linear Equations in Real life
It is used to calculate speed, distance and time of a moving object. Geometry related problems can be solved. It is used to calculate money and percentage related problems. Work, time and wages problems can be solved.
The linear programming method is used in modern computer programs for calculating various economic models. It is proposed to use graphical or vector methods for solving optimization problems when constructing a mathematical model after analyzing the boiler room operation data.
How do you find the consistency of 4 linear equations? ›- a 1 a 2 = 1 2.
- b 1 b 2 = 1 2.
- c 1 c 2 = 1 2.
Step 1: Find the values of f at the critical numbers of f in (a,b). Step 2: Find the values of f at the endpoints of the interval. Step 3: The largest of the values from step 1 and step 2 is the absolute maximum value; the smallest of the values from step 1 and step 2 is the absolute minimum value.
What is the maximum number of solutions an equation can have? ›Maximum number of solutions quadratic formula can give is two.
Can an LPP may have more than one optimal solution? ›Alternate or multiple optimal solutions occurs in LLP problem when the objective function line is parallel to one of the binding constraint lines or objective function line and constraint line have the same slope. Some special cases of LPP problem.
How many solutions can be found when solving a linear system? ›A system of linear equations usually has a single solution, but sometimes it can have no solution (parallel lines) or infinite solutions (same line).
How do you know if a problem is a standard maximization problem? ›A linear programming (LP) problem is called a standard maximization problem if: We are to find the maximum (not minimum) value of the objective function. All the decision variables x1, x2, ..., xn are constrained to be non-negative. All further constraints have the form bx1 + bx2 + ..
Which solution is a feasible solution for a maximization problem? ›An optimal solution is a feasible solution that results in the largest possible objective function value when maximizing (or smallest when minimizing).
What are the five steps in solving optimization problems? ›Five Steps to Solve Optimization Problems
It is: visualize the problem, define the problem, write an equation for it, find the minimum or maximum for the problem (usually the derivatives or end-points) and answer the question.
How do you know if a function has a maximum? ›
Answer: To determine whether a function has a minimum or maximum value, we have to double differentiate the function and check whether it has a negative or a positive value in the given domain.
What is the condition for maximum? ›To find whether f has a maximum or minimum at a critical point you must look to the quadratic approximation (or if necessary to the first higher approximation at which f deviates from flatness) to f. If its second derivative is positive then, like x2, f has a minimum at q, and if it is negative f has a maximum.
What is the 100% rule in linear programming? ›Under this rule, any combination of changes can occur without a change in the solution as long as the total percentage deviation from the coordinate extremes does not exceed 100%.
How do you tell if a function has a minimum or maximum value? ›We'll determine whether it is a maximum or minimum value by looking at the a value or checking the sign of the second derivative. A positive value means the parabola opens up, so it has a minimum value. A negative value means the parabola opens down, so it has a maximum value.
How do you determine the minimum or maximum value? ›The maximum value of a function is the function value at its highest point. This can be found by taking the y-coordinate of the highest point. Similarly, the minimum value of a function is the function value at its lowest point. This can be found by taking the y-coordinate of the lowest point.
How do you tell if a function has a local minimum or maximum value? ›The graph of a function y = f(x) has a local maximum at the point where the graph changes from increasing to decreasing. At this point the tangent has zero slope. The graph has a local minimum at the point where the graph changes from decreasing to increasing.
What is the formula for maximization? ›The profit maximization formula depends on profit = Total revenue – Total cost. Therefore, a firm maximizes profit when MR = MC, which is the first order, and the second order depends on the first order.
How do you calculate maximum profit? ›To calculate maximum profit, subtract your expenses from your product supply and potential revenue. Then, alter the prices and compare different price points to see what may bring you the most profit.
In what situation we can use linear programming problem? ›The linear programming problems can be used to get the optimal solution for the following scenarios, such as manufacturing problems, diet problems, transportation problems, allocation problems and so on.
How do you solve linear programming word problems? ›- Step 1 - Identify the decision variables. x = number of lamps L1 ...
- Step 2 - Write the objective function. ...
- Step 3 - Write the set of constraints. ...
- Step 4 - Choose the method to solve the problem. ...
- Step 5 - Construct the graph. ...
- Step 6 - Find the feasibility region of the graph. ...
- Step 7 - Find the optimum point.
What are the 5 examples of linear equation? ›
Some of the examples of linear equations are 2x – 3 = 0, 2y = 8, m + 1 = 0, x/2 = 3, x + y = 2, 3x – y + z = 3.
How do you solve linear applications? ›- Step 1: Read the problem several times, identify the key words and phrases, and organize the given information.
- Step 2: Identify the variables by assigning a letter or expression to the unknown quantities.
- Step 3: Translate and set up an algebraic equation that models the problem.
Answer: Some types of Linear Programming (LPs) are as follows: Solving Linear Programs (LPs) by Graphical Method. Solve Linear Program (LPs) Using R. Solve Linear Program (LPs) using Open Solver.
What are the applications of systems of linear equations? ›- Finding unknown age.
- Finding unknown angles in geometry.
- For calculation of speed, distance or time.
- Problems based on force and pressure.
- Decision Variables.
- Constraints.
- Data.
- Objective Functions.
You can use simultaneous method to solve 4 equations with 4 unknowns. Its really simple method. You just need to take one equation and substitute the values of the other variables form the remaining 3 equations into the first equation.
How many equations are needed to solve for 4 unknowns? ›If you have four unknowns, you need four independent equations to find a unique solution.
Is it possible to solve 3 equations with 4 variables? ›Solving a system of 3 equations and 4 variables using matrix row-echelon form. Sal solves a linear system with 3 equations and 4 variables by representing it with an augmented matrix and bringing the matrix to reduced row-echelon form.
How do you determine if a linear system is consistent and inconsistent? ›Definition: A system of linear equations is said to be consistent if it has either one solution or infinitely many solutions. A system of linear equations is said to be inconsistent if it has no solution. system can be recorded compactly in a rectangular array called a matrix.
How do you tell if a linear equation is consistent or inconsistent? ›A system of equations is consistent if it has at least one solution. A system is inconsistent if it has no solution. In a system of two equations in two variables, the equations are dependent if one equation is a multiple of the other. Dependent systems have an infinite number of solutions – every point is a solution.
How the problem of minimization can be solved by linear programming? ›
Minimization linear programming problems are solved in much the same way as the maximization problems. For the standard minimization linear program, the constraints are of the form ax+by≥c, as opposed to the form ax+by≤c for the standard maximization problem.
What is maximum problem linear programming? ›...
Example.
| Maximize | p = 2x − 3y + z | Objective function |
|---|---|---|
| subject to | x + y + z ≤ 10 4x − 3y + z ≤ 3 2x + y − z ≤ 10 x ≥ 0, y ≥ 0, z ≥ 0 | Constraints |
We determine the optimal solution to the LP by plotting (180x + 160y) = K (K constant) for varying K values (iso-profit lines). One such line (180x + 160y = 180) is shown dotted on the diagram.
How solve linear programming problem maximize and minimize using simplex method? ›- Set up the problem.
- Write a matrix whose rows represent each constraint with the objective function as its bottom row.
- Write the transpose of this matrix by interchanging the rows and columns.
- Now write the dual problem associated with the transpose.
In minimization problems, the variables are the constraints and the goal is to find a solution that satisfies all of the constraints as closely as possible. In maximization problems, the variables are the constraints and the goal is to find a solution that maximizes or maximize some criterion.
Which is the problem of maximizing or minimizing a linear function? ›Linear programming (LP) or Linear Optimisation may be defined as the problem of maximizing or minimizing a linear function that is subjected to linear constraints.
What is maximization vs minimization? ›maximizing: means finding the largest (or maximum) value the quantity can be. minimizing: means finding the smallest (or minimum) value the quantity can be.
How do you know if there is a min or max value linear programming? ›Whichever corner point yields the largest value for the objective function is the maximum and whichever corner point yields the smallest value for the objective function is the minimum.
What are the 3 requirements in solving linear programming? ›Standard form is the baseline format for all linear programs before solving for the optimal solution and has three requirements: (1) must be a maximization problem, (2) all linear constraints must be in a less-than-or-equal-to inequality, (3) all variables are non-negative.
How do you know if a solution is feasible in linear programming? ›Definition 1 If x satisfies Ax = b, x ≥ 0, then x is feasible. Definition 2 A linear program (LP) is feasible if there exists a feasible solution, otherwise it is said to be infeasible. Definition 3 An optimal solution x∗ is a feasible solution s.t. cT x∗ = min{cT x : Ax = b, x ≥ 0}.
What is the difference between feasible and optimal solution? ›
A feasible solution satisfies all the problem's constraints. An optimal solution is a feasible solution that results in the largest possible objective function value when maximizing (or smallest when minimizing).
What is the optimal condition for maximization problem in simplex method? ›Optimality condition: The entering variable in a maximization (minimization) problem is the non-basic variable having the most negative (positive) coefficient in the Z-row. The optimum is reached at the iteration where all the Z-row coefficient of the non-basic variables are non-negative (non-positive).