Description
Problem 1 (50pts). Consider the following linear program:
maximize 3×1 + 4×2 + 3×3 + 6×4
subject to 2×1 + x2 − x3 + x4 ≥ 12
x1 + x2 + x3 + x4 = 8
−x2 + 2×3 + x4 ≤ 10
x1, x2, x3, x4 ≥ 0.
(1)
After transforming the problem into standard form and apply Simplex method, we obtain the final
tableau as follow:
B 0 2 9 0 3 0 36
1 1 0 −2 0 −1 0 4
4 0 1 3 1 1 0 4
6 0 −2 −1 0 −1 1 6
a) Derive the dual problem of the linear program (1) and calculate a dual solution based on
complementarity conditions. Given that the optimal solution to the primal solution is unique,
investigate whether the dual solution is unique.
b) Do the optimal solution and the objective function value change if we
• decrease the objective function coefficient for x3 to 0?
• increase the objective function coefficient for x3 to 9?
• decrease the objective function coefficient for x4 to 5?
• increase the objective function coefficient for x1 to 7?
e) Find the possible range for adjusting the coefficient 8 of the second constraint such that the
current basis is kept optimal.
Problem 2 (50pts). An insurance company is introducing three products: special risk insurance,
mortgage insurance, and long-term care insurance. The expected profit is $500 per unit on special
risk insurance, $250 per unit on mortgage insurance and $600 per unit on long term care insurance.
The work requirements are as follows:
The management team wants to establish sales quotas for each product to maximize the total
expected profit.
1. Formulate this problem as a linear optimization problem. Specify the decision variables,
objective function, and constraints.
2. After solving the problem, the final simplex tableau (for the standard form) is given as below
(the variables are in the natural order as in the description of the problem):
B 0 50 0 0 140 80 35400
4 0 0.5 0 1 -0.7 0.1 153
1 1 0 0 0 0.4 -0.2 24
3 0 0.5 1 0 -0.1 0.3 39
Show the dual variables corresponding to the services of the three departments. Using complementarity conditions to explain why mortgage insurance is not sold.
3. Find the range of working hours available for underwriting to keep the current basis optimal.
4. Find the range of the expected profit on long-term care insurance such that the current basis
remains optimal.