เรื่องที่ 8.5.1 สเตปปิงสโตน

               เป็นวิธีที่ใช้กับตารางขนส่งที่มีจำนวนแถวบวกจำนวนสดมภ์ลบหนึ่ง เท่ากับจำนวนช่องคำตอบที่ได้ใส่ตัวเลขลงไป
               การปรับปรุงคำตอบเริ่มต้นวิธีนี้คือหาตัวแปรเข้าและตัวแปรออกโดยการสร้าง รูปบ่วงปิด ( Closed Loop ) 
โดยที่จุดเริ่มต้นและจุดสุดท้ายจะต้องเป็นตัวแปรไม่เป็นมูลฐานตัวเดียวกัน ในการสร้างบ่วงปิดจะลากเส้นตามแนวตั้งและ
แนวนอน จุดมุมของบ่วงปิดจะต้องเป็นตัวแปรมูลฐานเสมอ ( จุดมุมจะเป็นมุมฉาก )  ตัวอย่างการสร้างบ่วงปิดจากตารางที่ 
8-1 ซึ่งมีตัวแปรมูลฐาน m+n-1 ตัวพอดี ถ้าเริ่มจาก X31  ซึ่งไม่เป็นตัวแปรมูลฐานเมื่อลากเส้นตามแนวตั้งและแนวนอน
นอนโดยจุดมุมเป็นตัวแปรมูลฐาน จะลากดังนี้  X31 X11 X12 X22 X24 X34 X31 ถ้าเริ่ม
จาก  X32     จะสร้างบ่วงดังนี้ X32 X22 X24 X34 X32        ดังตารางที่ 8-2 ตัวแปรมูลฐานใด ที่ไม่ได้เป็น
จุดมุมจะถือว่าเป็นทางผ่านเท่านั้น
                                                            
                                                                                 ตารางที่ 8.1                          
                          
                                                                                ตารางที่ 8-2
                  เมื่อสร้างบ่วงปิดแล้วจะใช้บ่วงนี้ตรวจสอบว่าจะสามารถปรับปรุงคำตอบได้หรือไม่
                 การสร้างบ่วงปิดจะลากในทิศทวนเข็มหรือตามนาฬิกาก็ได้  จากตารางที่ 8-1 เมื่อสร้างบ่วงปิดโดยเริ่มจาก
ตัวแปรแปรไม่เป็นมูลฐานที่เหลือจะได้ดังนี้
                                                 
                  จากตารางที่ 8-2 ถ้าเพิ่มค่า X32  เท่ากับ  หน่วย จะต้องลด X22 ลง  หน่วย แล้วเพิ่ม X24 หน่วย และลดค่า 
X34 หน่วย ดังรูปที่ 8-1 ทั้งนี้เพื่อรักษาข้อจำกัดด้าน Si และ dj
                                                                           
                                                                                          รูปที่ 8-1
                 การเพิ่มค่าตัวแปรไม่เป็นมูลฐาน แสดงว่าหาตัวแปรมูลฐานเข้า จึงต้องหาตัวแปรมูลฐานออกเพื่อให้จำนวนตัวแปร
มูลฐานมี  m+n-1 ตัวคงเดิม  และการที่จะเลือกตัวแปรใดเป็นตัวแปรเข้า จะต้องทำให้ผลลัพธ์ดีขึ้น ซึ่งตรวจสอบดังนี้
               ให้เครื่องหมาย Cij ของตัวแปรไม่เป็นมูลฐาน ที่เป็นจุดเริ่มต้นในบ่วงปิดเป็น + จุดมุมถัดไปของบ่วงปิดให้เครื่องหมาย  
Cij เป็น  –  และมุมถัดไปเป็น + , - สลับกันไปเรื่อยๆ จนครบบ่วงปิด 
               ให้       เป็นค่าใช้จ่ายรวมที่เปลี่ยนไปเมื่อเพิ่มค่า Xij ( ตัวแปรไม่เป็นมูลฐาน ) 1 หน่วย 
               ค่า      =   ผลรวม Cij  ที่จุดมุมทุกๆจุดในบ่วงปิด โดยคิดเครื่องหมาย Cij ตามที่กำหนดให้
               ถ้าค่า  เป็น + แสดงว่าเพิ่ม Xij 1 หน่วย ทำให้ค่าใช้จ่ายเพิ่มขึ้น 
              ถ้าค่า  เป็น – แสดงว่าเพิ่ม Xij 1 หน่วย ทำให้ค่าใช้จ่ายลดลง 
ตัวอย่างที่ 12 จากตารางที่ 8-1 ต้องการตรวจสอบว่าเมื่อเพิ่ม X32 1 หน่วย จะทำให้ค่าใช้จ่ายเพิ่มขึ้นหรือลดลง
ทำได้โดยหา  จากบ่วงปิด X32  X22  X24  X34  X32 ดังนี้
              ใช้ทำเครื่องหมาย C32 เป็น +, C22 เป็น  - , C24  + , C34   -
              หา C32 โดยรวม Cij ทั้งหมดในบ่วงปิดนี้ จะได้   = +14-7+20-18  = 9
              ค่า C32 เป็นบวก แสดงว่าการเพิ่มค่า X32 1 หน่วย จะทำให้ค่าใช้จ่ายเพิ่มขึ้น 9 บาท
ในกรณีนี้ จึงไม่ควรเพิ่มค่า X32 เพราะว่า เป้าหมายขณะนี้คือค่าใช้จ่ายต่ำสุด
              ต่อไปพิจารณาว่าควรเพิ่มค่า X31 หรือไม่ โดยการหา C31 จากบ่วงปิด
X31 X11 X12 X22 X24 X34 X31
ให้เครื่องหมาย    C31  เป็น + , C11 - , C12 + , C22  -, C24  + , C34  - จะได้
                           =  + 0 – 10 + 0 – 7 + 20 – 18   =   –15
ค่า C31 =  -15 แสดงว่าถ้าเพิ่มค่า X31  1 หน่วย จะทำให้ค่าใช้จ่ายลดลง 15 บาท ใน กรณีนี้ควรเพิ่มค่า X31 ให้มากที่สุด   
เท่าที่จะมากได้โดยที่ยังสอดคล้องกับ Si และ dj จะได้ว่า X31 เพิ่มได้มากที่สุดเท่ากับ 5 ( เพิ่มภายในบ่วงปิดนั้นๆ ) ได้ตัวแปร
มูลฐานใหม่ดังตารางที่ 8-3 
                                        
                                                                              ตารางที่ 8-3
                 ค่าใช้ใหม่ที่ได้นี้ จะลดจากเดิม =   5(15)  =  75 บาท
                 นั่นคือ ค่าใช้จ่ายใหม่  =  410 – 75 = 335 บาท
หมายเหตุ การเพิ่ม Xij ( ตัวแปรไม่เป็นมูลฐาน ) จะเพิ่มให้มากที่สุดเท่าที่จะมากได้เพื่อให้ถึงเป้าหมายเร็วที่สุด โดยที่ยัง
สอดคล้อง คล้อง Si กับ dj และ ค่า Xij ที่เพิ่มขึ้น จึงเลือกจากค่าต่ำสุดของตัวแปรมูลฐานที่กำหนดค่า Cij  เป็น – ภายในบ่วงปิด
                 เช่นจากตารางที่ 8-2 จะเพิ่มค่า X31 โดยที่ X31 พิจารณาได้จากบ่วงปิด
                 X31 X11 X12 X22 X24 X34 X31
                 ค่า Cij ที่ถูกกำหนดเครื่องหมายเป็นลบ คือ C11 ,C22  ,C34  ค่าตัวแปรมูลฐาน 
                 X11 = 5, X22 = 5 , X34   = 5             จะได้
                 X31       มากที่สุด = min { X11  , X22 , X34 } =  5
                ต่อไปพิจารณาตารางที่ 8-3 โดยนับจำนวนตัวแปรมูลฐานใหม่ให้ครบ m+n-1 ตัว เริ่มสร้างบ่วงปิดแล้วคำนวณ 
ของ Xij ซึ่งไม่เป็นตัวแปรมูลฐาน จะได้ค่า Cij อยู่มุมล่างในแต่ละช่องของตารางที่ 8-4
               จากตารางที่ 8-3 ได้ค่า  =  -2 และ   =  -5 แสดงว่าตัวแปรไม่เป็นมูลฐานที่เพิ่มค่า แล้วทำให้ค่าใช้จ่าย
ลดลงมี 2 ตัว คือ X14 และ X21
                                               
                                                                                ตาราง ที่  8-4
                 ถ้าเพิ่ม X14   1 หน่วย จะทำให้ค่าใช้จ่ายลดลง  2 บาท
                ถ้าเพิ่ม X21   1 หน่วย จะทำให้ค่าใช้จ่ายลดลง 5 บาท
                ดังนั้นจึงควรเพิ่มค่า X21 เพราะลดค่าใช้จ่ายได้เร็วกว่า ปรากฏว่า เพิ่ม X21 ได้ 0 หน่วย = min{ 0,0 } 
                ดังตารางที่ 8-35 ซึ่งการเพิ่ม X21  0 หน่วย ค่าใช้จ่ายยังคงเดิมเพียงแต่เปลี่ยนตัวแปรมูลฐานจาก X11 เป็น X21
                                               
                                                                                 ตารางที่ 8-5
                 จากตารางที่ 8-5 นับจำนวนตัวแปรมูลฐานให้ได้ m+n-1 ตัวแล้วสร้างบ่วงปิดใหม่และคำนวณ  ใหม่ ได้ค่า 
ได้ค่า C14 =  -2 ขณะที่ค่า ของตัวแปรไม่เป็นมูลฐานอื่นๆ เป็นบวก แสดงว่า ถ้าเพิ่ม X14 1 หน่วย จะทำให้ค่าใช้จ่าย
ลดลง 2 บาท จึงเพิ่มค่า X14 มากที่สุด ได้ = min{ X24 ,X12 } = min{ 10 ,15 }  =  10 หน่วย ตัวแปรมูลฐานใหม่
ดังตารางที่ 8-6 คำนวณ  ใหม่โดยสร้างบ่วงปิดใหม่ ปรากฏว่าได้  เป็น + ทั้งหมด แสดงว่าไม่สามารถเพิ่มค่า
ตัวแปรเพื่อลดค่าใช้จ่ายได้อีก นั่นคือได้ค่าใช้จ่ายต่ำสุดเท่ากับ
                                        335+10(-2) = 315  = 5*0+10*11+0*12+10*7+15*9+5*0
                                              
                                                                                  ตารางที่ 8-6

หมายเหตุ  	กรณีเป้าหมายหาค่าต่ำสุด ถ้า ของตัวแปรไม่เป็นมูลฐานเป็น + ทั้งหมดแสดงว่าได้คำตอบเหมาะสมกับ
ปัญหาแล้ว ถ้ามี  บางตัวของตัวแปรไม่เป็นมูลฐานมีค่า  = 0 ขณะที่  อื่นๆ ของตัวแปรไม่เป็นมูลฐานเป็น + ทั้งหมด
 แสดงว่าปัญหานั้นมีคำตอบต่ำสุดได้มากกว่า 1 คำตอบ เพราะเมื่อเพิ่มค่า Xij ที่มี  =  0 จะได้คำตอบต่ำสุดเท่าเดิม 
                     กรณีเป้าหมายหาค่าสูงสุด ถ้า  ของตัวแปรไม่เป็นมูลฐานเป็น – ทั้งหมด แสดงว่าได้คำตอบเหมาะสม
ของปัญหาแล้ว ถ้ามี  บางตัวของตัวแปรไม่เป็นมูลฐาน  = 0 ขณะที่  อื่นๆเป็น – แสดงว่าปัญหานั้นมีคำตอบ
เหมาะสมมากกว่า 1 คำตอบ

ตัวอย่างที่ 13 สมมติว่า เราจะเลือกคำตอบเบื้องต้นจากวิธี  north to south row rule ซึ่งมีลักษณะดังนี้
                      คำตอบที่เป็นไปได้เบื้องต้นจากวิธี north to south row rule

                                                                                       ตาราง ก 
                 จากคำตอบที่เป็นไปได้เบื้องต้นดังกล่าว เราจะใช้เป็นพื้นฐานในการหาความแตกต่างของต้นทุนค่าขนส่งเรียกชื่อว่า 
dij โดยคำนวณเฉพาะช่องที่ไม่มีคำตอบอยู่เท่านั้น
                การคำนวณหา dij นั้นให้ทำโดยเพิ่มค่าเข้าไปในช่องที่ต้องการคำนวณเท่ากับ  a แล้วไล่ไป จนครบวงจรดังนี้ คือ
                                             d12 =  0.8+0.4+0.5-0     =  +0.9
                                             d14 =   0.7+0.1+0.8-0.4  =  +1.0
                                             d21 =   0.9+0.1+0.4-0.5  =  +0.7
                                             d24 =   0.7+0.1+0.8-0.5  =  +0.9
                                             d31 =   0.3+0.8+0.4-0.1  =  -0.2
                                             d32 =   0.6+0.8+0.5-0     =  +0.3
               เมื่อคำนวณความแตกต่างของต้นทุนค่าขนส่ง dij จนครบทุกช่องที่ว่างอยู่แล้ว ให้ตรวจสอบว่ามีค่า dij ที่ติดลบอยู่
หรือไม่ ถ้ามีแสดงว่าคำตอบที่เป็นไปได้เบื้องต้นนั้นยังไม่ถึงจุดที่ค่าขนส่งรวมต่ำที่สุด และ Xij หรือปริมาณการขนส่งควรจะ
มีค่าในช่องที่ dij เป็นลบ และมีค่าสมบูรณ์มากที่สุด ในที่นี้ dij เป็นลบที่ d31
              เราจะเพิ่มค่า X31 เข้าไปในตารางคำตอบที่เป็นไปได้เบื้องต้น ซึ่งค่าที่น่าจะเป็นไปได้มากที่สุด  คือ X31 เท่ากับ 50 
การเพิ่มค่าดังกล่าวจะทำให้เกิดผลกระทบเป็นวงจร ซึ่งเมื่อบวกและลบออกไป จนครบวงจรแล้วจะได้คำตอบดังนี้
                                     คำตอบที่ 1 ของวิธี stepping stone

                การเพิ่มค่า X31  =  50 นั้น จะทำให้ X33 ซึ่งมีค่าเท่ากับ 50 อยู่เดิมหายไป ในขณะเดียวกันในแถวตั้งที่ 1  จะทำให้ 
X11 มีค่าลดลงเท่ากับ 50 ในขณะที่ X13 มีค่าเพิ่มขึ้น 50 ซึ่งนับว่าครบวงจรพอดี คำตอบใหม่นี้จะให้ค่าต้นทุนค่าขนส่งรวม
ต่ำลงคือ
                                 ค่าขนส่ง  =  50*0.1+150*0.4+250*0+50*0.3+350*0.1  = 115 บาท
               อย่างไรก็ตาม ถึงแม้ว่าต้นทุนค่าขนส่งรวมจะต่ำลง เราก็ยังไม่แน่ใจว่า คำตอบที่ได้นี้ เป็นต้นทุนที่ต่ำที่สุดแล้วหรือไม่
วิธีการตรวจสอบก็คือ ใช้คำตอบที่ 1 ที่ได้นี้เป็นพื้นฐานในการคำนวณหาความแตกต่างของต้นทุน dij สำหรับช่องที่ว่างอยู่
ซึ่งนักศึกษาที่ฝึกฝนมาดีแล้วคงอยากจะทำงานใน ส่วนนี้เพื่อทดสอบความสามารถ และเมื่อคำนวณ dij สำหรับช่องที่ว่าง
อยู่จนครบแล้วจะเห็นว่า ไม่มี dij ที่มีค่าติดลบอีก คำตอบที่ 1 ที่ได้นี้จึงเป็นคำตอบที่ให้ค่าต้นทุนขนส่งรวมต่ำที่สุดแล้ว
                                  คำตอบก็คือ    X11     =   50      ขวด       X13      = 150  ขวด
                                                       X22     =   250   ขวด
                                                       X31     =   50     ขวด       X34      =  350  ขวด
                           ต้นทุนค่าขนส่งรวมคือ 115  บาท
ตัวอย่างที่14 กำหนดให้ตารางการขนส่งที่ตัวเลขภายในตารางที่อยู่ในวงกลมเป็นปริมาณสินค้า และตัวเลขที่อยู่ภายในตาราง
ที่ไม่ได้อยู่ในวงกลมเป็นค่าขนส่ง จงใช้วิธีสเตปปิงสโตน
                                     
วิธีทำ 
                            จำนวนช่องที่ใส่ตัวเลขซึ่งเป็นสโตนเซลล์                   =  5 ช่อง
                            จำนวนช่องที่ไม่ได้ใส่ตัวเลขซึ่งเป็นวอเตอร์เซลล์        =  4  ช่อง
                            คือ ช่อง ( 1,3 ) ช่อง ( 2,1 ) ช่อง ( 2,3 ) ช่อง ( 3,1 )
                            จำนวนแถวบวกจำนวนสดมภ์ลบหนึ่ง	                     =  3+3-1
                                                                                                           = 5 ช่อง
                                                                                                           =  จำนวนสโตนเซลล์
                             ดังนั้นใช้วิธีสเตปปิงสโตน
                             สร้างเส้นทางแสดงการเปลี่ยนแปลง และใส่เครื่องหมายโดยเริ่มจากวอเตอร์เซลล์แต่ละช่อง
                            เริ่มจากช่อง ( 1,3 )
                                        
                             ดัชนีการพัฒนา  =   ค่าขนส่งของช่อง ( 1,3 ) - ช่อง ( 1,2 ) + ช่อง ( 3,2 ) – ช่อง ( 3,3 )
                                                      =  4-2+6-3     =    5
                            เริ่มจากช่อง ( 2,1 )
                                       
                            ดัชนีการพัฒนา   =   ค่าขนส่งของช่อง ( 2,1 ) - ช่อง ( 2,2 ) + ช่อง ( 1,2 ) – ช่อง ( 1,1 )
                                                      =  1-5+2-3     =     -5
                            เริ่มจากช่อง ( 2,3 )
                                       
                            ดัชนีการพัฒนา   =  ค่าขนส่งของช่อง ( 2,3 ) - ช่อง ( 2,2 ) + ช่อง ( 3,2 ) – ช่อง ( 3,3 )
                                                      =   2-5+6-3     =     0
                            เริ่มจากช่อง ( 3,1 ) 
                                       
                            ดัชนีการพัฒนา   =   ค่าขนส่งของช่อง ( 3,1 ) - ช่อง ( 3,2 ) + ช่อง ( 1,2 ) – ช่อง ( 1,1 )
                                                     =   4-6+2-3     =     -3
                           จากการคำนวณค่าดัชนีการพัฒนา เลือกค่าที่น้อยที่สุด คือ –5 ซึ่งจะเริ่มจาก ช่อง ( 2,1 ) คือ
                                                                  
                           พบว่าค่าที่เป็นลบ มี 2 ช่อง คือ 50 หน่วย , 75 หน่วย ดังนั้นเลือกค่าที่น้อยที่สุด คือ เลือก 50 หน่วย และเติม 
เติม 50 หน่วย ลงในช่อง ( 2,1 ) พร้อมทั้งปรับค่าอื่นๆ ดังนี้
                                      
หมายเหตุ	***ปรับครั้งที่ 1
                      ** ปรับครั้งที่ 2
                        * ปรับครั้งที่ 3
หลังจากนั้นตรวจสอบวอเตอร์เซลล์ จากผลลัพธ์ที่พัฒนาไปแล้ว ได้แก่ช่อง ( 1,2 ) , ช่อง ( 1,3 ) ช่อง ( 2,3 ) ช่อง ( 3,1 )
                          เริ่มช่อง ( 1,1 )
                                     
                         ดัชนีพัฒนาคำตอบ  =   3-1+5-2  =     5
                         เริ่มช่อง ( 1,3 )
                                    
                        ดัชนีพัฒนาคำตอบ  =  4-2+6-3  =  5
                        เริ่มช่อง ( 2,3 )
                                    
                       ดัชนีพัฒนาคำตอบ  =  4-2+6-3  =  5
                       เริ่มช่อง ( 3,1 )
                                   
                       ดัชนีพัฒนาคำตอบ  =  4-6+5-1  =  2
จากการคำนวณดัชนีพัฒนาคำตอบที่ได้เป็น 5,5,0,2 ซึ่งมีค่าเป็นบวก ถือว่าคำตอบที่ได้เป็นคำตอบที่ดีที่สุด ดังนั้นคำนวณต้นทุน
การขนส่ง ได้ดังนี้
                                ต้นทุนการขนส่ง = 2(100 ) +1(50)+5(25)+6(45)+3(80)
                                                         = 200+50+125+270+240  = 885
และถ้าในทางกลับกันดัชนีพัฒนาคำตอบที่ได้ มีค่าเป็นศูนย์ แสดงว่ามีเส้นทางและปริมาณการขนส่งแบบอื่นที่ก่อให้เกิดต้นทุน
การขนส่งเท่ากับต้นทุนการขนส่งต่ำสุด
                                  
จากตารางมีค่าเป็นลบ 2 ช่อง คือ 25,80 ดังนั้นเลือกค่าที่น้อยที่สุด คือ 25 จึงใส่ที่ช่อง ( 2,3 )
                                 
                      คำนวณต้นทุนการขนส่ง = 2(100)+50(1)+25(2)+70(6)+55(3)
                                                           = 885
                     พบว่าต้นทุนการขนส่งเท่ากัน