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

ขั้นตอนวิธีซิมเพล็กซ์ (simplex algorithm) หรือ วิธีซิมเพล็กซ์ (simplex method) จะอาศัยหลักการของเมทริกซ์เข้าช่วยในการหาผลลัพธ์ที่เหมาะสมที่สุด ซึ่งจะทำให้เห็นถึงการเปลี่ยนแปลงของตัวแปรในแต่ละขั้นตอนอย่างมีเหตุผล และเปลี่ยนแปลงไปในทางที่จะนำมาซึ่งผลลัพธ์ที่โมเดลทางคณิตศาสตร์ต้องการ
== บทนำ ==
การแก้ปัญหาโปรแกรมเชิงเส้น หรือ กำหนดการเชิงเส้น (Linear programming) สำหรับโมเดลคณิตศาสตร์ที่มีตัวแปรไม่มาก เราก็สามารถหาคำตอบได้ไม่ยากนัก แต่หากตัวแปรมีมากขึ้น ก็จำเป็นต้องหาวิธีการอื่นเข้ามาช่วยในการหาคำตอบของโมเดล ซึ่งวิธีซิมเพล็กซ์เป็นวิธีการหนึ่งที่ให้ผลดี และเข้าใจได้ง่าย
ขั้นตอนวิธีซิมเพล็กซ์ เป็นวีธีการของ จอร์จ แดนท์ซิก (George Dantzig) ที่ได้รับความนิยมอย่างมากในการแก้ปัญหาโปรแกรมเชิงเส้น ซึ่งชื่อของขั้นตอนวิธีนี้ มาจากแนวคิดของ ซิมเพล็กซ์ นั่นเอง
วิธีซิมเพล็กซ์เป็นวิธีที่มีประสิทธิภาพมากในการแก้ปัญหากำหนดการเชิงเส้น (Linear programming) ซึ่งเป็นกระบวนการทางพีชคณิตที่ประกอบด้วยการกระทำซ้ำ ๆ กันเพื่อให้ได้คำตอบที่ดีที่สุด ยกตัวอย่างเช่น
 ค่าที่มากที่สุดของ   Z = 3x_1 + 2x_2
 ภายใต้เงื่อนไข
\begin{align}
4x_1 + 2x_2 &\leq 16 \\
x_1 + 2x_2 &\leq 8 \\
x_1 +  x_2 &\leq 5 \\
x_1 \geq 0 , x_2 &\geq 0
\end{align} 
ปัญหาในลักษณะเช่นนี้จะสามารถใช้วิธีซิมเพล็กซ์ในการหาคำตอบได้ โดยจำเป็นจะต้องเปลี่ยนปัญหาที่กำหนดให้อยู่ในรูปมาตรฐาน (Standard Form) โดยจะต้องแปลงอสมการของปัญหาให้เป็นสมการ ซึ่งจะมีการเพิ่มตัวแปรเข้าไปในแต่ละอสมการเรียกว่าตัวแปรแบบ Slack หรือ Surplus ดังนั้น เราจะเขียนตัวอย่างข้างต้นได้ใหม่เป็น
 ค่าที่มากที่สุดของ   Z = 3x_1 + 2x_2
 ภายใต้เงื่อนไข
\begin{align}
4x_1 + 2x_2 + s_1 &\leq 16 \\
x_1 + 2x_2 + s_2 &\leq 8 \\
x_1 +  x_2 + s_3 &\leq 5 \\
x_1 \geq 0 ,x_2 \geq 0 ,s_1 \geq 0 ,s_2 \geq 0 , s_3 &\geq 0
\end{align} 
== รูปมาตรฐาน ==
การจะแปลงกำหนดการเชิงเส้นให้อยู่ในรูปแบบมาตรฐาน สามารถทำได้โดยการแปลง อสมการที่มีเครื่องหมาย \geq,\leq ให้อยู่ในรูปของสมการ ซึ่งเราจะเพิ่มตัวแปรเข้าไปในสมการที่มีค่ามากกว่าหรือเท่ากับ 0 และย้ายตัวแปรทั้งหมดไว้ด้านขวา ส่วนตัวเลขที่เหลือไว้ด้านซ้าย ซึ่งรูปมาตรฐานจะอยู่ในรูป
 ค่าที่มากที่สุดของ   Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n
 ภายใต้เงื่อนไข
\begin{align}
a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &\leq b_1 \\
a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &\leq b_2 \\
&\ \ \vdots \\
a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n &\leq b_n \\
x_1 \geq 0 , x_2 \geq 0, \ldots,x_n &\geq 0
\end{align} 
จากรูปแบบโมเดลคณิตศาสตร์ของโปรแกรมเชิงเส้น
 ค่าที่มากที่สุดของ   Z = c_1x_1 + c_2x_2 + c_3x_3
 ภายใต้เงื่อนไข
\begin{align}
a_{11}x_1 + a_{12}x_2 + a_{13}x_3 &\leq b_1 \\
a_{21}x_1 + a_{22}x_2 + a_{23}x_3 &\leq b_2 \\
a_{31}x_1 + a_{32}x_2 + a_{33}x_3 &\leq b_3 \\
x_1 \geq 0 , x_2 \geq 0 ,x_3 &\geq 0
\end{align} 
เขียนสมการเพื่อเพิ่มเติมตัวแปรช่วย ได้ดังนี้
\begin{align}
Z - c_1x_1 - c_2x_2 - c_3x_3 &= 0\\
a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + x_4 &\leq b_1 \\
a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + x_5 &\leq b_2 \\
a_{31}x_1 + a_{32}x_2 + a_{33}x_3 + x_6 &\leq b_3 \\
x_1 \geq 0 , x_2 \geq 0 , x_3 \geq 0, x_4 \geq 0, x_5 \geq 0,x_6 &\geq 0
\end{align} 
=== ตัวแปรที่เพิ่มเข้ามา ===
ตัวแปรแบบ Slack
ในอสมการที่มี  \leq  โดยทางซ้ายเป็นการดำเนินการของตัวแปร และทางขวาเป็นค่าตัวเลขตัวหนึ่ง เราสามารถเพิ่มตัวแปรแบบ Slack เข้าไปทางซ้ายได้เพื่อเป็นตัวแทนเพิ่มค่าให้เท่ากับค่าทางขวา เช่น
 จากข้อจำกัด  7x_1 + 34x_2  \leq 125   สามารถเขียนเป็น    7x_1 + 34x_2 + x_3 = 125   เมื่อ x_3 \geq 0 
ตัวแปรแบบ Surplus
ในอสมการที่มี  \geq  โดยทางซ้ายเป็นการดำเนินการของตัวแปร และทางขวาเป็นค่าตัวเลขตัวหนึ่ง เราสามารถเพิ่มตัวแปรแบบ Surplus เข้าไปทางซ้ายได้เพื่อเป็นตัวแทนลดค่าให้เท่ากับค่าทางขวา เช่น
 จากข้อจำกัด  7x_1 + 34x_2  \geq 125   สามารถเขียนเป็น    7x_1 + 34x_2 - x_3 = 125   เมื่อ x_3 \geq 0 
== ขั้นตอนวิธี ==
วิธีการต่อไปนี้จะเป็นการดำเนินการตามขั้นตอนวิธีซิมเพล็กซ์ เพื่อหาผลเฉลยที่มีค่ามากที่สุด แต่หากต้องการหาผลเฉลยที่มีค่าน้อยสุดสามารถทำได้โดย ค่าน้อยสุดของ  Z = -( ค่ามากสุดของ  -Z) 
=== วิธีการ ===
1. จัดรูป กำหนดการเชิงเส้น ให้อยู่ในรูปมาตรฐาน
2. สร้างตารางซิมเพล็กซ์ดังนี้
::: 
3. เลือกตัวแปรขาเข้า (entering variable) คือการเลือกตัวแปรที่ไม่เป็นตัวแปรมูลฐาน (non-basic variable) ให้เป็นตัวแปรมูลฐาน (basic variable) โดยดูจากสัมประสิทธิ์ของตัวแปรในสมการเป้าหมาย (แถว Z) ที่ติดลบมากที่สุด แต่ถ้าสัมประสิทธิ์ของตัวแปรทุกตัวเป็นบวกหรือศูนย์แล้ว แสดงว่าถึงจุดที่เหมาะสม  (optimal solution) ไม่ต้องทำต่อไปอีก
4. เลือกตัวแปรขาออก (leaving variable) ด้วยการหาอัตราส่วนของค่าผลลัพธ์กับสัมประสิทธิ์ของตัวแปรเข้าที่เลือกไว้ในขั้นที่ 3 (ไม่ต้องคำนึงถึงสัมประสิทธิ์ที่เป็นลบหรือศูนย์) เลือกอัตราส่วนต่ำสุดของตัวแปรมูลฐาน อยู่ที่ตัวใดแสดงว่าตัวนั้นจะเป็นตัวแปรออก
5. เปลี่ยนตัวแปรมูลฐาน ด้วยการแลกที่กันระหว่างตัวแปรขาเข้าและตัวแปรขาออก ด้วยการคำนวณโดยใช้การดำเนินการตามแถว (row operation)
6. ให้กลับไปทำขั้นที่ 3 - 5 ต่อไปเรื่อย ๆ จนกระทั่งถึงจุดที่เหมาะสมแล้ว
=== ตัวอย่าง ===
ค่ามากที่สุด  Z = 6x_1 + 4x_2
จากข้อจำกัด
\begin{align}
2x_1 + 3x_2 &\leq 100 \\
4x_1 + 2x_2 &\leq 120 \\
x_1, x_2 &\geq 0
\end{align} 
สามารถเขียนเป็นรูปแบบมาตรฐานได้ดังนี้
ค่ามากที่สุด  Z - 6x_1 - 4x_2 = 0
จากข้อจำกัด
\begin{align}
2x_1 + 3x_2 + x_3 &\leq 100 \\
4x_1 + 2x_2 + x_4 &\leq 120 \\
x_1, x_2, x_3, x_4 &\geq 0
\end{align} 
นำรูปแบบมาตรฐานที่ได้ไปสร้างตารางซิมเพล็กซ์ ได้ดังนี้
พิจารณาแถวแรก Z ค่าสัมประสิทธิ์ที่มีค่าน้อยสุด คือ -6 จึงเลือก x_1 เป็นตัวแปรขาเข้า จากนั้นพิจารณาอัตราส่วนของค่า b กับสัมประสิทธิ์ของตัวแปรขาเข้า จะได้ว่า แถวที่  x_3  มีอัตราส่วนเป็น \frac{100}2 = 50 และแถวที่  x_4  มีอัตราส่วนเป็น \frac{120}4 = 30 ดังนั้นจึงเลือก x_4 เป็นตัวแปรขาออก
เปลี่ยนให้ x_1 เป็นตัวแปรมูลฐาน โดยแลกที่กับ x_4 ด้วยวิธีการดำเนินการตามแถว จะได้ตารางซิมเพล็กซ์ ดังนี้
\begin{align}
R_3 &:= \frac14R_3 \\
R_2 &:= -2R_3 + R_2  \\
R_1 &:= 6R_3 + R_1
\end{align} 
พิจารณาแถวแรก Z ค่าสัมประสิทธิ์ที่มีค่าน้อยสุด คือ -1 จึงเลือก x_2 เป็นตัวแปรขาเข้า จากนั้นพิจารณาอัตราส่วนของค่า b กับสัมประสิทธิ์ของตัวแปรขาเข้า จะได้ว่า แถวที่  x_3  มีอัตราส่วนเป็น \frac{40}2 = 20 และแถวที่  x_1  มีอัตราส่วนเป็น \frac{30}{1/2} = 60 ดังนั้นจึงเลือก x_3 เป็นตัวแปรขาออก
เปลี่ยนให้ x_2 เป็นตัวแปรมูลฐาน โดยแลกที่กับ x_3 ด้วยวิธีการดำเนินการตามแถว จะได้ตารางซิมเพล็กซ์ ดังนี้
\begin{align}
R_2 &:= \frac12R_2 \\
R_3 &:= -\frac12R_2 + R_3  \\
R_1 &:= R_2 + R_1
\end{align} 
เมื่อพิจารณาตารางซิมเพล็กซ์ก็จะเห็นว่า สัมประสิทธิ์ในสมการเป้าหมาย (พิจารณาแถว Z) มีค่าไม่ติดลบทั้งหมด ดังนั้นเราก็ได้ผลเฉลยที่เหมาะสมที่สุดแล้วดังนี้
 x_1 = 20,\  x_2  = 20,\ ค่ามากที่สุดของ Z = 200
== ประสิทธิภาพ ==
ขั้นตอนวิธีซิมเพล็กซ์ เป็นวิธีการที่มีประสิทธิภาพในทางปฏิบัติ และได้รับการพัฒนามากกว่าวิธีที่คิดค้นขึ้นมาก่อนหน้า อย่างไรก็ตามในปี พ.ศ. 2515 Klee และ Minty ได้เสนอตัวอย่างที่ที่แสดงให้เห็นว่าในกรณีเลวร้ายที่สุด ประสิทธิภาพการทำงานของขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นเอกซ์โพเนนเชียล ตั้งแต่นั้นมาการกระทำหรือการดำเนินการด้วยขั้นตอนวิธีนี้ก็ถูกแสดงว่าเป็นขั้นตอนวิธีที่มีประสิทธิภาพที่แย่
การวิเคราะห์เชิงปริมาณและการสังเกตว่าขั้นตอนวิธีซิมเพล็กซ์มีประสิทธิภาพในทางปฏิบัติแม้ว่าจะมีใช้เวลาเป็นเอกซ์โพแนนเชียลในกรณีที่เลวร้ายที่สุดก็ตาม และได้นำไปสู่การพัฒนาที่จะวัดประสิทธิภาพในรูปแบบอื่น ซึ่งจริงๆ แล้ว ขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นโพลิโนเมียลในกรณีเฉลี่ยทั่วไป ภายใต้การแจกแจงความน่าจะเป็น ซึ่งความแม่นยำของประสิทธิภาพในเชิงเฉลี่ยนี้จะขึ้นอยู่กับการเลือกการแจกแจงความน่าเป็นของโมเดลทางคณิตศาสตร์ และการนำเสนออื่นๆ ได้แสดงให้เห็นว่ากรณีที่เลวร้ายที่สุดสำหรับขั้นตอนวิธีซิมเพล็กซ์นั้นมีผลน้อยมากต่อประสิทธิภาพโดยรวม
== อ้างอิง ==
http://staff.cs.psu.ac.th/natikan/OR/OR2002/lesson/4/lesson4-1-4.php
http://web.ku.ac.th/schoolnet/snet2/knowledge_math/simplex/simplex.htm 
www.scaat.in.th/Bachelor/new/1_2552/003_1.doc
www.cs.duke.edu/courses/spring08/cps296.2/simplex.pdf 
http://www2.isye.gatech.edu/~spyros/LP/LP.html 
กำหนดการเชิงเส้น
การวิจัยดำเนินการ
ขั้นตอนวิธี