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 หน่วย