Arizona State University



Mat 211

Dr. Firoz

4: Linear Programming 6: Sets and Counting

Linear Programming

1. Graph the system of inequalities and list all corner points of your feasible region.

[pic]

2. Find the minimum value of the objective function [pic], subject to the given constraints: Show complete work.

[pic]

3. Minimize [pic] subject to [pic]. Use linear programming. Clearly mark the feasible region and the corner points.

4. Identify the feasible region and the corner points: [pic]

5. Minimize [pic] subject to [pic]. Use linear programming. Clearly mark the feasible region and the corner points.

6. Identify the feasible region and the corner points: [pic]

7. Minimize [pic] subject to [pic]. Use linear programming. Clearly mark the feasible region and the corner points.

8. Minimize [pic] subject to [pic]

9. Find both max and min of [pic] subject to [pic]

10. Determine maximum of [pic]

Subject to [pic]

11. Identify the feasible region and the corner points: [pic]

12. A small construction company specializes in building and selling single family homes. The firms offer two basic types of houses. Model A houses requires 4000 labor hours, 2 tons of stone, and 2000 board feet of lumber. Model B houses require 10000 labor hours, 3 tones of stone, and 2000 board feet of lumber. Due to long lead-time for ordering supplies and scarcity of skilled and semi-skilled workers in the area, the firm will be forced to rely on its present resources for upcoming building season. It has 400000 hours of labor, 150 tones of stone, and 200000 board feet of lumber. What mix of Model A and Model B houses should the company construct, if Model A yields a profit of $10000 per unit and Model B yields $12000 per unit. Assume that the company sells all the units they construct. Use linear programming, Make graph of the feasible region, label all constraints, objective function and table showing all corner points along with amount of profit.

13. You manage an ice cream factory that makes two flavors: Creamy Vanilla and Continental Mocha. Into each quart of Creamy Vanilla go two eggs and three cups of cream. Into each quart of Continental Mocha go one egg and three cups of cream. You have in stock 500 eggs and 900 cups of cream. Draw the feasible region showing the number of quarts of vanilla and number of quarts of mocha that can be produced. Find the corner points of the region. If each Creamy Vanilla is sold at $1.50 and each Continental Mocha is sold at $1.25, find the maximum revenue if all those ice creams are sold. Answer: max at (200, 100)

14. A company manufactures two types fancy wooden display cabinets. Each cabinet undergoes cutting (of raw materials), sanding and assembly, all of which are handled by machines. Cabinet A requires 2 hours of cutting, 1 hour of sanding and 1 hour of assembly, while cabinet B requires 1 hour of cutting, 1 hour of sanding and 3 hours of assembly. The cutting machine can be used at most 70 hours per week, the sander at most 40 hours and the assembler at most 90 hours. Cabinet A sells at a $40 profit and cabinet B sells at a $60 profit. How many cabinets A and B should be produced to maximize profit?

Hint: Objective function: [pic]

With constraints

[pic]

Determine the following corner points (0, 0), (0, 30), (15, 25), (30, 10) and (35, 0) from your feasible region. The maximum is found at (15, 25) which is equal to $2100.

15. A company produces two types of jeans, each of which goes through three manufacturing phases - cutting, sewing, and finishing. The regular jeans require 2 hours of cutting, 1 hour of sewing, and 1 hour of finishing. The low-rise jeans require 1 hour of cutting, 2 hours of sewing, and 3 hours of finishing. There are 70 hours of cutting time, 50 hours of sewing time, and 90 hours of finishing time each week. They make a profit of $13 on each pair of classic jeans and $17 on each pair of low-rise jeans. Assuming that all the jeans produced can be sold, determine the number of jeans of each type that should be made each week in order to maximize profit.

(a) Clearly define your variables and write the objective function, P, to be maximized in the above problem.

(b) Write down all the constraints.

(c) Graph the feasible region. (Clearly label your graph with the axis, scale, lines.)

d) List all corner points of the feasible region, and label them on the graph.

e) Use your answer to part (d) to maximize the objective function. Write out and box the solution.

6: Sets and Counting

Definition

Set A set is a collection of well-defined and well-distinguished elements of any nature.

If a, b, c, d, e are the elements of a set A then we write [pic]

Subsets For two sets A and B if all elements of the set B are also the elements of A then B is called the subset of A and we write [pic].

Null Set A set containing no element in it is called a null set or void set or empty set. Two sets are called mutually exclusive or disjoint if they do not have common elements.

Cardinal Number The total number of elements in set is called its cardinal number. For the set [pic], the cardinal number is 5 and we write [pic]

Operations on sets

For two sets A and B we have the following operations:

Union the union for two sets A and B denoted by[pic]is the set of all elements in A or in B. Suppose that [pic] then either [pic]belongs to both A and B.

Intersection the intersection for two sets A and B denoted by[pic]is the set of all elements in A and in B. Suppose that [pic] then [pic] and [pic]. For mutually exclusive sets C and D we have [pic]

Difference For two sets A and B, [pic]is a set of all elements in A but not in B.

Complement of a set Suppose U is a universal set and A is its subset. The set [pic] is the set with all elements in U but not in A is the complement of A. In this case A is the proper subset of U. Notice that [pic] the null set.

Cardinal number in a set which is a union of two sets:

[pic]

Venn Diagram The pictorial representation of elements of sets is called a Venn Diagram (after the name of an English logician John Venn 1834-1923). We will discuss more on Venn diagram in the class.

Examples:

1. Given [pic]. Find i) [pic]

ii) [pic]

2. List all subsets of [pic]; find also the cardinal number of the set of all such subsets.

3. Given [pic], find [pic]

4. Let [pic], find the following:

a) [pic] b) [pic] c) [pic] d) [pic]

Solution: a) [pic]; all in A and B

b) [pic]; common elements in A and B

c) [pic]; elements in A but not in B

d) [pic]

5. If the universal set is [pic] and [pic]then find [pic] and [pic]

Solution: [pic]; and now [pic]

6. Use appropriate examples to prove that [pic]

Solution: We consider [pic], and [pic]. Then we have the following [pic] and [pic]

Now [pic]

2 = 5 + 4 – 7 is true √

7. Prove logically the DeMorgan’s laws: [pic] and [pic]

8. Survey questions: use Venn diagram

a) A department store surveyed 428 shoppers, and the following information was obtained: 214 made a purchase, and 299 were satisfied with the service they received. If 52 of those who made a purchase were not satisfied with the service, find the probability of how many shoppers did the following?

i) made a purchase and were satisfied with the service 162

ii) made a purchase or were satisfied with the service 351

iii) were satisfied with the service but did not make a purchase 137

iv) were not satisfied and did not make a purchase 77

b) The given data indicates that on average, out of every 100 people in the United States, 40 have the A molecule, 15 have the B molecule, and 45 have neither the A nor the B molecule (O type). What percent of the U.S. population have the following blood type

i) Type O

ii) Type A

iii) Type B

iv) Type AB, where AB means A and B

c) A consumer survey was conducted to examine patterns in ownership of personal computers, cellular telephones, and DVD players. The following data were obtained: 213 people had personal computers, 294 had cellular telephones, 337 had DVD players, 109 had all three, 64 had none, 198 had cell phones and DVD players, 382 had cell phone or computers, and 61 had computers and DVD players but no cell phones.

i) What percent of the people surveyed owned a computer but no DVD player or cell phone?

ii) What percent of the people surveyed owned a DVD but no computer or cell phone?

9. In a consumer survey of 500 people, 200 indicated that they would be buying a major appliance within next month, 150 indicated that they would buy a car, and 25 said that they would purchase both a major appliance and a car. How many will purchase neither? How many will purchase only a car? How many will purchase either a car or a major appliance? What percent of the consumers exactly purchased only one (either a car or a major appliance)?

Solution: purchase neither = 25

purchase only a car = 125 Car MA

purchase either a car or a major appliance

= 125 + 25 + 175 = 325 125 25 175

percent of the consumers exactly purchased

only one = [pic] 175

10. A survey of 50 people had the following results: In the past year, 25 of those surveyed had been to Los Angeles, 19 had been to San Diego and 23 had been to Las Vegas. 10 had been to both Los Angeles and Las Vegas, 9 to both Los Angeles and San Diego, and 8 to both Las Vegas and San Diego. 5 people had been to all three places.

a) Fill in this Venn Diagram based on the survey’s results:

[pic]

b) How many people had been to neither of the three cities?

c) How many people had been to exactly two of the cities?

d) How many people had been to at most one of the cities?

e) What is the probability a randomly selected person had been to just Las Vegas?

11. Cartesian Product: The Cartesian product of two sets A and B is the set of all ordered pairs (a, b) with [pic] and we write as follows:

[pic]

12. If [pic] and [pic] then [pic] and [pic]

Introduction to Combinatorics (Counting Technique)

The fundamental concept of counting, permutations and combinations collectively are called Combinatorics.

The fundamental counting principle

If you have two T-shirts, two pairs of shoes and three pairs of jeans, how many different outfits can you have? To answer this question one may use the following tree diagram

Jeans 1

Shoes 1

Jeans 2

T-shirt 1

Jeans 1

Shoes 2

Jeans 2

Start

Jeans 1

Shoes 1

Jeans 2

T-shirt 2

Jeans 1

Shoes 2

Jeans 2

One can easily find that there are 8 possible outfits available namely T-shirt 1, Shoes 1, Jeans 1 (which is one outfit). Another choice would be like T-shirt 1, Shoes 1, Jeans 2 etc.

Using multiplication principle we can see that the total number of outfits = [pic]

Thus the principle is summarized below:

The total number of possible outcomes of a series of decisions is found by multiplying the number of choices for each decision as follows

1. Draw a box for each decision

2. Enter the number of choices for each decision in the appropriate box and multiply

Examples:

1. Five different mathematics books are to be arranged on a desk. How many different arrangements are possible? Answer 120

Solution: We make five boxes as follows and insert possible choices in each case. The books cannot be repeated. There are 5 choices for the first box, 4 choices for the second box and so on. The total number of choices equals [pic]

5 4 3 2 1

2. How many license plates consisting of 2 letters followed by 2 digits are possible? Answer 67600

3. How many different license plates can be made using 2 letters followed by 4 digits, if

a. Letters and digits may be repeated. Answer [pic]

b. Letters may be repeated, but digits are not repeated. Answer [pic]

c. Neither letters nor digits are repeated. Answer 3276000

4. Students log on to the California Virtual In Campus with a user name consisting of eight characters: four upper case letters followed by four digits.

a. How many user names are theoretically possible? Answer [pic]

b. How many users names for this system have no matching adjacent letters or digits? Answer [pic]

5. Find the number of 7-digit telephone numbers

a. With no repeated digits (lead 0 is allowed). Answer 604800

b. With no repeated digits (lead 0 is not allowed). Answer 544320

c. With repeated digits allowed including a lead 0. Answer [pic]

6. Each student at State University has a student I. D. number consisting of

four digits (the first digit is nonzero and digits may be repeated) followed by

three of the letters A, B, C, D, and E (letters may not be repeated). How

many different student numbers are possible?

Answer [pic]

Factorials: In example 1, we have seen that the total number ways that 5 books can be put in a shelf is [pic] which can also be written as [pic]

General form [pic]

Note that [pic]. Proof is kept as an exercise. Hint: Use [pic] where n is a positive integer.

7. Simplify [pic]. Your calculator will fail, but you don’t.

8. Simplify [pic]

9. Find when [pic]

Permutations: When more than one item is selected (without replacement) from a single category, and the order of selection is important, the various possible outcomes are called permutations. If you are using TI calculator, you go to MATH PRB 2 for n P r. To find a permutation of 3 different object out of 5 is P(5,3). Using calculator you type 5 MATH PRB 2 3. Your calculator will return a result 60. Try.

General formula for permutations: If r items are selected form n different items (no repetition, order is important)

[pic]

Combinations: When more than one item is selected (without replacement) from a single category, and the order of selection is not important, the various possible outcomes are called combinations. If you are using TI calculator, you go to MATH PRB 3 for n C r. To find a combination of 3 different object out of 5 is C(5,3). Using calculator you type 5 MATH PRB 2 3. Your calculator will return a result 10. Try.

1. How many ways in a group of three people have different birthdays? Assume there are 365 days in a year. Answer [pic]

2. How many ways are there to seat 5 people in 8 chairs? Answer [pic]

3. From 5 faculty members, a committee of 2 is to be formed. In how many ways can this be done? Answer 10

4. From 6 men and 5 women, a 5-member committee is to be formed. In how many ways this can be formed if no more than 3 women are in the committee?

Hint: C(6,5)+C(6,4)C(5,1)+C(6,3)C(5,2)+C(6,2)C(5,3)

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download