การโปรแกรมเชิงเส้น — การหาค่าเหมาะสมที่สุดของฟังก์ชันวัตถุประสงค์เชิงเส้นภายใต้ข้อจำกัดเชิงเส้น
- ผู้เสนอ
- George B. Dantzig
- ปี
- 1947
- ประเภท
- Mathematical programming / continuous optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การโปรแกรมเชิงเส้น (Linear programming - LP) ซึ่งริเริ่มโดย George B. Dantzig ในปี 1947 เป็นวิธีการทางคณิตศาสตร์สำหรับการหาค่าที่ดีที่สุดของฟังก์ชันวัตถุประสงค์เชิงเส้น — เช่น ต้นทุนต่ำสุดหรือกำไรสูงสุด — ภายใต้ชุดของข้อจำกัดอสมการและสมการเชิงเส้น เป็นเทคนิคพื้นฐานในวิจัยดำเนินงาน และเป็นรากฐานของการวางแผนการผลิต การจัดสรรทรัพยากร โลจิสติกส์ ปัญหาการกำหนดอาหาร และสถานการณ์การตัดสินใจอื่นๆ อีกนับไม่ถ้วนในสาขาวิศวกรรม เศรษฐศาสตร์ และวิทยาศาสตร์ธรรมชาติ
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพว่าคุณดำเนินโรงงานขนาดเล็กที่ผลิตสินค้าสองชนิด สินค้าแต่ละชนิดสร้างกำไรให้คุณจำนวนหนึ่ง แต่การผลิตต้องใช้ทรัพยากรวัตถุดิบและเวลาเครื่องจักรที่จำกัด การโปรแกรมเชิงเส้นจะหาปริมาณการผลิตที่เหมาะสมที่สุดของสินค้าทั้งสองชนิดที่สามารถสร้างกำไรสูงสุดจากทรัพยากรที่มีอยู่ของคุณ โดยไม่ละเมิดข้อจำกัดทางกายภาพหรือตามสัญญาใดๆ คำว่า 'เชิงเส้น' หมายความว่ากำไรและการใช้ทรัพยากรจะเพิ่มขึ้นตามสัดส่วนโดยตรงกับปริมาณที่คุณผลิต ตัวเลือกที่เป็นไปได้จะก่อตัวเป็นรูปหลายเหลี่ยม (ในสองมิติ) หรือรูปทรงหลายหน้า (ในมิติที่สูงกว่า) และคำตอบที่เหมาะสมที่สุดมักจะอยู่ที่จุดยอดจุดใดจุดหนึ่ง
ประวัติศาสตร์
การพัฒนาการโปรแกรมเชิงเส้นอย่างเป็นระบบเริ่มต้นขึ้นในปี 1947 เมื่อ George B. Dantzig ซึ่งทำงานให้กับกองทัพอากาศสหรัฐฯ ได้คิดค้นอัลกอริทึมซิมเพล็กซ์เพื่อทำให้การวางแผนโลจิสติกส์ทางทหารเป็นไปโดยอัตโนมัติ Dantzig ได้ตีพิมพ์ทฤษฎีพื้นฐานในตำราของเขาในปี 1963 ซึ่งยังคงเป็นเอกสารอ้างอิงหลัก งานที่เป็นอิสระและขนานกันโดย Leonid Kantorovich ในสหภาพโซเวียต (1939) ได้กล่าวถึงการวางแผนการผลิตโดยใช้แนวคิดทางคณิตศาสตร์ที่คล้ายคลึงกัน และ Kantorovich ได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์ในปี 1975 ส่วนหนึ่งจากผลงานนี้ คำถามเชิงทฤษฎีเกี่ยวกับความเป็นไปได้ในการแก้ปัญหาในเวลาพหุนาม (polynomial-time solvability) ได้รับการตัดสินโดยวิธีวงรีของ Khachian (1979) และต่อมาโดยวิธีจุดภายในของ Karmarkar (1984) ซึ่งพิสูจน์แล้วว่ารวดเร็วในทางปฏิบัติสำหรับปัญหาขนาดใหญ่ ปัจจุบัน ตัวประมวลผล LP เชิงพาณิชย์และโอเพนซอร์สถูกรวมเข้ากับการวางแผนทรัพยากรองค์กร การจัดตารางการบิน และระบบพลังงานทั่วโลก
ควรใช้เมื่อใด
การโปรแกรมเชิงเส้นมีความเหมาะสมเมื่อใดก็ตามที่คุณต้องการหาค่าที่เหมาะสมที่สุดของปริมาณที่ขึ้นอยู่กับตัวแปรตัดสินใจเป็นเชิงเส้น และข้อจำกัดทั้งหมดก็เป็นเชิงเส้นเช่นกัน ไม่จำเป็นต้องมีข้อสมมติฐานเกี่ยวกับการแจกแจงหรือขนาดตัวอย่างขั้นต่ำ — เป็นแบบจำลองทางคณิตศาสตร์เชิงกำหนด (deterministic) ไม่ใช่ตัวประมาณค่าทางสถิติ วิธีการนี้ใช้ได้เมื่อตัวแปรตัดสินใจเป็นค่าต่อเนื่อง (ค่าเศษส่วนมีความหมาย); หากตัวแปรต้องเป็นจำนวนเต็มหรือเลขฐานสอง จะต้องใช้การโปรแกรมจำนวนเต็ม (integer programming) แทน LP ถูกใช้อย่างแพร่หลายในการจัดตารางการผลิต โลจิสติกส์ห่วงโซ่อุปทาน ปัญหาอาหารและส่วนผสม การหาค่าเหมาะสมที่สุดของพอร์ตการลงทุนทางการเงิน ปัญหาการขนส่งและการมอบหมายงาน และการจัดส่งพลังงาน
ข้อจำกัดและข้อควรพิจารณา
- ข้อกำหนดเชิงเส้น: หากฟังก์ชันวัตถุประสงค์หรือข้อจำกัดใดๆ ไม่เป็นเชิงเส้น แบบจำลอง LP จะระบุผิดพลาดและผลลัพธ์อาจไม่ถูกต้องหรือไม่สามารถใช้ได้
- ตัวแปรต่อเนื่องเท่านั้น: เมื่อตัวแปรตัดสินใจต้องมีค่าเป็นจำนวนเต็มหรือเลขฐานสอง (0/1) การผ่อนคลาย LP (LP relaxation) จะให้ค่าขอบเขตล่าง แต่ไม่ใช่ผลลัพธ์ที่ถูกต้อง จะต้องใช้การโปรแกรมจำนวนเต็ม (integer programming)
- เชิงกำหนด: LP ไม่ได้จำลองความไม่แน่นอนในพารามิเตอร์ จะต้องใช้การโปรแกรมเชิงสุ่ม (stochastic programming) หรือการหาค่าเหมาะสมที่สุดแบบทนทาน (robust optimisation) เมื่อข้อมูลไม่แน่นอน
- ความเสื่อมและการวนซ้ำ (Degeneracy and cycling): ในบางกรณีที่เกิดขึ้นไม่บ่อยนัก วิธีซิมเพล็กซ์อาจวนซ้ำระหว่างฐานที่เสื่อมโดยไม่ลู่เข้า แม้ว่ากฎป้องกันการวนซ้ำ (เช่น กฎของแบลนด์ - Bland's rule) จะแก้ไขปัญหานี้ได้
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ค่าเหมาะสมที่สุดทั่วโลกที่รับประกัน: เนื่องจากบริเวณที่เป็นไปได้เป็นรูปทรงหลายหน้าแบบนูน (convex polyhedron) ค่าเหมาะสมที่สุดเฉพาะที่ (local optimum) จึงเป็นค่าเหมาะสมที่สุดทั่วโลก (global optimum) ด้วย โดยไม่มีความเสี่ยงที่จะติดอยู่ในผลลัพธ์ที่ไม่เหมาะสมที่สุด
- ปรับขนาดได้สูง: ตัวประมวลผลสมัยใหม่ (HiGHS, Gurobi, CPLEX) สามารถจัดการแบบจำลองที่มีตัวแปรและข้อจำกัดนับล้านรายการได้ในเวลาไม่กี่วินาที
- ข้อมูลหลังการแก้ปัญหาที่สมบูรณ์: ราคาเงาและช่วงความไวให้ข้อมูลเชิงลึกที่นำไปปฏิบัติได้เกี่ยวกับมูลค่าทรัพยากรและความเสถียรของผลลัพธ์โดยไม่ต้องทำการคำนวณเพิ่มเติม
- ไม่มีข้อสมมติฐานเกี่ยวกับการแจกแจง: LP เป็นแบบจำลองเชิงพีชคณิตล้วนๆ ดังนั้นจึงไม่ต้องการการแจกแจงปกติ (normality) หรือคุณสมบัติทางสถิติใดๆ ของข้อมูล
การประยุกต์ใช้
- การวางแผนการผลิต: การหาปริมาณการผลิตที่เหมาะสมที่สุดที่ให้กำไรสูงสุด โดยเคารพขีดจำกัดของเครื่องจักรและวัตถุดิบ
- โลจิสติกส์ห่วงโซ่อุปทานและการขนส่ง: การลดต้นทุนการขนส่งผ่านเครือข่ายคลังสินค้าและลูกค้า
- ปัญหาอาหารและส่วนผสม: การเลือกปริมาณส่วนผสมที่ตรงตามข้อกำหนดทางโภชนาการด้วยต้นทุนที่ต่ำที่สุด
- การหาค่าเหมาะสมที่สุดของพอร์ตการลงทุนทางการเงิน: การจัดสรรเงินทุนในสินทรัพย์ต่างๆ เพื่อเพิ่มผลตอบแทนที่คาดหวัง ภายใต้ข้อจำกัดด้านความเสี่ยงและกฎระเบียบ
- การจัดส่งพลังงานและการจัดตารางกริดไฟฟ้า: การลดต้นทุนเชื้อเพลิง โดยตอบสนองความต้องการไฟฟ้าและขีดจำกัดกำลังการผลิตของเครื่องกำเนิดไฟฟ้า
- การจัดตารางพนักงานและกำลังคน: การจัดตารางกะให้กับพนักงานเพื่อครอบคลุมความต้องการด้วยต้นทุนแรงงานที่ต่ำที่สุด
วิธีการทำงาน
วิธีการทำงาน
ปัญหาการตัดสินใจในโลกแห่งความเป็นจริงจะถูกแปลงเป็นสัญลักษณ์ทางคณิตศาสตร์ คุณระบุตัวแปรตัดสินใจ (ปริมาณที่คุณสามารถควบคุมได้) เขียนฟังก์ชันวัตถุประสงค์ (สิ่งที่คุณต้องการหาค่าสูงสุดหรือต่ำสุด) ในรูปของผลรวมเชิงเส้นของตัวแปรเหล่านั้น และเขียนข้อจำกัดทุกข้อ — ขีดจำกัดทรัพยากร ขีดจำกัดกำลังการผลิต ความต้องการของตลาด — ในรูปของอสมการหรือสมการเชิงเส้น LP ที่กำหนดรูปแบบอย่างถูกต้องจะมีวัตถุประสงค์ที่ชัดเจน ขอบเขตของตัวแปรที่ระบุไว้อย่างชัดเจน และข้อจำกัดเชิงโครงสร้างทุกข้อแสดงในรูปเชิงเส้น
แบบจำลองจะถูกแปลงให้อยู่ในรูปแบบมาตรฐาน (canonical or standard form) ที่ตัวประมวลผลสามารถดำเนินการได้ อสมการจะถูกแปลงเป็นสมการโดยการเพิ่มตัวแปรส่วนเกิน (slack or surplus variables) ที่ไม่เป็นลบ และตัวแปรใดๆ ที่ไม่มีขอบเขตจะถูกแทนที่ด้วยผลต่างของตัวแปรที่ไม่เป็นลบสองตัว ขั้นตอนนี้เชิงกลจะสร้างตาราง (tableau) หรือเมทริกซ์ที่อัลกอริทึมทำงานด้วย และจะไม่เปลี่ยนแปลงปัญหา — เพียงแต่ปรับเปลี่ยนรูปแบบเพื่อการคำนวณ
ตัวประมวลผลจะค้นหารูปทรงหลายหน้าที่เป็นไปได้เพื่อหาจุดยอดที่เหมาะสมที่สุด วิธีซิมเพล็กซ์ (Simplex method) แบบดั้งเดิมจะเคลื่อนที่จากจุดยอดหนึ่งไปยังอีกจุดยอดหนึ่งตามขอบของรูปทรงหลายหน้า โดยปรับปรุง (หรือคงไว้) ซึ่งฟังก์ชันวัตถุประสงค์เสมอ จนกว่าจะไม่มีจุดยอดข้างเคียงที่สามารถปรับปรุงได้อีกต่อไป วิธีการจุดภายใน (interior-point methods) จะเดินทางผ่านภายในของบริเวณที่เป็นไปได้ตามเส้นทางกลาง ซึ่งมีประสิทธิภาพโดยเฉพาะอย่างยิ่งสำหรับแบบจำลองขนาดใหญ่มาก ทั้งสองกลุ่มรับประกันว่าจะหาค่าเหมาะสมที่สุดทั่วโลกได้เมื่อมีอยู่ เนื่องจากบริเวณที่เป็นไปได้เป็นรูปทรงนูน (convex)
ตัวประมวลผลจะส่งคืนค่าที่เหมาะสมที่สุดของตัวแปรตัดสินใจและค่าวัตถุประสงค์ที่เหมาะสมที่สุด พร้อมด้วยตัวแปรคู่ (shadow prices) และช่วงความไว (sensitivity ranges) ราคาเงา (shadow prices) จะวัดว่าฟังก์ชันวัตถุประสงค์จะดีขึ้นเท่าใดหากข้อจำกัดที่ผูกมัดถูกผ่อนปรนไปหนึ่งหน่วย — ซึ่งบอกผู้มีอำนาจตัดสินใจโดยตรงว่าทรัพยากรเพิ่มเติมจะมีค่ามากที่สุดที่ใด การวิเคราะห์ความไว (sensitivity analysis) จะระบุว่าสัมประสิทธิ์ต้นทุนหรือค่าด้านขวา (right-hand-side value) สามารถเปลี่ยนแปลงได้มากน้อยเพียงใดก่อนที่ฐานปัจจุบัน (basis) จะไม่เหมาะสมที่สุดอีกต่อไป
ข้อผิดพลาดที่พบบ่อย
- การใช้ LP เมื่อข้อจำกัดหรือฟังก์ชันวัตถุประสงค์ไม่เป็นเชิงเส้น — ผลลัพธ์จะผิดพลาด หรือตัวประมวลผลจะปฏิเสธแบบจำลอง
- การละเลยข้อกำหนดจำนวนเต็ม: การปัดเศษผลลัพธ์ LP แบบต่อเนื่องให้เป็นจำนวนเต็มโดยทั่วไปแล้วไม่ได้ให้ผลลัพธ์จำนวนเต็มที่สามารถใช้ได้หรือเหมาะสมที่สุด ให้ใช้การโปรแกรมจำนวนเต็มแทน
- แบบจำลองที่ไม่สามารถหาค่าได้ (infeasible) หรือไม่มีขอบเขต (unbounded): หากบริเวณที่เป็นไปได้ว่างเปล่า (ข้อขัดแย้งกัน) หรือฟังก์ชันวัตถุประสงค์ไม่มีขอบเขต (ขาดข้อจำกัดขอบเขต) ตัวประมวลผลจะรายงานความล้มเหลว — ควรตรวจสอบโครงสร้างแบบจำลองเสมอ ก่อนดำเนินการ
- การปฏิบัติต่อผลลัพธ์ LP ในฐานะคำแนะนำโดยไม่มีการวิเคราะห์ความไว: ผลลัพธ์ที่เหมาะสมที่สุดทางเทคนิคอาจอยู่บนขอบที่บางมาก ซึ่งการเปลี่ยนแปลงข้อมูลเพียงเล็กน้อยก็สามารถพลิกคำแนะนำได้ — ควรตรวจสอบช่วงความไวเสมอ
คำถามที่พบบ่อย
อะไรทำให้ปัญหา 'เชิงเส้น' สำหรับวัตถุประสงค์ของ LP?
ทั้งฟังก์ชันวัตถุประสงค์และข้อจำกัดทุกข้อต้องเป็นเชิงเส้น — หมายความว่าแต่ละเทอมคือค่าคงที่คูณด้วยตัวแปรตัดสินใจเพียงตัวเดียว โดยไม่มีผลคูณของตัวแปร ไม่มีเลขชี้กำลัง และไม่มีฟังก์ชันที่ไม่เป็นเชิงเส้น หากมีข้อจำกัดหรือวัตถุประสงค์เพียงข้อเดียวที่เกี่ยวข้องกับ เช่น x คูณ y หรือ x ยกกำลังสอง การใช้ LP มาตรฐานจะไม่สามารถใช้ได้ และจำเป็นต้องใช้ตัวประมวลผลการโปรแกรมแบบไม่เชิงเส้น (nonlinear programming) หรือการโปรแกรมกำลังสอง (quadratic programming)
เหตุใดผลลัพธ์ที่เหมาะสมที่สุดจึงอยู่ที่จุดยอดของบริเวณที่เป็นไปได้เสมอ?
บริเวณที่เป็นไปได้ที่กำหนดโดยข้อจำกัดเชิงเส้นคือรูปทรงหลายหน้าแบบนูน (convex polyhedron) หรือรูปทรงหลายหน้าปิด (polytope) ฟังก์ชันวัตถุประสงค์เชิงเส้นนั้นเป็นเชิงเส้นเอง จึงไม่สามารถ 'ดึง' ไปยังภายในของเซตนูนได้ — มันจะบรรลุค่าสุดขีดบนขอบเสมอ และโดยเฉพาะอย่างยิ่งที่จุดยอด (corner point) นี่คือข้อมูลเชิงลึกทางเรขาคณิตที่เป็นรากฐานของกลยุทธ์การเคลื่อนที่จากจุดยอดไปยังจุดยอดของวิธีซิมเพล็กซ์
เมื่อใดที่ฉันควรใช้การโปรแกรมจำนวนเต็มแทน LP?
เมื่อใดก็ตามที่ตัวแปรตัดสินใจหนึ่งตัวหรือมากกว่านั้นต้องมีค่าเป็นจำนวนเต็มหรือเลขฐานสอง (0/1) — ตัวอย่างเช่น การตัดสินใจว่าจะเปิดสถานประกอบการหรือไม่ (ใช่/ไม่ใช่) จะจัดส่งรถบรรทุกกี่คัน (จำนวนเต็ม) หรือจะรวมรายการใดบ้างในการเลือก การแก้ LP แล้วปัดเศษผลลัพธ์แบบต่อเนื่องนั้นไม่น่าเชื่อถือ: ผลลัพธ์ที่ปัดเศษอาจไม่สามารถใช้ได้หรือห่างไกลจากค่าที่เหมาะสมที่สุด การโปรแกรมจำนวนเต็มจัดการกับความเป็นจำนวนเต็มได้อย่างถูกต้อง แต่มีต้นทุนการคำนวณที่สูงกว่า
ราคาเงาบอกอะไรฉัน?
ราคาเงา (ตัวแปรคู่ - dual variable) สำหรับข้อจำกัดที่ผูกมัด (binding constraint) บ่งชี้ว่าค่าวัตถุประสงค์ที่เหมาะสมที่สุดจะดีขึ้นเท่าใดหากค่าด้านขวาของข้อจำกัดนั้นถูกผ่อนปรนไปหนึ่งหน่วย โดยที่ทุกอย่างอื่นคงที่ ตัวอย่างเช่น ราคาเงาเท่ากับ 3 สำหรับข้อจำกัดชั่วโมงแรงงานหมายความว่าการเพิ่มแรงงานอีกหนึ่งชั่วโมงจะทำให้วัตถุประสงค์ดีขึ้น 3 หน่วย ข้อจำกัดที่ไม่ผูกมัดจะมีราคาเงาเป็นศูนย์ — ข้อจำกัดเหล่านั้นไม่ได้จำกัดค่าที่เหมาะสมที่สุดในปัจจุบัน
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
ISBN: 9780691059136คัดลอกแล้วVanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว