การหาผลลัพธ์ของรูปแบบแทนระบบของปัญหา (Model Solution)

ผู้เขียน : ดร. ระวี สุวรรณเดโชไช

หลังจากสร้างรูปแบบของโปรแกรมเชิงเส้น การแก้ปัญหาโปรแกรมเชิงเส้นสามารถทำได้หลายวิธีในที่นี้จะกล่าวถึง วิธีกราฟ และวิธีการของ simplex

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

วิธีกราฟ (Graphical Method)
วิธีกราฟนี้เป็นวิธีที่เข้าใจได้ง่ายสำหรับปัญหาที่มี 1 หรือ 2 ตัวแปร 

ตัวอย่าง พิจารณาโปรแกรมเชิงเส้นต่อไปนี้



การแก้ปัญหาโปรแกรมเชิงเส้นโดยวิธีกราฟมีขั้นตอนต่อไปนี้ 
1. วาดกราฟของสมการแสดงขอบข่ายทั้งหมด (สมการข้อจำกัด และ non-negativity constraints)
2. ระบุพื้นที่ที่เป็นสอดคล้องกับข้อจำกัดทั้งหมด นั่นคือคำตอบของสมการแสดงขอบข่ายทั้งหมดอยู่บนพื้นที่นี้พื้นที่นี้เรียกว่า (feasible region) 



เราจะเห็นได้ว่าค่าของตัวแปร  และ ที่อยู่ในพื้นที่ที่แรงเงามีค่าที่สอดคล้องกับข้อจำกัดที่กำหนด

3. วาดกราฟของสมการกำหนดเป้าหมายโดยการกำหนดให้สมการกำหนดเป้าหมายมีค่าต่างๆ พร้อมทั้งหาทิศทางการเปลี่ยนค่าของสมการกำหนดเป้าหมาย



สมการ เป็นเส้นตรงโดยที่จุดต่างๆ บนเส้นตรงจะให้ค่า z เดียวกัน เมื่อกำหนดค่า z ค่าใหม่สมการที่ได้จะเป็นเส้นตรงที่ขนานกับเส้นเดิม จากกราฟข้างต้นจุด  ทุกๆจุดที่อยู่บนเส้นตรง  จะมีค่าของสมการกำหนดเป้าหมายเท่ากับ 2 ในขณะเดียวกันสำหรับจุด ที่อยู่บนเส้นตรง จะมีค่าของสมการกำหนดเป้าหมายเท่ากับ 5 เราจะเห็นได้ว่าเมื่อค่าของสมการกำหนดเป้าหมายเพิ่มขึ้นเรื่อยๆ เส้นตรงจะเลื่อนขึ้นไปทางขวามือ ดังแสดงในกราฟ

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



จากกราฟข้างต้น ในการหาค่าสูงสุดของสมการกำหนดเป้าหมายทำได้โดยเลื่อนเส้นตรงไปทางขวาจนสุดเขตพื้นที่ที่แรงเงา จะเห็นได้ว่า ค่าของ  และ ที่ทำให้ค่าของสมการกำหนดเป้าหมายมีค่าสูงสุดคือ โดยที่ค่าของสมการกำหนดเป้าหมายมีค่าเท่ากับ 22/3 ถ้าเราต้องการหาค่าต่ำสุดของสมการกำหนดเป้าหมายทำได้โดยเลื่อนเส้นตรงไปทางซ้ายจนสุดพื้นที่แรงเงา ค่าของ และ ที่ทำให้ค่าของสมการกำหนดเป้าหมายมีค่าต่ำสุดคือ 

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

จุดยอด	ค่าของสมการกำหนดเป้าหมาย
(0,0)	0
(0,1)	4
(2/3, 5/3)	22/3*
(2,1)	6
(3,0)	3

จะเห็นได้ว่าในกรณีนี้ค่าของสมการกำหนดเป้าหมายมีค่าสูงสุดเท่ากับ 8 เมื่อ  และ หรือ และ  จากกราฟเราจะเห็นได้ว่าคำตอบทั้งหมดคือจุดทุกๆจุดของ x1 และ x2 ที่อยู่บนเส้นตรง โดยที่ มีค่าอยู่ระหว่าง 2/3 และ 2 

ตัวอย่าง พิจารณาโปรแกรมเชิงเส้นต่อไปนี้





จากกราฟจะเห็นได้ว่าพื้นที่ของอยู่สอดคล้องกับข้อจำกัดทั้งหมดมีขอบเขตไม่จำกัด (unbounded region) นอกจากนี้ค่าของสมการกำหนดเป้าหมายซึ่งเป็นเส้นตรงที่มีค่าเพิ่มขึ้น เส้นตรงจะเลื่อนไปทางขวามือ เราจะเห็นว่าค่าของสมการกำหนดเป้าหมายเพิ่มขึ้นไปเรื่อยๆไม่มีขีดจำกัด นั่นคือ ผลลัพธ์ไม่มีขอบเขตจำกัด ถ้าต้องการหาค่าสมการกำหนดเป้าหมายที่มีค่าต่ำสุด ค่าของสมการกำหนดเป้าหมายมีค่าต่ำลงเมื่อเส้นตรงเลื่อนไปทางซ้ายมือ เมื่อเลื่อนเส้นตรงไปทางซ้ายมือสุดขอบพื้นที่ ค่าของสมการกำหนดเป้าหมายมีค่าเท่ากับ 0 ที่จุดยอด 

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

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

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