Linear programming (LP) converts real-world decision problems into mathematical models with an objective and constraints. This page explains how to formulate LPs step-by-step with diagrams and numerical examples.

1. Components of a Linear Program

• Decision variables — what you control.
• Objective function — maximize or minimize.
• Constraints — limits on resources or requirements.
• Nonnegativity — variables ≥ 0.

2. Example: Product Mix Problem

A factory makes two products using machine time and labor.

Product 1: profit 40, machine 2 hrs, labor 1 hr
Product 2: profit 30, machine 1 hr, labor 1.5 hrs

Machine capacity = 100 hrs
Labor capacity = 90 hrs

Step 1: Define variables

\(x_1\) = units of Product 1 \(x_2\) = units of Product 2

Step 2: Objective

\[ \text{Maximize } Z = 40x_1 + 30x_2 \]

Step 3: Constraints

Machine: \[ 2x_1 + x_2 \le 100 \] Labor: \[ x_1 + 1.5x_2 \le 90 \]

Step 4: Nonnegativity

\[ x_1, x_2 \ge 0 \]

3. Feasible Region Diagram

   x2
   ^
90 |\
   | \
   |  \
   |   \  machine
   |    \
   |     \
   +------------------> x1
         50   100

The optimal solution lies at a corner point of the feasible region.

4. Example: Diet Problem

Choose foods to meet nutrition requirements at minimum cost.

Food A: cost 2, protein 3, carbs 4
Food B: cost 3, protein 4, carbs 2

Protein ≥ 20
Carbs ≥ 18

Variables: \(x_A, x_B\) = servings Objective: minimize \(2x_A + 3x_B\) Constraints: \[ 3x_A + 4x_B \ge 20 \] \[ 4x_A + 2x_B \ge 18 \]