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

หากคุณเป็นวิศวกรหรือนักศึกษาวิศวกรรมศาสตร์ คุณอาจรู้ว่าการปรับให้เหมาะสมนั้นหมายถึงอะไร

เพื่อให้ได้ผลลัพธ์ที่ดีที่สุด สิ่งสำคัญคือต้องหาวิธีที่ดีที่สุดในการทำสิ่งต่างๆ

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

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

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

โซลูชั่นพื้นฐานในการเขียนโปรแกรมเชิงเส้น

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

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

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

โดยเฉพาะอย่างยิ่ง เวกเตอร์ x เป็นคำตอบพื้นฐานสำหรับรูปทรงหลายหน้าถ้าเวกเตอร์ {ai : xi = 0} เป็นอิสระเชิงเส้น

ซึ่งหมายความว่าคอลัมน์ของ A ที่มีตัวแปร xi ที่ไม่เป็นศูนย์จะเป็นอิสระเชิงเส้น

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

BFS เป็นไปตามกฎทั้งหมดที่กำหนดรูปทรงหลายเหลี่ยม

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

ในการหาวิธีแก้ปัญหาพื้นฐาน คุณต้องตั้งค่าตัวแปร nm ที่ไม่เป็นพื้นฐานให้เป็นศูนย์และแก้ปัญหาตัวแปร m ที่เป็นพื้นฐาน

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

Simplex Method เป็นกระบวนการวนซ้ำที่ย้ายจาก BFS หนึ่งไปยัง BFS ถัดไปจนกว่าจะพบ BFS ที่ดีที่สุด

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

หากไม่มี BFS ดังกล่าว BFS ปัจจุบันคือสิ่งที่ดีที่สุด

โมเดลโปรแกรมเชิงเส้น

โมเดลโปรแกรมเชิงเส้นประกอบด้วยองค์ประกอบหลักสามส่วน: ตัวแปรการตัดสินใจ ฟังก์ชันวัตถุประสงค์ และข้อจำกัด

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

ฟังก์ชันวัตถุประสงค์ใช้เพื่อเพิ่มหรือลดจำนวนที่แสดงถึงกำไร ต้นทุน จำนวนผลิตภัณฑ์ที่ผลิต ฯลฯ

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

นอกจากนี้ โปรแกรมเชิงเส้นบางโปรแกรมกำหนดให้ตัวแปรการตัดสินใจทั้งหมดไม่เป็นค่าลบ

ในโมเดลโปรแกรมเชิงเส้น คุณยังสามารถใช้ตัวแปรจำนวนเต็มและไบนารีได้

ตัวแปรไบนารีสามารถมีค่าเป็น 0 หรือ 1 เท่านั้น ดังนั้นจึงมีค่าเป็น 0 หรือ 1 เท่านั้น

วิธี Simplex

วิธีหนึ่งที่ใช้มากที่สุดในการแก้ปัญหาโปรแกรมเชิงเส้นคือ Simplex Method

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

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

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

ค่าผลลัพธ์สำหรับตัวแปรพื้นฐานในรูปแบบ BFS

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

Simplex Method ย้ายจาก BFS หนึ่งไปยัง BFS ที่อยู่ติดกันจนกว่าจะถึง BFS ที่เหมาะสมที่สุดโดยใช้กระบวนการ Pivot

การเปรียบเทียบระหว่างโซลูชันพื้นฐานและโซลูชันที่เป็นไปได้

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

โดยเฉพาะอย่างยิ่ง ต้องมีเวกเตอร์ที่เป็นอิสระเชิงเส้นและมีค่าไม่เป็นศูนย์สำหรับ xi และ x ต้องน้อยกว่า 0

ในทางกลับกัน วิธีแก้ไขที่เป็นไปได้คือจุดใดๆ ที่อยู่ภายในขอบเขตของปัญหา

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

โซลูชันที่เป็นไปได้ขั้นพื้นฐาน (BFS) เป็นเพียงโซลูชันที่ตรงกับมุมของรูปทรงหลายหน้าของโซลูชันที่เป็นไปได้

กลับสู่พื้นฐาน: ปลดล็อกพลังของโซลูชันพื้นฐานด้านวิศวกรรม

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

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

ไม่ต้องกังวล เพราะคำตอบอยู่ที่นี่: แก้ค่าตัวแปร m ในรูปของตัวแปร (nm) ที่เหลือ และตั้งค่าตัวแปร (nm) เป็นศูนย์

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

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

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

การเขียนโปรแกรมเชิงเส้นโซลูชันพื้นฐาน

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

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

บทสรุป

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

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

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

เพื่อให้ได้ผลลัพธ์ที่ดีที่สุด แต่ละปัญหาจะต้องได้รับการพิจารณาและไตร่ตรองอย่างรอบคอบ

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

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

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

หนังสือ:

• การเขียนโปรแกรมเชิงเส้นโดย Vasek Chvatal
• การสร้างแบบจำลองและการแก้โปรแกรมเชิงเส้นด้วย R โดย Jose M. Sallan