Operation Research(OR) Part2 For Industrail Engineering

บทที่ 4 ปัญหาการขนส่งและ ปัญหาการกําหนดงาน (Transportation  Problems  and  Assignment  Problems)

ปัญหาการขนส่ง

กำหนดให้

Sm  คือ แหล่งผลิตแต่ละแห่งมีความสามารถในการผลิต

Dn  คือ ความต้องการของตลาดหรือความสามารถในการเก็บสินค้าของ คลังสินค้าแต่ละแห่ง

Cij  คือ ค่าใช้จ่ายในการส่งสินค้าจากแหล่งผลิต  i ไปยังตลาด  j  ต่อหน่วย *และถ้าการส่งสินค้าจากแหล่งผลิตหนึ่งไปยังตลาดหนึ่งเป็นไป ไม่ได้จะกําหนดให้  Cij  เท่ากับ  Infinity

Xij  คือ ปริมาณสินค้าจากแหล่งผลิต  i ที่ถูกส่งไปยังตลาด  j  เมื่อ  i =  1,  2,  .…….,  m  และ  j  =  1,  2,  .…….,  n

  

ดังนั้นจํานวนตัวแปรตัดสินใจจึงมีเท่ากับ  m x n  ตัว สมการขอบข่ายจึงมีเพียง  m + n – 1  สมการ ที่เป็นอิสระต่อกัน ซึ่งต้องน้อยกกว่าหรือเท่ากับจำนวนตัวแปรมูลฐาน (หมายความว่าจำนวนจุดที่เกิดการขนส่งจะเท่ากับ m + n – 1 ถ้าน้อยกว่าจะเป็นสภาวะซ้อนสถานะ), (จำนวนตัวแปรมูลฐาน=จำนวนจุดที่เกิดการขนส่ง)

วิธีการคำนวนเราจะสมมุติให้ตลาดเเละโรงงานมีจำนวนเท่ากัน แต่ถ้าไม่เท่าเราจะกำหนด ตลาดหรือโรงงานสมมุติขึ้นมา ซึ่งขึ้นกับว่าตลาดหรือโรงงานน้อยกว่ากัน

Eg.

ซึ่งจากตาราง จะมีค่า C=M (Million) และ X=0 บางจุดซึ่งโรงงานจะไม่ขนส่ง เนื่องจากสาเหตุเช่น ค่าใช้จ่ายสูง

และค่า C ของตลาดสมมุติจะ = 0 ทั้งหมด

วิธีการประมาณค่า Z ของ Least Cost

จากตาราง ขั้นตอนการหา

1. หาค่าเลขของ ต่าขนส่งต่อชิ้น ว่าส่งจากไหนไปไหน น้อยที่สุด
2. Focus ที่จุดนั้นแล้ว เอาค่า Demand หลักนั้น - Supply แถวนั้น ถ้า Supply = 0 หรือ Demand =0 ก็ขีดแถบนั้นทิ้ง แล้วหา ตาม 1. ต่อไปเรื่อยๆจนหมด
3. จากการตรวจว่าผลรวม Demand = ผลรวม Supply ทำให้ได้ว่าการหาครั้งสุดท้ายจะ = 0 พอดี
4. M+N-1 คือจำนวนโรงงานกับจำนวนที่จะส่ง จะต้องมีค่า เท่ากับ จำนวนที่ๆต้องขนส่งตามทีเฉพาะจุดๆไปรวมกัน ค่าที่นับได้มากกว่าได้ แต่น้อยกว่าจะเป็นสภาวะซ้อน = เลิกทำ
5. คำนวนค่า Total cost =ผลรวม จำนวนที่ขนส่ง ณ จุดนั้น × ราคา
6. ****แต่ละจุดในการหา 2. ต้องระบุจำนวนที่ส่งไปด้วยเพื่อมาคำนวณ

Eg.

วิธีการประมาณค่า Z ของ North-West Corner

จากตาราง

1. Focus จุด โรงงาน 1 ไปยัง ตลาด 1 แล้วทำการเอาค่า Demand หลักนั้น - Supply แถวนั้น ถ้า Supply = 0 หรือ Demand =0 ก็ขีดแถบนั้นทิ้ง
2. ทำต่อไปโดยคิดตัวถัดไปทางด้านขวาของแถวนั้น
3. แล้วมาเริ่มที่มุมซ้ายบนของตารางเหมอืนเดิม ไปจนครบ คือ Demand and Supply = 0 ทุกช่อง คล้ายๆวิธี Least Cost
4. ทำตาม ข้อ 5. Least Cost ต่อไปเพื่อหา Z

Eg.

วิธีการประมาณค่า Z ของ Vogale

1. นำสองอันดับที่มีค่าน้อยสุดในเเถวๆ หลักๆนั้นๆมาลบกัน
2. ดูว่าส่วนต่างไหนมากสุด focus แถว หรือ หลัก ที่ได้ แล้วFocus ที่ค่าส่งน้อย (เพราะต้นทุนต่ำ)
3. เอาค่า Demand หลักนั้น - Supply แถวนั้น ถ้า Supply = 0 หรือ Demand =0 ก็ขีดแถบนั้นทิ้ง
4. ทำการดำเนืน 1. ใหม่โดยไม่นำส่วนที่ตัดออกมาคิด
5. หา M+ N -1
6. หา Total cost
7. วิธีดีเกือบสุด

การหาผลลัพธ์เหมาะที่สุดโดยวิธี สเตปปิ่งสโตน (Stepping   Stone  Method)

จะต้องมีเส้นทางเดิน (Path) เชื่อมต่อจุดที่ต้องการหาของตัวแปรอมูลฐานตัวหนึ่งกับจุด ยอดที่เป็นตัวแปรมูลฐานที่มีอยู่จนกระทั่งสร้างเป็นทางเดินแล้ววนกลับมายังจุดที่เป็นตัวแปรอมูลฐานตัวเดิม

*ถ้าของตัวแปรอมูลฐานบางตัวเท่ากับศูนย์ขณะที่การหาผลลัพธ์ได้ผลที่ดีที่สุดแล้วจะทําให้ ปัญหาการขนส่งนั้นๆ มีผลลัพธ์เหมาะที่สุดมากกว่าหนึ่งชุด

มีวิธีขั้นตอนดังนี้ เมื่อได้ตารางมาเเล้ว

1. หา C bar จากช่องที่ไม่มีการขนส่งก่อน (เป็นค่าราคาต่อหน่วย)
2. ทำการหมุนจากจุดนั้น (ทวนหรือตามก็ได้ และไม่จำเป็นต้องเป็นล็อคสี่เหลี่ยมหรือติดกันเเต่มีข้อเเม้อยู่ว่า เมื่อถึงจุดถัดไปเเล้วต้องเปลี่ยนทิศ) ต่อจุดกับจุดที่มีการขนส่งวนมายังจุดนี้ ซึ่งจะเป็นการหาค่า C bar โดยเป็นการรวมค่าที่มี Pattern คือ + - + - (เป็นการรวมค่า C ที่ไม่ได้มีเเค่ +อย่างเดียว) จนกระทั้งวนมาจุดเริ่มต้นคือ +

กรณี C bar มีค่าต่างๆดังนี้

• ถ้าเป็น + ทุกจุดในตารางจะได้ ปัญหาที่ Optimal Solution
• ถ้าเป็น - บางจุดหรือมากกว่า ก็ต้องเลือกค่า C bar ที่ติดลบมากสุดไป Improve ก่อน
• ถ้ามี = 0 จะได้ว่าชุดคำตอบที่ดีที่สุดมีได้ มากกว่า 1 คำตอบ

3. หาก C bar ติดลบ ให้ Focus จุดที่มีการขนส่งน้อยสุด (Xij) ของ Pattern - ในการได้มาซึ่ง C bar ที่ติดลบ จากนั้นนำค่า Xij ที่เลือก ไป + - + - ตาม Pattern เดิมนี้ ที่จำนวนขนส่งของเเต่ละช่องของการได้มาซึ่งค่า C bar ติดลบ
4. จากนั้นเราจะได้ตารางใหม่เเล้วทำตาม 1.
5. *วิธีการหาคำตอบอื่นๆเมื่อ C bar = 0 ที่จุดนั้นๆ ก็ทำเหมือนว่า C bar มันติดลบ แต่ ไม่ต้องหมุนใหม่เฉยๆ เราก็จะได้ค่า Xij ที่ C bar = 0 นั้นเปลี่ยนไปจากเดิม แต่ Z จะเท่าเดิม

Eg.

ปัญหาการกําหนดงาน

งมีจํานวนเครื่องจักรเท่ากับจํานวนงาน  งานแต่ละงานจะถูกดําเนินการให้แล้ว เสร็จโดยเครื่องจักรหนึ่งๆ เท่านั้น  และเครื่องจักรทุกเครื่องจะทํางานได้เพียงงานเดียว ณ เวลานั้นๆ  สําหรับ ค่าใช้จ่ายในการทํางานหนึ่งโดยเครื่องจักรที่ต่างกันอาจจะไม่เท่ากัน

โรงงานแห่งหนึ่งมี เครื่องจักร  n  เครื่อง คือ  M1 ,  M2 ,  ……… ,  Mn

มีงานแตกต่างกันอยู่  n  งาน คือ J1 ,  J2 ,  ……… ,  Jn

ให้  Cij เป็นค่าใช้จ่ายในการทํางาน j  โดยเครื่องจักร  I

ตัวแปรตัดสินใจ คือ  Xij จะมีค่าเป็น  1  หรือ  0  เท่านั้น 

โดยกําหนดให้

Xij  =  1  เมื่อกําหนดงาน  j  ให้กับเครื่องจักร  i

Xij =  0  เมื่อไม่กําหนดงาน  j  ให้กับเครื่องจักร  i

การหาผลลัพธ์มูลฐานที่เป็นไปได้ของปัญหาการขนส่งจะต้องมีตัวแปรมูลฐานเท่ากับ  n + n -1

ตัวแปรมูลฐานอีก  n – 1  ตัวมีค่าเป็นศูนย์ จึงเป็นสาเหตุให้เกิดสภาวะซ้อนสถานะและทําให้ประสิทธิภาพการ หาผลลัพธ์ช้าลง

วิธีฮังกาเรียน (Hungarian  Method) มีวิธีการดังนี้

กรณี Objective=Minimize

1. นำค่าน้อยที่สุดในแถว || หลัก ไปลบกับค่า แถว || หลัก นั้นๆ ทุกๆเเถว || หลัก
2. ลากเส้นตรงผ่านเลข 0 ให้มากที่สุดและใช้เส้นตรงน้อยสุด

กรณีจำนวนเส้นตรงมีจำนวนดังนี้

• ถ้าจำนวนเส้นตรง = จำนวนคนงานหรือเครื่องจักร ก็จะสามารถหาจับคู่ระหว่างงานกับเครื่องจักรหรือคนได้ต่อไปตามข้อ 4.
• ถ้าจำนวนเส้นตรงน้อยกว่า จำนวนคนงานหรือเครื่องจักร ให้ทำตามข้อ 3. ต่อไปนี้

3. เลือกพิจารณาเฉพาะตัวเลขข้อมูลที่ไม่มีเส้นตรงตัดผ่าน จากนั้นนำค่าที่น้อยสุดไปลบทุกตัว(รวมตัวมันเองด้วย) จากนั้นลากเส้นตามวิธีที่ 2. ****(กรณีมีเส้นตรงที่มีจุดตัด ให้เรานำค่าที่น้อยสุดที่เราพิจารณาจากข้อ3.นี้ไป+กับจุดตัดนั้น)
4. ทำการจับคู่งานกับคนโดยเริ่มจากเลือกช่องที่มีเลข 0 อยู่เเถวเดียวซึ่งจะเป็นคู่กันระหว่างงานกับคน เเล้วได้คู่แรกไป จากนั้นพิจาณาไปเรื่อยๆ โดยใช้วิธีเลือกแบบนี้ไป การจับคู่งานอาจมีหลายคำตอบได้ จากนั้นนำค่า Cij เริ่มแรกมารวมกันตามจุดนั้นๆ

กรณี Objective=Maximize

1. นำ -1 คูณเข้าทุกค่าของ Cij
2. จากนั้นก็ทำตามวิธีแบบ Minimize เพราะจากการคูณเข้า ทำให้รูปแบบเป็นเหมือนกัน

*หากจำนวนงานกับคนทำงานไม่เท่ากันก็เพิ่มจำนวนแบบ Dummy ขึ้นมา เหมือนกับการเพิ่มสมมุติโรงงานหรือตลาด

Eg.

จบไปเเล้วสำหรับ Part แรก เจอกัน Part ต่อไปฮะ อย่าลืมติดตามกันนะ