# Connexions

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

### 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?

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

#### Endorsed by (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

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

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

"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

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

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

Inside Collection:

Collection by: Rupinder Sekhon. E-mail the author

# 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?

### 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?

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)

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?

### 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?

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

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

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

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

PDF | EPUB (?)

### What is an EPUB file?

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

#### 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?

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?

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

### Reuse / Edit:

Reuse or edit collection (?)

#### Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

#### Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.

| Reuse or edit module (?)

#### Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

#### Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.