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

การโปรแกรมเชิงเส้นแบบกำหนดได้ (Deterministic Linear Programming) — LP แบบคลาสสิกที่มีพารามิเตอร์ที่แน่นอน

ผู้เสนอ
George B. Dantzig
ปี
1947
ประเภท
Deterministic mathematical optimization
กลุ่มวิธี
Simulation / optimization

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การโปรแกรมเชิงเส้นแบบกำหนดได้ (Deterministic Linear Programming, DLP) คือรูปแบบคลาสสิกของการโปรแกรมเชิงเส้น ซึ่งสัมประสิทธิ์ฟังก์ชันวัตถุ สัมประสิทธิ์ข้อจำกัด และค่าทางด้านขวาของสมการ ทั้งหมดเป็นที่ทราบแน่นอน DLP หาการจัดสรรทรัพยากรที่เหมาะสมที่สุดเพื่อเพิ่มหรือลดฟังก์ชันวัตถุเชิงเส้นภายใต้ข้อจำกัดเชิงเส้น โดยให้ผลลัพธ์ที่แม่นยำและทำซ้ำได้ภายใต้ข้อมูลที่คงที่และแน่นอน

แนวคิดเบื้องหลังวิธีการ

ลองนึกภาพการจัดสรรงบประมาณคงที่ให้กับโครงการต่างๆ ซึ่งแต่ละโครงการมีต้นทุนและผลตอบแทนที่ทราบแน่นอน ภายใต้ข้อจำกัดด้านทรัพยากรที่คุณทราบอย่างแม่นยำ DLP จะเข้ารหัสสิ่งนี้เป็นระบบอสมการเชิงเส้น และหาผลเฉลยที่จุดมุม (corner-point solution) ที่ดึงคุณค่าสูงสุดจากข้อจำกัดเหล่านั้น เนื่องจากพารามิเตอร์ทุกตัวมีความแน่นอน — ไม่มีการแจกแจงความน่าจะเป็น ไม่มีความคลุมเครือ — ตัวแก้ปัญหา (solver) จะให้แผนที่เหมาะสมที่สุดเพียงแผนเดียว แทนที่จะเป็นชุดผลลัพธ์ที่หลากหลาย ความชัดเจนนี้ทำให้ DLP เป็นแบบจำลองทางเลือกแรกตามธรรมชาติเมื่อข้อมูลได้รับการวัดผลอย่างดีและไม่มีความไม่แน่นอนเป็นข้อกังวลหลัก

ประวัติศาสตร์

การโปรแกรมเชิงเส้นได้รับการกำหนดรูปแบบอย่างเป็นทางการโดย George B. Dantzig ในปี 1947 ด้วยการพัฒนาอัลกอริทึม Simplex ขณะทำงานให้กับกองทัพอากาศสหรัฐฯ เอกสารอ้างอิงของ Dantzig ในปี 1963 กลายเป็นเอกสารอ้างอิงหลัก คำคุณศัพท์ 'deterministic' เกิดขึ้นเมื่อมีการนำรูปแบบ LP แบบสุ่ม (stochastic LP) มาใช้ (Dantzig and Beale, ทศวรรษ 1950–1960) เพื่อแยกความแตกต่างระหว่างแบบจำลองพารามิเตอร์ที่แน่นอนดั้งเดิมกับส่วนขยายเชิงความน่าจะเป็น

ควรใช้เมื่อใด

ใช้ DLP เมื่อปัญหาการตัดสินใจสามารถจำลองได้ด้วยฟังก์ชันวัตถุเชิงเส้นและข้อจำกัดเชิงเส้น และเมื่อพารามิเตอร์ทั้งหมดเป็นที่ทราบแน่นอนเพียงพอที่จะถือว่าเป็นค่าคงที่ เหมาะสำหรับสถานการณ์ เช่น การวางแผนการผลิต การขนส่งและโลจิสติกส์ ปัญหาการกำหนดอาหารและส่วนผสม และปัญหาการไหลในเครือข่ายภายใต้สภาวะที่คงที่ **ห้าม** ใช้ DLP เมื่อพารามิเตอร์มีความไม่แน่นอนอย่างแท้จริงและมีความเสี่ยง — ควรเลือกใช้ Stochastic LP หรือ Robust LP แทน หลีกเลี่ยง DLP เมื่อฟังก์ชันวัตถุหรือข้อจำกัดไม่เป็นเชิงเส้น เมื่อตัวแปรต้องเป็นจำนวนเต็ม (ใช้ MIP) หรือเมื่อต้องสร้างสมดุลระหว่างวัตถุประสงค์ที่ขัดแย้งกันหลายประการโดยไม่รวมเข้าเป็นผลรวมถ่วงน้ำหนักเดียว (ใช้ multi-objective LP หรือ goal programming)

ข้อจำกัดและข้อควรพิจารณา

  • ต้องการให้ความสัมพันธ์ทั้งหมดเป็นเชิงเส้นอย่างเคร่งครัด — ไม่สามารถจับเส้นโค้งต้นทุนที่ไม่เป็นเชิงเส้นหรือผลตอบแทนที่ลดลงได้หากไม่มีการประมาณค่า
  • พารามิเตอร์ทั้งหมดต้องเป็นที่ทราบและคงที่ แบบจำลองไม่มีกลไกพื้นฐานในการจัดการกับความไม่แน่นอนหรือข้อผิดพลาดในการประมาณค่าพารามิเตอร์
  • ผลเฉลยที่เหมาะสมที่สุดอาจไม่ซ้ำกัน (degenerate) ทำให้การเลือกฐานที่รายงานมีความคลุมเครือหากไม่มีเกณฑ์เพิ่มเติม
  • ข้อกำหนดที่เป็นจำนวนเต็มหรือเชิงการจัด (เช่น การตัดสินใจ ใช่/ไม่ใช่) ต้องขยายไปยังการโปรแกรมเชิงจำนวนเต็มแบบผสม (mixed-integer programming) ซึ่งมีความซับซ้อนในการคำนวณมากกว่า
  • ปัญหาขนาดใหญ่ที่มีเมทริกซ์ข้อจำกัดที่หนาแน่นอาจใช้หน่วยความจำมาก แม้แต่สำหรับตัวแก้ปัญหาที่ทันสมัย

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • รับประกันผลเฉลยที่เหมาะสมที่สุดทั่วโลกสำหรับกรณี LP ที่เป็นไปได้และมีขอบเขตใดๆ เนื่องจากความเป็นเว้า
  • ปรับขนาดได้สูง — ตัวแก้ปัญหาที่ทันสมัยสามารถจัดการตัวแปรและข้อจำกัดนับล้านได้ในไม่กี่วินาที
  • ตัวแปรคู่และการวิเคราะห์ความไวให้การตีความทางเศรษฐศาสตร์ที่สมบูรณ์ของราคาเงาและการหาช่วง (ranging)
  • รูปแบบที่โปร่งใส ตรวจสอบได้: ทุกสมมติฐานระบุไว้อย่างชัดเจนในเมทริกซ์ข้อจำกัด
  • ระบบซอฟต์แวร์ที่พัฒนาแล้ว (CPLEX, Gurobi, HiGHS, GLPK) พร้อมการใช้งานที่เชื่อถือได้และผ่านการทดสอบมาอย่างดี
  • สัญญาณความสามารถในการเป็นไปได้ที่ชัดเจน (ผ่าน/ไม่ผ่าน): ความเป็นไปไม่ได้จะเปิดเผยการระบุแบบจำลองที่ผิดพลาดทันที

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

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

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

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

1

กำหนดตัวแปรตัดสินใจ x (เช่น ปริมาณการผลิต จำนวนการไหล), ฟังก์ชันวัตถุ c^T x เพื่อหาค่าต่ำสุดหรือสูงสุด, และชุดข้อจำกัด Ax <= b โดยที่ x >= 0 สัมประสิทธิ์ทั้งหมดใน c, A, และ b จะถูกพิจารณาว่าเป็นค่าคงที่ที่ทราบแน่นอน — นี่คือสิ่งที่ทำให้แบบจำลองเป็นแบบกำหนดได้ เขียน LP ในรูปแบบมาตรฐาน: min c^T x ภายใต้ข้อจำกัด Ax = b, x >= 0

สูตร
\min_{x} \; c^\top x \quad \text{s.t.} \quad Ax \leq b, \; x \geq 0
2

ก่อนทำการหาค่าที่เหมาะสมที่สุด ให้ตรวจสอบว่าบริเวณที่เป็นไปได้ (feasible region) ไม่ว่างเปล่า (ชุดข้อจำกัดมีอย่างน้อยหนึ่งผลเฉลย) และฟังก์ชันวัตถุมีขอบเขต หากบริเวณที่เป็นไปได้ว่างเปล่า ปัญหานั้นจะเป็นไปไม่ได้ (infeasible) หากฟังก์ชันวัตถุไม่มีขอบเขต แบบจำลองนั้นระบุผิดพลาด (mis-specified) การตรวจสอบเหล่านี้จะดำเนินการโดยอัตโนมัติโดยตัวแก้ปัญหา แต่ผู้ทำการวิเคราะห์ควรตีความเพื่อจับข้อผิดพลาดในการกำหนดรูปแบบ (formulation errors)

3

แก้ปัญหา LP โดยใช้วิธีซิมเพล็กซ์ (Simplex algorithm) (การหมุนเวียนตามขอบของรูปทรงหลายเหลี่ยมเว้า (convex polytope) ไปยังจุดยอดที่เหมาะสมที่สุด) หรือวิธีจุดภายใน (interior-point method) (การติดตามเส้นทางผ่านภายในของบริเวณที่เป็นไปได้) ทั้งสองแนวทางใช้ประโยชน์จากความเป็นเว้าของเซตที่เป็นไปได้และความเป็นเชิงเส้นของฟังก์ชันวัตถุ รับประกันว่าค่าที่เหมาะสมที่สุดเฉพาะที่ (local optimum) จะเป็นค่าที่เหมาะสมที่สุดทั่วโลก (global optimum) ตัวแก้ปัญหาที่ทันสมัย (CPLEX, Gurobi, HiGHS) สามารถจัดการตัวแปรและข้อจำกัดนับล้านได้อย่างมีประสิทธิภาพ

4

ตัวแก้ปัญหาจะส่งคืนเวกเตอร์การตัดสินใจที่เหมาะสมที่สุด x* และค่าฟังก์ชันวัตถุที่เหมาะสมที่สุด c^T x* เนื่องจากบริเวณที่เป็นไปได้เป็นรูปทรงหลายเหลี่ยมเว้าและฟังก์ชันวัตถุเป็นเชิงเส้น ค่าที่เหมาะสมที่สุดจึงมักจะเกิดขึ้นที่จุดยอด (basic feasible solution) บันทึก x* และตรวจสอบว่าสอดคล้องกับข้อจำกัดทั้งหมด จากนั้นจึงแปลกลับเป็นคำศัพท์ทางการจัดการ (เช่น หน่วยที่จะผลิต เส้นทางที่จะใช้)

สูตร
x^* = \arg\min \{ c^\top x : Ax \leq b,\; x \geq 0 \}
5

หลังจากได้ x* แล้ว ให้ทำการวิเคราะห์ความไว (sensitivity analysis) หรือการวิเคราะห์หลังการหาค่าที่เหมาะสมที่สุด (post-optimality analysis) เพื่อระบุว่าสัมประสิทธิ์แต่ละตัวใน c หรือ b สามารถเปลี่ยนแปลงได้มากน้อยเพียงใดก่อนที่ฐานปัจจุบัน — และดังนั้นผลเฉลยที่เหมาะสมที่สุด — จะเปลี่ยนแปลงไป ราคาเงา (shadow prices) หรือตัวแปรคู่ (dual variables) จะวัดค่าของส่วนเพิ่ม (marginal value) ของการผ่อนปรนข้อจำกัดแต่ละข้อ แม้ว่าแบบจำลองจะเป็นแบบกำหนดได้ การวิเคราะห์ความไวจะเผยให้เห็นความทนทานของผลเฉลยต่อข้อผิดพลาดในการประมาณค่าพารามิเตอร์ โดยไม่ต้องละทิ้งกรอบการทำงานแบบกำหนดได้

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

  • การพิจารณาพารามิเตอร์ที่ไม่แน่นอนเป็นค่าประมาณจุดคงที่โดยไม่มีการวิเคราะห์ความไวตามมา อาจให้ผลเฉลยที่ดูเหมือนเหมาะสมที่สุดในทางทฤษฎี แต่เปราะบางในทางปฏิบัติ
  • การลืมใส่ข้อจำกัดการไม่เป็นลบ (non-negativity constraints) หรือขอบเขตเชิงตรรกะ อาจให้ผลเฉลยที่เหมาะสมที่สุดทางคณิตศาสตร์ แต่ไม่สามารถนำไปปฏิบัติได้จริง (เช่น ปริมาณการผลิตติดลบ)
  • การตีความราคาเงาผิดพลาดว่าเป็นค่าส่วนเพิ่มที่รับประกันได้นอกช่วงความถูกต้องที่ระบุในการวิเคราะห์การหาช่วง
  • การใช้ DLP เมื่อปัญหาที่แท้จริงมีโครงสร้างจำนวนเต็ม (เช่น จำนวนรถบรรทุก) และการปัดเศษผลเฉลย LP — สิ่งนี้อาจละเมิดข้อจำกัดหรือพลาดค่าที่เหมาะสมที่สุดที่แท้จริง
  • การรวมวัตถุประสงค์มากเกินไปเป็นผลรวมถ่วงน้ำหนักเดียวโดยไม่ตรวจสอบว่าน้ำหนักสะท้อนความชอบของผู้มีส่วนได้ส่วนเสียอย่างถูกต้องหรือไม่ ทำให้มองข้ามการแลกเปลี่ยนที่สำคัญ

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

อะไรทำให้ LP เป็น 'deterministic' ตรงกันข้ามกับ 'stochastic'?

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

อัลกอริทึม Simplex มีประสิทธิภาพเสมอหรือไม่?

ในทางปฏิบัติ ใช่ — วิธี Simplex แก้ปัญหา LP ในโลกแห่งความเป็นจริงเกือบทั้งหมดได้อย่างรวดเร็วอย่างยิ่ง ในทางทฤษฎี อาจใช้เวลาเป็นเลขชี้กำลังในกรณีที่เลวร้ายที่สุด (ตัวอย่าง Klee–Minty) แต่วิธีจุดภายใน (เช่น อัลกอริทึม Karmarkar) ทำงานในเวลาพหุนามและสามารถแข่งขันได้สำหรับอินสแตนซ์ที่มีขนาดใหญ่มาก

ฉันสามารถใช้ DLP ได้หรือไม่หากตัวแปรตัดสินใจบางตัวของฉันต้องเป็นจำนวนเต็ม?

ไม่ได้ หากตัวแปรต้องเป็นจำนวนเต็ม (เช่น จำนวนเครื่องจักรที่จะซื้อ) แบบจำลองจะกลายเป็นการโปรแกรมเชิงจำนวนเต็มแบบผสม (mixed-integer programming) หรือการโปรแกรมเชิงจำนวนเต็มล้วน (pure integer programming) การแก้ปัญหาการผ่อนคลาย LP (LP relaxation) และการปัดเศษอาจละเมิดข้อจำกัดหรือพลาดค่าที่เหมาะสมที่สุดที่เป็นจำนวนเต็มที่แท้จริง ควรใช้ตัวแก้ปัญหา MIP โดยเฉพาะแทน

ราคาเงาช่วยได้อย่างไรหลังจากแก้ปัญหา?

ราคาเงา (ตัวแปรคู่) ของข้อจำกัดจะบอกคุณว่าค่าฟังก์ชันวัตถุจะปรับปรุงได้เท่าใดหากข้อจำกัดด้านขวาของข้อจำกัดนั้นถูกผ่อนปรนไปหนึ่งหน่วย ภายในช่วงความถูกต้องของการหาช่วง (ranging interval) สิ่งนี้จะช่วยในการตัดสินใจว่าจะลงทุนที่ใดเพื่อขยายกำลังการผลิตอย่างคุ้มค่าที่สุด

เมื่อใดที่ฉันควรเปลี่ยนจาก DLP เป็น Robust LP หรือ Stochastic LP?

ควรเปลี่ยนเมื่อความไม่แน่นอนของพารามิเตอร์มีความสำคัญ และต้นทุนของผลเฉลยที่ไม่สามารถเป็นไปได้หรือไม่ดีภายใต้ค่าพารามิเตอร์ที่เกิดขึ้นจริงนั้นมีนัยสำคัญ หากการเบี่ยงเบน 10–20% ในสัมประสิทธิ์ที่สำคัญจะเปลี่ยนผลเฉลยที่ต้องการหรือทำให้เกิดการละเมิดข้อจำกัด สมมติฐานความแน่นอนของ DLP จะแข็งแกร่งเกินไป

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

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

  1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press, Princeton, NJ.

    ISBN: 9780691059136
    คัดลอกแล้ว
  2. Linear programming. Wikipedia.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว