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

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

Definition

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

Scope

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

Core questions

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

Key theories

ทฤษฎีบทมูลฐานของการโปรแกรมเชิงเส้น

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

ภาวะคู่กันและภาวะหย่อนที่สมบูรณ์

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

วิธีซิมเพล็กซ์และวิธีจุดภายใน

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

Clinical relevance

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

History

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

Key figures

• George Dantzig
• Leonid Kantorovich
• John von Neumann
• Narendra Karmarkar

Seminal works

• dantzig1963
• luenberger2008

Frequently asked questions

เหตุใดค่าเหมาะสมที่สุดจึงอยู่ที่จุดยอด?

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

วิธีซิมเพล็กซ์รวดเร็วเสมอไปหรือไม่?

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