ดูต้นฉบับสำหรับ ขั้นตอนวิธีซิมเพล็กซ์

{{ไม่เป็นสารานุกรม|date=กันยายน 2011}}
{{Issues|สรุป=yes|แก้รูปแบบ=yes|ต้องการอ้างอิง=yes}}
'''ขั้นตอนวิธีซิมเพล็กซ์''' ({{langx|en|simplex algorithm}}) หรือ '''วิธีซิมเพล็กซ์''' ({{langx|en|simplex method}}) จะอาศัยหลักการของ[[เมทริกซ์]]เข้าช่วยในการหาผลลัพธ์ที่เหมาะสมที่สุด ซึ่งจะทำให้เห็นถึงการเปลี่ยนแปลงของตัวแปรในแต่ละขั้นตอนอย่างมีเหตุผล และเปลี่ยนแปลงไปในทางที่จะนำมาซึ่งผลลัพธ์ที่โมเดลทางคณิตศาสตร์ต้องการ
== บทนำ ==
การแก้ปัญหาโปรแกรมเชิงเส้น หรือ [[กำหนดการเชิงเส้น]] (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>

=== ตัวแปรที่เพิ่มเข้ามา ===
* '''ตัวแปรแบบ Slack'''
ในอสมการที่มี <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>
* '''ตัวแปรแบบ Surplus'''
ในอสมการที่มี <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. สร้างตารางซิมเพล็กซ์ดังนี้
:::: {| class="wikitable"
|-
! !! <math>Z</math> !! <math>x_1</math> !! <math>x_2</math> !! <math>x_3</math> !! <math>x_4</math> !! <math>x_5</math> !! <math>x_6</math> !! <math>b</math>
|-
| <math>Z</math> ||<math>1</math> || <math>-c_1</math> || <math>-c_2</math> || <math>-c_3</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math>
|-
| <math>x_4</math> || <math>0</math> || <math>a_{11}</math> || <math>a_{12}</math> || <math>a_{13}</math> || <math>1</math> || <math>0</math> || <math>0</math> || <math>b_1</math>
|-
| <math>x_5</math> || <math>0</math> || <math>a_{21}</math> || <math>a_{22}</math> || <math>a_{23}</math> || <math>0</math> || <math>1</math> || <math>0</math> || <math>b_2</math>
|-
| <math>x_6</math> || <math>0</math> || <math>a_{31}</math> || <math>a_{32}</math> || <math>a_{33}</math> || <math>0</math> || <math>0</math> || <math>1</math> || <math>b_3</math>
|}

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>

นำรูปแบบมาตรฐานที่ได้ไปสร้างตารางซิมเพล็กซ์ ได้ดังนี้
:
{| class="wikitable"
|+
!
!<math>Z</math>
!<math>x_1</math>
!<math>x_2</math>
!<math>x_3</math>
!<math>x_4</math>
!<math>b</math>
|-
|<math>Z</math>
|<math>1</math>
|<math>-6</math>
|<math>-4</math>
|<math>0</math>
|<math>0</math>
|<math>0</math>
|-
|<math>x_3</math>
|<math>0</math>
|<math>2</math>
|<math>3</math>
|<math>1</math>
|<math>0</math>
|<math>100</math>
|-
|<math>x_4</math>
|<math>0</math>
|<math>4</math>
|<math>2</math>
|<math>0</math>
|<math>1</math>
|<math>120</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>

{| class="wikitable"
|+
!
!<math>Z</math>
!<math>x_1</math>
!<math>x_2</math>
!<math>x_3</math>
!<math>x_4</math>
!<math>b</math>
|-
|<math>Z</math>
|<math>1</math>
|<math>0</math>
|<math>-1</math>
|<math>0</math>
|<math>\frac32</math>
|<math>180</math>
|-
|<math>x_3</math>
|<math>0</math>
|<math>0</math>
|<math>2</math>
|<math>1</math>
|<math>-\frac12</math>
|<math>40</math>
|-
|<math>x_1</math>
|<math>0</math>
|<math>1</math>
|<math>\frac12</math>
|<math>0</math>
|<math>\frac14</math>
|<math>30</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>

{| class="wikitable"
|-
! !! <math>Z</math> !! <math>x_1</math> !!<math>x_2</math> !! <math>x_3</math> !! <math>x_4</math> !! <math>b</math>
|-
| <math>Z</math> || <math>1</math> || <math>0</math> || <math>0</math> || <math>\frac12</math> || <math>\frac54</math> || <math>200</math>
|-
| <math>x_2</math> || <math>0</math> || <math>0</math> || <math>1</math> || <math>\frac12</math> || <math>-\frac14</math> || <math>20</math>
|-
| <math>x_1</math> || <math>0</math> || <math>1</math> || <math>0</math> || <math>-\frac14</math> || <math>\frac38</math> || <math>20</math>
|}

เมื่อพิจารณาตารางซิมเพล็กซ์ก็จะเห็นว่า สัมประสิทธิ์ในสมการเป้าหมาย (พิจารณาแถว Z) มีค่าไม่ติดลบทั้งหมด ดังนั้นเราก็ได้ผลเฉลยที่เหมาะสมที่สุดแล้วดังนี้

<math> x_1 = 20,\  x_2  = 20,\ </math>''ค่ามากที่สุดของ'' <math>Z = 200</math>

== ประสิทธิภาพ ==
ขั้นตอนวิธีซิมเพล็กซ์ เป็นวิธีการที่มีประสิทธิภาพในทางปฏิบัติ และได้รับการพัฒนามากกว่าวิธีที่คิดค้นขึ้นมาก่อนหน้า อย่างไรก็ตามในปี พ.ศ. 2515 Klee และ Minty ได้เสนอตัวอย่างที่ที่แสดงให้เห็นว่าในกรณีเลวร้ายที่สุด ประสิทธิภาพการทำงานของขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นเอกซ์โพเนนเชียล ตั้งแต่นั้นมาการกระทำหรือการดำเนินการด้วยขั้นตอนวิธีนี้ก็ถูกแสดงว่าเป็นขั้นตอนวิธีที่มีประสิทธิภาพที่แย่

การวิเคราะห์เชิงปริมาณและการสังเกตว่าขั้นตอนวิธีซิมเพล็กซ์มีประสิทธิภาพในทางปฏิบัติแม้ว่าจะมีใช้เวลาเป็นเอกซ์โพแนนเชียลในกรณีที่เลวร้ายที่สุดก็ตาม และได้นำไปสู่การพัฒนาที่จะวัดประสิทธิภาพในรูปแบบอื่น ซึ่งจริงๆ แล้ว ขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นโพลิโนเมียลในกรณีเฉลี่ยทั่วไป ภายใต้การแจกแจงความน่าจะเป็น ซึ่งความแม่นยำของประสิทธิภาพในเชิงเฉลี่ยนี้จะขึ้นอยู่กับการเลือกการแจกแจงความน่าเป็นของโมเดลทางคณิตศาสตร์ และการนำเสนออื่นๆ ได้แสดงให้เห็นว่ากรณีที่เลวร้ายที่สุดสำหรับขั้นตอนวิธีซิมเพล็กซ์นั้นมีผลน้อยมากต่อประสิทธิภาพโดยรวม

== อ้างอิง ==
* http://staff.cs.psu.ac.th/natikan/OR/OR2002/lesson/4/lesson4-1-4.php {{Webarchive|url=https://web.archive.org/web/20090815151647/http://staff.cs.psu.ac.th/natikan/OR/OR2002/lesson/4/lesson4-1-4.php |date=2009-08-15 }}
* http://web.ku.ac.th/schoolnet/snet2/knowledge_math/simplex/simplex.htm {{Webarchive|url=https://web.archive.org/web/20110912234119/http://web.ku.ac.th/schoolnet/snet2/knowledge_math/simplex/simplex.htm |date=2011-09-12 }}
* [http://www.scaat.in.th/Bachelor/new/1_2552/003_1.doc www.scaat.in.th/Bachelor/new/1_2552/003_1.doc]{{ลิงก์เสีย|date=กันยายน 2021 |bot=InternetArchiveBot |fix-attempted=yes }}
* [http://www.cs.duke.edu/courses/spring08/cps296.2/simplex.pdf www.cs.duke.edu/courses/spring08/cps296.2/simplex.pdf] {{Webarchive|url=https://web.archive.org/web/20120113102951/http://www.cs.duke.edu/courses/spring08/cps296.2/simplex.pdf |date=2012-01-13 }}
* http://www2.isye.gatech.edu/~spyros/LP/LP.html {{Webarchive|url=https://web.archive.org/web/20110903194027/http://www2.isye.gatech.edu/~spyros/LP/LP.html |date=2011-09-03 }}

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