IE 3315 Worked Examples

Teaching · IE 3315 Operations Research I · Worked examples

Each section has one idea, a short explanation, and something to try. The worked example is folded underneath for when you want every step, and the full math after that.

Simplex: corner to corner
Shadow prices and KKT
A transportation network
Branch and bound
Convexity: Hessians and Sylvester
Nonconvex problems and global solvers

1. Simplex: corner to corner

Turn a word problem into variables, an objective and constraints
Find the corner points of the feasible region
Explain how simplex moves from corner to corner, and report z and x

Problem. A shop makes chairs ($40 profit each) and tables ($50). A chair takes 1 hour of labor and 4 units of wood; a table takes 2 hours and 3 units. There are 40 hours and 120 units a week.

\max\ z = 40x_1 + 50x_2 \quad\text{s.t.}\quad x_1 + 2x_2 \le 40 \ \text{(labor)},\quad 4x_1 + 3x_2 \le 120 \ \text{(wood)},\quad x_1, x_2 \ge 0

The best answer is always at a corner. Simplex starts at one corner (make nothing), checks whether a neighbouring corner is better (a negative number in the z row says yes), moves there, and repeats. Each basis in the table is one corner on the graph.

Try it. Click a negative number in the z row to pick the entering variable, then press Pivot. Watch the table and the graph move together.

Profit per chair $40 Profit per table $50

Worked example: the graphical method

Draw each constraint from its intercepts. Labor: $(40, 0)$ and $(0, 20)$ . Wood: $(30, 0)$ and $(0, 40)$ .
Shade the feasible side (the origin passes both).
Find the corners. Where the lines cross, solve them together: $x_1 = 24$ , $x_2 = 8$ .
Check z at every corner: A $(0,0)$ 0; B $(30,0)$ 1,200; C $(0,20)$ 1,000; D $(24,8)$ 1,360.
Answer: $x = (24, 8),\ z = 1{,}360$

The feasible region, its corners, and the simplex path A → C → D.

Worked example: the pivots by hand

Corner A. Slacks $s_1$ (spare labor) and $s_2$ (spare wood) are the basis: $s_1 = 40,\ s_2 = 120,\ z = 0$ . The z row is $z - 40x_1 - 50x_2 = 0$ .
Entering variable: the most negative z-row number, $-50$ : $x_2$ enters.
Ratio test: labor $40/2 = 20$ , wood $120/3 = 40$ . Labor runs out first, so $s_1$ leaves: corner C $(0, 20)$ , $z = 1{,}000$ .
Again: z row $z - 15x_1 + 25s_1 = 1{,}000$ , so $x_1$ enters; ratios $20/0.5 = 40$ and $60/2.5 = 24$ , so wood leaves: corner D.
Stop: z row $z + 16s_1 + 6s_2 = 1{,}360$ , nothing negative. The 16 and 6 are the shadow prices.

2. Shadow prices and KKT

Write the dual of an LP and read its shadow prices
Explain a reduced cost
Use the KKT conditions to confirm a primal and a dual solution are optimal

Every LP has a dual that prices its resources: one price $y_i$ per constraint. A shadow price is how much z improves per extra unit of a resource. KKT checks a plan and a set of prices with three tests: the plan is feasible, the prices are feasible, and complementary slackness holds (slack means a zero price). As four lines:

Ax \le b,\ x \ge 0 \qquad A^\top y \ge c,\ y \ge 0 \qquad y\,(b - Ax) = 0 \qquad x\,(c - A^\top y) = 0

Try it. Change the resources and watch the best corner, the profit and the prices move. Then try your own prices in the KKT check.

Labor hours Wood units

Check KKT with any prices

Labor price y₁ Wood price y₂

Worked example: the dual, shadow prices and the KKT check

The primal and dual come in pairs: each primal constraint goes with a dual variable; the primal's $b$ is the dual's costs and its $c$ the dual's right-hand side; max becomes min; primal slacks are dual reduced costs.

\min\ w = 40y_1 + 120y_2 \quad\text{s.t.}\quad y_1 + 4y_2 \ge 40,\quad 2y_1 + 3y_2 \ge 50,\quad y \ge 0

Weak duality: any feasible pair has $cx \le by$ . Strong duality: at the optimum $cx = by$ , so when they match you can stop.
Both products are made, so both dual constraints are tight: $y = (16, 6),\ w = 1{,}360$ .
Shadow prices: labor is worth $16 an hour and wood $6 a unit, while labor stays between 30 and 80 hours and wood between 60 and 160.
Reduced cost: a bench earning $30, using 1 hour and 3 units, uses resources worth $16 + 3(6) = 34$ . Reduced cost $30 - 34 = -4$ : it stays out unless its profit passes $34.

KKT line	Plug in x = (24, 8), y = (16, 6)	Holds?
$Ax \le b$	labor $24 + 2(8) = 40 \le 40$ ; wood $4(24) + 3(8) = 120 \le 120$	yes
$A^\top y \ge c$	chair $16 + 4(6) = 40 \ge 40$ ; table $2(16) + 3(6) = 50 \ge 50$	yes
$y(b - Ax) = 0$	$16(0) + 6(0) = 0$	yes
$x(c - A^\top y) = 0$	$24(0) + 8(0) = 0$	yes

All four hold: $z = w = 1{,}360$ , both optimal. KKT is always necessary; it is also sufficient for convex problems (every LP), and only necessary for nonconvex ones.

The full KKT conditions, for nonlinear problems

For $\max f(x)$ subject to $g_i(x) \le b_i$ , dual feasibility becomes stationarity:

\begin{aligned} &\text{stationarity:} && \nabla f(x^*) = \textstyle\sum_i \lambda_i \nabla g_i(x^*)\\ &\text{primal feasibility:} && g_i(x^*) \le b_i\\ &\text{dual feasibility:} && \lambda_i \ge 0\\ &\text{complementary slackness:} && \lambda_i\,\big(b_i - g_i(x^*)\big) = 0 \end{aligned}

For the shop, $(40, 50) = 16\,(1, 2) + 6\,(4, 3)$ : the objective's direction is a positive mix of the binding constraints' directions.

Stationarity: c lies inside the cone of the binding constraints' normals.

Nonlinear example: $\min (x-3)^2 + (y-2)^2$ subject to $x + y \le 4$ gives $x^* = (2.5, 1.5)$ , $\lambda = 1$ ; the objective is convex, so it is the global minimum.

3. A transportation network

Write the standard transportation formulation
Draw it as a network of supply and demand nodes
Solve it and check it is optimal

Ship $x_{ij}$ from each supplier $i$ to each customer $j$ at cost $c_{ij}$ : every supply is shipped and every demand is met. Each plant and store is a node, each route an arc, and whole-number supplies give a whole-number answer.

\min \sum_{i,j} c_{ij}x_{ij} \quad\text{s.t.}\quad \sum_j x_{ij} = \text{supply}_i,\quad \sum_i x_{ij} = \text{demand}_j,\quad x_{ij} \ge 0

Try it. Change any shipping cost. The cheapest plan re-solves, and the network shows which arcs it uses.

Cost per unit	Store A (needs 70)	Store B (needs 80)
Plant 1 (has 50)	$	$
Plant 2 (has 60)	$	$
Plant 3 (has 40)	$	$

Worked example: three plants, two stores

Cheapest arcs first. Plant 2 to B costs $3: send 60. Plant 3 to A costs $3: send 40.
Fill what is left. A needs 30 more and B 20 more, from Plant 1.
Cost: $60(3) + 40(3) + 30(4) + 20(6) = 540$
Check. Prices with $u_i + v_j = c_{ij}$ on used arcs ( $u_1 = 0$ ): $v_A = 4,\ v_B = 6,\ u_2 = -3,\ u_3 = -1$ . Unused arcs' reduced costs $c_{ij} - u_i - v_j$ are 4 and 2, both positive: optimal.

The optimal plan: four arcs carry flow, $540.

4. Branch and bound

Solve the LP relaxation of an integer program
Branch on a fractional variable
Prune branches, and know when you are done

Problem. Maximize $5x_1 + 8x_2$ subject to $x_1 + x_2 \le 6$ and $5x_1 + 9x_2 \le 45$ , whole numbers only.

Relax (drop "whole numbers" and solve the LP: its z is a bound), branch on a fractional variable ( $x_2 \le 3$ or $x_2 \ge 4$ ), prune a branch that is infeasible, already whole, or no better than the best so far, and stop when nothing is left to branch.

Try it. Press Next to solve one LP at a time. Watch the region get cut and the tree grow.

Worked example: why rounding fails, and the whole tree

The LP answer is $(2.25, 3.75)$ , z = 41.25. Rounding to $(2, 4)$ breaks the second constraint (46 > 45); rounding down to $(2, 3)$ earns only 34.

The best whole-number point, (0, 5), is not near the LP optimum.

Seven LPs prove x = (0, 5), z = 40.

5. Convexity: Hessians and Sylvester

Build the Hessian of a function
Find the leading principal minors and apply Sylvester's criterion
Decide whether the objective and every constraint are convex

A convex problem has one valley, so any local minimum is the global one. To check a function: build the Hessian (second derivatives), take the leading principal minors $D_1 = H_{11}$ , $D_2 = H_{11}H_{22} - H_{12}^2$ , and apply Sylvester: all positive means convex (a bowl); alternating, starting negative, means concave (a dome); a negative $D_2$ means a saddle.

Try it. Move the sliders, or pick a shape. The checks update as you go.

a b c

Worked examples: a bowl and a saddle

\text{A: } f = 2x^2 + 2xy + 2y^2,\ H = \begin{bmatrix} 4 & 2 \\ 2 & 4 \end{bmatrix} \qquad \text{B: } f = x^2 + 4xy + y^2,\ H = \begin{bmatrix} 2 & 4 \\ 4 & 2 \end{bmatrix}

A: $D_1 = 4 > 0$ , $D_2 = 16 - 4 = 12 > 0$ : convex. Eigenvalues 6 and 2.
B: $D_1 = 2 > 0$ , $D_2 = 4 - 16 = -12 < 0$ : a saddle. Eigenvalues 6 and −2.
If a leading minor is 0, check every principal minor: all at least 0 still means convex (semidefinite).

Ellipses mean a bowl, hyperbolas a saddle. The arrows are the Hessian's eigenvectors.

6. Nonconvex problems and global solvers

Spot a nonconvex objective or constraint
Lift a polynomial into a quadratic by adding variables
Approximate other nonlinear terms with a Taylor series or pieces

With more than one valley, a local method stops in whichever one it starts in. Lift polynomials into quadratics (for $x^4$ , let $w = x^2$ , so $x^4 = w^2$ ) and approximate other functions with a Taylor series or straight-line pieces; then a global solver such as Gurobi, SCIP or BARON finds the best valley and proves it.

Try it. Pick a starting point. A local method slides downhill and stops in whichever valley it starts in.

Start x₀ Tilt t (the x term)

Worked example: x⁴ − 3x² + x

Convex? $f''(x) = 12x^2 - 6$ is negative near 0. No.
Two valleys: $x \approx -1.30$ ( $f \approx -3.51$ ) and $x \approx 1.13$ ( $f \approx -1.07$ ).
Lift: $\min\ w^2 - 3w + x$ subject to $w = x^2$ , $-2 \le x \le 2$ .
Solve globally (Gurobi, NonConvex=2): $x^* = -1.3008,\ f^* = -3.5139$

Two valleys: a global solver finds the deeper one and proves it.

How the global solvers do it

Spatial branch and bound: the tree from section 4, but branching on ranges of continuous variables. Each product such as $xy$ is bounded by a convex relaxation (McCormick envelopes), which gives the bounds that prune branches. Tight variable bounds make it much faster. Gurobi has solved nonconvex quadratic problems this way since version 9, and recent versions take functions such as $e^x$ directly.

Want the code? The LP examples, Gurobi LP/MIP examples and quadratic programming examples solve problems like these in Python, with Gurobi's free licence. For more on KKT, see APMonitor's KKT notes. The graduate course, IE 5301, adds decision trees, Markov chains and queues.

← IE 3315 Operations Research I