- last update
- Save as PDF
- Page ID
- 40136
\( \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{spa n}}\)\( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
learning goals
In this section you will learn:
- Formulate minimization problems of linear programming.
- Draw viable regions to minimize linear programming problems.
- Determine optimal solutions to linear programming minimization problems.
Required Skills
Before you begin, take this prerequisite quiz.
1. Graphically represent this system of inequalities:
\(\left\{\begin{array} {l} x+3y\geq6\\y>\dfrac{1}{3}x-1\end{array}\right.\)
- Click here to check your answer
-
If you missed this problem,see section 4.2. (Note that this will open another textbook in a new window.)
2. Graphically represent this system of inequalities:
\(\left\{\begin{array} {l} y\geq 2x+1\\y\geq-3x+6\\x\geq0\\y\geq0\end{array}\right.\)
- Click here to check your answer
- (Video) 4.4 Optimization Problems
(The solution is in the upper middle section.)
If you missed this problem,see section 4.2. (Note that this will open another textbook in a new window.)
Linear programming minimization problems are solved in the same way as the maximization problems.
For thestandard linear minimization program, the constraints have the form \(ax + by ≥ c\), in contrast to the form \(ax + by ≤ c\) for the standard maximization problem. As a result, the feasible solution extends indefinitely to the upper right of the first quadrant and is indefinite. However, this does not matter, because to minimize the objective function, the line associated with the objective function is shifted toward the origin, and the critical point that minimizes the function is closest to the origin.
However, one should be aware that in the case of an unrestricted allowable range, an optimal solution may not exist.
Minimization problems in linear programming
- Define the unknowns.
- Write down the objective function to be minimized.
- Write the restrictions.
- For standard linear programming minimization problems, constraints are of the form: \(ax + by ≥ c\)
- Since the variables are not negative, enclose the constraints: \(x ≥ 0\); \(y ≥ 0\).
- Graphically represent the constraints.
- Shade the allowed area.
- Find the vertices.
- Find the value of the objective function at each vertex to determine the vertex that gives the minimum value.
Example \(\PageIndex{1}\)
At a university, Professor Symons wants to hire two people, John and Mary, to grade papers for his courses. John is a graduate student and can grade 20 papers an hour; John makes $15 an hour grading work. Mary is a postdoc and can grade 30 papers an hour; Mary makes $25 an hour grading work. Everyone must be employed at least one hour a week to justify their employment.
If Prof. Symons has at least 110 papers to grade each week, how many hours per week should he employ each person to minimize costs?
Solution
We define the unknowns as follows:
Let the number of hours per week that John is employed = \(x\).
and the number of hours per week Mary is employed = \(y\).
The objective function is
\[C = 15x + 25y \nonumber \]
The fact that everyone has to work at least one hour a week leads to the following two restrictions:
\[\begin{array}{l}
x \geq 1 \\
y\geq 1
\end{array} \number \]
Since John can grade 20 papers per hour and Mary 30 papers per hour, and at least 110 papers to grade per week, we get
\[20x + 30y ≥ 110 \nonumber\]
We get the fact that \(x\) and \(y\) are nonnegative
\[x ≥ 0 \text{, and } y ≥ 0. \nonumber\]
The problem was formulated as follows.
\[\begin{array}{ll}
\textbf { Minimize } & \mathrm{C}=15 \mathrm{x}+25\mathrm{y}\\
\textbf { Subject: } & \mathrm{x}\geq1\\
&\mathrm{y}\geq1\\
&20\math{x}+30\math{y}\geq110\\
& \mathrm{x} \geq 0 ; \mathrm{y}\geq 0
\end{array} \nonumber\]
To solve the problem, let's graph the constraints as follows:
Again, we have shaded the allowable region where all the constraints are met.
Using the test point (0,0), which does not lie on any of the constraints, we observe that (0,0)notsatisfy one of the constraints \(x ≥ 1\), \(y ≥ 1\), \(20x + 30y ≥ 110\). Thus, all shading for the allowable range is on the opposite side of the constraint lines from point (0,0).
Alternatively, we could use the test point (4,6), which also does not lie on any of the constraint lines. We would find that (4.6)tutsatisfy all inequality conditions. Consequently, all shading for the allowable range is on the same side of the constraint lines as point (4,6).
Since the extremum of the objective function always occurs at the corners of the allowed range, we identify the two critical points (1, 3) and (4, 1). To minimize the cost, we substitute these points in the objective function to see which point gives us the minimum cost each week. The results are listed below.
| Critical points | income |
| (1, 3) | 15(1) + 25(3) = 90 $ |
| (4, 1) | 15(4) + 25(1) = $85 |
The point (4, 1) gives the lowest cost, and that cost is $85. Therefore, we conclude that to minimize grading costs, Professor Symons should employ John 4 hours per week and Mary 1 hour per week at a cost of $85 per week.
Example \(\PageIndex{2}\)
Professor Hamer eats a low-cholesterol diet. At lunch in the college cafeteria, he always chooses between two dishes: pasta or tofu. The table below lists the amount of protein, carbohydrates, and vitamins each meal provides, along with the amount of cholesterol it tries to minimize. Mr. Hamer needs at least 200 grams of protein, 960 grams of carbohydrates and 40 grams of vitamins for lunch every month. During this period, how many days should he eat the pasta meal and how many days the tofu meal in order to get the adequate amount of protein, carbohydrates, and vitamins while minimizing his cholesterol intake?
| PASTA | TOFU | |
| WHITE | 8 gr | 16g |
| carbohydrates | 60g | 40g |
| VITAMIN C | 2g | 2g |
| CHOLESTEROL | 60mg | 50mg |
Solution
We define the unknowns as follows.
Be the number of days that Mr. Hamer eats pasta = \(x\).
and the number of days Mr. Hamer eats tofu = \(y\).
Since he's trying to minimize his cholesterol intake, our objective function represents the total amount of cholesterol C provided by both meals.
\[C = 60x + 50y \nonumber \]
The limitation associated with the total amount of protein provided by both meals is
\[8x + 16y ≥ 200 \number \]
Similarly, the two limitations associated with total carbs and vitamins are preserved, and they are
\[\begin{array}{l}
60 x + 40 y \geq 960 \\
2 x + 2 y = 40
\end{array} \nonumber\]
The constraints that say x and y are not negative are
\[x ≥ 0 \text{, and } y ≥ 0 \nonumber.\]
We summarize all the information as follows:
\[\begin{array}{ll}
\textbf { Minimize } & \mathrm{C}=60 \mathrm{x}+50 \mathrm{y}\\
\textbf { Subject to: } & 8 \math{x}+16 \math{y}\geq200\\
&60\math{x}+40\math{y}\geq960\\
&2\math{x}+2\math{y}\geq40\\
& \mathrm{x} \geq 0 ; \mathrm{y}\geq 0
\end{array} \nonumber\]
To solve the problem, let's graph the constraints and shade the allowable range.
We have shaded the unconstrained legal region where all constraints are satisfied.
To minimize the objective function, we find the corners of the feasible region. These vertices are (0, 24), (8, 12), (15, 5), and (25, 0). To minimize cholesterol, we substitute these points in the objective function to see which point gives us the smallest value. The results are listed below.
| Critical points | income |
| (0, 24) | 60(0) + 50(24) = 1200 |
| (8, 12) | 60(8) + 50(12) = 1080 |
| (15, 5) | 60(15) + 50(5) = 1150 |
| (25, 0) | 60(25) + 50(0) = 1500 |
The point (8, 12) indicates the lowest cholesterol, which is 1080 mg. This states that Professor Hamer should eat noodles for 8 days and tofu for 12 days out of 20 meals.
We must be aware that in some cases a linear program may not have an optimal solution.
- A linear program cannot have an optimal solution if there is no feasible domain. If the inequality constraints are not compatible, there may not be an area on the graph that satisfies the requirementsatthe restrictions. If the linear program does not have a feasible solution that satisfies all the constraints, then it cannot have an optimal solution.
- A linear program cannot have an optimal solution if the allowed range is unbounded.
- The two linear minimization programs we examined had unbounded feasible domains. The realizable area was limited by constraints on some sides, but not entirely enclosed by the constraints. Both minimization problems had optimal solutions.
- However, if we were to consider a maximization problem with a similar unconstrained feasible domain, the linear program would not have an optimal solution. No matter what values of x and y were chosen, we could always find other values of \(x\) and \(y\) that would give a higher value for the objective function. In other words, if the value of the objective function can be increased indefinitely in a linear program with unlimited range, then there is no optimal maximum solution.
Although the method of solving minimization problems is similar to that of maximization problems, we still think we should summarize the steps involved.
Minimization problems in linear programming
- Define the unknowns.
- Write down the objective function to be minimized.
- Write the restrictions.
- For standard linear programming minimization problems, constraints are of the form: \(ax + by ≥ c\)
- Since the variables are not negative, enclose the constraints: \(x ≥ 0\); \(y ≥ 0\).
- Graphically represent the constraints.
- Shade the allowed area.
- Find the vertices.
- Find the value of the objective function at each vertex to determine the vertex that gives the minimum value.
FAQs
What are the real life applications of linear programming? ›
LPP applications may include production scheduling, inventory policies, investment portfolio, allocation of advertising budget, construction of warehouses, etc.
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.
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.
How linear programming is used in application? ›Linear programming provides a method to optimize operations within certain constraints. It is used to make processes more efficient and cost-effective. Some areas of application for linear programming include food and agriculture, engineering, transportation, manufacturing and energy.
What is an example of a linear function in real life? ›You can use a linear equation to determine the cost of whatever cab trip you take on your vacation without knowing how many miles it will be to each location. For example, the linear equation would be y = 0.15x + 9 if “x” represents the number of miles to your destination and “y” represents the cost of that taxi fare.
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.
In Mathematics, linear programming is a method of optimising operations with some constraints. The main objective of linear programming is to maximize or minimize the numerical value. It consists of linear functions which are subjected to the constraints in the form of linear equations or in the form of inequalities.
What is an example of minimization? ›In other words, minimizing is when we frame something to be lesser than it is by denying or dismissing its significance. Minimization can be a conscious process. For instance, a bully might deliberately downplay his rude remarks to avoid any consequences for his actions and claim that he was merely joking.
What is the purpose of minimization? ›The aim of minimisation is to minimise the imbalance between the number of patients in each treatment group over a number of factors. Normally patients would be allocated to a treatment group randomly and while this maintains a good overall balance, it can lead to imbalances within sub-groups.
Why is minimization important? ›Energy minimization is essential to determining the proper molecular arrangement in space since the drawn chemical structures are not energetically favorable.
What is the best use of linear programming? ›
Linear programming uses a mathematical or graphical technique to find the optimal way to use limited resources. When you have a problem that involves a variety of resource constraints, linear programming can generate the best possible solution.
How does Amazon use linear programming? ›Their motive is to maximize efficiency with minimum operation cost. As per the recommendations from the linear programming model, the manufacturer can reconfigure their storage layout, adjust their workforce and reduce the bottlenecks. Linear programming is also used in organized retail for shelf space optimization.
What is linear programming examples? ›Linear Programming Examples
Solution: Using the constraints we get the equations of the lines as 4x + y = 40 and 2x + 3y = 90. As the minimum value of Z is 127, thus, B (3, 28) gives the optimal solution.
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.
What are the real world 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.
- Finding unknown age.
- Finding unknown angles in geometry.
- For calculation of speed, distance or time.
- Problems based on force and pressure.
Linear equations can be used to explain linear cost functions, linear revenue functions, linear profit functions, and linear supply and demand functions.
What is the real life application of linear inequality? ›Our solar system is filled by over 100,000 asteroids, comets and planets. Astronomers use inequalities to classified them according to where they are mostly located on the basis of their distance. For example, the Asteroid Belt is located between 1.3 and 3.5 AU from the sun.
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 find the linear dependence of 4 vectors? ›You can verify if a set of vectors is linearly independent by computing the determinant of a matrix whose columns are the vectors you want to check. They are linearly independent if, and only if, this determinant is not equal to zero.
How do you determine if a linear system is consistent or 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 will you know that a system with four equations is inconsistent when solving it by graphing method? ›When you graph the equations, both equations represent the same line. If a system has no solution, it is said to be inconsistent . The graphs of the lines do not intersect, so the graphs are parallel and there is no solution.
What is the difference between maximization and minimization problems in linear programming? ›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.
What is real life linear programming problems? ›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.
What are the application of linear programming in manufacturing industry? ›It is a linear programming model with three objectives namely, Production cost minimization, production quantity maximization and maximization of capacity utilization. It is to be solved by considering each objective sequentially as a Lexicographic approach.
How do you know if its maximization or 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.
What are minimization techniques? ›Objective: Minimization is a legal interrogation tactic in which an interrogator attempts to decrease a suspect's resistance to confessing by, for example, downplaying the seriousness of the crime.
How do you calculate minimization? ›Cost Minimization Analysis - Key takeaways
In the cost minimization formula, the marginal product of labor divided by the wage rate equals the marginal product of capital divided by the rental price of capital.
This minimization is very crucial since it helps us in the reduction of cost and the overall complexity of an associated circuit. It is very clear from the image given above that the minimized version of any expression requires comparatively lesser numbers of logic gates.
What are the advantages of minimization of logical expressions? ›
Simplification Of Boolean Expressions Using Algebraic
Minimization of the number of literals and the number of terms leads to less complex circuits as well as less number of gates, which should be a designer's aim.
Structural risk minimization. Boolean minimization, a technique for optimizing combinational digital circuits. Cost-minimization analysis, in pharmacoeconomics. Expenditure minimization problem, in microeconomics.
What best describes data minimization? ›Data Minimisation is a principle that states that data collected and processed should not be held or further used unless this is essential for reasons that were clearly stated in advance to support data privacy. In the General Data Protection Regulation (GDPR), this is defined as data that is: Adequate. Relevant.
What is the difference between data minimization and purpose limitation? ›Purpose limitation: Only process personal information for the specified purpose for which you collected it, or for other purposes that are compatible with the original purpose. Data minimization: Only process the personal information that is necessary, relevant, and adequate for your purposes.
What are the three types of linear programming? ›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 is the importance of linear programming in real life decision making? ›The following are some of the key advantages of using linear programming: Attaining optimum use of resources. A more objective way of arriving at decisions. Ensuring due attention to bottlenecks before the problems occur.
Does Google use linear programming? ›We are software engineers, research scientists, and data scientists who use integer programming, linear programming, constraint programming, and graph algorithms to solve problems at scale.
How does FedEx use linear programming? ›Companies like Amazon and FedEx use linear programming to find the shortest and most efficient delivery routes. Linear programming is also used in machine learning applications where a neural network is trained to fit model of a function in order to label input data and predict unknown future values.
Do airlines use linear programming? ›Linear programming is used in business and industry in production planning, transportation and routing, and various types of scheduling. Airlines use linear programs to schedule their flights, taking into account both scheduling aircraft and scheduling staff.
What are the applications of linear programming? ›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.
What is a real life example of a linear relation? ›
Linear relationships are evident in real-life. For instance, the number of hours work compared to the amount of money earned is often a linear relationship. In this example, the number of hours worked would be the independent variable while the money earned would be the dependent variable.
What are the 5 categories of linear programming models? ›- Manufacturing problems.
- Diet Problems.
- Transportation Problems.
- Optimal Assignment Problems.
so the number of constraints is unlimited.
How do you do constraints in linear programming? ›- Well, you must read the text well and identify three things :
- 1) The linear function that has to be maximized/minimized.
- 2) The variables, those occur in the linear function of 1)
- 3) The constraints are also a linear function of the variables,
- and that function has to be ≥ or ≤ a number.
Multiple solutions of a linear programming problem are solutions each of which maximize or minimize the objective function. Under graphical method, the existence of multiple solution is indicated by a situation under which the objective function line coincides with one of the half planes generated by a constraint.
What are 5 types of constraints? ›- NOT NULL constraints. ...
- Unique constraints. ...
- Primary key constraints. ...
- (Table) Check constraints. ...
- Foreign key (referential) constraints. ...
- Informational constraints.
The three primary constraints that project managers should be familiar with are time, scope, and cost. These are frequently known as the triple constraints or the project management triangle.
What are the 2 most common design constraints? ›- 1- Commercial Constraints. Basic commercial constraints such as time and budget.
- 2- Requirements. ...
- 3- Non-Functional requirements. ...
- 4- Compliance. ...
- 5- Style. ...
- 6- Sensory Design. ...
- 7- Usability. ...
- 8- Principles.
- NOT NULL constraints. ...
- Unique constraints. ...
- Primary key constraints. ...
- (Table) Check constraints. ...
- Foreign key (referential) constraints. ...
- Informational constraints.
- graphing.
- substitution method.
- elimination method.
What are the 3 variables in simplex method minimization? ›
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.
What are the two limitations of linear programming? ›- It is not simple to specify the constraints even after the determination of a given function. ...
- There is a possibility that both functions are linear.
- Determining the given function mathematically in a linear programming problem is quite difficult.
Explanation: Because there is no need for optimization in traffic signal control problems, linear programming methods cannot be used to solve them.
What is most often used to solve a linear programming problem? ›The basic method for solving linear programming problems is called the simplex method, which has several variants. Another popular approach is the interior-point method.