ขั้นตอนวิธีซิมเพล็กซ์
 |
บทความนี้ทั้งหมดหรือบางส่วน มีเนื้อหา รูปแบบ หรือลักษณะการนำเสนอที่ไม่เหมาะสมสำหรับสารานุกรม โปรดอภิปรายปัญหาดังกล่าวในหน้าอภิปราย หากบทความนี้เข้ากันได้กับโครงการพี่น้อง โปรดทำการแจ้งย้ายแทน |
 |
บทความนี้ได้รับแจ้งให้ปรับปรุงตามด้านล่าง กรุณาช่วยปรับปรุงบทความ หรือเสนอแนะที่หน้าอภิปราย
|
-
- ขั้นตอนวิธีซิมเพล็กซ์(Simplex Algorithm) หรือวิธีซิมเพล็กซ์ (Simplex method) จะอาศัยหลักการของแมทริกซ์เข้าช่วยในการผลลัพธ์ที่เหมาะสมที่สุด ซึ่งจะทำให้เห็นถึงการเปลี่ยนแปลงของตัวแปรในแต่ละขั้นตน อย่างมีเหตุผล และเปลี่นแปลงไปในทางที่จะนำมาซึ่งผลลัพธ์ที่ โมเดลทางคณิตศาสตร์ต้องการ
เนื้อหา |
[แก้] บทนำ
-
- การแก้ปัญหาโปรแกรมเชิงเส้น หรือ กำหนดการเชิงเส้น (Linear programming) สำหรับโมเดลคณิตศาสตร์ที่มีตัวแปรไม่มาก เราก็สามารถหาคำตอบได้ไม่ยากนัก แต่หากตัวแปรมีมากขึ้น ก็จำเป็นต้องหาวิธีการอื่นเข้ามาช่วยในการหาคำตอบของโมเดล ซึ่งวิธีซิมเพล็กซ์เป็นวิธีการหนึ่งที่ให้ผลดี และเข้าใจได้ง่าย
- ขั้นตอนวิธีซิมเพล็กซ์ เป็นวีธีการของ จอร์จ แดนท์ซิก (George Dantzig) ที่ได้รับความนิยมอย่างมากในการแก้ปัญหาโปรแกรมเชิงเส้น ซึ่งชื่อของขั้นตอนวิธีนี้ มาจากแนวคิดของ ซิมเพล็กซ์ นั่นเอง
- วิธีซิมเพล็กซ์เป็นวิธีที่มีประสิทธิภาพมากในการแก้ปัญหากำหนดการเชิงเส้น(Linear programming) ซึ่งเป็นกระบวนการทางพีชคณิตที่ประกอบด้วยการกระทำซ้ำ ๆ กันเพื่อให้ได้คำตอบที่ดีที่สุด ยกตัวอย่างเช่น
- การแก้ปัญหาโปรแกรมเชิงเส้น หรือ กำหนดการเชิงเส้น (Linear programming) สำหรับโมเดลคณิตศาสตร์ที่มีตัวแปรไม่มาก เราก็สามารถหาคำตอบได้ไม่ยากนัก แต่หากตัวแปรมีมากขึ้น ก็จำเป็นต้องหาวิธีการอื่นเข้ามาช่วยในการหาคำตอบของโมเดล ซึ่งวิธีซิมเพล็กซ์เป็นวิธีการหนึ่งที่ให้ผลดี และเข้าใจได้ง่าย
ค่าที่มากที่สุดของ Z = 3x1 + 2x2
ภายใต้เงื่อนไข 4x1 + 2x2 ≤ 16
x1 + 2x2 ≤ 8
x1 + x2 ≤ 5
x1 ≥ 0 , x2 ≥ 0
ปัญหาในลักษณะเช่นนี้จะสามารถ ใช้วิธีซิมเพล็กซ์ ในการหาคำตอบได้ โดยจำเป็นจะต้องเปลี่ยนปัญหาที่กำหนดให้อยู่ในรูปมาตรฐาน (Standard Form) โดยจะต้องแปลงอสมการของปัญหา ให้เป็นสมการ ซึ่งจะมีการเพิ่มตัวแปรเข้าไปในแต่ละอสมาการเรียนกว่าตัวแปรแบบ Slack หรือ Surplus ดังนั้นเราจะเขียนตัวอย่างข้างต้นได้ใหม่เป็น
ค่ามากที่สุดของ Z = 3x1 + 2x2
ภายใต้เงื่อนไข 4x1 + 2x2 + s1 = 16
x1 + 2x2 + s2 = 8
x1 + x2 + s3 = 5
x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0, s3 ≥ 0
[แก้] รูปมาตรฐาน(Standard Form)
การจะแปลงกำหนดการเชิงเส้นให้อยู่ในรูปแบบมาตรฐาน สามารถทำได้โดยกแปลง อสมการที่มีเครื่องหมาย ≥, ≤ ให้อยู่ในรูปของสมการ ซึ่งเราจะเพิ่มตัวแปรเข้าไปในสมการที่มีค่ามากกว่าหรือเท่ากับ 0 และย้ายตัวแปรทั้งหมดไว้ด้านขวา ส่วนตัวเลขที่เหลือไว้ด้านซ้าย ซึ่งรูปมาตรฐานจะอยู่ในรูป
-
- จากรูปแบบโมเดลคณิตศาสตร์ของโปรแกรมเชิงเส้น
ค่ามากที่สุดของ Z = c1x1 + c2x2 + c3x3
a11x1 + a12x2 + a13x3 ≤ b1
a21x1 + a22x2 + a23x3 ≤ b2
a31x1 + a32x2 + a33x3 ≤ b3
x1 , x2 , x3 ≥ 0
-
- เขียนสมการเพื่อเพิ่มเติมตัวแปรช่วย ได้ดังนี้
Z - c1x1 - c2x2 - c3x3 = 0
a11x1 + a12x2 + a13x3 + x4 = b1
a21x1 + a22x2 + a23x3 + x5 = b2
a31x1 + a32x2 + a33x3 + x6 = b3
x1 , x2 , x3 , x4 , x5, x6 ≥ 0
[แก้] ตัวแปรที่เพิ่มเข้ามามีสองแบบดังนี้
- ตัวแปรแบบ Slack
-
- ในอสมการที่มี ≤ โดยทางซ้ายเป็นการดำเนินการของตัวแปร และทางขวาเป็นค่าตัวเลขตัวหนึ่ง เราสามารถเพิ่มตัวแปรแบบ Slack เข้าไปทางซ้ายได้เพื่อเป็นตัวแทนเพิ่มค่าให้เท่ากับค่าทางขวา เช่น
จากข้อจำกัด 7x1 + 34x2 ≤ 125
สามารถเขียนเป็น 7x1 + 34x2 + x3 = 125 เมื่อ x3 ≥ 0
- ตัวแปรแบบ Surplus
-
- ในอสมการที่มี ≥ โดยทางซ้ายเป็นการดำเนินการของตัวแปร และทางขวาเป็นค่าตัวเลขตัวหนึ่ง เราสามารถเพิ่มตัวแปรแบบ Surplus เข้าไปทางซ้ายได้เพื่อเป็นตัวแทนลดค่าให้เท่ากับค่าทางขวา เช่น
จากข้อจำกัด 7x1 + 34x2 ≥ 125
สามารถเขียนเป็น 7x1 + 34x2 - x3 = 125 เมื่อ x3 ≥ 0
[แก้] ขั้นตอนวิธี
-
- วิธีการต่อไปนี้จะเป็นการดำเนินการตามขั้นตอนวิธีซิมเพล็กซ์ ซึ่งหาผลเฉลยที่มีค่ามากที่สุด แต่หากต้องการหาผลเฉลยที่มีค่าน้อยสุดสามารถทำได้โดย
- วิธีการต่อไปนี้จะเป็นการดำเนินการตามขั้นตอนวิธีซิมเพล็กซ์ ซึ่งหาผลเฉลยที่มีค่ามากที่สุด แต่หากต้องการหาผลเฉลยที่มีค่าน้อยสุดสามารถทำได้โดย
ค่าน้อยสุดของ Z = - (ค่ามากสุดของ -Z)
[แก้] วิธีการ
1 จัดรูป กำหนดการเชิงเส้น ให้อยู่ในรูปมาตรฐาน
2 สร้างตารางซิมเพล็กซ์ดังนี้
-
-
-
- {| class="wikitable"
-
-
|- ! !! Z !! x1 !! x2 !! x3 !! x4 !! x5 !! x6 !! b |- | Z || 1 || -c1 || -c2 || -c3 || 0 || 0 || 0 || 0 |- | x4 || 0 || a11 || a12 || a13 || 1 || 0 || 0 || b1 |- | x5 || 0 || a21 || a22 || a23 || 0 || 1 || 0 || b2 |- | x6 || 0 || a31 || a32 || a33 || 0 || 0 || 1 || b3 |}
3 เลือกตัวแปรขาเข้า(entering variable) คือการเลือกตัวแปรที่ไม่เป็นตัวแปรมูลฐาน(non-basic variable) ให้เป็นตัวแปรมูลฐาน(basic variable) โดยดูจากสัมประสิทธิ์ของตัวแปรที่ติดลบมากที่สุด แต่ถ้าสัมประสิทธิ์ของตัวแปรในสมการเป้าหมายเป็น บวก หรือ 0 แล้วแสดงว่าถึงจุดที่เหมาะสม ไม่ต้องทำต่อไปอีก
4 เลือกตัวแปรขาออก(leaving variable) ด้วยการหาอัตราส่วนของค่าผลลัพธ์กับสัมประสิทธิ์ของตัวแปรเข้าที่เลือกไว้ในขั้นที่ 3 (ไม่ต้องคำนึงถึงสัมประสิทธิ์ที่เป็นลบหรือศูนย์) เลือกอัตราส่วนต่ำสุดของตัวแปรมูลฐาน อยู่ที่ตัวใดแสดงว่าตัวนั้นจะเป็นตัวแปรออก
5 เปลี่ยนตัวแปรมูลฐาน ด้วยการแลกที่กันระหว่างตัวแปรขาเข้าและตัวแปรขาออก ด้วยการคำนวณโดยใช้การดำเนินการตามแถว (row operation)
6 ให้กลับไปทำขั้นที่ 3, 4, 5 ต่อไปเรื่อย ๆ จนกระทั่งถึงจุดที่เหมาะสมแล้ว
[แก้] ตัวอย่าง
ค่ามากที่สุด Z = 6x1 + 4x2
จากข้อจำกัด 2x1 + 3x2 ≤ 100
4x1 + 2x2 ≤ 120
x1, x2 ≥ 0
สามารถเขียนเป็นรูปแบบมาตรฐานได้ดังนี้
ค่ามากที่สุด Z - 6x1 - 4x2 = 0
จากข้อจำกัด 2x1 + 3x2 + x3 = 100
4x1 + 2x2 + x4 = 120
x1, x2, x3, x4 ≥ 0
นำรูปแบบมาตรฐานที่ได้ไปสร้างตารางซิมเพล็กซ์ ได้ดังนี้
-
-
-
- {| class="wikitable"
-
-
|- ! !! Z !! x1 !! x2 !! x3 !! x4 !! b |- | Z || 1 || -6 || -4 || 0 || 0 || 0 |- | x3 || 0 || 2 || 3 || 1 || 0 || 100 |- | x4 || 0 || 4 || 2 || 0 || 1 || 120 |} พิจารณาแถวแรก Z ค่าสัมประสิทธ์ที่มีค่าน้อยสุด คือ -6 จึงเลือก x1 เป็นตัวแปรขาเข้า พิจารณา อัตราส่วนของค่า b กับสัมประสิทธิ์ของตัวแปรขาเข้า
แถวที่ x3 มีอัตราส่วนเป็น 100/2
แถวที่ x4 มีอัตราส่วนเป็น 120/4
ดังนั้นจึงเลือก x4 เป็นตัวแปรขาออก
เปลี่ยนให้ x1 เป็นตัวแปรมูลฐาน โดยแลกที่กับ x4 ด้วยวิธีการดำเนินการตามแถว จะได้ตารางซิมเพล็กซ์ ดังนี้
-
-
-
- {| class="wikitable"
-
-
|- ! !! Z !! x1 !! x2 !! x3 !! x4 !! b |- | Z || 1 || 0 || -1 || 0 || 3/2 || 180 |- | x3 || 0 || 0 || 2 || 1 || -1/2 || 40 |- | x1 || 0 || 1 || 1/ 2 || 0 || 1/4 || 30 |}
พิจารณาในแนวทางเดิมก็จะได้ x2 เป็นตัวแปรขาเข้า และ x3 เป็นตัวแปรขาออก เปลี่ยนให้ x2 เป็นตัวแปรมูลฐาน โดยแลกที่กับ x3 ด้วยวิธีการดำเนินการตามแถว จะได้ตารางซิมเพล็กซ์ ดังนี้
-
-
-
- {| class="wikitable"
-
-
|- ! !! Z !! x1 !! x2 !! x3 !! x4 !! b |- | Z || 1 || 0 || 0 || 1/2 || 5/4 || 200 |- | x2 || 0 || 0 || 1 || 1/2 || -1/4 || 20 |- | x1 || 0 || 1 || 0 || -1/4 || 3/8 || 20 |}
เมื่อพิจารณาตารางซิมเพล็กซ์ก็จะเห็นว่า สัมประสิทธิ์ในฟังก์ชันวัตุประสงค์(พิจารณาแถว Z) มีค่าไม่ติดลบทั้งหมด ดังนั้นเราก็ได้ผลเฉลยี่เหมาะสมที่สุดแล้วดังนี้
x1 = 20
x2 = 20
ค่ามากที่สุดของ z = 200
[แก้] ประสิทธิภาพ
-
- ขั้นตอนวิธีซิมเพล็กซ์ เป็นวิธีการที่มีประสิทธิภาพในทางปฏิบัติ และได้รับการพัฒนามากกว่าวิธีที่คิดค้นขึ้นมาก่อนหน้า อย่างไรก็ตามใน ค.ศ.1972 Klee และ Minty ได้เสนอตัวอย่างที่ที่แสดงให้เห็นว่าในกรณีเลวร้ายที่สุด ประสิทธิภาพการทำงานของขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นเอกซ์โพเนนเชียล ตั้งแต่นั้นมาการกระดำกรือการดำเนินการด้วยขั้นตอนวิธีนี้ก็ถูกแสดงว่าเป็นขั้นตอนตอนวิธีที่มีประสิทะภาพที่แย่
- การวิเคราะห์เชิงปริมาณและการสังเกตว่าขั้นตอนวิธีซิมเพล็กซ์มีประสิทธิภาพในทางปฏิบัติแม้ว่าจะมีใช้เวลาเป็นเอกซ์โพแนนเชียลในกรณีที่เลวร้ายที่สุดก็ตาม และได้นำไปสู่การพัฒนาที่จะวัดประสิทธิภาพในรูปแบบอื่น ซึ่งจริงๆ แล้ว ขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นโพลิโนเมียลในกรณีเฉลี่ยทั่วไป ภายใต้การแจกแจงความน่าจะเป็น ซึ่งความแม่นยำของประสิทธิภาพใยเชิงเฉลี่ยนี้จะขึ้นอยู่กับการเลือกการแจกแจงความน่าเป็นของโมเดลทางคณิตศาสตร์ และการนำเสอนอื่นๆ ได้แสดงให้เห็นว่ากรณีที่เลวร้ายที่สุดสำหรับขั้นตอนวิธีซิมเพล็กซ์นั้นมีผลน้อยมากต่อประสิธิภาพโดยรวม
