Network model (operations research) — โมเดลเครือข่าย
โมเดลเครือข่าย (ในการวิจัยเชิงปฏิบัติการ; อังกฤษ Network models) — คือกลุ่มของโมเดลทางคณิตศาสตร์ที่แทนปัญหาในรูปแบบของกราฟ (เครือข่าย) โดยที่จุดยอด (โหนด) แทนวัตถุหรือสถานะ และเส้นเชื่อม (ส่วนโค้ง) แทนความสัมพันธ์หรือกระบวนการระหว่างวัตถุเหล่านั้น[1] ในบริบทของการหาค่าเหมาะสมที่สุด คำว่า "เครือข่าย" มักหมายถึงกราฟแบบมีทิศทาง ซึ่งในการวิเคราะห์เชิงปฏิบัติการเรียกโดยตรงว่า "เครือข่าย" โดยจุดยอดของเครือข่ายดังกล่าวเรียกว่าโหนด และเส้นเชื่อมเรียกว่าส่วนโค้ง[2]
โมเดลเครือข่ายเป็นเครื่องมืออันทรงพลังสำหรับการวิเคราะห์และการหาค่าเหมาะสมที่สุดของระบบที่ซับซ้อนในสาขาต่าง ๆ เช่น โลจิสติกส์ โทรคมนาคม การบริหารโครงการ และการเงิน จุดแข็งของโมเดลเหล่านี้อยู่ที่ระดับการสร้างนามธรรมที่สูง กล่าวคือ โหนดอาจแทนเมือง เราเตอร์คอมพิวเตอร์ หรือขั้นตอนของโครงการ ในขณะที่ส่วนโค้งอาจแทนถนน ช่องทางการสื่อสาร หรือการดำเนินงานทางเทคโนโลยี
นิยามและศัพท์บัญญัติ
พื้นฐานของโมเดลเครือข่ายคือทฤษฎีกราฟ แนวคิดหลักได้แก่:
- เครือข่ายการไหล (อังกฤษ flow network): กราฟแบบมีทิศทางที่แต่ละเส้นเชื่อมมี ความจุ (capacity) และ การไหล (flow) ในกราฟมีจุดยอดพิเศษสองจุด ได้แก่ แหล่งต้นทาง (source) ซึ่งเป็นจุดที่การไหลออกมา และ แหล่งปลายทาง (sink) ซึ่งเป็นจุดที่การไหลเข้าสู่[1]
- กฎการอนุรักษ์การไหล: สำหรับจุดยอดใด ๆ ที่ไม่ใช่แหล่งต้นทางหรือแหล่งปลายทาง ผลรวมของการไหลเข้าต้องเท่ากับผลรวมของการไหลออก เงื่อนไขนี้เป็นอนาล็อกแบบไม่ต่อเนื่องของกฎการอนุรักษ์ทางฟิสิกส์[3]
- การวางแผนเครือข่าย: โมเดลที่แทนโครงการในรูปของกลุ่มการดำเนินงาน (ส่วนโค้ง) และเหตุการณ์ (โหนด) ที่สัมพันธ์กัน เครือข่ายดังกล่าวเป็นกราฟแบบมีทิศทางไม่มีวงจร ซึ่งสะท้อนลำดับการดำเนินงาน[4]
คุณสมบัติและทฤษฎีบทสำคัญ
โมเดลเครือข่ายมีคุณสมบัติพิเศษหลายประการที่ทำให้สามารถนำอัลกอริทึมที่มีประสิทธิภาพสูงมาใช้แก้ปัญหาได้
- ความเป็นจำนวนเต็มของผลลัพธ์: ปัญหาการหาค่าเหมาะสมที่สุดบนเครือข่ายหลายปัญหา (เช่น การไหลสูงสุดหรือเส้นทางสั้นที่สุด) มีคุณสมบัติการเป็น totally unimodular ของเมทริกซ์ข้อจำกัด ด้วยเหตุนี้ หากพารามิเตอร์ของปัญหา (ความจุ ความยาว) เป็นจำนวนเต็ม คำตอบที่เหมาะสมที่สุดซึ่งหาได้ด้วยวิธีการโปรแกรมเชิงเส้นก็จะเป็นจำนวนเต็มเช่นกัน โดยไม่จำเป็นต้องเพิ่มข้อจำกัดเพิ่มเติม[5][6]
- ทฤษฎีบทการไหลสูงสุด-การตัดต่ำสุด: ผลลัพธ์หลักของทฤษฎีการไหล กล่าวว่าค่าสูงสุดของการไหลจากแหล่งต้นทางไปยังแหล่งปลายทางเท่ากับความจุต่ำสุดในบรรดาการตัดทั้งหมดที่แยกแหล่งต้นทางและแหล่งปลายทางออกจากกัน ทฤษฎีบทนี้กำหนดเกณฑ์ความเหมาะสมที่สุดสำหรับการไหลและเป็นรากฐานของอัลกอริทึมจำนวนมาก[6][7]
- หลักการความเหมาะสมที่สุดสำหรับเส้นทางสั้นที่สุด: หากเส้นทางจากจุด A ไปยังจุด C เป็นเส้นทางสั้นที่สุด แล้วส่วนใด ๆ ของเส้นทางนั้น (เช่น จากจุดกึ่งกลาง B ไปยัง C) ก็เป็นเส้นทางสั้นที่สุดระหว่างจุดยอดที่สอดคล้องกันเช่นกัน คุณสมบัตินี้ซึ่งเป็นพื้นฐานของการโปรแกรมแบบไดนามิก เป็นสิ่งที่ทำให้อัลกอริทึม เช่น อัลกอริทึม Dijkstra ถูกต้อง[8]
- คุณสมบัติของต้นไม้ครอบคลุมต่ำสุด (MST):
- คุณสมบัติการตัด: สำหรับการตัดใด ๆ ของกราฟ เส้นเชื่อมที่มีน้ำหนักต่ำสุดซึ่งตัดผ่านการตัดนั้นจะเป็นส่วนหนึ่งของ MST อย่างน้อยหนึ่งต้น
- คุณสมบัติวงจร: ในวงจรใด ๆ ของกราฟ เส้นเชื่อมที่มีน้ำหนักสูงสุดจะไม่เป็นส่วนหนึ่งของ MST ใด ๆ เลย
คุณสมบัติเหล่านี้เป็นฐานรองรับความถูกต้องของอัลกอริทึมแบบ "โลภ" (greedy) ของ Prim และ Kruskal[9]
งานหลักในการหาค่าเหมาะสมที่สุดบนเครือข่าย
- ปัญหาเส้นทางสั้นที่สุด: หาเส้นทางที่มีความยาว (น้ำหนัก) รวมต่ำสุดระหว่างโหนดสองโหนดที่กำหนด แก้ได้ด้วยอัลกอริทึม Dijkstra (สำหรับน้ำหนักที่ไม่เป็นลบ) หรืออัลกอริทึม Bellman-Ford (สำหรับน้ำหนักทั่วไป)[8]
- ปัญหาการไหลสูงสุด: กำหนดการไหลสูงสุดที่เป็นไปได้จากแหล่งต้นทางไปยังแหล่งปลายทางภายใต้ความจุที่กำหนดของส่วนโค้ง วิธีแก้ปัญหาแบบดั้งเดิมคืออัลกอริทึม Ford-Fulkerson[6]
- ปัญหาต้นไม้ครอบคลุมต่ำสุด: หากราฟย่อยที่เชื่อมต่อจุดยอดทั้งหมดของเครือข่ายและมีต้นทุนรวมของเส้นเชื่อมต่ำสุด
- วิธีเส้นทางวิกฤต (CPM): ในโมเดลเครือข่ายการวางแผน ให้หาลำดับงานที่ยาวที่สุดซึ่งกำหนดเวลาต่ำสุดที่เป็นไปได้ในการดำเนินโครงการทั้งหมด งานบนเส้นทางนี้มีกันชนเวลาเป็นศูนย์[10]
ตัวอย่าง
- เส้นทางสั้นที่สุด: การค้นหาเส้นทางที่เหมาะสมที่สุดโดยระบบนำทางระหว่างสองจุดบนแผนที่เมือง โดยเมืองคือโหนดและถนนคือส่วนโค้งที่มีน้ำหนักเท่ากับระยะทางหรือเวลาในการเดินทาง
- การไหลสูงสุด: การกำหนดความจุสูงสุดของเครือข่ายท่อส่ง โดยสถานีสูบน้ำคือโหนดและท่อคือส่วนโค้งที่มีความจุจำกัด
- ต้นไม้ครอบคลุมต่ำสุด: การออกแบบเครือข่ายการสื่อสาร (เช่น การวางสายเคเบิลใยแก้วนำแสง) เพื่อเชื่อมต่อหลายเมืองด้วยความยาวเคเบิลรวมต่ำสุด
- เส้นทางวิกฤต: ในโครงการก่อสร้างบ้าน ซึ่งงานต่าง ๆ (การวางรากฐาน การก่อสร้างผนัง การติดตั้งหลังคา) มีระยะเวลาและการพึ่งพาทางเทคโนโลยีที่กำหนดไว้ เส้นทางวิกฤตจะกำหนดระยะเวลาต่ำสุดในการเสร็จสิ้นการก่อสร้าง ความล่าช้าใด ๆ ของงานบนเส้นทางนี้จะส่งผลให้โครงการทั้งหมดล่าช้า[10]
ดูเพิ่มเติม
- การวิจัยเชิงปฏิบัติการ
- ทฤษฎีกราฟ
- ปัญหาการขนส่ง
- วิธีเส้นทางวิกฤต
- PERT
หมายเหตุ
- ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
- ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [2]
- ↑ "Транспортная сеть". Википедия. [3]
- ↑ "Сетевое планирование". Википедия. [4]
- ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
- ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [6]
- ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
- ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [8]
- ↑ "Минимальное остовное дерево". Википедия.
- ↑ 10.0 10.1 "Метод критического пути". Википедия. [9]