Skip to content
กลับไปยังผลการค้นหา

การโปรแกรมเชิงเส้นเชิงสุ่ม — การปรับให้เหมาะสมภายใต้ความไม่แน่นอนด้วยพารามิเตอร์สุ่ม

ผู้เสนอ
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)
  • ปรับขนาดได้สำหรับปัญหาเชิงปฏิบัติขนาดใหญ่ผ่านการแยกส่วน; สามารถประมวลผลแบบขนานในทุกสถานการณ์

การประยุกต์ใช้

  • การวางแผนระบบไฟฟ้าและการผูกมัดหน่วยผลิตภายใต้ความไม่แน่นอนของการผลิตพลังงานหมุนเวียนและความต้องการ
  • การออกแบบเครือข่ายห่วงโซ่อุปทานที่มีความไม่แน่นอนของความต้องการของลูกค้า ระยะเวลารอคอยสินค้า หรือต้นทุนการขนส่ง
  • การวางแผนพืชผลและการชลประทานภายใต้ความไม่แน่นอนของปริมาณน้ำฝนและราคาสินค้าโภคภัณฑ์
  • การปรับพอร์ตการลงทุนทางการเงินให้เหมาะสมกับผลตอบแทนสินทรัพย์ที่ไม่แน่นอนภายใต้งบประมาณและข้อจำกัดด้านกฎระเบียบ
  • การจัดการรายได้ของสายการบินและการจัดตารางการทำงานของพนักงานภายใต้ความไม่แน่นอนของความต้องการผู้โดยสาร
  • การจัดเตรียมเสบียงบรรเทาทุกข์ล่วงหน้าสำหรับโลจิสติกส์ด้านมนุษยธรรมก่อนสถานการณ์ภัยพิบัติที่ไม่แน่นอน

วิธีการทำงาน

วิธีการทำงาน

1

กำหนดแบบจำลองสองขั้นตอน: ตัวแปร 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
2

แสดงเวกเตอร์สุ่ม xi ผ่านชุดสถานการณ์แบบไม่ต่อเนื่อง {xi_1, ..., xi_S} โดยแต่ละสถานการณ์มีความน่าจะเป็น p_s รวมกันเป็น 1 สถานการณ์สามารถดึงมาจากข้อมูลในอดีต การสอบถามผู้เชี่ยวชาญ หรือการสุ่มตัวอย่างแบบ Monte Carlo คุณภาพของชุดสถานการณ์เป็นตัวกำหนดคุณภาพของคำตอบอย่างยิ่ง เทคนิคการลดสถานการณ์ (เช่น การจัดกลุ่มด้วยระยะทาง Wasserstein) มักถูกนำมาใช้เพื่อรักษาขนาดของปัญหาให้อยู่ในระดับที่จัดการได้

3

สำหรับแต่ละสถานการณ์ 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
4

แก้ปัญหาในรูปแบบขยายเต็ม (extensive form) (ทุกสถานการณ์ถูกรวมเป็น LP ขนาดใหญ่หนึ่งเดียว) สำหรับชุดสถานการณ์ขนาดเล็กถึงปานกลาง หรือใช้การแยกส่วนแบบ Benders (วิธี L-shaped) สำหรับชุดสถานการณ์ขนาดใหญ่ วิธี L-shaped จะเพิ่มข้อจำกัดด้านความเป็นไปได้และค่าเหมาะสมที่สุดให้กับปัญหาหลักซ้ำ ๆ จนกว่าจะบรรจบกัน โดยใช้ประโยชน์จากโครงสร้างบล็อกแนวทแยงของปัญหาย่อยของสถานการณ์

5

ประเมินคุณภาพของคำตอบผ่านค่าของคำตอบเชิงสุ่ม (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 มาใช้เองเป็นเรื่องปกติในการวิจัยและอุตสาหกรรม

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. 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.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    ISBN: 9780387982175
    คัดลอกแล้ว