MATHEMATICS As LEVEL(FORM FIVE) NOTES – LINEAR PROGRAMING

LINEAR PROGRAMMING

Definition

Linear programming is a branch of mathematics that enables one to solve problems where either the greatest or minimum/least value of a certain quantity is required under some given limitations or constraints.

Example

In a large organization, decisions about distribution to realize maximum profit or reduce production costs are made using linear programming.

Limitations or constraints are translated into linear inequalities.

The greatest or least value will be expressed as a function called the objective function.

Introduction

Drawing of linear inequalities

Example 01

Draw and show the half-plane represented by 8x + 2y ≥ 16.

Solution

For 8x + 2y ≥ 16, draw the line 8x + 2y = 16.

For x-intercept, let y = 0:

8x = 16

x = 2

For y-intercept, let x = 0:

2y = 16

y = 8

Using (0, 0) as a test point:

8(0) + 2(0) ≥ 16

0 ≥ 16 (False)

The half-plane is the region not containing (0, 0).

Example 02

Determine the solution set of the simultaneous inequalities:

Solution

Draw x + y = 3 (solid line).

At x-intercept, y = 0; at y-intercept, x = 0:

x = 3, y = 3

Draw x – 2y = 9.

At x-intercept, y = 0; at y-intercept, x = 0:

x = 9, y = 0

Using (0, 0) as a test point:

x + y ≥ 3: 0 + 0 ≥ 3 (False)

x – 2y ≤ 9: 0 – 0 ≤ 9 (True)

The clear part is the solution set, called the feasible region.

Questions

Draw by shading unwanted regions of the half-planes represented by the following simultaneous inequalities:

1. y ≥ 2x – 1, y ≤ -1
2. y ≤ 2x – 1, y ≥ x – 3, y ≥ -1
3. y < 2x – 1, y ≤ -1
4. 6x + 9y ≥ 12
5. 0.4x + 0.1y ≥ 0.2
6. 32x + 10y ≥ 20

Evaluation of a function satisfied by the given set of inequalities

Example

Find the maximum and minimum value of c = 4x + 3y + 38 subject to:

• x + y ≥ 5
• 0 ≤ y ≤ 6
• 0 ≤ x ≤ 5
• x ≥ 0, y ≥ 0

Solution

For x + y ≥ 5, draw x + y = 5.

When x = 0, y = 5; when y = 0, x = 5.

For 0 ≤ y ≤ 6, draw lines y = 0 and y = 6.

For 0 ≤ x ≤ 5, draw lines x = 0 and x = 5.

Test points: x ≥ 0 (shade right of x = 0), y ≥ 0 (shade above x-axis).

The maximum value of c is 76 and occurs at (5, 6).

The minimum value of c is 53 and occurs at (0, 5).

Questions

Find the maximum and minimum values of the given functions and the values of x and y where they occur:

1. Z = 4x + 3y

   Subject to:

   • x + 2y ≤ 10
   • 3x + y ≤ 5
   • x ≥ 0, y ≥ 0

2. P = 134x + 20y

   Subject to:

   • x + y ≤ 160
   • 10 ≤ x ≤ 60
   • 0 ≤ y ≤ 120

3. T = 4x + 7y

   Subject to:

   • x + y ≤ 18
   • 5 ≤ x ≤ 10
   • 3 ≤ y ≤ 10
   • x ≥ 0, y ≥ 0

4. P = 2x + 4y

   Subject to:

   • 2x + 3y ≥ 3
   • -5x + 4y ≤ 0
   • 3x + 4y ≤ 18
   • x ≥ 0, y ≥ 0

Formulation of a Linear Programming Problem

Steps in formulating a linear programming problem:

1. Read the problem several times and assess what is known and what is to be determined.
2. Identify the unknown quantities and assign variables to them, being careful about the units.
3. Determine the objective function; it involves the quantity to be maximized or minimized.
4. Translate the constraints into linear inequalities. Constraints are limitations or restrictions; units must be consistent.
5. Graph the constraints and find the feasible solution.
6. Find the corner points of the feasible solution. These are points of intersection of the graphs.
7. Evaluate the objective function. The highest value is maximized or the smallest value is minimized.

Example

A student has 120 shillings to spend on exercise books. At a school shop, an exercise book costs 8 shillings; at a stationery store, an exercise book costs 12 shillings. The school has only 6 exercise books, and the student wants to obtain the greatest number of exercise books possible using the money. Find the greatest number of exercise books he can buy.

Solution

Let x be the number of exercise books bought at the school shop.

Let y be the number of exercise books bought at the stationery shop.

Objective function

Let f(x, y) = x + y (total number of books).

Constraints or linear inequalities

• 8x + 12y ≤ 120 (budget constraint)
• x ≤ 6 (school shop stock limit)
• x ≥ 0, y ≥ 0 (non-negative constraints)

Equations

8x + 12y = 120

Dividing by 4: 2x + 3y = 30

When x = 0, y = 10

When y = 0, x = 15

x = 6, y = 0

The greatest number of exercise books he can buy is 12 (6 from the school shop and 6 from the stationery shop).

Example

Students in a certain class are about to take a test of BAM which has two sections A and B. Each question in section A is worth 10 marks, while each in section B is worth 25 marks. The student must do at least 3 questions in section A but not more than 12. The student must also do 4 questions from section B but not more than 15. In addition, students cannot do more than 20 questions in total. How many questions of each type should the student do to obtain the maximum score?

Solution

Let x be the number of questions done in section A.

Let y be the number of questions done in section B.

Objective function

f(x, y) = 10x + 25y

Constraints

• 3 ≤ x ≤ 12
• 4 ≤ y ≤ 15
• x + y ≤ 20
• x ≥ 0, y ≥ 0

Equations

3 ≤ x ≤ 12

4 ≤ y ≤ 15

x + y = 20

When x = 20, y = 0

When x = 0, y = 20

The student should do 5 questions from section A and 15 questions from section B to obtain the maximum score of 425.

Diet Problems on Linear Programming

Example 01

A doctor prescribes a special diet for patients containing the following units of Vitamin A and B per kg of two types of food F₁ and F₂:

If the minimum daily intake required is 120 units of Vitamin A and 70 units of Vitamin B, what is the least total mass of food a patient must have to meet these requirements?

Example 02

Rice and beans provide maximum levels of protein, calories, and Vitamin B₂. The food values per kg of uncooked rice and beans are as shown in the table below:

What is the lowest cost of diet meeting these specifications?

Solution

Let x be the number of kg of rice to be bought.

Let y be the number of kg of beans to be bought.

Objective function

Minimize f(x, y) = 400x + 500y

Constraints

• 60x + 90y ≥ 120 (Protein)
• 3200x + 1000y ≥ 2000 (Calories)
• 0.4x + 0.1y ≥ 0.2 (Vitamin B₂)
• x ≥ 0, y ≥ 0

For 60x + 90y ≥ 120:

60x + 90y = 120

Dividing by 30: 2x + 3y = 4

When x = 0, y = 1.3

When y = 0, x = 2

For 3200x + 1000y ≥ 2000:

32x + 10y = 20

Dividing by 2: 16x + 5y = 10

When x = 0, y = 2

When y = 0, x = 0.63

For 0.4x + 0.1y ≥ 0.2:

0.4x + 0.1y = 0.2

When x = 0, y = 2

When y = 0, x = 0.5

The least total mass a patient should have is 6.8 kg, i.e., 3.6 kg of food 1 and 3.2 kg of food 2.

Question

A doctor prescribes that to obtain an adequate supply of vitamins A and C, his patient should have portions of food 1 and food 2. The number of units of vitamins A and C are given in the following table:

The doctor prescribes a minimum of 14 units of vitamin A and 21 units of vitamin C. What are the least portions of food 1 and food 2 that will fit the doctor’s prescriptions?

Linear Programming Problems

1. Two printers N and T produce three types of books. N produces 80 type I books per day, 10 type II books per day, and 20 type III books per day, while T produces 20 type I books per day, 10 type II books per day, and 70 type III books per day. The orders placed are 1600 type I, 500 type II, and 2100 type III books. The daily operating costs are 10,000 shillings for N and 20,000 shillings for T. How many days should each printer operate to meet the orders at minimum cost?

2. A small textile company manufactures three different sizes of shirts: Large (L), Medium (M), and Small (S) at two different plants A and B. The number of shirts of each size produced and the cost of production per day are as follows:

   	A	B	Monthly demand
   Large size per day	50	60	2500
   Medium size per day	100	70	3500
   Small size per day	100	200	7000
   Production Cost per day (Tshs.)	2500	3500

3. In a garage, the manager has the following facts: floor space required for a saloon is 2 m² and for a lorry is 3 m². Four technicians are required to service a saloon car and three technicians for a lorry per day. He has a maximum of 24 m² of floor space and a maximum of 36 technicians available. In addition, he is not allowed to service more lorries than saloon cars. The profit for servicing a saloon car is 40,000/= and for a lorry is 60,000/=. How many motor vehicles of each type should be serviced daily to maximize profit?

Solution

Let x be the number of saloon cars serviced daily.

Let y be the number of lorries serviced daily.

Objective function

F(x, y) = 40000x + 60000y

Constraints

• 2x + 3y ≤ 24 (floor space)
• 4x + 3y ≤ 36 (technicians)
• x ≥ y (no more lorries than saloon cars)
• x ≥ 0, y ≥ 0

6 saloon cars and 4 lorries should be serviced daily to maximize profit to 480,000/=.

More Examples

A builder has two stores, S₁ and S₂, and is building houses at P₁, P₂, and P₃. He needs 5 tons of bricks at P₁, 6 tons at P₂, and 4 tons at P₃. The stores contain 9 tons at S₁ and 6 tons at S₂. The transport cost per ton is shown in the diagram:

How does the builder send his bricks at minimum cost? What is the minimum overall cost?

Solution

Let x be tons of bricks sent from S₁ to P₁, y be tons from S₁ to P₂. The remaining bricks to P₃ from S₁ is 9 – (x + y).

Similarly, from S₂ to P₁ is 5 – x, to P₂ is 6 – y, and to P₃ is 4 – [9 – (x + y)].

The constraints are:

• x ≥ 0, y ≥ 0
• x + y ≤ 9
• x ≤ 5
• y ≤ 6
• x + y ≥ 5

Objective function

Minimize f(x, y) = 6x + 3y + 4[9 – (x + y)] + 4(5 – x) + 2(6 – y) + 6[4 – (9 – (x + y))]

Simplified:

f(x, y) = 4x – 3y + 38

Subject to:

• x + y ≤ 9
• x + y ≥ 5
• x ≤ 5, y ≥ 0
• y ≤ 6, y ≥ 0

The overall minimum cost is 53/=.