TU BCA Operations Research Master Guide: Linear Programming, Graphical Method, Simplex & Vogel’s VAM (Solved Board Numericals)
Author: Bhuban Subedi | Subject: Operations Research (CACS451) | Semester: Eighth Semester
In logistics optimization, algorithmic trading, supply chain management, and CPU resource scheduling, mathematical optimization models maximize profits or minimize operational costs under strict resource constraints. In the final semester of the Tribhuvan University BCA curriculum, Operations Research (CACS451) tests students on quantitative decision-making, Linear Programming Problems (LPP), Simplex algorithms, Transportation models, and Project Network CPM/PERT analysis.
In the final 60-mark TU board examination, computational numericals account for over 80% of the total marks. Group B and Group C consistently feature full 10-mark problems on the LPP Graphical Method, Simplex Method Table Iterations, and Vogel’s Approximation Method (VAM) for Transportation Problems.
In this guide, I will solve standard TU board numericals step-by-step.
1. Linear Programming Problem: Graphical Solution Method
Consider a standard maximization LPP with 2 decision variables:
Solved TU Board Problem 1: Graphical Method
Problem: Solve the following LPP graphically:
$$\begin{aligned}
\text{Maximize } Z &= 3x_1 + 5x_2 \
\text{Subject to:} \
x_1 + 2x_2 &\le 2000 \
x_1 + x_2 &\le 1500 \
x_2 &\le 600 \
x_1, x_2 &\ge 0
\end{aligned}$$
Step 1: Convert Inequalities into Boundary Lines:
1. Line 1: $x_1 + 2x_2 = 2000$
– If $x_1 = 0 \implies x_2 = 1000 \implies (0, 1000)$
– If $x_2 = 0 \implies x_1 = 2000 \implies (2000, 0)$
2. Line 2: $x_1 + x_2 = 1500$
– If $x_1 = 0 \implies x_2 = 1500 \implies (0, 1500)$
– If $x_2 = 0 \implies x_1 = 1500 \implies (1500, 0)$
3. Line 3: $x_2 = 600$ (Horizontal line)
Step 2: Find Intersection Points of Feasible Polygon:
– Point A (Origin): $(0, 0)$
– Point B: Intersection of $x_1$-axis and Line 2 $\implies (1500, 0)$
– Point C: Intersection of Line 1 and Line 2:
$$x_1 + 2x_2 = 2000$$
$$x_1 + x_2 = 1500 \implies x_2 = 500, \quad x_1 = 1000 \implies \mathbf{(1000, 500)}$$
– Point D: Intersection of Line 1 and Line 3 ($x_2 = 600$):
$$x_1 + 2(600) = 2000 \implies x_1 = 2000 – 1200 = 800 \implies \mathbf{(800, 600)}$$
– Point E: Intersection of $x_2$-axis and Line 3 $\implies (0, 600)$
Step 3: Evaluate Objective Function $Z = 3x_1 + 5x_2$ at Corner Points:
+---+-------------------+-----------------------------------+-----------------------+
| Pt| Corner Point (x1,x2)| Objective Calculation Z = 3x1 + 5x2| Value of Z |
+---+-------------------+-----------------------------------+-----------------------+
| A | (0, 0) | 3(0) + 5(0) | 0 |
| B | (1500, 0) | 3(1500) + 5(0) | 4,500 |
| C | (1000, 500) | 3(1000) + 5(500) = 3000 + 2500 | **5,500** |
| D | (800, 600) | 3(800) + 5(600) = 2400 + 3000 | 5,400 |
| E | (0, 600) | 3(0) + 5(600) | 3,000 |
+---+-------------------+-----------------------------------+-----------------------+
Optimal Solution: Maximum value $\mathbf{Z_{max} = 5,500}$ occurs at $\mathbf{x_1 = 1000, \; x_2 = 500}$.
2. Transportation Problem: Vogel’s Approximation Method (VAM)
VAM finds the Initial Basic Feasible Solution (IBFS) with minimal total transportation cost by evaluating unit penalty costs:
VAM Algorithm Steps:
- For each row and column, calculate the Penalty = (Difference between the two lowest cost cells).
- Identify the row or column with the highest penalty.
- In that selected row/column, allocate as much as possible to the cell with the absolute minimum cost.
- Cross out the satisfied row or column and repeat until all supplies and demands are exhausted.
+-------------------------------------------------------------------------------+
| TOTAL TRANSPORTATION COST FORMULA |
| Total Cost = \sum_{i} \sum_{j} (c_{ij} \times x_{ij}) |
+-------------------------------------------------------------------------------+
3. The Simplex Algorithm Overview
For problems with 3 or more decision variables where graphs cannot be drawn:
1. Convert inequalities into standard form equations by adding Slack Variables ($s_i \ge 0$) for $\le$ constraints or subtracting Surplus Variables for $\ge$ constraints.
2. Construct the Initial Simplex Table with basic variables having coefficients $c_j = 0$.
3. Compute net evaluation row: $z_j – c_j = \sum (c_B \cdot a_{ij}) – c_j$.
4. Optimality Test (Maximization): If all $(z_j – c_j) \ge 0$, the current solution is optimal.
5. Otherwise, select the most negative $(z_j – c_j)$ as the Entering Variable (Key Column), compute minimum ratio $\theta = \frac{X_B}{a_{ik}} > 0$ to identify the Leaving Variable (Key Row), and perform Gauss-Jordan row operations on the pivot element.
Frequently Asked Questions (FAQ)
Q1: What is Degeneracy in a Transportation Problem?
Degeneracy occurs when the number of allocated basic cells is less than $(m + n – 1)$, where $m$ is the number of supply sources and $n$ is the number of demand destinations. It is resolved by placing an infinitely small positive value $\epsilon$ in an independent unallocated cell.
Q2: What is the Dual Problem in LPP?
Every Linear Programming Problem (the Primal) has a corresponding symmetric optimization problem (the Dual). If the Primal is a Maximization problem with $\le$ constraints, the Dual is a Minimization problem with $\ge$ constraints.
