Math 132 Notes

UNLV
Department of Mathematical Sciences

MATH 132 - Finite Mathematics Notes
Steven T. Fisher
Graduate Assistant
November 2, 2010
1
3 3
UNLV
MATH 132 - Finite Mathematics Notes
Preface
Over the last couple of years I have been teaching MATH 132. In this process I have compiled a list of
typed-up notes. Granted these notes are not perfect, nor necessarily complete. I have primarily taken the
necessary information from each section and collected it into one place. For the most part I have excluded
examples, unless I felt that they were necessary to show particular concepts. I feel that there are plenty
of examples in the text for the students to look at on their own, and the examples I do in class are from
the problems in the textbook.
It is advised to cover chapter 6, 7, and 8, then cover 1, 3, 2, and 4. This is how the online homework is
done. In 1.2 I have included the concept of perpendicular lines, which has been exclude in the text. Also,
note that in 4.2 and 4.3, my method for nding the pivot element diers than the textbook. The method
that I use was from the previous edition. It is up to you whether you wish to include it in your class. As
far as classroom management goes, I usually have students work problems in class and then present them
to the rest of the class. This way you are able to determine where a student might have a problem and
correct it in class instead of the student nding out during the homework.
Chapters 3 and 4 deal with linear programming problems. In my experience students tend to have trouble
setting up the application problems. They often mix-up what the variables are suppose to be and get
confused in setting of the linear inequalities for the constraints. So, once I have shown them how to solve
the linear programming problems, I usually work with the students in class on how to set these problems
up. Paying particular attention to what the constraints will be and what the variables should represent.
In 6.6 the textbook gives the binomial theorem as
(x +y)
n
=
_
n
0
_
x
n
y
0
+
_
n
1
_
x
n1
y
1
+
_
n
2
_
x
n2
y
2
+ +
_
n
k
_
x
nk
y
k
+ +
_
n
n
_
x
0
y
n
In my notes I have stayed with how the previous addition stated it. I nd that this is less confusing to the
students.
These note are by no means perfect. I am constantly looking for ways to improve them. If you notice
anything that is incorrect or needs to be changed or added, please let me know. My email address is
sher18@unlv.nevada.edu.
v1.06 changes:
corrected some misspelled words
v1.05 changes:
changed the position of gures
added the values for the gure in 8.1
added a gure for 1.1
version 1.06 Page 2 of ??
3 3
UNLV
6.1: Sets: Union, Intersection, Venn Diagram
A. Denitions:
1. Set: any collection of objects
2. Roster Method: listing of the objects in the set
3. Rule Method (Set Builder Notation): Describing properties held by all members and no others.
4. Element: Member of a set.
5. Empty (null) set: Set with no elements. Notation: or {}
6. Equal Sets: two sets, A and B, are said to be equal if every element in A is also and element in B
and every element of B is also an element of A.
7. Subset (A B) any element in A is also an element in B. NOTE: it is possible for A = B.
8. Proper subset (A B): any element of A is also an element of B and there is at least one element
in B not in A.
9. Universal Set: Set of all objects being considered. The universal set is denoted by U.
10. Union (A B) : set of all elements in A OR B.
11. Intersection (A B) : set of all elements in both A AND B.
12. Disjoint sets:sets with no common elements. Therefore if A and B are two sets, then A and B are
disjoint if A B = .
13. Complement of a set (A) all elements in U but not A.
14. Venn Diagrams: provides a geometric intuition between relationships between sets.
15. Counting Principle: If A and B are two nite sets, then n(A B) = n(A) +n(B) n(A B)
16. De Morgans Properties:
(a) A B = A B
(b) A B = A B
B. Examples: Given U = {1, 2, 3, 4, 5, 6}, A = {2, 4, 5, 6} and B = {1, 2, 3, 5}.:
1. A B = {1, 2, 3, 4, 5, 6} = U
2. A B = {2, 5}
3. A = {1, 3}
3 3
4. A B = {1, 3, 4, 6}
5. A B= ? Nope
6. A U =? Yep
7. A B =
8. A B = {1, 3, 4, 6} by using De Morgans property with (4)
C. Venn Diagrams:
Two or more sets may be shown as circles enclosed in a rectangle, which represents the universal set. The
circles may or may not intersect depending upon the situation. The part of the circles which is the overlap
part represents the intersection of the two sets and the area inside each circle represents the elements of
that set so the total area inside the circles represents the union of the two sets. These Venn diagrams are
very helpful in determining the number of elements in the set.(6.2)
3 3
UNLV
6.2: The Number of Elements in a set
1. If A is any set, we denote the number of elements in the set by n(A). For example, if A =
{1, 2, 3, 4, 5, 6}, we can say that n(A) = 6.
2. If the number of elements in a set is zero or a counting number, then the set is nite. Otherwise the
set is innite.
3. The area of mathematics that deals with nite sets is called nite mathematics.
4. The counting formula, see 6.1, is n(A B) = n(A) + n(B) n(A B). This is a very important
formula.
(a) We can use Venn diagrams to assist in the counting of elements in a set
i. Draw the intersection of set in the Venn diagram
ii. Complete the innermost region (the one which represents the intersection of all sets)
iii. Work your way until you nd the number of elements in an individual set.
iv. Remember if n(A) = 22, n(B) = 12, and n(A B) = 6, That leaves only 16 elements in
the set A alone and only 6 elements in the set B alone.
3 3
UNLV
6.3: The Multiplication Principle
A. Introduction
1. Knowing how to count is one of the keys to being able to compute many of the probabilities in
chapter 7. Remember that to count means to nd the number of elements in a set, even in sets that
are too large to explicitly write down each element. It is the large sets, such as the set of possible
license plates or lottery picks) that drive the need for counting techniques. We have already seen
that Venn diagrams may be applied to specic types of counting problems. However, other counting
problems require more sophisticated techniques. Regardless of the counting technique applied,
(a) A counting problem always asks how many
(b) The answer is always found to be a non-negative integer(whole number) {0, 1, 2, 3, . . .}
2. The Multiplication Principle of Counting states: If a task consists of a sequence of choices in which
there are p selections for the rst choice, q selections for the second choice, r selections for the third
choice and so on, then the task of making these selections can be done in: p q r . . . dierent ways.
These selections can be depicted in a tree diagram (see pg. 332)
B. Examples:
1. If you have 4 coats and 2 hats, how many dierent coat and hat combinations can you make? 4 2 = 8
2. How many license plates can be made using 2 letters followed by 3 numbers? 2626101010 = 676, 000
3. 8 runners race against each other. How many ways are there of awarding them the rst-second and
third place medals?
(a) The rst place can be won by any of the 8 runners
(b) The second place can then be won by any of the 7 runners who did not win the rst place medal
(c) Third place can be won by any one of the remaining 6 runners.
(d) Hence the number of possible ways of awarding the medals is 8 7 6 = 336
3 3
UNLV
6.4: Permutations
A. Factorials
1. Before we begin, let us dene the factorial symbol represented by !. The symbol n! is read as
n factorial is dened as:
n! = n (n 1) (n 2) (n 3) . . . 1, where n is an interger 1
2. By denition 0! = 1
3. Example: Simplify:
8!
3!(83)!
=
87654321
32154321
= 56 or
8!
3!(83)!
=
8!
3!5!
=
8765!
3215!
= 56
B. Permutations
1. Permutation: an ordered arrangement of r objects chosen from n objects.
(a) The n objects are dierent and repetition is allowed in the selection of r of them(Distinct with
repetition)
(b) The n objects are dierent and repetition is not allowed in the selection of r of them(Distinct
without repetition)
2. Calculations:
(a) Permutations:(Distinct with repetition) = n
r
(b) Permutations:(Distinct with repetition) = P(n, r) =
n!
(n r)!
, where r n. REMEM-
BER: ORDER IS IMPORTANT
(c) Permutations:(Distinct using all of them) = n!
C. Examples:
1. Evaluate: P(6, 2) =
6!
(6 2)!
=
6!
4!
=
6 5 4!
4!
= 30
2. In how many ways can you arrange 5 books on a shelf? 5! = 120
3. In how many ways can 6 people be seated in 10 chairs?
P(10, 6) =
10!
(10 6)!
=
10!
4!
=
10 9 8 7 6 5 4!
4!
= 151200
3 3
UNLV
6.5: Combinations
A. Combinations
1. Combination: An arrangement of r objects chosen from n objects without regard to order.
(a) The symbol for combination of r objects chosen from n objects is C(n, r) where r n
(b) Combination of n objects taken r at a time = C(n, r) =
n!
(nr)!r!
REMEMBER: ORDER IS
NOT IMPORTANT
(c) The above formula is also equivalent to C(n, r) =
P(n,r)
r!
2. Permutation involving n objects that are not all dierent: The number of permutations of n objects,
of which n
1
are of one kind, n
2
are of a second kind, . . ., and n
k
are of a kth kind is given by
n!
n
1
!n
2
!n
3
! . . . n
k
!
where n
1
+n
2
+ n
k
= n
B. Examples:
1. Evaluate: C(6, 2) =
6!
(62)!2!
=
6!
4!2!
=
654!
4!2!
= 15
2. In how many ways can you deal a hand of 13 cards from a deck of 52 cards? C(52, 13) =
52!
(5213)!13!
=
52!
39!13!
= 635, 013, 559, 600
3. In how many ways can 3 people be chosen from 12 applicants? C(12, 3) =
12!
(123)!3!
=
12!
9!3!
=
1211109!
3219!
=
220
4. How many distinct words can be made using all the letters in the eight letter word BASEBALL?
8!
2!2!2!
= 5040
3 3
UNLV
6.6: The Binomial Theorem
A. Motivation
1. Our goal here is to nd a formula for expanding (a +b)
n
for positive integers n. Some examples are:
(a +b)
1
= a +b
(a +b)
2
= a
2
+ab +b
2
(a +b)
3
= a
3
+ 3a
2
b + 3ab
2
+b
3
(a +b)
4
= a
4
+ 4a
3
b + 6a
2
b
2
+ 4ab
3
+b
4
(a +b)
5
= a
5
+ 5a
4
b + 10a
3
b
2
+ 10a
2
b3 + 5ab
4
+b
5
2. Pascals Triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Notice that (except for the 1s) each number is the sum of the two numbers just above it. You should
now be able to write the next row . . ..
1 7 21 35 35 21 7 1
We can use Pascals triangle to expand any binomial but it would be helpful to have a more exact
formula so we could calculate any individual terms.
B. The Binomial Theorem
1. The Binomial Theorem: Let a and b be two real numbers. If n is a positive integer, we have
(a +b)
n
=
_
n
0
_
a
n
b
0
+
_
n
1
_
a
n1
b
1
+
_
n
2
_
a
n2
b
2
+ +
_
n
k
_
a
nk
b
k
+ +
_
n
n
_
a
0
b
n
where
_
n
r
_
= C(n, r) =
n!
(nr)!r!
. We call
_
n
r
_
the binomial coecient.
2. Properties of the Binomial Coecient
(a)
_
n
0
_
=
_
n
n
_
= 1
(b)
_
n
1
_
=
_
n
n1
_
= n
(c) In general
_
n
r
_
=
_
n
nr
_
(d)
_
n
k
_
=
_
n1
k
_
+
_
n1
k1
_
3 3
3. Theorem: A set with n elements has 2
n
subsets
4. Examples: Other than expansion we can nd other items of the expansion WITHOUT actually
expanding
(a) Lets now try to nd a particular coecient: Find the coecient of x
4
y
5
in the expansion of
(x +y)
9
. . . the coecient is
_
9
5
_
= 126
(b) How about the coecient of x
7
in the expansion of (x + 2)
12
?
_
12
5
_
x
7
(2)
5
= 792 32 = 25344.
3 3
UNLV
7.1: Sample Spaces and the Assignment of Probabilities
A. Denitions:
1. An experiment is any activity or procedure that produces distinct, well-dened possibilities called
outcomes which can be observed or measured, but which cannot be predicted with certainty.
2. Each outcome is an element in the universal set of all possible outcomes for the experiment.
3. The universal set is called the sample space.
(a) Example: A fair coin is tossed twice and the result of each toss is recorded. Find the sample
space of the result. S = {HH, HT, TH, TT}
B. Assignment of Probabilities
1. Suppose the sample space of an experiment has n outcomes given by S = {e
1
, e
2
, e
3
, . . . , e
n
}.
To each outcome we assign a real number P(e) which is called the probability of the outcome e. Then:
P(e
1
) 0, P(e
2
) 0, . . . , P(e
n
) 0 and P(e
1
) +P(e
2
) +. . . +P(e
n
) = 1
2. Example: A die is rolled. Find the sample space and assign probabilities:
S = {1, 2, 3, 4, 5, 6}, P(1) =
1
6
, P(2) =
1
6
, P(3) =
1
6
, P(4) =
1
6
, P(5) =
1
6
, P(6) =
1
6
3. Note: When the same probability is assigned to each outcome of a sample space, the outcomes are
said to be equally likely.
C. Formula:
1. P(E) =
(number of ways E can take place)
(number of outcomes)
=
n(E)
n(S)
2. Example: A bowl contains 4 red marbles, 7 green ones, 6 blue ones and 5 white marbles. If Jay
chooses one marble, nd the probability that:
(a) it is green:
7
12
(b) it is red:
4
22
=
2
11
(c) it is red or blue:
4+6
22
=
10
22
=
5
11
or
4
22
+
6
22
=
10
22
=
5
11
3 3
UNLV
7.2: Properties of the Probability of an Event
A. Denitions:
1. An event is any subset of the sample space. If an event has only one element, it is called a simple
event.
2. Two or more events of a sample space, S, are said to be mutually exclusive if and only if they have
no outcomes in common.
B. Formulas:
1. Probability of an event:
(a) If E = , the event is impossible so P(E) = P() = 0.
(b) If E = {e} is a simple event, then P(E) = P(e).
(c) If E = {e
1
, e
2
, . . . , e
n
}. Then P(E) = P(e
1
) +P(e
2
) +. . . +P(e
n
)
2. Probability of E and F if E and F are mutually exclusive.
P(E F) = P(E) +P(F), if E F =
3. The Additive Rule revisited:
P(E F) = P(E) +P(F) P(E F)
4. Properties of the Probability of and Event:
(a) 0 P(E) 1 for every event E in S
(b) P() = 0 and P(S) = 1
5. Probability of the Complement of and Event:
P(E) = 1 P(E)
6. odds
(a) If E is an event then the odds for E are
P(E)
P(E)
and the odds against E are
P(E)
P(E)
(b) Knowing odds, calculate probabilities: If the odds for E are a to b, then P(E) =
a
a +b
if the
odds against E are a to b, then P(E) =
b
a +b
(c) Example 1: If P(E) =
3
7
, then P(E) =
4
7
and the odds in favor of E are 3 : 4
(d) Example 2: If the odds against E are 6 : 5, then P(E) =
5
5 + 6
=
5
11
3 3
UNLV
7.3: Probability Problems Using Counting Techniques
A. Find the Probability of Events Using Counting Techniques
1. Suggested Sample Problems:# 7, 8, 10, 14(See part B), any from the applications and extensions
section
B. Birthday Problems
1. Derivation: Suppose that you are given a problem to nd the probability that in a group of r people
there are at least two people who have the same birthday (the same month and day of the year).
First, we need to determine the total number of outcomes in the sample space S. Now, there are
365 possibilities for each person to have a birthday. Since, there are r people in the group, there are
365
r
possibilities for birthdays. So,
n(S) = 365
r
We next need to determine the probability of event E:
E = At east two people have the same birthday
Now, it is dicult to count the elements in this set; it is much to count the elements of the comple-
ment:
E = No two people have the same birthday
In order to nd n(E) we know that for one of the people there are 365 possible birthdays, then for the
next there are 364 possible birthdays. Choosing a third person, we have 363 possible birthdays and
so on. The last person in the group has 365 (r 1) possible birthdays. Thus, by the multiplication
Principle, we have
n(E) = 365 364 363 . . . (365 (r 1)) = P(365, r)
Therefore
P(E) =
n(E)
n(S)
=
P(365, r)
365
r
Now, using the principle of the complement
P(E) = 1 P(E)
We get the probability that at least two people, from a group of r, have the same birthday is
P(E) = 1 P(E) = 1
P(365, r)
365
r
3 3
UNLV
7.4: Conditional Probability
A. Motivation
1. Suppose that someone rolls a single die, out of your sight, and tells you it came up an even number.
You are then asked What is the probability that a 2 has been rolled? Then answer that you give
is certainly aected by the information that is know to you, namely, that the die is know to have
come up 2, 4, or 6. This, in eect, reduces the sample space to S = {2, 4, 6} from which the answer
is obviously
1
3
. The mathematical notation for this question is:
P(a two comes up|an even number has been rolled) =
1
3
, where the vertical bar is read as given that
2. How do we calculate conditional probability? Look at how we calculated the answer above:
P(E|F) =
number of a two and an even number
total number of even numbers
=
number of outcomes in E F
total number in F
B. Formulas
1. Conditional Probability is: Let E and F be events of a sample space S and suppose P(F) > 0. The
conditional probability of the event E, given the event F, denoted by P(E|F), is dened as
P(E|F) =
P(E F)
P(F)
2. Product Rule: For two events E and F, the probability of the event E and F, namely P(E F) is
given by
P(E F) = P(F) P(E|F)
C. Examples
1. If two cards are randomly drawn, in succession, without replacement, from a deck of 52, what is the
probability that the second card is a spade given that the rst card is a spade? In mathematical
language we have: P(second card is a spade|rst was a spade). Because a spade is gone, the new
sample space is 51 cards including 12 spades. The answer is then
12
51
2. One card is drawn from a deck of 52 cards. What is the probability that the card is:
(a) A king(K) given that the card drawn is a heart?
1
13
(b) A diamond given that the card drawn was a heart or diamond?
13
26
=
1
2
(c) A heart, given that the card drawn was a diamond or a 10? P(H|10 D) =
1
16
(4 10s and 12
diamonds
3 3
3. The senior class of Podunko High has 80 members, 50 of whom are taking English(E), 30 math(M)
and 20 both subjects. What is the probability that a senior taking English, given that the senior is
taking math?
P(E|M) =
P(E M)
P(M)
=
20
80
30
80
=
20
30
=
2
3
4. A tree diagram is often helpful in working conditional probability problems. You would multiply the
branch probabilities.
3 3
UNLV
7.5: Independent Events
1. Let E and F be two events of a sample space, S, with P(F) > 0. The event E, is independent of
the event F, if and only if P(E|F) = P(E)
2. If two events have positive probabilities (P(E) > 0 and P(F) > 0), and if the event E is independent
of F, then F is also independent of E. So, we say that E and F are independent events.
3. Criterion for independent events:
(a) P(E F) = P(E) P(F)
4. Independence for more than two events, simply apply the criterion over and over which gives:
P(E
1
E
2
E
3
. . . E
n
) = P(E
1
) P(E
2
) P(E
3
) . . . P(E
n
)
5. Example: Given P(E) = 0.3, P(F) = 0.2, P(E F) = 0.4. Are E and F independent?
Solution: First nd P(E F) by using P(E F) = P(E) +P(F) P(E F) to get P(E F) = 0.1
Now apply number (3) to see if
P(E F)
?
= P(E) P(F)
0.1
?
= 0.3 0.2
0.1 = 0.06
Since, P(E F) = P(E) P(F), then E and F are not independent.
3 3
UNLV
8.1: Bayes Theorem
A. Motivation
1. Bayes Theorem is a special application of conditional probability. An example leads to the theorem:
2. Surf Mart, which sells shirts under its own label, buys 40% of its shirts from supplier A, 50% from
supplier B, and 10% from supplier C. It is found that 2% of the shirts from A have aws, 3% from B
have aws and 5% from C have aws. A probability tree diagram is shown below fro you to complete.
If one of the shirts is bought from Surf Mart, what is the probability that:
(a) the shirt has a aw, given that it came from A? Knowing that the shirt came from A means
that we have already traversed the A branch and now look for the probability, which is 0.02,
along the attached ow branch. Therefore P(aw|from A) is 0.02.
(b) The shirt has a aw? P(from A and a aw or from B and a aw or from C and a aw) =
(0.4)(0.02) + (0.5)(0.03) + (0.1)(0.05) = 0.028
(c) The shirt came from A given that it has a aw?
This time, the given event is on the right and we are confronted with somehow trying to read
back to the left to reach the event A. This is the reverse probability to which referred and will
always be a clue that the problem is a Bayes Theorem problem. We nd the solution:
P(A|aw) =
P(A and aw)
P(aw)
=
(0.40)(0.02)
(0.4)(0.02) + (0.5)(0.03) + (0.1)(0.05)
=
0.008
0.028
= 0.286
B. Bayes Theorem
1. Partition: A sample space S is partitioned into n subsets A
1
, A
2
, . . . , A
n
, provided
(a) Each subset is nonempty
(b) The intersection of any two of the subsets is empty
(c) A
1
A
2
A
n
= S
3 3
2. Let S be a sample space and let A
1
, A
2
, . . . , A
n
be n events that form a partition of the set S. If E
is any event in S, then
E = (E A
1
) (E A
2
) (E A
n
)
Since E A
1
, E A
2
, . . . , E A
n
are mutually exclusive events, we have
P(E) = P(E A
1
) +P(E A
2
) + P(E A
n
)
Now, if we replace P(E A
1
), P(E A
2
), . . . , P(E A
n
) using the Product Rule. Then we obtain
the formula
P(E) = P(A
1
) P(E|A
1
) +P(A
2
) P(E|A
2
) + +P(A
n
) P(E|A
n
)
3. Bayes Theorem: Let S be a sample space partitioned into n events, A
1
, . . . , A
n
. Let E be any event
of S for which P(E) > 0. The probability of the event A
j
(j = 1, 2, . . . , n), given the event E, is
P(A
j
|E) =
P(A
j
) P(E|A
j
)
P(E)
=
P(A
j
) P(E|A
j
)
P(A
1
) P(E|A
1
) +P(A
2
) P(E|A
2
) +. . . +P(A
n
) P(E|A
n
)
3 3
UNLV
8.2: Binomial Probability Model
A. Conditions
Experiments classied as binomial were rst studied by James Bernoulli in the late 1600s. The term
binomial comes from the fact that these experiments can be classied as having exactly two outcomes. For
an experiment to qualify as binomial, several conditions must be met.
1. The same experiment is repeated several times.
2. There are only two possible outcomes, success and failure, on each trial.
3. The repeated trials are independent.
4. The probability of each outcome remains the same for each trial.
B. Examples/Motivation
The central question in a binomial experiment is to nd the probability of r successes from among n trials;
the outcome labelled success will be determined by the question asked, and all other outcomes will be
lumped together and labelled failure. Some examples follow which should help clarify the terminology.
1. A single die is rolled 10 times and we want to know the probability that exactly 3 ves will be rolled.
The experiment is repeated n = 10 times, there are to be r = 3 successes and the outcome of each
trial is independent of the others.
Because the question asks about rolling 5s, we call roll a 5 a success, S, and roll a 1,2,3,4 or 6
a failure, F. It follows that p = P(S) =
1
6
and q = P(F) =
5
6
.
2. A coin is tossed 20 times and we are asked to determine the probability that exactly 12 heads will
turn up. Here, n = 20 and the outcome of the trials are independent. Success will be a head lands
up and failure will be a tail lands up. So, p = P(S) =
1
2
and q = P(F) =
1
2
and r = 12.
3. Test show that 4% of the hair dryers made by the Hot-Dri company have a defect. Suppose that
50 of the companys dryers are ordered by the Bettis Discount Store and she is interested in the
probability that exactly one will be defective. In this case n = 50 and because we are interested in
defects, success will be the dryer is defective and failure will be the dryer is not defective. Then
p = P(S) = 0.04 and q = P(F) = 0.96 and r = 1.
C. Formula for Binomial Probabilities
1. Formula for Binomial Probabilities:
b(n, k; p) =
_
n
k
_
p
k
q
nk
=
n!
k!(n k)!
p
k
q
nk
where p is the probability of success and q = 1 p is the probability of failure.
3 3
2. Examples
(a) Tests show that 4% of the people who take a particular drug are subject to side eects. Of
20 people taking the drug, what is the probability that exactly 5 of them will experience side
eects?
b(20, 5; 0.04) =
_
20
5
_
(0.04)
5
(0.96)
15
= 0.00086
(b) The Marcello Company polled a large number of potential customers and found that 25% would
buy the companys product. If Deanna calls on 10 potential customers, what is the probability
that:
i. Exactly 8 will buy the product?
b(10, 8; 0.25) =
_
10
8
_
(0.25)
8
(0.75)
2
= 0.00039
ii. Exactly 3 will buy the product?
b(10, 3; 0.25) =
_
10
3
_
(0.25)
3
(0.75)
7
= 0.25
iii. At least 8 will buy the product?
P(8 will buy) +P(9 will buy) +P(10 will buy)
=
_
10
8
_
(0.25)
8
(0.75)
2
+
_
10
9
_
(0.25)
9
(0.75)
1
+
_
10
10
_
(0.25)
10
(0.75)
0
= 0.00039 + 0.00003 + 0.00000
= 0.00042
iv. At least one will buy the product? The complement theorem will give the easiest translation:
P(at least one will buy) = 1 P(none will buy)
= 1 (0.75)
10
= 0.944
3 3
UNLV
8.3: Expected Value
A. Expected Value
1. Formula for expected value: Let S be a sample space and let A
1
, A
2
, A
3
, . . . , A
n
be n events that form
a partition of S. Let p
1
, p
2
, p
3
, . . . , p
n
be the probabilities of the events A
1
, A
2
, A
3
, . . . , A
n
. If each
event A
1
, A
2
, A
3
, . . . , A
n
is assigned a payo m
1
, m
2
, m
3
, . . . , m
n
, the expected value E corresponding
to these payos is:
E = m
1
p
1
+m
2
p
2
+m
3
p
3
+. . . m
n
p
n
2. If E is positive, we say that the game is favorable to the player; if E = 0, we say the game is fair;
and if E is negative, we say the game is unfavorable to the player.
3. Expected Value of a Bernoulli Trials: In a Bernoulli process with n trials the expected number of
successes is
E = np
where p is the probability of success for any single trial.
B. Examples
1. At a carnival midway, Shawn purchases a lottery ticket for $1. If 1000 tickets are to be sold and
there are 3 prizes . . . a rst prize of $100, a second prize of $50 and a third prize of $25, what is his
expected value for his ticket?
(a) What Formula is the expected value of a ticket? Soln:
E = 100
1
1000
+ 50
1
1000
+ 25
1
1000
= $0.10 + $0.05 + $0.025 = $0.175
(b) If Shawn purchases a lottery ticket for $1, how much should he expect to lose? Soln:
1 0.175 = 0.825
He should expect to lose $0.825.
2. If Steven rolls a die 600 times, how many times should a 4 turn up?
E = (600)
1
6
= 100
3 3
UNLV
1.1: Lines
A. Rectangular Coordinates
1. xaxis
2. yaxis
3. origin
4. ordered pair
5. quadrants
B. Graphing Linear Equations
1. Defn: A linear equation in two variables is an equation equivalent to the form:
Ax +By = C
where A, B, C R and A and B are not both zero.
2. Defn: The points where the graph of a linear equation crosses the axes are called intercepts. The
xintercept is the point at which the graph crosses the xaxis; the yintercept is the point at which
the graph crosses the yaxis.
3. Steps for Finding the Intercepts of a Linear Equation: To nd the intercepts of a linear equation
Ax +By = C, where A = 0 or B = 0, follow these steps:
Step 1: Let y = 0 and solve for x. This determines the xintercept.
Step 2: Let x = 0 and solve for y. This determines the yintercept.
3 3
C. Lines
1. Defn(Slope of a Line): Let P
1
= (x
1
, y
1
) and P
2
= (x
2
, y
2
) be two points. If x
1
= x
2
, the slope m of
the nonvertical line L containing P
1
and P
2
is given by:
m =
y
2
y
1
x
2
x
1
x
1
= x
2
If x
1
= x
2
, L is a vertical line and the slope m of L is undened.
2. Theorem(Equation of a Vertical Line): A vertical line is given by the equation:
x = a
where (a, 0) is the xintercept.
3. Theorem(Equation of a Horizontal Line): A horizontal line is given by the equation:
y = b
where (0, b) is the yintercept.
4. Theorem(Point-Slope Form of an Equation of a Line): An equation of a nonvertical line with slope
m that contains the point (x
1
, y
1
) is:
y y
1
= m(x x
1
)
5. Theorem(Slope-Intercept Form of an Equation of a Line): An equation of a line with slope m and
yintercept (0, b) is:
y = mx +b
3 3
UNLV
1.2: Pairs of Lines
A. Pairs of Lines
1. Theorem(Coincident Lines): Coincident lines that are vertical have undened slope and the same
xintercept. Coincident lines that are nonvertical have the same slope and same intercepts
2. Theorem(Parallel Lines): Parallel lines that are vertical have undened slope and dierent xintercepts.
Parallel lines that are nonvertical have the same slope and dierent intercepts.
3. Theorem(Intersecting Lines): Intercepting lines have dierent slopes
4. Theorem(Perpendicular Lines) No longer included in the textbook: Vertical lines are perpendicular
to horizontal lines. Given two lines L
1
and L
2
with slopes m
1
and m
2
respectively. Then L
1
is
perpendicular to L
2
if:
m
1
m
2
= 1 or m
1
=
1
m
2
3 3
UNLV
1.3: Applications to Business and Economics
A. Break-Even Point
1. Given the equations for cost(C) and revenue(R), then the break-even point occurs when C = R.
B. Supply and Demand
1. Given the equations for supple(S) and demand(D), then the market price occurs when S = D.
3 3
UNLV
3.1: Systems of Linear Inequalities
A. Graph linear inequalities
1. Defn: A linear inequality in two variables x and y is an inequality of one of the following forms:
Ax +By C
Ax +By C
Ax +By < C
Ax +By > C
Where A, B, C R and A and B are not both zero. The rst two inequalities are nonstrict and
the second two inequalities are strict.
2. The graph of a linear inequality in two variables x and y is the set of all points (x, y) for which the
inequality is satised.
3. Steps for Graphing a Linear Inequality:
S1: Graph the corresponding linear equation, a line L. If the inequality is nonstrict, graph L using
a solid line; if the inequality is strict, graph L using dashes.
S2: Select a test point P that is not on the line L.
S3: Substitute P into the inequality. If the inequality is satised, then shade the region containing
P. If the inequality is not satised then shade the region not containing P.
B. Graph Systems of Linear Inequalities
1. Defn: A system of linear inequalities is a collection of two or more linear inequalities
2. To graph a system of linear inequalities containing two variables x and y we locate all the points
(x, y) whose coordinates satisfy all the inequalities of the system.
3. Terminology:
(a) Bounded: A region is bounded in the sense that it can be enclosed by some circle of suciently
large radius
(b) Unbounded: A region is unbounded in the sense that it extends innitely far in some direction.
(c) Corner Point: The point of intersection of two line segments that form the boundary is called
a corner point.
3 3
UNLV
3.2: A Geometric Approach to Linear Programming Problems
A. Linear Programming Problems
1. Defn: (Linear Programming Problem)
A linear programming problem(lpp) in two variables, x and y, consists of maximizing or minimizing
an objective function
z = Ax +By
where A, B R, not both zero, subject to constraints expressible as a system of linear inequalities.
2. Defn: To maximize(minimize) z = Ax +By means to locate the points that result in the largest(or
smallest) value of z. Only the points that obey all the constraints are potential solutions. These
points are called feasible points.
3. A solution to a lpp is a feasible points, together with the value of the objective function at that point,
which maximizes(or minimizes) the objective function. If none of the feasible points maximizes(or
minimizes) the obj func, or there are no feasible points, then the lpp has no solution.
B. Solving a lpp
1. Theorem(Criteria for the Existence of a Solution)
Consider a lpp with the set R of feasible points and objective function z = Ax +By.
(a) If R is bounded, then z has both a max and min value on R
(b) If R is unbounded, A, B > 0, and the constraints include x, y 0, then z has a min on R but
not a max.
(c) If R = , then the lpp has no solution and z has neither a max nor a min.
2. Theorem(Fundamental Theorem of LPP with Two Variables)
Consider a lpp with the set R of feasible points and objective function z = Ax +By, where x, y 0.
If a lpp has a solution, it is located at a corner point of the set R of feasible points; if a lpp has
multiple solutions, at least one of them is located at a corner point of the set R of feasible points. In
either case the corresponding value of the objective function is unique.
3. Steps for Solving a LPP
If a lpp has a solution, follow these steps to nd it:
S1: Write an expression for the quantity to be maximized or minimized. (the objective function)
S2: Determine all the constraints and graph the set of feasible points.
S3: List the corner points of the feasible points.
S4: Determine the value of the objective function at each corner point.
S5: Select the maximum or minimum value of the objective function.
3 3
UNLV
2.1: Systems of Linear Equations: Substitution; Elimination
A. Defns:
1. System of linear equations: A system of linear equations is a collection of two or more linear equations.
2. Solution: A solution to a system of linear equations consists of values of the variables that are
solutions to each equation in the system.
3. Types of Solutions:
(a) If the lines are parallel, then the system of equations has no solutions, because the lines never
intersect. The system is inconsistent
(b) If the lines intersect, then the system of equations had one solution, given by the point of
intersection. The system is consistent and the equations are independent
(c) If the lines are coincident, then the system of equations has innitely many solutions represented
by the totality of the points on the line. The system is consistent and the equations are
dependent.
B. Solve Systems of Equations by Substitution
1. Steps for Solving by Substitution:
Step 1: Pick one of the equations and solve for one of the variables in terms of the remaining variables.
Step 2: Substitute the result in the remaining equations.
Step 3: If one equation in one variable results, solve this equation. Otherwise repeat Step 1 and 2
until a single equation with one variable remains.
Step 4: Find the values of the remaining variables by back-substitution.
Step 5: Check the solution.
C. Solve Systems of Equations by Elimination
1. Rules for obtaining an Equivalent System of Equations:
(a) Interchange any two equations in the system
(b) Multiply(or divide) each side of an equation by the same nonzero constant
(c) Replace any equation in the system by the sum(or dierence) of that equation and a nonzero
multiple of any other equation in the system
2. Steps for Solving by Elimination:
Step 1: Select two equations from the system and replace them by two equivalent equations that,
when added, eliminate at least one variable.
Step 2: If there are additional equations in the original system, pair o each one with one of the
equations selected in Step 1 and eliminate the same variable from them.
Step 3: Continue Steps 1 and 2 on successive systems until one equation containing one variable
3 3
remains.
Step 4: Solve for this variable and back-substitute in previous equations until all the variables have
been found.
Step 5: Check the solution.
3 3
UNLV
2.2: Systems of Linear Equations: Matrix Method
A. Defns:
1. matrix: a rectangular array of numbers, enclosed by brackets.
2. entries: the numbers of the matrix
3. When a matrix is used to represent a system of linear equations, it is called an augmented matrix.
B. Solve Systems of Equations by Matrices
1. Row Operations:
(a) Interchange any two rows
(b) Replace a row by a nonzero multiple of that row.
(c) Replace a row by the sum of that row and a constant nonzero multiple of some other row.
2. A matrix is in row echelon form when:
(a) The entry in row 1, column 1 is a 1, and 0s appear below it
(b) The rst nonzero entry in each row after the rst row is a 1, 0s appear below it, and it appears
to the right of the rst nonzero entry in any row above.
(c) Any rows that contain all 0s to the left of the vertical bar appear at the bottom.
3. Matrix Method for Solving a System of Linear Equations(Row Echelon Form):
Step 1: Write the augmented matrix that represents the system.
Step 2: Perform the row operations that place the entry 1 is row 1, column 1.
Step 3: Perform the row operations that leave the entry 1 in row 1, column 1 unchanged, while
causing 0s to appear below it in column 1.
Step 4: Perform the row operations that place the entry 1 in row 2, column 2 but leaves the entries
in column 1 unchanged. If impossible to place a 1 in row 2, column 2, then proceed to place a 1 in
row 2, column 3. Once a 1 is in place, perform the row operations to place 0s below it. (If any rows
are obtained that contain only 0s on the left side of the vertical bar, place such rows at the bottom
of the matrix.)
Step 5: Now repeat Step 4, placing a 1 in the next row, but one column to the right, while leaving
all entries in columns to the left unchanged. Continue until the bottom row or the vertical bar is
reached.
Step 6: The matrix that results is the row echelon form of the augmented matrix. Analyze the system
of equations corresponding to it to solve the original system.
4. Reduce row echelon form: obtain 0s above as well as below the 1s in each row.
3 3
UNLV
2.3: Systems of m Linear Equations Containing n Variables
A. Defns:
1. Systems of m Linear Equations Containing n Variables
A system of m linear equations containing n variables x
1
, x
2
, . . . , x
n
is of the form
_
_
a
11
x
1
+ a
12
x
2
+ + a
1n
x
n
= b
1
a
21
x
1
+ a
22
x
2
+ + a
2n
x
n
= b
2
a
31
x
1
+ a
32
x
2
+ + a
3n
x
n
= b
3
.
.
.
.
.
.
.
.
.
.
.
.
a
i1
x
1
+ a
i2
x
2
+ + a
in
x
n
= b
i
.
.
.
.
.
.
.
.
.
.
.
.
a
m1
x
1
+ a
m2
x
2
+ + a
mn
x
n
= b
m
where a
ij
and b
i
are real numbers, i = 1, 2, . . . , m, j = 1, 2, . . . , n.
A solution of a system of m linear equations containing n variables x
1
, x
2
, . . . , x
n
is any ordered set
(x
1
, x
2
, . . . , x
n
) of real numbers for which each of the m linear equations of the system is satised.
B. Solving a System of m Equations Containing n variables
1. Conditions for the Reduced Row Echelon Form of a Matrix:
(a) The rst nonzero entry in each row is a 1 and it has 0s above and below it
(b) The leftmost 1 in any row is to the right of the leftmost 1 in the row above.
(c) Any rows that contain all 0s to the left of the vertical bar appear at the bottom.
2. Steps for Solving Systems of m Equations Containing n variables.
Step 1: Write the augmented matrix.
Step 2: Find the reduced row echelon form of the augmented matrix.
Step 3: Analyze this matrix to determine if the system has no solution, one solution, or innitely
many solutions.
C. Applications
1. Example: In a chemistry laboratory one solution contains 10% hydrochloric acid (HCl), a second
solutions contains 20% HCl, and a third contains 40% HCl. How many liters of each should be mixed
to obtain 100 liters of 25% HCl? Soln:
Let x = number of liters of the 10% soluition of HCl
Let y = number of liters of the 20% soluition of HCl
Let z = number of liters of the 40% soluition of HCl
Since we want 100 liters in all and the amount of HCl obtained from each solution must sum to
25% of 100, or 25 liters, we must have
_
x +y +z = 100
0.1x + 0.2y + 0.4z = 0.25(100)
Thus, our problem
3 3
is to solve a system of two equations containing three variables. By matrix techniques we ob-
tain the solution
_
x = 2z 50
y = 3z + 150
where z is the parameter. Now, the practical considera-
tions of this problem lead us to the conditions that x 0, y 0, z 0. From above, we see
that we must have z 25 and z 50, since otherwise x < 0 or y < 0. Some possible solu-
tions are listed in the following table. The nal determination by the chemistry laboratory will
more than likely be based on the amount and availability of one acid solution versus the others.
No. of liters
10% solution 0 10 12 16 20 25 26 30 36 38 46 50
No. of liters
20% solution 75 60 57 51 45 37.5 36 30 21 18 6 0
No. of liters
30% solution 25 30 31 33 35 37.5 38 40 43 44 48 50
3 3
UNLV
2.4: Matrix Algebra
A. Defns:
1. A matrix is dened as a rectangular array of the form
_
_
a
11
a
12
a
1j
a
1n
a
21
a
22
a
2j
a
2n
.
.
.
.
.
.
.
.
.
.
.
.
a
i1
a
i2
a
ij
a
in
.
.
.
.
.
.
.
.
.
.
.
.
a
m1
a
m2
a
mj
a
mn
_
_
The symbols a
11
, a
12
, of a matrix are referred to as the entries (or elements) of the matrix. Each
entry a
ij
of the matrix has two indices: the row index, i, and the column index, j. The symbols
a
i1
, a
i2
, , a
in
represent the entries in the ith row, and the symbols a
1j
, a
2j
, , a
mj
represent the
entries in the jth column.
2. The dimension of a matrix A is determined by the number of rows and the number of columns in
the matrix. If a matrix has m rows and n columns, we denote the dimension of A by m n, read
m by n
3. If a matrix A has the same number of rows as it has columns, it is called a square matrix.
4. Equality of Matrices: Two matrices A and B are equal if they are of the same dimension and if
corresponding entries are equal. In this case we write A = B, read as matrix A is equal to matrix
B.
5. Addition of Matrices: We dene the sum A +B of two matrices A and B with the same dimension
as the matrix consisting of the sum of corresponding entries from A and B. That is, if A = [a
ij
] and
B = [b
ij
] are two mn matrices, the sum A +B is the mn matrix [a
ij
+b
ij
].
6. Subtraction of Matrices: We dene the dierence A B of two matrices A and B with the same
dimension as the matrix consisting of the dierence of corresponding entries from A and B. That is,
if A = [a
ij
] and B = [b
ij
] are two mn matrices, the dierence AB is the mn matrix [a
ij
b
ij
].
B. Properties of Matrix Algebra
1. Commutative Property of Addition: If A and B are two matrices of the same dimension, then
A +B = B +A
2. Associative Property of Addition: If A, B and C are three matrices of the same dimension, then
A + (B +C) = (A +B) +C
3. Additive Inverse Property: For any matrix A, we have the property that
A + (A) = 0
3 3
C. Scalar Multiplication
1. Scalar Multiplication: Let A be an m n matrix and let c be a real number, called a scalar. The
product of the matrix A by the scalar c, called scalar multiplication, is the mn matrix cA, whose
entries are the product of c and the corresponding entries of A. That is, if A = [a
ij
], then cA = [ca
ij
].
2. Properties of Scalar Multiplication: let k and h be two real numbers and let A and B be two matrices
of dimension mn. Then
k(hA) = (kh)A
(k +h)A = kA +hA
k(A +B) = kA +kB
3 3
UNLV
2.5: Multiplication of Matrices
A. Defns:
1. If R = [r
1
r
2
r
n
] is a row matrix of dimension 1 n and C =
_
_
c
1
c
2
.
.
.
c
n
_
_
is a column matrix of
dimension n 1, then by the product of R and C we mean the number
RC = r
1
c
1
+r
2
c
2
+ +r
n
c
n
2. Multiplication of Matrices: Let A denote an m r matrix, and let B denote an r n matrix. The
product AB is dened as the mn matrix whose entry in row i, column j is the product of the ith
row of A and the jth column of B
Note: Multiplication of matrices is possible only if the number of columns of the matrix on the left
equals the number of rows of the matrix on the right. If A is of dimension mr and B is of dimension
r n, then the product AB is of dimension mn.
B. Theorems and Properties
1. Theorem: Matrix multiplication is not commutative. That is, in general
AB is not equal to BA
2. Associative Property of Matrix Multiplication: Let A be a matrix of dimension m r, let B be a
matrix of dimension r p and let C be a matrix of dimension p n. Then matrix multiplication is
associative. That is,
A(BC) = (AB)C
The resulting matrix ABC is of dimension mn.
3. Distributive Property: Let A be a matrix of dimension mr. Let B and C be a matrices of dimension
r n. Then the distributive property states that
A(B +C) = AB +AC
The resulting matrix AB +AC is of dimension mn.
4. The Identity Matrix: For an n n matrix, the entries located in row i, column i, 1 i n, are
called the diagonal entries. An nn matrix whose diagonal entries are 1s, while all the other entries
are 0s, is called the identity matrix I
n
. For example:
I
2
=
_
1 0
0 1
_
, I
3
=
_
_
1 0 0
0 1 0
0 0 1
_
_
, I
4
=
_
_
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
_
_
3 3
5. Theorem: If A is a square matrix of dimension n n, then
AI
n
= I
n
A = A
6. Identity Property: If A is a matrix of dimension m n and if I
n
denotes the identity matrix of
dimension n n, and I
m
denotes the identity matrix of dimension mm, then
I
m
A = A AI
n
= A
3 3
UNLV
2.6: The Inverse of a Matrix
A. Inverse of a Matrix
1. Inverse of a Matrix: Let A be a matrix of dimension n n. A matrix B of dimension n n is called
the inverse of A if AB = BA = I
n
. We denote the inverse of a matrix A, if it exists, by A
1
.
NOTE: A nonsquare matrix has no inverse.
2. Steps for Finding the inverse of a Matrix of Dimension n n
Step 1: Form the matrix [A|I
n
].
Step 2: Using row operations, write [A|I
n
] in reduced row echelon form.
Step 3: If the resulting matrix is of the form [I
n
|B], that is, if the identity matrix appears on the left
side of the bar, then B is the inverse of A. Otherwise, A has no inverse.
B. Matrix Equation
1. Given a system of n linear equations containing n variables of the form
_
_
a
11
x
1
+ a
12
x
2
+ + a
1j
x
j
+ a
1n
x
n
= b
1
a
21
x
1
+ a
22
x
2
+ + a
2j
x
j
+ a
2n
x
n
= b
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
i1
x
1
+ a
i2
x
2
+ + a
ij
x
j
+ a
in
x
n
= b
i
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
n1
x
1
+ a
n2
x
2
+ + a
nj
x
j
+ a
nn
x
n
= b
n
where a
ij
and b
i
are real numbers, i = 1, 2, . . . , n, j = 1, 2, . . . , n.
Then I can express this system as the following matrix equation
_
_
a
11
a
12
a
1j
a
1n
a
21
a
22
a
2j
a
2n
.
.
.
.
.
.
.
.
.
.
.
.
a
i1
a
i2
a
ij
a
in
.
.
.
.
.
.
.
.
.
.
.
.
a
n1
a
n2
a
nj
a
nn
_
_
. .
A
_
_
x
1
x
2
.
.
.
x
i
.
.
.
x
n
_
_
. .
X
=
_
_
b
1
b
2
.
.
.
b
i
.
.
.
b
n
_
_
. .
B
2. Theorem: A system of n linear equations containing n variables
AX = B
for which A is a square matrix and A
1
exists, always has a unique solution that is given by
X = A
1
B
3 3
UNLV
4.1: The Simplex Method: Standard Form, Initial Tableau and Pivoting
We now know how to work linear programming problems graphically with two variables. Unfortunately
most LPP problems have many more variables, so we need a less restrictive algebraic method. This method
is called the simplex method. The rst type we will examine will be the standard maximum-type
problems.
A. Standard Form
1. The following conditions must be met to be a standard maximum-type problem:
(a) The objective function is linear and is to be maximized
(b) The variables are all nonnegative
(c) The constraints are all of the form ax
1
+bx
2
+cx
3
+ m, where m 0.
2. Examples:
(a) Maximize P = 3x
1
+ 4x
2
subject to the constraints:
_
_
_
5x
1
+ 2x
2
145
2x
1
+ 3x
2
222
x
1
0 x
2
0
is in standard form
(b) Maximize P = 3x
1
+ 4x
2
_
_
_
5x
1
+ 2x
2
125
2x
1
+ 3x
2
222
x
1
0 x
2
0
is NOT in standard form
(c) NOTE: 2x
1
+ 3x
2
125 can be put in correct form by multiplying by (-1) and getting
2x
1
3x
2
125
B. The initial tableau
1. In order to apply the simplex method to a maximum problem required the conversion to equations
by using slack variables.
(a) Convert the inequalities to equations by adding a slack variable to the left side which gives slack
equations:
_
5x
1
+ 2x
2
145
2x
1
+ 3x
2
222
The slack equations are:
5x
1
+ 2x
2
+s
1
= 145
2x
1
+ 3x
2
+s
2
= 222
where s
1
and s
2
are the slack variables and are nonnegative.
(b) We are now ready to set up the matrix which represents the initial simplex tableau.
i. The objective row is always the bottom row
ii. The slack equations form all the other rows
3 3
iii. The symbol for each variable appears above the column where its coecients appear.
iv. The notation BV stands for basic variables. These are the variables that have only 0s and
1s in the column. The others are called non-basic variables.
v. The notation RHS stands for the right-hand side of the equal sign in the slack equations.
vi. The initial simplex tableau for the above problem is:
BV P x
1
x
2
s
1
s
2
RHS
s
1
0 5 2 1 0 145
s
2
0 2 3 0 1 222
P 1 -3 -4 0 0 0
C. Pivoting
1. We need to discuss the method of pivoting:
(a) Denition: To pivot a matrix about a given element(the pivot element) is to apply row operations
so the pivot element is replaced by 1 and all the other elements in the same column (the pivot
column) are 0.
(b) Method:
i. Divide each element in the pivot row by the pivot element which causes the pivot element
to become 1.
ii. Obtain 0s in the remainder of the pivot column by performing row operations.
(c) Analyzing the tableau:
i. From the tableau, write the equation corresponding to each row.
ii. Solve the bottom equation for P and the remaining equations for the basic variables
iii. Set each non-basic variable equal to 0 to obtain the current values for P and the basic
variables
(d) Example: In the tableau given below, the pivot element is boxed.
BV P x
1
x
2
s
1
s
2
RHS
s
1
0 1 2 1 0 300
s
2
0 3 2 0 1 480
P 1 -1 -2 0 0 0
R
1
=
1
2
r
1
BV P x
1
x
2
s
1
s
2
RHS
s
1
0
1
2
1
1
2
0 150
s
2
0 3 2 0 1 480
P 1 -1 -2 0 0 0
R
2
=2r
1
+r
2
R
3
=2r
1
+r
3
BV P x
1
x
2
s
1
s
2
RHS
x
2
0
1
2
1
1
2
0 150
s
2
0 2 0 -1 1 180
P 1 0 0 1 0 300
Now, are basic variables are x
2
, s
2
and P, so the new equations will be:
x
2
=
1
2
x
1
1
2
s
1
+ 150
s
2
= 2x
1
+s
1
+ 180
P = s
1
+ 300
Thus, setting the non-basic variables equal to 0. We get x
1
= 0, x
2
= 150 and P = 300
3 3
UNLV
4.2: The Simplex Method: Solving Maximum Problems in standard form by the simplex
method
A. Simplex algorithm
Once we have the problem in standard form(see 4.1) we are ready to perform the simplex operation
according to the following algorithm:
1. Insert a slack variable into each of the constraints.
2. Rewrite the objective function to match the format of the slack equations and adjoin(place) the
objective function at the bottom of the system.
3. Write the augmented matrix for this new system of equations
4. Find the most negative(smallest value) indicator in the bottom row(the objective function) of the
tableau. This element will determine the pivot column. NOTE: This is dierent than the textbook,
in the text they choose the rst negative value in the bottom row.
5. Divide each positive element above the element found(do not negative elements or zero) into the
corresponding value of the RHS. This determines the quotient.
6. The smallest quotient found determines the pivot row.
7. Where the pivot row intersects the pivot column determines the pivot element.
8. Perform the pivot operations on that element.
(a) Divide each element in the pivot row by the pivot element
(b) Obtain zeros elsewhere in the pivot column by performing row operations on the other entries.
9. Find the basic variables
10. When completed, examine the new bottom row. If a negative element is still present in that row,
repeat steps 4-8 until no negative elements appear there.
11. At that point you are nished and can nd values of the basic variables.
(a) Write equations corresponding to each row.
(b) Solve the bottom equation for P and the remaining equations for the basic variables.
(c) Set each non-basic variable equal to 0 in order to solve.
B. Example:(pg 255,#13)
Maximize P = 3x
1
+x
2
_
_
x
1
+x
2
2
2x
1
+ 3x
2
12
3x
1
+x
2
12
x
1
0 x
2
0
3 3
So, our slack equations are:
_
_
P 3x
1
x
2
= 0
x
1
+x
2
+s
1
= 2
2x
1
+ 3x
2
+s
2
= 12
3x
1
+x
2
+s
3
= 12
1. The initial tableau is:
BV P x
1
x
2
s
1
s
2
s
3
RHS
s
1
0 1 1 1 0 0 2
s
2
0 2 3 0 1 0 12
s
3
0 3 1 0 0 1 12
P 1 -3 -1 0 0 0 0
2. Find the most negative value in the bottom row which is -3
3. Hence the column headed by x
1
is the pivot column.
4. Apply the smallest quotient rule
2
1
= 2,
12
2
= 6 and
12
3
= 4.
5. Hence row 1 is the pivot row and the element s
1
, x
1
, 1 is the pivot element.
6. After the pivot operation is performed, the new tableau is:
BV P x
1
x
2
s
1
s
2
s
3
RHS
x
1
0 1 1 1 0 0 2
s
2
0 0 1 -2 1 0 8
s
3
0 0 -2 -2 0 1 6
P 1 0 2 3 0 0 6
7. Since there are no negative values in the bottom row, we are nished. Notice that x
1
has become a
basic variable replacing s
1
.
8. Solving for the variables we get x
1
= 2, x
2
= 0, and P = 6.
3 3
UNLV
4.3: The Simplex Method: Solving Minimum problems in standard form by the duality
principle
There is a lot of similarity in solving a minimum problem as solving a maximum, once we get set up. A.
Standard Form
1. First we must make certain the problem is in standard form:
(a) The following conditions must be met to be a standard minimum-type problem.
i. The objective function is linear and has nonnegative coecients.
ii. The variables are all nonnegative
iii. The constraints are all of the form ax
1
+bx
2
+cx
3
+ m where m is a constant.
(b) We will solve using the duality principle
i. Suppose a linear programming problem in standard form has a solution. The minimum value
of the objective function of the minimum problem in standard form equals the maximum
value of the objective function of the dual problem which is a maximum problem in standard
from.
ii. Write the minimum problem in standard form.
iii. Construct a matrix that represents the constraints and the objective function.
iv. Interchange the rows and columns to form the matrix of the dual problem. (Transpose)
v. Translate the matrix into a maximum problem in standard form.
vi. Solve the maximum problem by the simplex method.
vii. The minimum value of the objective function (C) will appear in the lower right-hand corner
of the nal tableau and is equal to the maximum value of the dual objective function (P).
viii. The values of the variables that give rise to the minimum value are located in the objective
row in the slack variable columns.
B. Example(4.3 #15) Minimize C = 6x
1
+ 3x
2
_
_
_
x
1
+x
2
4
3x
1
+ 4x
2
12
x
1
0 x
2
0
Thus, our matrix is:
_
_
1 1 4
3 4 12
6 3 0
_
_
Transpose
_
_
1 3 6
1 4 3
4 12 0
_
_
Which gives the following dual maximum problem:
Maximize P = 4y
1
+ 12y
2
_
_
_
y
1
+ 4y
2
6
y
1
+ 4y
2
3
x
1
0 x
2
0
So, our slack equations are:
_
_
_
P 4y
1
12y
2
= 0
y
1
+ 4y
2
+s
1
= 6
y
1
+ 4y
2
+s
2
= 3
3 3
Hence, our initial tableau is:
BV P y
1
y
2
s
1
s
2
RHS
s
1
0 1 3 1 0 6
s
2
0 1 4 0 1 3
P 1 -4 -12 0 0 0
Once the pivot operations are completed you should have a tableau the resembles the following:
BV P y
1
y
2
s
1
s
2
RHS
s
1
0 0 -1 1 -1 3
y
1
0 1 4 0 1 3
P 1 0 4 0 4 12
which give P = 12, y
1
= 3, y
2
= 0 as the maximum solutions, so C = 12, x
1
= 0, x
2
= 4 is the nal solution
for the minimum problem.

Math 132 Notes

Uploaded by

Copyright:

Available Formats

Math 132 Notes

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Math 132 Notes

Uploaded by

Copyright:

Available Formats

UNLV

Department of Mathematical Sciences

You might also like