เรื่องที่ 5.1 ตัวแบบดูอัล
ตัวแบบดูอัล (Dual) ของปัญหาการโปรแกรมเชิงเส้นเป็นตัวแบบซึ่งสามารถเขียนได้จากตัวแบบการโปรแกรมเชิงเส้นที่มีอยู่
ู่ตัวแบบดูอัลถือเป็นตัวแบบคู่กันของตัวแบบการโปรแกรมเชิงเส้นที่มีอยู่เดิม เราจะเรียกตัวแบบการโปรแกรมเชิงเส้นที่มีอยู่เดิมว่า
ตัวแบบไพรมัล (Primal) ความสัมพันธ์ระหว่างตัวแบบดูอัลกับไพรมัล จะมีลักษณะตรงข้ามกัน ตัวแบบดูอัลเปรียบเสมือน
กระจกเงาของตัวแบบไพรมัล
พิจารณาปัญหาการโปรแกรมเข้งเส้น ต่อไปนี้
ภายใต้ข้อจำกัด
ถ้ากำหนดให้ตัวแบบข้างต้นเป็นตัวแบบไพรมัล ตัวแบบดูอัลของตัวแบบข้างต้นสามารถเขียนได้เป็น
ภายใต้ข้อจำกัด
ลองพิจารณาตัวแบบไพรมัลและดูอัล ความสัมพันธ์ในเบื้องต้นที่มองเห็นได้คือ
1. ฟังก์ชันวัตถุประสงค์มีลักษณะตรงข้ามกัน คือเมื่อตัวแบบไพรมัลเป็นการหาค่าสูงสุดตัวแบบดูอัลจะเป็นการหาค่าต่ำสุด
2. ฟังก์ชันข้อจำกัดมีเครื่องหมายของอสมการตรงข้ามกัน คือเมื่อตัวแบบไพรมัลมีเครื่องหมาย "  "
ตัวแบบดูอัลจะมีเครื่องหมาย "  "
3. ตัวแปรของตัวแบบดูอัลมีจำนวนเท่ากับจำนวนฟังก์ชันข้อจำกัดของตัวแบบไพรมัล คือเมื่อตัวแบบไพรมัลมีฟังก์ชัน
ข้อจำกัดจำนวน m ฟังก์ชัน จำนวนตัวแปรของตัวแบบดูอัลจะมีอยู่ m ตัวแปร คือ 
4. ฟังก์ชันข้อจำกัดของตัวแบบดูอัลมีจำนวนเท่ากับจำนวนตัวแปรของตัวแบบไพรมัล คือ เมื่อตัวแบบไพรมัลมีจำนวน
ตัวแปร n ตัว จำนวนฟังก์ชันข้อจำกัดของตัวแบบดูอัลจะมีอยู่ n ฟังก์ชัน
5. สัมประสิทธ์ของตัวแปรในฟังก์ชันวัตถุประสงค์ของตัวแบบไพรมัล  จะกลายเป็นค่าคงที่ทาง
ด้านขวามือของฟังก์ชันข้อจำกัดในตัวแบบดูอัล
6. ค่าคงที่ทางด้านขวามือของฟังก์ชันข้อจำกัดในตัวแบบไพรมัล  จะกลายเป็นสัมประสิทธิ์ของ
ตัวแปรในฟังก์ชันวัตถุประสงค์ของตัวแบบดูอัล
7. แถวของสัมประสิทธิ์ของตัวแปรในฟังก์ชันข้อจำกัดในตัวแบบไพรมัล
จะกลายไปเป็นสดมภ์ของสัมประสิทธิ์ของตัวแปรในฟังก์ชันข้อจำกัดในตัวแบบดูอัล
8. ตัวแปรทั้งของตัวแบบไพรมัลและตัวแบบดูอัลมีค่ามากกว่าหรือเท่ากับศูนย์
ความสำคัญของตัวแบบดูอัล มีอยู่ 3 ประการ คือ
1. ช่วยให้การแก้ปัญหาการโปรแกรมเชิงเส้นที่มีจำนวนฟังก์ชันข้อจำกัดมากกว่าจำนวนตัวแปรมาก ๆ ทำได้เร็วขึ้น
2. ใช้ตีความทางเศรษฐศาสตร์ของตัวแปรในปัญหาการโปรแกรมเชิงเส้น
3. ใช้ช่วยในการวิเคราะห์ความไวของปัญหาการโปรแกรมเชิงเส้น
|
