LINEAR PROGRAMMING
LINEAR PROGRAMMING
USIBAKI NYUMA>PATA NOTES ZETU KWA HARAKA:INSTALL APP YETU-BOFYA HAPA
UNAWEZA JIPATIA NOTES ZETU KWA KUCHANGIA KIASI KIDOGO KABISA:PIGA SIMU:0787237719
FOR MORE NOTES,BOOKS,SCHEMES OF WORKS,PAST PAPERS AND ANALYSIS CLICK HERE
This topic uses the knowledge of graphical solution of system of linear equations and inequalities. Owing to that, we will start this topic by looking at this important background knowledge.
SOLUTION OF SYSTEM OF LINEAR EQUATIONS
A system of linear equations can be solved graphically, by graphing the two linear equations on the same Cartesian coordinate plane, and solution of this is given by the point of intersection.
Example 11.1
Solve the system of equations by graphing
SOLUTION
We must obtain a table of values for the two linear equations. In all these, we will use only two points. This is because two points determine a straight line.
Table 11.1 3x – y = 4
X | 0 | 4/3 |
Y | -4 | 0 |
Table 11.2 2x + y = 6
X | 0 | 3 |
Y | 6 | 0 |
Figure11.1 shows the graph of the information’s in table 11.1 and 11.2
The two lines intersect at (2, 2)
Thus, the solution of the system is (2, 2) i.e x = 2 and y = 2
A system of linear equations that has unique solution like is said to be
Consistent and independent
There are equations that the same gradient (inclination) and the same x and y intercept. These system of equation have all of their points coinciding, as such we say they have infinitely many solutions.
Example 11.2
Solve the system of equations below graphically
Solution
The x and y intercepts of the equations above are 1 and 3 respectively is shown in figure 11.2.
Hence, the solution set is (
Note that, any system of linear equations which has infinitely many solution is said to be INCONSISTENT and DEPENDENT.
Example 11.3
Solve the following system of equations graphically:
Shows two straight lines that are not intersecting however much they are neither side. We call them parallel lines. I or the reason these two lines are not the system does not have a solution. Any system of linear equations that doesn’t have a solution is said to be INCONSISTENT.
Table 11.3 summarizing the study on graphical solutions of linear equation
Graph | Inclination (gradient) | Name of the system |
Lines that intersect | Distinct inclinations and distinct intercepts. | Consistent and independent. |
Parallel lines | Same inclinations but distinct intercepts. | Inconsistent. |
Lines that concide | Same inclinations and intercept. | Consistent and Dependent |
1. The following system of linear equations graphically and state whether the consistent and independent, inconsistent or consistent and dependent:
2.
3.
4.
5.
6. Write an equation the line that is inconsistent with the line 3x – y – 1 =0 and goes though (1, 1).
7. Write an equation of the line is inconsistent with the line 3x – y – 1 = 0 and
Goes through (1, 1)
8. Line kx + ty – 8 is consistent and dependent to line 12x + 15y = 24. Find the values of k and t that fit the stated condition.
Graphing systems of inequalities
Systems of inequalities can also be solved graphically. They have solutions like linear equations, but their solution are regions which satisfy set of inequalities being graphed.
1. Obtain the line of equality (boundary lines) by replacing the inequality sign with an equal sign.
2. Draw the line of equality (equalities) in Cartesian coordinate plane.
3. Test for the region satisfies the inequality (inequalities) and shade it
Example 11.4
Solve the following system graphically
Solution
The line of equalities for the above inequalities are y = 4, y = -3 and y = x + 1
Note
If the line of equality was derived from the inequality ≥ or ≤ the line must be drawn as full line, but if it was from > or < the line must be made broken
Draw each of the above lines in the same Cartesian coordinate plane, test and shade the required region.
The figure shows the required graph for the set of the inequalities.
The region marked F in figure 11.4 is the solution of the set of the given inequalities. We call it feasible region. If the system of inequalities does not have a region that satisfies all the inequalities in a given set, that system does not have a solution.
Exercise 11.2
Does the point given against each system of inequalities satisfy the system?
1. (0, 0)
2. (1, 0)
3. (5, 5)
4. (0, 4)
5. (1, 1)
Solve each of the following inequalities graphically
6.
7.
8.
9.
10.
11.
12.
Linear programming (Linear Optimization)
Linear programming (optimization) is the youngest branch of mathematics which was developed by George Dantizig in 1940’s. It is the model that consist of methods for solving many day to day life problems that in one way or the other demand the optimization of resources which are scarce.
The actual fact, linear programming is a mathematical procedure which helps to allocate, select, schedule and evaluate limited resources in the best possible way . These limited resources in this case may be money in the form of capital or costs. They can also be raw materials, labour and production equipments.
Generally, linear programming problems always are such that they tend to fulfill a linear statement of the form, mx + ny, called objective function. So if a_{1}x + b_{1}y ≤ c_{1} and a_{2}x + b_{2}yc_{2} are the only constraints that restrict the maximization of problems and if also x ≥ 0 and are their non – negativity constraints, then the standard way of reporting (writing) this problem is
Maximize: m_{1}x + n_{1}y
Subject to: a_{1}x + b_{1}y ≤ c_{1}
a_{2}x + b_{2}y ≤ c_{2}
x ≥ 0
y ≥ 0
Similarly, if the problem is not of minimization of the objective function m_{5}x ÷ n_{5}y and a_{3}x + b_{3}y ≥ c_{3} while a_{4}x + b_{4}y ≥ c_{4}, x ≥ 0 and y ≥ 0 are bounding constraints, then standard form is:
Minimize: m_{5}x + n_{5}y
Subject to: a_{3}x + b_{3}y ≥ c_{3}
a_{4}x + b_{4}y ≥ c_{4}
x ≥ 0
y ≥ 0
Note:
1. An objective function is a mathematical statement that defines how best a data fits a particular assertion. It describes the essential characteristics of the alternative
2. Constraints are sets of inequalities for a linear programming problem in question, i.e a_{1}x + b_{1}y ≤ c_{1}, a_{2}x + b_{2}y ≤ c_{2}, x ≥ 0 and y ≥ 0 in the standard form for maximization given earlier.
– If (x, y) happens to be one of the point that satisfies all the constraints, we call it a feasible solution. A set of all feasible solution form what we call a feasible region. The feasible region includes the boundary lines (lines of equality). If the feasible region is enclosed by a polygon, it is said to be bounded or unbounded (see figure 11.5).
If a feasible region has no point, the constraints involved are inconsistent and the problem does not have solution. The solution of any linear programming problem is given by one (some) of the feasible solution (s).However, these feasible solutions are many, which one should be taken as optimum solution? The following answer that
THEOREM
For a feasible region has no point of a linear programming which is bounded and not empty, the objective function attains either a maximum or a minimum value at the corner points (vertices) of the feasible region. If the feasible is unbounded, the objective function may or may not attain a minimum or maximum value, but if it attain, it does so at the corner points (vertices).
According to the theorem, the optimum solution comes the corner points, ie once you have graphed the constraints in Cartesian coordinate plane, test the corner points objective function, and then identify the optimum solution.
Example 11. 5
Siwatu wants to earn at least 13000/= this week. Her father has agreed to pay her 5000/= to know the lawn and 2000/= to weed the garden in a day suppose Siwatu mows the lawn once, what minimum number of days will she have to spend weeding the garden?
Solution
Let x and y be the number of days Siwatu spends moving the lawn and wedding the garden respectively.
Objective function x + y
For minimization
Subject to: 5000x + 2000y ≥ 13000
5x + 2y ≥ 13
Hence, she mows the lawns once, then
x ≥ 1 and x ≥0 y ≥ 0
Linear programming problems associated with this question is as follows
Minimize: x + y
Object to: 5x + 2y ≥ 13
x ≥ 1
x ≥ 0
y ≥ 0
The feasible region of the problem, together with the corner points are shown in figure the feasible region is indicated by shading.
Table 11.4
Corner points | x + y |
(1, 4) | 5 |
(2.6, 0) | 2. 6 |
(5) Is the optimum solution row.
From table 11.4, the optimum solution is (1,4) meaning that to earn the required amount of money, Siwatu will have to work 4 days a week.
Example 11.6
A carpenter makes two kinds of furniture, i.e chairs and tables. Two operations M and N are used. Operation M is limited to 20 days a month while operations N are limited to 15 days per month. Table 11.5 shows the amount of time each operation takes for one chair and one table and the profit it makes on each item.
Table 11.5
Furniture | Operations M | Operations N | Profit |
Chair | 2 day | 3 days | 20000/= |
Table | 4 days | 1 day | 24000/= |
How many tables and chairs should the carpenter make in a month to maximize the income?
Solution
Let the number of chairs and tables be x and y respectively
Object function:
f(x,y) = 20000x + 24000y
2000x + 24000y
2x + 4y 20
x + 2y ≤ 20
Also 3x + y ≤ 15
x ≥ 0 and y ≥ 0
Thus, the linear programming problems associated with this question is as follow
Maximize: 20000x + 24000y
Subject to: x + 2y ≤ 10
3x + y ≤ 15
x ≥ 0
y ≥ 0
Figure shows the graph of linear programming problem given in example 11.6
Table 11.6
Corner points | 20000x + 24000y |
(0, 0) | 0 |
(0, 5) | 120,000 |
(4, 3) | 152,000 |
(5, 0) | 100,000 |
152,000 is maximum value optimum solution row.
To maximize the income a month, a carpenter should make 4 chairs and 3 tables
Exercise 11.3
Answer each of the following questions as directed.
1. a) Are the solutions of linear programming problems unique?
Explain
b) What do you understand by the terms i) Feasible solutions? ii) Feasible region? iii) Constraints? iv) Objective function?
2. Maximize: 30x + 50y
Subject to: 2x + 8y ≤ 60
4x + 4y ≤ 60 ,x ≥ 0
x ≥ 0
3. Maximize: x + 6y
Subject to: 5x + 10y ≤ 50
x + y ≤ 10
x ≥ 0
y ≥ 0
4. Minimize: 60 – (x + y)
Subject to: x + y ≥ 3
x ≤ 4
x + 3y ≥ 15
x ≥ 0
y ≥ 0
5. Maximize a daily production of Mandazi and Chapati of mama Masawe’s business which is mixture of items M_{1}, and M_{2}. The required information is summarized in table 11.7
Table 11.7
Item | production | Daily supply | |
Maandazi | chapati | ||
M1 | 5 | 2.5 | 10kg |
M2 | 5 | 7.5 | 15kg |
Net profit in TZ shs | 300 | 250 |
6. A farmer produces and sells onions and tomatoes. His profit being 150000/=and 100000/= respectively. His production involves two workers, M_{1} and M_{2} who are available for 100 days and 80 days a year respectively. M_{1} works in union farms for 6 days in tomatoes farm for 10 days. M_{2} works in onion farm for 4 days and in tomatoes farms for 4 days determine production costs that will maximize the production.
7. Mnazimmoja parking lot has a total area of 600M^{2}.A car requires 6 M^{2 } and a bus 15 M^{2} of space. The attendants can handle not more than 60 vehicles. If car is charged 2500/= and a bus 7500/=, how many of each should be accepted to maximize the profits? What is the of space left unused?
8. A bus contractor is contracted to transport 500 workers to their working places.For the contract, he has 3 type M buses capable of carrying 50 workers and 4 type N buses capable of carrying 85 workers each. Only five drivers are available at the moment. If no bus is to repeat, how will the cost be reduced given that running type M bus costs 5000/= and type N bus costs 4000/=? How many drivers should be used?
9. Rose is a shopkeeper of Hilanyeupe. Shop in one occasion, she accepted goods with delivery note of a number of beef cans which was not visible enough. She trusted the supplier so she did not look at the delivery note and she did not bother herself counting. Two days later, she took the delivery note for the beef supplied two days ago and she found that the number was a three digits one with 4 as the middle digit. Owing to this, she concluded that the first digit can be less or equal to six (6) and the third digit can be smaller or equal to 6, and that the sum of the two unknown digits cannot exceed 8. If the difference of 6 times the first digit and the third’’ is to be big enough, what was the approximate number? (Assuming her conclusion was right)
Revision exercise 11
Solve each of the following graphically stating whether the system is inconsistent, consistent and independent or consistent and dependent.
1.
2.
3.
4.
5.
Solving each of the system of linear inequalities that follows
6.
7.
8.
9.
10.
11.
12.
13. Define the terms
i) Linear programming
ii) Bounded linear programming problem
iii) Unbounded linear programming problem
14. Maximize: x + 5y
Subject to:
15. Minimize: 3x + 2y
Subject to: 0≤ x ≤ 8
0 ≤ y ≤ 7
x + y ≤ 10
16. Maximize 10x + 20y
Subject to: 0< x <9
y > 18
x + 3y ≤ 75
17. Maximize: 2500x + 7500
Subject to: x + y ≤ 60
x + 5y ≤ 100
x ≥ 0, y ≥ 0
18. Maximize: 120x + 250y
Subject to: 0 ≤ x ≤ 300
0 ≤ y ≤ 200
2x + 3y ≤ 1200
19.A store manager of a certain company finds that he can store a batch of 3 machines in 2 m^{2} and batch of 4 freezers in 4m^{2}. He reserved 160m^{2} altogether for this section of his stock and never allows the number of items to exceed 400. Find the greatest number of items he can accept subject to those conditions? If the machine is sold at 450000/= and a freezer at 225000/=, find the combination of items he should keep to maintain the greatest possible value of stock.
20.A company is intending to buy two equipments, E_{1} and E_{2}, these equipments are to be used for a certain production. More information of these equipments is given in table 11.8
Table 11.
Equipment | Output per hour | Profit per hour | Floor space take |
E_{1} | 45 | 60000/= | 5m^{2} |
E_{2} | 30 | 37500/= | 4m^{2} |
The company is prepared to buy at least E_{2} equipment as E_{1} equipments. At least 360 products must be produced per hour and up to 80m^{2} of the floor space is available find the combination of the equipments that must be bought to maximize the profit will the floor space be left? If yes how much?
21. In a physics examination consisting of paper 1 (p_{1}) and paper 2 (p_{2}), both papers were marked out of 100. A candidate is given a mark x for p_{1} and mark y for p_{2}. Someone is considered to have passed if 3x + 5y is at least 210, but candidates must score above 35 marks on p_{1} and above 44 marks on p_{2}, Find the lowest value of x + y for any candidates who passes and give the corresponding values of x and y.
JE UNAMILIKI SHULE AU BIASHARA NA UNGEPENDA IWAFIKIE WALIO WENGI?BASI TUNAKUPA FURSA YA KUJITANGAZA NASI KWA BEI NAFUU KABISA BOFYA HAPA KUJUA
But for more post and free books from our site please make sure you subscribe to our site and if you need a copy of our notes as how it is in our site contact us any time we sell them in low cost in form of PDF or WORD.
UNAWEZA JIPATIA NOTES ZETU KWA KUCHANGIA KIASI KIDOGO KABISA:PIGA SIMU:0787237719
SHARE THIS POST WITH FRIEND