انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

Transportation Problem

Share |
الكلية كلية التربية للعلوم الصرفة     القسم  قسم الرياضيات     المرحلة 4
أستاذ المادة مشتاق عبد الغني شخير الجنابي       20/03/2021 19:11:30
Transportation Problem

The Transportation Problem (T.P.) is a special class of linear programming problems, where the objective is to minimize the cost of distributing a product from a number of sources (e.g. factories) to a number of destinations (e.g. warehouses ) while satisfying both the supply limits and the demand requirement.
Because of the special structure of the T.P., the simplex method is unsuitable for it. The model assumes that the distributing cost on a given route is directly proportional to the number of units distributed on that route. Generally, the transportation model can be extended to areas other than the direct transportation of a commodity, including among others, stored control, employment scheduling, etc.
Example:
Suppose a manufacturing company owns three factories (sources) and distribute its products to five different retail agencies (destinations). The following table shows the capacities of the three factories, the quantity of products required by the various retail agencies and the cost of shipping one unit of the product from each of the three factories to each of the five retail agencies.
Retail Agency
Factories 1 2 3 4 5 Capacity
1
2
3 1
24
14 9
12
33 13
16
1 36
20
23 51
1
26 50
100
150
Requirement 100 60 50 50 40 300
Usually the above table is referred as Transportation table, which provides the basic information regarding the transportation problem. The quantities inside the table are known as transportation cost per unit of product. The capacity of the factories 1, 2 and 3 is 50, 100 and 150 respectively. The requirement of the retail agency 1, 2, 3, 4 and 5 is 100, 60, 50, 50, and 40 respectively.
In this case, the transportation cost of one unit:
from factory 1 to retail agency 1 is 1,
from factory 1 to retail agency 2 is 9,
from factory 1 to retail agency 3 is 13,
from factory 2 to retail agency 1 is 24,
and so on… .
A transportation problem can be formulated as linear programming problem using variables with two subscripts. Let:
x11=Amount to be transported from factory 1 to retail agency 1.
x12= Amount to be transported from factory 1 to retail agency 2.
……..
……..
……..
x35= Amount to be transported from factory 3 to retail agency 5.
Let the transportation cost per unit be represented by c11, c12, ..., c35 that is c11=1, c12=9, and so on.
Let the capacities of the three factories be represented by a1=50, a2=100, a3=150.
Let the requirement of the retail agencies are b1=100, b2=60, b3=50, b4=50, and b5=40.
Thus, the problem can be formulated as
Minimize Z= c11x11+c12x12+……………+c35x35
Subject to: x11 + x12 + x13 + x14 + x15 = a1
x21 + x22 + x23 + x24 + x25 = a2
x31 + x32 + x33 + x34 + x35 = a3
x11 + x21 + x31 = b1
x12 + x22 + x32 = b2
x13 + x23 + x33 = b3
x14 + x24 + x34 = b4
x15 + x25 + x35 = b5
x11, x12, ……, x35 ? 0.
Thus, the problem has 8 constraints and 15 variables. So, it is not possible to solve such a problem using simplex method. This is the reason for the need of special computational procedure to solve transportation problem. There are varieties of procedures used to solve these problems.
Transportation Algorithm
The steps of the transportation algorithm are exact parallels of the simplex algorithm, they are:
Step 1: Determine a starting basic feasible solution, using any one of the following three methods:
1. North West Corner Method (NWCM).
2. Least Cost Method (Matrix Minimum Method) (LCM)(MMM).
3. Vogel Approximation Method ( VAM ).
Step 2: Determine the optimal solution by using one of the following methods:
MODI (Modified Distribution Method) or Stepping Stone Method.

Basic Feasible Solution of a T.P.
The difference among the three methods (NWCM, LCM and VAM) is the quality of the initial basic feasible solution they produce, in the sense that a better initial solution yields a smaller objective value. Generally, the VAM produces the best initial basic feasible solution, and the NWCM produces the worst, but the NWCM involves least computations.

Transportation Problem

The Transportation Problem (T.P.) is a special class of linear programming problems, where the objective is to minimize the cost of distributing a product from a number of sources (e.g. factories) to a number of destinations (e.g. warehouses ) while satisfying both the supply limits and the demand requirement.
Because of the special structure of the T.P., the simplex method is unsuitable for it. The model assumes that the distributing cost on a given route is directly proportional to the number of units distributed on that route. Generally, the transportation model can be extended to areas other than the direct transportation of a commodity, including among others, stored control, employment scheduling, etc.
Example:
Suppose a manufacturing company owns three factories (sources) and distribute its products to five different retail agencies (destinations). The following table shows the capacities of the three factories, the quantity of products required by the various retail agencies and the cost of shipping one unit of the product from each of the three factories to each of the five retail agencies.
Retail Agency
Factories 1 2 3 4 5 Capacity
1
2
3 1
24
14 9
12
33 13
16
1 36
20
23 51
1
26 50
100
150
Requirement 100 60 50 50 40 300
Usually the above table is referred as Transportation table, which provides the basic information regarding the transportation problem. The quantities inside the table are known as transportation cost per unit of product. The capacity of the factories 1, 2 and 3 is 50, 100 and 150 respectively. The requirement of the retail agency 1, 2, 3, 4 and 5 is 100, 60, 50, 50, and 40 respectively.
In this case, the transportation cost of one unit:
from factory 1 to retail agency 1 is 1,
from factory 1 to retail agency 2 is 9,
from factory 1 to retail agency 3 is 13,
from factory 2 to retail agency 1 is 24,
and so on… .
A transportation problem can be formulated as linear programming problem using variables with two subscripts. Let:
x11=Amount to be transported from factory 1 to retail agency 1.
x12= Amount to be transported from factory 1 to retail agency 2.
……..
……..
……..
x35= Amount to be transported from factory 3 to retail agency 5.
Let the transportation cost per unit be represented by c11, c12, ..., c35 that is c11=1, c12=9, and so on.
Let the capacities of the three factories be represented by a1=50, a2=100, a3=150.
Let the requirement of the retail agencies are b1=100, b2=60, b3=50, b4=50, and b5=40.
Thus, the problem can be formulated as
Minimize Z= c11x11+c12x12+……………+c35x35
Subject to: x11 + x12 + x13 + x14 + x15 = a1
x21 + x22 + x23 + x24 + x25 = a2
x31 + x32 + x33 + x34 + x35 = a3
x11 + x21 + x31 = b1
x12 + x22 + x32 = b2
x13 + x23 + x33 = b3
x14 + x24 + x34 = b4
x15 + x25 + x35 = b5
x11, x12, ……, x35 ? 0.
Thus, the problem has 8 constraints and 15 variables. So, it is not possible to solve such a problem using simplex method. This is the reason for the need of special computational procedure to solve transportation problem. There are varieties of procedures used to solve these problems.
Transportation Algorithm
The steps of the transportation algorithm are exact parallels of the simplex algorithm, they are:
Step 1: Determine a starting basic feasible solution, using any one of the following three methods:
1. North West Corner Method (NWCM).
2. Least Cost Method (Matrix Minimum Method) (LCM)(MMM).
3. Vogel Approximation Method ( VAM ).
Step 2: Determine the optimal solution by using one of the following methods:
MODI (Modified Distribution Method) or Stepping Stone Method.

Basic Feasible Solution of a T.P.
The difference among the three methods (NWCM, LCM and VAM) is the quality of the initial basic feasible solution they produce, in the sense that a better initial solution yields a smaller objective value. Generally, the VAM produces the best initial basic feasible solution, and the NWCM produces the worst, but the NWCM involves least computations.


المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
الرجوع الى لوحة التحكم