temi_esame2a.pdf
----------------

Problem 4)
----------
Given the following linear programming problem:
...
a) Rewrite the problem in standard form.
b) Give an upper bound on the number of basic feasible solutions of the problem, as a function of the number of constraints and variables.
c) Solve the problem via the Simplex method (applying Bland's rule). Indicate the optimal solution found and the objective function value, reporting all the iterations on the back of the previous page.
d) What is the reduced cost of a nonbasic variable from the objective function point of view? Report the reduced costs for the nonbasic variables on the optimal solutions that has been found.
e) Write the dual problem.
f) Deduce an optimal dual solution from the optimal primal one, clearly stating how it has been obtained.

Problem 5)
----------
Given the following linear programming problem:
...
a) Write the dual.
b) Solved the dual geometrically.
c) Deduce an optimal primal solution from an optimal dual one. State and explain on which property or theorem this deduction is based.

Problem 6)
----------
Given the following linear programming problem:
...
a) Rewrite the problem in standard form.
b) Carry out *two* iterations of the simplex method using Bland's rule. Only indicate the solution and the value of the objective function, reporting all the iterations on the back of the previous page.
c) Explain why the solution is optimal. Are there any other optimal solutions? Motivate the answer.
d) Write the dual problem.
e) State the complementary slackness conditions for this pair of primal and dual problems. Determine an optimal dual solution.

Problem 7)
----------
Solve the following integer linear programming problem
...
using the Branch-and-Bound method, solving the linear relaxations graphically. Explore first the subproblem with the most promising bound. If the solution of a relaxation has more than a single fractional component, branch on the component with the fractional part closest to 0.5.
a) Indicate the optimal solution that was found and the corresponding objective function value, reporting all the iterations (solutions of the subproblems) on the back of the previous page.
b) Report the enumeration tree.

temi_esame2b.pdf
----------------

Problem 5)
----------
Consider the following integer linear programming problem:
...
with the optimal tableau of the continuous relaxation
-31/4 |  0 0 1/2 0  1/4
----------------------
 11/4 | 1 0 -1/2 0  1/4
  9/4 | 0 1  3/2 0 -1/4
  1/2 | 0 0  -2  1 -1/2
a) Briefly describe the idea of the cutting plane method with Gomory cuts.
b) Determine the Gomory cut associated with the basic variable with the fractional part closest to 0.5.
c) Express the Gomory cut as a function of the decision variables x1 and x2 and represent it graphically with the other constraints that determine the feasible region of the integer linear program.
d) Which algorithm should we use to find an optimal solution of the continuous relaxation of the problem when adding the new constraint? Why?