สรุปเนื้อหา กำหนดการเชิงเส้น คืออะไร
กำหนดการเชิงเส้น หรือ Linear Programming คือ แขนงหนึ่งของคณิตศาสตร์ประยุกต์ที่ถูกพัฒนาขึ้นจากทฤษฎีทางเศรษฐศาสตร์ ตั้งแต่ปี ค.ศ. 1940 ซึ่งกำหนดการเชิงเส้นนี้เป็นเทคนิคอย่างหนึ่งในการตัดสินใจเพื่อแก้ไขปัญหาเกี่ยวกับการจัดสรรทรัพยากรณ์ที่มีอยู่อย่างจำกัด เพื่อให้ได้รับประโยชน์มากที่สุดนั่นเอง
หลักการของกำหนดการเชิงเส้น คือ
- การสร้าง mathematical model ที่ประกอบด้วยสมการและอสมการเชิงเส้นเพื่อจำลองปัญหาที่สนใจ
- หาผลเฉลยจากตัวแบบ
- กรณีตัวแบบมี 2 ตัวแปร จะใช้วิธีทางกราฟในการหาผลเฉลย แต่ถ้ามีตัวแปรหลายตัวจะใช้วิธี simplex ในการหาเฉลย
โครงสร้างของตัวแบบกำหนดการเชิงเส้น จะประกอบไปด้วย
- สมการเป้าหมาย ซึ่งเป็นสมการที่แสดงความสัมพันธืเพื่อกำหนดตัววัดผลของการดำเนินงานให้มีค่าต่ำสุดหรือสูงสุด
- สมการ, อสมการข้อจำกัด ซึ่งจะแสดงเงื่อนไข ขอบเขต หรือข้อจำกัดของทรัพยากรณ์ต่าง ๆ ที่มีอยู่ โดยอาจจะเรียกว่า “ข้อจำกัดเกี่ยวกับโครงสร้าง” ก็ได้
- ตัวแปรตัดสินใจ เป็นตัวแปรที่จะต้องหาค่าเพื่อให้ได้เป้าหมายที่ต้องการ ซึ่งตัวแปรตัดสินใจจะต้องมีความสัมพันธ์เชิงเส้นทั้งในสมการเป้าหมายและข้อจำกัด โดยตัวแปรตัดสินใจ ต้องมีค่ามากกว่าหรือเท่ากับศูนย์ หรือที่เรียกว่า “ข้อจำกัดเกี่ยวกับการไม่เป็นค่าลบ” นั่นเอง
การหาคำตอบอย่างง่ายโดยใช้วิธีกราฟของสมการและอสมการเชิงเส้นที่มีสองตัวแปร
กราฟของอสมการเชิงเส้น
พิจารณากราฟของสมการเชิงเส้นสองตัวแปร
สมการ x = 1
มี จุด (1,1), (1.3), (1, 2) , (1, 21) และจุดอื่น ๆอีกมากมายอยู่บนสมการ ดังกราฟรูปที่ 1
สมการ x+y= 5
มี จุด (1,4), (2.,3), (O, 5) , (5, 0) และจุดอื่น ๆอีกมากมายอยู่บนสมการ ดังกราฟรูปที่ 2
จากสมการเส้นตรง x = 1 จะเห็นว่าสมการดังกล่าวจะแบ่งระนาบออกเป็นสองส่วน คือ ส่วนที่อยู่ทางซ้ายของเส้นตรงและส่วนที่อยู่ทางขวาของเส้นตรง
จากกราฟ จุด ( 2, 1), ( 3, 5), (5, -1), (32, 3) และ (6, -2) อยู่ทางขวาของเส้นตรง ดังกราฟรูปที่ 3
ถ้าต้องการกล่าวถึงจุดทุกจุดทางขวาของเส้นตรง นั่นคือ กล่าวถึงทุกจุดที่มีพิกัดของ x มากกว่า 1 หรือ {(x, y) | x > 1} จะใช้เส้นประและการแรงาบริเวณด้านขวาของกราฟเส้นตรง x = 1 เพื่อแสดงกราฟของอสมการ x > 1 ดังกราฟรูปที่ 4.1
และถ้าต้องการทุกจุดที่มีพิกัดของ x มากกว่า 1 รวมทุกจุดบนเส้นตรง x= 1 ซึ่งมีอสมการ x มากกว่าหรือเท่ากับ 1 หรือ {(x, y) I x มากกว่าหรือเท่ากับ 1 ) จะได้รูปดังกราฟรูปที่ 4.2
กราฟของระบบอสมการเชิงเส้น
การพิจารณาอสมการเชิงเส้นมากกว่าหนึ่งอสมการพร้อม ๆ กัน เราจะเรียกว่า “ระบบอสมการเชิงเส้น” โดยคำตอบของระบบอสมการเชิงเส้น คือ คู่อันดับ (x, y ) ที่สอดคล้องกับอสมการทั้งหมดของระบบอสมการ หรือคู่อันดับ ( x, y ) ที่ค่า x และค่า y ทำให้อสมการทั้งหมดเป็นจริงและถ้าพิจารณาจากกราฟ คำตอบของระบบอสมการเชิงเส้นจะแทนด้วยบริเวณที่ซ้อนทับกันของกราฟของอสมการทั้งหมด
ตัวอย่าง การแก้ปัญหากำหนดการเชิงเส้นโดยวิธีใช้กราฟ
ในการแก้ปัญหากำหนดการเชิงเส้นนั้นจะต้องเริ่มต้นด้วยการสร้างแบบจำลองทางคณิตศาสตร์ ซึ่งเป็นการแปลงสถานการณ์ปัญหาให้เป็นปัญหาทางคณิตศาสตร์ จากนั้นจึงหาคำตอบของปัญหาโดยใช้กราฟช่วย ตัวอย่างเช่น
ตัวอย่างข้อสอบ กำหนดการเชิงเส้น
1. บริษัทจัดรายการโทรทัศน์ท้องถิ่นแห่งหนึ่งพบว่า ในแต่ละสัปดาห์ ถ้าจัดรายการโปรแกรม A ซึ่งมีมิวสิควิดี โอ 20 นาที และโฆษฌา 1 นาที จะมีผู้ชมรายการแต่ละครั้ง 30,000 คน ในขณะที่รายการโปรแกรม B ซึ่งมีมิวสิควิดิโอ 10 นาทีและโฆษณา 1 นาที จะมีผู้ชมรายการแต่ละครั้ง 10,000 คน ถ้าในหนึ่งสัปดาห์ผู้จัดรายการจะต้องให้มีโฆษณาอย่างน้อย 6 นาที และมีมิวสิควิดีโอไม่เกิน 80 นาที อยากทราบว่าจะต้องจัดรายการโทรทัศน์โปรแกรม A และ B อย่างละกี่ครั้งต่อสัปดาห์ โดยให้มีผู้ชมรายการมากที่สุด จงเขียนตัวแบบกำหนดการเชิงเส้น
2. บริษัทขนส่งแห่งหนึ่งมีรถบรรทุกสองประเภท รถประเภท A มีพื้นที่สำหรับบรรทุกสินค้าที่ต้องใช้ความเย็นได้ 20 ลูกบาศก์หลา และไม่ต้องใช้ความเย็น ได้ 30 ลูกบาศก์หลา ส่วนรถประเภท B มีพื้นที่สำหรับบรรทุกสินค้าที่ต้องใช้ความเย็นได้ 20 ลูกบาศก็หลา และไม่ต้องใช้ความเย็นได้ 10 ลูกบาศก์หลา ถ้าลูกค้าที่มาใช้บริการขนส่งสินค้าต้องการให้บรรทุกสินค้าที่ต้องใช้พื้นที่ที่ใช้ความเย็น 160 ลูกบาศก์หลา และไม่ต้องใช้เความเย็น 120 ลูกบาศก์หลา จงเขียนตัวแบบกำหนดการเชิงเส้น เพื่อหาจำนวนรถบรรทุกแต่ละประเภทที่จะใช้ในการขนส่งสินค้าให้แก่ลูกค้าผู้นี้ โดยเสียค่าใช้จ่ายน้อยที่สุด ถ้าค่าใช้จ่ายสำหรับรถประเภท A คันละ 3000 บาท และประเภท B คันละ 2000 บาท
3. โรงงานกลั่นน้ำมัน มีเครื่องกลั่นอยู่ 2 เครื่อง ในการเดินเครื่องกลั่นแต่ละครั้ง เครื่องกลั่นที่หนึ่งกลั่นน้ำมันเกรด A ได้ 1 หน่วย เกรด B ได้ 3 หน่วย และเกรด C ได้ 1 หน่วย สำหรับเครื่องกลั่นที่สองกลั่นน้ำมันเกรด A ได้ 1 หน่วย เกรด B ได้ 4 หน่วย และเกรด C ได้ 5 หน่วย โรงงานต้องการกลั่นน้ำมันส่งลูกค้า โดยเป็นน้ำมันเกรด A 100 หน่วย เกรด B 340 หน่วย และเกรด C 150 หน่วย โรงงานจะต้องเดินเครื่องกลั่นเครื่องละกี่ครั้ง จึงจะได้น้ำมันแต่ละเกรดตามความต้องการของลูกค้า และเสียค่าใช้จ่ายน้อยที่สุด ถ้าค่าใช้จ่ายแต่ละเครื่องสำหรับการเดินเครื่องกลั่นแต่ละครั้งเท่ากับ 4,000 บาท
4. เกษตรกรต้องการวางแผนปลูกพืชสามชนิดคือ ถั่วเหลือง ข้าวโพด และอ้อย บนพื้นที่ 15 ไร่ โดยการปลูกอ้อยจะใช้เวลาทำงาน 5 ชั่วโมง เงินลงทุน 1500 บาท และได้กำไร 1200 บาทต่อไร่ ส่วนข้าวโพดจะใช้เวลาทำงาน 7 ชั่วโมง เงินลงทุน 2,000 บาท และได้กำไร 1500 บาทต่อไร่ และการปลูกถั่วเหลืองจะต้องใช้เวลา 4 ชั่วโมง เงินลงทุน 1,000 บาท และกำไร 800 บาทต่อไร่ ถ้ามีเงินลงทุนทั้งหมด 60,000 บาทและเวลาทำงานทั้งหมด 52 ชั่วโมง จะต้องปลูกพืชอย่างไรถึงจะมีกำไรสูงที่สุด
