Topic:- Finding the solution to L.P.P. by graphical method.
Obtaining initial
transportation cost by MMM and NWCR method.
Solution to L.P.P. by Graphical Method and
Initial Transportation Cost Using NWCR and
MMM
Part 1: Linear Programming Problem (L.P.P.) – Graphical
Method
1.1 Introduction
Linear Programming is a widely used mathematical technique for optimizing an objective
function subject to constraints. The objective can either be maximization (profit, revenue,
production) or minimization (cost, time, resources). LPP finds applications in industries,
business planning, transportation, and resource allocation.
The key elements of an LPP are:
1. Decision Variables: Variables under our control that determine
outcomes, denoted as for two-variable problems.
2. Objective Function: Linear function to maximize or minimize.
Example: , where is profit.
3. Constraints: Linear inequalities restricting feasible solutions, e.g., , .
4. Non-negativity Restrictions: Decision variables cannot be negative,
i.e., .
Graphical method is suitable only for two-variable problems, as it allows visual plotting and
identification of feasible regions and optimal points.
1.2 Step-by-Step Graphical Method
Let’s solve the following example:
Maximize
Z = 3x + 2y
Subject to constraints:
\begin{aligned}
x + 2y &\le 8\\
3x + y &\le 9\\
x &\ge 0, y \ge 0
\end{aligned}
Step 1: Convert inequalities to equalities
To plot the constraints, convert each inequality to equality:
1.
o If , then
o If , then
2.
o If , then
o If , then
Step 2: Plot the feasible region
Draw both lines on the - plane, taking the first quadrant (since ).
Shade the region below each line (satisfying ) — the intersection is the
feasible region.
Step 3: Identify corner points
Feasible solutions occur within the region. The optimal solution occurs at corner points
(extreme points).
Find intersections:
1. Intersection with axes:
o , → Origin:
o with →
o with →
2. Intersection of two lines: Solve
\begin{cases}
x + 2y = 8\\
3x + y = 9
\end{cases}
3(8-2y) + y = 9 \Rightarrow 24 - 6y + y = 9 \Rightarrow -5y = -15 \Rightarrow
y = 3
Step 4: Evaluate objective function at corner points
Z = 3x + 2y
Poin
t
A 000
B 048
C 309
1
D 23
2
Step 5: Select optimum
Maximum at
Minimum at
1.3 Observations
Graphical method visually demonstrates feasible region, constraints,
and optimum.
If objective function is parallel to a constraint edge, multiple optimal
solutions exist along that edge.
If feasible region is unbounded, maximum or minimum may not
exist.
Extends to practical problems such as production planning, resource
allocation, diet optimization, and workforce scheduling.
Part 2: Transportation Problem – Initial Feasible Solution
2.1 Introduction
A transportation problem is a special linear programming problem aiming to minimize total
transportation cost from sources (factories) to destinations (warehouses or customers) while
satisfying supply and demand.
Decision Variables: = units transported from source to destination
Objective Function: Minimize
Constraints: Supply and demand limitations
Two popular methods to find initial feasible solutions:
1. North-West Corner Rule (NWCR)
2. Minimum Cost Method (Least-Cost Method / MMM)
2.2 Step-by-Step Example
Supplies:
A = 20, B = 30, C = 25
Demands:
D1 = 10, D2 = 25, D3 = 20, D4 = 20
Cost Matrix:
D D D D
1 2 3 4
A 8 6 10 9
B 9 12 13 7
C 14 9 16 5
2.3 North-West Corner Rule (NWCR)
1. Start at top-left cell (A→D1). Allocate maximum possible.
2. Move right if supply exhausted, down if demand satisfied.
3. Repeat until all supply & demand are allocated.
Allocation Table:
D D D D Suppl
1 2 3 4 y
A 10 10 0 0 0
B 0 15 15 0 0
C 0 0 5 20 0
Deman
0 0 0 0
d
Total Cost Calculation:
10\cdot8 + 10\cdot6 + 15\cdot12 + 15\cdot13 + 5\cdot16 + 20\cdot5 = 695
2.4 Minimum Cost Method (MMM)
1. Choose lowest-cost cell among remaining feasible cells.
2. Allocate maximum units respecting supply/demand.
3. Repeat until all supply/demand satisfied.
Allocation Table:
D D D D Suppl
1 2 3 4 y
A 0 20 0 0 0
B 10 0 20 0 0
C 0 5 0 20 0
Deman
0 0 0 0
d
Total Cost Calculation:
20\cdot6 + 10\cdot9 + 20\cdot13 + 5\cdot9 + 20\cdot5 = 615
Observation: MMM gives a better initial cost than NWCR.
2.5 Optimization After Initial Solution
The initial solution (NWCR or MMM) may not be optimal.
MODI Method / Stepping Stone Method used to check optimality
and reduce total cost.
Steps:
1. Compute dual variables from allocated cells.
2. Compute reduced costs .
3. If all , solution is optimal.
4. If any , adjust allocations along closed loops to reduce cost.
2.6 Key Points
1. NWCR is simple but may give high initial cost.
2. MMM uses cost information to improve initial solution.
3. MODI method ensures global optimal solution.
4. Transportation problem is a special LPP, but graphical method is
impractical for many sources/destinations.
Part 3: Summary
Graphical LPP is a visual method for 2-variable problems. It shows
feasible region, corner points, and optimum.
Transportation problem can be solved systematically by NWCR or
MMM to find an initial feasible solution.
MMM generally provides a better starting solution, but optimality is
verified using MODI method.
Understanding LPP and transportation problems together shows the
connection between linear programming and real-life cost
optimization.
Word count: ~1020 words
This explanation includes full step-by-step reasoning, formulas, tables, and conceptual notes
so it can serve as a complete reference for LPP and transportation problem initial solutions.
I can also create diagrams for the LPP feasible region and transportation allocations if you
want a visual version, which would enhance understanding.
Do you want me to add diagrams too?