การโปรแกรมเชิงเส้นเชิงสุ่ม — การปรับให้เหมาะสมภายใต้ความไม่แน่นอนด้วยพารามิเตอร์สุ่ม
- ผู้เสนอ
- George B. Dantzig
- ปี
- 1955
- ประเภท
- Stochastic optimization model
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การโปรแกรมเชิงเส้นเชิงสุ่ม (Stochastic Linear Programming หรือ SLP) เป็นการขยายแนวคิดของการโปรแกรมเชิงเส้นแบบดั้งเดิมไปสู่สถานการณ์ที่พารามิเตอร์บางตัวของแบบจำลอง เช่น ต้นทุน ความต้องการ หรือความพร้อมของทรัพยากร มีความไม่แน่นอนและถูกจำลองเป็นตัวแปรสุ่ม โดยการปรับให้เหมาะสมกับต้นทุนที่คาดหวังภายใต้การแจกแจงความน่าจะเป็นของสถานการณ์ต่าง ๆ SLP จะสร้างการตัดสินใจที่ยังคงเป็นไปได้และใกล้เคียงค่าเหมาะสมที่สุดในอนาคตที่เป็นไปได้หลากหลายรูปแบบ แทนที่จะเป็นเพียงสถานะเดียวที่สมมติขึ้น
แนวคิดเบื้องหลังวิธีการ
การโปรแกรมเชิงเส้นแบบดั้งเดิมสมมติว่าทุกสัมประสิทธิ์เป็นที่ทราบอย่างแม่นยำ ในทางปฏิบัติ ความต้องการในอนาคต ราคา และผลผลิตล้วนมีความไม่แน่นอน SLP ได้ผนวกความไม่แน่นอนนี้เข้ากับแบบจำลองโดยตรง: แทนที่จะปรับให้เหมาะสมสำหรับสถานการณ์เดียวที่ตายตัว ผู้วางแผนจะเลือกการดำเนินการในระยะแรกในปัจจุบัน สังเกตว่าสถานการณ์ใดเกิดขึ้นจริง จากนั้นจึงดำเนินการแก้ไขเพื่อแก้ไขข้อบกพร่องหรือส่วนเกิน วัตถุประสงค์คือการลดต้นทุนรวมที่คาดหวังในทุกสถานการณ์ โดยปรับสมดุลระหว่างต้นทุนผูกพันกับการดำเนินการแก้ไขที่คาดหวัง ซึ่งสะท้อนตรรกะการบริหารจัดการในโลกแห่งความเป็นจริง — คุณตัดสินใจวันนี้ว่าจะสั่งซื้อล่วงหน้าเท่าใด และพรุ่งนี้คุณสามารถซื้อเพิ่มได้ในราคาพรีเมียม หรือขายส่วนเกินในราคาลด
ประวัติศาสตร์
การโปรแกรมเชิงสุ่มริเริ่มโดย George Dantzig ซึ่งนำเสนอแบบจำลองสองขั้นตอนในปี 1955 ไม่นานหลังจากที่พัฒนาวิธีซิมเพล็กซ์ Beale (1955) ได้เสนอแนวคิดที่คล้ายกันโดยอิสระ สาขาวิชานี้ได้รับการจัดระบบโดยตำราเรียนที่มีอิทธิพลของ Birge และ Louveaux ในปี 1997 และโดยการพัฒนาอัลกอริทึมการแยกส่วนแบบ L-shaped (Benders) ในช่วงทศวรรษ 1960–1980 ปัจจุบัน SLP เป็นพื้นฐานของการตัดสินใจเชิงปฏิบัติในด้านพลังงาน โลจิสติกส์ และการเงินทั่วโลก
ควรใช้เมื่อใด
ใช้ SLP เมื่อ: (1) พารามิเตอร์นำเข้าที่สำคัญมีความไม่แน่นอนอย่างแท้จริงและสามารถระบุได้ด้วยการแจกแจงความน่าจะเป็นหรือชุดสถานการณ์เชิงประจักษ์; (2) การตัดสินใจจะต้องทำขึ้นก่อนที่ความไม่แน่นอนจะคลี่คลาย แต่สามารถดำเนินการแก้ไขได้ในภายหลังโดยมีค่าใช้จ่าย; (3) วัตถุประสงค์และข้อจำกัดเป็นเชิงเส้นในตัวแปรการตัดสินใจ การประยุกต์ใช้ทั่วไป ได้แก่ การวางแผนการผลิต การออกแบบห่วงโซ่อุปทาน การจัดส่งพลังงาน และการปรับพอร์ตการลงทุนให้เหมาะสม ห้ามใช้ SLP เมื่อ: ความไม่แน่นอนไม่สามารถหาปริมาณเชิงความน่าจะเป็นได้ (ให้ใช้การปรับให้เหมาะสมแบบแข็งแกร่งแทน); ความสัมพันธ์ระหว่างการตัดสินใจและผลลัพธ์ไม่เป็นเชิงเส้นหรือเป็นจำนวนเต็ม (ให้ใช้ Stochastic MIP หรือ Stochastic Dynamic Programming); ชุดสถานการณ์มีขนาดใหญ่เกินกว่าที่จะแจกแจงได้และการแยกส่วนไม่สามารถทำได้ในเชิงคำนวณ; หรือเมื่อการวิเคราะห์ความไวเชิงกำหนดที่ง่ายกว่าเพียงพอที่จะเข้าใจผลกระทบของความไม่แน่นอน
ข้อจำกัดและข้อควรพิจารณา
- ต้องระบุการแจกแจงความน่าจะเป็นหรือชุดสถานการณ์สำหรับพารามิเตอร์ที่ไม่แน่นอน — การสมมติฐานการแจกแจงนี้มักจะตรวจสอบความถูกต้องได้ยาก
- ภาระการคำนวณเพิ่มขึ้นอย่างรวดเร็วตามจำนวนสถานการณ์และตัวแปรในขั้นตอนแรก; ปัญหาขนาดใหญ่ต้องใช้การแยกส่วนและทรัพยากรโปรแกรมแก้ปัญหาจำนวนมาก
- จำกัดเฉพาะวัตถุประสงค์และข้อจำกัดเชิงเส้น; โครงสร้างที่ไม่เป็นเชิงเส้นหรือจำนวนเต็มต้องใช้ส่วนขยายที่เพิ่มความซับซ้อนมากขึ้น
- วัตถุประสงค์ค่าคาดหวังอาจละเลยความเสี่ยงส่วนท้าย; รูปแบบที่หลีกเลี่ยงความเสี่ยง (CVaR, chance constraints) เพิ่มภาระในการสร้างแบบจำลองและการคำนวณ
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ผนวกความไม่แน่นอนเชิงความน่าจะเป็นเข้ากับการปรับให้เหมาะสมโดยตรง ทำให้เกิดการตัดสินใจที่แข็งแกร่งในทุกสถานการณ์ แทนที่จะเป็นเพียงอนาคตเดียวที่สมมติขึ้น
- กรอบการทำงานสองขั้นตอนสะท้อนกระบวนการตัดสินใจจริงอย่างใกล้ชิด: ผูกมัดตอนนี้ ปรับเปลี่ยนในภายหลังด้วยการดำเนินการแก้ไข
- ค่าของคำตอบเชิงสุ่ม (VSS) และ EVPI ให้เมตริกที่เป็นหลักการสำหรับการสื่อสารประโยชน์ของการจำลองความไม่แน่นอน
- ได้รับการสนับสนุนอย่างดีจากอัลกอริทึมที่สมบูรณ์ (L-shaped / Benders decomposition) และโปรแกรมแก้ปัญหาเชิงพาณิชย์ (CPLEX, Gurobi)
- ปรับขนาดได้สำหรับปัญหาเชิงปฏิบัติขนาดใหญ่ผ่านการแยกส่วน; สามารถประมวลผลแบบขนานในทุกสถานการณ์
การประยุกต์ใช้
- การวางแผนระบบไฟฟ้าและการผูกมัดหน่วยผลิตภายใต้ความไม่แน่นอนของการผลิตพลังงานหมุนเวียนและความต้องการ
- การออกแบบเครือข่ายห่วงโซ่อุปทานที่มีความไม่แน่นอนของความต้องการของลูกค้า ระยะเวลารอคอยสินค้า หรือต้นทุนการขนส่ง
- การวางแผนพืชผลและการชลประทานภายใต้ความไม่แน่นอนของปริมาณน้ำฝนและราคาสินค้าโภคภัณฑ์
- การปรับพอร์ตการลงทุนทางการเงินให้เหมาะสมกับผลตอบแทนสินทรัพย์ที่ไม่แน่นอนภายใต้งบประมาณและข้อจำกัดด้านกฎระเบียบ
- การจัดการรายได้ของสายการบินและการจัดตารางการทำงานของพนักงานภายใต้ความไม่แน่นอนของความต้องการผู้โดยสาร
- การจัดเตรียมเสบียงบรรเทาทุกข์ล่วงหน้าสำหรับโลจิสติกส์ด้านมนุษยธรรมก่อนสถานการณ์ภัยพิบัติที่ไม่แน่นอน
วิธีการทำงาน
วิธีการทำงาน
กำหนดแบบจำลองสองขั้นตอน: ตัวแปร x ในขั้นตอนแรกแสดงถึงการตัดสินใจ ณ ปัจจุบันที่ทำขึ้นก่อนที่ความไม่แน่นอนจะคลี่คลาย; วัตถุประสงค์คือการลดต้นทุนในขั้นตอนแรก c^T x บวกกับต้นทุนการดำเนินการแก้ไขที่คาดหวัง E[Q(x,xi)] เหนือเวกเตอร์สุ่ม xi ข้อจำกัด Ax = b จะต้องเป็นจริงสำหรับการตัดสินใจในขั้นตอนแรกโดยไม่คำนึงถึงสถานการณ์
สูตร
\min_{x} c^T x + \mathbb{E}_\xi[Q(x, \xi)] \quad \text{s.t. } Ax = b,\; x \geq 0แสดงเวกเตอร์สุ่ม xi ผ่านชุดสถานการณ์แบบไม่ต่อเนื่อง {xi_1, ..., xi_S} โดยแต่ละสถานการณ์มีความน่าจะเป็น p_s รวมกันเป็น 1 สถานการณ์สามารถดึงมาจากข้อมูลในอดีต การสอบถามผู้เชี่ยวชาญ หรือการสุ่มตัวอย่างแบบ Monte Carlo คุณภาพของชุดสถานการณ์เป็นตัวกำหนดคุณภาพของคำตอบอย่างยิ่ง เทคนิคการลดสถานการณ์ (เช่น การจัดกลุ่มด้วยระยะทาง Wasserstein) มักถูกนำมาใช้เพื่อรักษาขนาดของปัญหาให้อยู่ในระดับที่จัดการได้
สำหรับแต่ละสถานการณ์ xi_s ให้แก้ปัญหาย่อยของการดำเนินการแก้ไข: เมื่อกำหนดการตัดสินใจในขั้นตอนแรก x ให้หาการดำเนินการแก้ไข y_s ที่ถูกที่สุดที่สอดคล้องกับ W y_s = h(xi_s) - T(xi_s) x, y_s >= 0 หากไม่มีการดำเนินการแก้ไขที่เป็นไปได้ จะเกิดค่าปรับจำนวนมาก (หรือความเป็นไปไม่ได้) ซึ่งบ่งชี้ว่าการตัดสินใจในขั้นตอนแรกนั้นรุนแรงเกินไป
สูตร
Q(x, \xi) = \min_{y} q(\xi)^T y \quad \text{s.t. } W y = h(\xi) - T(\xi) x,\; y \geq 0แก้ปัญหาในรูปแบบขยายเต็ม (extensive form) (ทุกสถานการณ์ถูกรวมเป็น LP ขนาดใหญ่หนึ่งเดียว) สำหรับชุดสถานการณ์ขนาดเล็กถึงปานกลาง หรือใช้การแยกส่วนแบบ Benders (วิธี L-shaped) สำหรับชุดสถานการณ์ขนาดใหญ่ วิธี L-shaped จะเพิ่มข้อจำกัดด้านความเป็นไปได้และค่าเหมาะสมที่สุดให้กับปัญหาหลักซ้ำ ๆ จนกว่าจะบรรจบกัน โดยใช้ประโยชน์จากโครงสร้างบล็อกแนวทแยงของปัญหาย่อยของสถานการณ์
ประเมินคุณภาพของคำตอบผ่านค่าของคำตอบเชิงสุ่ม (Value of Stochastic Solution หรือ VSS) — ซึ่งคือผลกำไรที่ได้จากการแก้ปัญหาค่าเฉลี่ยเชิงกำหนด — และค่าคาดหวังของข้อมูลที่สมบูรณ์ (Expected Value of Perfect Information หรือ EVPI) — ซึ่งคือขอบเขตบนของมูลค่าของการคาดการณ์ที่สมบูรณ์แบบ รายงานการตัดสินใจในขั้นตอนแรก x*, ต้นทุนรวมที่คาดหวัง และต้นทุนการดำเนินการแก้ไขต่อสถานการณ์ เพื่อสื่อสารโปรไฟล์ความเสี่ยงไปยังผู้มีอำนาจตัดสินใจ
ข้อผิดพลาดที่พบบ่อย
- การใช้สถานการณ์น้อยเกินไปทำให้เกิดคำตอบที่มีอคติซึ่งทำงานได้ไม่ดีนอกตัวอย่าง; ควรตรวจสอบความถูกต้องด้วยการทดสอบสถานการณ์นอกตัวอย่างเสมอ
- สับสนระหว่างคำตอบเชิงกำหนดค่าเฉลี่ย (แทนค่าเฉลี่ย) กับคำตอบเชิงสุ่ม — VSS อาจมีค่ามากแม้ว่าพารามิเตอร์จะดูคงที่
- ละเลยความเป็นไปได้ของการดำเนินการแก้ไข: หากปัญหาย่อยในขั้นตอนที่สองไม่สามารถทำได้สำหรับบางสถานการณ์ แบบจำลองจำเป็นต้องมีข้อจำกัดการดำเนินการแก้ไขที่สมบูรณ์หรือค่าปรับที่ชัดเจน
- การปรับให้เข้ากับข้อมูลในอดีตมากเกินไปโดยไม่ทดสอบกับสถานการณ์ที่รุนแรงหรือสถานการณ์ที่ไม่พึงประสงค์ โดยเฉพาะอย่างยิ่งในการประยุกต์ใช้ในห่วงโซ่อุปทานหรือทางการเงิน
- การถือว่า Stochastic LP เป็นสิ่งทดแทนการปรับให้เหมาะสมแบบแข็งแกร่ง (robust optimization) เมื่อผู้มีอำนาจตัดสินใจมีความไม่แน่นอนมากกว่าที่จะเป็นกลางต่อค่าคาดหวัง
คำถามที่พบบ่อย
ความแตกต่างระหว่างการโปรแกรมเชิงเส้นเชิงสุ่มและการปรับให้เหมาะสมแบบแข็งแกร่งคืออะไร?
SLP ลดต้นทุนที่คาดหวังภายใต้การแจกแจงความน่าจะเป็นของสถานการณ์ และอนุญาตให้มีการดำเนินการแก้ไขหลังจากความไม่แน่นอนคลี่คลาย ในทางกลับกัน การปรับให้เหมาะสมแบบแข็งแกร่ง (robust optimization) จะปรับให้เหมาะสมกับกรณีที่เลวร้ายที่สุดภายใต้ชุดความไม่แน่นอนโดยไม่สมมติการแจกแจงความน่าจะเป็น และโดยทั่วไปจะสร้างคำตอบเดียวที่ตายตัวซึ่งเป็นไปได้สำหรับทุกสถานการณ์ SLP เหมาะสมกว่าเมื่อสามารถประมาณความน่าจะเป็นได้; การปรับให้เหมาะสมแบบแข็งแกร่งเหมาะสมกว่าเมื่อทราบเฉพาะชุดความไม่แน่นอน หรือเมื่อการป้องกันความเสี่ยงส่วนท้ายมีความสำคัญสูงสุด
โดยทั่วไปแล้วต้องใช้กี่สถานการณ์?
ขึ้นอยู่กับมิติของปัญหาและความซับซ้อนของการแจกแจง สถานการณ์จำนวนสิบถึงสองสามร้อยสถานการณ์มักจะเพียงพอสำหรับปัญหาการวางแผน หากสร้างขึ้นอย่างชาญฉลาด (เช่น ผ่านการจับคู่โมเมนต์หรือการลดสถานการณ์) การประมาณค่าเฉลี่ยตัวอย่าง (Sample Average Approximation หรือ SAA) ที่ใช้ Monte Carlo อาจต้องใช้สถานการณ์หลายพันสถานการณ์สำหรับคำตอบที่มีความแม่นยำสูง โดยมีช่วงความเชื่อมั่นเป็นแนวทางในการบรรจบกัน
SLP สามารถจัดการกับการตัดสินใจที่เป็นจำนวนเต็มหรือไบนารีได้หรือไม่?
ไม่โดยตรง — ตัวแปรจำนวนเต็มต้องใช้การโปรแกรมจำนวนเต็มเชิงสุ่ม (Stochastic Integer Programming หรือ SIP) หรือการโปรแกรมจำนวนเต็มผสมเชิงสุ่ม (Stochastic Mixed-Integer Programming หรือ SMIP) ซึ่งยากกว่ามากในเชิงคำนวณ SLP ใช้ได้เฉพาะเมื่อตัวแปรการตัดสินใจทั้งหมดเป็นแบบต่อเนื่อง
ค่าของคำตอบเชิงสุ่ม (VSS) วัดอะไร?
VSS = EEV - RP โดยที่ EEV คือต้นทุนที่คาดหวังของคำตอบเชิงกำหนดค่าเฉลี่ยที่ประเมินในทุกสถานการณ์ และ RP คือค่าเหมาะสมที่สุดเชิงสุ่มที่แท้จริง (ปัญหาการดำเนินการแก้ไข) VSS ที่สูงบ่งชี้ว่าการละเลยความไม่แน่นอนและการใช้พารามิเตอร์เฉลี่ยนำไปสู่ผลลัพธ์ที่แย่ลงอย่างมาก
โปรแกรมแก้ปัญหาและซอฟต์แวร์ใดบ้างที่รองรับการโปรแกรมเชิงเส้นเชิงสุ่ม?
โปรแกรมแก้ปัญหาเชิงพาณิชย์ เช่น CPLEX และ Gurobi สามารถแก้ปัญหาในรูปแบบขยายได้โดยตรง เฟรมเวิร์กโอเพนซอร์ส ได้แก่ ตัวอ่านรูปแบบ SMPS, PySP (ส่วนหนึ่งของ Pyomo) และแพ็คเกจ Julia StochasticPrograms.jl สำหรับปัญหาขนาดใหญ่ การนำอัลกอริทึมการแยกส่วนแบบ L-shaped มาใช้เองเป็นเรื่องปกติในการวิจัยและอุตสาหกรรม
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Dantzig, G. B., & Madansky, A. (1961). On the solution of two-stage linear programs under uncertainty. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1, 165–176.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วBirge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.
ISBN: 9780387982175คัดลอกแล้ว