การโปรแกรมเชิงเส้น — วิธีซิมเพล็กซ์และการแก้แบบกราฟ

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

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

ความหมายของการโปรแกรมเชิงเส้น

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

ภายใต้ข้อจำกัด เช่น

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

รวมถึงอสมการเชิงเส้นอื่น ๆ ในลักษณะเดียวกัน พร้อมกับเงื่อนไขอย่าง $x_i \ge 0$ เมื่อค่าติดลบไม่มีความหมายในบริบทของปัญหา

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

วิธีแบบกราฟทำงานอย่างไร

ถ้ามีตัวแปรการตัดสินใจเพียงสองตัว คุณสามารถวาดข้อจำกัดแต่ละข้อบนระนาบ $xy$ ได้ ส่วนที่ทับซ้อนกันของทุกบริเวณที่อนุญาตคือบริเวณที่เป็นไปได้

ทุกจุดในบริเวณนั้นเป็นคำตอบที่ใช้ได้ ฟังก์ชันวัตถุประสงค์จะกำหนดค่าให้กับแต่ละจุด

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

ตัวอย่างทำโจทย์: แก้ปัญหาการโปรแกรมเชิงเส้นด้วยกราฟ

สมมติว่าร้านค้าผลิตสินค้าสองชนิด คือ $A$ และ $B$

• กำไรต่อหน่วยของ $A$: $3$
• กำไรต่อหน่วยของ $B$: $5$
• ข้อจำกัดด้านเวลาเครื่องจักร: สินค้า $A$ ใช้ $1$ ชั่วโมงต่อหน่วย สินค้า $B$ ใช้ $2$ ชั่วโมงต่อหน่วย และมีเวลาได้ไม่เกิน $8$ ชั่วโมง
• ข้อจำกัดด้านการประกอบ: สินค้า $A$ ใช้ $1$ ชั่วโมงต่อหน่วย สินค้า $B$ ใช้ $1$ ชั่วโมงต่อหน่วย และมีเวลาได้ไม่เกิน $5$ ชั่วโมง

ให้ $x$ เป็นจำนวนหน่วยของ $A$ และ $y$ เป็นจำนวนหน่วยของ $B$

หาค่าสูงสุดของ

$$P = 3x + 5y$$

ภายใต้ข้อจำกัด

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

หาจุดมุม

จากแกนพิกัดและเส้นข้อจำกัด จุดมุมที่เป็นไปได้คือ

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

จุด $(2,3)$ ได้มาจากการแก้สมการเส้นขอบเขต

$$x + 2y = 8,\quad x + y = 5$$

นำสมการมาลบกันจะได้ $y = 3$ และแทนกลับจะได้ $x = 2$

ทดสอบฟังก์ชันวัตถุประสงค์ที่แต่ละจุดมุม

คำนวณกำไรที่จุดมุมแต่ละจุด:

• ที่ $(0,0)$, $P = 0$
• ที่ $(5,0)$, $P = 15$
• ที่ $(0,4)$, $P = 20$
• ที่ $(2,3)$, $P = 21$

ดังนั้นกำไรสูงสุดคือ

$$P = 21$$

ที่

$$(x,y) = (2,3)$$

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

แนวคิดของวิธีซิมเพล็กซ์

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

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

ดังนั้นภาพจำที่ดีคือ:

• วิธีแบบกราฟ: มองเห็นจุดมุม
• วิธีซิมเพล็กซ์: เดินไปตามจุดมุมโดยไม่ต้องวาดกราฟ

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

ทำไมจุดมุมจึงสำคัญ

ฟังก์ชันวัตถุประสงค์เชิงเส้นสร้างเส้นระดับ เช่น

$$3x + 5y = k$$

สำหรับค่า $k$ ที่ต่างกัน เมื่อคุณเลื่อนเส้นนี้ไปในทิศทางที่ให้กำไรมากขึ้น จุดสุดท้ายที่เส้นยังสัมผัสกับบริเวณที่เป็นไปได้คือจุดที่เกิดค่าสูงสุด

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

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

สับสนระหว่างคำตอบที่เป็นไปได้กับคำตอบเหมาะที่สุด

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

ลืมเงื่อนไขไม่เป็นลบ

ถ้า $x$ และ $y$ แทนปริมาณที่คุณผลิตหรือขนส่ง ค่าติดลบมักไม่มีความหมาย การละเงื่อนไข $x \ge 0$ หรือ $y \ge 0$ อาจทำให้ปัญหาเปลี่ยนไป

คิดว่าคำตอบทุกข้อจะต้องเป็นจำนวนเต็ม

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

คิดว่าทุกปัญหาต้องมีคำตอบที่ดีที่สุดเสมอ

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

ใช้วิธีแบบกราฟทั้งที่มีตัวแปรมากเกินไป

เมื่อมีตัวแปรจำนวนมาก การวาดกราฟไม่ใช่เครื่องมือที่เหมาะสมอีกต่อไป นั่นคือจุดที่วิธีซิมเพล็กซ์หรือวิธีหาค่าเหมาะที่สุดแบบอื่น ๆ กลายเป็นสิ่งจำเป็น

การโปรแกรมเชิงเส้นถูกใช้เมื่อใด

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

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

ลองทำโจทย์ที่คล้ายกัน

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