วิธี Simplex และการประยุกต์ใช้

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

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

เมื่อต้องการทำเช่นนี้คุณต้องทำตามขั้นตอนต่อไปนี้:

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

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

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

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

ได้รับการพิสูจน์แล้วว่าการค้นหาทั้งทางออกที่ดีที่สุด (ในกรณี (ถ้ามี) เสร็จสมบูรณ์สำหรับทั้งจำนวนและจำนวนขั้น จำกัด ยกเว้นอย่างเดียวว่าวิธี simplex ไม่สามารถจัดการได้คือ "ปัญหาที่เลวร้าย" ในกรณีนี้มีสิ่งที่เรียกว่า "looping" ซึ่งนำไปสู่การทำซ้ำซ้ำ ๆ ของงานเดียวกันเป็นจำนวนนับไม่ถ้วน

วิธี simplex ได้รับการพัฒนาขึ้นในปี 1947 "แม่" ของเขาเป็นนักคณิตศาสตร์จาก US George Danzig ในมุมมองของความจริงที่ว่าวิธีการ simplex มีประวัติศาสตร์อันยาวนานนี้ตอนนี้เป็นหนึ่งในการศึกษามากที่สุดและมีประสิทธิภาพมากที่สุดสำหรับการหาทางออกที่ดีที่สุดในการแก้ไขปัญหาใด ๆ ที่คนเผชิญหน้า

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