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

Stepping Stone Method of Optimality Test

Share |
الكلية كلية التربية للعلوم الصرفة     القسم  قسم الرياضيات     المرحلة 4
أستاذ المادة مشتاق عبد الغني شخير الجنابي       20/03/2021 19:14:28
Stepping Stone Method of Optimality Test

Once, we get the basic feasible solution for a transportation problem, the next duty is to test whether the solution we got is an optimal solution or not?
1. Steps to test unused squares;
2. Select an unused square,
3. Allocate + ? unit to unused square and locate - ? and + ? alternatively to corners of the selected closed path.
4. Calculate the improvement index.
5. If improvement index is negative allocate as much as you can to that unused square.
Repeat the allocation till the improvement index is ? 0 for all unused squares.

Retail Agency

Factories 1 2 3 4 5

1 50 1
-1
9
+1
13 36 51

2 50 24
+1
50 12
-1 16
20
1


3 14
10 33
50 1
50 23
40 26

Improvement index (1 – 2) = 1*9-1*1+1*24-1*12= + 20 , this means if we allocate (1 – 2) +1 unit , then the transport cost will increase by +20.
Retail Agency

Factories 1 2 3 4 5

1 50 1
-1
9
13
+1
36 51

2 50 24
+1
50 12
-1
16
20
1


3 14
10 33
+1
50 1
-1 50 23
40 26


Improvement index (1 – 3) = 1*13-1*1+1*24-1*12+1*33-1*1= + 56 , this means if we allocate (1 – 3) +1 unit , then the transport cost will increase by +56.
Retail Agency

Factories 1 2 3 4 5

1 50 1
-1
9
13
36
+1
51


2 50 24
+1
50 12
-1
16
20
1


3 14
10 33
+1
50 1
50 23
-1 40 26


Improvement index (1– 4) = 1*13-1*1+1*24-1*12+1*33-1*23= + 34 , this means if we allocate (1 – 4) +1 unit , then the transport cost will increase by +24.
And so on …
Improvement index (1– 5) = 1*51-1*1+1*24-1*12+1*33-1*26= +73, this means if we allocate (1 – 5) +1 unit , then the transport cost will increase by +73.
Improvement index (2– 3) = 1*16-1*12+1*33-1*1= +36, this means if we allocate (2 – 3) +1 unit , then the transport cost will increase by +36.

Improvement index (2– 4) = 1*20-1*12+1*33-1*23=+18, this means if we allocate (2 – 4) +1 unit , then the transport cost will increase by +18.

Improvement index (2– 5) = 1*1-1*12+1*33-1*26= - 4, this means if we allocate (2 – 5) +1 unit , then the transport cost will decrease by - 4.

Since there is a decrease in the cost, we will allocate as much as we can to ( 2 – 5 ). To further improve the current solution, select the "smallest" number found in the path ( 2-5 , 2-2 , 3-2 , 3-5 ) containing minus ( - ) signs. This number is added to all cells on the closed path with plus ( + ) signs, and subtracted from all cells on the path with minus ( - ) signs.
Retail Agency

Factories 1 2 3 4 5 Capacity

1 1
50 9 13 36 51 50

2 24
50 12
10 16
20
1
40
100

3 14
33
50 1
50 23
50 26

150
Requirement 100 60 50 50 40

Z= 50 * 1 + 50 * 24 + 10 * 12 + 50 * 33 + 50 * 1 + 50 * 23 + 40 * 1 = 4260.

1 2 3 4 5
1
50 9 13 36 51
50 24
-1
10 12
+1
16
20
1
40
14
+1
50 33
-1 1
50 23
50 26


Improvement index (3 – 1) = 1*14-1*33+1*12-1*24= - 31, this means if we allocate (3 – 1) +1 unit , then the transport cost will decrease by - 31.

Since there is a decrease in the cost, so,
Retail Agency

Factories 1 2 3 4 5 Capacity

1 1
50 9 13 36 51 50

2 24
12
60 16
20
1
40
100

3 14
50 33
1
50 23
50 26

150
Requirement 100 60 50 50 40

Z= 50 * 1 + 50 * 14 + 60 * 12 + 50 * 1 + 50 * 23 + 40 * 1 = 2710.
We will check the Improvement index in each cell again:


(1 – 2 ) Not possible
(1 – 3 ) 1*13-1*1+1*14-1*1 = +25
(1 – 4 ) 1*36- 1*36-1*1+1*14-1*23 = +26
(1 – 5 ) Not possible
(2 – 1 ) Not possible
(2 – 3 ) Not possible
(2 – 4 ) Not possible
(3 – 2 ) Not possible
(3 – 5 ) Not possible

In the table above, no more negative improvement index, so the solution
Z = 2710 is optimal.
Example: According to the following table, Find the feasible solution by three methods (NWCM, LCM and VAM), then find the optimal solution.

Solution:
1) Initial Solution with NWCM

Albuquerque Boston Cleveland Capacity
Des Moines 5 4 3 100
Evansville 8 4 3 300
Fort Lauderdale 9 7 5 300
Demand 300 200 200 700


Z=100?5+200?8+100?4+100?7+200?5=500+1600+400+700+1000=4200 $
2) Initial Solution with LCM

Z=300?9+200?4+100?3+100?3=2700+800+300+300=4100 $
3) Initial Solution with VAM





Z= 100?5+200?4+100?3+200?9+100?5=500+800+300+1800+500=3900 $
Stepping Stone Method of Optimality Test





Since there is a decrease in the cost, we will allocate as much as we can to Fort Lauderdale – Albuquerque. The amount is the minimum of the numbers that we are assigning -? in the cycle.

Z=100?5 + 100?8+200?4+100?9+200?5=500+800+800+900+1000=4000 $

An improvement can be done by allocating to EC, since the minimum number in the square is 100; we allocate 100 to EC square.

Z=100?5 + 200?9+200?4+100?3+100?5=500+1800+800+300+500=3900 $
We will check the Improvement index in each cell again.

In this table, no more negative improvement index, so the solution is optimal.
Exercise:
1) A company has three factories X, Y, and Z and three warehouses A, B, and C. It is required to schedule factory production and shipments from factories to warehouses in such a manner so as to minimize total cost of shipment and production. Unit variable manufacturing cost (UVMC) and factory capacities and warehouse requirements are given below:
From / To A B C Capacity
X 10 4 11 70

Y 12 5 8 50

Z 9 7 6 30

Demand 40 50 60 150

a) Load the table with North-west method.
b) Load the table with least cost method.
c) Load the table with Vogel’s approximation method, (VAM).
d) Solve the question by stepping stone algorithm.

2) The demand and capacity are given
From / To Sarajevo Travnik Bihac Capacity
Mostar 5 7 15 120

Zenica 4 2 8 200

Tuzla 6 3 10 150

Demand 210 160 100 470

a) Load the table with North-west method.
b) Load the table with least cost method.
c) Load the table with Vogel’s approximation method, (VAM).
d) Solve the question by stepping stone algorithm.


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