ขั้นตอนวิธีซิมเพล็กซ์

จากวิกิพีเดีย สารานุกรมเสรี
ขั้นตอนวิธีซิมเพล็กซ์(Simplex Algorithm) หรือวิธีซิมเพล็กซ์ (Simplex method) จะอาศัยหลักการของแมทริกซ์เข้าช่วยในการผลลัพธ์ที่เหมาะสมที่สุด ซึ่งจะทำให้เห็นถึงการเปลี่ยนแปลงของตัวแปรในแต่ละขั้นตน อย่างมีเหตุผล และเปลี่นแปลงไปในทางที่จะนำมาซึ่งผลลัพธ์ที่ โมเดลทางคณิตศาสตร์ต้องการ

บทนำ[แก้]

การแก้ปัญหาโปรแกรมเชิงเส้น หรือ กำหนดการเชิงเส้น (Linear programming) สำหรับโมเดลคณิตศาสตร์ที่มีตัวแปรไม่มาก เราก็สามารถหาคำตอบได้ไม่ยากนัก แต่หากตัวแปรมีมากขึ้น ก็จำเป็นต้องหาวิธีการอื่นเข้ามาช่วยในการหาคำตอบของโมเดล ซึ่งวิธีซิมเพล็กซ์เป็นวิธีการหนึ่งที่ให้ผลดี และเข้าใจได้ง่าย
ขั้นตอนวิธีซิมเพล็กซ์ เป็นวีธีการของ จอร์จ แดนท์ซิก (George Dantzig) ที่ได้รับความนิยมอย่างมากในการแก้ปัญหาโปรแกรมเชิงเส้น ซึ่งชื่อของขั้นตอนวิธีนี้ มาจากแนวคิดของ ซิมเพล็กซ์ นั่นเอง
วิธีซิมเพล็กซ์เป็นวิธีที่มีประสิทธิภาพมากในการแก้ปัญหากำหนดการเชิงเส้น(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 ได้เสนอตัวอย่างที่ที่แสดงให้เห็นว่าในกรณีเลวร้ายที่สุด ประสิทธิภาพการทำงานของขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นเอกซ์โพเนนเชียล ตั้งแต่นั้นมาการกระดำกรือการดำเนินการด้วยขั้นตอนวิธีนี้ก็ถูกแสดงว่าเป็นขั้นตอนตอนวิธีที่มีประสิทะภาพที่แย่
การวิเคราะห์เชิงปริมาณและการสังเกตว่าขั้นตอนวิธีซิมเพล็กซ์มีประสิทธิภาพในทางปฏิบัติแม้ว่าจะมีใช้เวลาเป็นเอกซ์โพแนนเชียลในกรณีที่เลวร้ายที่สุดก็ตาม และได้นำไปสู่​​การพัฒนาที่จะวัดประสิทธิภาพในรูปแบบอื่น ซึ่งจริงๆ แล้ว ขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นโพลิโนเมียลในกรณีเฉลี่ยทั่วไป ภายใต้การแจกแจงความน่าจะเป็น ซึ่งความแม่นยำของประสิทธิภาพใยเชิงเฉลี่ยนี้จะขึ้นอยู่กับการเลือกการแจกแจงความน่าเป็นของโมเดลทางคณิตศาสตร์ และการนำเสอนอื่นๆ ได้แสดงให้เห็นว่ากรณีที่เลวร้ายที่สุดสำหรับขั้นตอนวิธีซิมเพล็กซ์นั้นมีผลน้อยมากต่อประสิธิภาพโดยรวม

อ้างอิง[แก้]