A linear programming problem (LPP) is a mathematical method used to find the best (maximum or minimum) value of a linear objective function, subject to a set of linear constraints.

🔹 General Form of a Linear Programming Problem

An LPP can be written as:

Maximize or Minimize Z=c1x1+c2x2+⋯+cnxn\text{Maximize or Minimize } Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_nMaximize or Minimize Z=c1​x1​+c2​x2​+⋯+cn​xn​

Subject to constraints:

a11x1+a12x2+⋯+a1nxn≤b1a21x1+a22x2+⋯+a2nxn≤b2⋯am1x1+am2x2+⋯+amnxn≤bm\begin{aligned} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &\leq b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &\leq b_2 \\ \cdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n &\leq b_m \end{aligned}a11​x1​+a12​x2​+⋯+a1n​xn​a21​x1​+a22​x2​+⋯+a2n​xn​⋯am1​x1​+am2​x2​+⋯+amn​xn​​≤b1​≤b2​≤bm​​

and

x1,x2,…,xn≥0x_1, x_2, \dots, x_n \geq 0x1​,x2​,…,xn​≥0

🔹 Key Components

1. Decision Variables
   These are the unknowns you want to determine (e.g., x1,x2x_1, x_2x1​,x2​).
2. Objective Function
   The function you want to maximize or minimize.
3. Constraints
   Equations or inequalities that limit the values of the variables.
4. Non-negativity Condition
   Variables cannot be negative.

🔹 Example

Maximize profit:

$$Z=3x+2y$$

Subject to:

x+y≤4x≤2y≤3x,y≥0\begin{aligned} x + y &\leq 4 \\ x &\leq 2 \\ y &\leq 3 \\ x, y &\geq 0 \end{aligned}x+yxyx,y​≤4≤2≤3≥0​

🔹 Solution Methods

• Graphical Method (for 2 variables)
• Simplex Method (for larger problems)
• Interior Point Methods

🔹 Applications

Linear programming is widely used in:

• Business (profit maximization, cost minimization)
• Transportation and logistics
• Manufacturing
• Diet planning
• Resource allocation