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

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

ผู้เสนอ
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 ด้วยพารามิเตอร์คงที่)
  • มีพื้นฐานทางทฤษฎีที่แข็งแกร่ง เชื่อมโยงกับวรรณกรรมเกี่ยวกับการตั้งโปรแกรมแบบมีข้อจำกัดโอกาสและการหาค่าเหมาะสมที่สุดแบบทนทาน

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

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

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

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

1

กำหนดตัวแปรการตัดสินใจ, เป้าหมายปรารถนาหลายประการ (เป้าหมาย), และข้อจำกัดที่เข้มงวดใดๆ เป้าหมายแต่ละรายการ i แสดงด้วย: f_i(x) + d_i^- - d_i^+ = g_i, โดยที่ d_i^- และ d_i^+ เป็นตัวแปรส่วนเบี่ยงเบนเชิงลบและเชิงบวกจากเป้าหมาย g_i กำหนดน้ำหนักลำดับความสำคัญที่สะท้อนถึงความสำคัญสัมพัทธ์ของการบรรลุแต่ละเป้าหมาย

2

ระบุว่าพารามิเตอร์ใดมีความไม่แน่นอน: เป้าหมาย g_i, สัมประสิทธิ์ข้อจำกัด, หรือสัมประสิทธิ์ฟังก์ชันวัตถุประสงค์ อาจถูกจำลองแบบเป็นตัวแปรสุ่มที่มีการแจกแจงที่ทราบหรือประมาณค่าได้ (เช่น การแจกแจงปกติ, การแจกแจงเอกรูป, การแจกแจงเชิงประจักษ์) ระบุข้อสมมติฐานการแจกแจงตามข้อมูลในอดีตหรือการตัดสินของผู้เชี่ยวชาญ

3

แปลงข้อจำกัดที่ไม่แน่นอนให้เป็นข้อจำกัดแบบโอกาส (เชิงความน่าจะเป็น) สำหรับข้อจำกัดเชิงสุ่มที่เกี่ยวข้องกับพารามิเตอร์สุ่ม 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
4

แก้ปัญหาการหาค่าเหมาะสมที่สุดที่ได้ (ซึ่งอาจถูกแปลงรูปแล้ว): หาค่าต่ำสุดของผลรวมถ่วงน้ำหนักของส่วนเบี่ยงเบน min sum_i (w_i^+ d_i^+ + w_i^- d_i^-) ภายใต้สมการเทียบเท่าเชิงกำหนดของข้อจำกัดแบบโอกาสและข้อจำกัดที่เข้มงวดที่เหลืออยู่ ใช้ตัวแก้ปัญหา LP, MILP, หรือตัวแก้ปัญหาไม่เชิงเส้น ขึ้นอยู่กับโครงสร้างปัญหา

สูตร
\min \sum_{i} (w_i^+ d_i^+ + w_i^- d_i^-)
5

ประเมินผลลัพธ์โดยการตรวจสอบระดับการบรรลุเป้าหมาย, ความน่าจะเป็นของการสอดคล้องกับข้อจำกัด, และความไวต่อข้อสมมติฐานการแจกแจง ดำเนินการตรวจสอบย้อนหลังด้วยการจำลองแบบมอนติคาร์โล โดยการสุ่มตัวอย่างการรับค่าพารามิเตอร์ และตรวจสอบว่าผลลัพธ์บรรลุเป้าหมายตามระดับความเชื่อมั่นที่ระบุในสถานการณ์จำลอง

ข้อผิดพลาดที่พบบ่อย

  • การสมมติฐานการแจกแจงปกติของพารามิเตอร์ที่ไม่แน่นอนโดยไม่มีการตรวจสอบเชิงประจักษ์ อาจให้การรับประกันความเชื่อมั่นที่ทำให้เข้าใจผิดได้
  • การตั้งระดับความเชื่อมั่นที่สูงเกินไป (เช่น 0.999) จะทำให้แบบจำลองลดรูปเป็นสูตรแบบกำหนดที่อนุรักษ์นิยม ซึ่งขัดต่อวัตถุประสงค์ของการสร้างแบบจำลองเชิงสุ่ม
  • การทำให้การตั้งโปรแกรมเป้าหมายแบบมีข้อจำกัดโอกาสสับสนกับการตั้งโปรแกรมเป้าหมายแบบทนทาน — ทั้งสองวิธีจัดการกับความไม่แน่นอนแตกต่างกันและไม่สามารถใช้แทนกันได้
  • การไม่ตรวจสอบผลลัพธ์เชิงสุ่มผ่านการจำลองแบบมอนติคาร์โล จะทำให้ไม่ทราบความเสี่ยงที่แท้จริงของการละเมิดเป้าหมาย
  • การละเลยความสัมพันธ์ระหว่างพารามิเตอร์ที่ไม่แน่นอน อาจทำให้ได้ผลลัพธ์ที่ไม่สามารถทำได้ หรือมองโลกในแง่ดีเกินไป

คำถามที่พบบ่อย

การตั้งโปรแกรมเป้าหมายเชิงสุ่มแตกต่างจากการตั้งโปรแกรมเป้าหมายแบบดั้งเดิมอย่างไร?

การตั้งโปรแกรมเป้าหมายแบบดั้งเดิมสมมติว่าพารามิเตอร์ทั้งหมด (เป้าหมาย, ข้อจำกัด, ต้นทุน) เป็นที่ทราบอย่างแน่นอน การตั้งโปรแกรมเป้าหมายเชิงสุ่มอนุญาตให้พารามิเตอร์บางส่วนเป็นตัวแปรสุ่ม โดยรวมข้อจำกัดเชิงความน่าจะเป็นที่กำหนดให้เป้าหมายต้องบรรลุด้วยระดับความเชื่อมั่นที่ระบุ แทนที่จะเป็นค่าที่แน่นอน

ข้อสมมติฐานการแจกแจงใดที่ใช้บ่อยที่สุด?

การแจกแจงปกติเป็นข้อสมมติฐานที่พบบ่อยที่สุด เพราะช่วยให้ข้อจำกัดแบบโอกาสสามารถแปลงรูปเป็นข้อจำกัดกรวยอันดับสองแบบกำหนดได้อย่างแม่นยำ เมื่อข้อมูลบ่งชี้ถึงการแจกแจงที่ไม่ใช่การแจกแจงปกติ จะใช้วิธีการตามสถานการณ์หรือการจำลองแบบแทน

ฉันจะเลือกระดับความเชื่อมั่น alpha_i สำหรับแต่ละข้อจำกัดแบบโอกาสได้อย่างไร?

ระดับความเชื่อมั่นสะท้อนถึงความทนทานต่อความเสี่ยงของผู้มีอำนาจตัดสินใจสำหรับแต่ละเป้าหมาย ค่าระหว่าง 0.90–0.95 เป็นที่นิยมใช้กันทั่วไป ค่าที่สูงขึ้นทำให้ปัญหามีความอนุรักษ์นิยมมากขึ้น และอาจต้องผ่อนคลายเป้าหมายอื่น ๆ ค่าที่ต่ำลงยอมรับความเสี่ยงได้มากขึ้น แต่อาจนำไปสู่ผลลัพธ์ที่ไม่เป็นที่ยอมรับ

การตั้งโปรแกรมเป้าหมายเชิงสุ่มสามารถจัดการกับตัวแปรการตัดสินใจที่เป็นจำนวนเต็มได้หรือไม่?

ได้ เมื่อรวมกับตัวแปรจำนวนเต็ม ปัญหาจะกลายเป็นการตั้งโปรแกรมเป้าหมายจำนวนเต็มเชิงสุ่ม ซึ่งแก้ไขได้ยากกว่า แต่ยังคงสามารถแก้ไขได้สำหรับอินสแตนซ์ขนาดปานกลาง โดยใช้เทคนิค branch-and-bound พร้อมกับการแปลงรูปข้อจำกัดแบบโอกาส

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

หากคุณมีข้อมูลการแจกแจงที่เชื่อถือได้และต้องการการรับประกันเชิงความน่าจะเป็น SGP จะเหมาะสม หากคุณทราบเพียงชุดความไม่แน่นอน (ขอบเขต) และต้องการการรับประกันกรณีที่เลวร้ายที่สุดโดยไม่มีข้อสมมติฐานการแจกแจง การหาค่าเหมาะสมที่สุดแบบทนทานจะดีกว่า เมื่อทั้งสองวิธีสามารถทำได้ การเปรียบเทียบผลลัพธ์จากทั้งสองแนวทางถือเป็นแนวปฏิบัติที่ดี

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

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

  1. Contini, B. (1968). A stochastic approach to goal programming. Operations Research, 16(3), 576–586.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Charnes, A., Cooper, W. W. (1959). Chance-constrained programming. Management Science, 6(1), 73–79.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว