Skip to content Skip to navigation

Connexions

You are here: Home » Content » Linear Programming - Grade 11

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • FETMaths display tagshide tags

    This module is included inLens: Siyavula: Mathematics (Gr. 10-12)
    By: Siyavula

    Review Status: In Review

    Click the "FETMaths" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Bookshare

    This module is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech InitiativeAs a part of collection: "FHSST: Grade 11 Maths"

    Comments:

    "Accessible versions of this collection are available at Bookshare. DAISY and BRF provided. "

    Click the "Bookshare" link to see all content affiliated with them.

  • Siyavula: Mathematics display tagshide tags

    This module is included inLens: Siyavula Textbooks: Maths
    By: Free High School Science Texts ProjectAs a part of collection: "FHSST: Grade 11 Maths"

    Click the "Siyavula: Mathematics" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Introduction

In everyday life people are interested in knowing the most efficient way of carrying out a task or achieving a goal. For example, a farmer might want to know how many crops to plant during a season in order to maximise yield (produce) or a stock broker might want to know how much to invest in stocks in order to maximise profit. These are examples of optimisation problems, where by optimising we mean finding the maxima or minima of a function.

You will see optimisation problems of one variable in Grade 12, where there were no restrictions to the answer. You will be required to find the highest (maximum) or lowest (minimum) possible value of some function. In this chapter we look at optimisation problems with two variables and where the possible solutions are restricted.

Terminology

There are some basic terms which you need to become familiar with for the linear programming chapters.

Decision Variables

The aim of an optimisation problem is to find the values of the decision variables. These values are unknown at the beginning of the problem. Decision variables usually represent things that can be changed, for example the rate at which water is consumed or the number of birds living in a certain park.

Objective Function

The objective function is a mathematical combination of the decision variables and represents the function that we want to optimise (i.e. maximise or minimise). We will only be looking at objective functions which are functions of two variables. For example, in the case of the farmer, the objective function is the yield and it is dependent on the amount of crops planted. If the farmer has two crops then the objective function f(x,y)f(x,y) is the yield, where xx represents the amount of the first crop planted and yy represents the amount of the second crop planted. For the stock broker, assuming that there are two stocks to invest in, the objective function f(x,y)f(x,y) is the amount of profit earned by investing xx rand in the first stock and yy rand in the second.

Constraints

Constraints, or restrictions, are often placed on the variables being optimised. For the example of the farmer, he cannot plant a negative number of crops, therefore the constraints would be:

x ≥ 0 y ≥ 0 . x ≥ 0 y ≥ 0 .
(1)

Other constraints might be that the farmer cannot plant more of the second crop than the first crop and that no more than 20 units of the first crop can be planted. These constraints can be written as:

x ≥ y x ≤ 20 x ≥ y x ≤ 20
(2)

Constraints that have the form

a x + b y ≤ c a x + b y ≤ c
(3)

or

a x + b y = c a x + b y = c
(4)

are called linear constraints. Examples of linear constraints are:

x + y ≤ 0 - 2 x = 7 y ≤ 2 x + y ≤ 0 - 2 x = 7 y ≤ 2
(5)

Feasible Region and Points

Constraints mean that we cannot just take any xx and yy when looking for the xx and yy that optimise our objective function. If we think of the variables xx and yy as a point (x,y)(x,y) in the xyxy-plane then we call the set of all points in the xyxy-plane that satisfy our constraints the feasible region. Any point in the feasible region is called a feasible point.

For example, the constraints

x ≥ 0 y ≥ 0 . x ≥ 0 y ≥ 0 .
(6)

mean that only values of xx and yy that are positive are allowed. Similarly, the constraint

x ≥ y x ≥ y
(7)

means that only values of xx that are greater than or equal to the yy values are allowed.

x ≤ 20 x ≤ 20
(8)

means that only xx values which are less than or equal to 20 are allowed.

Tip:

The constraints are used to create bounds of the solution.

The Solution

Tip:

Points that satisfy the constraints are called feasible solutions.

Once we have determined the feasible region the solution of our problem will be the feasible point where the objective function is a maximum / minimum. Sometimes there will be more than one feasible point where the objective function is a maximum/minimum — in this case we have more than one solution.

Example of a Problem

A simple problem that can be solved with linear programming involves Mrs Nkosi and her farm.

Mrs Nkosi grows mielies and potatoes on a farm of 100 m22. She has accepted orders that will need her to grow at least 40 m22 of mielies and at least 30 m22 of potatoes. Market research shows that the demand this year will be at least twice as much for mielies as for potatoes and so she wants to use at least twice as much area for mielies as for potatoes. She expects to make a profit of R650 per m22 for her mielies and R1 500 per m22 on her potatoes. How should she divide her land so that she can earn the most profit?

Let mm represent the area of mielies grown and let pp be the area of potatoes grown.

We shall see how we can solve this problem.

Method of Linear Programming

Method: Linear Programming

  1. Identify the decision variables in the problem.
  2. Write constraint equations
  3. Write objective function as an equation
  4. Solve the problem

Skills you will need

Writing Constraint Equations

You will need to be comfortable with converting a word description to a mathematical description for linear programming. Some of the words that are used is summarised in Table 1.

Table 1: Phrases and mathematical equivalents.
Words Mathematical description
xx equals aa x = a x = a
xx is greater than aa x > a x > a
xx is greater than or equal to aa x ≥ a x ≥ a
xx is less than aa x < a x < a
xx is less than or equal to aa x ≤ a x ≤ a
xx must be at least aa x ≥ a x ≥ a
xx must be at most aa x ≤ a x ≤ a

Exercise 1: Writing constraints as equations

Mrs Nkosi grows mielies and potatoes on a farm of 100 m22. She has accepted orders that will need her to grow at least 40 m22 of mielies and at least 30 m22 of potatoes. Market research shows that the demand this year will be at least twice as much for mielies as for potatoes and so she wants to use at least twice as much area for mielies as for potatoes.

Solution
  1. Step 1. Identify the decision variables :

    There are two decision variables: the area used to plant mielies (mm) and the area used to plant potatoes (pp).

  2. Step 2. Identify the phrases that constrain the decision variables :
    • grow at least 40 m22 of mielies
    • grow at least 30 m22 of potatoes
    • area of farm is 100 m22
    • demand is at least twice as much for mielies as for potatoes
  3. Step 3. For each phrase, write a constraint :
    • m ≥ 40 m ≥ 40
    • p ≥ 30 p ≥ 30
    • m + p ≤ 100 m + p ≤ 100
    • m ≥ 2 p m ≥ 2 p

constraints as equation

Write the following constraints as equations:

  1. Michael is registering for courses at university. Michael needs to register for at least 4 courses.
  2. Joyce is also registering for courses at university. She cannot register for more than 7 courses.
  3. In a geography test, Simon is allowed to choose 4 questions from each section.
  4. A baker can bake at most 50 chocolate cakes in 1 day.
  5. Megan and Katja can carry at most 400 koeksisters.

Writing the Objective Function

If the objective function is not given to you as an equation, you will need to be able to convert a word description to an equation to get the objective function.

You will need to look for words like:

  • most profit
  • least cost
  • largest area

Exercise 2: Writing the objective function

The cost of hiring a small trailer is R500 per day and the cost of hiring a big trailer is R800 per day. Write down the objective function that can be used to find the cheapest cost for hiring trailers for 1 day.

Solution
  1. Step 1. Identify the decision variables :

    There are two decision variables: the number of big trailers (nbnb) and the number of small trailers (nsns).

  2. Step 2. Write the purpose of the objective function :

    The purpose of the objective function is to minimise cost.

  3. Step 3. Write the objective function :

    The cost of hiring nsns small trailers for 1 day is:

    500 × n s 500 × n s
    (9)

    The cost of hiring nbnb big trailers for 1 day is:

    800 × n b 800 × n b
    (10)

    Therefore the objective function, which is the total cost of hiring nsns small trailers and nbnb big trailers for 1 day is:

    500 × n s + 800 × n b 500 × n s + 800 × n b
    (11)

Exercise 3: Writing the objective function

Mrs Nkosi expects to make a profit of R650 per m22 for her mielies and R1 500 per m22 on her potatoes. How should she divide her land so that she can earn the most profit?

Solution
  1. Step 1. Identify the decision variables :

    There are two decision variables: the area used to plant mielies (mm) and the area used to plant potatoes (pp).

  2. Step 2. Write the purpose of the objective function :

    The purpose of the objective function is to maximise profit.

  3. Step 3. Write the objective function :

    The profit of planting mm m22 of mielies is:

    650 × m 650 × m
    (12)

    The profit of planting pp m22 of potatoes is:

    1500 × p 1500 × p
    (13)

    Therefore the objective function, which is the total profit of planting mielies and potatoes is:

    650 × m + 1500 × p 650 × m + 1500 × p
    (14)

Writing the objective function

  1. The EduFurn furniture factory manufactures school chairs and school desks. They make a profit of R50 on each chair sold and of R60 on each desk sold. Write an equation that will show how much profit they will make by selling the chairs and desks.
  2. A manufacturer makes small screen GPS's and wide screen GPS's. If the profit on small screen GPS's is R500 and the profit on wide screen GPS's is R250, write an equation that will show the possible maximum profit.

Solving the Problem

The numerical method involves using the points along the boundary of the feasible region, and determining which point optimises the objective function.

Investigation : Numerical Method

Use the objective function

650 × m + 1500 × p 650 × m + 1500 × p
(15)

to calculate Mrs Nkosi's profit for the following feasible solutions:

Table 2
m m p p Profit
60 30  
65 30  
70 30  
66 2 3 66 2 3 33 1 3 33 1 3  

The question is How do you find the feasible region? We will use the graphical method of solving a system of linear equations to determine the feasible region. We draw all constraints as graphs and mark the area that satisfies all constraints. This is shown in Figure 1 for Mrs Nkosi's farm.

Figure 1: Graph of the feasible region
Figure 1 (MG11C15_001.png)

Vertices (singular: vertex) are the points on the graph where two or more of the constraints overlap or cross. If the linear objective function has a minimum or maximum value, it will occur at one or more of the vertices of the feasible region.

Now we can use the methods we learnt previously to find the points at the vertices of the feasible region. In Figure 1, vertex A is at the intersection of p=30p=30 and m=2pm=2p. Therefore, the coordinates of A are (30,60). Similarly vertex B is at the intersection of p=30p=30 and m=100-pm=100-p. Therefore the coordinates of B are (30,70). Vertex C is at the intersection of m=100-pm=100-p and m=2pm=2p, which gives (33133313,66236623) for the coordinates of C.

If we now substitute these points into the objective function, we get the following:

Table 3
m m p p Profit
60 30 81 000
70 30 87 000
66 2 3 66 2 3 33 1 3 33 1 3 89 997

Therefore Mrs Nkosi makes the most profit if she plants 66236623 m22 of mielies and 33133313 m22 of potatoes. Her profit is R89 997.

Exercise 4: Prizes!

As part of their opening specials, a furniture store has promised to give away at least 40 prizes with a total value of at least R2 000. The prizes are kettles and toasters.

  1. If the company decides that there will be at least 10 of each prize, write down two more inequalities from these constraints.
  2. If the cost of manufacturing a kettle is R60 and a toaster is R50, write down an objective function CC which can be used to determine the cost to the company of both kettles and toasters.
  3. Sketch the graph of the feasibility region that can be used to determine all the possible combinations of kettles and toasters that honour the promises of the company.
  4. How many of each prize will represent the cheapest option for the company?
  5. How much will this combination of kettles and toasters cost?
Solution
  1. Step 1. Identify the decision variables :

    Let the number of kettles be xkxk and the number of toasters be ytyt and write down two constraints apart from xk≥0xk≥0 and yt≥0yt≥0 that must be adhered to.

  2. Step 2. Write constraint equations :

    Since there will be at least 10 of each prize we can write:

    x k ≥ 10 x k ≥ 10
    (16)

    and

    y t ≥ 10 y t ≥ 10
    (17)

    Also the store has promised to give away at least 40 prizes in total. Therefore:

    x k + y t ≥ 40 x k + y t ≥ 40
    (18)
  3. Step 3. Write the objective function :

    The cost of manufacturing a kettle is R60 and a toaster is R50. Therefore the cost the total cost CC is:

    C = 60 x k + 50 y t C = 60 x k + 50 y t
    (19)
  4. Step 4. Sketch the graph of the feasible region :

    Figure 2
    Figure 2 (MG11C15_002.png)

  5. Step 5. Determine vertices of feasible region :

    From the graph, the coordinates of vertex A are (30,10) and the coordinates of vertex B are (10,30).

  6. Step 6. Calculate cost at each vertex :

    At vertex A, the cost is:

    C = 60 x k + 50 y t = 60 ( 30 ) + 50 ( 10 ) = 1800 + 500 = 2300 C = 60 x k + 50 y t = 60 ( 30 ) + 50 ( 10 ) = 1800 + 500 = 2300
    (20)

    At vertex B, the cost is:

    C = 60 x k + 50 y t = 60 ( 10 ) + 50 ( 30 ) = 600 + 1500 = 2100 C = 60 x k + 50 y t = 60 ( 10 ) + 50 ( 30 ) = 600 + 1500 = 2100
    (21)
  7. Step 7. Write the final answer :

    The cheapest combination of prizes is 10 kettles and 30 toasters, costing the company R2 100.

End of Chapter Exercises

  1. You are given a test consisting of two sections. The first section is on Algebra and the second section is on Geometry. You are not allowed to answer more than 10 questions from any section, but you have to answer at least 4 Algebra questions. The time allowed is not more than 30 minutes. An Algebra problem will take 2 minutes and a Geometry problem will take 3 minutes each to solve. If you answer xAxA Algebra questions and yGyG Geometry questions,
    1. Formulate the constraints which satisfy the above constraints.
    2. The Algebra questions carry 5 marks each and the Geometry questions carry 10 marks each. If TT is the total marks, write down an expression for TT.
  2. A local clinic wants to produce a guide to healthy living. The clinic intends to produce the guide in two formats: a short video and a printed book. The clinic needs to decide how many of each format to produce for sale. Estimates show that no more than 10 000 copies of both items together will be sold. At least 4 000 copies of the video and at least 2 000 copies of the book could be sold, although sales of the book are not expected to exceed 4 000 copies. Let xvxv be the number of videos sold, and ybyb the number of printed books sold.
    1. Write down the constraint inequalities that can be deduced from the given information.
    2. Represent these inequalities graphically and indicate the feasible region clearly.
    3. The clinic is seeking to maximise the income, II, earned from the sales of the two products. Each video will sell for R50 and each book for R30. Write down the objective function for the income.
    4. What maximum income will be generated by the two guides?
  3. A patient in a hospital needs at least 18 grams of protein, 0,006 grams of vitamin C and 0,005 grams of iron per meal, which consists of two types of food, A and B. Type A contains 9 grams of protein, 0,002 grams of vitamin C and no iron per serving. Type B contains 3 grams of protein, 0,002 grams of vitamin C and 0,005 grams of iron per serving. The energy value of A is 800 kilojoules and of B 400 kilojoules per serving. A patient is not allowed to have more than 4 servings of A and 5 servings of B. There are xAxA servings of A and yByB servings of B on the patient's plate.
    1. Write down in terms of xAxA and yByB
      1. The mathematical constraints which must be satisfied.
      2. The kilojoule intake per meal.
    2. Represent the constraints graphically on graph paper. Use the scale 1 unit = 20mm on both axes. Shade the feasible region.
    3. Deduce from the graphs, the values of xAxA and yByB which will give the minimum kilojoule intake per meal for the patient.
  4. A certain motorcycle manufacturer produces two basic models, the 'Super X' and the 'Super Y'. These motorcycles are sold to dealers at a profit of R20 000 per 'Super X' and R10 000 per 'Super Y'. A 'Super X' requires 150 hours for assembly, 50 hours for painting and finishing and 10 hours for checking and testing. The 'Super Y' requires 60 hours for assembly, 40 hours for painting and finishing and 20 hours for checking and testing. The total number of hours available per month is: 30 000 in the assembly department, 13 000 in the painting and finishing department and 5 000 in the checking and testing department. The above information can be summarised by the following table:
    Table 4
    DepartmentHours for `Super X'Hours for Super `Y'Maximum hours available per month
    Assembley1506030 000
    Painting and Finishing504013 000
    Checking and Testing10205 000
    Let xx be the number of 'Super X' and yy be the number of 'Super Y' models manufactured per month.
    1. Write down the set of constraint inequalities.
    2. Use the graph paper provided to represent the constraint inequalities.
    3. Shade the feasible region on the graph paper.
    4. Write down the profit generated in terms of xx and yy.
    5. How many motorcycles of each model must be produced in order to maximise the monthly profit?
    6. What is the maximum monthly profit?
  5. A group of students plan to sell xx hamburgers and yy chicken burgers at a rugby match. They have meat for at most 300 hamburgers and at most 400 chicken burgers. Each burger of both types is sold in a packet. There are 500 packets available. The demand is likely to be such that the number of chicken burgers sold is at least half the number of hamburgers sold.
    1. Write the constraint inequalities.
    2. Two constraint inequalities are shown on the graph paper provided. Represent the remaining constraint inequalities on the graph paper.
    3. Shade the feasible region on the graph paper.
    4. A profit of R3 is made on each hamburger sold and R2 on each chicken burger sold. Write the equation which represents the total profit, P, in terms of xx and yy.
    5. The objective is to maximise profit. How many, of each type of burger, should be sold to maximise profit?
  6. Fashion-cards is a small company that makes two types of cards, type X and type Y. With the available labour and material, the company can make not more than 150 cards of type X and not more than 120 cards of type Y per week. Altogether they cannot make more than 200 cards per week. There is an order for at least 40 type X cards and 10 type Y cards per week. Fashion-cards makes a profit of R5 for each type X card sold and R10 for each type Y card. Let the number of type X cards be xx and the number of type Y cards be yy, manufactured per week.
    1. One of the constraint inequalities which represents the restrictions above is x≤150x≤150. Write the other constraint inequalities.
    2. Represent the constraints graphically and shade the feasible region.
    3. Write the equation that represents the profit P (the objective function), in terms of xx and yy.
    4. Calculate the maximum weekly profit.
  7. To meet the requirements of a specialised diet a meal is prepared by mixing two types of cereal, Vuka and Molo. The mixture must contain xx packets of Vuka cereal and yy packets of Molo cereal. The meal requires at least 15 g of protein and at least 72 g of carbohydrates. Each packet of Vuka cereal contains 4 g of protein and 16 g of carbohydrates. Each packet of Molo cereal contains 3 g of protein and 24 g of carbohydrates. There are at most 5 packets of cereal available. The feasible region is shaded on the attached graph paper.
    1. Write down the constraint inequalities.
    2. If Vuka cereal costs R6 per packet and Molo cereal also costs R6 per packet, use the graph to determine how many packets of each cereal must be used for the mixture to satisfy the above constraints in each of the following cases:
      1. The total cost is a minimum.
      2. The total cost is a maximum (give all possibilities).
    Figure 3
    Figure 3 (MG11C15_003.png)
  8. A bicycle manufacturer makes two different models of bicycles, namely mountain bikes and speed bikes. The bicycle manufacturer works under the following constraints: No more than 5 mountain bicycles can be assembled daily. No more than 3 speed bicycles can be assembled daily. It takes one man to assemble a mountain bicycle, two men to assemble a speed bicycle and there are 8 men working at the bicycle manufacturer. Let xx represent the number of mountain bicycles and let yy represent the number of speed bicycles.
    1. Determine algebraically the constraints that apply to this problem.
    2. Represent the constraints graphically on the graph paper.
    3. By means of shading, clearly indicate the feasible region on the graph.
    4. The profit on a mountain bicycle is R200 and the profit on a speed bicycle is R600. Write down an expression to represent the profit on the bicycles.
    5. Determine the number of each model bicycle that would maximise the profit to the manufacturer.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks