Linear Programming and Optimization: Models, Methods, and Applications

1. Introduction

Linear programming (LP) is a mathematical framework for making optimal decisions when resources are limited. An LP problem consists of:

1. Decision variables $x_1,x_2,\dots ,x_n$ – quantities to determine.
2. Objective function $Z=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$ – to maximise or minimise.
3. Constraints $a_{i1}{x}_1+a_{i2}{x}_2+\cdots +a_{in}{x}_n\le b_i$ (or $\ge$, $=$).
4. Non‑negativity $x_j\ge 0$.

The set of all $(x_1,\dots ,x_n)$ satisfying the constraints is called the feasible region. Because all constraints are linear, the feasible region is a convex polytope. The optimal solution, if it exists, occurs at a corner point (vertex) of this polytope.

2. Standard and Canonical Forms

Transforming to canonical form introduces slack variables for $\le$ constraints, surplus variables for $\ge$ constraints, and artificial variables for $=$ constraints when needed.

3. Graphical Method (Two Variables)

The graphical method is intuitive for problems with only two decision variables. Steps:

1. Plot each constraint as a line on the $x_1$-$x_2$ plane.
2. Identify the feasible region (intersection of half‑planes).
3. Evaluate the objective function at each vertex of the feasible region.
4. Choose the vertex giving the best objective value.

3.1 Worked Example

Problem
A factory produces two products, $A$ and $B$.

• Profit: $P=4x_A+3x_B$.
• Constraint 1 (raw material): $2x_A+x_B\le 8$.
• Constraint 2 (labor): $x_A+3x_B\le 9$.
• Non‑negativity: $x_A,x_B\ge 0$.

Solution

1. Plot constraints

2. Vertices

• $V_1=(0,0)$
• $V_2=(4,0)$ (intersection with $x_B=0$)
• $V_3=(0,2)$ (intersection with $x_A=0$)
• $V_4=(2,2)$ (intersection of the two constraints)

3. Objective values

4. Optimal solution: $x_A=4,x_B=0$ with maximum profit $P=16$.

4. Simplex Method

The simplex method is an algorithmic procedure that moves from one basic feasible solution (BFS) to an adjacent one, improving the objective at each step until optimality is reached.

4.1 Simplex Tableau

A tableau is a tabular representation of the LP in canonical form. Each row corresponds to a constraint, and the last row represents the negative of the objective function.

Example Tableau (for the problem above after adding slack variables $s_1,s_2$)

4.2 Pivot Operations

1. Entering variable: column with most negative coefficient in the objective row (here $x_A$ with $-4$).
2. Leaving variable: row with the smallest non‑negative ratio $RHS/\text{pivot column entry}$.
3. Pivot: perform row operations to make the pivot element 1 and other entries in the column 0.

Repeat until no negative coefficients remain in the objective row.

4.3 Mermaid Diagram of Simplex Flow

flowchart TD
  A["Start: Form canonical tableau"] --> B["Check for optimality"]
  B -->|"Yes"| C["Optimal solution found"]
  B -->|"No"| D["Select entering variable (most negative)"]
  D --> E["Select leaving variable (minimum ratio)"]
  E --> F["Pivot to update tableau"]
  F --> B

5. Duality

Every LP (primal) has an associated dual problem. If the primal is a maximisation, the dual is a minimisation, and vice versa. Dual variables correspond to the constraints of the primal and represent shadow prices – the marginal value of relaxing a constraint by one unit.

5.1 Dual of the Example

Primal (P):
$$\begin{gathered} \max 4x_A+3x_B \\ \text{s.t. }2x_A+x_B\le 8,x_A+3x_B\le 9,x_A,x_B\ge 0 \end{gathered}$$

Dual (D):
$$\begin{gathered} \min 8y_1+9y_2 \\ \text{s.t. }2y_1+y_2\ge 4,y_1+3y_2\ge 3,y_1,y_2\ge 0 \end{gathered}$$

Solving the dual yields $y_1=1,y_2=1$, giving the same optimal value $Z^{\ast }=16$. The shadow prices $y_1,y_2$ indicate that increasing the right‑hand side of constraint 1 by one unit would increase the maximum profit by 1 unit.

6. Comparison of Solution Methods

7. Advantages and Disadvantages

8. Applications

9. In the Real World

Worked real‑world example – Daraz delivery scheduling:

• Decision variables $x_{ij}$: 1 if order $i$ is assigned to courier $j$, 0 otherwise.
• Objective: minimise ${\sum }_{i,j}{c}_{ij}{x}_{ij}$ where $c_{ij}$ is delivery cost.
• Constraints: each order assigned to exactly one courier; each courier’s capacity not exceeded.
• Solved by simplex to find the cheapest assignment.

10. Real Pictures

Transportation problem network diagram (Image: Михајло Анђелковић, CC BY-SA 3.0, via Wikimedia Commons)

11. Exam Tip

1. Formulate correctly – always write the problem in canonical form before applying simplex.
2. Check feasibility – ensure all RHS values are non‑negative; if not, use two‑phase simplex.
3. Track basic variables – keep a clear list of basic variables to avoid mistakes in pivoting.
4. Dual interpretation – be ready to explain shadow prices and their economic meaning.
5. Practice small problems graphically – they often appear in exams to test conceptual understanding.

Good luck!

In the real world

• eSewa uses linear programming for dynamic fee optimization to adjust transaction fees in real-time based on network load and user demand. The objective function maximizes revenue while keeping fees competitive, with constraints on transaction volume and user experience thresholds. The dual solution reveals the marginal impact of increasing transaction limits on revenue.

• Daraz applies simplex method for order routing optimization to assign delivery slots to couriers. Each order is a variable, and constraints include courier capacity, delivery time windows, and customer priorities. The optimal solution minimizes total delivery time while respecting all constraints.

• Ncell employs duality theory in network bandwidth allocation to balance data, voice, and IoT traffic. The primal problem maximizes throughput, while the dual provides shadow prices indicating how much additional revenue each unit of bandwidth would generate, guiding infrastructure investments.