กำหนดการเชิงเส้น

กำหนดการเชิงเส้น

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

ให้แก่กิจกรรมต่าง ๆ เพื่อให้เกิดประโยชน์มากที่สุด และมีประสิทธิภาพสูงสุด หรือก่อให้เกิดการสูญเสียน้อยที่สุด

การหาค่าสูงสุดหรือค่าตํ่าสุดภายใต้เงื่อนไขบังคับหรือข้อจํากัด

        1) ฟังก์ชันเชิงเส้นหรือสมการเชิงเส้น เป็นฟังก์ชันที่เราต้องการนําไปหาค่าที่เหมาะสม เช่น ฟังก์ชันเกี่ยวกับกําไร ซึ่งเราต้องการให้มีค่ามากที่สุด โดยที่สร้างขึ้นจากเงื่อนไขที่โจทย์กําหนด เรียกว่า ฟงก์ชันจุดประสงค์ (Objective Function) หรือสมการจุดประสงค์

        2) ระบบอสมการเชิงเส้น โดยสร้างจากเงื่อนไขบังคับหรือข้อจํากัด ที่มีอยู่ในปัญหาต่าง ๆ เหล่านั้น ซึ่งเรียกว่า อสมการขอจำกัด

การหาคำตอบของกำหนดการเชิงเส้นโดยวิธีใช้กราฟ

   1) สร้างฟังก์ชันจุดประสงค์และอสมการข้อจํากัด ตามเงื่อนไขข้อจํากัดที่โจทย์กําหนด

      2) เขียนกราฟของระบบสมการจากอสมการข้อจํากัด บริเวณที่แรเงาซึ่งสอดคล้องกับอสมการข้อจํากัด เรียกว่า รูปหลายเหลี่ยมของบริเวณที่หาคําตอบได้

     3) หาพิกัดจากจุดมุมของรูปหลายเหลี่ยมของบริเวณที่หาคําตอบได้

  4) แทนค่าพิกัดของจุดมุมของรูปหลายเหลี่ยมในฟังก์ชันจุดประสงค์ จุดมุมเป็นไปตามเงื่อนไข นั่นคือคําตอบของโจทย์ปัญหา