โมเดลการเขียนโปรแกรมเชิงเส้นจำนวนเต็ม วิธีการของโกโมริในการแก้ปัญหาการเขียนโปรแกรมจำนวนเต็ม ตัวอย่างการแก้ปัญหาเศรษฐกิจ

วิธีการตัด วิธีโกโมริ

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

ปัญหาเชิงเส้น การเขียนโปรแกรมจำนวนเต็ม มีการกำหนดไว้ดังนี้: ค้นหาวิธีแก้ปัญหาดังกล่าว (แผน)ฉัน, ที่ที่ ฟังก์ชันเชิงเส้น

ใช้เวลาสูงสุดหรือ ค่าต่ำสุดภายใต้ข้อจำกัด

(8.2)

(8.3)

– จำนวนเต็ม (8.4)

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

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

วิธีการเพิ่มประสิทธิภาพจำนวนเต็มสามารถแบ่งออกเป็นสามกลุ่มหลัก: ก) วิธีการตัดแต่งกิ่ง; ข) วิธีการผสมผสาน- c) วิธีการโดยประมาณ มาดูวิธีการตัดอย่างละเอียดยิ่งขึ้น

ตารางที่ 1

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

มันจะต้องเป็นเส้นตรง
ควรตัดแผนที่ไม่ใช่จำนวนเต็มที่เหมาะสมที่สุดที่พบออก
ไม่ควรตัดแผนจำนวนเต็มใดๆ ออก

เรียกว่าข้อจำกัดเพิ่มเติมเกี่ยวกับคุณสมบัติเหล่านี้ การตัดที่ถูกต้อง.

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

ในรูปทรงหลายเหลี่ยมดั้งเดิมของสารละลายและตามวิธีแก้ปัญหาที่เหมาะสมที่สุดที่ได้รับจากรูปทรงหลายเหลี่ยมนี้จะเป็นจำนวนเต็ม (รูปที่ 8.1)

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

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

(8.5)

ดังนั้นทางออกที่ดีที่สุดสำหรับปัญหา (8.1)-(8.3) คือ i ซึ่งในตัวอย่าง β; - องค์ประกอบที่ไม่ใช่จำนวนเต็ม ในกรณีนี้ก็สามารถพิสูจน์ได้ว่าความไม่เท่าเทียมกันเกิดขึ้นจาก ฉัน-ถึงสมการของระบบ (8.5) มีคุณสมบัติทั้งหมดของจุดตัดปกติ

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

1. ใช้วิธีซิมเพล็กซ์ แก้ปัญหาข้อ (8.1)-(8.3) โดยไม่ต้องคำนึงถึงเงื่อนไขจำนวนเต็ม หากส่วนประกอบทั้งหมดของแผนผังที่เหมาะสมที่สุดเป็นจำนวนเต็ม แสดงว่าเหมาะสมที่สุดสำหรับปัญหาการเขียนโปรแกรมจำนวนเต็ม (8.1)-(8.4) หากปัญหาแรก (8.1)-(8.3) ไม่สามารถแก้ไขได้ (นั่นคือ ไม่มีขอบเขตที่เหมาะสมที่สุดหรือมีเงื่อนไขขัดแย้งกัน) ปัญหาที่สอง (8.1)-(8.4) ก็ไม่สามารถแก้ไขได้เช่นกัน
2. หากมีส่วนประกอบที่ไม่ใช่จำนวนเต็มในบรรดาองค์ประกอบของโซลูชันที่ดีที่สุด ให้เลือกส่วนประกอบที่มีค่ามากที่สุด ทั้งส่วนและตามสมการที่สอดคล้องกันของระบบ (8.5) ทำให้เกิดจุดตัดที่ถูกต้อง (8.6)
3. ด้วยการแนะนำตัวแปรจำนวนเต็มที่ไม่เป็นลบเพิ่มเติม ให้แปลงอสมการ (8.6) ให้เป็นสมการที่เทียบเท่าและรวมไว้ในระบบข้อจำกัด (8.2)
4. แก้ไขปัญหาที่ขยายออกไปโดยใช้วิธีซิมเพล็กซ์ หากพบแผนที่เหมาะสมที่สุดเป็นจำนวนเต็ม ปัญหาการเขียนโปรแกรมจำนวนเต็ม (8.1)–(8.4) จะได้รับการแก้ไข มิฉะนั้น ให้กลับไปที่ขั้นตอนที่ 2 ของอัลกอริทึม

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

1 ในอสมการ (8.6) มีสัญลักษณ์ ( ) หมายถึงเศษส่วนของจำนวน ส่วนจำนวนเต็มของจำนวน aเป็นจำนวนเต็มที่ใหญ่ที่สุด [ใน] ไม่เกิน ก. เศษส่วนของจำนวน– หมายเลข (a) เท่ากับความแตกต่างระหว่างตัวเลขนี้กับส่วนจำนวนเต็มนั่นคือ (ก) = ก-[ข]

ตัวอย่างเช่น สำหรับ (หมายเหตุ ตรง -3 ไม่ใช่ -2) และ

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

8.1. ในการซื้ออุปกรณ์คัดแยกเมล็ดพืช ชาวนาจะจัดสรรจำนวน 34 รัง หน่วย โดยต้องวางอุปกรณ์บนพื้นที่ไม่เกิน 60 ตารางเมตร ฐ. ชาวนาสามารถสั่งอุปกรณ์ได้ 2 ประเภท ได้แก่ เครื่องจักรที่ทรงพลังน้อยกว่า เช่น กมูลค่า 3 เดน หน่วยที่ต้องการพื้นที่การผลิต 3 ตร.ม. m (รวมการส่งผ่าน) และผลผลิตต่อกะ 2 ตันของเมล็ดพืช และเครื่องจักรที่ทรงพลังยิ่งกว่าเช่น ในมูลค่า 4 เดน ยูนิตครอบครองพื้นที่ 5 ตร.ม. ม. และผลผลิตต่อกะของเมล็ดพืชคุณภาพสูง 3 ตัน

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

สารละลาย.ให้เราแสดงด้วยจำนวนเครื่องตามลำดับประเภท กและ ใน,ผ่าน Z – ผลผลิตโดยรวม จากนั้นแบบจำลองทางคณิตศาสตร์ของปัญหาจะเกิดขึ้น

(!!!8.8)

โดยมีข้อจำกัด:

(8.2)

– จำนวนเต็ม (8.4)

ให้เรานำปัญหามาสู่รูปแบบมาตรฐานโดยการแนะนำตัวแปรที่ไม่เป็นลบเพิ่มเติม เราได้รับระบบข้อจำกัด:

(8.5)

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

ในรูป 8.2 โอเค แอลเอ็ม– พื้นที่การแก้ปัญหาที่เป็นไปได้ (8.D)–(8.3”) จำกัดด้วยเส้นตรง (1), (2), (3) และแกนพิกัด ล(2/3; 8) – จุดที่เหมาะสม แต่ไม่ใช่วิธีแก้ปัญหาที่เป็นจำนวนเต็ม (8.1")–(8.3"); (4) – เส้นตรงตัดสารละลายที่ไม่ใช่จำนวนเต็มออก โอเคเอ็นเอ็ม– พื้นที่ของการแก้ปัญหาที่เป็นไปได้ของปัญหาเพิ่มเติม (8.1")–(8.3"), (8.6"); ยังไม่มีข้อความ( 2; 7) – จุดของคำตอบจำนวนเต็มที่เหมาะสมที่สุด

ขั้นตอนที่ 1 ตัวแปรพื้นฐาน ตัวแปรที่ไม่ใช่พื้นฐาน

วิธีแก้ปัญหาพื้นฐานประการแรกคือการสมมติ

ของฉัน. ค่าฟังก์ชันเชิงเส้นที่สอดคล้องกัน

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

ยอมรับระบบข้อจำกัดตามเงื่อนไขของความสัมพันธ์ขั้นต่ำที่เกี่ยวข้อง:

เหล่านั้น. สมการการแก้ปัญหา (ไฮไลต์) คือสมการที่สาม ที่ เอ็กซ์ 2 = 8 ในสมการนี้ เอ็กซ์- = 0 และตัวแปรเปลี่ยนเป็นค่าที่ไม่ใช่พื้นฐาน เอ็กซ์ 5.

ขั้นตอนที่สองตัวแปรสำคัญ เอ็กซ์ 2, เอ็กซ์ 3, เอ็กซ์ 4.

ตัวแปรรอง g, xy

หลังจากการเปลี่ยนแปลงที่เราได้รับ

แปลงเป็นตัวแปรหลัก และในอันที่ไม่ใช่หลัก x4

ขั้นตอนที่สามตัวแปรหลัก x, เอ็กซ์ 2, เอ็กซ์ 3.

ตัวแปรที่ไม่ใช่ตัวแปรหลัก x4, x5

หลังจากการเปลี่ยนแปลงที่เราได้รับ

วิธีแก้ปัญหาพื้นฐาน เอ็กซ์, เหมาะสมที่สุดสำหรับปัญหา (8.1")–(8.3") () เนื่องจากในการแสดงออกของฟังก์ชันเชิงเส้น

ไม่มีตัวแปรที่ไม่ใช่แกนหลักที่มีค่าสัมประสิทธิ์บวก

อย่างไรก็ตามการแก้ปัญหา เอ็กซ์ 3 ไม่ตรงตามเงื่อนไขจำนวนเต็ม (8.4") เมื่อใช้สมการแรกกับตัวแปร x ซึ่งได้รับค่าที่ไม่ใช่จำนวนเต็มในคำตอบที่เหมาะสมที่สุด (2/3) เราจะสร้างข้อจำกัดเพิ่มเติม (8.6):

โปรดทราบว่าตาม (8.5) และ (8.6) เราใช้เศษส่วน สมาชิกอิสระที่มีป้ายเดียวกันซึ่งเขามีอยู่ในสมการและเศษส่วน ค่าสัมประสิทธิ์สำหรับตัวแปรรอง x 4 และ x- – โดยมีเครื่องหมายตรงกันข้าม

เนื่องจากเป็นเศษส่วน ,

แล้วเราก็เขียนอสมการสุดท้าย

(8.6")

โดยการแนะนำตัวแปรจำนวนเต็มเพิ่มเติม x6 ≥ 0 เราได้สมการที่เทียบเท่ากับอสมการ (8.6")

(8.7")

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

ขั้นตอนที่สี่ตัวแปรสำคัญ xโวลต์ เอ็กซ์ 2, x3, χβ

ตัวแปรที่ไม่ใช่ตัวแปรหลัก x4, x5

ไม่อนุญาตให้ใช้วิธีแก้ปัญหาพื้นฐาน

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

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

ขั้นวี.ตัวแปรหลักคือ x, x2, x3, x5

ตัวแปรที่ไม่ใช่ตัวแปรหลัก x4, x6

เราได้รับหลังจากการเปลี่ยนแปลง

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

ดังนั้น Zmax = 25 ที่เหมาะสมที่สุด โซลูชันจำนวนเต็ม X* = X 5 = (2; 7; 19; 0; 1; 0) เช่น ประสิทธิภาพสูงสุดสามารถรับเมล็ดพืชคุณภาพสูงได้ 25 ตันต่อกะโดยการซื้อเครื่องจักรประเภท L 2 เครื่องและประเภทเครื่องจักร 7 เครื่อง ในในเวลาเดียวกันพื้นที่ว่างของสถานที่จะอยู่ที่ 19 ตารางเมตร ม. m ยอดคงเหลือของเงินทุนที่จัดสรรเป็นศูนย์ เงินสำรองสำหรับการซื้อคือ 1 เครื่องในประเภท ใน(องค์ประกอบที่หกไม่มีความหมายที่มีความหมาย)

ความคิดเห็น สำหรับการตีความทางเรขาคณิตบนระนาบ Ox, x2 (ดูรูปที่ 8.2) ของจุดตัด (8.6") ตัวแปรที่รวมอยู่ในนั้นจำเป็น เอ็กซ์ 4 และ เอ็กซ์-แสดงผ่านตัวแปร x และ x2 เราได้รับ (ดูสมการที่ 2 และ 3 ของระบบข้อ จำกัด (8.5"))

(ดูเส้นตัด (4) ในรูปที่ 8.2)
8.2. มีเพียงพอ จำนวนมากท่อนซุงยาว 3 ม. ควรตัดท่อนไม้เป็นชิ้นงานสองประเภท: ยาว 1.2 และ 0.9 ม. และควรได้ชิ้นงานแต่ละประเภทอย่างน้อย 50 และ 81 ชิ้น ตามลำดับ แต่ละท่อนสามารถตัดเป็นชิ้นที่ระบุได้หลายวิธี: 1) ออกเป็น 2 ชิ้น แต่ยาว 1.2 เมตร; 2) สำหรับ 1 ชิ้น 1.2 ม. และ 2 ชิ้น 0.9 ม. 3) สำหรับท่อนไม้จำนวน 3 ชิ้น ชิ้นละ 0.9 เมตร จงหาจำนวนท่อนไม้ที่ตัดในแต่ละวิธีเพื่อให้ได้ท่อนไม้ประเภทใดก็ได้จากท่อนไม้จำนวนน้อยที่สุด

สารละลาย.ให้เราแสดงโดย เอ็กซ์() x2, x3 คือจำนวนบันทึกที่เลื่อยโดยใช้วิธี 1, 2 และ 3 ตามลำดับ จากสิ่งเหล่านี้คุณจะได้ช่องว่าง 2xj +x2 ยาว 1.2 ม. และ 2x x +3x2 ช่องว่าง ช่องละ 0.9 ม. ให้เราแสดงจำนวนบันทึกทั้งหมด ซี.จากนั้นแบบจำลองทางคณิตศาสตร์ของปัญหาจะเกิดขึ้น

โดยมีข้อจำกัด:

โดยการแนะนำตัวแปรเพิ่มเติม

เราลดระบบอสมการให้เป็นระบบสมการที่เทียบเท่ากัน:

(8.5")

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

ขั้นตอนที่สามตัวแปรสำคัญ xโวลต์ เอ็กซ์ 2.

ตัวแปรที่ไม่ใช่แกนหลัก เอ็กซ์ที่ เอ็กซ์ก , เอ็กซ์ 5.

นั่นคือด้วยโซลูชั่นที่เหมาะสมที่สุด

ปรากฎว่าสององค์ประกอบของการแก้ปัญหาที่ดีที่สุด ไม่เป็นไปตามเงื่อนไขจำนวนเต็ม (8.4") และส่วนประกอบมีส่วนจำนวนเต็มที่ใหญ่ที่สุด เอ็กซ์ 2. ตาม ∏ 2 อัลกอริธึมสำหรับการแก้ปัญหาการเขียนโปรแกรมจำนวนเต็ม (ดูหน้า 166) โดยใช้สมการที่สองที่มีตัวแปรนี้ เอ็กซ์ 2 เราสร้างข้อจำกัดเพิ่มเติม (8.6):

มาหาเศษส่วนกัน

และเขียนอสมการสุดท้ายลงในแบบฟอร์ม

(8.6")

โดยการแนะนำตัวแปรเพิ่มเติมที่เราได้รับ

สมการเทียบเท่ากับอสมการ (8.6"):

(8.7")

ให้เราแสดงตัวแปรเพิ่มเติม x6 จาก (8.7") และนำสมการผลลัพธ์เข้าสู่ระบบข้อจำกัดที่เรามีในขั้นตอนสุดท้าย III ขั้นตอนการแก้ปัญหา (8.1") - (8.3") (โดยไม่มีเงื่อนไขจำนวนเต็ม ).

ขั้นตอนที่สี่ ตัวแปรสำคัญ เอ็กซ์{, เอ็กซ์ที่ เอ็กซ์ 6.

ตัวแปรที่ไม่ใช่แกนหลัก เอ็กซ์ 3,x4, เอ็กซ์ 5.

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

ขั้นวี. ตัวแปรหลัก x); เอ็กซ์ 2,x3.

ตัวแปรที่ไม่ใช่ตัวแปรหลัก x4, x5, xb

นั่นคือด้วยโซลูชั่นที่เหมาะสมที่สุด

ผลลัพธ์วิธีแก้ปัญหาที่ดีที่สุดสำหรับปัญหาเพิ่มเติม (8.1")–(8.3") (8.6") ไม่ตรงตามเงื่อนไขจำนวนเต็ม (8.4") อีกครั้ง ตามสมการแรกที่มีตัวแปร Xj ได้รับค่าที่ไม่ใช่จำนวนเต็มในตำแหน่งที่เหมาะสมที่สุด

โซลูชัน () เราปล่อยให้ขีดจำกัดเพิ่มเติมที่สอง

การอ่าน (8.6):

ที่เรานึกขึ้นได้

การใช้ตัวแปรเพิ่มเติม

เราลดความไม่เท่าเทียมกันนี้ให้เป็นสมการที่เทียบเท่า ซึ่งเรารวมไว้ในระบบข้อจำกัดที่ได้รับที่ขั้นตอนสุดท้าย V ซึ่งเป็นขั้นตอนในการแก้ปัญหาเพิ่มเติม (8.G")–(8.3"), (8.6") โดยใช้ วิธีเริม

ขั้นตอน VI ตัวแปรสำคัญ xโวลต์ เอ็กซ์ 2, เอ็กซ์ที่ เอ็กซ์ต

ตัวแปรที่ไม่ใช่แกนหลัก เอ็กซ์ 4, X-, x 6.

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

ขั้นตอนที่เจ็ด ตัวแปรสำคัญ xโวลต์ เอ็กซ์เสื้อ x3, เอ็กซ์ช

ตัวแปรที่ไม่ใช่แกนหลัก xโวลต์ เอ็กซ์ 6, เอ็กซ์ต

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

ควรสังเกตว่าในนิพจน์ผลลัพธ์ของฟังก์ชันเชิงเส้น Z ไม่มีตัวแปรรอง เอ็กซ์ง) และ เอ็กซ์ 6. ซึ่งหมายความว่า โดยทั่วไปแล้ว มีชุดคำตอบที่เหมาะสมที่สุดจำนวนอนันต์ (ใดๆ ไม่จำเป็นต้องเป็นจำนวนเต็ม) โดยที่ Z" = Zmjn = 46 คำตอบเหล่านี้ได้มาจากค่าของตัวแปรที่ไม่ใช่ตัวแปรหลัก เอ็กซ์ 7 (รวมอยู่ในนิพจน์สำหรับ Z) เท่ากับศูนย์(เช่น เมื่อ เอ็กซ์ 7 = 0) และที่ ใดๆค่าของตัวแปรที่ไม่ใช่พื้นฐาน x5 และ เอ็กซ์ 6 (ไม่รวมอยู่ในนิพจน์สำหรับ Z) ซึ่งระบบข้อจำกัด "อนุญาต" ที่จะยอมรับ: 0<лг5 เอ็กซ์ 5 ≤ 1 และ 0< x(i ≤ 1 แต่เนื่องจากเงื่อนไขจำนวนเต็ม ตัวแปร เอ็กซ์-และ เอ็กซ์(> รับได้เฉพาะค่า 0 หรือ 1 เท่านั้น ดังนั้น ปัญหาจะมีจำนวนเต็มสี่วิธีในการแก้ปัญหาที่เหมาะสมที่สุดเมื่อใด เอ็กซ์และ *6 ในการรวมกันใด ๆ จะใช้ค่า 0 หรือ 1 และ เอ็กซ์ 7 = 0. การแทนที่ค่าเหล่านี้ลงในระบบข้อ จำกัด ในขั้นตอนที่ 7 เราจะพบวิธีแก้ปัญหาที่ดีที่สุดเหล่านี้:

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

ดังนั้น Zmin=46 สำหรับคำตอบจำนวนเต็มที่เหมาะสมที่สุด (5; 41; 0), (6; 39; 1), (7; 36; 3), (6; 38; 2) เมื่อบันทึกวิธีแก้ปัญหาที่เหมาะสมที่สุด เราจะเหลือเพียงสามองค์ประกอบแรก โดยแสดงจำนวนบันทึกที่ถูกตัดตามวิธีที่ 1, 2 และ 3 ตามลำดับ และไม่รวมองค์ประกอบสี่ส่วนสุดท้ายซึ่งไม่มีความหมายทางความหมาย

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

จะเห็นได้ว่าการแก้ปัญหานั้นสั้นกว่า

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

มันควรจะเป็นเส้นตรง

ควรตัดแผนที่ไม่ใช่จำนวนเต็มที่เหมาะสมที่สุดที่พบออก

ไม่ควรตัดทอนแผนจำนวนเต็มใดๆ

ข้อจำกัดเพิ่มเติมที่มีคุณสมบัติเหล่านี้เรียกว่าจุดตัดที่ถูกต้อง

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

การกดตัวแปรหลัก *1, *2, ตัวแปรใหม่ Xm+1, Xm+2, ..., Xm+1, โซลูชั่น

Xt ถึง neo-x" เหมาะสมที่สุด

(8.5)

องค์ประกอบที่ไม่ใช่จำนวนเต็ม ในกรณีนี้สามารถพิสูจน์ได้ว่าความไม่เท่าเทียมกัน

(P, ) - (ก," m+\)xm+1 ■ -~(ที่ )Xn ^ 0, (* )

เกิดจากสมการ /th ของระบบ (8.5) มีคุณสมบัติทั้งหมดของจุดตัดปกติ

ในการแก้ปัญหาการเขียนโปรแกรมเชิงเส้นจำนวนเต็ม (8.1)-(8.4) โดยใช้วิธี Gomori จะใช้อัลกอริธึมต่อไปนี้:

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

(8.3) ไม่สามารถแก้ไขได้ (นั่นคือ ไม่มีค่าที่เหมาะสมขั้นสุดท้ายหรือเงื่อนไขขัดแย้งกัน) ดังนั้นปัญหาที่สอง (8.1)-(8.4) ก็ไม่สามารถแก้ไขได้เช่นกัน

2. หากในบรรดาองค์ประกอบของวิธีแก้ปัญหาที่ดีที่สุดนั้นมีองค์ประกอบที่ไม่ใช่จำนวนเต็ม ให้เลือกส่วนประกอบที่มีส่วนจำนวนเต็มที่ใหญ่ที่สุดและใช้สมการที่สอดคล้องกันของระบบ (8.5) ให้สร้างจุดตัดที่ถูกต้อง (8.6)

3. โดยการเพิ่มตัวแปรจำนวนเต็มที่ไม่เป็นลบ ให้แปลงอสมการ (8.6) ให้เป็นสมการที่เทียบเท่ากัน

(P() - |a/ t+1 )*t+1- ■-(a|"l )xn + xn+1 > (®*^)

และรวมไว้ในระบบข้อจำกัด (8.2)

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

ปัญหาการเขียนโปรแกรมจำนวนเต็ม (8.1)-(8.4) ได้รับการแก้ไข มิฉะนั้น ให้กลับไปที่ขั้นตอนที่ 2 ของอัลกอริทึม

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

^8.1. ในการซื้ออุปกรณ์คัดแยกเมล็ดพืช ชาวนาจะจัดสรรจำนวน 34 รัง หน่วย โดยต้องวางอุปกรณ์บนพื้นที่ไม่เกิน 60 ตารางเมตร m. ชาวนาสามารถสั่งซื้ออุปกรณ์ได้สองประเภท: เครื่องจักรประเภท A ที่ทรงพลังน้อยกว่าซึ่งมีราคา 3 เดน หน่วยที่ต้องการพื้นที่การผลิต 3 ตร.ม. เมตร (รวมระยะผ่าน) และให้ผลผลิต 2 ตันต่อกะ และเครื่องจักรประเภท B ที่ทรงพลังกว่าซึ่งมีราคา 4 Den ยูนิตครอบครองพื้นที่ 5 ตร.ม. เมตรและให้ผลผลิตเมล็ดพืชคุณภาพสูง 3 ตันต่อกะ

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

สารละลาย. ให้เราแสดงด้วย x\, x2 จำนวนเครื่องจักรประเภท A และ B ตามลำดับ และโดย Z คือผลผลิตทั้งหมด จากนั้นแบบจำลองทางคณิตศาสตร์ของปัญหาจะอยู่ในรูปแบบ:

ในรูป 8.2 OKM - พื้นที่ของแนวทางแก้ไขปัญหาที่เป็นไปได้ (8.1 ") - (8.3") จำกัด ด้วยเส้นตรง (1), (2), (3) และแกนพิกัด />(2/3; 8) - จุดของวิธีแก้ปัญหาที่เหมาะสมที่สุด แต่ไม่ใช่จำนวนเต็ม (8.1") - (8.3"); (4) - เส้นตรงตัดสารละลายที่ไม่ใช่จำนวนเต็มออก 0№М - พื้นที่ของการแก้ปัญหาที่เป็นไปได้ของปัญหาเพิ่มเติม (8.1 ') - (8.3'), (8.61) M2; 7) - จุดของคำตอบจำนวนเต็มที่เหมาะสมที่สุด

ขั้นตอนที่ 1 ตัวแปรหลัก x3, x4, *5; ตัวแปรที่ไม่ใช่พื้นฐาน X\, X2

x3	= 60 -	จ่า! - 5x2,
x4	= 34 -	Zx) - 4x2,
x5	= 8	- *2>
	ซี = 2x)	+ Zx2.

วิธีแก้ปัญหาพื้นฐานข้อแรก X\ = (0; 0; 60; 34; 8) สามารถใช้ได้ ค่าฟังก์ชันเชิงเส้นที่สอดคล้องกัน = 0

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

HG = 1ШП|т;т;Т| = 8,

เหล่านั้น. สมการการแก้ปัญหา (ไฮไลต์) คือสมการที่สาม เมื่อ *2 = 8 ในสมการนี้ X5 = 0 และตัวแปร X5 กลายเป็นค่าที่ไม่ใช่พื้นฐาน

ขั้นตอนที่สอง ตัวแปรหลัก x2, x3, x*; ตัวแปรที่ไม่ใช่ตัวแปรหลัก Xx X5

{

(8.6)

ด้วยการแนะนำตัวแปรจำนวนเต็มเพิ่มเติม x6 > O เราจะได้สมการที่เทียบเท่ากับอสมการ (8.6")

~1*5 + Xb = °" ^8"7 ^

ขั้นตอนที่สี่ ตัวแปรพื้นฐาน X), *2, xs> *b'> ตัวแปรที่ไม่ใช่พื้นฐาน *1, *2-

X1 = z - 3*4 +

x3 = 18 + x4 +___ x5,

x6 - + ^x4 + z"x5-

วิธีแก้ไขพื้นฐาน X4 = (y; 8; 18; 0; 0; -y) ไม่สามารถยอมรับได้ (โปรดทราบว่าหลังจากรวมสมการเพิ่มเติมที่สอดคล้องกับจุดตัดที่ถูกต้องในระบบข้อจำกัดแล้ว ก็จะได้คำตอบพื้นฐานที่ไม่ถูกต้องเสมอ)

เพื่อให้ได้วิธีแก้ปัญหาพื้นฐานที่ยอมรับได้ จำเป็นต้องแปลงเป็นตัวแปรหลักซึ่งรวมเข้ากับสัมประสิทธิ์เชิงบวกในสมการที่เทอมอิสระเป็นลบ เช่น *1 หรือ x$ (ในขั้นตอนนี้ เราไม่พิจารณาฟังก์ชันเชิงเส้น) เราแปลเป็นตัวแปรพื้นฐาน เช่น ตัวแปร X5

ขั้นวี. ตัวแปรหลัก X\, X2, X3, X5; ตัวแปรที่ไม่ใช่พื้นฐาน R], X£

หลังจากการเปลี่ยนแปลงเราได้รับ:

แอลจี| = 2 - x4 + 2x6,

*2 = 7 + 2х* ~ 2х("

x3 = 19 + -x4 + -x6,

*5 = 1 - 2х* + 2х6’

2 = 25-|x4--|x6

^5 =(2; 7; 19; 0; 1;0);^ = 25.

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

ดังนั้น 2max = 25 สำหรับคำตอบจำนวนเต็มที่เหมาะสมที่สุด X* - X$ =(2; 7; 19; 0; 1; 0) เช่น สามารถรับผลผลิตเมล็ดพืชคุณภาพสูงสูงสุด 25 ตันต่อกะได้โดยการซื้อเครื่องจักรประเภท A จำนวน 2 เครื่อง และประเภท B\ จำนวน 7 เครื่อง ในขณะที่พื้นที่ว่างของสถานที่จะอยู่ที่ 19 ตร.ม. m ยอดคงเหลือของเงินทุนที่จัดสรรเท่ากับ 0 ในทุนสำรองซื้อมีเครื่องจักรประเภท B 1 เครื่อง (องค์ประกอบที่หกไม่มีความหมายที่มีความหมาย)

ความคิดเห็น สำหรับการตีความทางเรขาคณิตบนระนาบ Ox\Xr (ดูรูปที่ 8.2) ของจุดตัด (8.6") จำเป็นต้องแสดงตัวแปร x4 และ x$ ที่รวมอยู่ในตัวแปรนั้นผ่านตัวแปร XI และ x2 เราได้รับ (ดู สมการที่ 2 และ 3 ของระบบข้อ จำกัด (8.5 "):

y - y (34 - 3x, - 4x2) - y (8 - x2) 0 ปอนด์ หรือ x, + 2x2 16 ปอนด์

(ดูเส้นตัด (4) ในรูปที่ 8.2)>

^8.2. มีท่อนไม้จำนวนมากพอสมควรที่มีความยาว 3 เมตร ควรตัดท่อนออกเป็นสองประเภท: ยาว 1.2 ม. และยาว 0.9 ม. และแต่ละประเภทควรมีอย่างน้อย 50 ชิ้น และ 81 ชิ้น ตามลำดับ แต่ละท่อนสามารถตัดเป็นชิ้นที่ระบุได้หลายวิธี: 1) แบ่งออกเป็น 2 ชิ้น ชิ้นละ 1.2 ม. 2) สำหรับ 1 ชิ้น 1.2 ม. และ 2 ชิ้น 0.9 ม. 3) สำหรับ 3 ชิ้น ชิ้นละ 0.9 ม. ค้นหาจำนวนบันทึก

เลื่อยแต่ละวิธีเพื่อให้ได้ชิ้นงานชนิดใดก็ได้จากท่อนไม้ที่น้อยที่สุด

สารละลาย. ให้เราแสดงด้วย х\, хі, хм จำนวนบันทึกที่ถูกตัดตามวิธี 1, 2 และ 3 จากนั้นคุณจะได้ช่องว่าง2хі + *2 ช่องละ 1.2 ม. และช่องว่าง 2l\ + 3x2 ช่องละ 0.9 ม. เราแสดงจำนวนบันทึกทั้งหมดเป็น I จากนั้นแบบจำลองทางคณิตศาสตร์ของปัญหาจะอยู่ในรูปแบบ:

ผม 2x, + x2 - x4 = 50,+ (?คุณ) ที่ไหน [ใช่] -ทั้งส่วนและ (ย) = คุณ ~ [y] ~ส่วนที่เป็นเศษส่วน

[h] เราพบวิธีแก้ปัญหาพื้นฐานที่ยอมรับได้ โดยพิจารณาจาก บรรทัดใหม่อนุญาตเช่น ฉัน = n + 1.

ก) ถ้าสัมประสิทธิ์ทั้งหมด UC> 0 แสดงว่าปัญหาไม่มีทางแก้ไข (เช่น ปัญหาจำนวนเต็มได้รับการแก้ไขแล้ว)
b) มิฉะนั้น ให้ค้นหาดัชนี ถึงเช่นนั้น

(เกณฑ์การเข้าสำหรับ พื้นฐานใหม่- โปรดทราบว่าการเลือกองค์ประกอบการแก้ไข ที่และ*ไม่เปลี่ยนเครื่องหมายเกณฑ์ อจ.

[4] ถ้าเข้า. ตารางใหม่มีอย่างน้อยหนึ่งอัน x3และทำซ้ำขั้นตอนเหล่านี้หลาย ๆ ครั้งตามที่จำเป็น

[~5~| หากผลเฉลยที่ดีที่สุดเป็นจำนวนเต็ม แสดงว่าปัญหาได้รับการแก้ไขแล้ว มิฉะนั้นคุณจะต้องกลับไปสู่จุดเดิม

ตัวอย่าง 4.6.1 แก้ปัญหาจำนวนเต็มโดยใช้วิธีโกโมริ

สารละลาย. หลังจากเพิ่มตัวแปรเสริมแล้ว เราประสบปัญหาการเขียนโปรแกรมเชิงเส้นในรูปแบบมาตรฐานดังต่อไปนี้:

ด้วยเมทริกซ์

ถึง= 1 ต

โดยใช้วิธีการหมุน กรอกตารางต่อไปนี้ องค์ประกอบความละเอียด - 6*

เค" = 2 ต

องค์ประกอบความละเอียด - 1/2*

เอ็กซ์เข้า^0) ดังนั้นโปรแกรม (xi = 11/3, เอ็กซ์ 2 = 5) จะให้ฟังก์ชันทางเศรษฐกิจสูงสุด z,เท่ากับ 1370/3 = 45b|, t.s. z= z สูงสุด = 456§ -

ตั้งแต่นี้เป็นต้นมา โปรแกรมที่เหมาะสมที่สุดไม่ใช่จำนวนเต็ม เราใช้อัลกอริทึม Gomori เพื่อค้นหาโปรแกรมจำนวนเต็มที่เหมาะสมที่สุด เป็นสตริงบนพื้นฐานที่เราสร้างขึ้น สายพิเศษจากเศษส่วนขององค์ประกอบทั้งหมด ให้เลือกบรรทัดที่สอง (ดัชนี 7' = 1) มากรอกตาราง 3" โดยเพิ่มแถวเพิ่มเติม (4.14) ลงในตาราง 3 โดยมีเศษส่วนสำหรับตัวแปรเพิ่มเติม Ж5 และคอลัมน์เพิ่มเติม เราได้รับ

เค" = 4 ต

หลังจากเพิ่มบรรทัดใหม่ ตารางด้านเดียว 3" จะไม่สอดคล้องกับวิธีแก้ปัญหาพื้นฐานที่ยอมรับได้อีกต่อไปสำหรับปัญหาที่อธิบายไว้ เราพบวิธีแก้ปัญหาพื้นฐานที่ยอมรับได้ โดยพิจารณาจากบรรทัดใหม่ที่จะแก้ไข เช่น /" = 5

เราพบคอลัมน์การแก้ไขเช่น ดัชนี ถึง"เช่นนั้น

(หลักเกณฑ์ในการเข้าเกณฑ์ใหม่) องค์ประกอบความละเอียด - (-2/3*) โปรดทราบว่าการเลือกองค์ประกอบการแก้ปัญหาดังกล่าวไม่ได้เปลี่ยนเครื่องหมายของเกณฑ์ อจ.

มาเติมตาราง simplex 4 กัน

ตารางที่ 4		เอ็กซ์2

	เอ็กซ์2

ค่าของเกณฑ์ทั้งหมด ^ 0, ( เอ็กซ์เข้า^0) ดังนั้น โปรแกรม (xi = 3, x 2 = 6, x±= 1) ให้ฟังก์ชันทางเศรษฐกิจสูงสุด r เท่ากับ 450, t.s z = ซามา^= 450 โปรแกรมที่เหมาะสมที่สุดนี้คือจำนวนเต็ม -

ตัวอย่าง 4.6.2 แก้ปัญหาจำนวนเต็มโดยใช้วิธีโกโมริ

สารละลาย. มีปัญหาการเขียนโปรแกรมเชิงเส้นกับเมทริกซ์

มากรอกตารางซิมเพล็กซ์ด้วยโปรแกรมเริ่มต้นกัน

ตารางที่ 1

ถึง= 1 ต

โดยใช้วิธีการหมุน กรอกตารางต่อไปนี้ องค์ประกอบความละเอียด - 1*

ตารางที่ 2				เอ็กซ์2

องค์ประกอบที่อนุญาต - 5*

ตารางที่ 3

ค่าของเกณฑ์ทั้งหมด ^ 0, ( เอ็กซ์เข้า^0) ดังนั้น โปรแกรม (xi = 12/5, 24 = 1/5, 25 = 28/5) ให้ฟังก์ชันทางเศรษฐกิจขั้นต่ำ r เท่ากับ -11/5 = -2.2 เช่น z =

~นาที= -2.2.

เนื่องจากโปรแกรมที่เหมาะสมที่สุดนี้ไม่ใช่จำนวนเต็ม เราจึงใช้อัลกอริทึมของ Gomori เพื่อค้นหาโปรแกรมจำนวนเต็มที่เหมาะสมที่สุด ในฐานะที่เป็นสตริงบนพื้นฐานของที่เราสร้างสตริงเพิ่มเติมจากส่วนที่เป็นเศษส่วนขององค์ประกอบ ss เราเลือกเช่นแถวที่สาม (ดัชนี r = 5) ที่มีส่วนที่เป็นเศษส่วนสูงสุด มากรอกตาราง 3" กัน โดยเพิ่มบรรทัดเพิ่มเติม (4.14) ลงในตารางที่ 3 โดยมีเศษส่วนของบรรทัดที่สามสำหรับตัวแปรเพิ่มเติม xq (บรรทัดนี้อนุญาตให้คุณตัดออกจากส่วนของพื้นที่โปรแกรมที่มีจุดที่มีพิกัดที่ไม่ใช่ตัวเลข) และคอลัมน์เพิ่มเติม เราได้รับ

ตารางที่ 3"





		จี - -และ

เค" = 3 ต

หลังจากเพิ่มบรรทัดใหม่ ตารางด้านเดียว 3" จะไม่สอดคล้องกับวิธีแก้ปัญหาพื้นฐานที่ยอมรับได้อีกต่อไปสำหรับปัญหาที่อธิบายไว้ เราพบวิธีแก้ปัญหาพื้นฐานที่ยอมรับได้ โดยพิจารณาถึงบรรทัดใหม่ที่จะแก้ไข เช่น ฉัน" = 6.

เราพบคอลัมน์การแก้ไขเช่น ดัชนี ถึง"เช่นนั้น

(หลักเกณฑ์ในการเข้าเกณฑ์ใหม่) องค์ประกอบความละเอียด - (-3/5*) โปรดทราบว่าการเลือกองค์ประกอบการแก้ปัญหาดังกล่าวไม่ได้เปลี่ยนเครื่องหมายของเกณฑ์ อจ.

มาเติมตาราง simplex 4 กัน

ตารางที่ 4

ค่าของเกณฑ์ทั้งหมด ^ 0, ( เอ็กซ์เข้า^0) ดังนั้นโปรแกรม (x= 2, เอ็กซ์2 = 0, xs = 1, เอ็กซ์ 4 = 0, f 5 = 5) จะให้ฟังก์ชันทางเศรษฐกิจขั้นต่ำ z 9 เท่ากับ (-2) t.s. ซี =-min = - 2 โปรแกรมที่เหมาะสมที่สุดนี้คือจำนวนเต็ม -

ปัญหา 4.6.1. แก้ปัญหาจำนวนเต็มโดยใช้วิธีโกโมริ