Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Applied Finite Mathematics » Linear Programming: A Geometric Approach

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 ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
  • College Open Textbooks display tagshide tags

    This collection is included inLens: Community College Open Textbook Collaborative
    By: CC Open Textbook Collaborative

    Comments:

    "Reviewer's Comments: 'I recommend this book for undergraduates. The content is especially useful for those in finance, probability statistics, and linear programming. The course material is […]"

    Click the "College Open Textbooks" link to see all content they endorse.

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

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.
  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    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.

  • Featured Content display tagshide tags

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Comments:

    "Applied Finite Mathematics covers topics including linear equations, matrices, linear programming, the mathematics of finance, sets and counting, probability, Markov chains, and game theory."

    Click the "Featured Content" 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.
 

Linear Programming: A Geometric Approach

Module by: Rupinder Sekhon. E-mail the author

Summary: This chapter covers principles of a geometrical approach to linear programming. After completing this chapter students should be able to: solve linear programming problems that maximize the objective function and solve linear programming problems that minimize the objective function.

Chapter Overview

In this chapter, you will learn to:

  1. Solve linear programming problems that maximize the objective function.
  2. Solve linear programming problems that minimize the objective function.

Maximization Applications

Application problems in business, economics, and social and life sciences often ask us to make decisions on the basis of certain conditions. These conditions or constraints often take the form of inequalities. In this section, we will look at such problems.

A typical linear programming problem consists of finding an extreme value of a linear function subject to certain constraints. We are either trying to maximize or minimize our function. That is why these linear programming problems are classified as maximization or minimization problems, or just optimization problems. The function we are trying to optimize is called an objective function, and the conditions that must be satisfied are called constraints. In this chapter, we will do problems that involve only two variables, and therefore, can be solved by graphing. We begin by solving a maximization problem.

Example 1

Problem 1

Niki holds two part-time jobs, Job I and Job II. She never wants to work more than a total of 12 hours a week. She has determined that for every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation. If she makes $40 an hour at Job I, and $30 an hour at Job II, how many hours should she work per week at each job to maximize her income?

Solution

We start by choosing our variables.

Let x=The number of hours per week Niki will work at Job I.x=The number of hours per week Niki will work at Job I. size 12{x="The number of hours per week Niki will work at Job I" "." } {}

and y=The number of hours per week Niki will work at Job II.y=The number of hours per week Niki will work at Job II. size 12{y="The number of hours per week Niki will work at Job II" "." } {}

Now we write the objective function. Since Niki gets paid $40 an hour at Job I, and $30 an hour at Job II, her total income I is given by the following equation.

I=40x+30yI=40x+30y size 12{I="40"x+"30"y} {}
(1)

Our next task is to find the constraints. The second sentence in the problem states, "She never wants to work more than a total of 12 hours a week." This translates into the following constraint:

x+y12x+y12 size 12{x+y <= "12"} {}
(2)

The third sentence states, "For every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation." The translation follows.

2x+y162x+y16 size 12{2x+y <= "16"} {}
(3)

The fact that xx size 12{x} {} and yy size 12{y} {} can never be negative is represented by the following two constraints:

x0x0 size 12{x >= 0} {}, and y0y0 size 12{y >= 0} {}.

Well, good news! We have formulated the problem. We restate it as

Maximize I = 40 x + 30 y I = 40 x + 30 y size 12{I="40"x+"30"y} {}

Subject to: x + y 12 x + y 12 size 12{x+y <= "12"} {}

2x+y162x+y16 size 12{2x+y <= "16"} {}
(4)
x0;y0x0;y0 size 12{x >= 0;``y >= 0} {}
(5)

In order to solve the problem, we graph the constraints as follows.

Figure 1
 The graph shows that the lines 2x+y=16 and x+y+12 intersect at the point (4,8). The shaded region represents the area of the graph that meets the required conditions.

Observe that we have shaded the region where all conditions are satisfied. This region is called the feasibility region or the feasibility polygon.

The Fundamental Theorem of Linear Programming states that the maximum (or minimum) value of the objective function always takes place at the vertices of the feasibility region.

Therefore, we will identify all the vertices of the feasibility region. We call these points critical points. They are listed as (0, 0), (0, 12), (4, 8), (8, 0). To maximize Niki's income, we will substitute these points in the objective function to see which point gives us the highest income per week. We list the results below.

Table 1
Critical Points Income
(0,0) 40 ( 0 ) + 30 ( 0 ) = $ 0 40 ( 0 ) + 30 ( 0 ) = $ 0 size 12{"40" \( 0 \) +"30" \( 0 \) =$0} {}
(0.12) 40 ( 0 ) + 30 ( 12 ) = $ 360 40 ( 0 ) + 30 ( 12 ) = $ 360 size 12{"40" \( 0 \) +"30" \( "12" \) =$"360"} {}
(4,8) 40 ( 4 ) + 30 ( 8 ) = $ 400 40 ( 4 ) + 30 ( 8 ) = $ 400 size 12{"40" \( 4 \) +"30" \( 8 \) =$"400"} {}
(8,0) 40 ( 8 ) + 30 ( 0 ) = $ 320 40 ( 8 ) + 30 ( 0 ) = $ 320 size 12{"40" \( 8 \) +"30" \( 0 \) =$"320"} {}

Clearly, the point (4, 8) gives the most profit: $400.

Therefore, we conclude that Niki should work 4 hours at Job I, and 8 hours at Job II.

Example 2

Problem 1

A factory manufactures two types of gadgets, regular and premium. Each gadget requires the use of two operations, assembly and finishing, and there are at most 12 hours available for each operation. A regular gadget requires 1 hour of assembly and 2 hours of finishing, while a premium gadget needs 2 hours of assembly and 1 hour of finishing. Due to other restrictions, the company can make at most 7 gadgets a day. If a profit of $20 is realized for each regular gadget and $30 for a premium gadget, how many of each should be manufactured to maximize profit?

Solution

We choose our variables.

Let x=The number of regular gadgets manufactured each day.x=The number of regular gadgets manufactured each day. size 12{x="The number of regular gadgets manufactured each day" "." } {}

and y=The number of premium gadgets manufactured each day.y=The number of premium gadgets manufactured each day. size 12{y="The number of premium gadgets manufactured each day" "." } {}

The objective function is

P=20x+30yP=20x+30y size 12{P="20"x+"30"y} {}
(6)

We now write the constraints. The fourth sentence states that the company can make at most 7 gadgets a day. This translates as

x+y7x+y7 size 12{x+y <= 7} {}
(7)

Since the regular gadget requires one hour of assembly and the premium gadget requires two hours of assembly, and there are at most 12 hours available for this operation, we get

x+2y12x+2y12 size 12{x+2y <= "12"} {}
(8)

Similarly, the regular gadget requires two hours of finishing and the premium gadget one hour. Again, there are at most 12 hours available for finishing. This gives us the following constraint.

2x+y122x+y12 size 12{2x+y <= "12"} {}
(9)

The fact that xx size 12{x} {} and yy size 12{y} {} can never be negative is represented by the following two constraints:

x0x0 size 12{x >= 0} {}, and y0y0 size 12{y >= 0} {}.

We have formulated the problem as follows:

Maximize P = 20 x + 30 y P = 20 x + 30 y size 12{P="20"x+"30"y} {}

Subject to: x + y 7 x + y 7 size 12{x+y <= 7} {}

x+2y12x+2y12 size 12{x+2y <= "12"} {}
(10)
2x+y122x+y12 size 12{2x+y <= "12"} {}
(11)
x0;y0x0;y0 size 12{x >= 0;y >= 0} {}
(12)

In order to solve the problem, we graph the constraints as follows:

Figure 2
 The graph shows that the line x+y=7 intersects the line 2x+y=12 at point (5,2) and also intersects the line x+2y=12 at the point (2,5). The shaded region represents the area of the graph that meets the required conditions.

Again, we have shaded the feasibility region, where all constraints are satisfied.

Since the extreme value of the objective function always takes place at the vertices of the feasibility region, we identify all the critical points. They are listed as (0, 0), (0, 6), (2, 5), (5, 2), and (6, 0). To maximize profit, we will substitute these points in the objective function to see which point gives us the maximum profit each day. The results are listed below.

Table 2
Critical point Income
(0,0) 20 ( 0 ) + 30 ( 0 ) = $ 0 20 ( 0 ) + 30 ( 0 ) = $ 0 size 12{"20" \( 0 \) +"30" \( 0 \) =$0} {}
(0,6) 20 ( 0 ) + 30 ( 6 ) = $ 180 20 ( 0 ) + 30 ( 6 ) = $ 180 size 12{"20" \( 0 \) +"30" \( 6 \) =$"180"} {}
(2,5) 20 ( 2 ) + 30 ( 5 ) = $ 190 20 ( 2 ) + 30 ( 5 ) = $ 190 size 12{"20" \( 2 \) +"30" \( 5 \) =$"190"} {}
(5,2) 20 ( 5 ) + 30 ( 2 ) = $ 160 20 ( 5 ) + 30 ( 2 ) = $ 160 size 12{"20" \( 5 \) +"30" \( 2 \) =$"160"} {}
(6,0) 20 ( 6 ) + 30 ( 0 ) = $ 120 20 ( 6 ) + 30 ( 0 ) = $ 120 size 12{"20" \( 6 \) +"30" \( 0 \) =$"120"} {}

The point (2, 5) gives the most profit, and that profit is $190. Therefore, we conclude that we should manufacture 2 regular gadgets and 5 premium gadgets daily for a profit of $190.

Although we are mostly focusing on the standard maximization problems where all constraints are of the form ax+by0ax+by0 size 12{ ital "ax"+ ital "by" <= 0} {}, we will now consider an example where that is not the case.

Example 3

Problem 1

Solve the following maximization problem graphically.

Maximize P = 10 x + 15 y P = 10 x + 15 y size 12{P="10"x+"15"y} {}

Subject to: x + y 1 x + y 1 size 12{x+y >= 1} {}

x+2y6x+2y6 size 12{x+2y <= 6} {}
(13)
2x+y62x+y6 size 12{2x+y <= 6} {}
(14)
x0;y0x0;y0 size 12{x >= 0;y >= 0} {}
(15)
Solution

The graph is shown below.

Figure 3
The graph shows that the line x+y=1 passes through the points, (0,1) and (1,0). The lines 2x+y=6 and x+2y=6 intersect at (2,2).The shaded region represents the area of the graph that meets the required conditions.

The five critical points are listed in the above figure. Clearly, the point (2, 2) maximizes the objective function to a maximum value of 50. The reader should observe that the first constraint x+y1x+y1 requires that feasibility region must be bounded below by the line x+y=1x+y=1.

Finally, we address an important question. Is it possible to determine the point that gives the maximum value without calculating the value at each critical point?

The answer is yes.

For example, in the above problem, we substituted the points (0, 0), (0, 6), (2, 5), (5, 2), and (6, 0), in the objective function P=20x+30yP=20x+30y size 12{P="20"x+"30"y} {}, and we got the values $0, $180, $190, $160, $120, respectively. Sometimes that is not the most efficient way of finding the optimum solution.

To determine the largest PP size 12{P} {}, we graph P=20x+30yP=20x+30y size 12{P="20"x+"30"y} {} for any value PP size 12{P} {} of our choice. Let us say, we choose P=60P=60 size 12{P="60"} {}. We graph 20x+30y=6020x+30y=60 size 12{"20"x+"30"y="60"} {}. Now we move the line parallel to itself, that is, keeping the same slope at all times. Since we are moving the line parallel to itself, the slope is kept the same, and the only thing that is changing is the PP size 12{P} {}. As we move away from the origin, the value of PP size 12{P} {} increases. The largest value of PP size 12{P} {} is realized when the line touches the last corner point. The figure below shows the movements of the line, and the optimum solution is achieved at the point (2, 5). In maximization problems, as the line is being moved away from the origin, this optimum point is the farthest critical point.

Figure 4
The graph shows that the line x+y=7 intersects the line 2x+y=12 at the point, (5,2), and the line x+2y=12 at the point, (2,5).

We summarize:

The Maximization Linear Programming Problems

  1. Write the objective function.
  2. Write the constraints.
    1. a) For the standard maximization linear programming problems, constraints are of the form: ax+bycax+byc size 12{ ital "ax"+ ital "by" <= c} {}
    2. b) Since the variables are non-negative, we include the constraints: x0;y0x0;y0 size 12{x >= 0;y >= 0} {}.
  3. Graph the constraints.
  4. Shade the feasibility region.
  5. Find the corner points.
  6. Determine the corner point that gives the maximum value.
    1. a) This is done by finding the value of the objective function at each corner point.
    2. b) This can also be done by moving the line associated with the objective function.

Minimization Applications

Minimization linear programming problems are solved in much the same way as the maximization problems. For the standard minimization linear programming problem, the constraints are of the form ax+bycax+byc size 12{ ital "ax"+ ital "by" >= c} {}, as opposed to the form ax+bycax+byc size 12{ ital "ax"+ ital "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 unbounded. But that is not a concern, since in order to minimize the objective function, the line associated with the objective function is moved towards 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 unbounded feasibility region, the possibility of no optimal solution exists.

Example 5

Problem 1

Professor Symons wishes to employ two students, John and Mary, to grade the homework papers for his classes. John can mark 20 papers per hour and charges $5 per hour, and Mary can mark 30 papers per hour and charges $8 per hour. Each student must be employed at least one hour a week to justify their employment. If Mr. Symons has at least 110 homework papers to be marked each week, how many hours per week should he employ each student to minimize his cost?

Solution

We choose the variables as follows:

Let x=The number of hours per week John is employed.x=The number of hours per week John is employed. size 12{x="The number of hours per week John is employed" "." } {}

and y=The number of hours per week Mary is employed.y=The number of hours per week Mary is employed. size 12{y="The number of hours per week Mary is employed" "." } {}

The objective function is

C=5x+8yC=5x+8y size 12{C=5x+8y} {}
(16)

The fact that each student must work at least one hour each week results in the following two constraints:

x1x1 size 12{x >= 1} {}
(17)
y1y1 size 12{y >= 1} {}
(18)

Since John can grade 20 papers per hour and Mary 30 papers per hour, and there are at least 110 papers to be graded per week, we get

20x+30y11020x+30y110 size 12{"20"x+"30"y >= "110"} {}
(19)

The fact that x and y are non-negative, we get

x0x0 size 12{x >= 0} {}, and y0y0 size 12{y >= 0} {}.

The problem has been formulated as follows.

Minimize C = 5x + 8y C = 5x + 8y size 12{C=5x+8y} {}

Subject to: x 1 x 1 size 12{x >= 1} {}

y1y1 size 12{y >= 1} {}
(20)
20x+30y11020x+30y110 size 12{"20"x+"30"y >= "110"} {}
(21)
x0;y0x0;y0 size 12{x >= 0;y >= 0} {}
(22)

To solve the problem, we graph the constraints as follows:

Figure 5
The graph shows that the line 20x+30y=110 intersects the line x=1 at the point, (1,3) and the line y=1 at the point, (4,1).The shaded region represents the area of the graph that meets the required conditions.

Again, we have shaded the feasibility region, where all constraints are satisfied.

Since the extreme value of the objective function always takes place at the vertices of the feasibility region, we identify the two critical points, (1, 3) and (4, 1). To minimize cost, we will substitute these points in the objective function to see which point gives us the minimum cost each week. The results are listed below.

Table 3
Critical Points Income
(1,3) 5 ( 1 ) + 8 ( 3 ) = $ 29 5 ( 1 ) + 8 ( 3 ) = $ 29 size 12{5 \( 1 \) +8 \( 3 \) =$"29"} {}
(4,1) 5 ( 4 ) + 8 ( 1 ) = $ 28 5 ( 4 ) + 8 ( 1 ) = $ 28 size 12{5 \( 4 \) +8 \( 1 \) =$"28"} {}

The point (4, 1) gives the least cost, and that cost is $28. Therefore, we conclude that Professor Symons should employ John 4 hours a week, and Mary 1 hour a week at a cost of $28 per week.

Example 6

Problem 1

Professor Hamer is on a low cholesterol diet. During lunch at the college cafeteria, he always chooses between two meals, Pasta or Tofu. The table below lists the amount of protein, carbohydrates, and vitamins each meal provides along with the amount of cholesterol he is trying to minimize. Mr. Hamer needs at least 200 grams of protein, 960 grams of carbohydrates, and 40 grams of vitamins for lunch each month. Over this time period, how many days should he have the Pasta meal, and how many days the Tofu meal so that he gets the adequate amount of protein, carbohydrates, and vitamins and at the same time minimizes his cholesterol intake?

Table 4
  Pasta Tofu
Protein 8g 16g
Carbohydrates 60g 40g
Vitamin C 2g 2g
Cholesterol 60mg 50mg
Solution

We choose the variables as follows.

Let x = The number of days Mr. Hamer eats Pasta.

and y = The number of days Mr. Hamer eats Tofu.

Since he is trying to minimize his cholesterol intake, our objective function represents the total amount of cholesterol C provided by both meals.

C=60x+50yC=60x+50y
(23)

The constraint associated with the total amount of protein provided by both meals is as follows:

8x+16y2008x+16y200
(24)

Similarly, the two constraints associated with the total amount of carbohydrates and vitamins are obtained, and they are

60x+40y96060x+40y960
(25)
2x+2y402x+2y40
(26)

The constraints that state that x and y are non-negative are

x0,andy0x0,andy0
(27)

We summarize all information as follows:

Minimize C=60x+50yC=60x+50y

Subject to: 8x+16y2008x+16y200

60x+40y96060x+40y960
(28)
2x+2y402x+2y40
(29)
x0;y0x0;y0
(30)

To solve the problem, we graph the constraints as follows.

Figure 6
The graph shows that the line 2x+2y=40 intersects the line 60x+40y=960 at the point, (8,12,) while intersecting the line x+2y=25 at the point, (15,5). The shaded region represents the area of the graph that meets the required conditions.

Again, we have shaded the unbounded feasibility region, where all constraints are satisfied.

To minimize the objective function, we find the vertices of the feasibility region. These vertices are (0, 24), (8, 12), (15, 5) and (25, 0). To minimize cholesterol, we will substitute these points in the objective function to see which point gives us the smallest value. The results are listed below.

Table 5
Critical Points Income
(0,24) 60 ( 0 ) + 50 ( 24 ) = 1200 60 ( 0 ) + 50 ( 24 ) = 1200 size 12{"60" \( 0 \) +"50" \( "24" \) ="1200"} {}
(8,12) 60 ( 8 ) + 50 ( 12 ) = 1080 60 ( 8 ) + 50 ( 12 ) = 1080 size 12{"60" \( 8 \) +"50" \( "12" \) ="1080"} {}
(15,5) 60 ( 15 ) + 50 ( 5 ) = 1150 60 ( 15 ) + 50 ( 5 ) = 1150 size 12{"60" \( "15" \) +"50" \( 5 \) ="1150"} {}
(25,0) 60 ( 25 ) + 50 ( 0 ) = 1500 60 ( 25 ) + 50 ( 0 ) = 1500 size 12{"60" \( "25" \) +"50" \( 0 \) ="1500"} {}

The point (8, 12) gives the least cholesterol, which is 1080 mg. This states that for every 20 meals, Professor Hamer should eat Pasta 8 days, and Tofu 12 days.

Although the method of solving minimization problems is similar to that of the maximization problems, we still feel that we should summarize the steps involved.

Minimization Linear Programming Problems

  1. Write the objective function.
  2. Write the constraints.
    1. a) For standard minimization linear programming problems, constraints are of the form: ax+bycax+byc size 12{ ital "ax"+ ital "by" >= c} {}
    2. b) Since the variables are non-negative, include the constraints: x0x0 size 12{x >= 0} {}; y0y0 size 12{y >= 0} {}.
  3. Graph the constraints.
  4. Shade the feasibility region.
  5. Find the corner points.
  6. Determine the corner point that gives the minimum value.
    1. a) This can be done by finding the value of the objective function at each corner point.
    2. b) This can also be done by moving the line associated with the objective function.
    3. c) There is the possibility that the problem has no solution.

Collection Navigation

Content actions

Download:

Collection 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 ...

Module as:

PDF | More downloads ...

Add:

Collection 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

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