การศึกษาวิธีเพิ่มประสิทธิภาพการกระจายสินค้าโดยใช้เครือข่ายการไหลที่มีค่าน้ำหนักสองค่าบนผลคูณเล็กซิโคกราฟิกของกราฟวิถีและกราฟว่าง

ชื่อนักเรียนผู้จัดทำโครงงานวิทยาศาสตร์

ชยพล เชาว์วีระประสิทธิ์, ณัฐชนน สาระธนะ, ธนกฤต กมลสัมฤทธิ์ผล

อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์

ธรรมนูญ ผุยรอด

โรงเรียนที่กำกับดูแลโครงงานวิทยาศาสตร์

โรงเรียนมหิดลวิทยานุสรณ์

ปีที่จัดทำโครงงานวิทยาศาสตร์

พ.ศ. 2562

บทคัดย่อโครงงานวิทยาศาสตร์

การไหลในเครือข่าย (Flow Network) เป็นแบบจำลองที่ถูกใช้ในระบบการขนส่งเพื่อหาปริมาณสินค้าที่มากที่สุดที่สามารถส่งได้ ในทฤษฎีกราฟได้มีการศึกษาปัญหาการไหลอยู่มากมาย เช่น การหาปริมาณการไหลที่มากที่สุด (Maximum flow) โดยที่ความจุของแต่ละเส้นในเครือข่าย ต้องไม่เป็นจำนวนจริงลบ แต่เมื่อพิจารณาโดยละเอียดแล้ว พบว่าปัจจัยที่ทำให้ระบบการขนส่งนั้นเกิดประสิทธิภาพสูงสุดไม่ได้มีเพียงปริมาณสินค้าเท่านั้น แต่ยังมีปัจจัยอื่น ๆ เช่น เวลา การขนส่งที่ดีต้องใช้เวลาให้น้อย ซึ่งเราสามารถจำลองระยะเวลาเป็นค่าน้ำหนักบนเส้นเชื่อมแต่ละเส้นของกราฟได้ จะเห็นได้ว่าความจุที่แทนเวลาของแต่ละเส้นก็ไม่เป็นจำนวนจริงลบ การใช้เวลาน้อยที่สุดจึงสมมูลกับปัญหาวิถีที่สั้นที่สุด (Shortest Path) ซึ่งทั้ง Maximum flow และ Shortest Path ได้มีการหาขั้นตอนวิธีและพิสูจน์ไว้แล้ว แต่สำหรับการขนส่งสินค้านั้น เราต้องพิจารณาปัญหาทั้งสองอย่างควบคู่กันไป จึงกลายมาเป็นที่มาของโครงงานนี้ซึ่งต้องการจะศึกษาการไหลในเครือข่ายซึ่งแต่ละเส้นจะมีค่าน้ำหนักสองค่าประกอบด้วยความจุและเวลา ทางคณะผู้จัดทำจึงนิยามประสิทธิภาพของการไหลหนึ่ง ๆ และศึกษาเงื่อนไขที่ช่วยในการหาการไหลที่มีประสิทธิภาพของการไหลสูงที่สุด เพื่อให้สามารถจัดการกับปัจจัยทั้งสองได้พร้อม ๆ กัน ทางคณะผู้จัดทำได้ทำการศึกษาเฉพาะการไหลในกราฟผลคูณเล็กซิโคกราฟิกของกราฟวิถีและกราฟว่าง