APM261: Quiz 7. Computational Complexity of Simplex Methods

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 x₁ - 5 x₃

subject to the constraints:

x₁ + x₂ <= -5
-x₁ - x₃ >= 6
x₁ + x₄ = -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?

x₀ = 0, where 0 is the vector of zeros
x₀ = 1/n, where 1 is the vector of units

x₀ = 
e_n/n

, where e_n is the unit vector for the component x_n

x₀ = 
e₁

, where e₁ is the unit vector for the component x₁

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

	`x₁`	`x₂`	`x₃`	`x₄`	`x₅`
`x₄`	0	-8	-5	1	0	-3
`x₁`	1	-1	2	0	0	1
`x₅`	0	-3	-4	0	1	-1
`z`	0	-4	-5	0	0	3

x₄ is departing variable, x₂ is entering variable
x₄ is departing variable, x₃ is entering variable
x₅ is departing variable, x₂ is entering variable
x₅ is departing variable, x₃ is entering variable

5: Suppose you have found an optimal solution with the value z = z₀ 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 z₀?

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

Your Results: