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

Abstract

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