Skip to content
กลับไปยังผลการค้นหา

Simplex Method

ผู้เสนอ
George Dantzig
ปี
1947
ประเภท
algorithm
กลุ่มวิธี
Optimization

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

Simplex Method ซึ่งพัฒนาโดย George Dantzig ในปี 1947 เป็นอัลกอริทึมพื้นฐานสำหรับการแก้ปัญหาการโปรแกรมเชิงเส้น วิธีการนี้จะสำรวจจุดยอด (vertices) ของขอบเขตที่เป็นไปได้ (feasible region) อย่างเป็นระบบ เพื่อหาคำตอบที่เหมาะสมที่สุด (optimal solution) โดยที่ฟังก์ชันวัตถุประสงค์ (objective function) ถูกทำให้สูงสุดหรือต่ำสุด ภายใต้ข้อจำกัดเชิงเส้น

แนวคิดเบื้องหลังวิธีการ

วิธีการทำงานโดยเริ่มจากจุดมุม (vertex) ของขอบเขตที่เป็นไปได้ที่กำหนดโดยข้อจำกัดเชิงเส้น จากนั้นย้ายไปยังจุดยอดที่อยู่ติดกันซึ่งปรับปรุงค่าของฟังก์ชันวัตถุประสงค์ให้ดีขึ้น วิธีการจะดำเนินต่อไปจนกว่าจะถึงจุดยอดที่ไม่มีจุดยอดที่อยู่ติดกันใดๆ ที่ให้การปรับปรุงเพิ่มเติม ซึ่งเป็นการรับประกันความเป็นเหมาะสมที่สุด อัลกอริทึมใช้ประโยชน์จากคุณสมบัติทางเรขาคณิตที่ว่า ปัญหาการโปรแกรมเชิงเส้นมีคำตอบที่เหมาะสมที่สุดอยู่ที่จุดยอดของโพลีโทป (polytope) ของข้อจำกัด

ประวัติศาสตร์

George Dantzig ได้นำเสนอ Simplex Method ในปี 1947 ซึ่งเป็นการปฏิวัติวงการวิจัยดำเนินงาน (operations research) และกลายเป็นอัลกอริทึมมาตรฐานสำหรับการโปรแกรมเชิงเส้นมานานหลายทศวรรษ Klee และ Minty (1972) แสดงให้เห็นถึงความซับซ้อนแบบเลขชี้กำลังในกรณีที่แย่ที่สุด แต่ในทางปฏิบัติ วิธีการนี้ยังคงรวดเร็ว ในช่วงทศวรรษ 1980 มีการพัฒนาวิธีการจุดภายในเป็นทางเลือก แต่ Simplex Method ยังคงเป็นที่นิยมสำหรับการใช้งานจริงจำนวนมาก เนื่องจากความทนทาน (robustness) และความซับซ้อนของการนำไปใช้ในปัจจุบัน

ควรใช้เมื่อใด

ใช้ Simplex Method เมื่อแก้ปัญหาการโปรแกรมเชิงเส้นที่มีขอบเขตที่เป็นไปได้จำกัด (bounded feasible regions) และฟังก์ชันวัตถุประสงค์เชิงเส้น วิธีการนี้มีประสิทธิภาพโดยเฉพาะอย่างยิ่งสำหรับปัญหาที่มีตัวแปรและข้อจำกัดหลายร้อยหรือหลายพันรายการ หลีกเลี่ยงการใช้งานหากปัญหามีลักษณะไม่เชิงเส้น (nonlinear) หรือไม่มีขอบเขต (unbounded) วิธีการจุดภายใน (interior point methods) อาจเหมาะสมกว่าสำหรับปัญหาขนาดใหญ่มาก

ข้อจำกัดและข้อควรพิจารณา

  • ความซับซ้อนของเวลาในกรณีที่แย่ที่สุด (worst-case time complexity) เป็นแบบเลขชี้กำลัง (exponential) (แม้ว่าจะเกิดขึ้นได้ยากในการใช้งานจริง)
  • อาจทำงานได้ไม่ดีกับปัญหาที่มีความเสื่อมสูง
  • แข่งขันได้น้อยกว่าวิธีการจุดภายในสำหรับปัญหาขนาดใหญ่มาก
  • ต้องการให้ปัญหาอยู่ในรูปแบบมาตรฐานพร้อมการจัดการข้อจำกัดอย่างชัดเจน

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • รับประกันว่าจะหาคำตอบที่เหมาะสมที่สุดได้ในเวลาจำกัดสำหรับปัญหาการโปรแกรมเชิงเส้น
  • มีประสิทธิภาพในการใช้งานจริงด้วยการนำไปใช้ที่รอบคอบและการจัดการความเสื่อม (degeneracy)
  • มีการนำไปใช้อย่างแพร่หลายและได้รับการสนับสนุนจากไลบรารีการหาค่าที่เหมาะสม (optimization libraries) ที่มีความสมบูรณ์
  • เป็นพื้นฐานสำหรับการทำความเข้าใจอัลกอริทึมการหาค่าที่เหมาะสมขั้นสูง

การประยุกต์ใช้

  • การวางแผนการผลิต: การหาปริมาณการผลิตที่เหมาะสมที่สุดเพื่อลดต้นทุนในขณะที่ยังคงตอบสนองข้อจำกัดด้านอุปสงค์
  • การขนส่งและโลจิสติกส์: การกำหนดเส้นทางการขนส่งและปริมาณที่เหมาะสมที่สุดระหว่างคลังสินค้าและศูนย์กระจายสินค้า
  • การหาค่าที่เหมาะสมของพอร์ตการลงทุน: การจัดสรรเงินทุนในสินทรัพย์ต่างๆ เพื่อเพิ่มผลตอบแทนสูงสุดภายใต้ข้อจำกัดด้านความเสี่ยงและงบประมาณ
  • การจัดสรรทรัพยากร: การกระจายทรัพยากรที่มีจำกัด เช่น แรงงานและวัสดุ เพื่อเพิ่มผลผลิตขององค์กรให้สูงสุด
  • ปัญหาการผสม: การผสมวัตถุดิบในสัดส่วนที่เหมาะสมที่สุดเพื่อตอบสนองข้อกำหนดด้านคุณภาพและลดต้นทุน
  • การจัดตารางการทำงานของพนักงาน: การจัดสรรพนักงานเข้ากะเพื่อลดต้นทุนแรงงานในขณะที่ยังคงตอบสนองความต้องการ

วิธีการทำงาน

วิธีการทำงาน

1

แปลงปัญหาการโปรแกรมเชิงเส้นให้อยู่ในรูปแบบมาตรฐาน (standard form) พร้อมตัวแปรส่วนเกิน (slack variables) และระบุคำตอบพื้นฐานที่เป็นไปได้เบื้องต้น (initial basic feasible solution) (โดยปกติคือจุดกำเนิดหากเป็นไปได้)

2

ดำเนินการการดำเนินการหมุน (pivot operations) บนตารางซิมเพล็กซ์ (simplex tableau): เลือกตัวแปรที่จะเข้า (entering variable) ที่มีต้นทุนลดทอน (reduced cost) เป็นลบ ระบุตัวแปรที่จะออก (leaving variable) ด้วยการทดสอบอัตราส่วนน้อยที่สุด (minimum ratio test) และปรับปรุงฐาน (basis)

3

ตรวจสอบเงื่อนไขความเป็นเหมาะสมที่สุดโดยใช้ต้นทุนลดทอน หากต้นทุนลดทอนทั้งหมดไม่เป็นลบสำหรับการหาค่าสูงสุด คำตอบปัจจุบันถือว่าเหมาะสมที่สุด หากไม่เป็นเช่นนั้น ให้กลับไปที่ขั้นตอนการหมุน

ข้อผิดพลาดที่พบบ่อย

  • ความล้มเหลวในการจัดการการเกิดวงจร (cycling) อย่างเหมาะสมเมื่อพบฐานที่เสื่อม (degenerate bases) (ใช้กฎของ Bland หรือวิธีการรบกวน (perturbation methods))
  • การเลือกจุดหมุนที่ไม่ถูกต้องหรือข้อผิดพลาดทางคณิตศาสตร์ในการปรับปรุงตารางที่นำไปสู่ความไม่เสถียรเชิงตัวเลข
  • การไม่ตรวจสอบขอบเขตที่ไม่มีที่สิ้นสุด (unboundedness) หรือความเป็นไปไม่ได้ (infeasibility) ก่อนเริ่มอัลกอริทึม

คำถามที่พบบ่อย

เหตุใด Simplex Method จึงเรียกว่า 'simplex'?

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

อะไรคือความแตกต่างระหว่าง Simplex Method และ Interior Point Method?

Simplex Method จะอยู่บนขอบของขอบเขตที่เป็นไปได้ที่จุดยอด ในขณะที่ Interior Point Method จะเดินทางผ่านภายใน Interior Point Method มีความซับซ้อนในกรณีที่แย่ที่สุดที่ดีกว่า แต่ Simplex มักจะเร็วกว่าในการใช้งานจริงสำหรับปัญหาขนาดกลาง

คุณจัดการกับความเป็นไปไม่ได้หรือขอบเขตที่ไม่มีที่สิ้นสุดได้อย่างไร?

ใช้ Simplex Method แบบสองเฟส (two-phase simplex method): เฟสแรกแก้ปัญหาเสริม (auxiliary problem) เพื่อหาคำตอบพื้นฐานที่เป็นไปได้หรือกำหนดความเป็นไปไม่ได้ เฟสสองใช้วิธีการซิมเพล็กซ์มาตรฐานกับปัญหาเดิม

ความเสื่อม (degeneracy) คืออะไรและทำไมจึงมีความสำคัญ?

ความเสื่อมเกิดขึ้นเมื่อคำตอบพื้นฐานที่เป็นไปได้มีตัวแทนฐานมากกว่าหนึ่ง ซึ่งอาจทำให้เกิดการเกิดวงจร (cycling) จัดการกับปัญหานี้โดยใช้กฎของ Bland (เลือกตัวแปรตามลำดับดัชนี) หรือวิธีการรบกวน (perturbation methods)

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว