Chapter 7: Linear Programming

7.1 Linear Programming Model

• Decision Variables: Unknown quantities to be determined, usually represented by $x$ and $y$.
• Constraints: Conditions or restrictions expressed as linear inequalities based on given scenarios.
• Objective Function: A linear function $K = ax + by$ representing total cost, profit, yield, or score to be maximized or minimized.

Key Inequality Keywords

Mathematical Inequality	Key Phrases / Keywords in Word Problems
$y \le ax + b$	At most, not more than, maximum value of $y$ is...
$y \ge ax + b$	At least, not less than, minimum value of $y$ is...
$y < ax + b$	Less than, smaller than, below...
$y > ax + b$	More than, greater than, exceeds...
$y \le kx$	$y$ is not more than $k$ times of $x$
$x + y \le K$	The total sum of $x$ and $y$ does not exceed $K$

7.2 Application of Linear Programming

Step-by-Step Graphical Method

1. Formulate Inequalities: Identify all constraints from the given text or table and write them in terms of $x$ and $y$.
2. Identify Non-Negativity Constraints: Usually $x \ge 0$ and $y \ge 0$ (since physical quantities cannot be negative).
3. Draw Boundary Lines: Treat inequalities as equations ($ax + by = c$), plot at least two points for each line, and draw solid lines for $\le, \ge$ or dashed lines for $<, >$.
4. Identify Feasible Region: Shade or locate the common region $R$ that satisfies all constraint inequalities simultaneously.
5. Optimize Objective Function ($K = ax + by$):
   • Assume a suitable initial constant value $k$ (e.g., $ax + by = k$) to draw a reference line.
   • Move a parallel ruler/line across the feasible region $R$:
     • Maximum Value: The furthest point $(x, y)$ in region $R$ touched by the moving parallel line away from origin.
     • Minimum Value: The first point $(x, y)$ in region $R$ touched by the moving parallel line nearest to origin.
   • Substitute the integer coordinates of the optimal point into $K = ax + by$ to evaluate the maximum or minimum value.