Tentamen

Question 1

How to bring a problem in standard form?

Answer 1

Just rewrite it to include slacks.

Question 2

How to do a simplex iteration?

Answer 2

Put in simplex tableau (note that everything needs to be multiplied by -1 in the objective function).

Check the lowest value (for min highest) value in the objective function, that is the entering variable, using the minimum ratio test find the leaving variable.

Make sure that the entering variable is 1, and in all the others 0.

Question 3

How to formulate the dual problem?

Answer 3

Rewrite the function s.t. you put y₁, y₂, … in front of every constraint, rewrite it s.t. you have x₁(….) + x₂(…). These are the constraints, they are ≥ then the objective coefficient (if they are ≤).

Then the dual objective is min (if max) and then c₁y₁ + c₂y₂ + … where c is every constraint. Don’t forget y ≥ 0

Question 4

How to find the optimal values when B^-1 is given?

Answer 4

Just B^-1 b, where b are the values of the constraints.

Question 5

How to find the optimal values of the dual when B^-1 is given?

Answer 5

Calculate c^T_B B^-1, where c_B are the coefficients of the optimal values in objective function.

Question 6

How to find how large a value needs to become before it becomes “intresting”?

Answer 6

Compute the n-th value of the dual function with the optimal values (of the dual), minus this by the constraint and that is it.

Question 7

How to derive a fractional cut?

Answer 7

1. Rewrite to keep all integer values before the = sign, and all the fractions behind, make sure all values behind the equality are negative.
2. Take what is behind the equality sign and ≤ 0.
3. Rewrite s.t. any fraction (without variable) is behind the ≤

Question 8

How to give the LP-relaxation and the best value in a 0-1 knapsack problem?

Answer 8

Just rewrite the in {0, 1} to in [0, 1]. Then take the fraction between every coefficent and the constraint. And add in the order from highest to lowest, add the last as a fraction. Don’t forget to give the objective value.

Question 9

How to solve the 0-1 knapsack-problem using B&B?

Answer 9

Start with the first solution, then add the constraint from the highest (first) value (so set to zero and one) and calulate. Continue from highest to lowest fraction. You can stop adding constraints when:

1. All constraints met
2. No bound attained (usually similar as one)
3. Not feasible

Question 10

What is the proof of weak duality?

Answer 10

Question 11

What is the proof of strong duality?

Answer 11

Question 12

How to proof a Lagrange relaxation?

Answer 12

Claim that the following:

1. Restrictions are L(𝜆) are also in Z^I
2. In addition, for every feasible solution x of Z^I we have sumⁿ _j=1 d_ijx_j = e_i or, equivalently, e_i −sumⁿ_j=1d_ijx_j = 0 for all i = 1 , . .., m.
3. Hence, sum ^m_i=1λ_i(e_i − sumⁿ_j=1d_ijx_j) = 0 and L(λ) ≥Z^I for all feasible solutions x of Z^I, so L(λ) is a relaxation of Z^I. This holds for all possible values of λ ∈ Rm.

Question 13

How to show that a basic feasible solution is optimal using B^-1(, and the dual)?

Answer 13

1. Calculate the solution of the dual first (c_B^T B^-1)
2. Calculate c_B^TB^-1A_i - c_i, where c_i is the coefficient, and A_i is a vector of the coeficients of the constrants of x_i, calculate this for every non-basic variable
3. If these values are all positive then this is a optimal solution.

Question 14

How to prove optimality using complementary slackness?

Answer 14

Show that:

(constraint value - constraint formula(with x_i*))y₁* = 0 for all constraints.