Stepping Stone Method (SSM)


SSM:   SOLD       



Transportation Method is a method used to organize the distribution of sources that provide the same product, to places that need it optimally. The allocation of this product must be arranged in such a way, because there are differences in allocation costs from one source to several different destinations, and several sources to several different destinations.


Stepping Stone Method (One part of the Transportation Method)

1. Stepping Stone Method

To solve a transportation problem using the stepping stone method, 2 steps are required:

  1. Determine the first feasible answer by using the northwest corner method.
  2. Testing whether the initial solution is optimal or not.
  3. Repeat step 2 until the non-basic variables in Zij are ≤ 0.

1.1. Determining the First Appropriate Answer

Determine a feasible answer that meets all the constraints or required transportation systems (using the north west corner method) using the following steps:

1). Replenishment starts from the northwest corner of the transportation problem table, which is cell (1,1). Compare the supply in A1 with the demand in T1, which are a1 and b1 respectively. Make X11 = min (a1, b1).

  • If a1 > b1, then X11 = b1. Continue to cell (1,2) which is horizontal movement with X12 = min (a1-b1, b2).
  • If a1 < b1, then X11 = a1. Continue to cell (2,1) which is vertical movement with X21 = min (b1-a1, a2).
  • If a1 = b1, then make X11 = b1 and continue the movement to X22 (oblique movement).

2). Continue this step by step away from the northwest corner until finally the price has been reached at the southeast corner of the chart.

After m+n-1 steps, m+n-1 constraints have been satisfied and the rest will be satisfied by themselves. Therefore, this method will produce no more than m+n-1 variables xij that are > 0, since each step satisfies either Ai (origin) or Tj (destination). These values ​​xij > 0 are called basis variables and their number is equal to m+n-1.

1.2. Testing Completion Optimality

For example, we have a basic feasible solution to a transportation problem with m origins and n destinations. This means that there are m+n-1 basic variables xij that are > 0. We do not know whether this solution is optimal or not.

To determine whether a feasible answer is optimal or not, we use the stepping stone method, which is through a transportation data table containing the basic variables xij > 0 and cij. We calculate zij for each cell (i,j) that does not contain the basic variables xij > 0.

For cell (i,j) we need a loop containing cell (i,j) itself and the base cells. Suppose the order of cells in the loop is:

{(i,r), (u,r), ..., (s,w), (s,j), (i,j)}

The corresponding zij price is

zij = cir - cur ... + charge - cij

To calculate zij for each cell that does not contain xij > 0, we need the following steps:

  1. Define a base cell in the same row such that the other base cell is in the same column.
  2. Make a horizontal movement then an upright movement.
  3. Repeat this movement from one base cell to another base cell until you arrive at a place or cell that is in the same column as the non-base cell being assessed, thus forming a loop.
  4. Add up the values ​​of all the basic cells in the lop by alternating positive and negative signs and the result is equal to zij.

We can do this process for all non-base cells. If:

  1. zij ≤ 0 for each cell (i,j) then the feasible basis answer is optimal.
  2. zij > 0 for a (i,j) then the feasible basis answer is not optimal.

After zij is calculated for all non-basic cells, we are now ready to determine the new basic answer, namely the following steps:

  1. Calculate or set zst = max zij (i,j) meaning the variable xst is in the basis and xst > 0.
  2. Define a loop that contains xst.
  3. Consider cαβ with a coefficient of 1.
  4. Set xpq = Min {xαβ with coefficient cαβ = 1}, meaning that the variable xpq comes out as a basic variable.

Determine the price of the basic variable for the new basic answer by:

  • xst = xpq.
  • if the coefficient cαβ = 1, then xαβ = xαβ - xpq.
  • if the coefficient cαβ = -1, then xαβ = xαβ + xpq.

Note that xαβ is contained in the loop containing (s,t).

Example:

OKE Company has 3 factories P1, P2, P3 and 3 warehouses G1, G2, G3. In one month each factory can produce 50, 40, 30 units of goods and each warehouse can accommodate 60, 20, 40 units of goods. The shipping cost from each factory to each warehouse (in hundreds of thousands of Rp):

P1 ke G1, G2, G3 : 3, 10, 8; P2 ke G1, G2, G3 : 7, 5, 1; P3 ke G1, G2, G3 : 9, 2, 7.

Determine the optimal allocation of units of goods from factories P1, P2, P3 to warehouses G1, G2, G3 to obtain minimum costs in one month.

Solution:

1. Determine the first correct answer


Determine the first proper answer

Using the North West Corner (NWC) method. Compare the inventory at a1 with the needs at b1.

X11 = min(a1;b1)
X11 = min(50;60)
X11 = 50, langkah dilanjutkan ke X21
X21 = min(a2;b1-50)
X21 = min(40;60-50)
X21 = min(40;10)
X21 = 10, langkah dilanjutkan ke X22
X22 = min(a2-10;b2)
X22 = min(40-10;20)
X22 = min(30;20)
X22 = 20, langkah dilanjutkan ke X23
X23 = min(a2-30;b3)
X23 = min(40-30;40)
X23 = min(10;40)
X23 = 10, langkah dilanjutkan ke X33
X33 = min(a3;b3-10)
X33 = min(30;40-10)
X33 = min(30;30)
X33 = 30

2. Testing the Optimization of the First Eligible Answer

a. Calculating Zij of Non-Basic Variables

Sel (1,2) Loop (1,1) (2,1) (2,2) (1,2)
Z12 = C11-C21+C22-C12
Z12 = 3-7+5-10
Z12 = -9

Sel (1,3) Loop (1,1) (2,1) (2,3) (1,3)
Z13 = C11-C21+C23-C13
Z13 = 3-7+1-8
Z13 = -11

Sel (3,1) Loop (3,3) (2,3) (2,1) (3,1)
Z31 = C33-C23+C21-C31
Z31 = 7-1+7-9
Z31 = 4

Sel (3,2) Loop (3,3) (2,3) (2,2) (3,2)
Z32 = C33-C23+C22-C32
Z32 = 7-1+5-2
Z32 = 9

b. Determining the variables included in the basis

Maks Zst = Maks Zij (Zij variabel non basis yang > 0)
Maks Zst = Maks (4;9)
Maks Zst = 9 = Z32, maka X32 masuk dalam Basis

c. Determining variables that are outside the base

Loop Variables included in Basis (3,2) = (3,3) (2,3) (2,2) (3,2)

Koefisien cαβ (+) = (3,3);(2,2)

Min Xpq = Min (X33;X22)
Min Xpq = Min (30;20)
Min Xpq = 20 = X22, maka X22 keluar dari basis

d. New Base Price

  1. Xst = Xpq = X32 = X22 = 20
  2. X33 = X33 - X22 = 30-20 =10
  3. X23 = X23 + X22 = 10 + 20 = 30

Arrange the new base prices into table 1

3. Repeat Step 2 Until Non-Basic Variable Zij ≤ 0

Testing the Optimality of the First Eligible Answer

a. Calculating Zij of Non-Basic Variables

Sel (1,2) Loop (1,1) (2,1) (2,3) (3,3) (3,2) (1,2)
Z12 = C11-C21+C23-C33+C32-C12
Z12 = 3-7+1-7+2-10
Z12 = -18

Sel (1,3) Loop (1,1) (2,1) (2,3) (1,3)
Z13 = C11-C21+C23-C13
Z13 = 3-7+1-8
Z13 = -11

Sel (2,2) Loop (2,3) (3,3) (3,2) (2,2)
Z22 = C23-C33+C32-C22
Z22 = 1-7+2-5
Z22 = -9

Sel (3,1) Loop (3,3) (2,3) (2,1) (3,1)
Z31 = C33-C23+C21-C31
Z31 = 7-1+7-9
Z31 = 4

b. Determining the variables included in the basis

Maks Zst = Maks Zij (Zij variabel non basis yang > 0)
Maks Zst = Maks (4)
Maks Zst = 4 = Z31, maka X31 masuk dalam Basis

c. Determining variables that are outside the base

Loop Variables included in Basis (3,1) = (3,3) (2,3) (2,1) (3,1)

Koefisien cαβ (+) = (3,3);(2,1)

Min Xpq = Min (X33;X21)
Min Xpq = Min (10;10)
Min Xpq = 10 = X33, maka X33 keluar dari basis

d. New Base Price

  1. Xst = Xpq = X31 = X33 = 10
  2. X23 = X23 + X33 = 30+10 =40
  3. X21 = X21 - X33 = 10 - 10 = 0

Arrange the new base prices into table 2


Retesting the Optimization of the First Eligible Answer

a. Calculating Zij of Non-Basic Variables

Sel (1,2) Loop (1,1) (3,1) (3,2) (1,2)
Z12 = C11-C31+C32-C12
Z12 = 3-9+2-10
Z12 = -14

Sel (1,3) Loop (1,1) (2,1) (2,3) (1,3)
Z13 = C11-C21+C23-C13
Z13 = 3-7+1-8
Z13 = -11

Sel (2,2) Loop (2,1) (3,1) (3,2) (2,2)
Z22 = C23-C33+C32-C22
Z22 = 7-9+2-5
Z22 = -5

Sel (3,3) Loop (3,1) (2,1) (2,3) (3,3)
Z31 = C31-C21+C23-C33
Z31 = 9-7+1-7
Z31 = -4

Since the non-basic variable Zij is already ≤ 0, it is optimal.

Biaya = 50*3 + 0*7 + 40*1 + 10*9 + 20*2
Biaya = 150 + 0 + 40 + 90 + 40
Biaya = 320
Biaya = 320*Rp.100.000,-
Biaya = Rp.32.000.000,-

Conclusion

Therefore, the allocation of units of goods from factories P1, P2, P3 to warehouses G1, G2, G3 in one month is optimal with a minimum cost of  Rp. 32,000,000.

Reference:

Operations Research Module, CHAPTER 3 Transportation Methods, "Stepping Stone Method", compiled by Minawarti, ST.


Post a Comment

Previous Next

نموذج الاتصال