Stochastic programming — การโปรแกรมสุ่ม

การโปรแกรมสุ่ม (อังกฤษ: stochastic programming) — สาขาหนึ่งของการโปรแกรมเชิงคณิตศาสตร์ที่พัฒนาแบบจำลองและวิธีการสำหรับแก้ปัญหาการหาค่าเหมาะที่สุดภายใต้สภาวะความไม่แน่นอน เมื่อพารามิเตอร์บางส่วนของแบบจำลองไม่ทราบค่าที่แน่นอน แต่ถูกแทนด้วยตัวแปรสุ่มที่มีการกระจายความน่าจะเป็นที่ทราบหรือประมาณไว้

ต่างจากปัญหาเชิงกำหนดที่ข้อมูลทั้งหมดถือว่าเป็นค่าคงที่ที่กำหนดไว้ การโปรแกรมสุ่มมีเป้าหมายในการหาคำตอบ (หรือนโยบายการตัดสินใจ) ที่เหมาะสมที่สุดในเชิงสถิติบางอย่าง โดยส่วนใหญ่หมายถึงการหาค่าต่ำสุดหรือสูงสุดของค่าคาดหมายทางคณิตศาสตร์ของฟังก์ชันวัตถุประสงค์ แนวคิดหลักคือการหานโยบายการตัดสินใจที่ดีที่สุด «โดยเฉลี่ย» สำหรับการเกิดขึ้นที่เป็นไปได้ทั้งหมดของพารามิเตอร์สุ่ม ซึ่งมีความสำคัญอย่างยิ่งสำหรับปัญหาที่มีการตัดสินใจซ้ำ ๆ ในสภาวะที่คล้ายคลึงกัน (เช่น ในการจัดการสินค้าคงคลังหรือระบบพลังงาน)

การกำหนดปัญหาทางคณิตศาสตร์

ในรูปแบบทั่วไป ปัญหาการโปรแกรมสุ่มสามารถกำหนดได้ดังนี้: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ โดยที่:

• $x$ — เวกเตอร์ของตัวแปรควบคุม (การตัดสินใจ) ที่ต้องกำหนด
• $X$ — เซตของคำตอบที่ยอมรับได้สำหรับ $x$ ซึ่งกำหนดโดยข้อจำกัดเชิงกำหนด
• $\xi$ — เวกเตอร์สุ่มที่แทนพารามิเตอร์ที่ไม่แน่นอนของปัญหา (เช่น ความต้องการ ราคา สภาพอากาศ)
• $f(x,\xi )$ — ฟังก์ชันวัตถุประสงค์ที่มีค่าขึ้นอยู่กับทั้งการตัดสินใจ $x$ และการเกิดขึ้นของเวกเตอร์สุ่ม $\xi$
• $𝔼[\cdot ]$ — ตัวดำเนินการค่าคาดหมายทางคณิตศาสตร์ที่คำนวณตามการกระจายความน่าจะเป็นของเวกเตอร์ $\xi$

หลักการสำคัญที่สุดที่เป็นรากฐานของแบบจำลองสุ่มหลายขั้นตอนคือ หลักการไม่คาดการณ์ล่วงหน้า (อังกฤษ: non-anticipativity principle) หลักการนี้ระบุว่าการตัดสินใจที่ทำในขั้นตอนใด ๆ สามารถขึ้นอยู่กับเฉพาะข้อมูลที่มีอยู่ ณ เวลานั้น และไม่สามารถ «มองอนาคต» ได้

ปัญหาสองขั้นตอนพร้อมสิทธิ์ชดเชย

แบบจำลองที่พบบ่อยที่สุดคือ ปัญหาสองขั้นตอนพร้อมสิทธิ์ชดเชย (อังกฤษ: two-stage stochastic program with recourse) กระบวนการตัดสินใจแบ่งออกเป็นสองขั้นตอน:

1. ขั้นตอนที่หนึ่ง: ตัดสินใจ «ที่นี่และตอนนี้» (here-and-now) — กำหนดเวกเตอร์ $x$ การตัดสินใจนี้ต้องทำก่อนที่จะทราบการเกิดขึ้นที่เจาะจงของเวกเตอร์สุ่ม $\xi$
2. ขั้นตอนที่สอง: หลังจากเหตุการณ์สุ่มเกิดขึ้นแล้ว จะมีการตัดสินใจปรับแก้หรือชดเชย (recourse decision) — เวกเตอร์ $y(\xi )$ ที่มุ่งลดผลกระทบด้านลบหรือใช้ประโยชน์จากโอกาสที่เกิดขึ้นจากการผสมผสานระหว่างการตัดสินใจขั้นตอนแรก $x$ และผลลัพธ์ $\xi$

ในเชิงคณิตศาสตร์ ปัญหาการโปรแกรมเชิงเส้นสุ่มสองขั้นตอนกำหนดดังนี้: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ ภายใต้ข้อจำกัดขั้นตอนแรก: $Ax=b,x\ge 0$ ที่นี่ $Q(x,\xi )$ คือ ฟังก์ชันชดเชย (recourse function) ซึ่งแทนค่าเหมาะที่สุดของปัญหาขั้นตอนที่สอง: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ โดยที่ $\xi$ คือเวกเตอร์สุ่มที่ประกอบด้วยพารามิเตอร์ $q(\xi ),T(\xi )$ และ $h(\xi )$ ส่วน $c,A,b$ และ $W$ คือพารามิเตอร์เชิงกำหนด

คุณสมบัติและทฤษฎีบทสำคัญ

• ความนูน: ผลลัพธ์พื้นฐานที่สำคัญของทฤษฎีคือสำหรับปัญหาการโปรแกรมเชิงเส้นสุ่มสองขั้นตอน ฟังก์ชันชดเชยที่คาดหวัง $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ เป็นฟังก์ชันนูน คุณสมบัตินี้มีความสำคัญอย่างยิ่ง เนื่องจากรับประกันว่าปัญหาขั้นตอนแรกโดยรวมเป็นปัญหาการโปรแกรมเชิงนูน ซึ่งมีวิธีการแก้ที่มีประสิทธิภาพและค่าเหมาะที่สุดส่วนกลางตรงกับค่าเหมาะที่สุดส่วนท้องถิ่น
• สมมูลเชิงกำหนด: หากเวกเตอร์สุ่ม $\xi$ มีการเกิดขึ้นที่เป็นไปได้ (สถานการณ์) จำนวนจำกัด ${\xi }_1,\dots ,{\xi }_K$ พร้อมความน่าจะเป็น $p_1,\dots ,p_K$ ปัญหาการโปรแกรมสุ่มสามารถกำหนดใหม่เป็นปัญหาการหาค่าเหมาะที่สุดเชิงกำหนดขนาดใหญ่เพียงปัญหาเดียว ในกรณีนี้ ค่าคาดหมายทางคณิตศาสตร์จะถูกแทนที่ด้วยผลรวมถ่วงน้ำหนักสำหรับทุกสถานการณ์ อย่างไรก็ตาม ขนาดของปัญหานี้เพิ่มขึ้นเชิงเส้นตามจำนวนสถานการณ์ ซึ่งทำให้เกิด «คำสาปแห่งมิติ» และทำให้แนวทางดังกล่าวไม่สามารถคำนวณได้จริงเมื่อมีสถานการณ์จำนวนมาก

การเปรียบเทียบกับการหาค่าเหมาะที่สุดแบบโรบัสต์

การโปรแกรมสุ่มเป็นหนึ่งในหลายแนวทางสำหรับการหาค่าเหมาะที่สุดภายใต้สภาวะความไม่แน่นอน ความแตกต่างสำคัญจากการหาค่าเหมาะที่สุดแบบโรบัสต์อยู่ที่วิธีการสร้างแบบจำลองความไม่แน่นอนและเกณฑ์ความเหมาะที่สุด

การเปรียบเทียบแนวทางการหาค่าเหมาะที่สุดภายใต้สภาวะความไม่แน่นอน

เกณฑ์	การหาค่าเหมาะที่สุดเชิงสุ่ม	การหาค่าเหมาะที่สุดแบบโรบัสต์
การแทนความไม่แน่นอน	พารามิเตอร์เป็นตัวแปรสุ่มที่มีการกระจายความน่าจะเป็นที่ทราบ	พารามิเตอร์อยู่ในเซตความไม่แน่นอนที่กำหนด โดยไม่ต้องการการกระจาย
เกณฑ์ความเหมาะที่สุด	การหาค่าเหมาะที่สุดของค่าคาดหมายทางคณิตศาสตร์ของฟังก์ชันวัตถุประสงค์	การหาค่าเหมาะที่สุดในสถานการณ์เลวร้ายที่สุด (minimax)
ลักษณะของคำตอบ	นโยบายที่เหมาะที่สุด «โดยเฉลี่ย» อาจไม่ยอมรับได้สำหรับสถานการณ์ที่หายาก	คำตอบที่รับประกันว่ายอมรับได้สำหรับการเกิดขึ้นทั้งหมด อาจมีความอนุรักษนิยม

ตัวอย่าง

• ปัญหาผู้ขายหนังสือพิมพ์ (อังกฤษ: newsvendor problem): ปัญหาคลาสสิกของการจัดการสินค้าคงคลัง ที่ผู้ขายต้องตัดสินใจว่าจะสั่งซื้อสินค้าจำนวนเท่าใดโดยไม่ทราบความต้องการในอนาคตที่แน่นอน คำตอบจะสร้างสมดุลระหว่างความเสี่ยงของการขาดทุนจากสินค้าส่วนเกินและความเสี่ยงของกำไรที่สูญเสียจากการขาดแคลน
• ปัญหาเกษตรกร: เกษตรกรตัดสินใจว่าจะจัดสรรพื้นที่กี่เอเคอร์ให้กับพืชผลต่าง ๆ บนพื้นที่รวม โดยไม่ทราบสภาพอากาศในอนาคตที่ส่งผลต่อผลผลิต หลังจากทราบสภาพอากาศแล้ว เกษตรกรสามารถดำเนินการปรับแก้ได้ (เช่น ขายสินค้าส่วนเกินหรือซื้อผลผลิตที่ขาดแคลนเพิ่มเติมในตลาด)

ดูเพิ่มเติม

• การโปรแกรมเชิงคณิตศาสตร์
• การวิจัยการดำเนินงาน
• การหาค่าเหมาะที่สุดแบบโรบัสต์
• การโปรแกรมเชิงพลวัต
• ทฤษฎีการควบคุม

หมายเหตุ

</references>