Linear Programming

Linear Programming (กำหนดการเชิงเส้น)

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

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

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

โครงสร้างของตัวแบบกำหนดการเชิงเส้น (Structure of the Linear Programming Model)

ตัวแบบกำหนดการเชิงเส้น (Formulation of Linear Programming Models)
1. ตัวแปรซึ่งไม่ทราบค่าและต้องการหาคำตอบ เรียกว่า ตัวแปรตัดสินใจ (Decision variables) ตัวแปรทุกตัวต้องไม่เป็นค่าลบ (non-negative restriction)
2. ฟังก์ชันจุดประสงค์ หรือ สมการเป้าหมาย (Objective Function) ซึ่งแสดงเป้าหมายของการหาคำตอบว่าต้องการหาค่าสูงสุดหรือค่าต่ำสุด เขียนในรูปฟังก์ชันของตัวแปรตัดสินใจ
3. สมการหรืออสมการแสดงเงื่อนไขบังคับ หรือ เรียกว่า การสร้างข้อจำกัด (Constraints)

การสร้างสมการเป้าหมาย
- กำหนดตัวแปรของปัญหา
- เขียนให้อยู่ใรรูปของสมการทางคณิตศาสตร์ ( ระบุว่าเป็นค่าสูงสุดหรือต่ำสุด )

รูปทั่วไปของตัวแบบกำหนดการเชิงเส้น

รูปแบบทั่วไปของตัวแบบกำหนดการเชิงเส้น กำหนดให้มีตัวแปรตัดสินใจ n ตัว (X1,...,Xn) มีเงื่อนไขบังคับด้าน ต่างๆ m เงื่อนไข
Z เป็นค่าของฟังก์ชันจุดประสงค์
Cj เป็นค่าการเปลี่ยนแปลงของ Z เมื่อ Xj เปลี่ยนไป 1 หน่วย ( ถ้า Z เป็นผลกำไรรวม Cj ก็เป็นกำไรต่อหน่วย , ถ้า Z เป็นต้นทุนรวม Cj ก็เป็นต้นทุนต่อหน่วย )
bi เป็นทรัพยากรชนิดที่ i ที่มีอยู่
aij เป็นปริมาณทรัพยากรชนิดที่ i ที่ตัวแปร Xj ใช้ไปในการผลิต 1 หน่วย
รูปย่อ

กรณีหาค่าต่ำสุด


รูปย่อ

( การหาค่าสูงสุด คือ ประโยชน์ที่ได้รับ และ การหาค่าต่ำสุดคือ เสียประโยชน์ )

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

ก. ระบุตัวแปรตัดสินใจ คือ ตัวแปรที่ต้องการหาคำตอบ มีทั้งหมดกี่ตัว โดยมากใช้ Xj แทนตัวแปรตัดสินใจตัวที่ j

ข. ระบุสัมประสิทธิ์ของตัวแปรตัดสินใจในฟังก์ชันจุดประสงค์ ใช้ Cj แทนสัมประสิทธิ์ของตัวแปรตัดสินใจ
ถ้าเป้าหมายคือการหากำไรสูงสุด Cj หมายถึงกำไรต่อหน่วยของสินค้า j

ถ้าเป้าหมายคือการหาต้นทุนต่ำสุด Cj หมายถึงต้นทุนต่อหน่วยของสินค้า

ค. สร้างฟังก์ชันจุดประสงค์ ฟังก์ชันจุดประสงค์คือการนำเป้าหมายมาเขียนในรูปฟังก์ชันของตัวแปรตัดสินใจ เช่น

ให้ X1 แทนจำนวนวนการผลิตโต๊ะ
X2 แทนจำนวนการผลิดตู้
Z = กำไรรวม
ขาย โต๊ะได้กำไรตัวละ 300 บาท ขายตู้ได้กำไรตัวละ 500 บาท
กำไร = Z = 300X1 + 500X2 เป็นฟังก์ชันจุดประสงค์ของปัญหาว่า ควรผลิตโต๊ะและตู้ อย่างละเท่าไรจึงจะได้กำไรสูงสุด

ง. ระบุปริมาณทรัพยากรที่มีอยู่ (bi) หรือเรียกว่าRHS (Right Hand Side) เช่นมีไม้อยู่ทั้งหมด 10,000 เมตร มีแรงงานอยู่ทั้งหมด 2400 ชม เป็นต้น

จ. หาปริมาณการใช้ทรัพยากร แต่ละชนิดของการผลิดสินค้าแต่ละชนิด (aij) เช่น ผลิตโต๊ะ 1 ตัวต้องใช้ไม้ 100 ตารางเมตร และแรงงาน 10 ชม ผลิตตู้ 1 ตัวต้องใช้ไม้ 150 เมตร และแรงงาน 12 ชม

ฉ. สร้างเงื่อนไขบังคับของทรัพยากรที่มีอยู่โดยใช้ข้อมูลจากข้อ ง และ จ

เช่น ผลิตโต๊ะ 1 ตัวต้องใช้ไม้ 100 ตารางเมตร จะได้ ผลิตโต๊ะ X1 ตัวใช้ไม้ 100X1 ตารางเมตร

วิธีการที่ใช้ในกำหนดการเชิงเส้น
แบ่งเป็น 2 แบบ คือ
1. แบบสองตัวแปร
2. แบบมากกว่าสองตัวแปร
แบบ 2 ตัวแปรมี 3 ประเภทคือ
1.1 วิธีจำกัดขอบข่ายของคำตอบ
1.2 วิธีอนุมานทางคณิตศาสตร์
1.3 วิธีกราฟ

1. วิธีจำกัดขอบข่ายของคำตอบ
- ทำได้โดยสร้างตารางแสดงค่าของตัวแปรตั้งแต่ 0,1,2,...
- ภายใต้ตารางแสดงผลลัพธ์ ที่เกิดจากการแทนค่าตัวแปรในสมการวัตถุประสงค์
- ใช้สมการหรืออสมการของข้อจำกัดตัดช่วงตัวเลขที่เป็นไปได้ออก ดังนั้นจะเหลือค่าภายในตารางที่เรียกว่า feasible solution ผลลัพธ์ ที่ให้ค่าสูงสุดหรือ ต่ำสุดหาจากผลลัพธ์ที่เป็นไปได้ โดยดูจากค่าที่อยู่ที่่บริเวณริมรอบๆเส้นดังกล่าว

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

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

3. การคำนวณด้วยกราฟ
ให้นำตัวแบบที่สร้างไว้แล้วนั้นมา plot graph แล้วพิจรณาขอบเขตที่เป็นไปได้ โดยพิจรณาจากข้อจำกัด เมื่อได้ขอบเขตดังกล่าวแล้ว ให้พิจรณาค่าที่ต้องการเพื่อให้ได้เป้าหมายที่วางไว้ การพิจารณาขอบเขตที่เป็นไปได้ ต้องนำข้อจำกัดที่เขียนอยู่ในรูปอสมการเส้นตรงมาพิจรณาเป็นเส้นๆไป