## Quiz 7. Computational Complexity of Simplex Methods

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