SYS 6003: Optimization Models and Methods 1
Fall 2022, Exam #1
This exam is a closed book and note examination; you will not need a
calculator for this exam, and you have 3 hours to complete it. Solutions
should be written in the exam booklet, and any separate sheets of paper
used should be attached.
There is a total of 104 points on this exam, and by signing this exam you are
confirming you abided by the UVA Honor Code of Conduct during this exam.
_____________________________________________
Your Signature
_____________________________________________
Your Printed Name
SHOW ALL WORK!! IF I DO NOT SEE IT, I CANNOT GIVE YOU CREDIT!!
SYS 6003, Exam #1
1
Part 1: Conceptual/Short Answer Questions (36 total points)
1. (3 points) Define what the term “basic” means when finding a Basic Feasible
Solution (BFS).
2. (4 points) Scenario: you are using the revised simplex method to solve a
minimization problem, and you are currently located at a degenerate basic
feasible solution (BFS) and you will pivot to a non-degenerate BFS.
Please circle your answer for the following questions/statements to this
scenario.
In order to pivot, the reduced cost must be: negative zero positive
When you pivot, the step size will be: negative zero positive
True or False, the BFS you pivot to will contain the same basic variables:
True False
True or False, the BFS you pivot to will have the same objective value as the
previous BFS:
True False
SYS 6003, Exam #1
2
3. (3 points) When using the Revised Simplex Method, how do you know your
optimal solution is unbounded?
4. (4 points) Scenario: you are using the revised simplex method to solve a
maximization problem, and you are currently located at a non-degenerate
basic feasible solution (BFS) and you will pivot to another degenerate BFS.
Please circle your answer for the following questions/statements to this
scenario.
In order to pivot, the reduced cost must be: negative zero positive
When you pivot, the step size will be: negative zero positive
True or False, the BFS you pivot to will contain the same basic variables:
True False
True or False, the BFS you pivot to will have the same objective value as the
previous BFS:
True False
SYS 6003, Exam #1
3
5. (3 points) Assume you are located a BFS for some Linear Programming
problem with a minimization objective. If the reduced cost of all non-basic
variables is strictly ≥0, does this mean your current BFS is optimal? Please
explain your answer.
6. (4 points) Scenario: you are using the revised simplex method to solve a
maximization problem, and you are currently located at a degenerate basic
feasible solution (BFS) and you will pivot to a degenerate BFS.
Please circle your answer for the following questions/statements to this
scenario.
In order to pivot, the reduced cost must be: negative zero positive
When you pivot, the step size will be: negative zero positive
True or False, the BFS you pivot to will contain the same basic variables:
True False
True or False, the BFS you pivot to will have the same objective value as the
previous BFS:
True False
SYS 6003, Exam #1
4
Questions 7 and 8 utilize the following information:
We have two variables X and Y, and both of these variables are binary. Please
answer questions 7 and 8 based on variables X and Y being binary.
7. (3 points) We have written a valid non-linear constraint X*Y = 0, but we need
to create an equivalent linear constraint(s) that achieves the same result as
the non-linear one. Please write the linear constraint(s) below that ensures
X*Y = 0.
8. (3 points) We have written a valid non-linear constraint X*Y ≤ 1, but we need
to create an equivalent linear constraint(s) that achieves the same result as
the non-linear one. Please write the linear constraint(s) below that ensures
X*Y ≤ 1.
SYS 6003, Exam #1
5
9. (3 points) If you are using the Big M method and you use k artificial variables
to find an initial basic feasible solution (BFS), can it ever take more than k
pivots before you find a “real” basic feasible solution (“real” meaning a BFS
that only includes variables in the original problem)? Please explain your
answer.
10.(3 points) For the Tableau Method, we did not find the “step size” when
making a pivot. What was the process step called that was equivalent to
finding the step size for the Revised Simplex Method? If you cannot
remember the exact name, you can also describe the process step.
SYS 6003, Exam #1
6
11.(3 points) Assume we have a Liner Program that is a maximization problem,
and we have 4 variables (x1, x2, x3, and x4), and assume the s1 and s2 variables
are slack variables. Based on the Tableau below, what variables are in our
current basis? Explain how you know this is the current basis.
SYS 6003, Exam #1
7
Part 2: Work Out Problems (77 total points)
Problem 1 (8 points)
a) (4 points) Please expand the following expression written in set notation:
Sets:
I: {1, 2}
J: {1, 2, 3}
ΣiεIΣjεJ xkij = bk ∀ k∈{2, 5, 1}
SYS 6003, Exam #1
8
b) (4 points) Please write the following constraints using set notation (i.e.
please write the 3 constraints as a single constraint using set notation):
a11x1 + a12x2 + a11y1 + a12y1 = b3 (1)
a21x1 + a22x2 + a21y2 + a22y2 = b3 (2)
a31x1 + a32x2 + a31y3 + a32y3 = b3 (3)
SYS 6003, Exam #1
9
Problem 2 (20 total points)
Rosie loves to (1) read, (2) play the piano, (3) play tennis, (4) draw, and (5) play with
her little sister, but she has limited time to do so during her weekends (Saturday
and Sunday). Her goal is to maximize the total joy from how much time she spends
doing each activity during her upcoming weekend, and she needs help determining
how much time to spend doing each activity for both Saturday and Sunday. Please
note that the amount of time Rosie spends doing a particular activity on Saturday
and Sunday can be different.
On Saturday, Rosie can spend at most 10 hours choosing her 5 activities of interest,
but on Sunday Rosie has at most 8 hours to utilize for the 5 activities. Rosie needs
to play with her little sister at least 6 total hours combined over both days, and she
should practice piano exactly 3 hours over the two days combined. Rosie also
receives different amounts of “joy per hour” depending on which day (Saturday or
Sunday) she spends doing the activity. See the table below for the “joy per hour”
by weekend day:
Activity Saturday (joy per hr) Sunday (joy per hr)
Read 9 8
Play Piano 6 7
Play Tennis 8 7
Draw 5 5
Play with Sister 4 -1
a. (10 points) Formulate the problem above algebraically. Please make sure
you clearly state your variables and label each constraint.
SYS 6003, Exam #1
10
b. (10 points) Based on your algebraic formulation in (a), please develop a
set notation formulation for this same problem. The goal is to create as
many sets and parameters as possible to make a succinct set notation
formulation. Please state all assumptions, nomenclature, sets,
parameters, etc. utilized in this formulation.
SYS 6003, Exam #1
11
SYS 6003, Exam #1
12
Problem 3 (20 total points)
You have just been hired to take over the study-abroad program at UVA. You can
pick up to 10 universities from around the world (out of a very very large candidate
list of universities) to formalize partnerships with. You also have to decide which
university each of the 70 SYS 3021 students will go to. Every student specifies 5
universities (out of the original candidate list of universities) that they are willing to
travel to. Each university specifies an upper limit on the number of students they
will accept.
a) (8 points) Please formulate a linear program (with continuous, integer,
and/or binary variables and linear constraints and objective function) to
determine which universities to choose as possible destinations, and which
students to send to which universities. A student cannot be sent to a
university that is not on their list, and all students must be sent somewhere.
Your sole objective initially is just to determine a feasible solution (so you do
not need to specify an objective function for part a).
SYS 6003, Exam #1
13
For parts (b)-(d), please fully define any new sets, parameters, variables,
assumptions, etc. in order to answer each question.
b) (4 points) How would you change/revise your formulation to also require
that, if you partner with a certain university, that university must get at least
a given number of UVA students?
SYS 6003, Exam #1
14
c) (4 points) How would you change/revise your formulation to maximize the
number of students who get assigned to their first choice?
d) (4 points) How would you change/revise your formulation to ensure that no
more than one school in any given country was chosen?
SYS 6003, Exam #1
15
Problem 4 (12 points)
Consider the following linear program:
min 2v – 4w + 2x + y + 6z
st: -2w + x + 2y + 2z = 1
4v – 4w + z = 8
v, w, x, y, z ≥ 0
Let {v, x} be your initial BFS, and use the simplex method as taught in lecture to
pivot to variable y; you should show that the calculated reduced cost indicates you
should pivot. You only need to complete this one pivot, and state what the new
basis is and the values the basic and non-basic variables take. Do NOT solve to
optimality!
SYS 6003, Exam #1
16
SYS 6003, Exam #1
17
Problem 5 (8 points)
Consider the following linear program with 5 variables (v, w, x, y, and z):
Maximize 3x + 4z
Subject to: w + v – x = 6
3w ≥ 2x –z
y ≤ 8 – z
w, x, y > 0
Convert this program to the “graphical” standard form shown below.
Minimize cx
Subject to: Ax ≤ b
x > 0
SYS 6003, Exam #1
18
Scratch Paper
SYS 6003, Exam #1
19
Scratch Paper
SYS 6003, Exam #1
20
SYS 6003: Exam #1 Equation Sheet
xB = AB
-1b
RCp = cdp = cp – cBAB
-1Ap
dp = -AB
-1Ap
θ = min -xb / [dp]b over all b ∈ B for which [dp]b < 0