การแนะนำ

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

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

หนึ่งในวิธีการแก้ปัญหาที่ใช้กันอย่างแพร่หลาย ปัญหาจำนวนเต็มเป็นวิธีสาขาและผูกมัด เสนอครั้งแรกโดยแลนด์และโดอิกในปี พ.ศ. 2503

การเขียนโปรแกรมเชิงเส้นขอบเขตสาขา

สาขาและวิธีการผูกมัด

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

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

2. หากตัวแปรบางตัวไม่ได้รับค่าจำนวนเต็ม การแยกสาขาจะถูกสร้างเป็นสองงานใหม่ ZLP-1, ZLP-2 หนึ่งใน งาน ZLP-1 แสดงถึงปัญหา ZLP-0 เสริมด้วยข้อจำกัดโดยที่ - ทั้งส่วนตัวเลข ประการที่สองเกิดจากการเพิ่มข้อจำกัดให้กับปัญหา ZLP-0 ควรสังเกตว่าการเลือกตัวแปรจำนวนเต็มสามารถกำหนดได้โดยพลการดังนี้:

ดัชนีขึ้นหรือลง

ตัวแปรแสดงถึง การตัดสินใจที่สำคัญได้รับการยอมรับภายในกรอบของงานนี้

ค่าสัมประสิทธิ์ใน ฟังก์ชั่นวัตถุประสงค์ด้วยตัวแปรนี้จึงเกินกว่าตัวแปรอื่นๆ ทั้งหมดอย่างมาก

3. งานของ ZLP-1 และ ZLP-2 ได้รับการแก้ไขอย่างอิสระ สาขาจะสิ้นสุดลงหากขอบเขตของโซลูชันที่เป็นไปได้ว่างเปล่าหรือ ทางออกที่ดีที่สุดจำนวนเต็มสมบูรณ์ มิฉะนั้น จำเป็นต้องแยกสาขาจากจุดที่ 2 โดยกำหนดจำนวนงาน ZLP ต่อไปนี้ตามลำดับปกติของ ZLP-3, ZLP-4

กระบวนการแก้ปัญหาสามารถแสดงเป็นแผนภูมิต้นไม้ซึ่งจุดยอด ZLP-0 สอดคล้องกับแผนเริ่มต้นสำหรับการแก้ปัญหา และแต่ละจุดยอดที่เชื่อมต่อกันด้วยกิ่งก้านนั้นสอดคล้องกับแผนการที่เหมาะสมที่สุดสำหรับปัญหาถัดไป

ลองพิจารณาตัวอย่างต่อไปนี้เพิ่มฟังก์ชันวัตถุประสงค์ให้สูงสุด

ภายใต้ข้อจำกัด

ลองใช้วิธีแบบกราฟิกเพื่อแก้ปัญหาการเขียนโปรแกรมเชิงเส้น

1. มาแก้ไขปัญหาเดิมโดยไม่ต้องคำนึงถึงข้อกำหนดของตัวแปรจำนวนเต็ม

ให้เราแสดงว่าปัญหาเชิงเส้นนี้ การเขียนโปรแกรม ZLP-0.

ในรูปที่ 1.1 รูปหลายเหลี่ยมของวิธีแก้ปัญหานี้ถูกเน้นด้วยการแรเงา ค่าสูงสุดถึงจุดนั้น ผลเฉลยไม่ใช่จำนวนเต็ม

ขั้นตอนต่อไปของวิธีแบรนช์และเมธอดที่ถูกผูกไว้คือแบรนช์ตามตัวแปรจำนวนเต็มตัวใดตัวหนึ่งที่มีค่าเศษส่วน เช่น ในการดำเนินการนี้ เราได้เพิ่มข้อจำกัดใหม่สองข้อให้กับปัญหา ZLP-0 และข้อจำกัดเหล่านี้จะลบช่วง = ซึ่งไม่มีค่าจำนวนเต็มออก ดังนั้นในกระบวนการแยกสาขาจึงมีการสร้างงานใหม่สองงาน ZLP-1 และ ZLP-2

รูปที่ 1.1 วิธีแก้ไขปัญหา ZLP-0

2. มาแก้ปัญหา ZLP-1 แบบกราฟิกกัน

รูปที่ 1.2 แสดง พื้นที่ที่ถูกต้องงาน ZLP-1 ถึงค่าสูงสุดที่จุด วิธีแก้ไขปัญหาไม่ใช่จำนวนเต็ม

รูปที่ 1.2 วิธีแก้ไขปัญหา ZLP-1

3. มาแก้ปัญหา ZLP-2 แบบกราฟิกกัน

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

รูปที่ 1.3 วิธีแก้ไขปัญหา ZLP-2

ตอนนี้เรามาศึกษาปัญหา ZLP-1 กันต่อ เนื่องจากค่าไม่ใช่จำนวนเต็ม มาสร้างอีกหนึ่งสาขาด้วยการแนะนำข้อจำกัดและ เป็นผลให้เราได้รับปัญหาใหม่สองประการ ZLP-3 และ ZLP-4

คำอธิบายทั่วไป

แนวคิดทั่วไปของวิธีการสามารถอธิบายได้โดยใช้ตัวอย่างการค้นหาฟังก์ชันขั้นต่ำในชุด ค่าที่ยอมรับได้ตัวแปร ฟังก์ชันและตัวแปรสามารถมีลักษณะใดก็ได้ วิธีการแยกสาขาและผูกต้องใช้สองขั้นตอน: การแยกสาขาและการค้นหาการประมาณการ (ขอบเขต)

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

ขั้นตอน การหาค่าประมาณประกอบด้วยการหาขอบเขตบนและล่างเพื่อแก้ปัญหาในโดเมนย่อยของค่าที่อนุญาตของตัวแปร

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

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

แอปพลิเคชัน

วิธีการนี้ใช้เพื่อแก้ไขปัญหา NP-complete บางอย่าง เช่น:

ดูสิ่งนี้ด้วย

หมายเหตุ

มูลนิธิวิกิมีเดีย 2010.

ดูว่า "วิธีสาขาและผูกมัด" ในพจนานุกรมอื่น ๆ คืออะไร:

สาขาและวิธีการผูกมัด- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov พจนานุกรมภาษาอังกฤษเป็นภาษารัสเซียเกี่ยวกับวิศวกรรมไฟฟ้าและวิศวกรรมกำลัง มอสโก] หัวข้อวิศวกรรมไฟฟ้า แนวคิดพื้นฐาน สาขา EN และวิธีการผูกมัด ... คู่มือนักแปลทางเทคนิค

วิธี- วิธีการ: วิธีการวัดปริมาณความชื้นของสารโดยอ้อม โดยขึ้นอยู่กับค่าคงที่ไดอิเล็กตริกของสารเหล่านี้กับปริมาณความชื้น ที่มา: RMG 75 2004: ระบบของรัฐการจัดหาอาหาร... หนังสืออ้างอิงพจนานุกรมเกี่ยวกับเอกสารเชิงบรรทัดฐานและทางเทคนิค

เส้นทางที่ดีที่สุดสำหรับพนักงานขายที่เดินทางผ่าน 15 เมืองที่ใหญ่ที่สุดในเยอรมนี เส้นทางที่ระบุสั้นที่สุดที่เป็นไปได้ทั้งหมด 43,589,145,600 ปัญหาพนักงานขายเดินทาง (TSP) (พนักงานขายเดินทาง ... Wikipedia

คำนี้มีความหมายอื่น ดูที่ Overkill ค้นหาให้เสร็จสิ้น(หรือวิธีการ" กำลังดุร้าย", ภาษาอังกฤษ กำลังดุร้าย) วิธีการแก้ปัญหา ปัญหาทางคณิตศาสตร์- อยู่ในคลาสของวิธีการในการค้นหาวิธีแก้ไขโดยการใช้ความเป็นไปได้ทั้งหมดจนหมด... ... Wikipedia

ตัวอย่างปัญหาเกี่ยวกับกระเป๋าเป้: จำเป็นต้องวางกล่องไว้ในกระเป๋าเป้ โดยความจุของกระเป๋าเป้คือ 15 กก. เพื่อให้สิ่งของในกระเป๋าเป้มีประโยชน์ใช้สอยสูงสุด ปัญหาเกี่ยวกับเป้ (backpack) (อังกฤษ... Wikipedia

ปัญหาพนักงานขายที่เดินทาง (พนักงานขายที่เดินทาง) เป็นหนึ่งในปัญหาการปรับให้เหมาะสมแบบผสมผสานที่มีชื่อเสียงที่สุดปัญหาหนึ่ง ภารกิจคือการค้นหาเส้นทางที่ทำกำไรได้มากที่สุดผ่านเมืองที่ระบุอย่างน้อยหนึ่งครั้งทุกๆ... ... Wikipedia

ปัญหาพนักงานขายที่เดินทาง (พนักงานขายที่เดินทาง) เป็นหนึ่งในปัญหาการปรับให้เหมาะสมแบบผสมผสานที่มีชื่อเสียงที่สุดปัญหาหนึ่ง ภารกิจคือการค้นหาเส้นทางที่ทำกำไรได้มากที่สุดผ่านเมืองที่ระบุอย่างน้อยหนึ่งครั้งทุกๆ... ... Wikipedia

ปัญหาพนักงานขายที่เดินทาง (พนักงานขายที่เดินทาง) เป็นหนึ่งในปัญหาการปรับให้เหมาะสมแบบผสมผสานที่มีชื่อเสียงที่สุดปัญหาหนึ่ง ภารกิจคือการค้นหาเส้นทางที่ทำกำไรได้มากที่สุดผ่านเมืองที่ระบุอย่างน้อยหนึ่งครั้งทุกๆ... ... Wikipedia

บทความนี้ไม่มีลิงก์ไปยังแหล่งข้อมูล ข้อมูลจะต้องสามารถตรวจสอบได้ มิฉะนั้นอาจถูกซักถามและลบทิ้ง คุณสามารถ... วิกิพีเดีย

หนังสือ

• การพัฒนาเครื่องมือซอฟต์แวร์สำหรับค้นหาพอร์ตโฟลิโอที่เหมาะสมที่สุดของการซื้อขายส่งขององค์กรการค้า A. V. Mishchenko เราได้พัฒนาส่วนหนึ่งของงานนี้ เครื่องมือซอฟต์แวร์เพื่อแก้ปัญหาในการค้นหาพอร์ตโฟลิโอการซื้อขายส่งที่เหมาะสมที่สุดสำหรับองค์กร ขายปลีก- ในกรณีนี้วิธีการแยกสาขาและ...

การแนะนำ................................................. ....... ........................................... ..... 3

1. ..…………….4

2. สาขาและวิธีการผูกมัด………………………………………..6

2.1 อัลกอริทึมวิธีสาขาและขอบค………………………………....10

สรุป……………………………………………………….14

บรรณานุกรม…………………………………………………….15

การแนะนำ

สาขาและวิธีการผูกมัดถูกเสนอครั้งแรกโดย Land และ Doig ในปี 1960 เพื่อแก้ปัญหา งานทั่วไปการเขียนโปรแกรมเชิงเส้นจำนวนเต็ม ความสนใจในวิธีนี้และในความเป็นจริง "การเกิดใหม่" ของมันเกี่ยวข้องกับงานของ Little, Murthy, Sweeney และ Carell เกี่ยวกับปัญหาพนักงานขายที่กำลังเดินทาง ตั้งแต่บัดนี้เป็นต้นไปก็ปรากฏ จำนวนมากงานที่เกี่ยวข้องกับสาขาและวิธีผูกและการปรับเปลี่ยนต่างๆ ความสำเร็จที่ยิ่งใหญ่ดังกล่าวอธิบายได้จากข้อเท็จจริงที่ว่าผู้เขียนเป็นคนแรกที่ให้ความสนใจกับความเป็นไปได้ที่หลากหลายของวิธีการ สังเกตความสำคัญของการใช้ปัญหาเฉพาะ และใช้ประโยชน์จากปัญหาเฉพาะของพนักงานขายที่เดินทางด้วยตนเอง

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

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

1. วิธีสาขาและขอบเขตของการเขียนโปรแกรมจำนวนเต็ม แนวคิดพื้นฐาน

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

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

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

1. ลดจำนวนตัวแปรจำนวนเต็มให้มากที่สุด ตัวอย่างเช่น ตัวแปรจำนวนเต็มที่มีค่าอย่างน้อย 20 สามารถถือเป็นค่าต่อเนื่องได้

2. ต่างจากปัญหา LP ทั่วไป การเพิ่มข้อจำกัดใหม่ โดยเฉพาะที่เกี่ยวข้องกับตัวแปรจำนวนเต็ม มักจะช่วยลดเวลาที่ต้องใช้ในการแก้ปัญหา CPU

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

สามารถใช้วิธีแยกสาขาและผูกไว้เพื่อแก้ปัญหาการเขียนโปรแกรมแบบไม่เชิงเส้นได้

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

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

2. สาขาและวิธีการผูกมัด

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

f(X) -> สูงสุด,

xxD,

โดยที่ D คือเซตจำกัด

ขั้นแรก เราค้นหาค่าประมาณ £(D) (ขอบเขต) ของฟังก์ชัน f(X), X е D: f(X) ≤ £(D) สำหรับ V X е D ถ้าสำหรับแผนบางแผน X° ของปัญหา ความเท่าเทียมกัน f(X0) = £(D ) ดังนั้น X° = X* เป็นวิธีการแก้ปัญหา หากไม่เป็นไปตามเงื่อนไขที่ระบุ ก็เป็นไปได้ที่จะแบ่งพาร์ติชัน (สาขา) เซต D ให้เป็นจำนวนจำกัดของเซตย่อยที่ไม่เชื่อมติดกัน D1i: ỤD1i = D, ∩D1i = ̨ และการคำนวณค่าประมาณ £(D1i) (ขอบเขต), 1≤i≤m (รูปที่ 2.1)

รูปที่ 2. 1

ถ้าสำหรับบางแผน X1i е Di1, 1 ≤ / ≤ m เงื่อนไข f(Xkl)= £(D1k)≥ £(D1i), 1≤i≤m เป็นไปตามเงื่อนไข ดังนั้น Xk1=X* เป็นแผน (วิธีแก้ปัญหา) ที่เหมาะสมที่สุดของ ปัญหา (7.9) - (7.10)

หากไม่มีแผนดังกล่าว ดังนั้นเซตย่อย Dkl ที่มีค่าประมาณสูงสุด £(D1i) จะถูกเลือกและแบ่งออกเป็นจำนวนจำกัดของเซตย่อยที่ไม่เป็นสมาชิกร่วม D2kj: UD2kj=D1k, ∩D2kj=gest สำหรับแต่ละเซตย่อยค่าประมาณ £(D2kj) จะพบ1≤j≤n (รูปที่ 2.2)

รูปที่ 2.2

หากในกรณีนี้มีแผน X2j е D2kJ, 1 ≤j ≤n โดยที่ f(X2r)= £(D2kr)≥ £(D2kj), 1≤j≤n ดังนั้น X2r= X* จึงเป็นคำตอบของ ปัญหา. หากไม่มีแผนดังกล่าว ขั้นตอนการแตกแขนงจะดำเนินการสำหรับชุด D2kj ที่มีค่าประมาณสูงสุด £(D2kj) , 1≤j≤n วิธีการแยกสาขาถูกกำหนดโดยลักษณะเฉพาะของงานเฉพาะ

ลองพิจารณาปัญหาที่สามารถลดให้เป็นปัญหาการเขียนโปรแกรมเชิงเส้นจำนวนเต็มได้

ตัวอย่าง.

ตู้คอนเทนเนอร์ที่มีปริมาตร 5 ลบ.ม. วางอยู่บนเรือคอนเทนเนอร์ที่มีความจุ 12 ตัน ตู้คอนเทนเนอร์จะต้องเต็มไปด้วยสินค้าสองประเภท มวลของหน่วยสินค้า mj (เป็นตัน) ปริมาตรของหน่วยสินค้า Vj (เป็น m3) ต้นทุน Cj (ในหน่วยการเงินทั่วไป) แสดงไว้ในตารางที่ 2.1

ตารางที่ 2.1

จำเป็นต้องบรรทุกตู้คอนเทนเนอร์ในลักษณะที่ต้นทุนของสินค้าที่ขนส่งสูงสุด

สารละลาย. แบบจำลองทางคณิตศาสตร์ปัญหามีรูปแบบ

Z(X) = 10x1+12x2→สูงสุด

3x1+x2≤12,

x1+2x2≤5

x1≥0

x2≥0

x1, x2 เป็นจำนวนเต็ม

โดยที่ x1, x2 คือจำนวนหน่วยของการโหลดครั้งแรกและครั้งที่สองตามลำดับ

เราแสดงชุดของแผนสำหรับปัญหานี้โดย D - นี่คือชุดของจุดจำนวนเต็มของรูปทรงหลายเหลี่ยม OABC (รูปที่ 2.3)

รูปที่ 2.3

ขั้นแรก เราจะแก้ปัญหาโดยไม่มีเงื่อนไขจำนวนเต็มและรับค่าประมาณของเซต D - ค่าของฟังก์ชัน Z(X) บนแผนที่เหมาะสมที่สุด X° = (19/5, 3/5)

จุด X ไม่ใช่แผนที่เหมาะสมที่สุดสำหรับปัญหา ดังนั้น ตามวิธีสาขาและขอบเขต จำเป็นต้องแบ่งพาร์ติชันชุด D ออกเป็นชุดย่อยที่ไม่เชื่อมต่อกัน ลองเลือกตัวแปรที่ไม่ใช่จำนวนเต็มตัวแรก x1=19/5=34/5 แล้วแบ่งเซต D ออกเป็นเซตย่อยที่ไม่ต่อเนื่องกันสองชุด D11 และ D22 เส้น x1=3 (L3) และ x4= (L3) คือเส้นพาร์ติชัน

ให้เราค้นหาค่าประมาณสำหรับ £(D11) และ £(D12) ซึ่งเราจะแก้ปัญหาการเขียนโปรแกรมเชิงเส้น

Z(X)=10x1+12x2→สูงสุด

3x1+x2≤12

x1+2x2≤5

x1≤3

x1≥0, x2 – จำนวนเต็ม

Z(X)=10x1+12x2→สูงสุด

3x1+ x2≤12

x1+2x2≤5

x1≥4

x1≥0, x2 – จำนวนเต็ม

ตัวอย่างเช่น การใช้วิธีแบบกราฟิก:

X11eD11→X01= (3,1); £(D11)=42; X12eD12→X02= (4,0); ปอนด์(D12)=40.

ผลการแตกแขนงดังแสดงในรูปที่ 2.5

แผน X01 เป็นไปตามเงื่อนไขของปัญหา และเป็นไปตามเงื่อนไขต่อไปนี้: Z(X11)= £(D11)=42 > £(/)/) = 42 > £(D12) = 40 ดังนั้น แผน X °1= (3, 1) เป็นวิธีการแก้ปัญหา (7.11)-(7.13) กล่าวคือ คุณต้องใช้โหลดแรกสามหน่วยและโหลดที่สองหนึ่งหน่วย

2.1 สาขาและอัลกอริธึมที่ถูกผูกไว้

· เราพบวิธีแก้ไขปัญหาการเขียนโปรแกรมเชิงเส้นโดยไม่ต้องคำนึงถึงจำนวนเต็ม

· สร้างข้อจำกัดเพิ่มเติมเกี่ยวกับองค์ประกอบที่เป็นเศษส่วนของแผน

· เราพบวิธีแก้ไขปัญหาสองประการด้วยข้อจำกัดในส่วนประกอบ

· หากจำเป็น เราจะสร้างข้อจำกัดเพิ่มเติม ตามสี่กรณีที่เป็นไปได้ เราได้รับแผนจำนวนเต็มที่เหมาะสมที่สุดหรือสร้างปัญหาที่แก้ไม่ได้

อัลกอริทึมสำหรับสาขาและวิธีการผูกมัด

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

หากในบรรดาองค์ประกอบของแผน X0 มีตัวเลขเศษส่วน X0 จะไม่เป็นไปตามเงื่อนไขจำนวนเต็มและจำเป็นต้องดำเนินการเปลี่ยนผ่านไปยังแผนใหม่อย่างเป็นระเบียบจนกว่าจะพบวิธีแก้ไขปัญหา ให้เราแสดงวิธีการนี้ให้เสร็จสิ้น ขั้นแรกสังเกตว่า F(X0) ³ F(X) สำหรับแผน X ลำดับถัดไปใดๆ เนื่องจากจำนวนข้อจำกัดที่เพิ่มขึ้น

สมมติว่าแผนที่เหมาะสมที่สุด X0 ที่พบไม่ตรงตามเงื่อนไขของตัวแปรจำนวนเต็ม ดังนั้นเราจึงถือว่าในบรรดาส่วนประกอบต่างๆ นั้นมีตัวเลขเศษส่วน ตัวอย่างเช่น สมมติว่าตัวแปรใช้ค่าเศษส่วนในรูปของ X0 จากนั้นในแผนจำนวนเต็มที่เหมาะสมที่สุด ค่าของมันจะเป็นไปตาม อย่างน้อยน้อยกว่าหรือเท่ากับจำนวนเต็มเล็กที่ใกล้ที่สุด หรือมากกว่าหรือเท่ากับจำนวนเต็มขนาดใหญ่ที่ใกล้ที่สุด font-size:14.0pt">font-size:14.0pt">ลองค้นหาวิธีแก้ไขปัญหาการเขียนโปรแกรมเชิงเส้น (5) และ ( 6). แน่นอนว่าหนึ่งในสี่กรณีต่อไปนี้เป็นไปได้ที่นี่:

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

2. ปัญหาประการหนึ่งไม่สามารถแก้ไขได้ และอีกปัญหาหนึ่งมีแผนที่เหมาะสมที่สุด โดยมีองค์ประกอบเป็นเศษส่วน จากนั้นเราจะพิจารณาปัญหาที่สองและปัญหาของมัน แผนการที่เหมาะสมที่สุดเราเลือกองค์ประกอบหนึ่งซึ่งมีค่าเท่ากับจำนวนเศษส่วนและสร้างปัญหาสองข้อที่คล้ายกับปัญหา (5) และ (6)

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

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

3.2. หากค่าของฟังก์ชันวัตถุประสงค์มากกว่าในแผน ในบรรดาองค์ประกอบที่มีจำนวนเศษส่วน ควรใช้จำนวนใดจำนวนหนึ่งเหล่านี้ และสำหรับปัญหาที่กำลังพิจารณาแผนอยู่ จำเป็นต้องสร้างปัญหาสองข้อที่คล้ายกับ (5) และ (6)

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

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

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

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

1. ค้นหาวิธีแก้ไขปัญหาการเขียนโปรแกรมเชิงเส้น

2. สร้างข้อ จำกัด เพิ่มเติมสำหรับตัวแปรตัวใดตัวหนึ่งซึ่งค่าในแผนที่เหมาะสมที่สุดคือจำนวนเศษส่วน

3. ค้นหาวิธีแก้ไขปัญหา (5) และ (6) ซึ่งได้มาจากปัญหา (1)-(3) อันเป็นผลมาจากการเพิ่มข้อจำกัดเพิ่มเติม

4. หากจำเป็น ให้สร้างข้อจำกัดเพิ่มเติมสำหรับตัวแปรที่มีค่าเป็นเศษส่วน กำหนดปัญหาที่คล้ายคลึงกับปัญหา (5) และ (6) และค้นหาวิธีแก้ไข

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

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

ตัวอย่างการใช้ Branch และ Bound Method

เป็นตัวอย่างของกิ่งและวิธีผูก พิจารณาฟังก์ชัน z=4x1+x2+1®max ภายใต้ข้อจำกัด:

font-size:14.0pt">ให้ X0 = (0; 0), z0 = 1 - วิธีแก้ปัญหา "เหมาะสมที่สุด" เรามาทำขั้นตอนที่ 1 กัน อัลกอริธึมทั่วไปแล้วหาโดยใช้วิธีซิมเพล็กซ์แล้ว วิธีดูอัลซิมเพล็กซ์(ดูภาคผนวก 1) X1 ตามข้อจำกัด ดังนั้น X1 = (3; 0.5; 0; 1; 0; 2.5), z1 = 13.5 เนื่องจาก z1 เป็นเศษส่วน แผน X0 จึงยังคง "เหมาะสมที่สุด"

ตามจุดที่ 2 ของแผนของเรา เราจะสร้างระบบข้อจำกัดใหม่ 2 ระบบสำหรับ:

https://pandia.ru/text/79/453/images/image012_25.gif" alt="Description: http://*****/images/paper/93/79/4327993.png" width="108" height="98"> . !}

ลองทำจุดที่ 3 ของอัลกอริทึมกัน เริ่มต้นด้วยการแก้ปัญหาโดยใช้ โปรเซสเซอร์ตาราง Microsoft Excel (ภาคผนวก 2) และเราได้รับ X2 = (2; 1) z2= 10 เนื่องจาก z2 ≥ z0 แผน X0 จึง "เหมาะสมที่สุด"

มาแก้ปัญหากันเถอะ จากสมการสุดท้ายจะเห็นได้ชัดว่า x2 = 0 และตามมาด้วย x1 = 3 (ค่าสูงสุดที่เป็นไปได้) จากนั้น X3 = (3; 0), z3 = 13 ดังนั้นแผนนี้จึงเหมาะสมที่สุด (ตอนนี้ไม่มีเครื่องหมายคำพูด)

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

บทสรุป

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

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

บรรณานุกรม

1. อ. ชไรเวอร์. ทฤษฎีการเขียนโปรแกรมเชิงเส้นและจำนวนเต็ม มี 2 เล่ม; แปลจากภาษาอังกฤษ 1991 360s

2. ต.หู. การเขียนโปรแกรมจำนวนเต็มและไหลไปในเครือข่าย; แปลจากภาษาอังกฤษ 1974

3. - คณิตศาสตร์ชั้นสูง: การเขียนโปรแกรมทางคณิตศาสตร์- เด็กฝึกงาน - รุ่นที่ 2 2544 351ส.

4. - การเขียนโปรแกรมทางคณิตศาสตร์: บทช่วยสอน- ฉบับที่ 5, Stereotype-M: FISMAT, 2001 - 264 หน้า

5. , .: วิธีเศรษฐศาสตร์-คณิตศาสตร์และแบบจำลองประยุกต์: หนังสือเรียน. คู่มือสำหรับมหาวิทยาลัย/UNITI, 1999 - 391 น.

6. - แก้ไขโดย ศาสตราจารย์ - : การวิจัยปฏิบัติการทางเศรษฐศาสตร์; หนังสือเรียน คู่มือสำหรับมหาวิทยาลัย

ภาคผนวก 2

วิธีแก้ปัญหา z = 4x1 + x2 +1 ® สูงสุดภายใต้ข้อจำกัด:

ใช้โต๊ะ โปรเซสเซอร์ไมโครซอฟต์เอ็กเซล