Convex Optimization - การเขียนโปรแกรมเชิงเส้น
ระเบียบวิธี
Linear Programming เรียกอีกอย่างว่า Linear Optimization เป็นเทคนิคที่ใช้ในการแก้ปัญหาทางคณิตศาสตร์ที่ความสัมพันธ์เป็นแบบเส้นตรง ลักษณะพื้นฐานของ Linear Programming คือการขยายหรือย่อขนาดไฟล์objective function กับบางเรื่อง constraints. ฟังก์ชันวัตถุประสงค์คือฟังก์ชันเชิงเส้นซึ่งได้มาจากแบบจำลองทางคณิตศาสตร์ของปัญหา ข้อ จำกัด คือเงื่อนไขที่กำหนดในแบบจำลองและยังเป็นแบบเชิงเส้น
- จากคำถามที่กำหนดให้ค้นหาฟังก์ชันวัตถุประสงค์
- ค้นหาข้อ จำกัด
- วาดข้อ จำกัด บนกราฟ
- ค้นหาพื้นที่ที่เป็นไปได้ซึ่งเกิดจากจุดตัดของข้อ จำกัด ทั้งหมด
- ค้นหาจุดยอดของพื้นที่ที่เป็นไปได้
- หาค่าของฟังก์ชันวัตถุประสงค์ที่จุดยอดเหล่านี้
- จุดยอดที่ขยายหรือย่อฟังก์ชันวัตถุประสงค์ (ตามคำถาม) คือคำตอบ
ตัวอย่าง
Step 1 - เพิ่มสูงสุด $ 5x + 3y $ ขึ้นอยู่กับ
$ x + y \ leq 2 $,
$ 3x + y \ leq 3 $,
$ x \ geq 0 \: และ \: y \ geq 0 $
Solution -
ขั้นตอนแรกคือการค้นหาพื้นที่ที่เป็นไปได้บนกราฟ
จากกราฟจุดยอดของพื้นที่ที่เป็นไปได้คือ
$ \ left (0, 0 \ right) \ left (0, 2 \ right) \ left (1, 0 \ right) \ left (\ frac {1} {2}, \ frac {3} {2} \ right ) $
ให้ $ f \ left (x, y \ right) = 5x + 3y $
การใส่ค่าเหล่านี้ในฟังก์ชันวัตถุประสงค์เราจะได้ -
$ f \ left (0, 0 \ right) $ = 0
$ f \ left (0, 2 \ right) $ = 6
$ f \ left (1, 0 \ right) $ = 5
$ f \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $ = 7
ดังนั้นฟังก์ชันจะขยายใหญ่สุดที่ $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $
Step 2- บริษัท นาฬิกาแห่งหนึ่งผลิตนาฬิกาดิจิตอลและนาฬิกากลไก การคาดการณ์ระยะยาวบ่งบอกถึงความต้องการที่คาดว่าจะมีนาฬิกาดิจิตอลอย่างน้อย 100 เรือนและนาฬิกากลไก 80 เรือนในแต่ละวัน เนื่องจากข้อ จำกัด ด้านกำลังการผลิตจึงสามารถผลิตนาฬิการะบบดิจิตอลได้ไม่เกิน 200 เรือนและ 170 เรือนต่อวัน เพื่อให้เป็นไปตามสัญญาการจัดส่งจะมีการจัดส่งนาฬิกาอย่างน้อย 200 เรือนในแต่ละวัน
หากนาฬิกาดิจิตอลแต่ละเรือนขายได้ผลขาดทุน $ \ $ 2 $ แต่นาฬิกากลไกแต่ละเรือนสร้างกำไร $ $ 5 $ แต่ละประเภทควรทำทุกวันเพื่อเพิ่มผลกำไรสุทธิสูงสุด?
Solution -
ให้ $ x $ เป็นจำนวนนาฬิกาดิจิทัลที่ผลิต
$ y $ คือจำนวนนาฬิกากลไกที่ผลิต
ตามคำถามต้องมีนาฬิกาดิจิตอลอย่างน้อย 100 เรือนต่อวันและสามารถผลิตนาฬิกาดิจิตอลได้สูงสุด 200 เรือน
$ \ Rightarrow 100 \ leq \: x \ leq 200 $
ในทำนองเดียวกันจะมีนาฬิกากลไกอย่างน้อย 80 เรือนต่อวันและสามารถผลิตนาฬิกากลไกได้สูงสุด 170 เรือน
$ \ Rightarrow 80 \ leq \: y \ leq 170 $
เนื่องจากต้องผลิตนาฬิกาอย่างน้อย 200 เรือนในแต่ละวัน
$ \ Rightarrow x + y \ leq 200 $
เนื่องจากนาฬิกาดิจิตอลแต่ละเรือนขายได้ผลขาดทุน $ 2 $ แต่นาฬิกากลไกแต่ละเรือนสร้างกำไร $ $ 5 $
กำไรทั้งหมดสามารถคำนวณได้เป็น
กำไร $ = -2x + 5y $
และเราต้องเพิ่มผลกำไรให้สูงสุดดังนั้นจึงสามารถกำหนดคำถามได้ว่า -
เพิ่มสูงสุด $ -2x + 5y $ ขึ้นอยู่กับ
$ 100 \: \ leq x \: \ leq 200 $
$ 80 \: \ leq y \: \ leq 170 $
$ x + y \: \ leq 200 $
การพล็อตสมการข้างต้นในกราฟเราได้
จุดยอดของภูมิภาคที่เป็นไปได้คือ
$ \ left (100, 170 \ right) \ left (200, 170 \ right) \ left (200, 180 \ right) \ left (120, 80 \ right) และ \ left (100, 100 \ right) $
ค่าสูงสุดของฟังก์ชันวัตถุประสงค์จะได้รับที่ $ \ left (100, 170 \ right) $ ดังนั้นเพื่อเพิ่มผลกำไรสุทธิควรผลิตนาฬิกาดิจิทัล 100 เรือนและนาฬิกากลไก 170 หน่วย