Linear Programming

Introduction to Linear Programming

Linear Programming (LP) is an essential mathematical approach used for optimization, where the aim is to maximize or minimize a linear function within a set of linear constraints. The term 'linear' indicates that both the objective function and constraints are linear, involving variables only raised to the first power and multiplied by constants.

Key Components of LP

An LPP is defined by:
- Decision Variables: The unknowns we seek to solve.
- Objective Function: A linear function to be maximized or minimized.
- Constraints: A series of linear inequalities or equations that set limits on the decision variables.
- Non-negativity Restrictions: Decision variables must be greater than or equal to zero.

Mathematical Formulation

The LPP is generally formulated as:

Maximize/Minimize:  Z = c₁x₁ + c₂x₂ + ... + cₙxₙ
Subject to:
  a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁
  a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂
  ...
x₁, x₂, ..., xₙ ≥ 0

Here, Z is the objective function, c values are coefficients of the objective function, and a values are coefficients of constraints, while b values are constants.

Geometric Interpretation

LP problems can be represented geometrically in two dimensions with feasible regions formed by constraints. The optimum solution is found at the vertices of these regions (corner-point method).

Methods to Solve LP Problems

Several methods are available to solve LPPs:
1. Graphical Method (for two-variable problems)
2. Simplex Method (efficient for more variables)
3. Dual Simplex Method (when primal is infeasible)
4. Interior-Point Methods (for large-scale problems)
5. Software Tools (like Excel Solver) for automated solutions.

Steps to Solve LPPs

1. Formulate the problem with decision variables, objective function, and constraints.
2. Graph the constraints and identify the feasible region.
3. Plot the objective function and optimize it.
4. Verify the solution meets all constraints.

Another Example:

Types of LPPs

• Maximization Problem: Objective is to maximize profits.
• Minimization Problem: Objective is to minimize costs.
• Standard Form: Constraints in ≤ inequalities with non-negative variables.

Applications

LP is widely applicable in economics, business, and engineering, helping to resolve issues like resource allocation, transportation logistics, production planning, and more.

DOCN in Action: A Bakery Example

A bakery produces cakes and pastries. Each cake yields a profit of ₹40 and each pastry ₹30. The bakery has at most 200 hours of labor and 150 kg of flour per day.
A cake requires 4 hours and 3 kg flour; a pastry requires 2 hours and 3 kg flour. Decide how many of each to make to maximize profit.

D — Decision Variables
Let \(x\) = number of cakes, \(y\) = number of pastries.

O — Objective Function
Maximize profit:
\[
Z = 40x + 30y
\]

C — Constraints
Labor:
\[
4x + 2y \le 200
\]
Flour:
\[
3x + 3y \le 150
\]

N — Non-negativity
\[
x \ge 0,\quad y \ge 0
\]

Conclusion

Mastering fundamental LP concepts allows for effective problem-solving in optimization scenarios, aiding various decision-making processes under constraints.

Linear Programming (LP) — Worked Example

A. Diet Problem — Full LP Formulation + Graphical Solution

1) Problem Statement

Choose quantities of two foods to meet nutrition needs at minimum cost.

Daily requirements: at least 1200 calories and 36 g protein.

2) Decision Variables

Let
- \(x \ge 0\) = servings of Food A
- \(y \ge 0\) = servings of Food B

3) Objective (Minimize Cost)

\[
\min \ C = 30x + 20y
\]

4) Constraints (Nutrition)

• Calories: \(400x + 200y \ge 1200 \ \Rightarrow\ 2x + y \ge 6\)
• Protein: \(10x + 6y \ge 36 \ \Rightarrow\ 5x + 3y \ge 18\)
• Non-negativity: \(x \ge 0,\ y \ge 0\)

5) Graphical Method (Two-Variable LP)

Plot the lines:
- \(2x + y = 6\) (region above the line is feasible)
- \(5x + 3y = 18\) (region above the line is feasible)

Corner points of the feasible region (check intersections with axes and each other):

1. Intersection with axes for \(2x + y = 6\):
2. \(x=0 \Rightarrow y=6\) → \((0,6)\)
3. \(y=0 \Rightarrow x=3\) → \((3,0)\) (but check protein)
4. Intersection with axes for \(5x + 3y = 18\):
5. \(x=0 \Rightarrow y=6\) → \((0,6)\)
6. \(y=0 \Rightarrow x=\tfrac{18}{5}=3.6\) → \((3.6,0)\)
7. Intersection of the two lines:
   Solving
   \[
   \begin{cases}
   2x + y = 6 \
   5x + 3y = 18
   \end{cases}
   \Rightarrow x=0,\ y=6 \ (\text{same as } (0,6)).
   \]

Feasibility check & cost at corner points:
- \((3,0)\): Protein \(=5(3)+3(0)=15 < 18\) ⇒ infeasible.
- \((0,6)\): Feasible. Cost \(C = 30(0)+20(6)=120\).
- \((3.6,0)\): Feasible. Cost \(C = 30(3.6)+20(0)=108\).

Optimal Solution (Minimum Cost):
Alright 👍 here it is in a plain copyable format (not markdown):

x⁎ = 3.6, y⁎ = 0, Cₘᵢₙ = ₹108

Interpretation: Choose 3.6 servings of Food A and 0 of B to meet both requirements at the lowest cost.

Tip: In diet problems, fractional servings are allowed (continuous decision variables).

B. (Optional) LP Tableau Illustration (Maximization Example)

To see an LP tableau, it’s simpler to use a standard maximization with “\(\le\)” constraints (no artificial variables needed initially).

Example

Maximize \(Z = 5x + 4y\)
Subject to
\[
\begin{aligned}
6x + 4y &\le 24 \
x + 2y &\le 6 \
x, y &\ge 0
\end{aligned}
\]

Add slack variables \(s_1, s_2 \ge 0\):
\[
\begin{aligned}
6x + 4y + s_1 &= 24 \
x + 2y + s_2 &= 6
\end{aligned}
\]

Initial Simplex Tableau

• Entering variable: \(x\) (most negative in Z-row: \(-5\))
• Leaving variable: ratio test → \(24/6 = 4\) vs \(6/1 = 6\) ⇒ row 1 leaves (pivot at 6).

(You can continue the usual Simplex steps—normalize pivot row, eliminate \(x\) from others—to reach the optimal solution. Graphically, this one reaches optimum at \((x,y)=(2,2)\) with \(Z=18\).)