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

ขั้นตอนวิธีซิมเพล็กซ์  หรือ วิธีซิมเพล็กซ์  จะอาศัยหลักการของเมทริกซ์เข้าช่วยในการหาผลลัพธ์ที่เหมาะสมที่สุด ซึ่งจะทำให้เห็นถึงการเปลี่ยนแปลงของตัวแปรในแต่ละขั้นตอนอย่างมีเหตุผล และเปลี่ยนแปลงไปในทางที่จะนำมาซึ่งผลลัพธ์ที่โมเดลทางคณิตศาสตร์ต้องการ
บทนำ.
การแก้ปัญหาโปรแกรมเชิงเส้น หรือ กำหนดการเชิงเส้น (Linear programming) สำหรับโมเดลคณิตศาสตร์ที่มีตัวแปรไม่มาก เราก็สามารถหาคำตอบได้ไม่ยากนัก แต่หากตัวแปรมีมากขึ้น ก็จำเป็นต้องหาวิธีการอื่นเข้ามาช่วยในการหาคำตอบของโมเดล ซึ่งวิธีซิมเพล็กซ์เป็นวิธีการหนึ่งที่ให้ผลดี และเข้าใจได้ง่าย
ขั้นตอนวิธีซิมเพล็กซ์ เป็นวีธีการของ จอร์จ แดนท์ซิก (George Dantzig) ที่ได้รับความนิยมอย่างมากในการแก้ปัญหาโปรแกรมเชิงเส้น ซึ่งชื่อของขั้นตอนวิธีนี้ มาจากแนวคิดของ ซิมเพล็กซ์ นั่นเอง
วิธีซิมเพล็กซ์เป็นวิธีที่มีประสิทธิภาพมากในการแก้ปัญหากำหนดการเชิงเส้น (Linear programming) ซึ่งเป็นกระบวนการทางพีชคณิตที่ประกอบด้วยการกระทำซ้ำ ๆ กันเพื่อให้ได้คำตอบที่ดีที่สุด ยกตัวอย่างเช่น
" ค่าที่มากที่สุดของ" <math> Z = 3x_1 + 2x_2</math>
" ภายใต้เงื่อนไข"
<math> \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} </math>
ปัญหาในลักษณะเช่นนี้จะสามารถใช้วิธีซิมเพล็กซ์ในการหาคำตอบได้ โดยจำเป็นจะต้องเปลี่ยนปัญหาที่กำหนดให้อยู่ในรูปมาตรฐาน (Standard Form) โดยจะต้องแปลงอสมการของปัญหาให้เป็นสมการ ซึ่งจะมีการเพิ่มตัวแปรเข้าไปในแต่ละอสมการเรียกว่าตัวแปรแบบ Slack หรือ Surplus ดังนั้น เราจะเขียนตัวอย่างข้างต้นได้ใหม่เป็น
" ค่าที่มากที่สุดของ" <math> Z = 3x_1 + 2x_2</math>
" ภายใต้เงื่อนไข"
<math> \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} </math>
รูปมาตรฐาน.
การจะแปลงกำหนดการเชิงเส้นให้อยู่ในรูปแบบมาตรฐาน สามารถทำได้โดยการแปลง อสมการที่มีเครื่องหมาย <math>\geq,\leq</math> ให้อยู่ในรูปของสมการ ซึ่งเราจะเพิ่มตัวแปรเข้าไปในสมการที่มีค่ามากกว่าหรือเท่ากับ 0 และย้ายตัวแปรทั้งหมดไว้ด้านขวา ส่วนตัวเลขที่เหลือไว้ด้านซ้าย ซึ่งรูปมาตรฐานจะอยู่ในรูป
" ค่าที่มากที่สุดของ" <math> Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n</math>
" ภายใต้เงื่อนไข"
<math> \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} </math>
จากรูปแบบโมเดลคณิตศาสตร์ของโปรแกรมเชิงเส้น
" ค่าที่มากที่สุดของ" <math> Z = c_1x_1 + c_2x_2 + c_3x_3</math>
" ภายใต้เงื่อนไข"
<math> \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} </math>
เขียนสมการเพื่อเพิ่มเติมตัวแปรช่วย ได้ดังนี้
<math> \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} </math>
ตัวแปรที่เพิ่มเข้ามา.
ในอสมการที่มี <math> \leq </math> โดยทางซ้ายเป็นการดำเนินการของตัวแปร และทางขวาเป็นค่าตัวเลขตัวหนึ่ง เราสามารถเพิ่มตัวแปรแบบ Slack เข้าไปทางซ้ายได้เพื่อเป็นตัวแทนเพิ่มค่าให้เท่ากับค่าทางขวา เช่น
" จากข้อจำกัด" <math> 7x_1 + 34x_2 \leq 125 </math> " สามารถเขียนเป็น" <math> 7x_1 + 34x_2 + x_3 = 125 </math> เมื่อ <math>x_3 \geq 0 </math>
ในอสมการที่มี <math> \geq </math> โดยทางซ้ายเป็นการดำเนินการของตัวแปร และทางขวาเป็นค่าตัวเลขตัวหนึ่ง เราสามารถเพิ่มตัวแปรแบบ Surplus เข้าไปทางซ้ายได้เพื่อเป็นตัวแทนลดค่าให้เท่ากับค่าทางขวา เช่น
" จากข้อจำกัด" <math> 7x_1 + 34x_2 \geq 125 </math> " สามารถเขียนเป็น" <math> 7x_1 + 34x_2 - x_3 = 125 </math> เมื่อ <math>x_3 \geq 0 </math>
ขั้นตอนวิธี.
วิธีการต่อไปนี้จะเป็นการดำเนินการตามขั้นตอนวิธีซิมเพล็กซ์ เพื่อหาผลเฉลยที่มีค่ามากที่สุด แต่หากต้องการหาผลเฉลยที่มีค่าน้อยสุดสามารถทำได้โดย ค่าน้อยสุดของ <math> Z = -(</math> ค่ามากสุดของ <math> -Z) </math>
วิธีการ.
1. จัดรูป กำหนดการเชิงเส้น ให้อยู่ในรูปมาตรฐาน
2. สร้างตารางซิมเพล็กซ์ดังนี้
3. เลือกตัวแปรขาเข้า (entering variable) คือการเลือกตัวแปรที่ไม่เป็นตัวแปรมูลฐาน (non-basic variable) ให้เป็นตัวแปรมูลฐาน (basic variable) โดยดูจากสัมประสิทธิ์ของตัวแปรในสมการเป้าหมาย (แถว Z) ที่ติดลบมากที่สุด แต่ถ้าสัมประสิทธิ์ของตัวแปรทุกตัวเป็นบวกหรือศูนย์แล้ว แสดงว่าถึงจุดที่เหมาะสม (optimal solution) ไม่ต้องทำต่อไปอีก
4. เลือกตัวแปรขาออก (leaving variable) ด้วยการหาอัตราส่วนของค่าผลลัพธ์กับสัมประสิทธิ์ของตัวแปรเข้าที่เลือกไว้ในขั้นที่ 3 (ไม่ต้องคำนึงถึงสัมประสิทธิ์ที่เป็นลบหรือศูนย์) เลือกอัตราส่วนต่ำสุดของตัวแปรมูลฐาน อยู่ที่ตัวใดแสดงว่าตัวนั้นจะเป็นตัวแปรออก
5. เปลี่ยนตัวแปรมูลฐาน ด้วยการแลกที่กันระหว่างตัวแปรขาเข้าและตัวแปรขาออก ด้วยการคำนวณโดยใช้การดำเนินการตามแถว (row operation)
6. ให้กลับไปทำขั้นที่ 3 - 5 ต่อไปเรื่อย ๆ จนกระทั่งถึงจุดที่เหมาะสมแล้ว
ตัวอย่าง.
"ค่ามากที่สุด" <math>Z = 6x_1 + 4x_2</math>
"จากข้อจำกัด" 
<math> \begin{align}
2x_1 + 3x_2 &\leq 100 \\
4x_1 + 2x_2 &\leq 120 \\
x_1, x_2 &\geq 0
\end{align} </math>
สามารถเขียนเป็นรูปแบบมาตรฐานได้ดังนี้
"ค่ามากที่สุด" <math>Z - 6x_1 - 4x_2 = 0</math>
"จากข้อจำกัด" 
<math> \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} </math>
นำรูปแบบมาตรฐานที่ได้ไปสร้างตารางซิมเพล็กซ์ ได้ดังนี้
พิจารณาแถวแรก <math>Z</math> ค่าสัมประสิทธิ์ที่มีค่าน้อยสุด คือ <math>-6</math> จึงเลือก <math>x_1</math> เป็นตัวแปรขาเข้า จากนั้นพิจารณาอัตราส่วนของค่า <math>b</math> กับสัมประสิทธิ์ของตัวแปรขาเข้า จะได้ว่า แถวที่ <math>x_3</math> มีอัตราส่วนเป็น <math>\frac{100}2 = 50</math> และแถวที่ <math>x_4</math> มีอัตราส่วนเป็น <math>\frac{120}4 = 30</math> ดังนั้นจึงเลือก <math>x_4</math> เป็นตัวแปรขาออก
เปลี่ยนให้ <math>x_1</math> เป็นตัวแปรมูลฐาน โดยแลกที่กับ <math>x_4</math> ด้วยวิธีการดำเนินการตามแถว จะได้ตารางซิมเพล็กซ์ ดังนี้
<math> \begin{align}
R_3 &:= \frac14R_3 \\
R_2 &:= -2R_3 + R_2 \\
R_1 &:= 6R_3 + R_1
\end{align} </math>
พิจารณาแถวแรก <math>Z</math> ค่าสัมประสิทธิ์ที่มีค่าน้อยสุด คือ <math>-1</math> จึงเลือก <math>x_2</math> เป็นตัวแปรขาเข้า จากนั้นพิจารณาอัตราส่วนของค่า <math>b</math> กับสัมประสิทธิ์ของตัวแปรขาเข้า จะได้ว่า แถวที่ <math>x_3</math> มีอัตราส่วนเป็น <math>\frac{40}2 = 20</math> และแถวที่ <math>x_1</math> มีอัตราส่วนเป็น <math>\frac{30}{1/2} = 60</math> ดังนั้นจึงเลือก <math>x_3</math> เป็นตัวแปรขาออก
เปลี่ยนให้ <math>x_2</math> เป็นตัวแปรมูลฐาน โดยแลกที่กับ <math>x_3</math> ด้วยวิธีการดำเนินการตามแถว จะได้ตารางซิมเพล็กซ์ ดังนี้
<math> \begin{align}
R_2 &:= \frac12R_2 \\
R_3 &:= -\frac12R_2 + R_3 \\
R_1 &:= R_2 + R_1
\end{align} </math>
เมื่อพิจารณาตารางซิมเพล็กซ์ก็จะเห็นว่า สัมประสิทธิ์ในสมการเป้าหมาย (พิจารณาแถว Z) มีค่าไม่ติดลบทั้งหมด ดังนั้นเราก็ได้ผลเฉลยที่เหมาะสมที่สุดแล้วดังนี้
<math> x_1 = 20,\ x_2 = 20,\ </math>"ค่ามากที่สุดของ" <math>Z = 200</math>
ประสิทธิภาพ.
ขั้นตอนวิธีซิมเพล็กซ์ เป็นวิธีการที่มีประสิทธิภาพในทางปฏิบัติ และได้รับการพัฒนามากกว่าวิธีที่คิดค้นขึ้นมาก่อนหน้า อย่างไรก็ตามในปี พ.ศ. 2515 Klee และ Minty ได้เสนอตัวอย่างที่ที่แสดงให้เห็นว่าในกรณีเลวร้ายที่สุด ประสิทธิภาพการทำงานของขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นเอกซ์โพเนนเชียล ตั้งแต่นั้นมาการกระทำหรือการดำเนินการด้วยขั้นตอนวิธีนี้ก็ถูกแสดงว่าเป็นขั้นตอนวิธีที่มีประสิทธิภาพที่แย่
การวิเคราะห์เชิงปริมาณและการสังเกตว่าขั้นตอนวิธีซิมเพล็กซ์มีประสิทธิภาพในทางปฏิบัติแม้ว่าจะมีใช้เวลาเป็นเอกซ์โพแนนเชียลในกรณีที่เลวร้ายที่สุดก็ตาม และได้นำไปสู่การพัฒนาที่จะวัดประสิทธิภาพในรูปแบบอื่น ซึ่งจริง ๆ แล้ว ขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นโพลิโนเมียลในกรณีเฉลี่ยทั่วไป ภายใต้การแจกแจงความน่าจะเป็น ซึ่งความแม่นยำของประสิทธิภาพในเชิงเฉลี่ยนี้จะขึ้นอยู่กับการเลือกการแจกแจงความน่าเป็นของโมเดลทางคณิตศาสตร์ และการนำเสนออื่น ๆ ได้แสดงให้เห็นว่ากรณีที่เลวร้ายที่สุดสำหรับขั้นตอนวิธีซิมเพล็กซ์นั้นมีผลน้อยมากต่อประสิทธิภาพโดยรวม