ในการเพิ่มประสิทธิภาพทางคณิตศาสตร์อัลกอริทึมซิมเพล็กซ์ของDantzig (หรือวิธีซิมเพล็กซ์ ) เป็นอัลกอริทึมสำหรับ การ เขียนโปรแกรมเชิงเส้น^{[ 1 ]}

ชื่อของอัลกอริทึมนี้ได้มาจากแนวคิดของซิมเพล็กซ์และได้รับการเสนอแนะโดยTS Motzkin [ ^{2 ] จริงๆ}แล้วไม่ได้ใช้ซิมเพล็กซ์ในวิธีการนี้ แต่การตีความอย่างหนึ่งคือมันทำงานกับกรวยซิมเพล็กซ์และสิ่งเหล่านี้จะกลายเป็นซิมเพล็กซ์ที่เหมาะสมด้วยข้อจำกัดเพิ่มเติม^{[ 3 ] [ 4 ] [ 5 ] [ 6 ]}กรวยซิมเพล็กซ์ที่กล่าวถึงคือมุม (เช่น บริเวณใกล้เคียงของจุดยอด) ของวัตถุทางเรขาคณิตที่เรียกว่าโพลีโทปรูปร่างของโพลีโทปนี้ถูกกำหนดโดยข้อจำกัดที่ใช้กับฟังก์ชันเป้าหมาย

จอร์จ แดนท์ซิกทำงานเกี่ยวกับการวางแผนวิธีการสำหรับกองทัพอากาศสหรัฐฯ ในช่วงสงครามโลกครั้งที่สองโดยใช้เครื่องคิดเลขตั้งโต๊ะในปี 1946 เพื่อนร่วมงานของเขาได้ท้าทายให้เขาสร้างระบบอัตโนมัติสำหรับกระบวนการวางแผนเพื่อเบี่ยงเบนความสนใจของเขาจากการรับงานอื่น แดนท์ซิกได้กำหนดปัญหาเป็นอสมการเชิงเส้นโดยได้รับแรงบันดาลใจจากงานของวาสซิลี เลอนทิฟอย่างไรก็ตาม ในเวลานั้นเขาไม่ได้รวมวัตถุประสงค์ไว้ในการกำหนดปัญหาของเขา หากไม่มีวัตถุประสงค์ วิธีแก้ปัญหาที่เป็นไปได้จำนวนมากก็เป็นไปได้ ดังนั้น เพื่อหาวิธีแก้ปัญหาที่เป็นไปได้ "ที่ดีที่สุด" จึงต้องใช้ "กฎพื้นฐาน" ที่กำหนดโดยกองทัพ ซึ่งอธิบายว่าเป้าหมายสามารถบรรลุได้อย่างไร แทนที่จะระบุเป้าหมายเอง ความเข้าใจหลักของแดนท์ซิกคือการตระหนักว่ากฎพื้นฐานส่วนใหญ่สามารถแปลเป็นฟังก์ชันวัตถุประสงค์เชิงเส้นที่ต้องทำให้สูงสุดได้^{[ 7 ]}การพัฒนาวิธีการซิมเพล็กซ์เป็นการวิวัฒนาการและเกิดขึ้นในช่วงระยะเวลาประมาณหนึ่งปี^{[ 8 ]}

หลังจากที่ Dantzig รวมฟังก์ชันวัตถุประสงค์เป็นส่วนหนึ่งของการกำหนดสูตรของเขาในช่วงกลางปี ​​1947 ปัญหาดังกล่าวก็สามารถแก้ไขได้ทางคณิตศาสตร์มากขึ้น Dantzig ตระหนักว่าหนึ่งในปัญหาที่ยังแก้ไม่ตกซึ่งเขาเข้าใจผิดว่าเป็นงานบ้านในชั้นเรียนของศาสตราจารย์Jerzy Neyman (และต่อมาได้แก้สำเร็จ) นั้นสามารถนำไปใช้ในการหาอัลกอริทึมสำหรับโปรแกรมเชิงเส้นได้ ปัญหานี้เกี่ยวข้องกับการหาการมีอยู่ของตัวคูณลากรางจ์สำหรับโปรแกรมเชิงเส้นทั่วไปเหนือตัวแปรต่อเนื่อง ซึ่งแต่ละตัวมีค่าอยู่ระหว่างศูนย์ถึงหนึ่ง และเป็นไปตามข้อจำกัดเชิงเส้นที่แสดงในรูปแบบของปริพันธ์เลเบส Dantzig ได้ตีพิมพ์ "งานบ้าน" ของเขาในภายหลังในรูปแบบวิทยานิพนธ์เพื่อรับปริญญาเอก เรขาคณิตคอลัมน์ที่ใช้ในวิทยานิพนธ์นี้ทำให้ Dantzig เข้าใจว่าวิธีการซิมเพล็กซ์จะมีประสิทธิภาพมาก^{[ 9 ]}

อัลกอริทึมซิมเพล็กซ์ทำงานกับโปรแกรมเชิงเส้นในรูปแบบมาตรฐาน

เพิ่มสูงสุด${\textstyle \mathbf {c^{T}} \mathbf {x} }$

ขึ้นอยู่กับและ${\displaystyle A\mathbf {x} \leq \mathbf {b} }$${\displaystyle \mathbf {x} \geq 0}$

โดยที่คือสัมประสิทธิ์ของฟังก์ชันเป้าหมายคือเมทริกซ์ทรานสโพสที่มีจุดแทนตำแหน่งและคือตัวแปรของปัญหาคือ เมทริกซ์ขนาด p × nและมีกระบวนการที่ตรงไปตรงมาในการแปลงโปรแกรมเชิงเส้นใดๆ ให้เป็นรูปแบบมาตรฐาน ดังนั้นการใช้โปรแกรมเชิงเส้นในรูปแบบนี้จึงไม่ทำให้สูญเสียความทั่วไปแต่อย่างใด ${\displaystyle \mathbf {c} =(c_{1},\,\dots ,\,c_{n})}$${\displaystyle (\cdot )^{\mathrm {T} }}$${\displaystyle \mathbf {x} =(x_{1},\,\dots ,\,x_{n})}$${\displaystyle A}$${\displaystyle \mathbf {b} =(b_{1},\,\dots ,\,b_{p})}$

ในทางเรขาคณิตบริเวณที่เป็นไปได้ซึ่งกำหนดโดยค่าทั้งหมดของที่ทำให้และเป็นรูปทรงหลายเหลี่ยมนูน (ซึ่งอาจไม่มีขอบเขต) จุดสุดขั้วหรือจุดยอดของรูปทรงหลายเหลี่ยมนี้เรียกว่าคำตอบที่เป็นไปได้พื้นฐาน (Basic Feasible Solution: BFS) ${\displaystyle \mathbf {x} }$${\textstyle A\mathbf {x} \leq \mathbf {b} }$${\displaystyle \forall i,x_{i}\geq 0}$

สามารถแสดงได้ว่าสำหรับโปรแกรมเชิงเส้นในรูปแบบมาตรฐาน หากฟังก์ชันวัตถุประสงค์มีค่าสูงสุดบนพื้นที่ที่เป็นไปได้ ฟังก์ชันนั้นจะมีค่าดังกล่าวบนจุดสุดขั้วอย่างน้อยหนึ่งจุด^{[ 10 ]}ซึ่งในตัวมันเองจะลดปัญหาให้เหลือการคำนวณแบบจำกัด เนื่องจากมีจำนวนจุดสุดขั้วที่จำกัด แต่จำนวนจุดสุดขั้วนั้นมีขนาดใหญ่เกินกว่าจะจัดการได้ ยกเว้นโปรแกรมเชิงเส้นขนาดเล็กที่สุด^{[ 11 ]}

นอกจากนี้ยังสามารถแสดงได้ว่า หากจุดสุดขั้วไม่ใช่จุดสูงสุดของฟังก์ชันเป้าหมาย จะมีขอบที่ประกอบด้วยจุดนั้น โดยที่ค่าของฟังก์ชันเป้าหมายจะเพิ่มขึ้นอย่างต่อเนื่องบนขอบที่เคลื่อนห่างจากจุดนั้น^{[ 12 ]}หากขอบนั้นมีค่าจำกัด ขอบนั้นจะเชื่อมต่อกับจุดสุดขั้วอื่นที่ฟังก์ชันเป้าหมายมีค่ามากกว่า มิฉะนั้น ฟังก์ชันเป้าหมายจะไม่มีขอบเขตบนขอบ และโปรแกรมเชิงเส้นจะไม่มีคำตอบ อัลกอริทึมซิมเพล็กซ์ใช้ความเข้าใจนี้โดยการเดินไปตามขอบของรูปหลายเหลี่ยมไปยังจุดสุดขั้วที่มีค่าฟังก์ชันเป้าหมายมากขึ้นเรื่อยๆ กระบวนการนี้จะดำเนินต่อไปจนกว่าจะถึงค่าสูงสุด หรือจนกว่าจะถึงขอบที่ไม่มีขอบเขต (สรุปได้ว่าปัญหาไม่มีคำตอบ) อัลกอริทึมจะสิ้นสุดลงเสมอเนื่องจากจำนวนจุดยอดในรูปหลายเหลี่ยมมีค่าจำกัด ยิ่งไปกว่านั้น เนื่องจากเรากระโดดระหว่างจุดยอดในทิศทางเดียวกันเสมอ (ทิศทางของฟังก์ชันเป้าหมาย) เราจึงหวังว่าจำนวนจุดยอดที่เยี่ยมชมจะมีน้อย^{[ 12 ]}

การแก้ปัญหาโปรแกรมเชิงเส้นจะดำเนินการในสองขั้นตอน ในขั้นตอนแรก ซึ่งเรียกว่าเฟสที่ 1 จะค้นหาจุดเริ่มต้นสุดขั้ว ขึ้นอยู่กับลักษณะของโปรแกรม จุดนี้อาจเป็นจุดง่ายๆ แต่โดยทั่วไปแล้วสามารถแก้ไขได้โดยการใช้อัลกอริธึมซิมเพล็กซ์กับโปรแกรมดั้งเดิมที่ได้รับการแก้ไข ผลลัพธ์ที่เป็นไปได้ของเฟสที่ 1 คือ การพบวิธีแก้ปัญหาพื้นฐานที่เป็นไปได้ หรือพื้นที่ที่เป็นไปได้ว่างเปล่า ในกรณีหลัง โปรแกรมเชิงเส้นจะเรียกว่าไม่สามารถแก้ไขได้ในขั้นตอนที่สอง เฟสที่ 2 จะใช้อัลกอริธึมซิมเพล็กซ์โดยใช้วิธีแก้ปัญหาพื้นฐานที่เป็นไปได้ที่พบในเฟสที่ 1 เป็นจุดเริ่มต้น ผลลัพธ์ที่เป็นไปได้จากเฟสที่ 2 คือ วิธีแก้ปัญหาพื้นฐานที่เป็นไปได้ที่ดีที่สุด หรือขอบอนันต์ที่ฟังก์ชันวัตถุประสงค์ไม่มีขอบเขตบน^{[ 13 ] [ 14 ] [ 15 ]}

การแปลงโปรแกรมเชิงเส้นให้เป็นโปรแกรมในรูปแบบมาตรฐานสามารถทำได้ดังต่อไปนี้^{[ 16 ]}ขั้นแรก สำหรับแต่ละตัวแปรที่มีขอบเขตล่างที่ไม่ใช่ 0 จะมีการแนะนำตัวแปรใหม่ที่แสดงถึงความแตกต่างระหว่างตัวแปรและขอบเขต จากนั้นสามารถกำจัดตัวแปรเดิมได้โดยการแทนที่ ตัวอย่างเช่น เมื่อกำหนดข้อจำกัด

${\displaystyle x_{1}\geq 5}$

มีการแนะนำ ตัวแปรใหม่โดย ${\displaystyle y_{1}}$

${\displaystyle {\begin{aligned}y_{1}=x_{1}-5\\x_{1}=y_{1}+5\end{aligned}}}$

สมการที่สองอาจใช้เพื่อกำจัดออกจากโปรแกรมเชิงเส้น ด้วยวิธีนี้ ข้อจำกัดขอบล่างทั้งหมดสามารถเปลี่ยนเป็นข้อจำกัดที่ไม่เป็นลบได้ ${\displaystyle x_{1}}$

ประการที่สอง สำหรับข้อจำกัดอสมการที่เหลืออยู่แต่ละข้อ จะมีการแนะนำตัวแปรใหม่ที่เรียกว่าตัวแปรผ่อนปรนเพื่อเปลี่ยนข้อจำกัดให้เป็นข้อจำกัดสมการ ตัวแปรนี้แสดงถึงความแตกต่างระหว่างสองด้านของอสมการ และถือว่ามีค่าไม่เป็นลบ ตัวอย่างเช่น อสมการ

${\displaystyle {\begin{aligned}x_{2}+2x_{3}&\leq 3\\-x_{4}+3x_{5}&\geq 2\end{aligned}}}$

ถูกแทนที่ด้วย

${\displaystyle {\begin{aligned}x_{2}+2x_{3}+s_{1}&=3\\-x_{4}+3x_{5}-s_{2}&=2\\s_{1},\,s_{2}&\geq 0\end{aligned}}}$

การดำเนินการทางพีชคณิตกับอสมการในรูปแบบนี้ทำได้ง่ายกว่ามาก ในอสมการที่มี ≥ ปรากฏอยู่ เช่น อสมการที่สอง ผู้เขียนบางคนเรียกตัวแปรที่นำมาใช้ว่า aส่วน เกิน ผันแปร

ประการที่สาม ตัวแปรที่ไม่จำกัดแต่ละตัวจะถูกกำจัดออกจากโปรแกรมเชิงเส้น สามารถทำได้สองวิธี วิธีแรกคือการแก้หาค่าตัวแปรในสมการใดสมการหนึ่งที่ตัวแปรนั้นปรากฏอยู่ แล้วจึงกำจัดตัวแปรนั้นโดยการแทนค่า อีกวิธีหนึ่งคือการแทนที่ตัวแปรด้วยผลต่างของตัวแปรที่จำกัดสองตัว ตัวอย่างเช่น ถ้าเป็นตัวแปรที่ไม่จำกัด ให้เขียนว่า ${\displaystyle z_{1}}$

${\displaystyle {\begin{aligned}&z_{1}=z_{1}^{+}-z_{1}^{-}\\&z_{1}^{+},\,z_{1}^{-}\geq 0\end{aligned}}}$

สมการนี้สามารถใช้เพื่อกำจัดออกจากโปรแกรมเชิงเส้น ได้${\displaystyle z_{1}}$

เมื่อกระบวนการนี้เสร็จสมบูรณ์ พื้นที่ที่เป็นไปได้จะมีรูปแบบดังนี้

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} ,\,\forall \ x_{i}\geq 0}$

นอกจากนี้ การสมมติว่าอันดับของคือจำนวนแถว ก็เป็นประโยชน์เช่นกัน ซึ่งจะไม่ทำให้สูญเสียความเป็นทั่วไป เนื่องจากมิฉะนั้น ระบบจะมีสมการที่ซ้ำซ้อนซึ่งสามารถตัดทิ้งได้ หรือระบบจะไม่สอดคล้องกัน และโปรแกรมเชิงเส้นจะไม่มีคำตอบ^{[ 17 ]}${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

โปรแกรมเชิงเส้นในรูปแบบมาตรฐานสามารถแสดงได้ในรูปตารางดังนี้

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {A} &\mathbf {b} \end{bmatrix}}}$

แถวแรกกำหนดฟังก์ชันเป้าหมาย และแถวที่เหลือระบุข้อจำกัด ศูนย์ในคอลัมน์แรกแสดงถึงเวกเตอร์ศูนย์ที่มีมิติเท่ากับเวกเตอร์(ผู้เขียนแต่ละคนใช้ข้อกำหนดที่แตกต่างกันเกี่ยวกับรูปแบบที่แน่นอน) หากสามารถจัดเรียงคอลัมน์ของใหม่เพื่อให้มีเมทริกซ์เอกลักษณ์อันดับ(จำนวนแถวใน) ได้ ตารางนั้นจะเรียกว่าอยู่ใน รูป แบบมาตรฐาน^{[ 18 ]}ตัวแปรที่สอดคล้องกับคอลัมน์ของเมทริกซ์เอกลักษณ์เรียกว่าตัวแปรพื้นฐานในขณะที่ตัวแปรที่เหลือเรียกว่าตัวแปรที่ไม่ใช่พื้นฐานหรือตัวแปรอิสระหากค่าของตัวแปรที่ไม่ใช่พื้นฐานถูกตั้งค่าเป็น 0 ค่าของตัวแปรพื้นฐานจะหาได้ง่ายจากรายการในและวิธีแก้ปัญหานี้เป็นวิธีแก้ปัญหาพื้นฐานที่เป็นไปได้ การตีความทางพีชคณิตในที่นี้คือสัมประสิทธิ์ของสมการเชิงเส้นที่แสดงโดยแต่ละแถวจะเป็น, , หรือตัวเลขอื่น ๆ แต่ละแถวจะมีคอลัมน์ที่มีค่าคอลัมน์ที่มีสัมประสิทธิ์และคอลัมน์ที่เหลือจะมีสัมประสิทธิ์อื่นๆ (ตัวแปรอื่นๆ เหล่านี้แทนตัวแปรที่ไม่ใช่ตัวแปรพื้นฐาน) โดยการกำหนดค่าของตัวแปรที่ไม่ใช่ตัวแปรพื้นฐานให้เป็นศูนย์ เราจะมั่นใจได้ว่าในแต่ละแถว ค่าของตัวแปรที่แสดงด้วย a ในคอลัมน์นั้นจะเท่ากับค่าในแถวนั้น ${\displaystyle \mathbf {b} }$${\displaystyle \mathbf {A} }$${\displaystyle p}$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {b} }$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle 1}$${\displaystyle 1}$${\displaystyle p-1}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle b}$

ในทางกลับกัน เมื่อกำหนดวิธีแก้ปัญหาพื้นฐานที่เป็นไปได้ คอลัมน์ที่สอดคล้องกับตัวแปรที่ไม่เป็นศูนย์สามารถขยายเป็นเมทริกซ์ที่ไม่เอกฐานได้หากตารางที่สอดคล้องกันถูกคูณด้วยส่วนกลับของผลลัพธ์ที่ได้จะเป็นตารางในรูปแบบมาตรฐาน^{[ 19 ]}${\displaystyle B}$${\displaystyle B}$

อนุญาต

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} _{B}^{T}&-\mathbf {c} _{D}^{T}&0\\0&I&\mathbf {D} &{\widehat {\mathbf {b} }}\end{bmatrix}}}$

เป็นตารางในรูปแบบมาตรฐาน โดยที่ สามารถใช้ การแปลงเพิ่มแถวเพิ่มเติมเพื่อลบสัมประสิทธิ์c ออกได้${\displaystyle {\widehat {\mathbf {b} }}=B^{-1}\mathbf {b} }$ทีบี จากฟังก์ชันเป้าหมาย กระบวนการนี้เรียกว่าการกำหนดราคาและส่งผลให้ได้ตารางมาตรฐาน

${\displaystyle {\begin{bmatrix}1&0&-{\bar {\mathbf {c} }}_{D}^{T}&z_{B}\\0&I&\mathbf {D} &{\widehat {\mathbf {b} }}\end{bmatrix}}}$

โดยที่z _Bคือค่าของฟังก์ชันวัตถุประสงค์ที่โซลูชันพื้นฐานที่เป็นไปได้ที่สอดคล้องกัน สัมประสิทธิ์ที่อัปเดตแล้ว หรือที่รู้จักกันในชื่อสัมประสิทธิ์ต้นทุนสัมพัทธ์คืออัตราการเปลี่ยนแปลงของฟังก์ชันวัตถุประสงค์เมื่อเทียบกับตัวแปรที่ไม่ใช่พื้นฐาน^{[ 14 ]}

การดำเนินการทางเรขาคณิตของการย้ายจากคำตอบที่เป็นไปได้พื้นฐานไปยังคำตอบที่เป็นไปได้พื้นฐานที่อยู่ติดกันนั้น ถูกนำมาใช้ ในรูปแบบ ของการดำเนินการแบบ Pivotขั้นแรกเลือกองค์ประกอบ Pivot ที่ไม่เป็นศูนย์ในคอลัมน์ที่ไม่ใช่พื้นฐาน แถวที่มีองค์ประกอบนี้จะ ถูกคูณด้วยส่วนกลับของมันเพื่อเปลี่ยนองค์ประกอบนี้เป็น 1 จากนั้นจะนำผลคูณของแถวนั้นไปบวกกับแถวอื่นๆ เพื่อเปลี่ยนค่าอื่นๆ ในคอลัมน์นั้นให้เป็น 0 ผลลัพธ์คือ ถ้าองค์ประกอบ Pivot อยู่ในแถวrคอลัมน์นั้นจะกลายเป็น คอลัมน์ที่ rของเมทริกซ์เอกลักษณ์ ตัวแปรสำหรับคอลัมน์นี้จะเป็นตัวแปรพื้นฐาน แทนที่ตัวแปรที่สอดคล้องกับ คอลัมน์ที่ rของเมทริกซ์เอกลักษณ์ก่อนการดำเนินการ ในทางปฏิบัติ ตัวแปรที่สอดคล้องกับคอลัมน์ Pivot จะเข้าสู่ชุดของตัวแปรพื้นฐานและเรียกว่าตัวแปรที่เข้ามาและตัวแปรที่ถูกแทนที่ออกจากชุดของตัวแปรพื้นฐานและเรียกว่าตัวแปรที่ออกไปตารางยังคงอยู่ในรูปแบบมาตรฐาน แต่ชุดของตัวแปรพื้นฐานเปลี่ยนไปหนึ่งองค์ประกอบ^{[ 13 ] [ 14 ]}

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

ส่วนต่อไปนี้จะเน้นที่การหาค่าสูงสุดของฟังก์ชันเป้าหมาย หากต้องการค่าต่ำสุดแทน สามารถปรับเปลี่ยนอัลกอริธึมได้โดยการกลับเครื่องหมายของการอ้างอิงถึงฟังก์ชันเป้าหมายทั้งหมด

เนื่องจากตัวแปรป้อนเข้าโดยทั่วไปจะเพิ่มขึ้นจาก 0 ไปเป็นจำนวนบวก ค่าของฟังก์ชันเป้าหมายจะเพิ่มขึ้น (และเข้าใกล้ค่าสูงสุดมากขึ้น) หากอนุพันธ์ (เช่น สัมประสิทธิ์) ของฟังก์ชันเป้าหมายเทียบกับตัวแปรนี้เป็นบวก ดังนั้น จึงควรเลือกคอลัมน์หลักที่มีค่าในแถวเป้าหมาย ( ) ที่สอดคล้องกันในตารางเป็นลบ (หากต้องการลดค่าฟังก์ชันเป้าหมายให้เหลือน้อยที่สุด ควรเลือกคอลัมน์ที่มีค่าในแถวเป้าหมายเป็นบวกแทน) ${\displaystyle {\bar {\mathbf {c} }}^{\mathrm {T} }}$${\displaystyle -{\bar {\mathbf {c} }}^{\mathrm {T} }}$

โดยทั่วไปจะมีคอลัมน์มากกว่าหนึ่งคอลัมน์ที่มีค่าลบในแถววัตถุประสงค์ และการเลือกคอลัมน์ใดที่จะเพิ่มลงในชุดตัวแปรพื้นฐานจะถูกชี้นำโดยกฎการเลือกตัวแปรขาเข้าหลายข้อ[ 20 ^{]เช่นอั}ลกอริทึม Devex ^{[ 21 ]}

ถ้าไม่มีค่าใดในแถวเป้าหมายเป็นค่าลบ ก็จะไม่สามารถเลือกตัวแปรป้อนเข้าได้ และคำตอบที่ได้ก็คือค่าสูงสุด สามารถเห็นได้ง่ายว่าเป็นค่าสูงสุด เนื่องจากแถวเป้าหมายในขณะนี้สอดคล้องกับสมการในรูปแบบ

$${\displaystyle z(\mathbf {x} )=z_{B}+{\text{non-positive terms corresponding to nonbasic variables}}}$$

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

ถัดไป ต้องเลือกแถวหลัก (pivot row) โดยให้ตัวแปรที่ป้อนเข้าไป (และด้วยเหตุนี้ การปรับปรุงในเป้าหมาย) มีค่าสูงสุด โดยที่ตัวแปรพื้นฐานอื่นๆ ทั้งหมดต้องไม่เป็นลบ ถ้าคอลัมน์หลัก (pivot column) คือc ก็จะสามารถทำได้โดย การเลือก แถวหลักr โดยให้เงื่อนไขต่อไปนี้เป็นจริง:

${\displaystyle {\hat {b}}_{r}/{\hat {a}}_{rc}\,}$

คือค่าต่ำสุดเหนือr ทั้งหมด ซึ่ง> 0 เรียกว่า การ ทดสอบอัตราส่วนขั้นต่ำ^{[ 20 ]}หากมีมากกว่าหนึ่งแถวที่บรรลุค่าต่ำสุด สามารถใช้ กฎการเลือกตัวแปรแบบตัดทิ้ง^{[ 22 ]}เพื่อกำหนดได้ ${\displaystyle {\hat {a}}_{rc}}$

พิจารณาโปรแกรมเชิงเส้น

เพิ่มให้สูงสุด

${\displaystyle Z=2x+3y+4z}$

ขึ้นอยู่กับ

${\displaystyle {\begin{aligned}3x+2y+z&\leq 10\\2x+5y+3z&\leq 15\\x,\,y,\,z&\geq 0\end{aligned}}}$

เมื่อเพิ่มตัวแปรส่วนเกินsและtเข้าไปแล้ว จะแสดงออกมาในรูปแบบตารางมาตรฐาน

${\displaystyle {\begin{bmatrix}1&-2&-3&-4&0&0&0\\0&3&2&1&1&0&10\\0&2&5&3&0&1&15\end{bmatrix}}}$

โดยที่คอลัมน์ที่ 5 และ 6 แทนตัวแปรพื้นฐานsและtและคำตอบที่เป็นไปได้พื้นฐานที่สอดคล้องกันคือ

${\displaystyle x=y=z=0,\,s=10,\,t=15.}$

สามารถเลือกคอลัมน์ที่ 2, 3 และ 4 เป็นคอลัมน์หลักได้ ในตัวอย่างนี้ สมมติว่าเลือกคอลัมน์ที่ 4 ค่าของzที่ได้จากการเลือกแถวที่ 2 และ 3 เป็นแถวหลักคือ 10/1 = 10 และ 15/3 = 5 ตามลำดับ ในจำนวนนี้ ค่าต่ำสุดคือ 5 ดังนั้นแถวที่ 3 ต้องเป็นแถวหลัก เมื่อทำการแปลงเป็นแถวหลักแล้วจะได้ผลลัพธ์ดังนี้

${\displaystyle {\begin{bmatrix}1&{\frac {2}{3}}&{\frac {11}{3}}&0&0&{\frac {4}{3}}&20\\0&{\frac {7}{3}}&{\frac {1}{3}}&0&1&-{\frac {1}{3}}&5\\0&{\frac {2}{3}}&{\frac {5}{3}}&1&0&{\frac {1}{3}}&5\end{bmatrix}}}$

ตอนนี้คอลัมน์ที่ 4 และ 5 แสดงถึงตัวแปรพื้นฐานzและsและคำตอบที่เป็นไปได้พื้นฐานที่สอดคล้องกันคือ

${\displaystyle x=y=t=0,\,z=5,\,s=5.}$

สำหรับขั้นตอนต่อไป ไม่มีค่าลบในแถวเป้าหมาย และในความเป็นจริง

$${\displaystyle Z=20-{\frac {2}{3}}x-{\frac {11}{3}}y-{\frac {4}{3}}t}$$

ดังนั้นค่าสูงสุดของZคือ 20

โดยทั่วไป โปรแกรมเชิงเส้นจะไม่ถูกกำหนดในรูปแบบมาตรฐาน และจะต้องค้นหาตารางมาตรฐานที่เทียบเท่ากันก่อนจึงจะสามารถเริ่มอัลกอริทึมซิมเพล็กซ์ได้ ซึ่งสามารถทำได้โดยการแนะนำตัวแปรเทียมคอลัมน์ของเมทริกซ์เอกลักษณ์จะถูกบวกเป็นเวกเตอร์คอลัมน์สำหรับตัวแปรเหล่านี้ หากค่า b สำหรับสมการข้อจำกัดเป็นลบ สมการจะถูกกลับเครื่องหมายก่อนที่จะบวกคอลัมน์ของเมทริกซ์เอกลักษณ์ วิธีนี้จะไม่เปลี่ยนแปลงชุดของคำตอบที่เป็นไปได้หรือคำตอบที่เหมาะสมที่สุด และรับประกันว่าตัวแปรส่วนเกินจะประกอบเป็นคำตอบที่เป็นไปได้เริ่มต้น ตารางใหม่นี้อยู่ในรูปแบบมาตรฐาน แต่ไม่เทียบเท่ากับปัญหาเดิม ดังนั้นจึงมีการแนะนำฟังก์ชันวัตถุประสงค์ใหม่ ซึ่งเท่ากับผลรวมของตัวแปรเทียม และใช้อัลกอริทึมซิมเพล็กซ์เพื่อหาค่าต่ำสุด โปรแกรมเชิงเส้นที่แก้ไขแล้วเรียกว่าปัญหาเฟส I ^{[ 23 ]}

อัลกอริทึมซิมเพล็กซ์ที่ใช้กับปัญหาเฟส I จะต้องสิ้นสุดด้วยค่าต่ำสุดสำหรับฟังก์ชันวัตถุประสงค์ใหม่ เนื่องจากเป็นผลรวมของตัวแปรที่ไม่เป็นลบ ค่าของมันจึงถูกจำกัดไว้ที่ 0 หากค่าต่ำสุดเป็น 0 ตัวแปรเทียมสามารถถูกกำจัดออกจากตารางแคนอนิกที่ได้ ทำให้ได้ตารางแคนอนิกที่เทียบเท่ากับปัญหาเดิม จากนั้นสามารถใช้อัลกอริทึมซิมเพล็กซ์เพื่อหาคำตอบได้ ขั้นตอนนี้เรียกว่าเฟส IIหากค่าต่ำสุดเป็นบวก จะไม่มีคำตอบที่เป็นไปได้สำหรับปัญหาเฟส I ที่ตัวแปรเทียมทั้งหมดเป็นศูนย์ ซึ่งหมายความว่าบริเวณที่เป็นไปได้สำหรับปัญหาเดิมนั้นว่างเปล่า ดังนั้นปัญหาเดิมจึงไม่มีคำตอบ^{[ 13 ] [ 14 ] [ 24 ]}

พิจารณาโปรแกรมเชิงเส้น

เพิ่มให้สูงสุด

${\displaystyle Z=2x+3y+4z}$

ขึ้นอยู่กับ

${\displaystyle {\begin{aligned}3x+2y+z&=10\\2x+5y+3z&=15\\x,\,y,\,z&\geq 0\end{aligned}}}$

ปัญหานี้แตกต่างจากตัวอย่างก่อนหน้าตรงที่มีข้อจำกัดแบบเท่ากันแทนที่จะเป็นแบบไม่เท่ากัน วิธีแก้ปัญหาเดิมนั้นละเมิดข้อจำกัดข้อแรก ปัญหาใหม่นี้แสดงด้วยตาราง (ที่ไม่ใช่แบบมาตรฐาน) ${\displaystyle x=y=0\,,z=5}$

${\displaystyle {\begin{bmatrix}1&-2&-3&-4&0\\0&3&2&1&10\\0&2&5&3&15\end{bmatrix}}}$

แนะนำตัวแปรเทียมuและvและฟังก์ชันเป้าหมายW  =  u  +  vซึ่งจะทำให้ได้ตารางใหม่

${\displaystyle {\begin{bmatrix}1&0&0&0&0&-1&-1&0\\0&1&-2&-3&-4&0&0&0\\0&0&3&2&1&1&0&10\\0&0&2&5&3&0&1&15\end{bmatrix}}}$

สมการที่กำหนดฟังก์ชันเป้าหมายเดิมจะถูกเก็บรักษาไว้เพื่อเตรียมพร้อมสำหรับขั้นตอนที่สอง

โดยโครงสร้างแล้วuและvต่างก็เป็นตัวแปรพื้นฐาน เนื่องจากเป็นส่วนหนึ่งของเมทริกซ์เอกลักษณ์เริ่มต้น อย่างไรก็ตาม ฟังก์ชันเป้าหมายWในปัจจุบันถือว่าuและvมีค่าเป็น 0 ทั้งคู่ เพื่อปรับฟังก์ชันเป้าหมายให้มีค่าที่ถูกต้อง โดยที่u  = 10 และv  = 15 ให้บวกแถวที่สามและสี่เข้ากับแถวแรก จะได้

${\displaystyle {\begin{bmatrix}1&0&5&7&4&0&0&25\\0&1&-2&-3&-4&0&0&0\\0&0&3&2&1&1&0&10\\0&0&2&5&3&0&1&15\end{bmatrix}}}$

เลือกคอลัมน์ที่ 5 เป็นคอลัมน์หลัก ดังนั้นแถวหลักต้องเป็นแถวที่ 4 และตารางที่อัปเดตแล้วจะเป็นดังนี้

${\displaystyle {\begin{bmatrix}3&0&7&1&0&0&-4&15\\0&3&2&11&0&0&4&60\\0&0&7&1&0&3&-1&15\\0&0&2&5&3&0&1&15\end{bmatrix}}}$

ตอนนี้ให้เลือกคอลัมน์ที่ 3 เป็นคอลัมน์หลัก โดยที่แถวที่ 3 ต้องเป็นแถวหลัก เพื่อให้ได้ผลลัพธ์ดังนี้

${\displaystyle {\begin{bmatrix}7&0&0&0&0&-7&-7&0\\0&7&0&25&0&-2&10&130\\0&0&7&1&0&3&-1&15\\0&0&0&11&7&-2&3&25\end{bmatrix}}}$

ตัวแปรเทียมมีค่าเป็น 0 แล้ว และสามารถตัดทิ้งได้เพื่อให้ได้ตารางแบบมาตรฐานที่เทียบเท่ากับปัญหาเดิม:

${\displaystyle {\begin{bmatrix}7&0&25&0&130\\0&7&1&0&15\\0&0&11&7&25\end{bmatrix}}}$

โดยบังเอิญ ค่านี้เป็นค่าที่เหมาะสมที่สุดอยู่แล้ว ดังนั้นค่าที่เหมาะสมที่สุดสำหรับโปรแกรมเชิงเส้นดั้งเดิมคือ 130/7 ค่านี้ "แย่กว่า" 20 ซึ่งเป็นสิ่งที่คาดหวังได้สำหรับปัญหาที่มีข้อจำกัดมากกว่า

รูปแบบตารางที่ใช้ข้างต้นเพื่ออธิบายอัลกอริทึมนั้นเอื้อต่อการนำไปใช้งานได้ทันที โดยที่ตารางจะถูกเก็บรักษาไว้ในรูปอาร์เรย์สี่เหลี่ยมผืนผ้าขนาด ( m  + 1) x ( m  +  n  + 1) การหลีกเลี่ยงการจัดเก็บคอลัมน์ m คอลัมน์ที่ชัดเจนของเมทริกซ์เอกลักษณ์ที่จะปรากฏในตารางนั้นทำได้ง่าย เนื่องจากBเป็นเซตย่อยของคอลัมน์ของ [ A ,  I ] การนำไปใช้งานนี้เรียกว่า " อัลกอริทึมซิมเพล็กซ์ มาตรฐาน " อย่างไรก็ตาม ค่าใช้จ่ายในการจัดเก็บและการคำนวณนั้นสูงมาก ทำให้วิธีซิมเพล็กซ์มาตรฐานเป็นวิธีการที่แพงเกินไปสำหรับการแก้ปัญหาการเขียนโปรแกรมเชิงเส้นขนาดใหญ่

ในแต่ละรอบการทำซ้ำซิมเพล็กซ์ ข้อมูลที่จำเป็นมีเพียงแถวแรกของตาราง คอลัมน์ (สำคัญ) ของตารางที่สอดคล้องกับตัวแปรขาเข้า และด้านขวามือ ซึ่งสามารถอัปเดตได้โดยใช้คอลัมน์สำคัญ และแถวแรกของตารางสามารถอัปเดตได้โดยใช้แถว (สำคัญ) ที่สอดคล้องกับตัวแปรขาออก ทั้งคอลัมน์สำคัญและแถวสำคัญสามารถคำนวณได้โดยตรงโดยใช้ผลเฉลยของระบบสมการเชิงเส้นที่เกี่ยวข้องกับเมทริกซ์Bและผลคูณเมทริกซ์-เวกเตอร์โดยใช้Aข้อสังเกตเหล่านี้เป็นแรงบันดาลใจให้เกิด " อัลกอริทึมซิมเพล็กซ์ที่ปรับปรุงใหม่ " ซึ่งการใช้งานจะแตกต่างกันโดยการแสดง  ^Bที่ ผกผันได้ ^{[ 25} ]

ในปัญหาการเขียนโปรแกรมเชิงเส้นขนาดใหญ่Aมักจะเป็นเมทริกซ์เบาบางและเมื่อใช้ประโยชน์จากความเบาบางของB ที่เกิดขึ้น ในขณะที่ยังคงรักษาการแสดงผลแบบผกผันได้ อัลกอริทึมซิมเพล็กซ์ที่ปรับปรุงแล้วจะมีประสิทธิภาพมากกว่าวิธีซิมเพล็กซ์มาตรฐานมาก โปรแกรมแก้ปัญหาซิมเพล็กซ์เชิงพาณิชย์นั้นใช้พื้นฐานจากอัลกอริทึมซิมเพล็กซ์ที่ปรับปรุงแล้ว^{[ 24 ] [ 25 ] [ 26 ] [ 27 ] [ 28 ]}

ถ้าค่าของตัวแปรพื้นฐานทั้งหมดเป็นบวกอย่างเคร่งครัด การเลือกจุดหมุนจะต้องส่งผลให้ค่าเป้าหมายดีขึ้น เมื่อเป็นเช่นนี้เสมอ จะไม่มีชุดตัวแปรพื้นฐานใดปรากฏซ้ำสองครั้ง และอัลกอริทึมซิมเพล็กซ์จะต้องหยุดทำงานหลังจากจำนวนขั้นตอนที่จำกัด คำตอบที่เป็นไปได้พื้นฐานซึ่งอย่างน้อยหนึ่ง ตัวแปร พื้นฐานเป็นศูนย์เรียกว่า คำตอบ ที่เสื่อมสภาพและอาจส่งผลให้จุดหมุนไม่มีการปรับปรุงค่าเป้าหมาย ในกรณีนี้จะไม่มีการเปลี่ยนแปลงที่แท้จริงในคำตอบ แต่เป็นการเปลี่ยนแปลงเฉพาะชุดของตัวแปรพื้นฐานเท่านั้น เมื่อมีการเลือกจุดหมุนดังกล่าวหลายครั้งติดต่อกัน จะไม่มีการปรับปรุงใดๆ ในการใช้งานทางอุตสาหกรรมขนาดใหญ่ ความเสื่อมสภาพเป็นเรื่องปกติ และการ " หยุดชะงัก " ดังกล่าวเป็นสิ่งที่น่าสังเกต สิ่งที่แย่กว่าการหยุดชะงักคือความเป็นไปได้ที่ชุดตัวแปรพื้นฐานเดียวกันจะปรากฏซ้ำสองครั้ง ในกรณีนี้ กฎการเลือกจุดหมุนแบบกำหนดของอัลกอริทึมซิมเพล็กซ์จะสร้างวงวนไม่สิ้นสุด หรือ "วัฏจักร" ในขณะที่ความเสื่อมสภาพเป็นกฎในทางปฏิบัติและการหยุดชะงักเป็นเรื่องปกติ แต่วัฏจักร นั้นหายากในทางปฏิบัติ การอภิปรายเกี่ยวกับตัวอย่างของวัฏจักรในทางปฏิบัติปรากฏอยู่ในPadberg ^{[ 24 ]}กฎของ Bland ป้องกันการวนซ้ำและรับประกันว่าอัลกอริทึม simplex จะสิ้นสุดเสมอ^{[ 24 ] [ 29 ] [ 30 ]}อัลกอริทึมการหมุนอีกแบบหนึ่งคืออัลกอริทึมไขว้จะไม่วนซ้ำในโปรแกรมเชิงเส้น^{[ 31 ]}

กฎการเลือกตัวแปรตามประวัติ เช่นกฎของ Zadehและกฎของ Cunninghamพยายามหลีกเลี่ยงปัญหาการหยุดชะงักและการวนซ้ำ โดยการติดตามความถี่ในการใช้งานตัวแปรต่างๆ แล้วจึงเลือกตัวแปรที่ถูกใช้น้อยที่สุด

วิธีซิมเพล็กซ์มีประสิทธิภาพอย่างมากในทางปฏิบัติและเป็นการปรับปรุงที่ดีกว่าวิธีเดิม ๆ เช่นการกำจัดฟูริเยร์-มอตซกินอย่างไรก็ตาม ในปี 1972 Kleeและ Minty ^{[ 32 ]}ได้ยกตัวอย่างลูกบาศก์ Klee-Mintyซึ่งแสดงให้เห็นว่าความซับซ้อนในกรณีที่เลวร้ายที่สุดของวิธีซิมเพล็กซ์ตามที่ Dantzig กำหนดนั้นใช้เวลาแบบเลขชี้กำลัง นับตั้งแต่นั้นมา สำหรับเกือบทุกรูปแบบของวิธีนี้ ได้มีการแสดงให้เห็นว่ามีตระกูลของโปรแกรมเชิงเส้นที่วิธีนี้ทำงานได้ไม่ดี ยังคงเป็นคำถามที่เปิดอยู่ว่ามีรูปแบบที่มีเวลาแบบพหุนามหรือไม่ แม้ว่าจะทราบกฎการหมุนแบบต่ำกว่าเลขชี้กำลังแล้วก็ตาม^{[ 33 ]}

ในปี 2014 มีการพิสูจน์^{[ 34 ]}ว่ารูปแบบเฉพาะของวิธีซิมเพล็กซ์เป็นNP-mightyกล่าวคือ สามารถใช้แก้ปัญหาใดๆ ใน NP ได้โดยปริยายระหว่างการดำเนินการของอัลกอริทึมด้วยค่าใช้จ่ายพหุนาม นอกจากนี้ การตัดสินใจว่าตัวแปรที่กำหนดจะเข้าสู่ฐานระหว่างการดำเนินการของอัลกอริทึมบนอินพุตที่กำหนดหรือไม่ และการกำหนดจำนวนรอบที่จำเป็นสำหรับการแก้ปัญหาที่กำหนด ล้วนเป็นปัญหาNP-hard ^{[ 34 ]}ในเวลาเดียวกันนั้น มีการแสดงให้เห็นว่ามีกฎการหมุนเทียมซึ่งการคำนวณเอาต์พุตเป็นPSPACE -complete ^{[ 35 ]}ในปี 2015 สิ่งนี้ได้รับการเสริมความแข็งแกร่งเพื่อแสดงให้เห็นว่าการคำนวณเอาต์พุตของกฎการหมุนของ Dantzig เป็นPSPACE -complete ^{[ 36 ]}

การวิเคราะห์และการหาปริมาณของการสังเกตว่าอัลกอริทึมซิมเพล็กซ์มีประสิทธิภาพในทางปฏิบัติ แม้ว่าจะมีความซับซ้อนในกรณีที่เลวร้ายที่สุดแบบเลขชี้กำลัง ทำให้เกิดการพัฒนามาตรวัดความซับซ้อนอื่นๆ อัลกอริทึมซิมเพล็กซ์มีความซับซ้อนในกรณีเฉลี่ย แบบพหุนามภายใต้ การแจกแจงความน่าจะเป็นต่างๆโดยประสิทธิภาพในกรณีเฉลี่ยที่แม่นยำของอัลกอริทึมซิมเพล็กซ์ขึ้นอยู่กับการเลือกการแจกแจงความน่าจะเป็นสำหรับเมทริกซ์สุ่ม^{[ 37 ] [ 38 ]}แนวทางอื่นในการศึกษา " ปรากฏการณ์ทั่วไป " ใช้ทฤษฎีหมวดหมู่แบร์จากโทโพโลยีทั่วไปและแสดงให้เห็นว่า (ในเชิงโทโพโลยี) เมทริกซ์ "ส่วนใหญ่" สามารถแก้ไขได้โดยอัลกอริทึมซิมเพล็กซ์ในจำนวนขั้นตอนแบบพหุนาม

อีกวิธีหนึ่งในการวิเคราะห์ประสิทธิภาพของอัลกอริธึมซิมเพล็กซ์คือการศึกษาพฤติกรรมของสถานการณ์กรณีเลวร้ายที่สุดภายใต้การรบกวนเล็กน้อย – สถานการณ์กรณีเลวร้ายที่สุดมีเสถียรภาพภายใต้การเปลี่ยนแปลงเล็กน้อย (ในแง่ของเสถียรภาพเชิงโครงสร้าง ) หรือสามารถจัดการได้หรือไม่? สาขาการวิจัยนี้เรียกว่าการวิเคราะห์แบบเรียบ (smoothed analysis ) ซึ่งถูกนำมาใช้เพื่อศึกษาเฉพาะวิธีซิมเพล็กซ์ อันที่จริง เวลาในการทำงานของวิธีซิมเพล็กซ์บนอินพุตที่มีสัญญาณรบกวนนั้นเป็นพหุนามตามจำนวนตัวแปรและขนาดของการรบกวน^{[ 39 ] [ 40 ]}

อัลกอริทึมอื่นๆ สำหรับการแก้ปัญหาการเขียนโปรแกรมเชิงเส้นอธิบายไว้ใน บทความ การเขียนโปรแกรมเชิงเส้นอัลกอริทึมการสลับฐานอีกแบบหนึ่งคืออัลกอริทึมไขว้^{[ 41 ] [ 42 ]}มีอัลกอริทึมเวลาพหุนามสำหรับการเขียนโปรแกรมเชิงเส้นที่ใช้วิธีจุดภายใน ได้แก่อัลกอริทึมวงรีของKhachiyanอั ลกอริ ทึมเชิงฉายของKarmarkarและ อัลกอริ ทึมการติดตามเส้นทาง^{[ 15 ]}วิธีBig-Mเป็นกลยุทธ์ทางเลือกสำหรับการแก้ปัญหาการเขียนโปรแกรมเชิงเส้นโดยใช้ซิมเพล็กซ์เฟสเดียว Cohen et al. ^{[ 43 ]}เป็นตัวแทนของสาขาของอัลกอริทึมที่ใช้อัลกอริทึมการคูณเมทริกซ์อย่างรวดเร็วกับการเขียนโปรแกรมเชิงเส้น

การเขียนโปรแกรมเชิงเส้นเศษส่วน (LFP) เป็นการวางนัยทั่วไปของการเขียนโปรแกรมเชิงเส้น (LP) ใน LP ฟังก์ชันเป้าหมายคือ ฟังก์ชันเชิงเส้นในขณะที่ฟังก์ชันเป้าหมายของการเขียนโปรแกรมเชิงเส้นเศษส่วนคืออัตราส่วนของฟังก์ชันเชิงเส้นสองฟังก์ชัน กล่าวอีกนัยหนึ่ง การเขียนโปรแกรมเชิงเส้นคือการเขียนโปรแกรมเชิงเส้นเศษส่วนซึ่งตัวส่วนเป็นฟังก์ชันคงที่ที่มีค่าเป็นหนึ่งทุกที่ การเขียนโปรแกรมเชิงเส้นเศษส่วนสามารถแก้ไขได้โดยใช้อัลกอริทึมซิมเพล็กซ์แบบต่างๆ^{[ 44 ] [ 45 ] [ 46 ] [ 47 ]}หรือโดยอัลกอริทึมครอส^{[ 48 ]}

บทนำเหล่านี้เขียนขึ้นสำหรับนักศึกษาด้านวิทยาการคอมพิวเตอร์และการวิจัยเชิงปฏิบัติการ :

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. RivestและClifford Stein . Introduction to Algorithms , ฉบับพิมพ์ครั้งที่สอง. MIT Press และ McGraw-Hill, 2001. ISBN 0-262-03293-7ส่วนที่ 29.3: อัลกอริทึมซิมเพล็กซ์ หน้า 790–804
• Frederick S. Hillier และ Gerald J. Lieberman: บทนำสู่การวิจัยปฏิบัติการฉบับที่ 8 สำนักพิมพ์ McGraw-Hill ISBN 0-07-123828-X
• Rardin, Ronald L. (1997). การเพิ่มประสิทธิภาพในการวิจัยปฏิบัติการ . Prentice Hall. หน้า 919. ISBN 978-0-02-398415-0.

เว็บไซต์ Wikibook เรื่องการวิจัยดำเนินงาน (Operations Research)มีหน้าเว็บที่กล่าวถึงหัวข้อ: วิธีซิมเพล็กซ์ (Simplex Method)

• หนังสือ "An Introduction to Linear Programming and the Simplex Algorithm"โดย Spyros Reveliotis จากสถาบันเทคโนโลยีจอร์เจีย
• Greenberg, Harvey J., Klee–Minty Polytope แสดงให้เห็นถึงความซับซ้อนเชิงเวลาแบบเลขชี้กำลังของวิธีการซิมเพล็กซ์มหาวิทยาลัยโคโลราโดที่เดนเวอร์ (1997) ดาวน์โหลด PDF
• วิธีซิมเพล็กซ์บทแนะนำวิธีซิมเพล็กซ์พร้อมตัวอย่าง (รวมถึงวิธีสองเฟสและวิธีเอ็ม)
• เครื่องคิดเลขซิมเพล็กซ์ Mathstoolsจาก www.mathstools.com
• ตัวอย่างขั้นตอนวิธีซิมเพล็กซ์สำหรับปัญหาการเขียนโปรแกรมเชิงเส้นมาตรฐานโดย โทมัส แมคฟาร์แลนด์ จากมหาวิทยาลัยวิสคอนซิน-ไวท์วอเตอร์
• PHPSimplex: เครื่องมือออนไลน์สำหรับแก้ปัญหาการเขียนโปรแกรมเชิงเส้นโดย Daniel Izquierdo และ Juan José Ruiz จากมหาวิทยาลัยมาลากา (UMA ประเทศสเปน)
• simplex-mโปรแกรมแก้ปัญหาซิมเพล็กซ์ออนไลน์