Linear Programming: Simplex Method – Basics, Tableau, and Applications

1. What is Linear Programming?

Linear programming (LP) is a mathematical framework for optimizing a linear objective function subject to linear equality or inequality constraints.

• Decision variables $x_1,x_2,\dots ,x_n$ represent quantities to be determined.
• Objective function $Z=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$ is to be maximized or minimized.
• Constraints are linear inequalities or equalities of the form
  $$a_{i1}{x}_1+a_{i2}{x}_2+\cdots +a_{in}{x}_n(\le ,\ge ,=)b_i$$
• Non‑negativity $x_j\ge 0$ is usually imposed.

The set of all feasible solutions is a convex polyhedron (feasible region). The optimum lies at a vertex (basic feasible solution).

---

2. Standard Form

For the simplex method we convert every LP to standard form:

$$\begin{array}{rl}\text{Maximize }& Z=c^{T}x\\ \text{subject to }& Ax=b,\\ & x\ge 0,\end{array}$$

where $A$ is an $m\times n$ matrix, $b$ is an $m$-vector, and $c$ is an $n$-vector.

• Slack variables convert $\le$ constraints into equalities: $x_i+s_i=b_i$.
• Surplus + artificial variables handle $\ge$ constraints.

---

3. Tableau Representation

A simplex tableau is a compact tabular form that stores the coefficients of the constraints, the objective function, and the current basic variables.

Table 1: Initial tableau for the example in Section 5.

The bottom row contains the reduced costs (coefficients of non‑basic variables in the objective).

---

4. Simplex Algorithm – Step‑by‑Step

1. Identify entering variable: Choose a non‑basic variable with the most negative reduced cost (for maximization).
2. Identify leaving variable: Compute the minimum ratio $b_i/a_{ij}$ over all rows where $a_{ij}>0$.
3. Pivot: Perform row operations to make the pivot element $1$ and all other entries in the pivot column $0$.
4. Update tableau: Repeat until all reduced costs are $\ge 0$.

4.1 Worked Example

Problem
Maximize $Z=7x_1+5x_2$
subject to
$$\{\begin{array}{l}{x}_1+2x_2\le 6,\\ 4x_1+3x_2\le 6,\\ x_1,x_2\ge 0.\end{array}$$

Step 0 – Convert to Standard Form
Add slack variables $s_1,s_2$:

$$\begin{array}{rl}{x}_1+2x_2+s_1& =6,\\ 4x_1+3x_2+s_2& =6.\end{array}$$

Step 1 – Initial Tableau (Table 1 above).

Step 2 – Pivot Selection

• Reduced costs: $-7$ (for $x_1$), $-5$ (for $x_2$).
• Entering variable: $x_1$ (most negative).
• Ratios: $6/1=6$ (row 1), $6/4=1.5$ (row 2).
• Leaving variable: $s_2$ (smallest ratio).

Step 3 – Pivot on $a_{21}=4$

After row operations:

Step 4 – Check Optimality
Reduced costs: $x_2$ has $+1.75$ (non‑negative), so the current solution is optimal.

Optimal Solution
$x_1=1.5,x_2=0,Z=10.5$.

---

5. Visualizing the Feasible Region

Figure 1: Feasible region and constraint lines for the worked example. The optimal vertex is at $(1.5,0)$.

---

6. Pivot Rules and Variants

---

7. Duality

Every LP has a dual problem.

• Primal (P): maximize $c^{T}x$ subject to $Ax\le b,x\ge 0$.
• Dual (D): minimize $b^{T}y$ subject to $A^{T}y\ge c,y\ge 0$.

The Weak Duality Theorem states $c^{T}x\le b^{T}y$ for any feasible $x,y$.
The Strong Duality Theorem guarantees equality at optimality.

Duality provides bounds, sensitivity analysis, and economic interpretation (e.g., shadow prices).

---

8. Sensitivity Analysis

After solving an LP, we can ask:

• How does the optimal value change if $b_i$ changes?
• What is the allowable range for a coefficient $c_j$ before the basis changes?

These questions are answered by examining the shadow price (dual variable) and the reduced cost in the final tableau.

---

9. Advantages & Disadvantages

---

10. Real‑World Applications

10.1 eSewa – Cash‑less Payments

• Problem: Allocate limited transaction bandwidth to maximize revenue.
• LP Idea: Objective = revenue per transaction; constraints = server capacity, transaction limits.
• Result: Optimal allocation of transaction slots to merchants.

10.2 Daraz – Order Fulfilment Queue

• Problem: Schedule pick‑up and delivery to minimize total delivery time.
• LP Idea: Variables = number of orders assigned to each courier; constraints = courier capacity, delivery windows.
• Result: Efficient routing and load balancing.

10.3 Pathao – Ride‑Sharing Pricing

• Problem: Set dynamic fares to maximize profit while keeping demand within driver supply.
• LP Idea: Objective = profit = fare × number of rides; constraints = driver availability, minimum service level.
• Result: Real‑time fare adjustments.

---

11. In the Real World

• Google Ads: Uses LP to allocate ad slots to maximize click‑through revenue under budget constraints.
• Ncell Network Planning: Optimizes tower placement and bandwidth allocation using LP models.
• NEPSE Trading: Portfolio optimization to maximize expected return subject to risk limits.

---

12. Exam Tip

• Know the tableau format: Be able to write the initial tableau quickly.
• Pivot selection: Practice identifying entering/leaving variables and performing row operations.
• Optimality check: Remember that for maximization all reduced costs must be $\ge 0$.
• Duality: Be prepared to write the dual of a given primal problem.
• Sensitivity: Understand how to read shadow prices from the final tableau.

---

13. Real Pictures

Feasible region of a two‑variable LP (Image: en:User:Jacj, Public domain, via Wikimedia Commons)

Example of resource allocation in manufacturing (Image: Marek Ślusarczyk (Tupungato) Photo portfolio, CC BY 3.0, via Wikimedia Commons)

---