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

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

บทนำ แก้

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

ขั้นตอนวิธีซิมเพล็กซ์ เป็นวีธีการของ จอร์จ แดนท์ซิก (George Dantzig) ที่ได้รับความนิยมอย่างมากในการแก้ปัญหาโปรแกรมเชิงเส้น ซึ่งชื่อของขั้นตอนวิธีนี้ มาจากแนวคิดของ ซิมเพล็กซ์ นั่นเอง

วิธีซิมเพล็กซ์เป็นวิธีที่มีประสิทธิภาพมากในการแก้ปัญหากำหนดการเชิงเส้น (Linear programming) ซึ่งเป็นกระบวนการทางพีชคณิตที่ประกอบด้วยการกระทำซ้ำ ๆ กันเพื่อให้ได้คำตอบที่ดีที่สุด ยกตัวอย่างเช่น

ค่าที่มากที่สุดของ $Z=3x_{1}+2x_{2}$

ภายใต้เงื่อนไข

{\begin{aligned}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{aligned}}

ปัญหาในลักษณะเช่นนี้จะสามารถใช้วิธีซิมเพล็กซ์ในการหาคำตอบได้ โดยจำเป็นจะต้องเปลี่ยนปัญหาที่กำหนดให้อยู่ในรูปมาตรฐาน (Standard Form) โดยจะต้องแปลงอสมการของปัญหาให้เป็นสมการ ซึ่งจะมีการเพิ่มตัวแปรเข้าไปในแต่ละอสมการเรียกว่าตัวแปรแบบ Slack หรือ Surplus ดังนั้น เราจะเขียนตัวอย่างข้างต้นได้ใหม่เป็น

ค่าที่มากที่สุดของ $Z=3x_{1}+2x_{2}$

ภายใต้เงื่อนไข

{\begin{aligned}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{aligned}}

รูปมาตรฐาน แก้

การจะแปลงกำหนดการเชิงเส้นให้อยู่ในรูปแบบมาตรฐาน สามารถทำได้โดยการแปลง อสมการที่มีเครื่องหมาย $\geq ,\leq$ ให้อยู่ในรูปของสมการ ซึ่งเราจะเพิ่มตัวแปรเข้าไปในสมการที่มีค่ามากกว่าหรือเท่ากับ 0 และย้ายตัวแปรทั้งหมดไว้ด้านขวา ส่วนตัวเลขที่เหลือไว้ด้านซ้าย ซึ่งรูปมาตรฐานจะอยู่ในรูป

ค่าที่มากที่สุดของ $Z=c_{1}x_{1}+c_{2}x_{2}+\cdots +c_{n}x_{n}$

ภายใต้เงื่อนไข

{\begin{aligned}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{aligned}}

จากรูปแบบโมเดลคณิตศาสตร์ของโปรแกรมเชิงเส้น

ค่าที่มากที่สุดของ $Z=c_{1}x_{1}+c_{2}x_{2}+c_{3}x_{3}$

ภายใต้เงื่อนไข

{\begin{aligned}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{aligned}}

เขียนสมการเพื่อเพิ่มเติมตัวแปรช่วย ได้ดังนี้

{\begin{aligned}Z-c_{1}x_{1}-c_{2}x_{2}-c_{3}x_{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{aligned}}

ตัวแปรที่เพิ่มเข้ามา แก้

ตัวแปรแบบ 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. สร้างตารางซิมเพล็กซ์ดังนี้

	$Z$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$	$x_{6}$	$b$
$Z$	$1$	$-c_{1}$	$-c_{2}$	$-c_{3}$	$0$	$0$	$0$	$0$
$x_{4}$	$0$	$a_{11}$	$a_{12}$	$a_{13}$	$1$	$0$	$0$	$b_{1}$
$x_{5}$	$0$	$a_{21}$	$a_{22}$	$a_{23}$	$0$	$1$	$0$	$b_{2}$
$x_{6}$	$0$	$a_{31}$	$a_{32}$	$a_{33}$	$0$	$0$	$1$	$b_{3}$

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{aligned}2x_{1}+3x_{2}&\leq 100\\4x_{1}+2x_{2}&\leq 120\\x_{1},x_{2}&\geq 0\end{aligned}}

สามารถเขียนเป็นรูปแบบมาตรฐานได้ดังนี้

ค่ามากที่สุด $Z-6x_{1}-4x_{2}=0$

จากข้อจำกัด

{\begin{aligned}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{aligned}}

นำรูปแบบมาตรฐานที่ได้ไปสร้างตารางซิมเพล็กซ์ ได้ดังนี้


	$Z$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$b$
$Z$	$1$	$-6$	$-4$	$0$	$0$	$0$
$x_{3}$	$0$	$2$	$3$	$1$	$0$	$100$
$x_{4}$	$0$	$4$	$2$	$0$	$1$	$120$

พิจารณาแถวแรก $Z$ ค่าสัมประสิทธิ์ที่มีค่าน้อยสุด คือ $-6$ จึงเลือก $x_{1}$ เป็นตัวแปรขาเข้า จากนั้นพิจารณาอัตราส่วนของค่า $b$ กับสัมประสิทธิ์ของตัวแปรขาเข้า จะได้ว่า แถวที่ $x_{3}$ มีอัตราส่วนเป็น ${\frac {100}{2}}=50$ และแถวที่ $x_{4}$ มีอัตราส่วนเป็น ${\frac {120}{4}}=30$ ดังนั้นจึงเลือก $x_{4}$ เป็นตัวแปรขาออก

เปลี่ยนให้ $x_{1}$ เป็นตัวแปรมูลฐาน โดยแลกที่กับ $x_{4}$ ด้วยวิธีการดำเนินการตามแถว จะได้ตารางซิมเพล็กซ์ ดังนี้

{\begin{aligned}R_{3}&:={\frac {1}{4}}R_{3}\\R_{2}&:=-2R_{3}+R_{2}\\R_{1}&:=6R_{3}+R_{1}\end{aligned}}


	$Z$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$b$
$Z$	$1$	$0$	$-1$	$0$	${\frac {3}{2}}$	$180$
$x_{3}$	$0$	$0$	$2$	$1$	$-{\frac {1}{2}}$	$40$
$x_{1}$	$0$	$1$	${\frac {1}{2}}$	$0$	${\frac {1}{4}}$	$30$

พิจารณาแถวแรก $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{aligned}R_{2}&:={\frac {1}{2}}R_{2}\\R_{3}&:=-{\frac {1}{2}}R_{2}+R_{3}\\R_{1}&:=R_{2}+R_{1}\end{aligned}}

	$Z$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$b$
$Z$	$1$	$0$	$0$	${\frac {1}{2}}$	${\frac {5}{4}}$	$200$
$x_{2}$	$0$	$0$	$1$	${\frac {1}{2}}$	$-{\frac {1}{4}}$	$20$
$x_{1}$	$0$	$1$	$0$	$-{\frac {1}{4}}$	${\frac {3}{8}}$	$20$

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

$x_{1}=20,\ x_{2}=20,\$ ค่ามากที่สุดของ $Z=200$

ประสิทธิภาพ แก้

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

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

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

เนื้อหา

บทนำ แก้

รูปมาตรฐาน แก้

ตัวแปรที่เพิ่มเข้ามา แก้

ขั้นตอนวิธี แก้

วิธีการ แก้

ตัวอย่าง แก้

ประสิทธิภาพ แก้

อ้างอิง แก้