Posted on

# LINEAR PROGRAMMING

LINEAR PROGRAMMING

UNAWEZA JIPATIA NOTES ZETU KWA KUCHANGIA KIASI KIDOGO KABISA:PIGA SIMU:0787237719

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 a1x + b1y ≤ c1 and a2x + b2yc2 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: m1x + n1y

Subject to:     a1x + b1y ≤ c1

a2x + b2y ≤ c2

x ≥ 0

y ≥ 0

Similarly, if the problem is not of minimization of the objective function  m5x ÷ n5y and a3x + b3y ≥ c3 while a4x + b4y ≥ c4, x ≥ 0 and y ≥ 0 are  bounding constraints, then standard form is:

Minimize: m5x + n5y

Subject to:     a3x + b3y ≥ c3

a4x + b4y ≥ c4

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 a1x + b1y ≤ c1, a2x + b2y ≤ c2, 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 M1, and M2. 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, M1 and M2 who are available for 100 days and 80 days a year respectively. M1 works in union farms for 6 days in tomatoes farm for 10 days. M2 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 600M2.A car requires 6 M   and a bus 15 M2 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 m2 and batch of 4 freezers in 4m2. He reserved 160m2   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, E1 and E2, 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 E1 45 60000/= 5m2 E2 30 37500/= 4m2

The company is prepared to buy at least E2 equipment as E1   equipments. At least 360 products must be produced per hour and up to 80m2 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 (p1) and paper 2 (p2), both papers were marked out of 100. A candidate is given a mark x for p1 and mark y for p2. Someone is considered to have passed if 3x + 5y is at least 210, but candidates must score above 35 marks on p1 and above 44 marks on p2, 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