Quiz 1 Quiz 2 Quiz 3 Quiz 4 Quiz 5 Quiz 6 Quiz 7 Quiz 8 Quiz 9

Quiz 7. Computational Complexity of Simplex Methods

Enter your name:
Each question has only one correct answer. The results of the quiz do not affect the final marks.

1: The following statements are true except for ...

Computational time required by the simplex method may grow exponentially with the size of the system
Binary search methods have polynomial-time complexity
Method based on the representation theorem is more useful than the simplex method because it has the polynomial-time complexity
Karmarkar's projective algorithm is competitive to the simplex method because of its polynomial-time complexity

2: What method would you use to maximize the function:

z = -3 x1 - 5 x3

subject to the constraints:

x1 + x2 <= -5
-x1 - x3 >= 6
x1 + x4 = -3

where all variables are non-negative?

Revised simplex method
Two-phase method
Dual simplex method
Karmarkar's projective method

3: What is the starting point for the Karmarkar's projective algorithm in n dimensions?

x0 = 0, where 0 is the vector of zeros
x0 = 1/n, where 1 is the vector of units
x0 = en/n, where en is the unit vector for the component xn
x0 = e1, where e1 is the unit vector for the component x1

4: Identify entering and departing variables for the next iteration of the dual simplex method.


x1 x2 x3 x4 x5
x4 0 -8 -5 1 0 -3
x1 1 -1 2 0 0 1
x5 0 -3 -4 0 1 -1
z 0 -4 -5 0 0 3
x4 is departing variable, x2 is entering variable
x4 is departing variable, x3 is entering variable
x5 is departing variable, x2 is entering variable
x5 is departing variable, x3 is entering variable

5: Suppose you have found an optimal solution with the value z = z0 in the problem of minimization of z = c x, subject to the constraints

A x >= 0, x >= 0

If a new variable x' >= 0 is added to the problem, what may happen to the optimal objective function value z0?

The value z0 is not affected by the new variable x'
The value z0 may increase
The value z0 may decrease
The problem with the new variable x' may have empty feasible region


Your Results:


Quiz 1 Quiz 2 Quiz 3 Quiz 4 Quiz 5 Quiz 6 Quiz 7 Quiz 8 Quiz 9