Unit 3 – Simplex Method & Duality

Introduction

Operational Research (OR) is the science of decision‑making under constraints.
A Linear Programming Problem (LPP) is a special OR model where the objective and constraints are linear.
The Simplex method is the most widely used algorithm to solve LPPs exactly.
Duality is a fundamental property of LPs that associates a dual problem to every primal problem, revealing hidden economic meanings.

1. Simplex Method

1.1 Standard Form

A primal maximization problem is written as

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

To apply Simplex, we convert inequalities to equalities by adding slack variables $s\ge 0$:

$$Ax+Is=b.$$

The initial basic feasible solution (BFS) is obtained by setting decision variables $x$ to zero and taking $s=b$.

1.2 Simplex Tableau

The tableau records the coefficients of the constraints, the objective function, and the current basic variables.
A typical tableau for the example below is shown in Figure 1.

1.3 Pivot Operations

1. Entering variable – choose the most negative coefficient in the objective row (for maximization).
2. Leaving variable – compute the minimum ratio $\frac{\text{RHS}}{\text{pivot column}}$ among positive entries.
3. Pivot – divide the pivot row by the pivot element and eliminate the pivot column from other rows by row operations.

1.4 Simplex Algorithm (Mermaid Flowchart)

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

1.5 Worked Example – Bakery Production

A bakery produces two types of cakes:

• Type A requires 2 kg of flour and 1 kg of sugar.
• Type B requires 1 kg of flour and 1 kg of sugar.

The bakery has 5 kg of flour and 4 kg of sugar.
Profit per cake: ₹5 for A, ₹3 for B.

Formulate and solve:

$$\begin{array}{rl}\text{Max }z& =5x_1+3x_2\\ \text{s.t. }& 2x_1+x_2\le 5\\ & x_1+x_2\le 4\\ & x_1,x_2\ge 0.\end{array}$$

Step 1 – Standard form

Add slack variables $s_1,s_2$:

$$\begin{array}{rl}2x_1+x_2+s_1& =5\\ x_1+x_2+s_2& =4.\end{array}$$

Step 2 – Initial tableau (Figure 1)

Step 3 – First pivot

• Entering variable: $x_1$ (most negative coefficient $-5$).
• Leaving variable: $s_1$ (ratio $5/2=2.5$ vs $4/1=4$).

Pivot on element $2$ in row 1, column $x_1$.

Updated tableau (Figure 2)

Step 4 – Second pivot

• Entering variable: $x_2$ (coefficient $1.5$ in z‑row).
• Leaving variable: $s_2$ (ratio $1.5/0.5=3$ vs $2.5/0.5=5$).

Pivot on element $0.5$ in row 2, column $x_2$.

Final tableau (Figure 3)

Optimal solution:
$x_1=1$ cake of type A, $x_2=3$ cakes of type B, profit $z=₹15$.
All constraints satisfied and no negative coefficients remain in the objective row, so the solution is optimal.

2. Duality

2.1 Primal–Dual Relationship

For a primal maximization problem in standard form:

$$\begin{array}{rl}\text{Max }z& =c^{T}x\\ \text{s.t. }& Ax\le b,\\ & x\ge 0,\end{array}$$

the dual minimization problem is

$$\begin{array}{rl}\text{Min }w& =b^{T}y\\ \text{s.t. }& A^{T}y\ge c,\\ & y\ge 0.\end{array}$$

• Primal variables $x$ ↔ Dual constraints.
• Primal constraints $Ax\le b$ ↔ Dual variables $y$.
• Objective coefficients $c$ ↔ Dual RHS $b$.

2.2 Weak and Strong Duality

• Weak duality: For any feasible $x$ and $y$, $c^{T}x\le b^{T}y$.
• Strong duality: If both problems have optimal solutions, then $c^T{x}^{\ast }=b^T{y}^{\ast }$.

2.3 Dual of the Bakery Example

Primal (above) has $c=[5,3{]}^T$, $b=[5,4{]}^T$, $A=\left[\begin{array}{cc}2& 1\\ 1& 1\end{array}\right]$.
Dual:

$$\begin{array}{rl}\text{Min }w& =5y_1+4y_2\\ \text{s.t. }& 2y_1+y_2\ge 5\\ & y_1+y_2\ge 3\\ & y_1,y_2\ge 0.\end{array}$$

Solving dual by Simplex (Figure 4)

Pivoting yields optimal dual solution $y_1=1$, $y_2=2$, $w=15$, matching the primal optimum $z=15$.
The dual variables $y_1,y_2$ are the shadow prices: the marginal increase in profit per additional unit of flour or sugar.

2.4 Complementary Slackness

For optimal primal $x^{\ast }$ and dual $y^{\ast }$:

$$y_i(b_i-a_i^T{x}^{\ast })=0,x_j(c_j-a_j^T{y}^{\ast })=0.$$

In the bakery example, $s_1=0$ (flour constraint tight), so $y_1$ can be positive; $s_2=1.5>0$, so $y_2=0$.
This confirms the economic interpretation: flour is a binding resource, sugar is not.

3. Comparison of Primal and Dual

4. Advantages & Disadvantages of Simplex

5. Real‑World Applications

5.1 eSewa – Transaction Routing

eSewa processes millions of micro‑transactions daily.
It models the routing of funds through multiple payment gateways as an LPP:

• Decision variables: number of transactions routed via each gateway.
• Constraints: gateway capacity, regulatory limits.
• Objective: minimize transaction fee or maximize throughput.
  The simplex solution tells eSewa the optimal split of traffic to keep costs low while respecting limits.

5.2 Ncell – Tower Placement

Ncell must decide where to install new base stations to cover the Kathmandu Valley.
An LPP models:

• Variables: binary decision to build a tower at a candidate site.
• Constraints: coverage requirements, budget, interference limits.
• Objective: maximize coverage or minimize cost.
  The dual variables represent the marginal value of adding coverage to a specific area, guiding future investment.

5.3 Daraz – Warehouse Allocation

Daraz assigns orders to regional warehouses to minimize delivery time.
The problem is a transportation LP:

• Variables: number of orders shipped from warehouse $i$ to customer zone $j$.
• Constraints: warehouse capacity, demand fulfillment.
• Objective: minimize total shipping cost.
  Simplex yields the optimal shipment plan; dual prices indicate how much the cost would rise if a warehouse’s capacity were reduced.

6. In the Real World

Worked real‑situation example:
A local bakery (like the one in the worked example) uses the Simplex solution to decide how many cakes of each type to bake each day. The optimal mix (1 type A, 3 type B) maximizes profit given limited flour and sugar, exactly mirroring the theoretical example.

7. Exam Tip

• Formulation: Always write the problem in standard form before applying Simplex.
• Tableau: Keep the tableau clean; label rows and columns clearly.
• Pivot rules: Use the most negative coefficient for entering variable; minimum ratio for leaving variable.
• Dual questions: Identify primal and dual variables; write complementary slackness conditions.
• Interpretation: Explain the economic meaning of dual variables (shadow prices).
• Practice: Solve at least two full Simplex traces and one duality pair before the exam.

A standard scientific calculator used for manual simplex calculations (Image: LoMit, CC BY-SA 4.0, via Wikimedia Commons) Graph paper for sketching constraint lines and feasible region (Image: Mikus, CC BY-SA 4.0, via Wikimedia Commons) A pen for writing tableau entries during exams (Image: Petar Milošević, CC BY-SA 4.0, via Wikimedia Commons)