Suppose that the problem in Exercise 10 is the continuous relaxation of an integer programming problem (i.e., the same problem but with the restriction that the variables take integral values). Suppose further that the best known integral solution has value 8. Derive two inequalities from the dual solution that can be propagated to reduce domains. Also, derive an upper bound on the non-basic variable x3 from its reduced cost. (You can deduce the reduced cost from the slack in the corresponding dual constraint. Why?)
Exercise 10
Consider the linear programming problem
min 4x1+4x2+3x3
x1+2x2+x3>=2
2x1+x2+x3>=3
x1,x2,x3>=0
Solve the classical dual by hand and use the solution to obtain the surrogate that provides the tightest bound on the optimal value of the primal.
What is the optimal value? (There is no need to solve the primal directly.) Now use complementary slackness to find an optimal solution of the primal by solving two simultaneous equations.