การโปรแกรมเชิงเส้นแบบกำหนดได้ (Deterministic Linear Programming) — LP แบบคลาสสิกที่มีพารามิเตอร์ที่แน่นอน
- ผู้เสนอ
- George B. Dantzig
- ปี
- 1947
- ประเภท
- Deterministic mathematical optimization
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การโปรแกรมเชิงเส้นแบบกำหนดได้ (Deterministic Linear Programming, DLP) คือรูปแบบคลาสสิกของการโปรแกรมเชิงเส้น ซึ่งสัมประสิทธิ์ฟังก์ชันวัตถุ สัมประสิทธิ์ข้อจำกัด และค่าทางด้านขวาของสมการ ทั้งหมดเป็นที่ทราบแน่นอน DLP หาการจัดสรรทรัพยากรที่เหมาะสมที่สุดเพื่อเพิ่มหรือลดฟังก์ชันวัตถุเชิงเส้นภายใต้ข้อจำกัดเชิงเส้น โดยให้ผลลัพธ์ที่แม่นยำและทำซ้ำได้ภายใต้ข้อมูลที่คงที่และแน่นอน
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพการจัดสรรงบประมาณคงที่ให้กับโครงการต่างๆ ซึ่งแต่ละโครงการมีต้นทุนและผลตอบแทนที่ทราบแน่นอน ภายใต้ข้อจำกัดด้านทรัพยากรที่คุณทราบอย่างแม่นยำ DLP จะเข้ารหัสสิ่งนี้เป็นระบบอสมการเชิงเส้น และหาผลเฉลยที่จุดมุม (corner-point solution) ที่ดึงคุณค่าสูงสุดจากข้อจำกัดเหล่านั้น เนื่องจากพารามิเตอร์ทุกตัวมีความแน่นอน — ไม่มีการแจกแจงความน่าจะเป็น ไม่มีความคลุมเครือ — ตัวแก้ปัญหา (solver) จะให้แผนที่เหมาะสมที่สุดเพียงแผนเดียว แทนที่จะเป็นชุดผลลัพธ์ที่หลากหลาย ความชัดเจนนี้ทำให้ DLP เป็นแบบจำลองทางเลือกแรกตามธรรมชาติเมื่อข้อมูลได้รับการวัดผลอย่างดีและไม่มีความไม่แน่นอนเป็นข้อกังวลหลัก
ประวัติศาสตร์
การโปรแกรมเชิงเส้นได้รับการกำหนดรูปแบบอย่างเป็นทางการโดย George B. Dantzig ในปี 1947 ด้วยการพัฒนาอัลกอริทึม Simplex ขณะทำงานให้กับกองทัพอากาศสหรัฐฯ เอกสารอ้างอิงของ Dantzig ในปี 1963 กลายเป็นเอกสารอ้างอิงหลัก คำคุณศัพท์ 'deterministic' เกิดขึ้นเมื่อมีการนำรูปแบบ LP แบบสุ่ม (stochastic LP) มาใช้ (Dantzig and Beale, ทศวรรษ 1950–1960) เพื่อแยกความแตกต่างระหว่างแบบจำลองพารามิเตอร์ที่แน่นอนดั้งเดิมกับส่วนขยายเชิงความน่าจะเป็น
ควรใช้เมื่อใด
ใช้ DLP เมื่อปัญหาการตัดสินใจสามารถจำลองได้ด้วยฟังก์ชันวัตถุเชิงเส้นและข้อจำกัดเชิงเส้น และเมื่อพารามิเตอร์ทั้งหมดเป็นที่ทราบแน่นอนเพียงพอที่จะถือว่าเป็นค่าคงที่ เหมาะสำหรับสถานการณ์ เช่น การวางแผนการผลิต การขนส่งและโลจิสติกส์ ปัญหาการกำหนดอาหารและส่วนผสม และปัญหาการไหลในเครือข่ายภายใต้สภาวะที่คงที่ **ห้าม** ใช้ DLP เมื่อพารามิเตอร์มีความไม่แน่นอนอย่างแท้จริงและมีความเสี่ยง — ควรเลือกใช้ Stochastic LP หรือ Robust LP แทน หลีกเลี่ยง DLP เมื่อฟังก์ชันวัตถุหรือข้อจำกัดไม่เป็นเชิงเส้น เมื่อตัวแปรต้องเป็นจำนวนเต็ม (ใช้ MIP) หรือเมื่อต้องสร้างสมดุลระหว่างวัตถุประสงค์ที่ขัดแย้งกันหลายประการโดยไม่รวมเข้าเป็นผลรวมถ่วงน้ำหนักเดียว (ใช้ multi-objective LP หรือ goal programming)
ข้อจำกัดและข้อควรพิจารณา
- ต้องการให้ความสัมพันธ์ทั้งหมดเป็นเชิงเส้นอย่างเคร่งครัด — ไม่สามารถจับเส้นโค้งต้นทุนที่ไม่เป็นเชิงเส้นหรือผลตอบแทนที่ลดลงได้หากไม่มีการประมาณค่า
- พารามิเตอร์ทั้งหมดต้องเป็นที่ทราบและคงที่ แบบจำลองไม่มีกลไกพื้นฐานในการจัดการกับความไม่แน่นอนหรือข้อผิดพลาดในการประมาณค่าพารามิเตอร์
- ผลเฉลยที่เหมาะสมที่สุดอาจไม่ซ้ำกัน (degenerate) ทำให้การเลือกฐานที่รายงานมีความคลุมเครือหากไม่มีเกณฑ์เพิ่มเติม
- ข้อกำหนดที่เป็นจำนวนเต็มหรือเชิงการจัด (เช่น การตัดสินใจ ใช่/ไม่ใช่) ต้องขยายไปยังการโปรแกรมเชิงจำนวนเต็มแบบผสม (mixed-integer programming) ซึ่งมีความซับซ้อนในการคำนวณมากกว่า
- ปัญหาขนาดใหญ่ที่มีเมทริกซ์ข้อจำกัดที่หนาแน่นอาจใช้หน่วยความจำมาก แม้แต่สำหรับตัวแก้ปัญหาที่ทันสมัย
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- รับประกันผลเฉลยที่เหมาะสมที่สุดทั่วโลกสำหรับกรณี LP ที่เป็นไปได้และมีขอบเขตใดๆ เนื่องจากความเป็นเว้า
- ปรับขนาดได้สูง — ตัวแก้ปัญหาที่ทันสมัยสามารถจัดการตัวแปรและข้อจำกัดนับล้านได้ในไม่กี่วินาที
- ตัวแปรคู่และการวิเคราะห์ความไวให้การตีความทางเศรษฐศาสตร์ที่สมบูรณ์ของราคาเงาและการหาช่วง (ranging)
- รูปแบบที่โปร่งใส ตรวจสอบได้: ทุกสมมติฐานระบุไว้อย่างชัดเจนในเมทริกซ์ข้อจำกัด
- ระบบซอฟต์แวร์ที่พัฒนาแล้ว (CPLEX, Gurobi, HiGHS, GLPK) พร้อมการใช้งานที่เชื่อถือได้และผ่านการทดสอบมาอย่างดี
- สัญญาณความสามารถในการเป็นไปได้ที่ชัดเจน (ผ่าน/ไม่ผ่าน): ความเป็นไปไม่ได้จะเปิดเผยการระบุแบบจำลองที่ผิดพลาดทันที
การประยุกต์ใช้
- การจัดตารางการผลิตและการผลิตด้วยกำลังการผลิตทรัพยากรคงที่และความต้องการที่ทราบ
- การขนส่งและโลจิสติกส์: การหาเส้นทางการขนส่งต้นทุนต่ำสุดผ่านเครือข่าย
- ปัญหาการกำหนดอาหารและส่วนผสม: การกำหนดส่วนผสมอาหารหรือสารเคมีต้นทุนต่ำสุดที่ตรงตามข้อจำกัดองค์ประกอบ
- การหาค่าที่เหมาะสมที่สุดของพอร์ตการลงทุนทางการเงินภายใต้ผลตอบแทนเชิงเส้นและข้อจำกัดด้านงบประมาณ
- การวางแผนระบบพลังงาน: การจัดส่งหน่วยผลิตไฟฟ้าที่เหมาะสมที่สุดด้วยต้นทุนและความจุที่ทราบ
- การออกแบบเครือข่ายห่วงโซ่อุปทานเมื่อความต้องการและระยะเวลานำถูกพิจารณาว่าเป็นค่าคงที่ที่ทราบ
วิธีการทำงาน
วิธีการทำงาน
กำหนดตัวแปรตัดสินใจ x (เช่น ปริมาณการผลิต จำนวนการไหล), ฟังก์ชันวัตถุ c^T x เพื่อหาค่าต่ำสุดหรือสูงสุด, และชุดข้อจำกัด Ax <= b โดยที่ x >= 0 สัมประสิทธิ์ทั้งหมดใน c, A, และ b จะถูกพิจารณาว่าเป็นค่าคงที่ที่ทราบแน่นอน — นี่คือสิ่งที่ทำให้แบบจำลองเป็นแบบกำหนดได้ เขียน LP ในรูปแบบมาตรฐาน: min c^T x ภายใต้ข้อจำกัด Ax = b, x >= 0
สูตร
\min_{x} \; c^\top x \quad \text{s.t.} \quad Ax \leq b, \; x \geq 0ก่อนทำการหาค่าที่เหมาะสมที่สุด ให้ตรวจสอบว่าบริเวณที่เป็นไปได้ (feasible region) ไม่ว่างเปล่า (ชุดข้อจำกัดมีอย่างน้อยหนึ่งผลเฉลย) และฟังก์ชันวัตถุมีขอบเขต หากบริเวณที่เป็นไปได้ว่างเปล่า ปัญหานั้นจะเป็นไปไม่ได้ (infeasible) หากฟังก์ชันวัตถุไม่มีขอบเขต แบบจำลองนั้นระบุผิดพลาด (mis-specified) การตรวจสอบเหล่านี้จะดำเนินการโดยอัตโนมัติโดยตัวแก้ปัญหา แต่ผู้ทำการวิเคราะห์ควรตีความเพื่อจับข้อผิดพลาดในการกำหนดรูปแบบ (formulation errors)
แก้ปัญหา LP โดยใช้วิธีซิมเพล็กซ์ (Simplex algorithm) (การหมุนเวียนตามขอบของรูปทรงหลายเหลี่ยมเว้า (convex polytope) ไปยังจุดยอดที่เหมาะสมที่สุด) หรือวิธีจุดภายใน (interior-point method) (การติดตามเส้นทางผ่านภายในของบริเวณที่เป็นไปได้) ทั้งสองแนวทางใช้ประโยชน์จากความเป็นเว้าของเซตที่เป็นไปได้และความเป็นเชิงเส้นของฟังก์ชันวัตถุ รับประกันว่าค่าที่เหมาะสมที่สุดเฉพาะที่ (local optimum) จะเป็นค่าที่เหมาะสมที่สุดทั่วโลก (global optimum) ตัวแก้ปัญหาที่ทันสมัย (CPLEX, Gurobi, HiGHS) สามารถจัดการตัวแปรและข้อจำกัดนับล้านได้อย่างมีประสิทธิภาพ
ตัวแก้ปัญหาจะส่งคืนเวกเตอร์การตัดสินใจที่เหมาะสมที่สุด x* และค่าฟังก์ชันวัตถุที่เหมาะสมที่สุด c^T x* เนื่องจากบริเวณที่เป็นไปได้เป็นรูปทรงหลายเหลี่ยมเว้าและฟังก์ชันวัตถุเป็นเชิงเส้น ค่าที่เหมาะสมที่สุดจึงมักจะเกิดขึ้นที่จุดยอด (basic feasible solution) บันทึก x* และตรวจสอบว่าสอดคล้องกับข้อจำกัดทั้งหมด จากนั้นจึงแปลกลับเป็นคำศัพท์ทางการจัดการ (เช่น หน่วยที่จะผลิต เส้นทางที่จะใช้)
สูตร
x^* = \arg\min \{ c^\top x : Ax \leq b,\; x \geq 0 \}หลังจากได้ x* แล้ว ให้ทำการวิเคราะห์ความไว (sensitivity analysis) หรือการวิเคราะห์หลังการหาค่าที่เหมาะสมที่สุด (post-optimality analysis) เพื่อระบุว่าสัมประสิทธิ์แต่ละตัวใน c หรือ b สามารถเปลี่ยนแปลงได้มากน้อยเพียงใดก่อนที่ฐานปัจจุบัน — และดังนั้นผลเฉลยที่เหมาะสมที่สุด — จะเปลี่ยนแปลงไป ราคาเงา (shadow prices) หรือตัวแปรคู่ (dual variables) จะวัดค่าของส่วนเพิ่ม (marginal value) ของการผ่อนปรนข้อจำกัดแต่ละข้อ แม้ว่าแบบจำลองจะเป็นแบบกำหนดได้ การวิเคราะห์ความไวจะเผยให้เห็นความทนทานของผลเฉลยต่อข้อผิดพลาดในการประมาณค่าพารามิเตอร์ โดยไม่ต้องละทิ้งกรอบการทำงานแบบกำหนดได้
ข้อผิดพลาดที่พบบ่อย
- การพิจารณาพารามิเตอร์ที่ไม่แน่นอนเป็นค่าประมาณจุดคงที่โดยไม่มีการวิเคราะห์ความไวตามมา อาจให้ผลเฉลยที่ดูเหมือนเหมาะสมที่สุดในทางทฤษฎี แต่เปราะบางในทางปฏิบัติ
- การลืมใส่ข้อจำกัดการไม่เป็นลบ (non-negativity constraints) หรือขอบเขตเชิงตรรกะ อาจให้ผลเฉลยที่เหมาะสมที่สุดทางคณิตศาสตร์ แต่ไม่สามารถนำไปปฏิบัติได้จริง (เช่น ปริมาณการผลิตติดลบ)
- การตีความราคาเงาผิดพลาดว่าเป็นค่าส่วนเพิ่มที่รับประกันได้นอกช่วงความถูกต้องที่ระบุในการวิเคราะห์การหาช่วง
- การใช้ DLP เมื่อปัญหาที่แท้จริงมีโครงสร้างจำนวนเต็ม (เช่น จำนวนรถบรรทุก) และการปัดเศษผลเฉลย LP — สิ่งนี้อาจละเมิดข้อจำกัดหรือพลาดค่าที่เหมาะสมที่สุดที่แท้จริง
- การรวมวัตถุประสงค์มากเกินไปเป็นผลรวมถ่วงน้ำหนักเดียวโดยไม่ตรวจสอบว่าน้ำหนักสะท้อนความชอบของผู้มีส่วนได้ส่วนเสียอย่างถูกต้องหรือไม่ ทำให้มองข้ามการแลกเปลี่ยนที่สำคัญ
คำถามที่พบบ่อย
อะไรทำให้ LP เป็น 'deterministic' ตรงกันข้ามกับ 'stochastic'?
ในการโปรแกรมเชิงเส้นแบบกำหนดได้ (deterministic LP) สัมประสิทธิ์ทุกตัวในฟังก์ชันวัตถุ เมทริกซ์ข้อจำกัด และเวกเตอร์ค่าทางด้านขวาเป็นค่าคงที่ที่ทราบ ในทางตรงกันข้าม Stochastic LP ถือว่าสัมประสิทธิ์บางส่วนหรือทั้งหมดเป็นตัวแปรสุ่มที่มีการแจกแจงความน่าจะเป็น โดยพยายามหาผลเฉลยที่ทำงานได้ดีโดยเฉลี่ยหรือมีความน่าจะเป็นสูงในสถานการณ์ต่างๆ
อัลกอริทึม Simplex มีประสิทธิภาพเสมอหรือไม่?
ในทางปฏิบัติ ใช่ — วิธี Simplex แก้ปัญหา LP ในโลกแห่งความเป็นจริงเกือบทั้งหมดได้อย่างรวดเร็วอย่างยิ่ง ในทางทฤษฎี อาจใช้เวลาเป็นเลขชี้กำลังในกรณีที่เลวร้ายที่สุด (ตัวอย่าง Klee–Minty) แต่วิธีจุดภายใน (เช่น อัลกอริทึม Karmarkar) ทำงานในเวลาพหุนามและสามารถแข่งขันได้สำหรับอินสแตนซ์ที่มีขนาดใหญ่มาก
ฉันสามารถใช้ DLP ได้หรือไม่หากตัวแปรตัดสินใจบางตัวของฉันต้องเป็นจำนวนเต็ม?
ไม่ได้ หากตัวแปรต้องเป็นจำนวนเต็ม (เช่น จำนวนเครื่องจักรที่จะซื้อ) แบบจำลองจะกลายเป็นการโปรแกรมเชิงจำนวนเต็มแบบผสม (mixed-integer programming) หรือการโปรแกรมเชิงจำนวนเต็มล้วน (pure integer programming) การแก้ปัญหาการผ่อนคลาย LP (LP relaxation) และการปัดเศษอาจละเมิดข้อจำกัดหรือพลาดค่าที่เหมาะสมที่สุดที่เป็นจำนวนเต็มที่แท้จริง ควรใช้ตัวแก้ปัญหา MIP โดยเฉพาะแทน
ราคาเงาช่วยได้อย่างไรหลังจากแก้ปัญหา?
ราคาเงา (ตัวแปรคู่) ของข้อจำกัดจะบอกคุณว่าค่าฟังก์ชันวัตถุจะปรับปรุงได้เท่าใดหากข้อจำกัดด้านขวาของข้อจำกัดนั้นถูกผ่อนปรนไปหนึ่งหน่วย ภายในช่วงความถูกต้องของการหาช่วง (ranging interval) สิ่งนี้จะช่วยในการตัดสินใจว่าจะลงทุนที่ใดเพื่อขยายกำลังการผลิตอย่างคุ้มค่าที่สุด
เมื่อใดที่ฉันควรเปลี่ยนจาก DLP เป็น Robust LP หรือ Stochastic LP?
ควรเปลี่ยนเมื่อความไม่แน่นอนของพารามิเตอร์มีความสำคัญ และต้นทุนของผลเฉลยที่ไม่สามารถเป็นไปได้หรือไม่ดีภายใต้ค่าพารามิเตอร์ที่เกิดขึ้นจริงนั้นมีนัยสำคัญ หากการเบี่ยงเบน 10–20% ในสัมประสิทธิ์ที่สำคัญจะเปลี่ยนผลเฉลยที่ต้องการหรือทำให้เกิดการละเมิดข้อจำกัด สมมติฐานความแน่นอนของ DLP จะแข็งแกร่งเกินไป
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press, Princeton, NJ.
ISBN: 9780691059136คัดลอกแล้วLinear programming. Wikipedia.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว