อัลกอริทึม Simplex และจุดสุดขีด
สำหรับคำถามนี้คำสั้น ๆ ของฉันคือ LP = โปรแกรมเชิงเส้น BFS = วิธีแก้ปัญหาพื้นฐานที่เป็นไปได้ SEF = รูปแบบความเท่าเทียมกันมาตรฐาน
เนื่องจากอัลกอริทึม Simplex วนซ้ำจากจุดสุดโต่งไปยังจุดสุดขั้ว (ซึ่งสอดคล้องกับข้อเท็จจริงที่ว่า Simplex วนซ้ำจาก BFS ไปยัง BFS เมื่อ LP อยู่ใน SEF) อัลกอริทึม Simplex ทำงานอย่างไรในทางเรขาคณิตเมื่อพื้นที่ที่เป็นไปได้คือรูปทรงหลายเหลี่ยมที่ไม่สามารถรับรู้ได้ SEF (เช่น halfspace)? สมมติว่าเรามี LP ซึ่งพื้นที่ที่เป็นไปได้นั้นไม่มีคะแนนที่รุนแรง จากนั้นเราสามารถเขียน LP ที่ 'เทียบเท่า' ซึ่งอยู่ใน SEF และเรียกใช้อัลกอริทึม Simplex แทน แต่มีจุดสุดขั้วสำหรับรูปทรงหลายเหลี่ยมใหม่นี้ในขณะที่ไม่มีสำหรับของดั้งเดิมโดยการสันนิษฐาน เดิมทีฉันคิดว่าจุดสุดขั้วของ LP หนึ่งในเชิงชีวประวัติสอดคล้องกับจุดสุดขั้วของอีกอันหนึ่ง แต่เห็นได้ชัดว่าไม่เป็นเช่นนั้น
ดังนั้นเมื่อใดที่จุดสูงสุดของ LP เวอร์ชัน SEF จะสอดคล้องกับจุดสูงสุดของต้นฉบับ และยิ่งไปกว่านั้นเมื่อไม่มีการคาดเดาทางชีวภาพเราควรตีความทางเรขาคณิตว่าอัลกอริทึม Simplex กำลังทำในแง่ของ LP ดั้งเดิมอย่างไร?
คำตอบ
อัลกอริทึม Simplex วนซ้ำจากจุดสุดโต่งไปยังจุดสุดขั้ว
ในทางเทคนิคไม่ อัลกอริทึมเริม iterates จากพื้นฐานที่จะเป็นพื้นฐาน มันเกิดขึ้นที่วิธีแก้ปัญหาพื้นฐานที่เป็นไปได้นั้นสอดคล้องกับจุดที่รุนแรง (ตัวอย่างเช่นดูอัลซิมเพล็กซ์จะวนซ้ำผ่านโซลูชันพื้นฐานที่เป็นไปได้แบบคู่ซึ่งไม่ใช่จุดสุดโต่งของพื้นที่ที่เป็นไปได้เบื้องต้น)
พิจารณา LP ในรูปแบบมาตรฐานซึ่งเขียน \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}พื้นที่ที่เป็นไปได้ของ LP นั้นเป็นรูปหลายเหลี่ยมเสมอ หากไม่มีจุดสุดขีดแสดงว่าว่างเปล่า (และไม่มีวิธีแก้ไขปัญหาพื้นฐานที่เป็นไปได้) หรือกำหนดพื้นที่ย่อยของ$\mathbb{R}^{n}$. ตอนนี้กรณีหลังไม่สามารถเกิดขึ้นได้เนื่องจากไม่มีช่องว่างย่อยที่สามารถเป็นส่วนย่อยของ$\mathbb{R}_{+}^{n}$.
ตอนนี้กลับมาที่ (สิ่งที่ฉันคิดว่าเป็น) คำถามเดิมของคุณ: ด้วยรูปทรงหลายเหลี่ยมดั้งเดิมและการเป็นตัวแทนของ SEF การแสดงนั้นมีจุดสุดขั้วหรือไม่และสอดคล้องกับจุดสุดขั้วของ polyhderon ดั้งเดิมหรือไม่? คำตอบคือใช่ SEF จะมีจุดสุดขั้วและไม่อาจไม่ตรงกับจุดสุดขั้วของรูปทรงหลายเหลี่ยมดั้งเดิมของคุณเสมอไป
นี่คือตัวอย่างง่ายๆ: take $\mathcal{P} = \{x \in \mathbb{R}\}$ซึ่งเป็นรูปทรงหลายเหลี่ยม 1 มิติ สูตรมีตัวแปรอิสระหนึ่งตัวและไม่มีข้อ จำกัด
ในการสร้างการแสดง SEF ให้แทนที่ $x$ โดย $x^{+} - x^{-}$ ด้วย $x^{\pm} \geq 0$. ตอนนี้$(0, 0)$ เป็นจุดสูงสุดของ SEF ซึ่งสอดคล้องกับ $x=0$ซึ่งไม่ใช่จุดสุดโต่งของ $\mathcal{P}$.
ไม่แน่ใจว่าฉันเข้าใจคำถามของคุณอย่างถ่องแท้ แต่ฉันเดาว่าความสับสนของคุณเกิดจากการสันนิษฐานว่าวิธีแก้ปัญหาเบื้องต้นเป็น "จุดที่รุนแรง" โซลูชันพื้นฐาน (ไม่จำเป็นต้องเป็นแบบดั้งเดิมหรือเป็นไปได้คู่) เป็นเพียงจุดตัดของข้อ จำกัด ของจำนวนแถว (ซึ่งบางส่วนอาจเป็นขอบเขต) เป็นไปได้ว่าปัญหาไม่มีวิธีแก้ปัญหาเบื้องต้นหรือสองทางที่เป็นไปได้ในผลลัพธ์นั้นเป็นไปไม่ได้หรือไม่ถูกผูกมัด บางครั้งอัลกอริธึมแบบ simplex ของ Textbook จะข้ามไปที่ความจริงที่ว่ารูปแบบของเฟส 1 บางรูปแบบจำเป็นในการสร้าง BFS เพื่อเริ่มอัลกอริทึม เป็นไปได้ว่าระยะแรกที่ 1 พบปัญหาเบื้องต้นไม่สามารถทำได้และยังเป็นไปได้ว่าเฟส 1 คู่พบว่าปัญหาไม่ถูกผูกไว้
อัปเดต: คำตอบของ mtanneau อาจจะบอกว่าทั้งหมดที่มีเพื่อพูดสำหรับข้อ จำกัด เดียวที่มีตัวแปรอิสระจะใช้เช่นเดียวกัน ฉันแค่ต้องการเพิ่มว่าการใช้งาน simplex ทำงานร่วมกับตัวแปรอิสระโดยตรงและอย่าแปลงเป็นสองตัวแปรที่มีขอบด้วย 0 แต่การเก็บรักษาแบบเดียวกันอัลกอริทึมจะวนซ้ำบนโซลูชันพื้นฐานและมีการกำหนดให้ตัวแปรอิสระที่ไม่ใช่พื้นฐานรับค่า 0. โปรดทราบว่าสำหรับรูปทรงหลายเหลี่ยมที่มีขอบเขตการแก้ปัญหาพื้นฐานจะสอดคล้องกับจุดสุดขั้ว