Mixed Exam Problems
Mixed Exam Problems
Mixed exam problems combine formulation, standard form, BFS verification, reduced costs, simplex, and interpretation.
General approach
- Identify the subtask.
- Keep the original LP separate from the standard-form LP.
- Use the original LP for interpretation.
- Use standard form for BFS, reduced costs, and simplex.
- Always report both $x^$ and $z^$.
Simulation 1 — formulation only
An investor has €50,000 and can invest in 8 funds. Funds A, B, C are bonds with prices $4.5,4,2.5$ and rates $7\%,8\%,6\%$. Funds D, E, F are balanced with prices $3,4.5,5$ and rates $6\%,9\%,9\%$. Funds G, H are equity with prices $6,5.5$ and rates $10\%,12\%$. At least €15,000 must be invested in bonds, at least €20,000 in balanced funds, and at most €5,000 in equity.
Tasks
- Define decision variables.
- Formulate the LP.
- State whether variables should be continuous or integer.
Solution outline
Let $x_A,\ldots,x_H$ be units purchased.
\[\max \sum_j r_jp_jx_j\]subject to budget, bond minimum, balanced minimum, equity maximum, and $x_j\ge0$.
Use continuous variables unless the problem explicitly says units must be indivisible.
Simulation 2 — graphical plus standard form
\[\min -x_1+3x_2\]subject to
\[x_1+x_2\le6,\] \[-2x_1+x_2\le2,\] \[x_1-x_2\le3.\]Tasks
- Solve graphically.
- Convert to standard form.
- Explain the nonnegativity trap.
Solution outline
The feasible vertices are
\[\left(\frac43,\frac{14}{3}\right), \quad \left(\frac92,\frac32\right), \quad (-5,-8).\]Objective values are
\[\frac{38}{3},\quad 0, \quad -19.\]Thus
\[x^*=(-5,-8), \qquad z^*=-19.\]Since no sign restrictions are stated, $x_1$ and $x_2$ are free. For standard form set
\[x_1=x_1^+-x_1^- , \qquad x_2=x_2^+-x_2^-.\]Then add slacks to all three $\le$ constraints.
Simulation 3 — BFS, reduced costs, simplex
\[\min -3x_1-2x_2\]subject to
\[x_1+x_2+s_1=4,\] \[2x_1+x_2+s_2=5,\] \[x\ge0.\]Start from $B={s_1,s_2}$.
Tasks
- Check the starting BFS.
- Compute reduced costs.
- Perform two simplex iterations.
- Report the optimal solution.
Solution outline
Initial BFS:
\[x=(0,0,4,5),\]with reduced costs
\[\bar c=(-3,-2,0,0).\]Iteration 1: $x_1$ enters, $s_2$ leaves. New BFS:
\[x=(5/2,0,3/2,0).\]Iteration 2: $x_2$ enters, $s_1$ leaves. New BFS:
\[x=(1,3,0,0).\]Reduced costs are then nonnegative, so
\[x^*=(1,3,0,0), \qquad z^*=-9.\]Simulation 4 — given candidate vector
Original:
\[\max x_1-5x_2+4x_3\]subject to
\[3x_1-2x_2+x_3=10,\] \[x_2+2x_3\le5,\] \[3x_1+5x_2+x_3\ge10,\] \[x\ge0.\]Candidate:
\[\bar x=(3,0,1)^T.\]Tasks
- Convert to standard form.
- Lift $\bar x$ with slack/surplus variables.
- Verify whether it is a BFS.
Solution outline
Standard form uses slack $s_1$ and surplus $s_2$:
\[x_2+2x_3+s_1=5,\] \[3x_1+5x_2+x_3-s_2=10.\]At $\bar x=(3,0,1)$:
\[s_1=3, \qquad s_2=0.\]So
\[\hat x=(3,0,1,3,0)^T.\]It is feasible, but the positive columns $A_1,A_3,A_{s_1}$ are linearly dependent, so the candidate is not a BFS.
Simulation 5 — BFS and optimality
Original:
\[\max 5x_1-5x_2\]subject to
\[x_1+x_2+x_3=4,\] \[-x_1+3x_2-6x_3\le-4,\] \[-3x_1+4x_2+4x_3\ge2,\] \[x\ge0.\]Candidate:
\[\bar x=(2,0,2)^T.\]Tasks
- Convert to standard form.
- Verify BFS.
- Check optimality with reduced costs.
Solution outline
The lifted vector is
\[\hat x=(2,0,2,10,0)^T.\]A valid basis is $B=[A_1,A_3,A_{s_1}]$, with determinant $-7\ne0$.
For the minimization form $\min -5x_1+5x_2$, reduced costs are
\[\bar c=(0,5,0,0,5/7).\]All are nonnegative, so the candidate is optimal.
Exam checkpoint
Practice under exam timing. Write the full pipeline: model, standard form if needed, BFS/reduced costs if asked, simplex iterations if asked, final objective value and interpretation.