ความรู้เบื้องต้นเกี่ยวกับวิธีแก้ปัญหาเบื้องต้นที่เป็นไปได้ทางวิศวกรรม

คุณรู้ว่าการปรับระบบให้เหมาะสมเพื่อให้ได้ผลลัพธ์ที่ดีที่สุดนั้นหมายความว่าอย่างไร หากคุณเป็นนักศึกษาวิศวกรรมศาสตร์หรือวิศวกร

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

แนวคิดของวิธีแก้ปัญหาที่เป็นไปได้ขั้นพื้นฐานมาถึงจุดนี้

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

แต่ทำไมมันถึงสำคัญมาก? ในบทความนี้ ผมจะพูดถึงวิธีแก้ปัญหาพื้นฐานที่เป็นไปได้และวิธีที่สามารถนำไปใช้ในการแก้ปัญหาทางวิศวกรรมในโลกแห่งความเป็นจริงได้

ฉันจะพูดถึงวิธีค้นหาพวกเขา ทำมาจากอะไร และทำไมพวกเขาถึงสำคัญ

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

ทำความเข้าใจกับโซลูชันพื้นฐานที่เป็นไปได้

คำนิยามอย่างเป็นทางการ:

วิธีแก้ปัญหาพื้นฐานสำหรับโมเดลโปรแกรมเชิงเส้นซึ่งตัวแปรทั้งหมดไม่เป็นค่าลบ

โซลูชันที่เป็นไปได้ขั้นพื้นฐาน (BFS) เป็นแนวคิดหลักในการเขียนโปรแกรมเชิงเส้นที่ช่วยค้นหาโซลูชันที่ดีที่สุด

BFS เป็นโซลูชันที่มีจำนวนตัวแปรที่ไม่ใช่ศูนย์น้อยที่สุดเท่าที่จะเป็นไปได้

เป็นมุมของรูปทรงหลายหน้าของคำตอบที่เป็นไปได้

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

การค้นหาโซลูชันที่เป็นไปได้ขั้นพื้นฐานที่เหมาะสมที่สุด

ในการหา BFS ที่ดีที่สุด เราต้องทำสิ่งต่อไปนี้:

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

ขณะนี้ตัวแปรนี้เป็นตัวแปรพื้นฐาน และตัวแปรพื้นฐานตัวอื่นไม่ใช่ตัวแปรพื้นฐานอีกต่อไป

หากมีวิธีแก้ปัญหาที่ดีที่สุด จะต้องอยู่ที่ปลายด้านใดด้านหนึ่งหรือจุดยอดของพื้นที่ที่สามารถแก้ปัญหาได้

ดังนั้น หาก LP มีวิธีแก้ปัญหาที่ดีที่สุด ก็จะมีโซลูชันที่เหมาะสมที่สุด ณ จุดสุดโต่งของชุดที่เป็นไปได้

นอกจากนี้ยังมี BFS ที่ดีที่สุดเสมอ หากมีโซลูชันที่เหมาะสมที่สุด

ใช้วิธี Simplex เพื่อค้นหา BFS ที่เหมาะสมที่สุด

Simplex Method เป็นอัลกอริทึมสำหรับแก้ปัญหาในโปรแกรมเชิงเส้น

โดยจะย้ายจาก BFS หนึ่งไปยัง BFS "ที่อยู่ติดกัน" โดยใช้กระบวนการเดือย

ในกระบวนการ Pivot ตัวแปรที่ไม่ใช่พื้นฐานจะถูกเลือกให้เป็นตัวแปรพื้นฐาน จากนั้นจึงใช้ BFS ปัจจุบันเพื่อแก้ปัญหาสำหรับตัวแปรพื้นฐานใหม่

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

เหตุใดวิธีแก้ปัญหาพื้นฐานที่เป็นไปได้จึงมีความสำคัญอย่างยิ่งต่อการแก้ปัญหาทางวิศวกรรมที่ซับซ้อน

ยังยากที่จะเข้าใจ? ให้ฉันเปลี่ยนมุมมองเล็กน้อย:

ใครต้องการคำตอบที่เรียบง่ายและใช้การได้ เพียงแค่โยนทุกอย่างเข้าด้วยกันและหวังว่าจะดีที่สุด

ท้ายที่สุดแล้ว ใครต้องการการเพิ่มประสิทธิภาพในเมื่อความโกลาหลสนุกกว่ากันเยอะ? ยินดีต้อนรับสู่โลกของตัวแปรที่ไม่ใช่ค่าลบ ที่ทุกอย่างเป็นเพียงข้อเสนอแนะและความล้มเหลวเกือบจะแน่นอน

หรือมันคืออะไร?

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

โอเค นั่นเป็นแค่เรื่องตลกที่ทำให้ดูเหมือนโฆษณาทีวี

ตอนนี้กลับไปที่คำอธิบาย

การหาทางออกที่เป็นไปได้ขั้นพื้นฐาน

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

แต่ละ BFS เป็นมุมของรูปทรงหลายหน้าของคำตอบที่เป็นไปได้จากมุมมองทางเรขาคณิต

หากมีทางออกที่ดีที่สุด ก็ต้องมีก้าวแรกที่ดีที่สุดเช่นกัน

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

การค้นหาวิธีแก้ปัญหาเบื้องต้นเบื้องต้นที่เป็นไปได้

เราสามารถใช้วิธีการต่างๆ กัน ขึ้นอยู่กับวิธีการตั้งค่าปัญหา เพื่อหาทางออกเบื้องต้นเบื้องต้นที่ใช้ได้กับปัญหาการปรับให้เหมาะสมเชิงเส้น

วิธีหนึ่งคือการเพิ่มตัวแปรหย่อนให้กับข้อจำกัดของอสมการและตั้งค่าตัวแปรอื่นๆ ทั้งหมดให้เป็นศูนย์

ตัวแปรหย่อนกลายเป็นตัวแปรพื้นฐาน และส่วนที่เหลือเป็นตัวแปรที่ไม่ใช่พื้นฐาน

วิธี Simplex แบบสองเฟสเป็นอีกวิธีหนึ่งในการแก้ปัญหา

วิธีนี้เกี่ยวข้องกับการแก้ปัญหาโปรแกรมเชิงเส้นเพิ่มเติมเพื่อหาทางออกพื้นฐานเบื้องต้นที่เป็นไปได้

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

ค้นหาวิธีแก้ปัญหาพื้นฐานที่เป็นไปได้ทั้งหมด

อาจมีวิธีแก้ปัญหาพื้นฐานมากกว่าหนึ่งวิธีที่ใช้ได้กับโปรแกรมเชิงเส้น

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

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

การหาทางออกที่เป็นไปได้ขั้นพื้นฐานโดยไม่มีตัวแปรหย่อน

เราจำเป็นต้องใช้ตัวแปร slack เพื่อกำจัดข้อจำกัดที่น้อยกว่า เพื่อให้เราสามารถหาทางออกพื้นฐานที่ใช้งานได้โดยไม่มีตัวแปร slack

ตัวแปรหย่อนเป็นเพียงความแตกต่างระหว่างด้านขวาของข้อจำกัดและด้านซ้าย

ตัวอย่างเช่น สำหรับข้อจำกัดแรก เรากำหนดตัวแปร slack x4 = 14 - 2x1 - x2 - x3 ในแง่ของตัวแปรใหม่นี้ ข้อจำกัดแรกเทียบเท่ากับ x4 ≥ 0 ซึ่งเป็นข้อจำกัดเชิงบวกสำหรับ x4

เมื่อเราเพิ่มตัวแปร slack เหล่านี้ เราจะได้โปรแกรมเชิงเส้นที่เหมือนกับโปรแกรมดั้งเดิม ยกเว้นว่าข้อจำกัดทั้งหมดเป็นสมการหรือข้อจำกัดที่บอกว่าบางอย่างเป็นบวก

ชุดของตัวแปรพื้นฐาน ซึ่งมีค่าอื่นที่ไม่ใช่ศูนย์ในการแก้ปัญหาพื้นฐาน เรียกว่า พื้นฐาน

ตัวแปรที่มีค่าเป็นศูนย์ในโซลูชันพื้นฐานไม่ใช่ตัวแปรพื้นฐาน

ในการหาทางออกที่ดีที่สุด เราต้องหาเวกเตอร์ x ที่ตรงตามกฎทั้งหมดและได้ค่าที่มากที่สุดหรือน้อยที่สุดสำหรับวัตถุประสงค์

แต่การหาทางออกที่ดีที่สุดนั้นต้องมีขั้นตอนมากกว่าแค่การหาวิธีแก้ปัญหาที่ได้ผลและไม่มีตัวแปรหย่อน

เป็นไปไม่ได้เสมอที่จะหาทางออกพื้นฐานที่ไม่มีตัวแปรหย่อน โดยเฉพาะอย่างยิ่งสำหรับปัญหาที่มีข้อจำกัดน้อยกว่า

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

คุณสมบัติและความสำคัญของโซลูชันที่เป็นไปได้ขั้นพื้นฐาน

คุณสมบัติของวิธีแก้ปัญหาที่เป็นไปได้ขั้นพื้นฐาน

วิธีแก้ปัญหาเบื้องต้นที่เป็นไปได้มีตัวแปร m มากที่สุดที่ไม่เป็นศูนย์ และตัวแปร nm อย่างน้อยเป็นศูนย์ โดยที่ n คือจำนวนของตัวแปรการตัดสินใจ และ m คือจำนวนของข้อจำกัด

BFS เป็นมุมหนึ่งของโพลิฮีดรอนของคำตอบที่เป็นไปได้ และแต่ละ BFS มีข้อจำกัดที่ใช้งานอยู่ n ข้อที่เป็นอิสระเชิงเส้น

หากมีทางออกที่ดีที่สุด ก็ต้องมีก้าวแรกที่ดีที่สุดเช่นกัน

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

เพื่อหาคำตอบที่ดีที่สุด อัลกอริธึม Simplex จะต้องผ่านชุดของ BFS

อัลกอริทึม Simplex จะค้นหาโซลูชันพื้นฐานทั้งหมดที่เป็นไปได้ด้วยวิธีที่เป็นระบบเพื่อค้นหาโซลูชันที่ดีที่สุด

ความสำคัญของโซลูชันที่เป็นไปได้ขั้นพื้นฐาน

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

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

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

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

วิดีโอ: วิธีแก้ปัญหาเบื้องต้นที่เป็นไปได้

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

กรณีการใช้งาน

บทสรุป

เมื่อพิจารณาแนวทางแก้ไขปัญหาพื้นฐานที่เป็นไปได้แล้ว ก็ชัดเจนว่าเป็นเครื่องมือสำคัญสำหรับวิศวกรหรือนักศึกษาวิศวกรรมศาสตร์ทุกคน

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

แต่นอกจากจะมีประโยชน์แล้ว ยังแสดงให้เห็นว่าคณิตศาสตร์มีความหรูหราและสวยงามเพียงใด

น่าทึ่งมากที่คุณสามารถสรุปปัญหาที่ซับซ้อนให้กลายเป็นชุดสมการง่ายๆ แล้วใช้สมการเหล่านั้นแก้ปัญหาในโลกแห่งความเป็นจริง

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

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

ลิงค์และการอ้างอิง

หนังสือ:

• การเขียนโปรแกรมเชิงเส้น: รากฐานและส่วนขยาย
• การเขียนโปรแกรมเชิงเส้น: ทฤษฎีและการประยุกต์