ขั้นตอนวิธีซิมเพล็กซ์ (อังกฤษ: simplex algorithm) หรือ วิธีซิมเพล็กซ์ (อังกฤษ: simplex method) จะอาศัยหลักการของเมทริกซ์เข้าช่วยในการหาผลลัพธ์ที่เหมาะสมที่สุด ซึ่งจะทำให้เห็นถึงการเปลี่ยนแปลงของตัวแปรในแต่ละขั้นตอนอย่างมีเหตุผล และเปลี่ยนแปลงไปในทางที่จะนำมาซึ่งผลลัพธ์ที่โมเดลทางคณิตศาสตร์ต้องการ
การแก้ปัญหาโปรแกรมเชิงเส้น หรือ กำหนดการเชิงเส้น (Linear programming) สำหรับโมเดลคณิตศาสตร์ที่มีตัวแปรไม่มาก เราก็สามารถหาคำตอบได้ไม่ยากนัก แต่หากตัวแปรมีมากขึ้น ก็จำเป็นต้องหาวิธีการอื่นเข้ามาช่วยในการหาคำตอบของโมเดล ซึ่งวิธีซิมเพล็กซ์เป็นวิธีการหนึ่งที่ให้ผลดี และเข้าใจได้ง่าย
ขั้นตอนวิธีซิมเพล็กซ์ เป็นวีธีการของ จอร์จ แดนท์ซิก (George Dantzig) ที่ได้รับความนิยมอย่างมากในการแก้ปัญหาโปรแกรมเชิงเส้น ซึ่งชื่อของขั้นตอนวิธีนี้ มาจากแนวคิดของ ซิมเพล็กซ์ นั่นเอง
วิธีซิมเพล็กซ์เป็นวิธีที่มีประสิทธิภาพมากในการแก้ปัญหากำหนดการเชิงเส้น (Linear programming) ซึ่งเป็นกระบวนการทางพีชคณิตที่ประกอบด้วยการกระทำซ้ำ ๆ กันเพื่อให้ได้คำตอบที่ดีที่สุด ยกตัวอย่างเช่น
ค่าที่มากที่สุดของ
ภายใต้เงื่อนไข
-
ปัญหาในลักษณะเช่นนี้จะสามารถใช้วิธีซิมเพล็กซ์ในการหาคำตอบได้ โดยจำเป็นจะต้องเปลี่ยนปัญหาที่กำหนดให้อยู่ในรูปมาตรฐาน (Standard Form) โดยจะต้องแปลงอสมการของปัญหาให้เป็นสมการ ซึ่งจะมีการเพิ่มตัวแปรเข้าไปในแต่ละอสมการเรียกว่าตัวแปรแบบ Slack หรือ Surplus ดังนั้น เราจะเขียนตัวอย่างข้างต้นได้ใหม่เป็น
ค่าที่มากที่สุดของ
ภายใต้เงื่อนไข
-
การจะแปลงกำหนดการเชิงเส้นให้อยู่ในรูปแบบมาตรฐาน สามารถทำได้โดยการแปลง อสมการที่มีเครื่องหมาย ให้อยู่ในรูปของสมการ ซึ่งเราจะเพิ่มตัวแปรเข้าไปในสมการที่มีค่ามากกว่าหรือเท่ากับ 0 และย้ายตัวแปรทั้งหมดไว้ด้านขวา ส่วนตัวเลขที่เหลือไว้ด้านซ้าย ซึ่งรูปมาตรฐานจะอยู่ในรูป
ค่าที่มากที่สุดของ
ภายใต้เงื่อนไข
-
จากรูปแบบโมเดลคณิตศาสตร์ของโปรแกรมเชิงเส้น
ค่าที่มากที่สุดของ
ภายใต้เงื่อนไข
-
เขียนสมการเพื่อเพิ่มเติมตัวแปรช่วย ได้ดังนี้
-
ในอสมการที่มี โดยทางซ้ายเป็นการดำเนินการของตัวแปร และทางขวาเป็นค่าตัวเลขตัวหนึ่ง เราสามารถเพิ่มตัวแปรแบบ Slack เข้าไปทางซ้ายได้เพื่อเป็นตัวแทนเพิ่มค่าให้เท่ากับค่าทางขวา เช่น
จากข้อจำกัด สามารถเขียนเป็น เมื่อ
ในอสมการที่มี โดยทางซ้ายเป็นการดำเนินการของตัวแปร และทางขวาเป็นค่าตัวเลขตัวหนึ่ง เราสามารถเพิ่มตัวแปรแบบ Surplus เข้าไปทางซ้ายได้เพื่อเป็นตัวแทนลดค่าให้เท่ากับค่าทางขวา เช่น
จากข้อจำกัด สามารถเขียนเป็น เมื่อ
วิธีการต่อไปนี้จะเป็นการดำเนินการตามขั้นตอนวิธีซิมเพล็กซ์ เพื่อหาผลเฉลยที่มีค่ามากที่สุด แต่หากต้องการหาผลเฉลยที่มีค่าน้อยสุดสามารถทำได้โดย ค่าน้อยสุดของ ค่ามากสุดของ
1. จัดรูป กำหนดการเชิงเส้น ให้อยู่ในรูปมาตรฐาน
2. สร้างตารางซิมเพล็กซ์ดังนี้
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3. เลือกตัวแปรขาเข้า (entering variable) คือการเลือกตัวแปรที่ไม่เป็นตัวแปรมูลฐาน (non-basic variable) ให้เป็นตัวแปรมูลฐาน (basic variable) โดยดูจากสัมประสิทธิ์ของตัวแปรในสมการเป้าหมาย (แถว Z) ที่ติดลบมากที่สุด แต่ถ้าสัมประสิทธิ์ของตัวแปรทุกตัวเป็นบวกหรือศูนย์แล้ว แสดงว่าถึงจุดที่เหมาะสม (optimal solution) ไม่ต้องทำต่อไปอีก
4. เลือกตัวแปรขาออก (leaving variable) ด้วยการหาอัตราส่วนของค่าผลลัพธ์กับสัมประสิทธิ์ของตัวแปรเข้าที่เลือกไว้ในขั้นที่ 3 (ไม่ต้องคำนึงถึงสัมประสิทธิ์ที่เป็นลบหรือศูนย์) เลือกอัตราส่วนต่ำสุดของตัวแปรมูลฐาน อยู่ที่ตัวใดแสดงว่าตัวนั้นจะเป็นตัวแปรออก
5. เปลี่ยนตัวแปรมูลฐาน ด้วยการแลกที่กันระหว่างตัวแปรขาเข้าและตัวแปรขาออก ด้วยการคำนวณโดยใช้การดำเนินการตามแถว (row operation)
6. ให้กลับไปทำขั้นที่ 3 - 5 ต่อไปเรื่อย ๆ จนกระทั่งถึงจุดที่เหมาะสมแล้ว
ค่ามากที่สุด
จากข้อจำกัด
-
สามารถเขียนเป็นรูปแบบมาตรฐานได้ดังนี้
ค่ามากที่สุด
จากข้อจำกัด
-
นำรูปแบบมาตรฐานที่ได้ไปสร้างตารางซิมเพล็กซ์ ได้ดังนี้
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
พิจารณาแถวแรก ค่าสัมประสิทธิ์ที่มีค่าน้อยสุด คือ จึงเลือก เป็นตัวแปรขาเข้า จากนั้นพิจารณาอัตราส่วนของค่า กับสัมประสิทธิ์ของตัวแปรขาเข้า จะได้ว่า แถวที่ มีอัตราส่วนเป็น และแถวที่ มีอัตราส่วนเป็น ดังนั้นจึงเลือก เป็นตัวแปรขาออก
เปลี่ยนให้ เป็นตัวแปรมูลฐาน โดยแลกที่กับ ด้วยวิธีการดำเนินการตามแถว จะได้ตารางซิมเพล็กซ์ ดังนี้
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
พิจารณาแถวแรก ค่าสัมประสิทธิ์ที่มีค่าน้อยสุด คือ จึงเลือก เป็นตัวแปรขาเข้า จากนั้นพิจารณาอัตราส่วนของค่า กับสัมประสิทธิ์ของตัวแปรขาเข้า จะได้ว่า แถวที่ มีอัตราส่วนเป็น และแถวที่ มีอัตราส่วนเป็น ดังนั้นจึงเลือก เป็นตัวแปรขาออก
เปลี่ยนให้ เป็นตัวแปรมูลฐาน โดยแลกที่กับ ด้วยวิธีการดำเนินการตามแถว จะได้ตารางซิมเพล็กซ์ ดังนี้
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
เมื่อพิจารณาตารางซิมเพล็กซ์ก็จะเห็นว่า สัมประสิทธิ์ในสมการเป้าหมาย (พิจารณาแถว Z) มีค่าไม่ติดลบทั้งหมด ดังนั้นเราก็ได้ผลเฉลยที่เหมาะสมที่สุดแล้วดังนี้
ค่ามากที่สุดของ
ขั้นตอนวิธีซิมเพล็กซ์ เป็นวิธีการที่มีประสิทธิภาพในทางปฏิบัติ และได้รับการพัฒนามากกว่าวิธีที่คิดค้นขึ้นมาก่อนหน้า อย่างไรก็ตามในปี พ.ศ. 2515 Klee และ Minty ได้เสนอตัวอย่างที่ที่แสดงให้เห็นว่าในกรณีเลวร้ายที่สุด ประสิทธิภาพการทำงานของขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นเอกซ์โพเนนเชียล ตั้งแต่นั้นมาการกระทำหรือการดำเนินการด้วยขั้นตอนวิธีนี้ก็ถูกแสดงว่าเป็นขั้นตอนวิธีที่มีประสิทธิภาพที่แย่
การวิเคราะห์เชิงปริมาณและการสังเกตว่าขั้นตอนวิธีซิมเพล็กซ์มีประสิทธิภาพในทางปฏิบัติแม้ว่าจะมีใช้เวลาเป็นเอกซ์โพแนนเชียลในกรณีที่เลวร้ายที่สุดก็ตาม และได้นำไปสู่การพัฒนาที่จะวัดประสิทธิภาพในรูปแบบอื่น ซึ่งจริงๆ แล้ว ขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นโพลิโนเมียลในกรณีเฉลี่ยทั่วไป ภายใต้การแจกแจงความน่าจะเป็น ซึ่งความแม่นยำของประสิทธิภาพในเชิงเฉลี่ยนี้จะขึ้นอยู่กับการเลือกการแจกแจงความน่าเป็นของโมเดลทางคณิตศาสตร์ และการนำเสนออื่นๆ ได้แสดงให้เห็นว่ากรณีที่เลวร้ายที่สุดสำหรับขั้นตอนวิธีซิมเพล็กซ์นั้นมีผลน้อยมากต่อประสิทธิภาพโดยรวม