การตั้งโปรแกรมเป้าหมายเชิงสุ่ม — การหาค่าเหมาะสมที่สุดของเป้าหมายหลายประการภายใต้ความไม่แน่นอน
- ผู้เสนอ
- Contini, B. (building on Charnes & Cooper's chance-constrained programming)
- ปี
- 1968
- ประเภท
- Stochastic multi-goal optimization
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การตั้งโปรแกรมเป้าหมายเชิงสุ่ม (SGP) เป็นการขยายการตั้งโปรแกรมเป้าหมายแบบดั้งเดิมเพื่อจัดการกับความไม่แน่นอนในเป้าหมาย, สัมประสิทธิ์ข้อจำกัด, หรือพารามิเตอร์ด้านขวา โดยการรวมข้อจำกัดเชิงความน่าจะเป็นและองค์ประกอบวัตถุประสงค์เชิงสุ่ม SGP จะหาคำตอบที่สอดคล้องกับเป้าหมายหลายประการในระดับความน่าจะเป็นที่ยอมรับได้ ทำให้เหมาะสำหรับปัญหาการตัดสินใจที่ข้อมูลมีความไม่แน่นอนหรือแปรปรวนโดยธรรมชาติ
แนวคิดเบื้องหลังวิธีการ
การตั้งโปรแกรมเป้าหมายแบบดั้งเดิมถามว่า: เราจะเข้าใกล้แต่ละเป้าหมายพร้อมกันได้อย่างไร? การตั้งโปรแกรมเป้าหมายเชิงสุ่มถามคำถามเดียวกัน แต่ยอมรับว่าโลกมีความไม่แน่นอน — เป้าหมายอาจเปลี่ยนแปลง, ทรัพยากรอาจแปรผัน, และข้อมูลอาจมีสัญญาณรบกวน แทนที่จะหาค่าที่เหมาะสมที่สุดสำหรับสถานการณ์ที่แน่นอนเพียงสถานการณ์เดียว SGP จะหาคำตอบที่ทำงานได้ดีโดยเฉลี่ย หรือที่บรรลุแต่ละเป้าหมายด้วยความน่าจะเป็นที่ระบุไว้ ลองคิดว่าเป็นการวางแผนที่ดีที่สุดเท่าที่จะเป็นไปได้ โดยคำนึงถึงสิ่งที่คุณไม่รู้ตามความเป็นจริง
ประวัติศาสตร์
การตั้งโปรแกรมเป้าหมายถูกนำเสนอโดย Charnes และ Cooper ในช่วงปลายทศวรรษ 1950 Contini (1968) ได้ขยายผลอย่างเป็นทางการสู่บริบทเชิงสุ่มโดยใช้แนวคิดการตั้งโปรแกรมแบบมีข้อจำกัดโอกาส ในทศวรรษต่อมามีการประยุกต์ใช้เพิ่มขึ้นในด้านการเงิน, การเกษตร, และนโยบายสาธารณะ วิธีการนี้ได้รับพื้นฐานทางทฤษฎีเพิ่มเติมผ่านการเชื่อมโยงกับการหาค่าเหมาะสมที่สุดแบบทนทานที่พัฒนาขึ้นในช่วงทศวรรษ 1990 และ 2000
ควรใช้เมื่อใด
ใช้การตั้งโปรแกรมเป้าหมายเชิงสุ่มเมื่อปัญหาการตัดสินใจมีเป้าหมายที่ขัดแย้งกันหลายประการ, อย่างน้อยพารามิเตอร์บางส่วน (อุปสงค์, ต้นทุน, ผลผลิต) มีความไม่แน่นอนและสามารถอธิบายได้ด้วยการแจกแจงความน่าจะเป็น, และผู้กำหนดนโยบายต้องการการรับประกันที่แสดงในรูปของระดับความเชื่อมั่นมากกว่าขอบเขตกรณีที่เลวร้ายที่สุด เหมาะสำหรับ การวางแผนห่วงโซ่อุปทาน, การจัดสรรทรัพยากรด้านการดูแลสุขภาพ, การบริหารพอร์ตการลงทุนทางการเงินที่มีวัตถุประสงค์หลายประการ, และการวางแผนการเกษตรภายใต้ความไม่แน่นอนของสภาพอากาศ **ห้าม** ใช้เมื่อเป้าหมายไม่สามารถเปรียบเทียบกันได้อย่างแท้จริงและไม่สามารถให้น้ำหนักได้, เมื่อไม่มีข้อมูลการแจกแจง (ใช้การหาค่าเหมาะสมที่สุดแบบทนทานแทน), เมื่อปัญหามีวัตถุประสงค์เพียงอย่างเดียว (ใช้การตั้งโปรแกรมเชิงสุ่ม), หรือเมื่อจำนวนสถานการณ์มีมากเกินไปจนการแปลงรูปสมการเทียบเท่าเชิงกำหนดไม่สามารถทำได้
ข้อจำกัดและข้อควรพิจารณา
- ต้องการความรู้เกี่ยวกับพารามิเตอร์การแจกแจง (ค่าเฉลี่ย, ความแปรปรวน) ซึ่งอาจประมาณค่าได้อย่างแม่นยำได้ยาก
- การแจกแจงที่ไม่ใช่การแจกแจงปกติ หรือข้อจำกัดแบบโอกาสร่วม อาจทำให้การแปลงรูปเป็นแบบกำหนดทำได้ยาก ต้องใช้วิธีการตามสถานการณ์หรือการจำลองแบบ
- การเลือก ระดับความเชื่อมั่น alpha_i และ น้ำหนักเป้าหมาย w_i เป็นเรื่องอัตวิสัยโดยเนื้อแท้ และอาจส่งผลกระทบต่อผลลัพธ์อย่างมาก
- มีความต้องการในการคำนวณมากกว่าการตั้งโปรแกรมเป้าหมายแบบกำหนด โดยเฉพาะอย่างยิ่งสำหรับปัญหาขนาดใหญ่หรือไม่เชิงเส้น
- การตีความการแลกเปลี่ยนระหว่างเป้าหมายเชิงความน่าจะเป็นอาจเป็นเรื่องยากสำหรับผู้มีส่วนได้ส่วนเสียที่ไม่ใช่ผู้เชี่ยวชาญ
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- จัดการกับเป้าหมายที่ขัดแย้งกันหลายประการพร้อมกันภายในกรอบการหาค่าที่เหมาะสมที่สุดเดียว
- อนุญาตให้ระบุระดับความเสี่ยงที่ยอมรับได้ (ความเชื่อมั่น) สำหรับแต่ละเป้าหมายหรือข้อจำกัดได้อย่างชัดเจน
- ภายใต้ข้อสมมติฐานการแจกแจงปกติ ข้อจำกัดแบบโอกาสจะลดรูปเป็นข้อจำกัดกรวยอันดับสองที่สามารถแก้ไขได้ด้วยตัวแก้ปัญหามาตรฐาน
- ให้ข้อมูลแก่ผู้มีอำนาจตัดสินใจเกี่ยวกับความน่าจะเป็นของการบรรลุเป้าหมาย ซึ่งให้ข้อมูลที่สมบูรณ์กว่าผลลัพธ์จากสถานการณ์เดียว
- ครอบคลุมการตั้งโปรแกรมเป้าหมายแบบกำหนดเป็นกรณีพิเศษ (ระดับความเชื่อมั่น = 1 ด้วยพารามิเตอร์คงที่)
- มีพื้นฐานทางทฤษฎีที่แข็งแกร่ง เชื่อมโยงกับวรรณกรรมเกี่ยวกับการตั้งโปรแกรมแบบมีข้อจำกัดโอกาสและการหาค่าเหมาะสมที่สุดแบบทนทาน
การประยุกต์ใช้
- การวางแผนการเกษตร: การจัดสรรที่ดินและทรัพยากรข้ามพืชผลภายใต้สภาวะฝนตกและราคาที่ไม่แน่นอน
- การจัดสรรทรัพยากรด้านการดูแลสุขภาพ: การจัดตารางบุคลากรและเตียงในขณะที่บรรลุเป้าหมายระดับบริการภายใต้ความต้องการของผู้ป่วยที่ไม่แน่นอน
- การจัดการห่วงโซ่อุปทาน: การวางแผนการผลิตและสินค้าคงคลังด้วยผลผลิต, เวลานำ, และอุปสงค์ที่ไม่แน่นอน
- การหาค่าเหมาะสมที่สุดของพอร์ตการลงทุนทางการเงินด้วยวัตถุประสงค์หลายประการ (ผลตอบแทน, ความเสี่ยง, สภาพคล่อง) ภายใต้ความไม่แน่นอนของตลาด
- การวางแผนระบบพลังงาน: การสร้างสมดุลระหว่างต้นทุน, ความน่าเชื่อถือ, และเป้าหมายการปล่อยมลพิษ ภายใต้การผลิตพลังงานหมุนเวียนที่ไม่แน่นอน
- การจัดทำงบประมาณเทศบาล: การจัดสรรเงินทุนสาธารณะระหว่างหน่วยงานด้วยรายรับและรายจ่ายที่ไม่แน่นอน
วิธีการทำงาน
วิธีการทำงาน
กำหนดตัวแปรการตัดสินใจ, เป้าหมายปรารถนาหลายประการ (เป้าหมาย), และข้อจำกัดที่เข้มงวดใดๆ เป้าหมายแต่ละรายการ i แสดงด้วย: f_i(x) + d_i^- - d_i^+ = g_i, โดยที่ d_i^- และ d_i^+ เป็นตัวแปรส่วนเบี่ยงเบนเชิงลบและเชิงบวกจากเป้าหมาย g_i กำหนดน้ำหนักลำดับความสำคัญที่สะท้อนถึงความสำคัญสัมพัทธ์ของการบรรลุแต่ละเป้าหมาย
ระบุว่าพารามิเตอร์ใดมีความไม่แน่นอน: เป้าหมาย g_i, สัมประสิทธิ์ข้อจำกัด, หรือสัมประสิทธิ์ฟังก์ชันวัตถุประสงค์ อาจถูกจำลองแบบเป็นตัวแปรสุ่มที่มีการแจกแจงที่ทราบหรือประมาณค่าได้ (เช่น การแจกแจงปกติ, การแจกแจงเอกรูป, การแจกแจงเชิงประจักษ์) ระบุข้อสมมติฐานการแจกแจงตามข้อมูลในอดีตหรือการตัดสินของผู้เชี่ยวชาญ
แปลงข้อจำกัดที่ไม่แน่นอนให้เป็นข้อจำกัดแบบโอกาส (เชิงความน่าจะเป็น) สำหรับข้อจำกัดเชิงสุ่มที่เกี่ยวข้องกับพารามิเตอร์สุ่ม b_i ที่มีการแจกแจง F, กำหนดให้ P(g_i(x) <= b_i) >= alpha_i, โดยที่ alpha_i คือระดับความเชื่อมั่นที่ผู้ใช้ระบุ (เช่น 0.90 หรือ 0.95) ภายใต้ข้อสมมติฐานการแจกแจงปกติ สามารถแปลงเป็นข้อจำกัดกรวยอันดับสองแบบกำหนดได้
สูตร
P(g_i(x) \leq b_i) \geq \alpha_i
แก้ปัญหาการหาค่าเหมาะสมที่สุดที่ได้ (ซึ่งอาจถูกแปลงรูปแล้ว): หาค่าต่ำสุดของผลรวมถ่วงน้ำหนักของส่วนเบี่ยงเบน min sum_i (w_i^+ d_i^+ + w_i^- d_i^-) ภายใต้สมการเทียบเท่าเชิงกำหนดของข้อจำกัดแบบโอกาสและข้อจำกัดที่เข้มงวดที่เหลืออยู่ ใช้ตัวแก้ปัญหา LP, MILP, หรือตัวแก้ปัญหาไม่เชิงเส้น ขึ้นอยู่กับโครงสร้างปัญหา
สูตร
\min \sum_{i} (w_i^+ d_i^+ + w_i^- d_i^-)ประเมินผลลัพธ์โดยการตรวจสอบระดับการบรรลุเป้าหมาย, ความน่าจะเป็นของการสอดคล้องกับข้อจำกัด, และความไวต่อข้อสมมติฐานการแจกแจง ดำเนินการตรวจสอบย้อนหลังด้วยการจำลองแบบมอนติคาร์โล โดยการสุ่มตัวอย่างการรับค่าพารามิเตอร์ และตรวจสอบว่าผลลัพธ์บรรลุเป้าหมายตามระดับความเชื่อมั่นที่ระบุในสถานการณ์จำลอง
ข้อผิดพลาดที่พบบ่อย
- การสมมติฐานการแจกแจงปกติของพารามิเตอร์ที่ไม่แน่นอนโดยไม่มีการตรวจสอบเชิงประจักษ์ อาจให้การรับประกันความเชื่อมั่นที่ทำให้เข้าใจผิดได้
- การตั้งระดับความเชื่อมั่นที่สูงเกินไป (เช่น 0.999) จะทำให้แบบจำลองลดรูปเป็นสูตรแบบกำหนดที่อนุรักษ์นิยม ซึ่งขัดต่อวัตถุประสงค์ของการสร้างแบบจำลองเชิงสุ่ม
- การทำให้การตั้งโปรแกรมเป้าหมายแบบมีข้อจำกัดโอกาสสับสนกับการตั้งโปรแกรมเป้าหมายแบบทนทาน — ทั้งสองวิธีจัดการกับความไม่แน่นอนแตกต่างกันและไม่สามารถใช้แทนกันได้
- การไม่ตรวจสอบผลลัพธ์เชิงสุ่มผ่านการจำลองแบบมอนติคาร์โล จะทำให้ไม่ทราบความเสี่ยงที่แท้จริงของการละเมิดเป้าหมาย
- การละเลยความสัมพันธ์ระหว่างพารามิเตอร์ที่ไม่แน่นอน อาจทำให้ได้ผลลัพธ์ที่ไม่สามารถทำได้ หรือมองโลกในแง่ดีเกินไป
คำถามที่พบบ่อย
การตั้งโปรแกรมเป้าหมายเชิงสุ่มแตกต่างจากการตั้งโปรแกรมเป้าหมายแบบดั้งเดิมอย่างไร?
การตั้งโปรแกรมเป้าหมายแบบดั้งเดิมสมมติว่าพารามิเตอร์ทั้งหมด (เป้าหมาย, ข้อจำกัด, ต้นทุน) เป็นที่ทราบอย่างแน่นอน การตั้งโปรแกรมเป้าหมายเชิงสุ่มอนุญาตให้พารามิเตอร์บางส่วนเป็นตัวแปรสุ่ม โดยรวมข้อจำกัดเชิงความน่าจะเป็นที่กำหนดให้เป้าหมายต้องบรรลุด้วยระดับความเชื่อมั่นที่ระบุ แทนที่จะเป็นค่าที่แน่นอน
ข้อสมมติฐานการแจกแจงใดที่ใช้บ่อยที่สุด?
การแจกแจงปกติเป็นข้อสมมติฐานที่พบบ่อยที่สุด เพราะช่วยให้ข้อจำกัดแบบโอกาสสามารถแปลงรูปเป็นข้อจำกัดกรวยอันดับสองแบบกำหนดได้อย่างแม่นยำ เมื่อข้อมูลบ่งชี้ถึงการแจกแจงที่ไม่ใช่การแจกแจงปกติ จะใช้วิธีการตามสถานการณ์หรือการจำลองแบบแทน
ฉันจะเลือกระดับความเชื่อมั่น alpha_i สำหรับแต่ละข้อจำกัดแบบโอกาสได้อย่างไร?
ระดับความเชื่อมั่นสะท้อนถึงความทนทานต่อความเสี่ยงของผู้มีอำนาจตัดสินใจสำหรับแต่ละเป้าหมาย ค่าระหว่าง 0.90–0.95 เป็นที่นิยมใช้กันทั่วไป ค่าที่สูงขึ้นทำให้ปัญหามีความอนุรักษ์นิยมมากขึ้น และอาจต้องผ่อนคลายเป้าหมายอื่น ๆ ค่าที่ต่ำลงยอมรับความเสี่ยงได้มากขึ้น แต่อาจนำไปสู่ผลลัพธ์ที่ไม่เป็นที่ยอมรับ
การตั้งโปรแกรมเป้าหมายเชิงสุ่มสามารถจัดการกับตัวแปรการตัดสินใจที่เป็นจำนวนเต็มได้หรือไม่?
ได้ เมื่อรวมกับตัวแปรจำนวนเต็ม ปัญหาจะกลายเป็นการตั้งโปรแกรมเป้าหมายจำนวนเต็มเชิงสุ่ม ซึ่งแก้ไขได้ยากกว่า แต่ยังคงสามารถแก้ไขได้สำหรับอินสแตนซ์ขนาดปานกลาง โดยใช้เทคนิค branch-and-bound พร้อมกับการแปลงรูปข้อจำกัดแบบโอกาส
ฉันควรใช้การตั้งโปรแกรมเป้าหมายเชิงสุ่ม หรือ การหาค่าเหมาะสมที่สุดแบบทนทาน เมื่อฉันมีพารามิเตอร์ที่ไม่แน่นอน?
หากคุณมีข้อมูลการแจกแจงที่เชื่อถือได้และต้องการการรับประกันเชิงความน่าจะเป็น SGP จะเหมาะสม หากคุณทราบเพียงชุดความไม่แน่นอน (ขอบเขต) และต้องการการรับประกันกรณีที่เลวร้ายที่สุดโดยไม่มีข้อสมมติฐานการแจกแจง การหาค่าเหมาะสมที่สุดแบบทนทานจะดีกว่า เมื่อทั้งสองวิธีสามารถทำได้ การเปรียบเทียบผลลัพธ์จากทั้งสองแนวทางถือเป็นแนวปฏิบัติที่ดี
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Contini, B. (1968). A stochastic approach to goal programming. Operations Research, 16(3), 576–586.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วCharnes, A., Cooper, W. W. (1959). Chance-constrained programming. Management Science, 6(1), 73–79.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว