Scribd Logo
Upload

Welcome to Scribd!

  • 38 views

    Transportation Problems: Feasible Solution

    Uploaded by

    NITESH SINGH
    This document discusses transportation problems and how to solve them. It defines a transportation problem as involving m sources of goods and n destinations, with costs associated with transporting goods from each source to each destination. The goal is to minimize total transportation costs while meeting supply and demand constraints. It provides an overview of key terms like feasible and basic feasible solutions. It also describes three methods for obtaining an initial basic feasible solution: the northwest corner rule, lowest cost entry method, and Vogel's approximation method. The document outlines a theorem and algorithm for testing if a basic feasible solution is optimal. It involves calculating cell evaluations for empty cells based on costs and transportation amounts. If all evaluations are positive the solution is optimal, if

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Transportation Problems: Feasible Solution

    Uploaded by

    NITESH SINGH
    38 views4 pages
    This document discusses transportation problems and how to solve them. It defines a transportation problem as involving m sources of goods and n destinations, with costs associated with transporting goods from each source to each destination. The goal is to minimize total transportation costs while meeting supply and demand constraints. It provides an overview of key terms like feasible and basic feasible solutions. It also describes three methods for obtaining an initial basic feasible solution: the northwest corner rule, lowest cost entry method, and Vogel's approximation method. The document outlines a theorem and algorithm for testing if a basic feasible solution is optimal. It involves calculating cell evaluations for empty cells based on costs and transportation amounts. If all evaluations are positive the solution is optimal, if

    Original Title

    B&T(part6) (1)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses transportation problems and how to solve them. It defines a transportation problem as involving m sources of goods and n destinations, with costs associated with transporting goods from each source to each destination. The goal is to minimize total transportation costs while meeting supply and demand constraints. It provides an overview of key terms like feasible and basic feasible solutions. It also describes three methods for obtaining an initial basic feasible solution: the northwest corner rule, lowest cost entry method, and Vogel's approximation method. The document outlines a theorem and algorithm for testing if a basic feasible solution is optimal. It involves calculating cell evaluations for empty cells based on costs and transportation amounts. If all evaluations are positive the solution is optimal, if

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    38 views4 pages

    Transportation Problems: Feasible Solution

    Uploaded by

    NITESH SINGH
    This document discusses transportation problems and how to solve them. It defines a transportation problem as involving m sources of goods and n destinations, with costs associated with transporting goods from each source to each destination. The goal is to minimize total transportation costs while meeting supply and demand constraints. It provides an overview of key terms like feasible and basic feasible solutions. It also describes three methods for obtaining an initial basic feasible solution: the northwest corner rule, lowest cost entry method, and Vogel's approximation method. The document outlines a theorem and algorithm for testing if a basic feasible solution is optimal. It involves calculating cell evaluations for empty cells based on costs and transportation amounts. If all evaluations are positive the solution is optimal, if

    Copyright:

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

    TRANSPORTATION PROBLEMS

    We can think about a transportation problem in a general way if there are m


    sources (say A1, A2, ..., Am) and n destinations (say B1, B2,....,Bn). We can use ai
    to denote the quantity of goods concentrated at points Ai (i=1,2,...., m) and bj
    denote the quantity of goods expected at points Bj (j =1,2,...,n). To represent
    transportation problem we can construct the following table:

    B1 B2 … Bn Stock
    A1 x11(c11) x12(c12) x1n(c1n) a1
    A2 x21(c21) x22(c22) x2n(c2n) a2
    ⋮ ⋮
    Am xm1(cm1) xm2(cm2) xmn(cmn) am
    Requirement b1 b2 … bn

    We assume the condition a1+a2+....+am=b1+b2+....+bn implying that the total


    stock of goods is equal to the summed demand for it.
    The cost of transportation is equal
    ∑ 𝑐𝑖𝑗 𝑥𝑖𝑗
    𝑖,𝑗
    Our task is to minimize this function subject to:
    𝑥11 + 𝑥12 + ⋯ + 𝑥1𝑛 = 𝑎1
    𝑥21 + 𝑥22 + ⋯ + 𝑥2𝑛 = 𝑎2
    ⋮
    𝑥𝑚1 + 𝑥𝑚2 + ⋯ + 𝑥𝑚𝑛 = 𝑎𝑚

    𝑥11 + 𝑥21 + ⋯ + 𝑥𝑚1 = 𝑏1


    𝑥12 + 𝑥22 + ⋯ + 𝑥𝑚2 = 𝑏2
    ⋮
    𝑥1𝑛 + 𝑥2𝑛 + ⋯ + 𝑥𝑚𝑛 = 𝑏𝑛
    The following terms are to be defined with reference to the transportation
    problems:

    Feasible Solution
    A set of non-negative allocations xij ≥ 0 which satisfies the row and column
    restrictions is known as feasible solution.

    Basic Feasible Solution


    A feasible solution to a m-origin and n-destination problem is said to be basic
    feasible solution if the number of positive allocations are (m+n–1).
    If the number of allocations in a basic feasible solutions are less than (m+n–1), it
    is called degenerate basic feasible solution

    Optimal Solution
    A feasible solution (not necessarily basic) is said to be optimal if it minimizes
    the total transportation cost.

    In order to find the solution of this transportation problem we have to follow the
    steps given below.
    (1) Initial basic feasible solution
    (2) Test for optimization.

    There are three different methods to obtain the initial basic feasible solution.

    (I) North-West corner rule

    (II) Lowest cost entry method

    (III) Vogel’s approximation method


    (a) Write the difference of minimum cost and next to minimum cost against
    each row in the penalty column. (This difference is known as penalty).
    (b) Write the difference of minimum cost and next to minimum cost against
    each column in the penalty row. (This difference is known as penalty).
    (c) Identify the maximum penalties and allocate the maximum units to the
    place where the cost is minimum. Then return to a).

    Exercise 9
    Determine an initial basic feasible solution to the following transportation
    problems.

    A1 A2 A3 A4 Stock
    B1 2 3 5 1 8
    B2 7 3 4 6 10
    B3 4 1 7 2 20
    Requirement 6 8 9 15

    A1 A2 A3 A4 Stock
    B1 10 8 5 9 14
    B2 12 13 6 11 16
    B3 8 7 10 6 5
    Requirement 6 10 15 4
    A1 A2 A3 A4 Stock
    B1 21 16 15 3 11
    B2 17 18 14 23 13
    B3 32 27 18 41 19
    Requirement 6 10 12 15

    Test for optimization.


    A basic feasible solution of an (m × n) transportation problem is said to be non-
    degenerate if it has following two properties :
    (a) Initial basic feasible solution must contain exactly m+n–1 number of
    individual allocations.
    (b) These allocations must be in independent positions. Independent positions of
    a set of allocations means that it is always impossible to form any closed loop
    through these allocations.
    The following theorem is also helpful in testing the optimality.

    Theorem
    If we have a basic feasible solution consisting of m+n–1 independent positive
    allocations and a set of arbitrary number ui and vj (i=1,2,...m; j=1,2,...n) such
    that crs = ur+vs for all occupied cells (r,s) then the evaluation dij corresponding to
    each empty cell (i, j) is given by dij = cij – (ui+vj).

    Algorithm for optimality test :


    In order to test for optimality we should follow the procedure as given below:
    Step 1 Start with basic feasible solution consisting of m+n–1 allocations in
    independent positions.
    Step 2 Determine a set of m+n numbers ui (i=1,2,....m) and vj (j=1,2,...n)
    such that for each occupied cells (r,s) crs = ur+vs
    Step 3 Calculate cell evaluations (unit cost difference) dij for each empty cell
    (i,j) by using the formula dij = cij – ( ui+vj )
    Step 4 Examine the matrix of cell evaluation dij for negative entries and
    conclude that
    (i) if all dij > 0 then solution is optimal and unique,
    (ii) if all dij ≥ 0 (at least one dij = 0) then solution is optimal and alternate
    solution also exists,
    (iii) if at least one dij < 0 then solution is not optimal.
    If it is so, further improvement is required by repeating the above process. See
    step 5 and onwards.
    Step 5
    (i) See the most negative cell in the matrix [ dij ].
    (ii) Allocate ɛ to this empty cell in the final allocation table. Subtract and add the
    amount of this allocation to other corners of the loop in order to restore
    feasibility.
    (iii) The value of ɛ, in general is obtained by equating to zero the minimum of
    the allocations containing –ɛ (not + ɛ) only at the corners of the closed loop.
    (iv) Substitute the value of ɛ and find a new allocation table.
    Step 6
    Again, apply the above test for optimality till you find all dij ≥ 0.

    You might also like