MODIFIED
DISTRIBUTION
METHOD (MODI)
HRIDYANSHU MAHAJAN-20242020
SUBMITTED TO:
RONIT GAUTAM-20242041 DR. ASHUTOSH YADAV
SARTHAK -20242044
ASSISTANT PROFESSOR
SHOURYA MAHLI-20242047
SEMESTER IV, BBA LLB (HONS.) UNIVERSITY OF DELHI
Introduction to Transportation
Problems
A specific type of distribution problem where transfers
of goods are made from various sources (or origins)
to different destinations
efficient method to handle the logistical challenge of
moving goods from the factories or warehouses where
they are produced to the markets where they are
required
CORE OBJECTIVE
The primary goal is to determine the optimal
shipping schedule
Ultimately, the objective is to execute these transfers in a
manner that ensures the total cost involved in transportation
is minimized
Key Data Points:
Supply: denoted as ai.
Demand: denoted as bj.
Unit Cost: denoted as cij
What isThe Variables and ParametersTo build the
Mathematical Model model, we first need to define our terms:
xij: The decision variable
Objective Function cij: The unit cost of transporting
minimize the total one product from origin i to
transportation cost, destination j.
denoted as $Z$
ai: The total quantity of the
product
(This represents the sum of the bj: The total quantity of the
quantities shipped on each route
multiplied by their respective unit product required
costs ).
Constraints
Supply Constraints:
Demand Constraints:
Non-negativity Condition:
Fundamental Assumption:
Phases of Solving a Transportation
Phase I: Initial Basic
Problem Phase II: Optimality
Feasible Solution (IBFS) Test
Purpose: "optimal" (cheapest)
Purpose: starting allocation that
solution.
satisfies all supply and demand The Process:
requirements (rim conditions). "opportunity costs" of all currently
Characteristics: exactly m+n−1 1. 6x +cells.
unoccupied 12y
Refinement: If the
6(xtest+ shows
2y) the
occupied cells.
solution is not optimal, perform a
The allocations must be non- redistribution of goods to reduce the
negative. 2. 16xy - 12x
cost and then test it again. This cycle
It provides a "baseline" cost 4(4x - 3)
continues until no further cost
reduction is possible.
Obtaining an Initial Before we can use the MODI method, we must first
Solution generate an Initial Basic Feasible Solution (IBFS). This
solution must satisfy all supply and demand
constraints. The three most common methods to
achieve this are:
1. North-West Corner (NWC)
Rule
[Link] Cost Method (LCM)
[Link]’s Approximation
Method (VAM)
Introduction to Optimality Tests
Two Common Methods
2. MODI Method (Modified
1. Stepping-Stone Method
Distribution)
Mechanism: closed "loop" for
Mechanism: streamlined
every empty cell in the tableau
version of the Stepping-Stone
method.
Limitation: tedious and
time-consuming for large Advantage: it uses row and
matrices, as you must column "dual variables" (ui
manually trace a path for and vi) to evaluate all
every single unoccupied cell. empty cells simultaneously.
What is the MODI Method?
Definition: a) 3(x + 18)
The MODI (Modified Distribution) Method, often referred to as the u-v
1 . Fact oris e fully
method, is an algebraic procedure used to test the optimality of a
transportation solution. b) 3(x + 6)
x + 18a basic feasible solution
begins3with
improves by identifying the most profitable route to which units should
be reallocated. c) 3(3x + 6)
"Dual" algorithms in linear programming, (ui for rows and vj for columns)
to evaluate the status of the current solution.
Prerequisites for the MODI Method
1. Feasibility (Rim 2. Non-Degeneracy
Requirements) Condition
Before testing for The Rule: For the MODI
optimality, the current method to function
shipping schedule must mathematically, the
be a Basic Feasible number of independent
Solution. basic variables (occupied
Condition: The allocations or filled cells) in the
must perfectly satisfy all solution must be exactly
"rim requirements".
.m + n - 1
MODI Method:
1. Assign ui to rows and vj to
The
3. Factorise fully
columns
2. Use occupied cells to solve for ui and vj
Algorithm 2
18x + 30x 3. Calculate opportunity costs for empty
Overview cells
[Link] for optimality
5. Improve the solution if necessary
Computing Dual Variables
Formula for Occupied Cells
apply the following equation:c ij = ui + vj
STEP - 1 Starting Point: The Zero Assignment
assign an arbitrary value of 0 to one of the
variables.
Solving for all u and v
use Formula to find the values of the other variables connected
via occupied cells.
if you know uiand the cell cost cij, then vj=cij−ui.
Continue this process until every row (u1, u2, um) and every column (v1, v2, vn) has
an assigned value.
[Link] Empty Cells
STEP - 2 [Link] Opportunity Cost Formula
Calculating Formula: ij = cij - (ui + vj)
Opportunity
Costs [Link] Meaning of ij
IF positive it means if negative it means the
using that route actual cost is lower than
would increase the the implied cost, and using
this route will decrease the
total cost.
total cost.
Step 3 – The Optimality Criterion
Evaluating the Results:Once all opportunity costs ( ij) for the
empty cells have been calculated, we apply the Optimality Criterion
to determine if the current distribution plan is the most cost-
effective.
Three Possible Outcomes:
1. Optimal Solution:
[Link] Optimal Solution:
[Link] Optimal Solutions
Step 4 – Selecting the
[Link] "Entering
Entering Variable
Variable" Concept
[Link] the Opportunity for By selecting this cell, we are
Improvement (Step 3) reveals designating it as the Entering
negative ij values, the current
Variable.
solution is not optimal.
In the next iteration, this
[Link] Selection Rule
previously empty cell will
Primary Rule: Identify all empty cells with
negative opportunity costs and choose
become an "occupied cell" with a
the one with the most negative ij specific quantity allocated to it,
value. while at least one currently
Tie-Breaking: If two or more empty cells
occupied cell will likely become
have the same most negative value, you
may choose any one of them arbitrarily. empty.
Step 5 – Drawing the Closed Path (Loop)
Purpose of the Loop Rules for Constructing the Loop
Once the "Entering Variable" Start and End: The loop must start at
(the empty cell with the most the selected empty cell and end at the
same cell.
negative ij) is identified, we
Nodes: Every other corner of the loop
must determine how much must be an occupied (allocated) cell.
quantity can be shifted into Movement: You can only move
this new route without horizontally or vertically. Diagonal
violating supply and demand moves are strictly prohibited.
[Link] loop Turns: A "turn" in the path can only
represents a chain reaction of occur at an occupied cell. You may skip
over other occupied or empty cells to
adjustments across the
reach a turning point.
tableau.
Shape: The loop is a "closed path."
Step 6 – Reallocating Quantities
Assigning Signs (+ and -)
Assign a plus sign (+) to the selected empty cell (the entering variable).
Alternating: Move along the loop and alternate minus (–) and plus (+) signs at
each corner (occupied cell) where the loop turns.
Identifying the Shift Value (θ)
Look only at the cells marked with a minus sign (–) on the loop.
Identify the smallest quantity currently allocated among these negative-
sign cells. This value is denoted as θ.
EXAMPLE
The Initial Tableau:NWC MWTHOD
SAMPLE
PROBLEM
INITIAL SOLUTION : FOR OPTIMALITY
SAMPLE
PROBLEM
IMPROVED SOLUTION:NON -OPTIMAL
SAMPLE
PROBLEM
IMPROVED SOLUTION:OPTIMAL
SAMPLE
PROBLEM
THANK YOU.