การเขียนโปรแกรมเชิงเส้นจำนวนเต็มคืออะไร?

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

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

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

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

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