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

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

หมวดหมู่:กำหนดการเชิงเส้น
หมวดหมู่:การวิจัยดำเนินการ
หมวดหมู่:ขั้นตอนวิธี