การแก้ปัญหากำหนดการเชิงเส้นโดยวิธีการใช้กราฟ
ในการแก้ปัญหากำหนดการเชิงเส้นนั้นต้องเริ่มต้นด้วยการสร้างแบบจำลองทางคณิตศาสตร์ ซึ่งประกอบด้วย 2 ส่วน คือ
ส่วนที่ 1 ส่วนที่เป็นเป้าหมาย จะอยู่ในรูปของ สมการจุดประสงค์ (ในเอกสารเล่มนี้ใช้ P)ส่วนที่ 2 ส่วนที่เป็นข้อจำกัด จะอยู่ในรูปของ อสมการข้อจำกัด
ซึ่งเป็นการแปลงสถานการณ์ปัญหาให้เป็นปัญหาทางคณิตศาสตร์ จากนั้นจึงหาคำตอบของปัญหาด้วยวิธีการต่าง ๆ ในการศึกษาครั้งนี้ใช้การกราฟช่วยในการหาคำตอบ
ส่วนที่ 1 ส่วนที่เป็นเป้าหมาย จะอยู่ในรูปของ สมการจุดประสงค์ (ในเอกสารเล่มนี้ใช้ P)ส่วนที่ 2 ส่วนที่เป็นข้อจำกัด จะอยู่ในรูปของ อสมการข้อจำกัด
ซึ่งเป็นการแปลงสถานการณ์ปัญหาให้เป็นปัญหาทางคณิตศาสตร์ จากนั้นจึงหาคำตอบของปัญหาด้วยวิธีการต่าง ๆ ในการศึกษาครั้งนี้ใช้การกราฟช่วยในการหาคำตอบ
|
ลองสมมติให้กราฟของระบบอสมการข้อจำกัด เป็นดังนี้
นำความจริงจากข้อกำหนดมาวิเคราะห์ กราฟของระบบสมการข้อจำกัดดังนี้
1. จุดทุกจุดในบริเวณส่วนที่แรเงาจะสอดคล้องกับระบบอสมการข้อจำกัด ถูกเรียกว่า
“เซตของคำตอบที่เป็นไปได้”
“เซตของคำตอบที่เป็นไปได้”
2. จากเซตของคำตอบที่เป็นไปได้ เราจะนำไปหาจุดใดที่สดคล้องกับสมการจุดประสงค์ที่ให้ค่าน้อยที่สุด
หรือค่ามากที่สุดจากกราฟของระบบอสมการข้อจำกัด
หรือค่ามากที่สุดจากกราฟของระบบอสมการข้อจำกัด
3. จุดทุกจุดในบริเวณส่วนที่แรเงา มีโอกาสเป็นไปได้ที่จะทำให้สมการจุดประสงค์มีค่าน้อยที่สุด
หรือมากที่สุด แต่จุดหักมุมมีโอกาสเป็นไปได้มากกว่า
หรือมากที่สุด แต่จุดหักมุมมีโอกาสเป็นไปได้มากกว่า
4. จุดในบริเวณส่วนที่แรเงาที่ทำให้สมการจุดประสงค์มีค่าน้อยที่สุดหรือมากทีสุดถูกเรียกว่า
คำตอบที่เหมาะสม
คำตอบที่เหมาะสม
5. ถ้ากำหนดการเชิงเส้นมีคำตอบเดียว แล้วจุด A,B,C และ O จุดใดจุดหนึ่ง จะทำให้สมการจุดประสงค์
มีค่าน้อยที่สุด หรือมากที่สุด
มีค่าน้อยที่สุด หรือมากที่สุด
6. ถ้าจุด A และ B ทำให้สมการจุดประสงมีค่าน้อยที่สุด แล้ว จุดทุกจุดที่อยู่บนส่วนของเส้นตรง AB จะทำ
ให้สมการจุดประสงค์ มีค่าน้อยที่สุดหรือมากที่สุดด้วย แสดงว่าคำตอบที่เหมาะสมจะมีจำนวนนับไม่ถ้วน
ให้สมการจุดประสงค์ มีค่าน้อยที่สุดหรือมากที่สุดด้วย แสดงว่าคำตอบที่เหมาะสมจะมีจำนวนนับไม่ถ้วน
เทคนิคการแก้ปัญหากำหนดการเชิงเส้นโดยวิธีใช้กราฟ
หลักการ
1. ถ้าโจทย์ที่ให้มาเป็นเรื่องราวที่ให้มาเป็นเรื่องราวที่ไม่ได้บอกตัวแปรออกมาตรงๆ เราซึ่งเป็นผู้อ่านโจทย์
จะต้องตั้งตัวแปรให้เป็นปริมาณต่างๆ จากโจทย์และสร้างสมการจุดประสงค์ กับอสมการข้อจำกัด
จะต้องตั้งตัวแปรให้เป็นปริมาณต่างๆ จากโจทย์และสร้างสมการจุดประสงค์ กับอสมการข้อจำกัด
2. เขียนกราฟของระบบอสมการข้อจำกัด เพื่อแสดงจุดทุกจุดในบริเวณส่วนที่แรเงาที่สอดคล้องกับระบบ
อสมการข้อจำกัด
อสมการข้อจำกัด
3. หาจุดหักมุมในบริเวณส่วนที่แรเงา
4. นำจุดหักมุมแต่ละจุดไปแทนค่าในสมการจุดประสงค์
4.1 ถ้าได้ค่าน้อยที่สุด (มากที่สุด) เพียงคำตอบเดียว แล้วค่านั้นคือ ค่าน้อยที่สุด (มากที่สุด)
ของสมการจุดประสงค์
ของสมการจุดประสงค์
4.2 ถ้ามีจุดหักมุม 2 จุด ที่มีแขนของจุดหักมุมร่วมกันทำให้สมการจุดประสงค์ มีค่าน้อยที่สุด
(มากที่สุด)
(มากที่สุด)
แล้ว จุดทุกจุดบนแกนของมุมนั้น คือ ค่าน้อยที่สุด(มากที่สุด) ของสมการจุดประสงค์ แสดงว่าคำตอบที่เหมาะสม จะมีจำนวนนับไม่ถ้วน
ตัวอย่างที่ 2 กำหนดให้สมการจุดประสงค์ คือ P = 30x + 50y
และอสมการข้อจำกัด คือ 2x + y ≤ 10
x + 2y ≤ 11
x ≥ 0
y ≥ 0
แล้วจงหาว่า P มีค่ามากที่สุดเป็นเท่าไร
วิธีทำ เขียนกราฟของระบบอสมการข้อจำกัด พร้อมจุดหักมุม
จากรูปจะเห็นได้ว่าจุดหักมุมของรูปสี่เหลี่ยมคือ (0,0) , (0,5.5) , (3,4) และ (5,0) นำจุดหักมุมแทนค่าในจุดประสงค์ ดังตารางต่อไปนี้
จุดหักมุม (x , y)
|
P = 30x + 50y
|
(0,0)
(0,5.5)
(3,4)
(5,0)
|
P = 30(0) + 50(0) = 0
P = 30(0) + 50(5.5) = 275
P = 30(3) + 50(4) = 290
P = 30(5) + 50(0) = 150
|
ดังนั้น จากตาราง จะพบว่า ค่ามากที่สุดของ P คือ 290 เมื่อ x = 3 และ y = 4
ตัวอย่างที่ 3 กำหนดให้สมการจุดประสงค์ คือ P = 4x + 3y
และอสมการข้อจำกัด คือ 2x + 3y ≥ 12
2x + y ≥ 8
x ≥ 0
y ≥ 0
แล้วจงหาว่า P มีค่าน้อยที่สุด เป็นเท่าไร
วิธีทำ เขียนกราฟของระบบอสมการข้อจำกัด พร้อมจุดหักมุม
จากรูปจะเห็นได้ว่าจุดหักมุมของรูปเหลี่ยมคือ (6, 0) (3,2) และ(0,8)นำจุดหักมุมแทนค่าในสมการจุดประสงค์ ดังตารางต่อไปนี้
จุดหักมุม (x , y)
|
P = 4x + 3y
|
(6,0)
(3,2)
(0,8)
|
P = 4(6) + 3(0) = 24
P = 4(3) + 3(2) = 18
P = 4(0) + 3(8) = 24
|
ดังนั้น จากตารางจะพบว่า ค่าน้อยที่สุดของ P คือ18 เมื่อ x = 3 และ y = 2
ตัวอย่างที่ 4 กำหนดให้สมการจุดประสงค์ คือP = 2x + 3y
และอสมการข้อจำกัด คือ x + y ≥ 4 , 5x + 2y ≤ 25
x ≤ 5 , y ≤ 5
x ≥ 0 , y ≥ 0
x ≤ 5 , y ≤ 5
x ≥ 0 , y ≥ 0
แล้วจงหาว่า P มีค่ามากที่สุดเป็นเท่าไร
วิธีทำ เขียนกราฟของระบบอสมการข้อจำกัด พร้อมจุดหักมุม
จากรูปจะเห็นได้ว่า จุดหักมุมของรูปเหลี่ยม คือ (0,4) , (0,5) , (3,5) , (5,0) และ (0,4) นำจุดหักมุมแทนค่าในสมการจุดประสงค์ ดังตารางต่อไปนี้
จุดหักมุม (x , y)
|
P = 2x + 3y
|
(0,4)
(0,5)
(3,5)
(5,0)
(4,0)
|
P = 2(0) + 3(4) = 12
P = 2(0) + 3(5) = 15
P = 2(3) + 3(5) = 21
P = 2(5) + 3(0) = 10
P = 2(4) + 3(0) = 8
|
ดังนั้น จากตารางจะพบว่าค่ามากที่สุดของ P คือ 21 เมื่อ x = 3 และ y = 5
ตัวอย่างที่ 5 กำหนดให้สมการจุดประสงค์ คือ P = x + 4y
และอสมการข้อจำกัด คือ x + 2y ≥ 8
5x + 2y ≥ 20
x + 4y ≤ 22
x ≥ 0 , y ≥ 0
แล้วจงหาว่า P มีค่าน้อยที่สุดและค่ามากที่สุดเป็นเท่าไร
วิธีทำ เขียนกราฟของระบบอสมการข้อจำกัด พร้อมจุดหักมุม
จากรูปจะเห็นได้ว่าจุดหักมุมของรูปสี่เหลี่ยม คือ (3,2.5) , (2,5) , (22,0) และ (8,0)
นำจุดหักมุมแทนค่าในสมการจุดประสงค์ ดังตารางต่อไปนี้
จุดหักมุม (x , y)
|
P = x + 4y
|
(3,2.5)
(2,5)
(22,0) (8,0) |
P = 3+ 4(2.5) = 13
P = 2+ 4(5) = 22
P = 22+ 4(0) =22
P = 8+ 4(0) = 8
|
จากตารางจะพบว่า
1. ค่าที่น้อยที่สุดของ P คือ 8 เมื่อ x = 8 และ y = 0
2. ค่ามากที่สุดของ P คือ 22 ณ. จุดหักมุม (2,5) และ (22,0) ซึ่งเป็นจุดหักมุมที่มีแขนของจุดมุมร่วมกัน
ดังนั้น จุดทุกจุดบนส่วนของเส้นตรงที่เชื่อมจุดหักมุม (2,5)และ(22,0)จะทำให้ค่ามากที่สุดของ P คือ 22
ตัวอย่างที่ 6 กำหนดให้สมการจุดประสงค์ คือ P = 3x + 2y
และอสมการข้อจำกัด คือ x + y ≤ 4
x + 2y ≥ 10
x ≥ 0
y ≥ 0
แล้วจงหาว่า P มีค่าน้อยที่สุด และค่ามากที่สุดเป็นเท่าไร
วิธีทำ เขียนกราฟของระบบอสมการข้อจำกัด พร้อมจุดหักมุม
จากกราฟจะเห็นได้ว่าไม่มีบริเวณส่วนที่แรเงา แสดงว่า เซตของคำตอบที่เป็นไปได้เป็น ดังนี้
ดังนั้น จึงไม่มีจุดที่เป็นไปได้ ปัญหานี้จึงไม่มีคำตอบ
วิเคราะห์เพิ่มเติม ถ้าเราประยุกต์กำหนดการเชิงเส้นช่วยในการตัดสินใจเกี่ยวกับปัญหาทรัพยากรที่มีอยู่อย่างจำกัดเพื่อให้เกิดประโยชน์หรือประสิทธิภาพสูงสุดแก่ผู้ทำการตัดสินใจเราถือว่าสถานการณ์แบบนี้
ไม่น่าจะเกิดขึ้น
ไม่น่าจะเกิดขึ้น
ไม่มีความคิดเห็น:
แสดงความคิดเห็น