Spring 2024
Assignment 4
Linear programming and its applications to computer science
Objective: Assess understanding of the course.
• Please read each exercise carefully.
• Every item on the test awards 2 points for each correct answer, for a maximum
possible score of 20 points.
• You don’t need calculator for this examination.
• Mere suspicion of cheating, sharing calculators or using any unfair means of aid
is enough to get your test withdrawn.
i
Multiple Choice Questions.
1. (MSQ, 2 mark) Which of the following is not necessary for a solution to form a basic
feasible solution.
A. The columns corresponding to the variables with non-zero value
form a basis.
B. The columns corresponding to the variables with zero value form a
basis.
C. The columns corresponding to the variables with non-zero values are linearly
independent.
D. The columns corresponding to the variables with zero value are lin-
early independent.
Solution: Not all basic variables need to have zero value. The nonzero ones will be
linearly independent but need not be a basis.
2. (MCQ, 2 mark) Which of the following is true.
A. A BFS can correspond to two vertices.
B. A vertex can correspond to two BFS’s.
C. A BFS always corresponds to a unique vertex.
D. A vertex always corresponds to a unique BFS.
Solution: A BFS will specify a solution and hence a unique vertex. A vertex can
have different partitions into basic and non-basic variables.
3. (MCQ, 2 mark) Slack variables are used to
A. Convert equalities into inequalities.
B. Convert strict inequalities into equalities.
C. Find the starting solution by going to a new LP.
D. Convert inequalities into equalities.
Solution: recall
4. (MSQ, 2 mark) In simplex method,
A. for a maximization problem, the objective value of the solution always increases
strictly with subsequent iteration.
B. for a maximization problem, the objective value of the solution always de-
creases or remains same with subsequent iteration.
C. for a maximization problem, the objective value of the solution al-
ways increases or remains same with subsequent iteration.
D. for a minimization problem, the objective value of the solution always decreases
strictly with subsequent iteration.
E. for a minimization problem, the objective value of the solution al-
ways decreases or remains same with subsequent iteration.
F. for a minimization problem, the objective value of the solution always increases
or remains same with subsequent iteration.
1
Solution: recall
START ——————————————–
Assume we are running simplex method on a maximization problem as discussed in
the class. Remember that by multiplying with the inverse of the basic part of the
constraint matrix A to equations, and then substituting these new equations in the
objective function, we get a nice form in an iteration of the simplex method.
5. (MSQ, 2 mark) What is true about this nice form?
A. All basic variables are represented in terms of the non-basic vari-
ables.
B. All non-basic variables are represented in terms of the basic variables.
C. the objective function does not contain any basic variable.
D. the objective function does not contain any non-basic variable.
Solution: Since AB is invertible, we get basic variables in terms of non-basic vari-
ables. Using them, we can remove basic variables from the objective function.
6. (MCQ, 2 mark) The entering variable in the BFS can be the one
A. Which has positive coefficient in the objective function.
B. Which has zero coefficient in the objective function.
C. Which has negative coefficient in the objective function.
D. Which has positive coefficient in all the constraints.
E. Which has negative coefficient in all the constraints.
F. Which has zero coefficient in at least one of the constraints.
Solution: Any variable with positive value will increase the objective function and
can be selected.
7. (MSQ, 2 mark) In which of these circumstances we have reached the optimal in the
simplex algorithm
A. If all coefficients of variables in the objective function are positive.
B. If all coefficients of variables in the objective function are nonposi-
tive.
C. If all coefficients of variables in the objective function are zero.
D. If at least one coefficient of variables in the objective function is positive.
E. If at least one coefficient of variables in the objective function is zero.
Solution: In the correct cases, a positive increase in any nonbasic variable leads to
reducing the value.
—————————————————- END
2
START ——————————————–
Look at the following linear program given at the end of the simplex method.
max 23 − (1/5)u − (2/5)v − (6/5)w
s.t. y + (3/8)u + (2/5)v = 3/8
z − (1/4)u + (1/5)v + (4/5)w = 1/8
x + (4/5)u − (3/8)v + (1/5)w = 7/4
x, y, z, u, v, w ≥ 0.
8. (MCQ, 2 mark) The optimal solution for this linear program is:
A. x = 3/8, y = 0, z = 7/4, u = 0, v = −1/8, w = 0
B. x = 7/4, y = 3/8, z = 1/8, u = 0, v = 0, w = 0
C. x = 3/8, y = 1/8, z = 7/4, u = 0, v = 0, w = 0
D. x = 3/8, y = −1/8, z = 7/4, u = 1/8, v = 0, w = 7/4
E. x = 3/8, y = 0, z = 0, u = 1/8, v = 0, w = 7/4
F. x = 0, y = −1/8, z = 7/4, u = 3/8, v = 0, w = 0
Solution: Put the value of nonbasic variables (u,v,w) as zero.
9. (FB, 2 mark) The optimal value of this linear program is 23 .
Solution: The constant in the objective function is the value, since non-basic vari-
ables are zero.
—————————————————- END
10. (MCQ, 2 mark) In Bland’s rule, we choose the leaving variable by
A. the one which has highest value in the BFS solution.
B. the nonbasic variable which has the highest coefficient in the objective function.
C. The variable with the least index in the assumed order.
D. the basic variable with the least value in the BFS solution.
Solution: recall
