Solved Exam Template
Solved Exam Template
Use this template whenever an exam question combines standard form, BFS, reduced costs, and simplex.
Template A — formulation problem
- Define variables with units.
- Write the objective.
- Translate every sentence into one constraint.
- Add sign restrictions.
- State the final LP clearly.
Example: investment model
Let $x_A,\ldots,x_H$ be the number of units bought in funds $A,\ldots,H$.
If fund $j$ has price $p_j$ and annual return rate $r_j$, the expected return per unit is $r_jp_j$.
The LP is
\[\max \sum_j r_jp_jx_j\]subject to
\[\sum_j p_jx_j\le 50000,\]bond requirement:
\[4.5x_A+4x_B+2.5x_C\ge15000,\]balanced requirement:
\[3x_D+4.5x_E+5x_F\ge20000,\]equity limit:
\[6x_G+5.5x_H\le5000,\]and
\[x_j\ge0.\]Template B — graphical problem
- Draw each boundary line.
- Use a test point to identify the correct half-plane.
- Mark the feasible region.
- Find all relevant vertices.
- Evaluate the objective at the vertices.
- Report the best point and objective value.
Warning
Do not assume $x_1,x_2\ge0$ unless it is explicitly given.
Template C — standard form
Course convention:
\[\min c^Tx \quad \text{s.t. } Ax=b,\;x\ge0.\]Rules:
| Original form | Standard-form change |
|---|---|
| $\max f(x)$ | replace by $\min -f(x)$ |
| $a^Tx\le b$ | add slack: $a^Tx+s=b$, $s\ge0$ |
| $a^Tx\ge b$ | subtract surplus: $a^Tx-s=b$, $s\ge0$ |
| $x_j\le0$ | set $x_j=-y_j$, $y_j\ge0$ |
| $x_j$ free | set $x_j=x_j^+-x_j^-$, both nonnegative |
Template D — BFS verification
Given a candidate $\bar x$:
- Convert the problem to standard form.
- Compute slack/surplus values to lift $\bar x$ into the full standard-form vector.
- Check feasibility: $A\bar x=b$, $\bar x\ge0$.
- Identify the positive variables.
- Select $m$ columns that can support the point.
- Check that those columns are linearly independent.
A feasible vector is a BFS if it can be represented by a basis $B$ with
\[x_B=B^{-1}b\ge0,\]and all nonbasic variables zero.
Template E — reduced-cost optimality check
For a minimization problem in standard form:
\[\bar c^T=c^T-c_B^TB^{-1}A.\]- If $\bar c_j\ge0$ for all $j$, the current BFS is optimal.
- If some $\bar c_j<0$, choose an entering variable and pivot.
Template F — one revised simplex iteration
At basis $B$:
- Compute $x_B=B^{-1}b$.
- Compute reduced costs.
- Choose entering $x_j$ with $\bar c_j<0$.
- Compute
- If $u_i\le0$ for all $i$, the problem is unbounded below.
- Otherwise compute
- The row attaining the minimum leaves the basis.
- Replace the leaving column with $A_j$.
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.