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

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

บทนำ

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

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

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

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

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

\begin{matrix} 4 x_{1} + 2 x_{2} & \leq 16 \\ x_{1} + 2 x_{2} & \leq 8 \\ x_{1} + x_{2} & \leq 5 \\ x_{1} \geq 0, x_{2} & \geq 0 \end{matrix}

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

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

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

\begin{matrix} 4 x_{1} + 2 x_{2} + s_{1} & \leq 16 \\ x_{1} + 2 x_{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{matrix}

รูปมาตรฐาน

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

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

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

\begin{matrix} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} & \leq b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} & \leq b_{2} \\ ⋮ \\ a_{n 1} x_{1} + a_{n 2} x_{2} + \dots + a_{n n} x_{n} & \leq b_{n} \\ x_{1} \geq 0, x_{2} \geq 0, \dots, x_{n} & \geq 0 \end{matrix}

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

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

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

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

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

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

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

ตัวแปรแบบ Slack

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

จากข้อจำกัด $7 x_{1} + 34 x_{2} \leq 125$ สามารถเขียนเป็น $7 x_{1} + 34 x_{2} + x_{3} = 125$ เมื่อ $x_{3} \geq 0$

ตัวแปรแบบ Surplus

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

จากข้อจำกัด $7 x_{1} + 34 x_{2} \geq 125$ สามารถเขียนเป็น $7 x_{1} + 34 x_{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 = 6 x_{1} + 4 x_{2}$

จากข้อจำกัด

\begin{matrix} 2 x_{1} + 3 x_{2} & \leq 100 \\ 4 x_{1} + 2 x_{2} & \leq 120 \\ x_{1}, x_{2} & \geq 0 \end{matrix}

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

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

จากข้อจำกัด

\begin{matrix} 2 x_{1} + 3 x_{2} + x_{3} & \leq 100 \\ 4 x_{1} + 2 x_{2} + x_{4} & \leq 120 \\ x_{1}, x_{2}, x_{3}, x_{4} & \geq 0 \end{matrix}

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


	$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{matrix} R_{3} & : = \frac{1}{4} R_{3} \\ R_{2} & : = - 2 R_{3} + R_{2} \\ R_{1} & : = 6 R_{3} + R_{1} \end{matrix}


	$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{matrix} R_{2} & : = \frac{1}{2} R_{2} \\ R_{3} & : = - \frac{1}{2} R_{2} + R_{3} \\ R_{1} & : = R_{2} + R_{1} \end{matrix}

	$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 ได้เสนอตัวอย่างที่ที่แสดงให้เห็นว่าในกรณีเลวร้ายที่สุด ประสิทธิภาพการทำงานของขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นเอกซ์โพเนนเชียล ตั้งแต่นั้นมาการกระทำหรือการดำเนินการด้วยขั้นตอนวิธีนี้ก็ถูกแสดงว่าเป็นขั้นตอนวิธีที่มีประสิทธิภาพที่แย่

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

อ้างอิง

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

เนื้อหา

บทนำ

รูปมาตรฐาน

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

ขั้นตอนวิธี

วิธีการ

ตัวอย่าง

ประสิทธิภาพ

อ้างอิง

รายการนำทางไซต์

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

บทนำ

รูปมาตรฐาน

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

ขั้นตอนวิธี

วิธีการ

ตัวอย่าง

ประสิทธิภาพ

อ้างอิง

รายการนำทางไซต์

ค้นหา