บทที่ 2 เอกสารที่เกี่ยวข้อง

ในการทำโครงงานคณิตศาสตร์ครั้งนี้ คณะผู้จัดทำได้ศึกษาเอกสารที่เกี่ยวข้อง เพื่อใช้เป็นแนวทางในทำโครงงาน ดังรายละเอียดต่อไปนี้ 2.1 ความรู้เบื้องต้นเกี่ยวกับกำหนดการเชิงเส้น 2.2 ความรู้เบื้องต้นเกี่ยวกับการใช้ Excel’s Solver แก้ปัญหาการโปรแกรมเชิงเส้น 2.1 กำหนดการเชิงเส้น กำหนดการเชิงเส้น เป็นเทคนิคเชิงคณิตศาสตร์ที่ใช้ในการจัดสรรหรือแจกจ่ายทรัพยากรที่มีอยู่อย่างจำกัดให้เกิดผลดีที่สุด และตรงตามวัตถุประสงค์ที่วางไว้อย่างมีประสิทธิภาพ เป้าหมายจะเป็นฟังก์ชันเชิงเส้น เรียกว่า ฟังก์ชันเป้าหมาย ซึ่งกำหนดในรูปของการหาค่าสูงสุด หรือหาค่าต่ำสุดของฟังก์ชัน โดยมีข้อจำกัดเกี่ยวกับการใช้ทรัพยากรอันได้แก่ กลังคน เงินทุน วัตถุดิบเครื่องจักรต่างๆกำหนดในรูปของสมการหรืออสมการซึ่งความสัมพันธ์ระหว่างตัวแปรทั้งหมดที่สมนัยกันทรัพยากรเป็นแบบเชิงเส้น ปัญหากำหนดการเชิงเส้นนี้เกิดขึ้นราวปลาย ค.ศ. 1940 กำหนดการเชิงเส้นช่วยแก้ปัญหาบางปัญหาที่ไม่สามารถแก้ได้ด้วยตัวเองเราเสียเวลานานและอาจมองข้ามปัญหาปลีกย่อยบางอย่างไป กำหนดการเชิงเส้นมีประโยชน์ในการแก้ปัญหาที่มีทางเลือกมากมาย ซึ่งเกิดขึ้นของทางเลือกเหล่านั้นอยู่ภายใต้สภาวการณ์ที่แน่นอนเพียงแต่ไม่ทราบว่าทางเลือกไหนดีที่สุด ปัจจุบันประเทศที่มีความเจริญทางวิชาการนอยมประยุกต์ใช้กำหนดการเชิงสันแก้ปัญหาด้านธุรกิจอุตสาหกรรม และองค์กรของรัฐอย่างกว้างขวาง เช่น ปัญหาเกี่ยวกับการขนส่ง การคมนาคม การวางแผนเกี่ยวกับการผลิตและสินค้าคงคลัง การวางแผนพัฒนาการเกษตร การทหาร การจัดการทางด้านโภชนา การจัดสรรงบประมาณ การให้บริการชุมชน ซึ่งปัญหาเหล่านี้มีการจำกัดของทรัพยากร ผู้วิเคราะห์ต้องศึกษาลักษณะของปัญหาและข้อจำกัด แล้วนำมาคิดวิเคราะห์เพื่อแสวงหาคำตอบที่ดีที่สุดต่อปัญหาให้บรรลุตามเป้าหมายที่วางไว้ 2.2 แบบจำลองทางคณิตศาสตร์ บุญสม ศิริโสภนา แลพประสาร บุญเสริม ได้กล่าวถึงแบบจำลองทางคณิตศาสตร์ คือความคิดพื้นฐาน และเทคนิคของกำหนดการเชิงเส้นช่วยในการตัดสินใจเกี่ยวกับปัญหาทรัพยากรที่มีอยู่อย่างจำกัดเพื่อให้เกิดประโยชน์หรือประสิทธิภาพในการสูงสุดแก่ผู้ตัดสินใจนั้น แสดงว่า การแก้ปัญหา กำหนดการเชิงเส้นจึงเกี่ยวกับการหาค่าต่ำสุด หรือค่าสูงสุดภายใต้เงื่อนไขข้อบังคับ โดยการนำเอาเงื่อนไขข้อบังคับมาสร้างในรูปแบบจำลองกำหนดการเชิงเส้น สำหรับแบบจำลองทางคณิตศาสตร์ของปัญหาที่ใช้ในกำหนดการเชิงเส้น ซึ่งเรียกว่า ตัวแบบกำหนดการเชิงเส้น จะต้องมีโครงสร้างดังนี้ คือ 1. สมการเป้าหมาย เป็นสมการที่แสดงถึงความสัมพันธ์เพื่อกำหนดเป้าหมายสูงสุดหรือต่ำสุดซึ่งจะเป็นตัววัดผลการดำเนินงาน 2. สมการหรืออสมการข้อจำกัด แสดงข้อจำกัดของทรัพยากรต่างๆที่มีอยู่ เพื่อใช้ในการดำเนินงาน 3. ตัวแปรตัดสินใจ เป็นกิจกรรมในการแก้ปัญหาซึ่งจะเป็นตัวตัดสินใจในการดำเนินงาน ตัวแปรตัดสินใจทั้งหลายจะต้องมีความสัมพันธ์เชิงเส้น ทั้งในสมการเป้าหมายและข้อจำกัด 4. ตัวแปรตัดสินใจมากกว่าหรือเท่ากับศูนย์ หมายเหตุ 1. สมการหรืออสมการข้อจำกัดในข้อ2 เรียกว่า ข้อจำกัดเกี่ยวกับโครงสร้าง 2. ตัวแปรตัดสินใจ ในการแก้ปัญหากำหนดการเชิงเส้นจะต้องมีค่ามากกว่าหรือเท่ากับศูนย์ในข้อ 4 ข้อจำกัดนี้เรียกว่า ข้อจำกัดเกี่ยวกับการไม่เป็นค่าลบ ตัวแบบในรูปแบบคาโมนิคัลของกำหนดการเชิงเส้นเป็นดังนี้ สมการเป้าหมาย ค่าสูงสุด R=p_1 x_1+p_2 x_2+...+p_n x_n ภายใต้ข้อจำกัด : a_11 x_1+a_12 x_2+...+a_1n x_n≤c_1 a_21 x_1+a_22 x_2+...+a_2n x_n≤c_2 …………………………………………………… a_m1 x_1+a_m2 x_2+...+a_mn x_n≤c_m โดยที่ R=f(x_j) ; j=1,2,3,…,n เป็นสมการเป้าหมาย x_j ; x=1,2,3,…,n เป็นตัวแปรตัดสินใจของแต่ละกิจกรรม a_ij,p_j เป็นสัมประสิทธิ์ตัวแปรตัดสินใจซึ่งเป็นค่าคงตัว c_i ; i=1,2,3,…,m เป็นปริมาณของทรัพยากรที่จะนำมาใช้ในการกระทำกิจกรรมเขียนในรูปสั้นๆได้เป็น สมการเป้าหมาย ค่าสูงสุด R=∑_j^n▒〖=1〗 p_j x_j ภายใต้ข้อจำกัด : R=∑_j^n▒〖=1〗 a_ij x_j≤c_i ; i=1,2,3,…,m x_j≥0 ; j=1,2,3,…,n สมการเป้าหมาย ค่าต่ำสุด Z=c_1 y_1+c_2 y_2+...+c_n y_n b_11 y_1+b_12 y_2+...+b_1n y_n≥p_1 b_21 y_1+b_22 y_2+...+b_2n y_n≥p_1 ………………………………………………… b_m1 y_1+b_m2 y_2+...+b_mn y_n≥p_m y_1,y_2,y_3,…,y_n≥0 โดยที่ Z=f(x_j ) ; j=1,2,3,…,n เป็นสมการเป้าหมาย y_j ; y=1,2,3,…,n เป็นตัวแปรตัดสินใจของแต่ละกิจกรรม b_ij,c_j เป็นสัมประสิทธิ์ของตัวแปรตัดสินใจซึ่งเป็นค่าคงตัว p_i ; i=1,2,3,…,n เป็นปริมาณของทัพยากรที่จะนำมาใช้ในการกระทำกิจกรรมเขียนในรูปสั้นๆได้เป็น สมการเป้าหมาย ค่าต่ำสุด Z=∑_j^n▒〖=1〗 c_j y_j ภายใต้ข้อจำกัด : Z=∑_j^n▒〖=1〗 b_ij y_j≥p_i ;i=1,2,3,…,m y_i≥0 ;j=1,2,3,…,n