math 308 final exam 1
pdf
keyboard_arrow_up
School
Simon Fraser University *
*We aren’t endorsed by this school
Course
308
Subject
Mathematics
Date
Feb 20, 2024
Type
Pages
18
Uploaded by LieutenantCrown6971
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
December 15, 2022, 3:30 – 6:30
SFU Email:
@SFU.CA
Signature:
First Name:
Last Name:
SFU ID #:
Question:
1
2
3
4
5
6
7
8
9
10
11
Total
Points:
10
6
4
4
8
4
4
13
16
16
15
100
1. Do not open this booklet until told to do so.
2. Write your name, SFU student number and email ID in the space provided.
3. Write your answer in the space provided.
4. To receive full credit for any question, your solution must include justification, be complete and well
presented.
5. Simple calculators and one page handwritten note may be used.
No other aids are allowed.
For
notations that are not defined, use the corresponding information from the text book.
6. D
URING THE EXAMINATION
,
COPYING FROM
,
COMMUNICATING WITH
,
OR DELIBERATELY EXPOSING
WRITTEN PAPERS TO THE VIEW OF
,
OTHER EXAMINEES IS FORBIDDEN
.
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
Blank page for extra work
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
1.
[10]
Choose the correct answer.
(a) The point that does not belong to the half-space defined by
5
x
1
-
2
x
2
≤
0
is
(0
,
0)
(1
,
2)
(2
,
6)
(1
,
3)
(b) The corner points of the feasible region of a linear program (LP) to maximize
x
1
+
x
2
are
(0
,
12)
,
(1
,
8)
,
(3
,
3)
,
(12
,
0)
. Then,
the LP has a unique optimal solution at
(0
,
12)
(0
,
12)
and
(12
,
0)
are alternative optimal solutions of the LP.
(3
,
3)
is the unique optimal solution of the LP.
the LP is unbounded.
(c) A linear program has one of its constraints as
x
1
≥
.
4(
x
1
+
x
2
)
.
If
x
3
is a slack variable in this
constraint, the standard form of the LP have the constraint
-
0
.
6
x
1
+ 0
.
4
x
2
+
x
3
= 0
0
.
6
x
1
-
0
.
4
x
2
+
x
3
= 0
-
0
.
6
x
1
+ 0
.
4
x
2
-
x
3
= 0
0
.
6
x
1
+ 0
.
4
x
2
+
x
3
= 0
(d) A tea powder manufacturer sells two blends of tea powder: Morning Glory and Moonlight Madness.
Each kilogram of Moonlight Madness blend uses
60%
Darjeeling Delight,
20%
Kukicha Green and
20%
Wuyi Mountain tea powders and each kilogram of Morning Glory blend contains
40%
Darjeel-
ing Delight,
25%
Kukicha Green and
35%
Wuyi Mountain.
At most 20 kg of Kukicha Green, 20
kg of Wuyi Mountain and 10 kg of Darjeeling Delight tea will be used each day.
Morning Glory
blend sells for
$4
per
kg
and Moonlight Madness blend sells for
$7
per kg. How many kilograms of
Morning Glory and Moonlight Madness blends need to be produced to maximize revenue? Let
x
1
be the number of kilograms of Morning Glory blend produced and
x
2
be the number of kilograms of
Moonlight Madness blend produced. Then a valid constraint in a linear programming formulation
of this problem is
.
25
x
1
-
.
2
x
2
≤
20
-
.
4
x
1
+
.
6
x
2
≤
10
.
4
x
1
+
.
6
x
2
≤
5
.
35
x
1
+
.
2
x
2
≤
20
(e) In the two phase simplex method, the phase 1 problem associated with a linear program (LP)
produced an optimal value of 10 for the phase 1 objective function. Then
the LP is unbounded.
the optimal objective function value of the LP is 10.
the dual of the LP is either infeasible or unbounded.
none of the above conclusions are correct.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
2.
[6]
Choose the correct answer.
(a) A linear program in maximization form with three constraints and 8 variables is solved using the
simplex method which resulted in a unique non-degenerate optimal solution. The associated com-
plimentary dual vector is
(1
,
1
,
1)
. A new variable
x
9
needs to be added to the LP. The coefficient
vector of
x
9
is
a
T
9
= (1
,
0
,
-
2)
T
and its cost coefficient is -1.
After adding
x
9
, the current optimal solution will no longer be optimal.
The current solution will be the unique optimal solution to the changed problem.
The current solution will be an optimal solution to the changed problem but there are
alternative optimal solutions as well.
The given information is insufficient to make any conclusion on the effect of adding the
variable
x
9
.
(b) The following statements are about a balanced transportation problem in minimization form. Choose
the correct statement.
The greedy algorithm could produce a solution with the largest objective function value.
The number of variables will always be greater than or equal to the number of constraints.
If the supply and demand vectors are integers, then every optimal solution for the problem
must be integer valued.
If the reduced cost
u
i
+
v
j
-
c
ij
>
0
for some cell
(
i, j
)
in the transportation tableau, then
the associated BFS is not optimal.
(c) While solving the linear program
Maximize
2
x
1
+4
x
2
+2
x
3
Subject to
2
x
1
-
x
2
+
x
3
≤
10
-2
x
1
+
x
2
+2
x
3
≤
20
x
1
-
x
2
+
x
3
≤
10
x
i
≥
0
, i
= 1
,
2
,
3
.
by simplex method, we reached the following tableau:
x
1
x
2
x
3
x
4
x
5
x
6
RHS
BV
0
0
3
1
1
0
30
x
4
-2
1
2
0
1
0
20
x
2
-1
0
3
0
1
1
30
x
6
-10
0
6
0
4
0
80
⇐
OBJ
x
4
, x
5
, x
6
respectively are slack variables in the first, second, and third constraints. Then,
the linear program is infeasible.
The linear program is unbounded.
x
1
= 0
, x
2
= 20
, x
3
= 0
is an optimal solution.
the optimal objective function value is 80.
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
3.
[4]
Choose the correct answer.
(a) An optimal simplex tableau for the linear program
Maximize
3
x
1
+
x
2
+2
x
3
Subject to
x
1
-
x
2
+
x
3
≤
30
-2
x
1
+2
x
3
≤
20
x
1
+
x
2
+
x
3
≤
10
x
i
≥
0
, i
= 1
,
2
,
3
.
is given below.
x
4
, x
5
, x
6
respectively are slack variables in the first, second, and third constraints.
x
1
x
2
x
3
x
4
x
5
x
6
RHS
BV
0
-2
0
1
0
-1
20
x
4
0
2
4
0
1
2
40
x
5
1
1
1
0
0
1
10
x
1
0
2
1
0
0
3
30
⇐
OBJ
The allowable decrease in the cost coefficient of
x
1
is
∞
2
1
1
4
(b) In a simplex tableau corresponding to a maximization linear program (LP), no artificial variable is
in the basis and
x
1
and
x
2
are non-basic variables with
z
1
-
c
1
=
-
9
and
z
2
-
c
2
=
-
10
. All other
entries in the column corresponding to
x
1
are negative and that corresponding to
x
2
are positive.
The LP is unbounded.
The LP is infeasible.
The LP have an optimal solution.
The given information is insufficient to make a conclusion since we can perform a pivot
in the column of
x
2
and we don’t have enough information to conclude anything about the
tableaus that follow.
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
4.
[4]
Choose the correct answer. If more than one answers are correct, choose all of them.
(a) An optimal simplex tableau of the linear program
Maximize
2
x
1
+2
x
2
+3
x
3
Subject to
x
1
+
x
3
≤
15
-2
x
1
+
x
2
+2
x
3
≤
20
3
x
1
+
x
2
+
x
3
≤
10
x
i
≥
0
, i
= 1
,
2
,
3
.
is given below.
x
4
, x
5
, x
6
respectively are slack variables in the first, second, and third constraints.
x
1
x
2
x
3
x
4
x
5
x
6
RHS
BV
0
-
3
/
4
0
1
-
1
/
4
-
1
/
2
5
x
4
0
5
/
8
1
0
3
/
8
1
/
4
10
x
3
1
1
/
8
0
0
-
1
/
8
1
/
4
0
x
1
0
1
/
8
0
0
7
/
8
5
/
4
30
⇐
OBJ
Choose all correct statements.
The optimal objective function value is
30
The reduced cost of
x
4
is
1
8
The complementary dual vector associated with the BFS is
(0
,
7
/
8
,
5
/
4
)
.
The optimal solution given by the tableau is non-degenerate.
(b) An optimal simplex tableau of the linear program
Maximize
x
1
+2
x
2
+
x
3
Subject to
x
1
+
x
2
≤
50
x
1
+2
x
3
≤
60
x
1
+
x
2
+
x
3
≤
70
x
i
≥
0
, i
= 1
,
2
,
3
.
is given below.
x
4
, x
5
, x
6
respectively are slack variables in the first, second, and third constraints.
x
1
x
2
x
3
x
4
x
5
x
6
RHS
BV
1
1
0
1
0
0
50
x
2
1
0
0
2
1
-2
20
x
5
0
0
1
-1
0
1
20
x
3
1
0
0
1
0
1
120
⇐
OBJ
Choose the correct statements.
Alternate optimal solutions exist.
The surplus vector in the dual is
(1
,
0
,
0)
.
The inverse of the optimal basis matrix is
1
0
0
2
1
-
2
-
1
0
1
The solution represented by the tableau is degenerate.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
5.
[8]
Choose the correct answer. If more than one answers are correct, choose all of them.
(a) The following is the tableau of a linear program (in maximization form) obtained at some iteration
of the dual simplex algorithm.
x
1
x
2
x
3
x
4
x
5
x
6
RHS
BV
1
0
1
1
0
0
8
x
4
0
3
2
0
1
0
-18
x
5
1
-1
-1
0
0
1
88
x
6
4
2
8
0
0
0
0
⇐
OBJ
Identify all valid conclusions from below.
The primal problem is infeasible
The dual problem is unbounded
The tableau represents an optimal solution to primal.
The optimal objective function value of the primal is
0
(b) Choose all correct statements from below.
The minimum cost flow problem restricted to a tree is either infeasible or have a unique
optimal solution.
If
c
ij
≥
0
for all arcs
(
i, j
)
then the minimum cost flow problem cannot be unbounded.
When the supply and demand values are integers, if an optimal solution exists for the
minimum cost flow problem then there exists an optimal solution which is integer.
If the directed graph
G
= (
V, E
)
with edge costs
c
ij
for
(
i, j
)
∈
E
contains a directed cycle
D
such that
∑
(
i,j
)
∈
D
c
ij
<
0
then the minimum cost flow problem on
G
with edge costs
c
ij
and having a feasible solution, must be unbounded.
none of the above statements are correct.
(c) Choose all correct statements from below.
A feasible linear program is either unbounded, or have a unique optimal solution, or have
an infinite number of optimal solutions.
If the primal is infeasible then the dual is unbounded.
For a linear program in standard form, if there exists an optimal solution then there exists
an optimal basic feasible solution.
The balanced transportation problem can be unbounded if negative cost values are al-
lowed.
(d) Choose all correct statements from below. Here,
w
is the vector of dual variables and
a
j
is a coeffi-
cient vector in the primal.
The optimal dual variable associated with a primal equality constraint is never zero.
If the primal has an optimal solution then the dual is either unbounded or infeasible.
If
x
j
>
0
in some optimal solution to the primal then
wa
j
=
c
j
for every optimal dual
solution.
If
x
j
>
0
in some optimal BFS of the primal then
wa
j
=
c
j
for some optimal dual solution.
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
6.
[4]
Choose the correct answer. If more than one answers are correct, choose all of them.
(a) Identify all correct statements from below.
The linear program
Maximize
cx
-
wb
Subject to:
A
x
≤
b
,
w
A
≥
c
,
x
≥
0
,
w
≥
0
is either infeasible or the optimal objective function value is zero.
Cycling will never occur if we use the revised simplex method.
Let
A
be a symmetric matrix. Then, for the linear program
Maximize
cx
Subject to:
A
x
≤
c
,
x
≥
0
if
x
0
is a feasible solution satisfying
A
x
0
=
c
then it must be an optimal solution.
Let
P
be a convex polyhedron. Then, a point
x
0
∈
P
is an extreme point of
P
if and only if
the set
P
- {
x
0
}
is a convex set.
(b) Consider simplex tableau below for a maximization version of the linear program where some in-
formation is hidden.
x
1
x
2
x
3
x
4
x
5
x
6
RHS
BV
2
0
4
0
1
-1
7
-
3
d
3
0
0
0
2
-
0
e
f
i
0
0
a
-
0
c
b
0
h
5
10
Obj
Identify all correct statements from below.
x
2
must be a basic variable.
-1 is a valid choice for
a
If
b >
0
and
a
≥
0
then alternative optimal BFS must exist.
If
b <
0
the solution represented by the tableau cannot be optimal.
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
7.
[4]
Choose the correct answer. If more than one answers are correct, choose all of them.
(a) Select correct statements from below.
If
x
0
is an optimal solution to the linear program LP1 with cost coefficients
c
1
, c
2
, . . . , c
n
and LP2 is a linear program obtained by subtracting 1 from each of the objective function
coefficients of LP1 then
x
0
will be an optimal solution to LP2.
If
x
0
is an optimal solution to the linear program LP1 and LP2 is a linear program obtained
by multiplying the objective function of LP1 by a constant
λ >
0
then
x
0
will be an optimal
solution to LP2.
If
x
1
and
x
2
are optimal solutions to a linear program, then
x
*
=
λ
x
1
+ (1
-
λ
)
x
2
,
0
≤
λ
≤
1
is also optimal to the linear program.
x
0
= (0
,
0
,
17
,
1
,
4
,
0)
is a BFS of the linear program
Maximize
3
x
1
+2
x
2
+4
x
3
-
x
4
+2
x
5
+
x
6
Subject to
x
1
+
x
2
+
x
3
+2
x
4
-
x
5
+4
x
6
=
15
x
1
+2
x
2
+
x
3
-
x
4
+
x
5
+5
x
6
=
20
x
i
≥
0
, i
= 1
, . . . ,
6
.
(b) Consider the properties listed below and choose if such a linear program exists.
A linear program with exactly three feasible solutions.
A linear program with the set of optimal objective function values have cardinality at least
two.
A linear program with at least three corner points for the feasible region and having a
unique optimal solution which lies on four constraints.
A linear program with a unique optimal solution for the minimization version and two
corner point optimal solutions for the maximization version. (Same objective function and
constraints).
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
8. Consider the following linear program.
Maximize
4
x
1
+ 2
x
2
Subject to:
-
x
1
+ 2
x
2
≥
0
,
-
6
x
1
+
x
2
≤
0
x
1
-
4
x
2
≥ -
23
,
3
x
1
-
2
x
2
≤
8
2
x
1
+
x
2
≤
17
, x
1
≥
0
, x
2
≥
0
(a)
[5]
Sketch the feasible region of the linear program and solve the linear program using the graphical
method. Identify an optimal solution and the optimal objective function value.
(b)
[2]
Are there any redundant constraints? Why or why not?
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
(c)
[3]
Determine if alternative optimal solutions exist. If yes, identify three of them. If no, justify your
answer.
(d)
[3]
Write the dual of the linear program.
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
9. Consider the linear program
Maximize
x
1
+2
x
2
+
x
3
Subject to
x
1
+3
x
2
≤
40
x
1
+2
x
3
≤
50
x
1
+
x
2
+
x
3
≤
70
x
i
≥
0
, i
= 1
, . . . ,
3
.
An optimal simplex tableau is given below
x
1
x
2
x
3
x
4
x
5
x
6
RHS
BV
1
/
3
1
0
1
/
3
0
0
40
/
3
x
2
1
/
2
0
1
0
1
/
2
0
25
x
3
1
/
6
0
0
-
1
/
3
-
1
/
2
1
95
/
3
x
6
1
/
6
0
0
2
/
3
1
/
2
0
155
/
3
⇐
OBJ
(a)
[4]
Identify a pair of optimal primal and dual solutions.
(b)
[4]
Write the Gomory cut corresponding to row 1 of the simplex tableau.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
(c)
[6]
Introduce the Gomory cut into the tableau and perform one iteration of the simplex method.
(d)
[2]
Determine if the solution obtained solves the LP with the additional restriction that the variables
must take integer values only.
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
10. Consider the balanced transportation problem given below.
30
b
2
15
25
20
3
8
12
10
15
14
4
7
11
34
6
10
8
15
22
10
11
8
13
(a)
[5]
Identify
b
2
and compute a feasible solution using the north-west corner rule.
(b)
[2]
Compute the objective function value of this solution.
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
(c)
[4]
Identify the dual variables corresponding to the solution from (a) and compute the reduced costs.
(d)
[5]
Perform one iteration of the simplex algorithm for the transportation problem to identify an im-
proved solution.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
11.
(a)
[6]
Consider a primal linear program of maximization type in standard inequality form and its dual.
Show that if
x
0
is any feasible solution to the primal and
w
0
is any feasible solution to the dual,
then
cx
0
≤
w
0
b
.
(b)
[9]
Corona Windows, Inc., manufactures two types of windows: Arched Windows and Awning Windows.
An Arched Window sells for $575 and an Awning Window sells for $430. The raw materials cost for
each type of window is $80. The labor cost for each Arched Window is $120 and for each Awning
Window is $90. The production of these windows requires skilled labor in carpentry and finishing.
An Arched window requires 5 hours of finishing and 3 hour of carpentry work. An Awning Window
requires 4 hour of finishing and 2 hour of carpentry work. Marketing research shows that in each
month at most 25 Awning Windows can be sold. There is significant demand for Arched windows
and whatever is produced can be sold. However, there are limitations on labor hours available but
no limitation on raw material availability. Each month only 500 hours are available for carpentry
job and 300 hours are available for finishing job. Corona Windows wants to determine how many
Awning Windows and Arched Windows are to be produced each month to maximize the monthly
profit. Formulate a linear programming model for this problem . (Use integer variables, if neces-
sary.) Clearly identify decision variables, objective function, and constraints.
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
Blank page for extra work
It’s hard to beat a person who never gives up. – Babe Ruth
MATH 308 D200, Fall 2022
Final Examination
Blank page for extra work
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help