วิธีการ Homori แก้ปัญหาการเขียนโปรแกรมจำนวนเต็ม

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

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

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

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

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

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

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

วิธีการของ Homori ในความเป็นจริงเกี่ยวข้องกับการสร้างข้อ จำกัด ที่ตัดการตัดสินใจที่ไม่ใช่ไม่ใช่จำนวนเต็ม ในกรณีนี้จะไม่มีการตัดทอนวิธีใด ๆ ให้กับแผนมูลค่าที่มีจำนวนเต็ม

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

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

เมื่อสร้างข้อ จำกัด คุณควรเลือกส่วนประกอบของแผนการที่เหมาะสมกับส่วนเศษส่วนที่ใหญ่ที่สุด นี่คือข้อ จำกัด ที่จะถูกเพิ่มลงในตาราง simplex ที่มีอยู่

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

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