Dynamic Programming

[t.B.]

คือตอนนี้ผมเรียนเรื่อง Linear Programming อยู่ พอดีมีโจทย์ข้อหนึ่ง
สมการจุดประสงค์คือ $P(x,y,z)=15x+24y+z+2$ หาค่าสูงสุดและต่ำสุดของP
อสมการข้อจำกัดคือ
$x+z\leq 48$
$2x-y\leq 40$
$-3x+y\leq 10$
$x\geq 0$
$y\geq 0$
และ y-z=2 << ถ้าไม่มีบรรทัดนี้ครูบอกว่าต้องใช้ Dynamic Programming
คือผมอยากทราบว่าถ้าไม่มีบรรทัดดังกล่าวจะใช้ Dynamic Programming ยังไงกับโจทย์ข้อนี้อะครับ
อ่อ..ผมยังไม่รู้ด้วยซ้ำว่ามันคืออะไรไอ dynamic programming เนี่ยอะครับ

ปล.ผมลอง search หาอ่านใน google แล้วอ่านไม่รู้เรื่องเลยครับ จึงมาโพสให้ผู้รู้ช่วยอธิบายไม่ให้เป็นภาษาคอมมากเกินไป
ให้เด็กมัธยมพอเข้าใจหน่อยนะครับ

[M@gpie]

อ.คงเข้าใจผิดกระมังครับ ไม่ถึงกับต้องใช้ Dynamic programming หรอกครับ

วิธีแก้ปัญหา linear programming ที่เรารู้จักในชั้นมัธยม สามารถใช้ได้ดี สำหรับสองตัวแปร โดยที่ ค่าสูงสุดต่ำสุดเกิดที่จุดยอดของบริเวณที่เป็นไปได้
สำหรับข้อนี้ เราสามารถกำจัดตัวแปร $z$ แล้วก็แก้ปัญหาโดยใช้วิธีปกติได้

สำหรับ 3 ตัวแปร เราก็สามารถทำได้ในทำนองเดียวกัน แต่ต้องวาดภาพ 3 มิติ ซึ่งยากกว่า

สำหรับตัวแปรตั้งแต่ 3 ตัวขึ้นไป แนวคิดยังคงเหมือนเดิมครับ แต่เป็น n รูปเหลี่ยมใดๆ ทำให้เราไม่สามารถวาดรูปได้ จึงมีวิธีแก้ปัญหา linear programming สำหรับ n ตัวแปร วิธีที่นิยมกันมากเรียกว่า Simplex Method (ลองหาข้อมูลดูครับถ้าสนใจ) เป็นวิธีมาตรฐานที่ใช้ในคอมพิวเตอร์ครับ

ส่วน Dynamic programming เป็นวิธีการหาค่าสูงสุดต่ำสุดภายในเงื่อนไขบังคับแบบหนึ่ง ซึ่งคิดว่าใช้แก้ linear programming ได้แต่ผมไม่เคยใช้วิธีนี้เลยครับ

[t.B.]

แล้วจะกำจัดตัวแปร z ยังไงหรอครับ ช่วยแสดงวิธีทำให้ดูทีครับ

[M@gpie]

ก็ $z=y-2$ ไม่ใช่เหรอครับ ก็เอาไปแทน

[t.B.]

อ๋อ ผมหมายถึงถ้าเค้าไม่ให้บรรทัด y-z=2 มาให้อะครับ จะแก้อย่างไร