LP Cheat Sheet Formulation · Graphical · Simplex · Big-M — Winston Row-0 form

Setup & Standard Form

• Row 0 (max): \(z-c_1x_1-c_2x_2-\dots-c_nx_n=0\) — objective coeffs flip sign when moved left of "=".
• Any \(b_i<0\) → multiply that whole row by \(-1\) first (this flips its inequality).
• Basic variable = currently in the solution (value read off its row's RHS). Nonbasic = temporarily set to 0. You always have exactly (# constraints) basic variables.
• bfs = basic feasible solution: a choice of which variables are basic where all variables come out \(\ge0\). Geometrically a bfs is a corner of the feasible region — simplex hops from one bfs to a better adjacent one until it's optimal.
• \(s_i\) = unused resource (slack) · \(e_i\) = amount above the minimum (surplus) · \(a_i\) = artificial: a fake variable only there to give a starting point, penalized out by \(M\).
• Assumptions: Proportionality · Additivity · Divisibility (fractions allowed) · Certainty.

1 · Formulation

1. Decision variableswhat you get to choose. \(x_i=\) # of ___ per [unit & period]. Define each precisely — a vague variable is the #1 way to lose points.
2. ObjectiveMax \(z\) (profit/revenue) or Min \(z\)/\(w\) (cost) \(=\sum c_ix_i\); each \(c_i\) = value gained or spent per unit of \(x_i\).
3. Constraints (one per limit; label each)put all variable terms on the left, the number on the right. Sense comes from the wording (box below).
4. Sign restrictions\(x_i\ge 0\) — you can't make a negative amount.

Type skeletons (read each: vars → objective → constraint pattern)

Product-mix — MAX profit. \(x_i=\) units of product \(i\) to make.

• Obj: Max \(z=\sum(\text{profit per unit})\,x_i\).
• One \(\le\) per shared resource: \(\sum(\text{amount used per unit})\,x_i\le\) total available.
• Demand cap (only if the problem states a most-you-can-sell/allow): write \(x_i\le D_i\) as its own \(\le\) constraint — nothing special, it just caps that one variable. In the answer it's either binding (you make exactly \(D_i\)) or has slack (making more wasn't worth it).

Diet / blend — MIN cost. \(x_i=\) amount of ingredient \(i\) used.

• Obj: Min \(w=\sum(\text{cost per unit})\,x_i\).
• One \(\ge\) per requirement: \(\sum(\text{nutrient per unit})\,x_i\ge\) minimum needed.

Multi-period — MIN cost. You must meet a known demand each period; you choose how much to make each period and carry any leftovers forward as inventory.

• Variables, one set per period \(t=1,2,\dots\):  \(x_t\) = number of units made at regular pay;  \(y_t\) = number of units made at overtime pay;  \(i_t\) = inventory (units left in stock at the end of period \(t\));  \(d_t\) = demand due in \(t\) (given).
• Objective: Min \(z=\sum_t\big(\text{unit cost}\cdot x_t+\text{OT cost}\cdot y_t+\text{holding cost}\cdot i_t\big)\).
• Balance — one "\(=\)" per period: \(i_t=i_{t-1}+x_t+y_t-d_t\).  In words: end-of-period stock = last period's leftover + what you made this period − what you shipped this period.
• The chaining is the whole trick: each period's starting stock \(i_{t-1}\) is the previous period's ending stock — that link is what ties the periods into one model.
• Anchor & limits: \(i_0\) = starting inventory (given, often 0);  \(i_t\ge0\) means demand must be met on time (no backorders);  \(x_t\le\) capacity if production is capped.

Scheduling / staffing — MIN workforce. "days-off" type: each worker works 5 consecutive days then gets 2 off; find the fewest workers that cover each day's staffing need.

• Variables: \(x_i\) = number of workers who start their week on day \(i\) (\(i=\)Mon…Sun). Careful: it's workers who begin that day, not workers present that day.
• Objective: Min \(z=x_1+x_2+\dots+x_7\) (total workers hired).
• Coverage — one \(\ge\) per day: (workers whose 5-day shift covers that day) \(\ge\) staff needed. A worker starting day \(i\) works days \(i,i{+}1,\dots,i{+}4\) (wrapping the week), so each day is staffed by that day's starter + the 4 previous days' starters.
• \(x_i\ge0\) (whole workers, but solve as LP).

2 · Graphical (2 vars)

1. Constraint → lineplot by intercepts: \(x_1{=}0\!\to\!x_2\)-int, \(x_2{=}0\!\to\!x_1\)-int.
2. Shade feasible sidesub \((0,0)\): TRUE → origin side, FALSE → far side; region = overlap (+ \(x\ge0\)).
3. Find cornersaxis = first binding line on that axis; interior = solve the two lines' \(2\times2\) by elimination; keep only those meeting all constraints.
4. Evaluate \(z\) at each cornermax = largest, min = smallest.

Alt (isoprofit): slide obj line — max away from O, min toward O; tangent vertex = optimum.

Binding = LHS=RHS at the optimum (resource used up) · Non-binding = slack left · Redundant = line never touches the region.

3 · Simplex (all \(\le\), max)

Standard form = all constraints are equations, all vars \(\ge0\). Basic vars = "active" (read values off the RHS); nonbasic vars = temporarily set to 0. Slacks form an identity matrix → the initial basis.

1. Convert the LP to standard formadd a slack \(s_i\) to each \(\le\). Row 0: \(z-c_1x_1-c_2x_2-\dots-c_nx_n=0\).
2. Obtain a starting bfsdecision vars (nonbasic) \(=0\); slacks (basic) \(=\) their RHS; \(z=0\).
3. Is the bfs optimal? If yes, STOP.optimal when every nonbasic variable has a nonnegative coefficient in Row 0 (max). Any negative Row-0 coefficient → not optimal.
4. If not optimal, find a better bfschoose one nonbasic var to enter the basis and one basic var to leave. Entering = variable that increases \(z\) fastest = most negative Row-0 coefficient. Leaving = ratio test (box); that row is the pivot equation. Do the row operations so the new basic values can be read off.
5. Go back to Step 3.

Minimization: enter the most positive Row-0 coefficient; optimal when every Row-0 coefficient is \(\le0\). (Or solve \(\max(-z)\), then \(\min z=-[\max(-z)]\).)

Snags: tie for most-negative → pick either · ratio-test tie → degeneracy (a basic var \(=0\)) · no positive entry in the entering column → unbounded.

4 · Big-M (any \(\ge\) or \(=\))

Used when there is no obvious starting bfs (a \(\ge\) or \(=\) constraint). Artificial variables give a start; the penalty \(M\) = a very large positive number forces them back to 0.

1. Step 1 — Fix RHSif any RHS \(<0\), multiply that constraint by \(-1\) (reverse the inequality).
2. Step 2 — Convert to equations\(\le\) add slack · \(\ge\) subtract surplus · \(=\) nothing yet.
3. Step 3 — Add artificials\(+a\) to every \(\ge\) and every \(=\) constraint.
4. Step 4 — Modify the objective Max: \(Z=(\text{orig})-Ma_1-Ma_2-\cdots\) → canonical \(Z-c_1x_1-c_2x_2+Ma_1+Ma_2=0\).
   Min: \(Z=(\text{orig})+Ma_1+Ma_2+\cdots\) → canonical \(z-c_1x_1-c_2x_2-Ma_1-Ma_2=0\).
5. Step 5 — Simplex; first eliminate artificials from Row 0they start basic, so before pivoting: New Row 0 = Row 0 \(+M\)(each artificial's row) for a min (subtract for a max). Coefficients become symbolic in \(M\) (a number plus a multiple of \(M\)); Row-0's RHS becomes the starting \(z\). Then run ordinary simplex carrying \(M\).

Two-Phase (alternative to Big-M): Phase I minimize \(W=\sum a_i\); if \(W=0\) a feasible start exists → drop artificials, Phase II on the real objective.

5 · Diagnostics

Row 0 max: \(z-c_1x_1-\dots=0\) · convert \(\le\!+s\), \(\ge\!-e+a\), \(=\!+a\) · Big-M: max \(-Ma\), min \(+Ma\) · divisibility → fractional answers OK.