البحث:

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

# NWCM

الكلية كلية التربية للعلوم الصرفة     القسم  قسم الرياضيات     المرحلة 4
أستاذ المادة مشتاق عبد الغني شخير الجنابي       20/03/2021 19:12:49
1)) NWCM:
This method starts at the north west (upper left) corner cell of the tableau (variable x11).
Step 1: Allocate as much as possible to the selected cell, and adjust the associated amounts of capacity (supply) and requirement (demand) by subtracting the allocated amount.
Step 2: Cross out the row (column) with zero supply or demand to indicate that no further assignments can be made in that row (column). If both the row and column becomes zero in the same time, cross out one of them only, and leave a zero supply or demand in the uncrossed out row (column).
Step 3: If exactly one row (column) is left uncrossed out, then stop. Otherwise, move to the cell to the right if a column has just been crossed or the one below if a row has been crossed out. Go to step 1.
Refer to above example:

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

Retail Agency

Factories 1 2 3 4 5 Capacity

1 1
50 9 13 36 51 50

2 24
50 12
50 16
20
1

100 50

3 14
33
10 1
50 23
50 26
40
150 140 90 40

Requirement 100 50
60 10
50
50
40

The arrows show the order in which the allocated amounts are generated. The starting basic solution is given as
x11 = 50, x21 = 50, x22 = 50 , x32 = 10, x33 = 50, x34 = 50, x35 = 40.
The corresponding transportation cost is:
Z= 50 * 1 + 50 * 24 + 50 * 12 + 10 * 33 + 50 * 1 + 50 * 23 + 40 * 26 = 4420
It is clear that as soon as a value of xij is determined, a row (column) is eliminated from further consideration. The last value of xij eliminates both a row and column. Hence a feasible solution computed by North West Corner Method can have at most m + n – 1 positive xij if the transportation problem has m sources and n destinations.

2)) LCM
Least cost method is also known as matrix minimum method in the sense we look for the row and the column corresponding to which Cij is minimum. This method finds a better initial basic feasible solution by concentrating on the cheapest routes. Instead of starting the allocation with the northwest cell as in the North West Corner Method, we start by allocating as much as possible to the cell with the smallest unit cost. If there are two or more minimum costs then we should select the row and the column corresponding to the lower numbered row. If they appear in the same row we should select the lower numbered column. We then cross out the satisfied row or column, and adjust the amounts of capacity and requirement accordingly. If both a row and a column is satisfied simultaneously, only one is crossed out. Next, we look for the uncrossed-out cell with the smallest unit cost and repeat the process until we are left at the end with exactly one uncrossed-out row or column.
Retail Agency

Factories 1 2 3 4 5 Capacity

1 1
50 9
X 13
X 36
X 51
X 50

2 24
X 12
60 16
X 20
X 1
40
100

3 14
50 33
X 1
50 23
50 26
X
150
Requirement 100 60 50 50 40

We observe that C11=1 is the minimum unit cost in the table. Hence X11=50 and the first row is crossed out since the row has no more capacity. Then the minimum unit cost in the uncrossed-out row and column is C25=1, hence X25=40 and the fifth column is crossed out. Next C33=1is the minimum unit
cost, hence X33=50 and the third column is crossed out. Next C22=12 is the minimum unit cost, hence X22=60 and the second column is crossed out. Next we look for the uncrossed-out row and column now C31=14 is the minimum unit cost, hence X31=50 and crossed out the first column since it was satisfied. Finally C34=23 is the minimum unit cost, hence X34=50 and the fourth column is crossed out.
So that the basic feasible solution developed by the Least Cost Method has transportation cost is
Z= 1 * 50 + 12 * 60 + 1 * 40 + 14 * 50 + 1 * 50 + 23 * 50 = 2710
3)) Vogel Approximation Method ( VAM )
Step 1: For each row and column find the difference between the two lowest unit shipping costs.
Step 2: Assign as many units as possible to the lowest-cost square in the row and column selected.
Step 3: Eliminate the column or row that has been satisfied.
Example: Consider the following transportation problem
Origin Destination
ai
1 2 3 4
1 20 22 17 4
120
2 24 37 9
7 70
3 32 37 20 15
50
bj 60 40 30 110 240
Solution:
1. Compute the penalty for various rows and columns.
2. Look for the highest penalty in the row or column, the highest penalty occurs in the second column and the minimum unit cost i.e. cij in this column is c12=22. Hence assign 40 to this cell i.e. x12= 40 and cross out the second column (since second column was satisfied ).
Origin Destination
ai column
Penalty
1
2
3
4

1
20
X 22
40 17
X 4
80 120 13

2
24
37
X 9
30 7
70 2

3
32
37
X 20
X 15
50 5

bj
Row Penalty 60
4 40
15 30
8 110
3 240

Origin Destination
ai column
Penalty
1
2
3
4

1
20
X 22
40 17
X 4
80 120 13

2
24
10 37
X 9
30 7
30 70 2 17

3
32
50 37
X 20
X 15
X 50 5 17

bj
Row Penalty 60
4
8 40
15
30
8
110
3
8 240

The transportation cost corresponding to this choice of basic variables is:
Z = 22 * 40 + 4 * 80 + 30 * 9 + 30 * 7 + 10 * 24 + 50 * 32 = 3520.

1)) NWCM:
This method starts at the north west (upper left) corner cell of the tableau (variable x11).
Step 1: Allocate as much as possible to the selected cell, and adjust the associated amounts of capacity (supply) and requirement (demand) by subtracting the allocated amount.
Step 2: Cross out the row (column) with zero supply or demand to indicate that no further assignments can be made in that row (column). If both the row and column becomes zero in the same time, cross out one of them only, and leave a zero supply or demand in the uncrossed out row (column).
Step 3: If exactly one row (column) is left uncrossed out, then stop. Otherwise, move to the cell to the right if a column has just been crossed or the one below if a row has been crossed out. Go to step 1.
Refer to above example:

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

Retail Agency

Factories 1 2 3 4 5 Capacity

1 1
50 9 13 36 51 50

2 24
50 12
50 16
20
1

100 50

3 14
33
10 1
50 23
50 26
40
150 140 90 40

Requirement 100 50
60 10
50
50
40

The arrows show the order in which the allocated amounts are generated. The starting basic solution is given as
x11 = 50, x21 = 50, x22 = 50 , x32 = 10, x33 = 50, x34 = 50, x35 = 40.
The corresponding transportation cost is:
Z= 50 * 1 + 50 * 24 + 50 * 12 + 10 * 33 + 50 * 1 + 50 * 23 + 40 * 26 = 4420
It is clear that as soon as a value of xij is determined, a row (column) is eliminated from further consideration. The last value of xij eliminates both a row and column. Hence a feasible solution computed by North West Corner Method can have at most m + n – 1 positive xij if the transportation problem has m sources and n destinations.

2)) LCM
Least cost method is also known as matrix minimum method in the sense we look for the row and the column corresponding to which Cij is minimum. This method finds a better initial basic feasible solution by concentrating on the cheapest routes. Instead of starting the allocation with the northwest cell as in the North West Corner Method, we start by allocating as much as possible to the cell with the smallest unit cost. If there are two or more minimum costs then we should select the row and the column corresponding to the lower numbered row. If they appear in the same row we should select the lower numbered column. We then cross out the satisfied row or column, and adjust the amounts of capacity and requirement accordingly. If both a row and a column is satisfied simultaneously, only one is crossed out. Next, we look for the uncrossed-out cell with the smallest unit cost and repeat the process until we are left at the end with exactly one uncrossed-out row or column.
Retail Agency

Factories 1 2 3 4 5 Capacity

1 1
50 9
X 13
X 36
X 51
X 50

2 24
X 12
60 16
X 20
X 1
40
100

3 14
50 33
X 1
50 23
50 26
X
150
Requirement 100 60 50 50 40

We observe that C11=1 is the minimum unit cost in the table. Hence X11=50 and the first row is crossed out since the row has no more capacity. Then the minimum unit cost in the uncrossed-out row and column is C25=1, hence X25=40 and the fifth column is crossed out. Next C33=1is the minimum unit
cost, hence X33=50 and the third column is crossed out. Next C22=12 is the minimum unit cost, hence X22=60 and the second column is crossed out. Next we look for the uncrossed-out row and column now C31=14 is the minimum unit cost, hence X31=50 and crossed out the first column since it was satisfied. Finally C34=23 is the minimum unit cost, hence X34=50 and the fourth column is crossed out.
So that the basic feasible solution developed by the Least Cost Method has transportation cost is
Z= 1 * 50 + 12 * 60 + 1 * 40 + 14 * 50 + 1 * 50 + 23 * 50 = 2710
3)) Vogel Approximation Method ( VAM )
Step 1: For each row and column find the difference between the two lowest unit shipping costs.
Step 2: Assign as many units as possible to the lowest-cost square in the row and column selected.
Step 3: Eliminate the column or row that has been satisfied.
Example: Consider the following transportation problem
Origin Destination
ai
1 2 3 4
1 20 22 17 4
120
2 24 37 9
7 70
3 32 37 20 15
50
bj 60 40 30 110 240
Solution:
1. Compute the penalty for various rows and columns.
2. Look for the highest penalty in the row or column, the highest penalty occurs in the second column and the minimum unit cost i.e. cij in this column is c12=22. Hence assign 40 to this cell i.e. x12= 40 and cross out the second column (since second column was satisfied ).
Origin Destination
ai column
Penalty
1
2
3
4

1
20
X 22
40 17
X 4
80 120 13

2
24
37
X 9
30 7
70 2

3
32
37
X 20
X 15
50 5

bj
Row Penalty 60
4 40
15 30
8 110
3 240

Origin Destination
ai column
Penalty
1
2
3
4

1
20
X 22
40 17
X 4
80 120 13

2
24
10 37
X 9
30 7
30 70 2 17

3
32
50 37
X 20
X 15
X 50 5 17

bj
Row Penalty 60
4
8 40
15
30
8
110
3
8 240

The transportation cost corresponding to this choice of basic variables is:
Z = 22 * 40 + 4 * 80 + 30 * 9 + 30 * 7 + 10 * 24 + 50 * 32 = 3520.

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