กำหนดการเชิงเส้นกับการใช้ทรัพยากรให้คุ้มค่าที่สุด

กำหนดการเชิงเส้นกับการใช้ทรัพยากรให้คุ้มค่าที่สุด

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

กำหนดการเชิงเส้นคืออะไร?

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

ส่วนประกอบสำคัญของกำหนดการเชิงเส้น

ในการสร้างแบบจำลองกำหนดการเชิงเส้นขึ้นมาเพื่อแก้ปัญหา น้องๆ จะต้องเข้าใจส่วนประกอบหลักๆ เหล่านี้ก่อนครับ

• ตัวแปรตัดสินใจ (Decision Variables): เป็นสิ่งที่เราต้องการหาค่าหรือปริมาณของมัน เพื่อนำไปสู่คำตอบที่ดีที่สุด เช่น จำนวนสินค้าแต่ละชนิดที่จะผลิต หรือจำนวนชั่วโมงที่จะใช้สำหรับแต่ละกิจกรรม โดยปกติเราจะกำหนดให้เป็น $x, y, z$ ครับ
• ฟังก์ชันวัตถุประสงค์ (Objective Function): คือสมการที่เราต้องการทำให้มีค่าสูงสุดหรือต่ำสุด ซึ่งจะอยู่ในรูปของตัวแปรตัดสินใจ เช่น $text{Maximize } P = 3x + 4y$ โดย $P$ คือกำไรที่ต้องการให้สูงสุดครับ
• ข้อจำกัด (Constraints): คือเงื่อนไขหรือข้อจำกัดต่างๆ ที่ตัวแปรตัดสินใจของเราต้องเป็นไปตามนั้น ซึ่งมักจะเกี่ยวข้องกับทรัพยากรที่มีอยู่จำกัด เช่น วัตถุดิบ เวลา หรือกำลังคน ข้อจำกัดเหล่านี้ก็อยู่ในรูปของอสมการเชิงเส้นเช่นกันครับ เช่น $2x + y le 10$ และ $x + 3y le 15$ เป็นต้นครับ
• เงื่อนไขไม่เป็นลบ (Non-negativity Constraints): โดยทั่วไปแล้ว ปริมาณหรือจำนวนของสิ่งที่เราผลิตหรือใช้ไม่สามารถติดลบได้ ดังนั้นเราจึงต้องมีข้อจำกัดที่ว่าตัวแปรตัดสินใจต้องมีค่ามากกว่าหรือเท่ากับศูนย์เสมอ นั่นคือ $x ge 0$ และ $y ge 0$ ครับ

ขั้นตอนการแก้ปัญหากำหนดการเชิงเส้นด้วยวิธีกราฟ

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

1. กำหนดตัวแปรและสร้างแบบจำลอง: กำหนดตัวแปรตัดสินใจ ($x, y$) สร้างฟังก์ชันวัตถุประสงค์ และข้อจำกัดทั้งหมดครับ
2. เขียนกราฟข้อจำกัด: เปลี่ยนอสมการข้อจำกัดแต่ละตัวให้เป็นสมการเส้นตรง (โดยเปลี่ยน $le$ หรือ $ge$ เป็น $=$) แล้ววาดกราฟเส้นตรงเหล่านั้นลงบนระนาบ $XY$ ครับ
3. หาบริเวณที่เป็นไปได้ (Feasible Region): ระบายสีในบริเวณที่สอดคล้องกับอสมการข้อจำกัดทั้งหมด รวมถึงข้อจำกัด $x ge 0$ และ $y ge 0$ ด้วย บริเวณที่ระบายสีทับกันทั้งหมดคือบริเวณที่เป็นไปได้ ซึ่งทุกๆ จุดในบริเวณนี้คือคำตอบที่เป็นไปได้สำหรับปัญหาของเราครับ
4. หาจุดยอดมุม (Corner Points): จุดยอดมุมคือจุดตัดของเส้นตรงที่ล้อมรอบบริเวณที่เป็นไปได้ หาพิกัดของจุดยอดมุมเหล่านี้ทั้งหมดครับ
5. คำนวณหาค่าฟังก์ชันวัตถุประสงค์: นำพิกัดของจุดยอดมุมแต่ละจุดที่ได้ในข้อ 4 ไปแทนค่าในฟังก์ชันวัตถุประสงค์ เพื่อคำนวณหาค่า $P$ (หรือค่าที่เราต้องการหา) ครับ
6. เลือกคำตอบที่ดีที่สุด: หากเราต้องการ Maximize ให้เลือกจุดยอดมุมที่ทำให้ฟังก์ชันวัตถุประสงค์มีค่าสูงสุด แต่ถ้าต้องการ Minimize ก็เลือกจุดที่ทำให้มีค่าต่ำสุดครับ

ตัวอย่างโจทย์: การผลิตสินค้าเพื่อกำไรสูงสุด

สมมติว่าโรงงานผลิตเก้าอี้ไม้มีกำลังการผลิตจำกัด โรงงานผลิตเก้าอี้ได้ 2 แบบคือ เก้าอี้แบบ A และเก้าอี้แบบ B

• เก้าอี้แบบ A ใช้ไม้ 2 ท่อน และใช้เวลาประกอบ 1 ชั่วโมง ขายได้กำไรตัวละ 300 บาท
• เก้าอี้แบบ B ใช้ไม้ 1 ท่อน และใช้เวลาประกอบ 2 ชั่วโมง ขายได้กำไรตัวละ 400 บาท

โรงงานมีไม้ทั้งหมด 10 ท่อน และมีเวลาประกอบรวม 12 ชั่วโมง

โรงงานควรผลิตเก้าอี้แต่ละแบบกี่ตัวจึงจะได้กำไรสูงสุด?

มาดูขั้นตอนการแก้ปัญหากันครับ

1. กำหนดตัวแปร:
   • ให้ $x$ แทนจำนวนเก้าอี้แบบ A ที่ผลิต (ตัว)
   • ให้ $y$ แทนจำนวนเก้าอี้แบบ B ที่ผลิต (ตัว)
2. ฟังก์ชันวัตถุประสงค์ (Maximize Profit):
   • กำไรจากเก้าอี้ A คือ $300x$
   • กำไรจากเก้าอี้ B คือ $400y$
   • ฟังก์ชันวัตถุประสงค์: $text{Maximize } P = 300x + 400y$
3. ข้อจำกัด:
   • ข้อจำกัดไม้: เก้าอี้ A ใช้ 2 ท่อน, เก้าอี้ B ใช้ 1 ท่อน, มีไม้รวม 10 ท่อน
     $2x + y le 10$
   • ข้อจำกัดเวลาประกอบ: เก้าอี้ A ใช้ 1 ชั่วโมง, เก้าอี้ B ใช้ 2 ชั่วโมง, มีเวลารวม 12 ชั่วโมง
     $x + 2y le 12$
   • เงื่อนไขไม่เป็นลบ:
     $x ge 0$ และ $y ge 0$
4. เขียนกราฟและหาบริเวณที่เป็นไปได้:

   แปลงอสมการเป็นสมการเส้นตรง:

   • $L_1: 2x + y = 10$ (จุดตัดแกน $x$ คือ (5,0), จุดตัดแกน $y$ คือ (0,10))
   • $L_2: x + 2y = 12$ (จุดตัดแกน $x$ คือ (12,0), จุดตัดแกน $y$ คือ (0,6))

   จากนั้นวาดเส้นตรงและระบายสีบริเวณที่เป็นไปได้ (ซึ่งอยู่ในจตุภาคที่ 1 เนื่องจาก $x ge 0$, $y ge 0$) ที่อยู่ใต้เส้นตรงทั้งสองเส้น (เพราะเป็นอสมการ $le$)

5. หาจุดยอดมุม:

   จากกราฟ เราจะเห็นจุดยอดมุม 4 จุด คือ

   • $A = (0,0)$
   • $B = (5,0)$ (จุดตัด $L_1$ กับแกน $x$)
   • $C = (0,6)$ (จุดตัด $L_2$ กับแกน $y$)
   • $D$ (จุดตัดของ $L_1$ และ $L_2$): แก้สมการ $2x + y = 10$ และ $x + 2y = 12$ จะได้ $x=2.67$ และ $y=4.67$ ครับ (หรือ $x = 8/3$, $y = 14/3$) ซึ่งก็คือจุด $D = (8/3, 14/3)$
6. คำนวณค่าฟังก์ชันวัตถุประสงค์ $P = 300x + 400y$ ที่แต่ละจุด:
   • ที่ $A = (0,0)$: $P = 300(0) + 400(0) = 0$
   • ที่ $B = (5,0)$: $P = 300(5) + 400(0) = 1500$
   • ที่ $C = (0,6)$: $P = 300(0) + 400(6) = 2400$
   • ที่ $D = (8/3, 14/3)$: $P = 300(8/3) + 400(14/3) = 800 + 5600/3 = 800 + 1866.67 approx 2666.67$
7. เลือกคำตอบที่ดีที่สุด:

   ค่ากำไรสูงสุดคือ 2666.67 บาท ซึ่งเกิดขึ้นเมื่อผลิตเก้าอี้แบบ A จำนวน $8/3 approx 2.67$ ตัว และเก้าอี้แบบ B จำนวน $14/3 approx 4.67$ ตัว

   ข้อสังเกต: ในชีวิตจริง การผลิตสินค้าอาจต้องเป็นจำนวนเต็มเท่านั้น ซึ่งปัญหานี้เรียกว่า กำหนดการเชิงเส้นจำนวนเต็ม (Integer Linear Programming) ซึ่งซับซ้อนกว่า แต่ในระดับพื้นฐาน เรามักจะอนุญาตให้คำตอบเป็นทศนิยมได้ก่อนครับ ถ้าโจทย์ไม่ได้บอกว่าต้องเป็นจำนวนเต็ม.

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

ข้อผิดพลาดที่พบบ่อยและเทคนิคทำข้อสอบ

• การกำหนดตัวแปรผิด: ตรวจสอบให้แน่ใจว่าตัวแปร $x$ และ $y$ แทนอะไร และมีความหมายตรงตามที่โจทย์ต้องการ
• การสร้างฟังก์ชันวัตถุประสงค์และข้อจำกัดผิด: อ่านโจทย์อย่างละเอียด แยกแยะให้ได้ว่าอะไรคือเป้าหมาย (Maximize/Minimize) และอะไรคือข้อจำกัดของทรัพยากร
• การวาดกราฟคลาดเคลื่อน: หาจุดตัดแกนให้แม่นยำ และวาดเส้นตรงให้ถูกต้อง การใช้ไม้บรรทัดจะช่วยได้มากครับ
• การระบุบริเวณที่เป็นไปได้ผิด: ทดสอบจุด (0,0) ในอสมการ เพื่อช่วยในการพิจารณาว่าต้องระบายสีไปทางไหน หรือใช้ลูกศรบนเส้นตรงแสดงทิศทางของบริเวณที่เป็นไปได้
• การหาจุดยอดมุมไม่ครบ: ตรวจสอบให้แน่ใจว่าได้หาจุดตัดของเส้นตรงทุกเส้นที่เป็นไปได้ ซึ่งจะล้อมรอบบริเวณที่เป็นไปได้ และจุดตัดแกน $x$ และ $y$ ด้วย
• ลืมเงื่อนไขไม่เป็นลบ: ข้อจำกัด $x ge 0$ และ $y ge 0$ มักจะทำให้บริเวณที่เป็นไปได้อยู่ในจตุภาคที่ 1 เสมอ อย่าลืมพิจารณาตรงนี้ครับ

การประยุกต์ใช้กำหนดการเชิงเส้นในโลกแห่งความเป็นจริง

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

• การวางแผนการผลิตในโรงงาน: ใช้ในการตัดสินใจว่าจะผลิตสินค้าชนิดใดในปริมาณเท่าใด เพื่อให้ได้กำไรสูงสุดหรือใช้ต้นทุนต่ำสุดภายใต้ข้อจำกัดด้านวัตถุดิบ แรงงาน และเครื่องจักร
• การจัดการโลจิสติกส์และการขนส่ง: ใช้ในการวางแผนเส้นทางการขนส่งสินค้าให้มีประสิทธิภาพสูงสุด เพื่อลดระยะทาง เวลา และค่าใช้จ่าย
• การจัดพอร์ตการลงทุน: นักลงทุนใช้ LP เพื่อเลือกสินทรัพย์ต่างๆ มาจัดสรรในพอร์ตโฟลิโอให้ได้ผลตอบแทนสูงสุดภายใต้ระดับความเสี่ยงที่ยอมรับได้
• การจัดตารางเวลา: เช่น การจัดตารางบินของสายการบิน การจัดตารางเดินรถขนส่งสาธารณะ เพื่อเพิ่มประสิทธิภาพและลดความแออัด
• การวางแผนโภชนาการ: ใช้ในการกำหนดสัดส่วนของอาหารที่ต้องบริโภคเพื่อให้ได้สารอาหารครบถ้วนตามความต้องการในต้นทุนที่ต่ำที่สุด

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

สรุปแนวคิดสำคัญ

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

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

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