Scribd
Upload
78 views26 pages

Transportation Problem: - Transportation Problem - A "Special Case" of LP - Reasons?

Uploaded by

Fun Toosh345

The document discusses different methods for solving transportation problems: 1. The Northwest corner method assigns supply to demand starting from the top left cell moving right and down. 2. The Minimum cell cost method assigns supply to the cell with the lowest cost, blocks that cell, and repeats until all supply is assigned. 3. Vogel's approximation method calculates penalty costs for rows and columns, assigns supply to the row/column with the highest penalty cost and lowest cell cost, and repeats. 4. The stepping-stone and modified distributed methods can be used to check if the initial solutions are optimal by introducing non-basic variables as basics and forming closed loops. Dummy rows and columns address when total demand does

Copyright:

© All Rights Reserved
Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt

Transportation Problem: - Transportation Problem - A "Special Case" of LP - Reasons?

Uploaded by

Fun Toosh345
78 views26 pages
The document discusses different methods for solving transportation problems: 1. The Northwest corner method assigns supply to demand starting from the top left cell moving right and down. 2. The Minimum cell cost method assigns supply to the cell with the lowest cost, blocks that cell, and repeats until all supply is assigned. 3. Vogel's approximation method calculates penalty costs for rows and columns, assigns supply to the row/column with the highest penalty cost and lowest cell cost, and repeats. 4. The stepping-stone and modified distributed methods can be used to check if the initial solutions are optimal by introducing non-basic variables as basics and forming closed loops. Dummy rows and columns address when total demand does

Original Title

Modelling Transportation Problem

Copyright

© © All Rights Reserved

Available Formats

PPT, PDF, TXT or read online from Scribd

Did you find this document useful?

Is this content inappropriate?

The document discusses different methods for solving transportation problems: 1. The Northwest corner method assigns supply to demand starting from the top left cell moving right and down. 2. The Minimum cell cost method assigns supply to the cell with the lowest cost, blocks that cell, and repeats until all supply is assigned. 3. Vogel's approximation method calculates penalty costs for rows and columns, assigns supply to the row/column with the highest penalty cost and lowest cell cost, and repeats. 4. The stepping-stone and modified distributed methods can be used to check if the initial solutions are optimal by introducing non-basic variables as basics and forming closed loops. Dummy rows and columns address when total demand does

Copyright:

© All Rights Reserved
Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt
78 views26 pages

Transportation Problem: - Transportation Problem - A "Special Case" of LP - Reasons?

Uploaded by

Fun Toosh345
The document discusses different methods for solving transportation problems: 1. The Northwest corner method assigns supply to demand starting from the top left cell moving right and down. 2. The Minimum cell cost method assigns supply to the cell with the lowest cost, blocks that cell, and repeats until all supply is assigned. 3. Vogel's approximation method calculates penalty costs for rows and columns, assigns supply to the row/column with the highest penalty cost and lowest cell cost, and repeats. 4. The stepping-stone and modified distributed methods can be used to check if the initial solutions are optimal by introducing non-basic variables as basics and forming closed loops. Dummy rows and columns address when total demand does

Copyright:

© All Rights Reserved
Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt
You are on page 1/ 26

Transportation Problem

• Transportation problem - a “special case”


of LP

• Reasons?
– it can be formulated & solved using LP
technique
Review of Transportation Problem

Warehouse supply of televisions sets: Retail store demand for television sets:

1- Cincinnati 300 A - New York 200


2- Atlanta 200 B - Dallas 300
3- Pittsburgh 200 C - Detroit 200
total 700 total 600

From To Store
Warehouse
A B C
1 $16 $18 $11
2 14 12 13
3 13 15 17

2
A Transportation Example (2 of 3)
Model Summary and Computer Solution with Excel
Minimize Z = $16x1A + 18x1B + 11x1C + 14x2A + 12x2B + 13x2C + 13x3A + 15x3B + 17x3C

subject to
x1A + x1B+ x1C = 300
x2A+ x2B + x2C = 200
x3A+ x3B + x3C =300
x1A + x2A + x3A = 200
x1B + x2B + x3B = 250
x1C + x2C + x3C = 200
xij  0

3
Transportation Tableau

4
initial tableau
• Three different ways:
– Northwest corner method
– The Minimum cell cost method
– Vogel’s approximation method (VAM)

• Now, are these initial tableaus given us an


Optimal solution?

5
Northeast corner

150
150

50

--

6
Initial tableau of NW corner method
• Repeat the above steps, we have the following
tableau.
• Stop. Since all allocated have been assigned

Ensure that all columns and rows added up to its respective totals. 7
The Minimum cell cost method
Here, we use the following steps:
Steps:
Step 1 Find the cell that has the least cost
Step 2: Assign as much as allocation to this cell
Step 3: Block those cells that cannot be allocated
Step 4: Repeat above steps until all allocation have
been assigned.

8
Step 1 Find the cell that has the least cost
Step 2: Assign as much as allocation to this cell

Step 1:
Step 2:

200

The min cost, so allocate as much resource as possible here

9
Step 3: Block those cells that cannot be allocated
Step 4: Repeat above steps until all allocation
have been assigned.

Second iteration, step 4


Step 3:

--

--

200 75

10
The initial solution

• Stop. The above tableau is an initial tableau


because all allocations have been assigned

(to p8)
11
Vogel’s approximation method
Operational steps:
Step 1: for each column and row, determine its
penalty cost by subtracting their two of their
least cost
Step 2: select row/column that has the highest penalty cost
in step 1
Step 3: assign as much as allocation to the
selected row/column that has the least cost
Step 4: Block those cells that cannot be further allocated
Step 5: Repeat above steps until all allocations have been
assigned

12
subtracting their two of their
least cost

Step 1

(8-6)

(11-7)

(5-4)

(6-4) (8-5) (11-10)

13
Steps 2 & 3
Step 2:
Highest penalty
cost

Step 3: this has the least cost


14
Step 4

--- ---

15
Step 5
Second Iteration

---

--- ---

16
3 Iteration of VAM
rd

--- ---

--- ---

17
Initial tableau for VAM

18
Solution methods
• We need a method, like the simplex
method, to check and obtain the optimal
solution
• Two methods:

1. Stepping-stone method
2. Modified distributed method (MODI)

19
Stepping-stone method
Let consider the following initial tableau from the Min Cost algorithm

There are
Non-basic variables

These are basic


variables
Question: How can we introduce
a non-basic variable into basic variable?
20
Introduce
a non-basic variable into basic variables
• Here, we can select any non-basic variable as
an entry and then using the “+ and –” steps to
form a closed loop as follows:

let consider this non


basic variable

21
Stepping stone

+ -

- +

The above saying that, we add min value of all –ve cells into cell that has “+” sign, and subtracts
the same value to the “-ve” cells 22
Thus, max –ve is min (200,25) = 25, and we add 25 to cell A1 and A3, and subtract it from B1 and A3
Stepping stone

The above tableaus give min cost = 25*6 + 120*10 + 175*11


175*4 + 100* 5 = $4525

We can repeat this process to all possible non-basic cells in that above
tableau until one has the min cost! NOT a Good solution method 23
Total demand ≠ total supply

Note that, total demand=650, and total supply = 600

How to solve it?

We need to add a dummy row and assign o cost to each cell as such .. 24
Dd≠ss

Extra row, since Demand > supply


25
Dd≠ss

Extra column is added


26

You might also like