3.2. Illustration with an exampleFo

3.2. Illustration with an example

For the sake of clearly describing the concept of proposed method, we consider the following ILP problem
with three constraints and two variables:
maximize z= 7x1 +10x2
subject to
x1 + 3x2 < 6;
7x1 + x2 < 35;
x1 + 2x2 < 2;
x1; x2 >0 and are integers.

Step 1: Solve the relaxed problem to get the optimum point A(4.5, 3.5) as shown in Fig. 1.

Step 2: Select (5, 0) and (0, 2) to calculate z
ð5;0Þ ¼ 35 and z
ð0;2Þ ¼ 20. In this case, we find that (5, 0) is the nearest
extreme point to A and designate (5, 0) as B.

Step 3: Draw a line passing through B with the same slope of objective function. After that we obtain a new
intersection C and the first subspace S1. Then we add new constraint BC and remove irrelative constraints
x1 + 2x2 >2 as shown in Fig. 2. The original problem could be revised as below:
maximize z = 7x1 + 10x2
subject to
x1 +3x2 < 6;
7x1 +x2 35;
x1; x2 > 0 and are integers.

Step 4: Use B&B procedure to obtain optimum solution in subspace S1, we could get the maximum value z = 58 when x1 = 4 and x2 = 3. It is also the optimum integer solution in the original space and we could claim that this is the solution of the original ILP problem.

ผลลัพธ์ (ไทย) 1:

3.2. ภาพประกอบพร้อมตัวอย่างเพื่อประโยชน์ในการอธิบายแนวคิดของวิธีการนำเสนออย่างชัดเจน เราพิจารณาปัญหา ILP ต่อไปนี้ด้วยข้อจำกัดสามและสองตัวแปร:ให้ z = 7 x 1 x 2 + 10ขึ้นอยู่กับ x1 + 3 x 2 < 67 x 1 + x2 < 35x1 + 2 x 2 < 2x1 x2 > 0 และมีจำนวนเต็มขั้นตอนที่ 1: แก้ไขปัญหาอาชีพจะได้รับ A(4.5, 3.5) จุดสูงสุดดังแสดงในรูปที่ 1ขั้นตอนที่ 2: เลือก (5, 0) และ (0, 2) เพื่อคำนวณ zð5; 0Þ ¼ 35 และ zð0; 2Þ ¼ 20 ในกรณีนี้ เราพบว่า (5, 0) จะให้สุดขีดจุด A และกำหนด (5, 0) เป็น bขั้นตอนที่ 3: วาดเส้นผ่าน B มีความลาดชันเดียวกันของฟังก์ชันวัตถุประสงค์ หลังจากที่ เราได้รับใหม่จุดตัด C และ subspace แรก S1 จากนั้นเราเพิ่มข้อจำกัดใหม่ BC และลบข้อจำกัด irrelativex1 + 2 x 2 > 2 ดังแสดงในรูป 2 สามารถแก้ไขปัญหาเดิม: ด้านล่างให้ z = 7 x 1 + 10 x 2ขึ้นอยู่กับ x1 + 3 x 2 < 67 x 1 + x2 < 357 x 1 + 10 x 2 > 35x1 x2 > 0 และมีจำนวนเต็มขั้นตอนที่ 4: ใช้ B & B กระบวนการแก้ปัญหาที่ดีที่สุดใน subspace S1 เราจะได้รับค่าสูงสุด z = 58 เมื่อ x1 = x2 และ 4 = 3 ก็ยังแก้ไขปัญหาจำนวนเต็มสูงสุดในพื้นที่เดิม และเราจะอ้างว่า เป็นการแก้ปัญหาของปัญหา ILP เดิม

ผลลัพธ์ (ไทย) 2:

3.2 ภาพประกอบด้วยตัวอย่างเพื่อประโยชน์ในการได้อย่างชัดเจนอธิบายแนวคิดของวิธีที่นำเสนอให้เราพิจารณาปัญหาดังต่อไปนี้ ILP มีสามข้อ จำกัด และสองตัวแปร: เพิ่ม Z = 7x1 + 10x2 อาจมีการX1 + 3x2 <6; 7x1 + X2 <35; X1 + 2x2 <2; X1; . X2> 0 และมี integers ขั้นตอนที่ 1: แก้ปัญหาผ่อนคลายที่จะได้รับจุด A ที่ดีที่สุด (4.5, 3.5) ดังแสดงในรูป 1. ขั้นตอนที่ 2: เลือก (5, 0) และ (0, 2) เพื่อคำนวณ Z ? D5; 0TH ¼ 35 และ Z D0; 2th ¼ 20. ในกรณีนี้เราจะพบว่า (5, 0) ที่ใกล้ที่สุดจุดที่รุนแรงเป็น A และกำหนด (5, 0) เป็นบีขั้นตอนที่ 3: วาดเส้นผ่าน B กับความลาดชันเดียวกันของฟังก์ชั่นวัตถุประสงค์ หลังจากที่เราได้รับใหม่แยก C และสเปซแรก S1 จากนั้นเราก็เพิ่มข้อ จำกัด ใหม่ BC และลบข้อ จำกัด irrelative X1 + 2x2> 2 ดังแสดงในรูป 2. ปัญหาเดิมจะได้รับการแก้ไขดังต่อไปนี้: เพิ่ม Z = 7x1 + 10x2 อาจมีการX1 + 3x2 <6; 7x1 + X2 <35; 7x1 + 10x2> 35; X1; . X2> 0 และมี integers ขั้นตอนที่ 4: ใช้ B & B ขั้นตอนเพื่อให้ได้วิธีการแก้ปัญหาที่ดีที่สุดในสเปซ S1 เราสามารถได้รับค่า Z สูงสุด = 58 เมื่อ X1 = 4 และ X2 = 3. นอกจากนี้ยังเป็นวิธีการแก้ปัญหาจำนวนเต็มที่เหมาะสมในพื้นที่เดิม และเราอาจจะอ้างว่านี่เป็นวิธีการแก้ปัญหาของ ILP เดิม

ผลลัพธ์ (ไทย) 3:

3.2 . ภาพประกอบตัวอย่างเพื่อให้ชัดเจนอธิบายแนวคิดของวิธีที่เสนอจะพิจารณาตามปัญหาส.กับสามข้อจำกัดและสองตัวแปร :เพิ่ม 7x1 Z = + 10x2ภายใต้x1 + 3x2 < 6 ;7x1 X2 + < 3 ;x1 + 2x2 < 2X1 ; x2 > 0 และเป็นจำนวนเต็ม .ขั้นตอนที่ 1 : แก้ไขผ่อนคลายปัญหาที่จะได้รับที่จุด A ( 4.5 , 3.5 ) ดังแสดงในรูปที่ 1ขั้นตอนที่ 2 : เลือก ( 5 , 0 ) และ ( 1 , 2 ) คำนวณหา ซีð 5 ; 0 Þ¼ 35 และ Zð 0 2 Þ¼ 20 ในกรณีนี้ เราพบว่า ( 5 , 0 ) ที่ใกล้ที่สุดรุนแรงและกำหนดจุด ( 5 , 0 ) Bขั้นตอนที่ 3 : วาดเส้นผ่าน B ที่มีความลาดชันเดียวกันของฟังก์ชันวัตถุประสงค์ หลังจากที่เราได้รับใหม่แยก C และย่อยแรก S1 . แล้วเราเพิ่มเงื่อนไขใหม่ และลบข้อ จำกัด ที่ไม่สัมพันธ์กัน บีซีx1 + 2x2 > 2 ดังแสดงในรูปที่ 2 ปัญหาเดิมสามารถแก้ไขดังนี้เพิ่ม 7x1 Z = + 10x2ภายใต้x1 + 3x2 < 6 ;7x1 X2 + < 3 ;7x1 + 10x2 > 35 ;X1 ; x2 > 0 และเป็นจำนวนเต็ม .ขั้นตอนที่ 4 : ใช้ บีแอนด์บี เพื่อให้ได้โซลูชั่นที่เหมาะสมในขั้นตอนย่อย : เราสามารถได้รับสูงสุด ค่า Z = ตอนที่ 1 = 4 และ x2 = 3 ก็ยังเป็นโซลูชั่นที่เหมาะสมในพื้นที่เดิมและจำนวนเต็มเราสามารถอ้างว่า นี่คือทางออกของปัญหาส. เดิม