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

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

ผู้เสนอ
George B. Dantzig
ปี
1947
ประเภท
Mathematical programming / continuous optimization

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

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

ใช้ทำอะไร?

การโปรแกรมเชิงเส้น (Linear programming - LP) ซึ่งริเริ่มโดย George B. Dantzig ในปี 1947 เป็นวิธีการทางคณิตศาสตร์สำหรับการหาค่าที่ดีที่สุดของฟังก์ชันวัตถุประสงค์เชิงเส้น — เช่น ต้นทุนต่ำสุดหรือกำไรสูงสุด — ภายใต้ชุดของข้อจำกัดอสมการและสมการเชิงเส้น เป็นเทคนิคพื้นฐานในวิจัยดำเนินงาน และเป็นรากฐานของการวางแผนการผลิต การจัดสรรทรัพยากร โลจิสติกส์ ปัญหาการกำหนดอาหาร และสถานการณ์การตัดสินใจอื่นๆ อีกนับไม่ถ้วนในสาขาวิศวกรรม เศรษฐศาสตร์ และวิทยาศาสตร์ธรรมชาติ

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

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

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

การพัฒนาการโปรแกรมเชิงเส้นอย่างเป็นระบบเริ่มต้นขึ้นในปี 1947 เมื่อ George B. Dantzig ซึ่งทำงานให้กับกองทัพอากาศสหรัฐฯ ได้คิดค้นอัลกอริทึมซิมเพล็กซ์เพื่อทำให้การวางแผนโลจิสติกส์ทางทหารเป็นไปโดยอัตโนมัติ Dantzig ได้ตีพิมพ์ทฤษฎีพื้นฐานในตำราของเขาในปี 1963 ซึ่งยังคงเป็นเอกสารอ้างอิงหลัก งานที่เป็นอิสระและขนานกันโดย Leonid Kantorovich ในสหภาพโซเวียต (1939) ได้กล่าวถึงการวางแผนการผลิตโดยใช้แนวคิดทางคณิตศาสตร์ที่คล้ายคลึงกัน และ Kantorovich ได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์ในปี 1975 ส่วนหนึ่งจากผลงานนี้ คำถามเชิงทฤษฎีเกี่ยวกับความเป็นไปได้ในการแก้ปัญหาในเวลาพหุนาม (polynomial-time solvability) ได้รับการตัดสินโดยวิธีวงรีของ Khachian (1979) และต่อมาโดยวิธีจุดภายในของ Karmarkar (1984) ซึ่งพิสูจน์แล้วว่ารวดเร็วในทางปฏิบัติสำหรับปัญหาขนาดใหญ่ ปัจจุบัน ตัวประมวลผล LP เชิงพาณิชย์และโอเพนซอร์สถูกรวมเข้ากับการวางแผนทรัพยากรองค์กร การจัดตารางการบิน และระบบพลังงานทั่วโลก

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

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

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

  • ข้อกำหนดเชิงเส้น: หากฟังก์ชันวัตถุประสงค์หรือข้อจำกัดใดๆ ไม่เป็นเชิงเส้น แบบจำลอง LP จะระบุผิดพลาดและผลลัพธ์อาจไม่ถูกต้องหรือไม่สามารถใช้ได้
  • ตัวแปรต่อเนื่องเท่านั้น: เมื่อตัวแปรตัดสินใจต้องมีค่าเป็นจำนวนเต็มหรือเลขฐานสอง (0/1) การผ่อนคลาย LP (LP relaxation) จะให้ค่าขอบเขตล่าง แต่ไม่ใช่ผลลัพธ์ที่ถูกต้อง จะต้องใช้การโปรแกรมจำนวนเต็ม (integer programming)
  • เชิงกำหนด: LP ไม่ได้จำลองความไม่แน่นอนในพารามิเตอร์ จะต้องใช้การโปรแกรมเชิงสุ่ม (stochastic programming) หรือการหาค่าเหมาะสมที่สุดแบบทนทาน (robust optimisation) เมื่อข้อมูลไม่แน่นอน
  • ความเสื่อมและการวนซ้ำ (Degeneracy and cycling): ในบางกรณีที่เกิดขึ้นไม่บ่อยนัก วิธีซิมเพล็กซ์อาจวนซ้ำระหว่างฐานที่เสื่อมโดยไม่ลู่เข้า แม้ว่ากฎป้องกันการวนซ้ำ (เช่น กฎของแบลนด์ - Bland's rule) จะแก้ไขปัญหานี้ได้

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

จุดแข็ง

  • ค่าเหมาะสมที่สุดทั่วโลกที่รับประกัน: เนื่องจากบริเวณที่เป็นไปได้เป็นรูปทรงหลายหน้าแบบนูน (convex polyhedron) ค่าเหมาะสมที่สุดเฉพาะที่ (local optimum) จึงเป็นค่าเหมาะสมที่สุดทั่วโลก (global optimum) ด้วย โดยไม่มีความเสี่ยงที่จะติดอยู่ในผลลัพธ์ที่ไม่เหมาะสมที่สุด
  • ปรับขนาดได้สูง: ตัวประมวลผลสมัยใหม่ (HiGHS, Gurobi, CPLEX) สามารถจัดการแบบจำลองที่มีตัวแปรและข้อจำกัดนับล้านรายการได้ในเวลาไม่กี่วินาที
  • ข้อมูลหลังการแก้ปัญหาที่สมบูรณ์: ราคาเงาและช่วงความไวให้ข้อมูลเชิงลึกที่นำไปปฏิบัติได้เกี่ยวกับมูลค่าทรัพยากรและความเสถียรของผลลัพธ์โดยไม่ต้องทำการคำนวณเพิ่มเติม
  • ไม่มีข้อสมมติฐานเกี่ยวกับการแจกแจง: LP เป็นแบบจำลองเชิงพีชคณิตล้วนๆ ดังนั้นจึงไม่ต้องการการแจกแจงปกติ (normality) หรือคุณสมบัติทางสถิติใดๆ ของข้อมูล

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

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

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

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

1

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

2

แบบจำลองจะถูกแปลงให้อยู่ในรูปแบบมาตรฐาน (canonical or standard form) ที่ตัวประมวลผลสามารถดำเนินการได้ อสมการจะถูกแปลงเป็นสมการโดยการเพิ่มตัวแปรส่วนเกิน (slack or surplus variables) ที่ไม่เป็นลบ และตัวแปรใดๆ ที่ไม่มีขอบเขตจะถูกแทนที่ด้วยผลต่างของตัวแปรที่ไม่เป็นลบสองตัว ขั้นตอนนี้เชิงกลจะสร้างตาราง (tableau) หรือเมทริกซ์ที่อัลกอริทึมทำงานด้วย และจะไม่เปลี่ยนแปลงปัญหา — เพียงแต่ปรับเปลี่ยนรูปแบบเพื่อการคำนวณ

3

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

4

ตัวประมวลผลจะส่งคืนค่าที่เหมาะสมที่สุดของตัวแปรตัดสินใจและค่าวัตถุประสงค์ที่เหมาะสมที่สุด พร้อมด้วยตัวแปรคู่ (shadow prices) และช่วงความไว (sensitivity ranges) ราคาเงา (shadow prices) จะวัดว่าฟังก์ชันวัตถุประสงค์จะดีขึ้นเท่าใดหากข้อจำกัดที่ผูกมัดถูกผ่อนปรนไปหนึ่งหน่วย — ซึ่งบอกผู้มีอำนาจตัดสินใจโดยตรงว่าทรัพยากรเพิ่มเติมจะมีค่ามากที่สุดที่ใด การวิเคราะห์ความไว (sensitivity analysis) จะระบุว่าสัมประสิทธิ์ต้นทุนหรือค่าด้านขวา (right-hand-side value) สามารถเปลี่ยนแปลงได้มากน้อยเพียงใดก่อนที่ฐานปัจจุบัน (basis) จะไม่เหมาะสมที่สุดอีกต่อไป

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

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

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

อะไรทำให้ปัญหา 'เชิงเส้น' สำหรับวัตถุประสงค์ของ LP?

ทั้งฟังก์ชันวัตถุประสงค์และข้อจำกัดทุกข้อต้องเป็นเชิงเส้น — หมายความว่าแต่ละเทอมคือค่าคงที่คูณด้วยตัวแปรตัดสินใจเพียงตัวเดียว โดยไม่มีผลคูณของตัวแปร ไม่มีเลขชี้กำลัง และไม่มีฟังก์ชันที่ไม่เป็นเชิงเส้น หากมีข้อจำกัดหรือวัตถุประสงค์เพียงข้อเดียวที่เกี่ยวข้องกับ เช่น x คูณ y หรือ x ยกกำลังสอง การใช้ LP มาตรฐานจะไม่สามารถใช้ได้ และจำเป็นต้องใช้ตัวประมวลผลการโปรแกรมแบบไม่เชิงเส้น (nonlinear programming) หรือการโปรแกรมกำลังสอง (quadratic programming)

เหตุใดผลลัพธ์ที่เหมาะสมที่สุดจึงอยู่ที่จุดยอดของบริเวณที่เป็นไปได้เสมอ?

บริเวณที่เป็นไปได้ที่กำหนดโดยข้อจำกัดเชิงเส้นคือรูปทรงหลายหน้าแบบนูน (convex polyhedron) หรือรูปทรงหลายหน้าปิด (polytope) ฟังก์ชันวัตถุประสงค์เชิงเส้นนั้นเป็นเชิงเส้นเอง จึงไม่สามารถ 'ดึง' ไปยังภายในของเซตนูนได้ — มันจะบรรลุค่าสุดขีดบนขอบเสมอ และโดยเฉพาะอย่างยิ่งที่จุดยอด (corner point) นี่คือข้อมูลเชิงลึกทางเรขาคณิตที่เป็นรากฐานของกลยุทธ์การเคลื่อนที่จากจุดยอดไปยังจุดยอดของวิธีซิมเพล็กซ์

เมื่อใดที่ฉันควรใช้การโปรแกรมจำนวนเต็มแทน LP?

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

ราคาเงาบอกอะไรฉัน?

ราคาเงา (ตัวแปรคู่ - dual variable) สำหรับข้อจำกัดที่ผูกมัด (binding constraint) บ่งชี้ว่าค่าวัตถุประสงค์ที่เหมาะสมที่สุดจะดีขึ้นเท่าใดหากค่าด้านขวาของข้อจำกัดนั้นถูกผ่อนปรนไปหนึ่งหน่วย โดยที่ทุกอย่างอื่นคงที่ ตัวอย่างเช่น ราคาเงาเท่ากับ 3 สำหรับข้อจำกัดชั่วโมงแรงงานหมายความว่าการเพิ่มแรงงานอีกหนึ่งชั่วโมงจะทำให้วัตถุประสงค์ดีขึ้น 3 หน่วย ข้อจำกัดที่ไม่ผูกมัดจะมีราคาเงาเป็นศูนย์ — ข้อจำกัดเหล่านั้นไม่ได้จำกัดค่าที่เหมาะสมที่สุดในปัจจุบัน

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

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

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

    ISBN: 9780691059136
    คัดลอกแล้ว
  2. Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.

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