Linear programming — การโปรแกรมเชิงเส้น
การโปรแกรมเชิงเส้น คือสาขาหนึ่งของการโปรแกรมเชิงคณิตศาสตร์ และเป็นวิธีการวิจัยการดำเนินงานที่ใช้กันอย่างแพร่หลาย โดยอุทิศให้กับการพัฒนาทฤษฎีและวิธีการแก้ปัญหาการหาค่าสุดขีด (ค่าสูงสุดหรือต่ำสุด) ของฟังก์ชันเชิงเส้นภายใต้เงื่อนไขข้อจำกัดเชิงเส้น
การโปรแกรมเชิงเส้นเป็นหนึ่งในเครื่องมือที่มีประสิทธิภาพสูงและถูกนำมาใช้บ่อยที่สุดในการแก้ปัญหาการหาค่าที่เหมาะสมในด้านเศรษฐศาสตร์ การบริหารจัดการ การวางแผน โลจิสติกส์ และสาขาอื่น ๆ
หัวข้อและวัตถุประสงค์
ปัญหาหลักของการโปรแกรมเชิงเส้น คือการค้นหาวิธีที่ดีที่สุด (เหมาะสมที่สุด) ในการจัดสรรทรัพยากรที่มีจำกัดเพื่อบรรลุเป้าหมายบางอย่าง เมื่อทั้งเป้าหมายและข้อจำกัดในการใช้ทรัพยากรสามารถแสดงออกมาในรูปของความสัมพันธ์เชิงเส้น
- การโปรแกรมเชิงเส้นช่วยแก้ปัญหาเชิงปฏิบัติต่าง ๆ เช่น:
- การวางแผนการผลิตที่เหมาะสมที่สุด
- การหาค่าที่เหมาะสมของการไหลของการขนส่ง (ปัญหาการขนส่ง)
- การจัดสรรการลงทุนที่เหมาะสมที่สุด
- การตัดวัสดุที่เหมาะสมที่สุด และปัญหาการมอบหมายงาน
การกำหนดสูตรทางคณิตศาสตร์ของปัญหาการโปรแกรมเชิงเส้น
ปัญหาการโปรแกรมเชิงเส้นในรูปแบบมาตรฐานมีการกำหนดดังต่อไปนี้:
ต้องการหาค่าของตัวแปรในการตัดสินใจที่ทำให้ฟังก์ชันวัตถุประสงค์เชิงเส้นมีค่าสูงสุดหรือต่ำสุด โดยตัวแปรในการตัดสินใจอยู่ภายใต้ข้อจำกัดในรูปของระบบสมการเชิงเส้นและ/หรืออสมการเชิงเส้น โดยทั่วไปจะเพิ่มเงื่อนไขความไม่เป็นลบของตัวแปรในการตัดสินใจ (ค่าของตัวแปรต้องมากกว่าหรือเท่ากับศูนย์) ซึ่งมักกำหนดโดยความหมายทางกายภาพหรือทางเศรษฐกิจของปัญหา
ในเชิงคณิตศาสตร์ หมายความว่าต้องทำงานกับฟังก์ชันเชิงเส้นและระบบสมการ/อสมการเชิงเส้น
แนวคิดพื้นฐานของการโปรแกรมเชิงเส้น
- ตัวแปรในการตัดสินใจ (ตัวแปรที่ควบคุมได้): ปริมาณที่ต้องกำหนดค่าในกระบวนการแก้ปัญหา (เช่น ปริมาณการผลิตของผลิตภัณฑ์ต่าง ๆ จำนวนทรัพยากรที่จัดสรรไปยังเป้าหมายต่าง ๆ)
- ฟังก์ชันวัตถุประสงค์: ฟังก์ชันเชิงเส้นของตัวแปรในการตัดสินใจ ซึ่งต้องการหาค่าสูงสุดหรือต่ำสุด โดยแสดงเป้าหมายของปัญหาในเชิงปริมาณ (เช่น กำไรรวม ต้นทุนรวม)
- ข้อจำกัด: ระบบสมการเชิงเส้นและ/หรืออสมการเชิงเส้นที่ตัวแปรในการตัดสินใจต้องเป็นไปตาม ข้อจำกัดสะท้อนถึงขีดจำกัดของทรัพยากร ข้อกำหนดทางเทคโนโลยี การกำหนดแผนงาน และเงื่อนไขอื่น ๆ ของปัญหา
- บริเวณคำตอบที่ยอมรับได้ (Feasible Region): เซตของชุดค่าตัวแปรในการตัดสินใจทั้งหมดที่เป็นไปตามข้อจำกัดทุกข้อของปัญหา ในเชิงเรขาคณิตในปริภูมิหลายมิติ บริเวณนี้เป็นรูปทรงหลายเหลี่ยมนูน (polyhedron) ซึ่งอาจไม่มีขอบเขตหรือว่างเปล่า
- คำตอบที่ยอมรับได้: ชุดค่าตัวแปรใด ๆ ที่อยู่ในบริเวณคำตอบที่ยอมรับได้
- คำตอบที่เหมาะสมที่สุด: คำตอบที่ยอมรับได้ซึ่งฟังก์ชันวัตถุประสงค์บรรลุค่าสุดขีด (สูงสุดหรือต่ำสุด) หากมีคำตอบที่เหมาะสมที่สุดอยู่ จะพบได้ที่ขอบเขตของบริเวณคำตอบที่ยอมรับได้เสมอ อย่างน้อยที่จุดยอดหนึ่งของรูปทรงหลายเหลี่ยมนูน (ทฤษฎีบทพื้นฐานของการโปรแกรมเชิงเส้น)
วิธีการแก้ปัญหาการโปรแกรมเชิงเส้น
มีวิธีการหลักหลายวิธีในการแก้ปัญหาการโปรแกรมเชิงเส้น:
- วิธีกราฟิก: ใช้กับปัญหาที่มีตัวแปรในการตัดสินใจสองตัว ช่วยให้สามารถแสดงบริเวณคำตอบที่ยอมรับได้และฟังก์ชันวัตถุประสงค์บนระนาบได้อย่างชัดเจน และค้นหาคำตอบที่เหมาะสมที่สุดโดยการวิเคราะห์จุดยอดของบริเวณดังกล่าวหรือการเลื่อนเส้นระดับของฟังก์ชันวัตถุประสงค์
- วิธีซิมเพล็กซ์ (Simplex Method): อัลกอริทึมแบบวนซ้ำที่มีความเป็นสากล พัฒนาโดย George Dantzig วิธีนี้เคลื่อนที่จากจุดยอดหนึ่งของบริเวณคำตอบที่ยอมรับได้ไปยังจุดยอดที่อยู่ติดกัน โดยปรับปรุงค่าฟังก์ชันวัตถุประสงค์ในแต่ละขั้นตอนจนกว่าจะพบคำตอบที่เหมาะสมที่สุด เป็นวิธีคลาสสิกและเป็นที่รู้จักมากที่สุดในการแก้ปัญหาการโปรแกรมเชิงเส้น
- วิธีจุดภายใน (Interior Point Methods): กลุ่มอัลกอริทึมทางเลือกที่เกิดขึ้นหลังวิธีซิมเพล็กซ์ วิธีเหล่านี้เคลื่อนที่ไปสู่คำตอบที่เหมาะสมที่สุดภายในบริเวณคำตอบที่ยอมรับได้ ไม่ใช่ตามขอบเขตของบริเวณนั้น วิธีเหล่านี้มีประสิทธิภาพเป็นพิเศษสำหรับการแก้ปัญหาการโปรแกรมเชิงเส้นที่มีขนาดใหญ่มาก
ความเป็นคู่ในการโปรแกรมเชิงเส้น
สำหรับปัญหาการโปรแกรมเชิงเส้นทุกปัญหา (เรียกว่าปัญหาเดิม) สามารถสร้างปัญหาการโปรแกรมเชิงเส้นอีกปัญหาหนึ่งที่เรียกว่าปัญหาคู่ (dual problem) ได้ ปัญหาเดิมและปัญหาคู่มีความสัมพันธ์กันอย่างใกล้ชิด:
การแก้ปัญหาหนึ่งให้ข้อมูลเกี่ยวกับการแก้ปัญหาอีกปัญหาหนึ่ง ค่าที่เหมาะสมที่สุดของฟังก์ชันวัตถุประสงค์ในทั้งสองปัญหาเท่ากัน (หากมีอยู่) ตัวแปรของปัญหาคู่มีการตีความทางเศรษฐกิจที่สำคัญ ซึ่งสอดคล้องกับราคาเงา (หรือการประเมินค่าคู่) ของทรัพยากร โดยแสดงให้เห็นว่าค่าที่เหมาะสมที่สุดของฟังก์ชันวัตถุประสงค์ของปัญหาเดิมจะเปลี่ยนแปลงไปมากเพียงใดเมื่อมีการเปลี่ยนแปลงข้อจำกัดของทรัพยากรที่สอดคล้องกันเล็กน้อย
การประยุกต์ใช้การโปรแกรมเชิงเส้น
การโปรแกรมเชิงเส้นถูกนำไปใช้อย่างกว้างขวางใน:
- เศรษฐศาสตร์และธุรกิจ (การวางแผนการผลิต โลจิสติกส์ การเงิน การตลาด)
- อุตสาหกรรม (การหาค่าที่เหมาะสมของกระบวนการทางเทคโนโลยี การจัดการสินค้าคงคลัง การตัดวัสดุ)
- การขนส่ง (การหาค่าที่เหมาะสมของเส้นทาง ตารางเวลา) และเกษตรกรรม (การหาค่าที่เหมาะสมของพื้นที่เพาะปลูก สูตรอาหารสัตว์)
- พลังงาน (การหาค่าที่เหมาะสมของภาระของกำลังการผลิตไฟฟ้า)
เอกสารอ้างอิง
- Dantzig, George B. การโปรแกรมเชิงเส้น การประยุกต์ใช้และการวางนัยทั่วไป — มอสโก: Progress, 1966
- Yudin, D. B.; Golstein, E. G. การโปรแกรมเชิงเส้น (ทฤษฎี วิธีการ และการประยุกต์) — มอสโก: Nauka, 1969
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)
ดูเพิ่มเติม
- การวิจัยการดำเนินงาน
- การหาค่าที่เหมาะสม
- ฟังก์ชันวัตถุประสงค์
- ข้อจำกัด
- บริเวณคำตอบที่ยอมรับได้
- คำตอบที่เหมาะสมที่สุด