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

กำหนดการเชิงเส้น เป็นคณิตศาสตร์ประยุกต์แขนงหนึ่งที่คิดค้นขึ้นมาประมาณ พ.ศ. 2482 โดย Leonid Kantorovich เพื่อแก้ปัญหาให้เป็นไปตามจุดประสงค์ของมนุษย์ โดยมีแนวคิดที่ว่า ให้เพียงพออย่างสูงสุดในทรัพยากรที่มีจำกัด สามารถใช้คำนวณเพื่อแก้ปัญหาได้หลายอย่าง เช่น คำนวณการผลิตสินค้าให้ได้มากที่สุด แต่เสียค่าใช้จ่ายน้อยที่สุด, หาวิธีการเคลื่อนย้ายทหารให้มากที่สุดโดยที่เสียค่าใช้จ่ายน้อยที่สุด, ผลิตสินค้าจำนวนน้อยที่สุด แต่ทำกำไรได้มากที่สุด หรือหาว่า หากบริษัทหนึ่งผลิตสินค้า 2 ประเภท ต้องผลิตอย่างละกี่ชิ้นจึงจะได้กำไรสูงสุด เป็นต้น

กำหนดการเชิงเส้น จะอยู่ในรูปแบบทางคณิตศาสตร์ของสมการเชิงเส้นและอสมการเชิงเส้น แล้วหาค่าสูงสุด ต่ำสุดของฟังก์ชันที่สอดคล้องกับสมการ (และอสมการ) ที่กำหนด ตัวแบบคณิตศาสตร์ประกอบด้วย

  • ฟังก์ชันเชิงเส้น เป็นสมการที่สร้างให้ตรงกับจุดประสงค์ที่ต้องการ เรียกฟังก์ชันนี้ว่า ฟังก์ชันเป้าหมาย โดยจะตั้งสมการขึ้นเพื่อหาค่าสูงสุด หรือต่ำสุด ขึ้นอยู่กับตัวแปร เช่น D = 15x+20y
  • เงื่อนไขจำกัด (เงื่อนไขบังคับ) ได้แก่อสมการ หรือสมการที่เป็นเงื่อนไขที่กำหนดให้ เป็นเงื่อนไขที่ถูกจำกัดของทรัพยากร หรือตัวแปร เช่น

อ้างอิง

แก้