Sample_FinalExam
docx
keyboard_arrow_up
School
University of Houston *
*We aren’t endorsed by this school
Course
6372
Subject
Industrial Engineering
Date
Jan 9, 2024
Type
docx
Pages
11
Uploaded by MasterSeaUrchin440
University of Houston, Dept. of Industrial Engineering
INDE6372 Advanced Linear Optimization,
Sample Final Exam
5:00-8:00 PM, December, **, Thursday
Print Name
: ______________________________
Student ID:
______________________________
Signature:
______________________________
Read the following instructions carefully:
This exam is close book. However, you can bring a sheet of note
to the exam.
You can use a calculator in your exam. However, you can’t use the
advanced functionalities in your calculator.
You have 180 minutes to finish the exam.
You
MUST SHOW ALL
THE KEY STEPS IN YOUR WORK
to receive credit for the
computational problems.
Problem
1
2
3
4
5
Total
Score
Question 1
(
8 pts
):
Given the following network.
(1.1)
Use the Augmenting path method to send the maximum flow from the
source node (1) to the sink node (6);
4
2
2
Source
3
5
4
Sink
6
2
(1.2)
Find a cut in the network whose capacity equals the maximum flow obtained
in (1.1). Explain why the solution you obtained is optimal;
4
6
1
5
3
4
2
(1.3) Write down the linear optimization model for the maximum
flow problem.
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
Question 2 (12 pts).
A company supplies its four customers from its three
plants. The shipping cost per batch from each plant to each customer is given
below.
Customer
1
Customer
2
Customer 3
Customer 4
Supply
Plant 1
$2,000
$1,100
$300
$600
5
Plant 2
$500
$900
$1,000
$200
10
Plant 3
$1,800
$700
$400
$100
15
Demand
3
3
12
12
(2.1) Formulate the problem as a transportation problem to minimize the
transportation cost of the company and use the minimum cost method to find a
basic feasible solution;
(2.2) Use vogel’s method to find a basic feasible solution and determine whether
the obtained solution is optimal. If not, please use simplex method to find the
optimal solution.
(2.3) Find the range of values of c
13
for which the current basis remains optimal;
(2.4)
Due to recent market change, the demand from customer 1 has changed from
3 to 5 batches. The company needs to select one out of its three plants and
increases the production capacity by 2 batches in the selected plant to meet the new
demand from customer 1. Suppose that the costs of expanding the production
capacity in all the plants are the same. Please help the company to determine which
plant should be selected for expansion (
Hint:
Expanding the production capacity
by 2 batches in one plant corresponds to a special scenario of sensitivity analysis
for the transportation problem).
Question 3 (6 pts)
Given the information for a project in the following
table.
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
Activity
Immediate
Predecessors
Duration in weeks
A
----
3
B
----
3
C
----
1
D
A,B
3
E
A,C
3
F
D,E
2
G
D,F
4
H
E
3
(3.1) Construct a network for this project;
(3.2) Find a project schedule to minimize the completion time of the project.
Question 4 (4 pts)
A real estate development firm, Peterson and
Johnson, is considering seven possible development projects. The
following table shows the estimated long-term profit that each
project will produce and the investment required to undertake the
project, in units of millions of dollars.
1
2
3
4
5
6
7
Profit
1
1.8
1.6
0.8
1.4
2.5
1.5
Investm
ent
7
10
8
5
7
6
9
The owners of the company have raised $20 Million of investment
capital for these projects. However, after reviewing the proposals
for these projects, the owners have the following considerations:
(a):
At most two projects from the first four projects can be
selected;
(b):
At least one project from projects 6 and 7 must be selected;
(c):
If one project’s estimated profit p
i
is more than or equal 2
times of the profit p
j
of another project, then project (j) cannot be
selected unless project (i) is selected, i.e.,
x
j
-x
i
≤
0
if
p
i
-2p
j
≥
0
;
(d) Use covering to construct some valid cut to improve the LP
relaxation of the ILP model.
Formulate an integer linear
optimization model to help the company to select the projects to
maximize its estimated profit.
Question 5 (4 pts)
Determine whether the following statements are
correct.
(5.1)
The linear system
{
Ax
=
b,x ≤
0
}
has no feasible solutions if and only if
(a) the system
{
b
T
y
<
0,
A
T
y
=
0,
y≥
0
}
is feasible;
(b) the system
{
b
T
y
>
0,
A
T
y
=
0,
y≥
0
}
is feasible;
(c) the system
{
b
T
y
>
0,
A
T
y≤
0,
}
is feasible;
(d) the system
{
b
T
y
<
0,
A
T
y≤
0,
}
is feasible.
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
(5.2)
Which of the following algorithms will find the optimal solution to the
shortest-path problem?
(a)
Dijkstra’s algorithm;
(b) Dynamic Programming;
(c) Augmenting path method;
(d) Simplex method;
(5.3)
Label the following statements regarding network flow as true or false?
(a) A feasible network flow from the source node to the sink node is larger than or
equals the flow cross some cut;
(b) A feasible network flow from the source node to the sink node is less than or
equals the flow cross some cut;
(c) A feasible flow that equals the flow cross some cut is the maximum flow.
(5.4)
Label the following
statements about ILP and its relaxation as true or false.
(a) The feasible region of the LP relaxation is a subset of the feasible region
of the original ILP problem;
(b) If an optimal solution to the LP relaxation is an integer solution, then the
optimal value of the objective function is the same for both problems;
(c) If a non-integer solution is feasible to the LP relaxation, then its nearest
integer solution (obtained by rounding each variable to the nearest integer) is
a feasible solution to the original ILP problem.
(5.5)
Which of the following methods can be used to improve the LP relaxation of
an ILP.
(a) Set some variable to a fixed value;
(b) Exploring the structure of the underlying problem to derive a tighter
formulation;
(c) Add some valid linear inequality based on the standard Gomory cut;
(d) Add some valid linear inequality based on the refined Gomory cut.
Question 6
:
Suppose after solving the LP relaxation of some ILP
problem, we find the following equality
x1 + 2.3x2-0.4x3+1.4 x4=4.5,
where only x1 is a basic variable in the final tableau. Please construct
the corresponding cut to improve the LP relaxation using the standard
Gomory cut and the refined Gomory cut.
Question 7:
Consider the following knapsack problem:
Max
x
1
+1.8 x
2
+1.6 x
3
+0.8 x
4
+ 1.4 x
5
+ 2.5 x
6
+ 1.5 x
7
s.t.
7 x
1
+10 x
2
+ 8 x
3
+5 x
4
+7x
5
+6x
6
+9x
7
≤
20;
all x
i
binary.
Use the set of covers to construct some valid linear inequalities to
improve the LP relaxation of the above binary LP.