Unit 3: Probability distributions, LP and game theory

Normal distribution: a continuous, bell-shaped, symmetric distribution with mean = median = mode. Probabilities are found with Z = (X − μ)/σ and the normal table. About 68.27% of values lie within μ ± 1σ, 95.45% within μ ± 2σ and 99.73% within μ ± 3σ.

Linear programming (LP) optimises a linear objective function subject to linear constraints and non-negativity.

• Components: decision variables, objective function, constraints, non-negativity.
• Assumptions: linearity (proportionality, additivity), divisibility, certainty, finiteness.

• Corner points: (0, 0) Z = 0; (40, 0) Z = 1,600; (0, 40) Z = 2,400; intersection of 2x + 3y = 120 and 2x + y = 80 → y = 20, x = 30 → Z = 1,200 + 1,200 = 2,400. Two corners give the same Z — multiple optimal solutions (objective is parallel to the carpentry constraint).
• Special cases: multiple optima, unbounded solution, infeasible problem, redundant constraint.

• Convert inequalities to equations: add slack (≤), subtract surplus and add artificial variables (≥ or =).

• Big-M method: artificial variables are given a very large penalty −M in a maximisation objective (+M for minimisation) so they leave the basis; if an artificial variable remains positive in the final table, the problem is infeasible.
• Two-phase method: alternative to Big-M — first minimise the sum of artificial variables.
• Duality: every LP (primal) has a dual; optimal values are equal; dual values give shadow prices of resources.

• Degeneracy: a basic variable takes the value zero — ties in the minimum ratio; may cause cycling (resolved by perturbation or Bland's rule).
• Duality: every primal LP has a dual; if the primal maximises with ≤ constraints, the dual minimises with ≥ constraints; the objective values are equal at the optimum; dual variables = shadow prices (value of one more unit of a resource).

• Post-optimality (sensitivity) analysis: how the optimal solution changes with changes in objective coefficients, right-hand-side values (resources) or constraint coefficients — ranges of optimality and feasibility.

A game is a competitive situation where the gain of one player is the loss of the other (zero-sum).

• Terms: players, strategies (pure or mixed), payoff matrix (from the row player's view), value of the game, saddle point.
• Saddle point: an element that is the minimum of its row and the maximum of its column — maximin = minimax; both players use pure strategies.

• Dominance rule: a row that is ≤ another row in every column (for the maximising player) can be deleted; a column ≥ another column (for the minimising player) can be deleted.

Graphical solution of 2 × n and m × 2 games

• For a 2 × n game, plot each column's expected payoff as a line against the row player's probability p (0 to 1); the highest point of the lower envelope (maximin) gives the optimal p and value; the two lines meeting there form a 2 × 2 sub-game solved by the formula.
• For an m × 2 game, use the lowest point of the upper envelope (minimax).