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

กราฟขอบเขตที่เป็นไปได้ของปัญหาของคุณ บริเวณที่เป็นไปได้คือพื้นที่ในอวกาศที่กำหนดโดยข้อจำกัดเชิงเส้นของปัญหา ตัวอย่างเช่น หากปัญหาของคุณมีความไม่เท่ากัน x + 2y > 4, 3x - 4y < 12, x > 1 และ y > 0 คุณสร้างกราฟจุดตัดของพื้นที่เหล่านี้เป็นพื้นที่ที่เป็นไปได้

ค้นหาจุดมุมของภูมิภาค หากปัญหาของคุณแก้ไขได้ จะมีจุดหรือมุมแหลมที่มองเห็นได้ในภูมิภาคของคุณ ทำเครื่องหมายจุดเหล่านี้บนกราฟของคุณ

คำนวณพิกัดของจุดเหล่านี้ หากคุณวาดกราฟบริเวณที่เป็นไปได้อย่างดี คุณจะรู้พิกัดของจุดมุมในทันที หากไม่เป็นเช่นนั้น คุณสามารถคำนวณด้วยมือได้โดยการแทนที่ความไม่เท่าเทียมกันของคุณเข้าด้วยกันแล้วแก้หา x และ y ในตัวอย่างที่กำหนด คุณจะพบ (4,0) เป็นจุดมุม เช่นเดียวกับ (1,1.5)

แทนที่จุดมุมเหล่านี้ลงในฟังก์ชันวัตถุประสงค์ของปัญหาการโปรแกรมเชิงเส้น คุณจะมีคำตอบมากเท่ากับที่คุณทำคะแนนจากมุม ตัวอย่างเช่น สมมติว่าฟังก์ชันวัตถุประสงค์ของคุณคือการเพิ่มฟังก์ชัน x + y ให้สูงสุด ในตัวอย่างนี้ คุณจะมีสองคำตอบ: คำตอบสำหรับประเด็น (4,0) และคำตอบสำหรับประเด็น (1,1.5) คำตอบที่ได้คะแนนเหล่านี้คือ 4 และ 2.5 ตามลำดับ

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

อ้างอิง

เกี่ยวกับผู้เขียน

เครดิตภาพ