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