ขั้นตอนวิธีซิมเพล็กซ์ (อังกฤษ: simplex algorithm) หรือ วิธีซิมเพล็กซ์ (อังกฤษ: simplex method) จะอาศัยหลักการของเมทริกซ์เข้าช่วยในการหาผลลัพธ์ที่เหมาะสมที่สุด ซึ่งจะทำให้เห็นถึงการเปลี่ยนแปลงของตัวแปรในแต่ละขั้นตอนอย่างมีเหตุผล และเปลี่ยนแปลงไปในทางที่จะนำมาซึ่งผลลัพธ์ที่โมเดลทางคณิตศาสตร์ต้องการ
การแก้ปัญหาโปรแกรมเชิงเส้น หรือ กำหนดการเชิงเส้น (Linear programming) สำหรับโมเดลคณิตศาสตร์ที่มีตัวแปรไม่มาก เราก็สามารถหาคำตอบได้ไม่ยากนัก แต่หากตัวแปรมีมากขึ้น ก็จำเป็นต้องหาวิธีการอื่นเข้ามาช่วยในการหาคำตอบของโมเดล ซึ่งวิธีซิมเพล็กซ์เป็นวิธีการหนึ่งที่ให้ผลดี และเข้าใจได้ง่าย
ขั้นตอนวิธีซิมเพล็กซ์ เป็นวีธีการของ จอร์จ แดนท์ซิก (George Dantzig) ที่ได้รับความนิยมอย่างมากในการแก้ปัญหาโปรแกรมเชิงเส้น ซึ่งชื่อของขั้นตอนวิธีนี้ มาจากแนวคิดของ ซิมเพล็กซ์ นั่นเอง
วิธีซิมเพล็กซ์เป็นวิธีที่มีประสิทธิภาพมากในการแก้ปัญหากำหนดการเชิงเส้น (Linear programming) ซึ่งเป็นกระบวนการทางพีชคณิตที่ประกอบด้วยการกระทำซ้ำ ๆ กันเพื่อให้ได้คำตอบที่ดีที่สุด ยกตัวอย่างเช่น
ค่าที่มากที่สุดของ
ภายใต้เงื่อนไข
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41dcb0400cc0c6034810e2b66e43d4a4a48280ff)
ปัญหาในลักษณะเช่นนี้จะสามารถใช้วิธีซิมเพล็กซ์ในการหาคำตอบได้ โดยจำเป็นจะต้องเปลี่ยนปัญหาที่กำหนดให้อยู่ในรูปมาตรฐาน (Standard Form) โดยจะต้องแปลงอสมการของปัญหาให้เป็นสมการ ซึ่งจะมีการเพิ่มตัวแปรเข้าไปในแต่ละอสมการเรียกว่าตัวแปรแบบ Slack หรือ Surplus ดังนั้น เราจะเขียนตัวอย่างข้างต้นได้ใหม่เป็น
ค่าที่มากที่สุดของ
ภายใต้เงื่อนไข
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec5d63debea037d2aaac0ea174d0b06d9c2923e1)
รูปมาตรฐาน[แก้]
การจะแปลงกำหนดการเชิงเส้นให้อยู่ในรูปแบบมาตรฐาน สามารถทำได้โดยการแปลง อสมการที่มีเครื่องหมาย
ให้อยู่ในรูปของสมการ ซึ่งเราจะเพิ่มตัวแปรเข้าไปในสมการที่มีค่ามากกว่าหรือเท่ากับ 0 และย้ายตัวแปรทั้งหมดไว้ด้านขวา ส่วนตัวเลขที่เหลือไว้ด้านซ้าย ซึ่งรูปมาตรฐานจะอยู่ในรูป
ค่าที่มากที่สุดของ
ภายใต้เงื่อนไข
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36dd78233a8d0f2576af4d0edca27f3a763fb98d)
จากรูปแบบโมเดลคณิตศาสตร์ของโปรแกรมเชิงเส้น
ค่าที่มากที่สุดของ
ภายใต้เงื่อนไข
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c1848b44ccd17505196b10db409836334dee53a)
เขียนสมการเพื่อเพิ่มเติมตัวแปรช่วย ได้ดังนี้
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4835ada6b0a6245f508eecd3aa98e78d8d29618)
ตัวแปรที่เพิ่มเข้ามา[แก้]
ในอสมการที่มี
โดยทางซ้ายเป็นการดำเนินการของตัวแปร และทางขวาเป็นค่าตัวเลขตัวหนึ่ง เราสามารถเพิ่มตัวแปรแบบ Slack เข้าไปทางซ้ายได้เพื่อเป็นตัวแทนเพิ่มค่าให้เท่ากับค่าทางขวา เช่น
จากข้อจำกัด
สามารถเขียนเป็น
เมื่อ
ในอสมการที่มี
โดยทางซ้ายเป็นการดำเนินการของตัวแปร และทางขวาเป็นค่าตัวเลขตัวหนึ่ง เราสามารถเพิ่มตัวแปรแบบ Surplus เข้าไปทางซ้ายได้เพื่อเป็นตัวแทนลดค่าให้เท่ากับค่าทางขวา เช่น
จากข้อจำกัด
สามารถเขียนเป็น
เมื่อ
ขั้นตอนวิธี[แก้]
วิธีการต่อไปนี้จะเป็นการดำเนินการตามขั้นตอนวิธีซิมเพล็กซ์ เพื่อหาผลเฉลยที่มีค่ามากที่สุด แต่หากต้องการหาผลเฉลยที่มีค่าน้อยสุดสามารถทำได้โดย ค่าน้อยสุดของ
ค่ามากสุดของ
วิธีการ[แก้]
1. จัดรูป กำหนดการเชิงเส้น ให้อยู่ในรูปมาตรฐาน
2. สร้างตารางซิมเพล็กซ์ดังนี้
|
![{\displaystyle Z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1cc6b75e09a8aa3f04d8584b11db534f88fb56bd) |
![{\displaystyle x_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8788bf85d532fa88d1fb25eff6ae382a601c308) |
![{\displaystyle x_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7af1b928f06e4c7e3e8ebfd60704656719bd766) |
![{\displaystyle x_{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/766d09a498699be10e276ad49145c921f8cbe335) |
![{\displaystyle x_{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb828766e82e496666b179ff70d8e2fd24a79e5f) |
![{\displaystyle x_{5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61b358d0e5e47692d8e6bf61c74130b612a7f919) |
![{\displaystyle x_{6}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/315276aae6e84d8cbb6f4e165a29dbe51f323307) |
|
![{\displaystyle Z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1cc6b75e09a8aa3f04d8584b11db534f88fb56bd) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle -c_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f5c9b64c97b767ecce20a82a00adf256abca48e) |
![{\displaystyle -c_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0bac847a29cb1033acec319b2a3fedfa3690b8b) |
![{\displaystyle -c_{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf9968103de8f4de3e937f8a5616c04dceccdd26) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
|
![{\displaystyle x_{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb828766e82e496666b179ff70d8e2fd24a79e5f) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle a_{11}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/411c26881c752d514e61bfdd5eb8463c6e808202) |
![{\displaystyle a_{12}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e062aea942fa88bbd0aa72d26f8fc011b323bf5e) |
![{\displaystyle a_{13}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de4f86c305ff1b04fabb1cddcedd192853d6815c) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
|
![{\displaystyle x_{5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61b358d0e5e47692d8e6bf61c74130b612a7f919) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle a_{21}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/372531d1d09885784f3430660f8654b0d48eb394) |
![{\displaystyle a_{22}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7a66fac4dcd116c0dca38bd6cd9a805f62b69f4) |
![{\displaystyle a_{23}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e214e4d1b4dcc0f3909e915fd69012c5bd1b7b7b) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
|
![{\displaystyle x_{6}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/315276aae6e84d8cbb6f4e165a29dbe51f323307) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle a_{31}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c322ba2770ed3e56043ffd0247fb8b9d3aa63aa) |
![{\displaystyle a_{32}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7963f39d82cffee051a6599222e1ab49aff45c0a) |
![{\displaystyle a_{33}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7970738c75edb91b81f6be1c4d5f7facd2637a3) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
|
3. เลือกตัวแปรขาเข้า (entering variable) คือการเลือกตัวแปรที่ไม่เป็นตัวแปรมูลฐาน (non-basic variable) ให้เป็นตัวแปรมูลฐาน (basic variable) โดยดูจากสัมประสิทธิ์ของตัวแปรในสมการเป้าหมาย (แถว Z) ที่ติดลบมากที่สุด แต่ถ้าสัมประสิทธิ์ของตัวแปรทุกตัวเป็นบวกหรือศูนย์แล้ว แสดงว่าถึงจุดที่เหมาะสม (optimal solution) ไม่ต้องทำต่อไปอีก
4. เลือกตัวแปรขาออก (leaving variable) ด้วยการหาอัตราส่วนของค่าผลลัพธ์กับสัมประสิทธิ์ของตัวแปรเข้าที่เลือกไว้ในขั้นที่ 3 (ไม่ต้องคำนึงถึงสัมประสิทธิ์ที่เป็นลบหรือศูนย์) เลือกอัตราส่วนต่ำสุดของตัวแปรมูลฐาน อยู่ที่ตัวใดแสดงว่าตัวนั้นจะเป็นตัวแปรออก
5. เปลี่ยนตัวแปรมูลฐาน ด้วยการแลกที่กันระหว่างตัวแปรขาเข้าและตัวแปรขาออก ด้วยการคำนวณโดยใช้การดำเนินการตามแถว (row operation)
6. ให้กลับไปทำขั้นที่ 3 - 5 ต่อไปเรื่อย ๆ จนกระทั่งถึงจุดที่เหมาะสมแล้ว
ตัวอย่าง[แก้]
ค่ามากที่สุด
จากข้อจำกัด
![{\displaystyle {\begin{aligned}2x_{1}+3x_{2}&\leq 100\\4x_{1}+2x_{2}&\leq 120\\x_{1},x_{2}&\geq 0\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30ca22771da900120b1fd9e8971f7b8597d8875a)
สามารถเขียนเป็นรูปแบบมาตรฐานได้ดังนี้
ค่ามากที่สุด
จากข้อจำกัด
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74912457fa81120c25b486ad1e21be29174a2e62)
นำรูปแบบมาตรฐานที่ได้ไปสร้างตารางซิมเพล็กซ์ ได้ดังนี้
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
พิจารณาแถวแรก
ค่าสัมประสิทธิ์ที่มีค่าน้อยสุด คือ
จึงเลือก
เป็นตัวแปรขาเข้า จากนั้นพิจารณาอัตราส่วนของค่า
กับสัมประสิทธิ์ของตัวแปรขาเข้า จะได้ว่า แถวที่
มีอัตราส่วนเป็น
และแถวที่
มีอัตราส่วนเป็น
ดังนั้นจึงเลือก
เป็นตัวแปรขาออก
เปลี่ยนให้
เป็นตัวแปรมูลฐาน โดยแลกที่กับ
ด้วยวิธีการดำเนินการตามแถว จะได้ตารางซิมเพล็กซ์ ดังนี้
![{\displaystyle {\begin{aligned}R_{3}&:={\frac {1}{4}}R_{3}\\R_{2}&:=-2R_{3}+R_{2}\\R_{1}&:=6R_{3}+R_{1}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21ab5830a6b4cf6f2d46b885e9b992f0fd499eca)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
พิจารณาแถวแรก
ค่าสัมประสิทธิ์ที่มีค่าน้อยสุด คือ
จึงเลือก
เป็นตัวแปรขาเข้า จากนั้นพิจารณาอัตราส่วนของค่า
กับสัมประสิทธิ์ของตัวแปรขาเข้า จะได้ว่า แถวที่
มีอัตราส่วนเป็น
และแถวที่
มีอัตราส่วนเป็น
ดังนั้นจึงเลือก
เป็นตัวแปรขาออก
เปลี่ยนให้
เป็นตัวแปรมูลฐาน โดยแลกที่กับ
ด้วยวิธีการดำเนินการตามแถว จะได้ตารางซิมเพล็กซ์ ดังนี้
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7410270e9bb3fe33ae629d08b32a7137e0c3a677)
|
![{\displaystyle Z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1cc6b75e09a8aa3f04d8584b11db534f88fb56bd) |
![{\displaystyle x_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8788bf85d532fa88d1fb25eff6ae382a601c308) |
![{\displaystyle x_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7af1b928f06e4c7e3e8ebfd60704656719bd766) |
![{\displaystyle x_{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/766d09a498699be10e276ad49145c921f8cbe335) |
![{\displaystyle x_{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb828766e82e496666b179ff70d8e2fd24a79e5f) |
|
![{\displaystyle Z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1cc6b75e09a8aa3f04d8584b11db534f88fb56bd) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle {\frac {1}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a11cfb2fdb143693b1daf78fcb5c11a023cb1c55) |
![{\displaystyle {\frac {5}{4}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52f3e79a6a2f8288b72472a4649e78fba98f9290) |
|
![{\displaystyle x_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7af1b928f06e4c7e3e8ebfd60704656719bd766) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle {\frac {1}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a11cfb2fdb143693b1daf78fcb5c11a023cb1c55) |
![{\displaystyle -{\frac {1}{4}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/204c4acf21e018ddc2a68336f6332fb511c49862) |
|
![{\displaystyle x_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8788bf85d532fa88d1fb25eff6ae382a601c308) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle -{\frac {1}{4}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/204c4acf21e018ddc2a68336f6332fb511c49862) |
![{\displaystyle {\frac {3}{8}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6fe52a498e9788c548326304098d2122ca4645d) |
|
เมื่อพิจารณาตารางซิมเพล็กซ์ก็จะเห็นว่า สัมประสิทธิ์ในสมการเป้าหมาย (พิจารณาแถว Z) มีค่าไม่ติดลบทั้งหมด ดังนั้นเราก็ได้ผลเฉลยที่เหมาะสมที่สุดแล้วดังนี้
ค่ามากที่สุดของ
ประสิทธิภาพ[แก้]
ขั้นตอนวิธีซิมเพล็กซ์ เป็นวิธีการที่มีประสิทธิภาพในทางปฏิบัติ และได้รับการพัฒนามากกว่าวิธีที่คิดค้นขึ้นมาก่อนหน้า อย่างไรก็ตามในปี พ.ศ. 2515 Klee และ Minty ได้เสนอตัวอย่างที่ที่แสดงให้เห็นว่าในกรณีเลวร้ายที่สุด ประสิทธิภาพการทำงานของขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นเอกซ์โพเนนเชียล ตั้งแต่นั้นมาการกระทำหรือการดำเนินการด้วยขั้นตอนวิธีนี้ก็ถูกแสดงว่าเป็นขั้นตอนวิธีที่มีประสิทธิภาพที่แย่
การวิเคราะห์เชิงปริมาณและการสังเกตว่าขั้นตอนวิธีซิมเพล็กซ์มีประสิทธิภาพในทางปฏิบัติแม้ว่าจะมีใช้เวลาเป็นเอกซ์โพแนนเชียลในกรณีที่เลวร้ายที่สุดก็ตาม และได้นำไปสู่การพัฒนาที่จะวัดประสิทธิภาพในรูปแบบอื่น ซึ่งจริงๆ แล้ว ขั้นตอนวิธีซิมเพล็กซ์จะใช้เวลาเป็นโพลิโนเมียลในกรณีเฉลี่ยทั่วไป ภายใต้การแจกแจงความน่าจะเป็น ซึ่งความแม่นยำของประสิทธิภาพในเชิงเฉลี่ยนี้จะขึ้นอยู่กับการเลือกการแจกแจงความน่าเป็นของโมเดลทางคณิตศาสตร์ และการนำเสนออื่นๆ ได้แสดงให้เห็นว่ากรณีที่เลวร้ายที่สุดสำหรับขั้นตอนวิธีซิมเพล็กซ์นั้นมีผลน้อยมากต่อประสิทธิภาพโดยรวม
อ้างอิง[แก้]