การเลือกหลักเกณฑ์การหมุนออก-เข้าสําหรับระเบียบวิธีซิมเพล็กซ์

จาก ChulaPedia

รุ่นปัจจุบันของ 07:37, 6 ตุลาคม 2557

      ปัญหากำหนดการเชิงเส้น (linear programming problem) เป็นปัญหาการหาค่าเหมาะสมที่สุดของฟังก์ชันวัตถุประสงค์ที่เป็นฟังก์ชันเชิงเส้น ภายใต้เงื่อนไขบังคับ ที่เป็นกลุ่มของสมการหรืออสมการเชิงเส้น โดยการแก้ปัญหาชนิดนี้มุ่งจัดสรรทรัพยากรที่มีอยู่จำกัดให้เกิดประโยชน์สูงสุดตามความต้องการ ยกตัวอย่างเช่นการหาต้นทุนต่ำสุดในการผลิตสินค้าของโรงงาน หรือการหากำไรสูงสุดการผลิตสินค้าของโรงงาน ภายใต้เงื่อนไขของวัตถุดิบ ปริมาณแรงงาน และจำนวนเครื่องจักรเป็นต้น
      ในปี 1984  จอร์จ บี แดนท์ซิก ได้นำเสนอวิธีการหาผลเฉลยของปัญหากำหนดการเชิงเส้น คือ ระเบียบวิธีซิมเพล็กซ์ (the simplex method) โดยระเบียบวิธีนี้เริ่มที่จุดมุมหนึ่งจุดของบริเวณที่เป็นไปได้ (the feasible region) จากนั้นจะเดินไปยังจุดมุมถัดไป โดยรับประกันการปรับปรุงค่าฟังก์ชันวัตถุประสงค์ให้ดีขึ้น โดยการเดินแต่ละครั้งจะมีการแลกเปลี่ยนตัวแปร โดยจะเลือกตัวแปรด้วยหลักเกณฑ์การหมุน (pivot rule) จากตัวแปรไม่พื้นฐานทั้งหมดให้เป็นตัวแปรเข้า (the entering variable) แล้วจึงเลือกตัวแปรออกเรียกว่า (the leaving variable)  ที่สอดคล้องกันจากตัวแปรพื้นฐานทั้งหมด และจะทำซ้ำกระบวนการนี้ไปเรื่อยๆ จนได้คำตอบที่เหมาะสมที่สุด ประสิทธิภาพของระเบียบวิธีขึ้นอยู่กับจำนวนการทำซ้ำ และเวลาทั้งหมดที่ใช้จนลู่เข้าสู่ผลเฉลยที่เหมาะสมที่สุด โดยระเบียบวิธีซิมเพล็กซ์ได้รับความนิยมอย่างมาก และมีประสิทธิภาพมากในการแก้ปัญหากำหนดการเชิงเส้นขนาดเล็ก และขนาดกลาง นั่นคือมีจำนวนตัวแปร และ จำนวนเงื่อนไขของปัญหาไม่มาก 
      อย่างไรก็ตามใน ค.ศ.1972 Klee และ Minty ได้เสนอตัวอย่างปัญหาเรียกว่า Klee and Minty Problem ที่แสดงให้เห็นถึงกรณีเลวร้ายที่สุด ซึ่งประสิทธิภาพการทำงานของขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นเอกซ์โพเนนเชียล โดยขึ้นกับจำนวนตัวแปร และ จำนวนเงื่อนไขของปัญหา นอกจากนี้ระเบียบวิธีซิมเพล็กซ์ไม่รับประกันการลู่เข้าสู่ผลเฉลย นั่นคืออาจเกิดการทำซ้ำอย่างไม่สิ้นสุด (cycling)  
      ดังนั้นจึงมีนักวิจัยจำนวนมากที่พยายามปรับปรุงประสิทธิภาพของระเบียบวิธีซิมเพล็กซ์ โดยพยายามลดจำนวนการทำซ้ำในการหาผลเฉลย หรือลดเวลาทังหมดที่ใช้ในการหาผลเฉลย รวมถึงรับประกันว่าการลู่เข้าสู่ผลเฉลย เนื่องจากหลักเกณฑ์การหมุนส่งผลต่อประสิทธิภาพของระเบียบวิธีซิมเพล็กซ์ จึงได้มีงานวิจัยมากมายที่นำเสนอหลักเกณฑ์การหมุนใหม่ๆ เพื่อใช้ร่วมกับระเบียบวิธีซิมเพล็ก ตัวอย่างหลักเกณฑ์ที่ใช้งานได้ดีเช่น  Devex rule (Harris, 1973) และ Steepest-edge rule (Forrest, Goldfarb, 1992) และ Largest-distance pivot rule (Pan, 2008) อย่างไรก็ตามหลักเกณฑ์เหล่านี้ก็ยังไม่สามารถป้องกันการเกิดการทำซ้ำอย่างไม่สิ้นสุดได้
      เพื่อที่จะป้องกันการเกิดการทำซ้ำอย่างไม่สิ้นสุด  แบลนด์ ได้นำเสนอหลักเกณฑ์การหมุน เรียกว่า หลักเกณฑ์การหมุนของแบลนด์ (Bland, 1977) ถึงแม้ว่าหลักเกณฑ์ของแบลนด์จะรับประกันการลู่เข้าสู่คำตอบแต่ไม่รับประกันการปรับปรุงค่าฟังก์ชันวัตถุประสงค์ในแต่ละ การทำซ้ำจึงทำให้ระเบียบวิธีซิมเพล็กซ์เมื่อใช้ร่วมกับหลักเกณฑ์การหมุนของแบลนด์ จึงยังมีประสิทธิภาพไม่ดีเมื่อเทียบกับหลักเกณฑ์การหมุนอื่นๆที่มีอยู่
      หลักเกณฑ์การหมุนทั้งหมดสามารถแยกได้เป็นสองประเภทคือ หลักเกณฑ์การหมุนแบบเข้า-ออก โดยหลักเกณฑ์การหมุนประเภทนี้จะเลือกตัวแปรเข้าก่อนตามหลักในการเลือกของแต่ละหลักเกณฑ์การหมุน เพื่อที่จะปรับปรุงค่าฟังก์ชันวัตถุประสงค์ แล้วจึงเลือกตัวแปรออกที่สอดคล้องกันจากกฎ minimum ratio test สำหรับหลักเกณฑ์ประเภทที่สองคือ หลักเกณฑ์การหมุนแบบออก-เข้า โดยหลักเกณฑ์การหมุนประเภทนี้จะเลือกตัวแปรออกก่อน จากนั้นจึงจะเลือกตัวแปรเข้าที่สอดคล้องกัน 
      การเลือกหลักเกณฑ์การหมุนออก-เข้าสําหรับระเบียบวิธีซิมเพล็กซ์[2] เป็นงานวิจัยที่นำเสนอหลักเกณฑ์การหมุนแบบออก-เข้า แบบใหม่สองหลักเกณฑ์คือ min-out-in และ max-out-in สำหรับใช้ในระเบียบวิธีซิมเพล็กซ์ในการหาผลเฉลยปัญหากำหนดการเชิงเส้น ที่ต้องการหาค่าสูงสุด โดยทั้งสองหลักเกณฑ์เริ่มโดยการแปลงค่าสัมประสิทธิ์ของฟังก์ชันวัตถุประสงค์ ให้เป็น 1 หรือ 0 หรือ -1  หลักเกณฑ์การหมุน min-out-in เลือกตัวแปรออกก่อน ตามเกณฑ์ที่ตัวแปรออกต้องมีค่าน้อยที่สุดจากตัวแปรพื้นฐานทั้งหมด สำหรับหลักเกณฑ์การหมุน  max-out-in  เลือกตัวแปรออกก่อน โดยใช้เกณฑ์ที่ตัวแปรออกต้องมีค่ามากที่สุดจากตัวแปรพื้นฐานทั้งหมด  จากนั้นทั้งสองหลักเกณฑ์จึงเลือกตัวแปรเข้าจากตัวแปรไม่พื้นฐานที่สอดคล้องกัน  ถ้าหลักเกณฑ์การหมุนไม่สามารถใช้ได้ หลักเกณฑ์การหมุนของแดนท์ซิกจะถูกใช้แทน กล่าวคือหลักเกณฑ์การหมุนของแดนท์ซิกเป็นหลักเกณฑ์ที่คอยระวัง หลักเกณฑ์การหมุน  max-out-in  หลักเกณฑ์การหมุนที่คอยระวังด้วยหลักเกณฑ์การหมุนของแบลนด์ สามารถป้องกันการเกิดการทำงานซ้ำรอบสำหรับปัญหากำหนดการเชิงเส้นที่มีค่าทางด้านขวา มากกว่าศูนย์อย่างน้อยหนึ่งค่า  ผลที่ได้นำไปสู่การลู่เข้าสู่คำตอบด้วยจำนวนการทำซ้ำที่จำกัด และหลักเกณฑ์การหมุนนี้สามารถปรับปรุงหลักเกณฑ์การหมุนของแบลนด์ในการแก้ปัญหาการทำงานซ้ำรอบ ดังนั้นหลักเกณฑ์การหมุนนี้เหมาะสมที่จะใช้แก้ปัญหากำหนดการเชิงเส้นที่มีจุดเสื่อม นอกจากนี้หลักเกณฑ์การหมุน min-out-in และ max-out-in สามารถประยุกต์ใช้กับวิธีการซิมเพล็กซ์เครือข่ายเพื่อแก้ปัญหาการไหลในเครือข่ายที่ต่ำที่สุดได้

อ้างอิง

1. Bazara M, Jarvis J, Sherali H (1990). Linear Programming and Network Flows, 3rd edn, John Whiley, New York.

2. มนสิชา ติปะวรรณา (2556). การเลือกหลักเกณฑ์การหมุนออก-เข้าสำหรับระเบียบวิธีซิมเพล็กซ์.วิทยานิพนธ์ปริญญาวิทยาศาสตรดุษฎีบัณฑิต สาขาคณิตศาสตร์ ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ คณะวิทยาศาสตร์จุฬาลงกรณ์มหาวิทยาลัย.