โปรแกรมเชิงเส้น (Linear Programming)
บทนำ
โปรแกรมเชิงเส้น (Linear Programming) เป็นเทคนิคที่รู้จักกันแพร่หลายและเป็นส่วนหนึ่งของการวิจัยดำเนินงาน (Operations Research) ในหลายๆด้าน นักบริหาร วิศวกรหรือนักวิทยาศาสตร์ในหลายๆ หน่วยงานได้ประยุกต์ใช้วิธีการทางโปรแกรมเชิงเส้น ในการแก้ปัญหาทางการจัดสรรปัจจัยหรือทรัพยากร (allocating resource) โดยที่ปัจจัยหรือทรัพยากรมีความหมายรวมถึงวัตถุดิบ กำลังคน เวลา สถานที่ เงินตรา หรือความรู้ความสามารถต่างๆ ปัญหาการจัดสรรปัจจัยและทรัพยากรเกิดขึ้นเมื่อเราต้องการจัดสรรทรัพยากรที่มีอยู่จำกัดทั้งขนาด ปริมาณ และขอบเขตของการใช้งาน เพื่อให้เกิดประโยชน์สูงสุด
โปรแกรมเชิงเส้นเป็นเทคนิคในการแก้ไขปัญหาทางการจัดสรรปัจจัยและทรัพยากรที่มีลักษณะความสัมพันธ์ของตัวแปรต่างๆ เป็นแบบเชิงเส้น โดยมีจุดหมายเพื่อแก้ปัญหาและตัดสินใจให้เกิดผลตามแนวทางการดำเนินงานที่ดีที่สุด (optimal) เช่นกำไรสูงสุด ค่าใช้จ่ายน้อยที่สุด หรือแนวทางการตำเนินงานอื่นๆ ที่ให้ผลประโยชน์มากที่สุดต่อระบบนั้นๆ โดยพิจารณาเงื่อนไขหรือข้อจำกัดที่กำหนด เช่นสภาวะตลาด การขาดแคลนวัตถุดิบ กำลังคน เงินทุน สถานที่ ความรู้ข้อกำหนดของกฎหมายและระเบียบต่างๆของสังคม นโยบายของฝ่ายบริหาร ขอบข่ายของธุรกิจที่ดำเนินอยู่และอื่นๆ ตัวอย่างเช่น การใช้เทคนิคทางโปรแกรมเชิงเส้นที่ใช้กับการแก้ปัญหาทางด้านขนส่งสินค้า ซึ่งจะเกี่ยวข้องกับสินค้าชนิดต่างๆ น้ำหนักและขนาดของสินค้า ราคาขนส่งสินค้า กำลังคนที่ใช้ในการขับรถ โดยมีข้อจำกัดต่างๆ เช่น ปริมาณและขนาดของรถที่มีอยู่ น้ำหนักของสินค้าที่สามารถบรรทุกได้ต่อเที่ยว ปริมาณความต้องการของตลาด เงินทุนจำกัด เวลาที่ในการขนส่งสินค้า นอกจากนี้โปรแกรมเชิงเส้นได้ถูกนำไปใช้ในการแก้ปัญหาทางด้านการผลิตของอุตสาหกรรมต่างๆ ซึ่งจะต้องเกี่ยวข้องโดยตรงกับวัตถุดิบชนิดต่างๆ ที่ใช้ในการผลิต ชนิดของเครื่องจักรที่มี กำลังคนที่ผลิต ราคาขาย และการตลาด โดยมีเงื่อนไขต่างๆ เช่น ขนาดขีดความสามารถในการผลิตของเครื่องจักรและแรงงาน ปริมาณความต้องการของตลาด ปริมาณวัตถุดิบและพลังงานอื่นๆในการผลิตเช่น น้ำ น้ำมัน ไฟฟ้า ไม้ มีอยู่ในจำนวนจำกัด เงินทุนจำกัด
เทคนิคทางการโปรแกรมเชิงเส้น ในการวิจัยดำเนินงานนี้พัฒนามาจากผลความก้าวหน้าทางวิทยาศาสตร์ ซึ่งมีแนวคิดริเริ่มมาจากนักคณิตศาสตร์วิทยาศาสตร์หลายๆท่านซึ่งได้นำไปใช้ในทฤษฎีเกม รวมทั้งถูกพัฒนานำไปใช้ในทางการขนส่ง นอกจากนี้ได้มีการใช้เทคนิคดังกล่าวในการแก้ปัญหาทางโภชนาการ ต่อมาได้มีการใช้คณิตศาสตร์และเทคนิคที่เกี่ยวข้องมาแก้ปัญหาทางการวางแผนโครงงานในกองทัพ
ปัจจุบันเป็นที่ยอมรับกันในหลายๆวงการในการนำเทคนิคทางการโปรแกรมเชิงเส้นไปใช้ประโยชน์ในหลายๆด้านเช่น ทางการเกษตร ทางเศรษฐศาสตร์ และการจัดการเกี่ยวกับการผลิต ทางอุตสาหกรรม
รูปแบบแทนระบบทางคณิตศาสตร์ของโปรแกรมเชิงเส้น
โปรแกรมเชิงเส้นประกอบไปด้วย 2 ส่วน ดังนี้
1. มีสมการกำหนดเป้าหมาย (objective function) คือสมการแสดงความสัมพันธ์ของต้นทุน กำไร เพื่อให้กำหนดเป้าหมายสูงสุดหรือต่ำสุด
2. มีสมการแสดงขอบข่าย (constraints) ซึ่งแสดงข้อจำกัดต่างๆของปัจจัยหรือทรัพยากรในรูปสมการหรืออสมการ
โดยที่สมการต่างๆ ทั้งหมดเป็นสมการเชิงเส้น เมื่อเทียบกับตัวแปร
คำตอบของสมการแสดงขอบข่ายอาจจะมีได้หลายคำตอบ ซึ่งคำตอบเหล่านี้อยู่ภายใต้ข้อจำกัดต่างๆที่กำหนดให้ อย่างไรก็ตามสมการกำหนดเป้าหมายเป็นตัววัดผลหรือตัวตัดสินว่าระหว่างคำตอบทั้งหมดของสมการแสดงขอบข่าย คำตอบใดเป็นคำตอบที่ดีที่สุด นั่นคือคำตอบนั้นจะทำให้สมการกำหนดเป้าหมายมีค่าที่ดีที่สุด ซึ่งเราจะต้องพยายามหาค่าเป็นไปตามเป้าหมายโดยอาศัยเทคนิคที่มีอยู่ ตัวแปรต่างๆ จะเป็นตัวแทนจำนวนปริมาณหรือค่าของปัจจัยที่มีอยู่จำกัดโดยการกำหนดของสมการหรืออสมการในขอบข่ายของปัญหา
ตัวอย่างง่ายๆ ของโปรแกรมจะประกอบไปด้วยตัวแปรตัดสินใจซึ่งเป็นค่าอินพุท และเอาท์พุต ซึ่งเป็นผลลัพธ์ โดยที่ค่าของตัวแปรเหล่านี้อยู่ในข้อจำกัดของปัจจัยต่างๆที่กำหนด จุดประสงค์ของโปรแกรมเชิงเส้นก็คือหาค่าของตัวแปรเหล่านี้ที่ทำให้สมการกำหนดเป้าหมายมีค่าที่ดีที่สุด
ขั้นตอนการดำเนินการของโปรเกรมเชิงเส้น
ขั้นตอนของการใช้โปรแกรมเชิงเส้นในการแก้ปัญหา ประกอบไปด้วย
1. จัดรูปแบบแทนระบบของปัญหา (Model Formulation)
ก่อนอื่นต้องศึกษาข้อมูลองค์ประกอบของปัญหาให้เข้าใจ โดยเลือกเฉพาะองค์ประกอบที่สำคัญและมีอิทธิพลมาก แล้วจัดตั้งตัวแปรแทนส่วนประกอบของปัญหานั้นๆ ให้ถูกต้อง
2. การหาผลลัพธ์ของรูปแบบแทนระบบของปัญหา (Model Solution)
การจัดตั้งรูปแบบแทนระบบของปัญหา (Model Formulation)
ในการจัดตั้งรูปแบบแทนระบบของปัญหาโดยใช้โปรแกรมเชิงเส้น เราต้องทำความเข้าใจและศึกษาปัญหาอย่างชัดเจน นอกจากนี้ยังต้องสามารถระบุสิ่งต่อไปนี้ในปัญหา
1. ตัวแปรตัดสินใจ หรือเรียกสั้นๆ ว่า ตัวแปร (decision variables) ซึ่งคือตัวแปรที่สำหรับใส่เข้าไปในระบบ และเป็นตัวแปรที่เราสามารถจะควบคุมได้ ตัวแปรนี้เป็นสิ่งสำคัญที่เราจะป้อนเข้าไปในระบบเพื่อให้เกิดประโยชน์สูงสุด ตัวอย่างเช่น จำนวนสินค้าที่จะผลิตซึ่งเป็นตัวแปรที่เราควบคุมได้
2. พารามิเตอร์เป็นค่าในระบบที่เราไม่สามารถควบคุมได้ ตัวอย่างเช่นราคาสินค้าซึ่งขึ้นอยู่กับกลไกตลาด
3. สมการกำหนดเป้าหมาย (objective function) คือสมการแสดงความสัมพันธ์ของต้นทุน กำไร เพื่อให้กำหนดเป้าหมายสูงสุดหรือต่ำสุด
4. สมการแสดงขอบข่าย (constraints) ซึ่งแสดงข้อจำกัดต่างๆของปัจจัยหรือทรัพยากรในรูปสมการหรืออสมการ
เมื่อจัดตั้งรูปแบบแทนระบบของปัญหาโดยเขียนให้อยู่รูปแบบทางคณิตศาสตร์ รูปแบบที่ได้จะเป็นรูปแบบของโปรแกรมเชิงเส้นก็ต่อเมื่อมีคุณสมบัติต่อไปนี้
1. สมการกำหนดเป้าหมายจะต้องเป็นเชิงเส้น นั่นคือ ตัวแปรทุกตัวจะต้องมีกำลังเป็น 1 เท่านั้น นอกจากนี้จะต้องเขียนอยู่ในรูปของ การบวกและการลบของตัวแปรต่างๆ เท่านั้น ตัวอย่างเช่น เป็นเชิงเส้น เพราะตัวแปร x และ y มีกำลังเท่ากับ 1 และตัวแปรอยู่ในรูปของผลบวก แต่ ไม่เป็นเชิงเส้นเนื่องจากตัวแปรอยู่ในรูปของผลคูณของตัวแปร x และ y
2. สมการกำหนดเป้าหมายจะต้องระบุว่าต้องการหาค่าต่ำสุดหรือสูดสุด สมการกำหนดเป้าหมายจะต้องแสดงถึงจุดประสงค์ในการตัดสินใจ เช่น การหากำไรสูงสุด ค่าใช้จ่ายต่ำสุด
3. สมการแสดงขอบเขตเป็นเชิงเส้น นอกจากนี้จะต้องเขียนให้อยู่ในรูปของ หรือ = เท่านั้น (ถ้าสมการอยู่ในรูปของ < หรือ > รูปแบบนี้จะไม่ใช้ปัญหาของโปรแกรมเชิงเส้น)
รูปแบบของปัญหาทางการโปรแกรมเชิงเส้น จะสามารถเขียนได้ดังนี้
ตัวอย่างข้างล่างนี้เป็นตัวอย่างอย่างง่ายของโปรแกรมเชิงเส้น
ตัวอย่าง Diet Problem
ปัญหาการเลือกสารอาหารทางด้านโภชนาการทาง อย่างเช่น มีอาหารอยู่ทั้งหมด 4 ประเภท สิ่งที่เราสนใจคือ เราควรจะทานอาหารประเภทใดจำนวนเท่าไรจีงจะได้สารอาหารประกอบด้วย โปรตีน วิตามินและ ธาตุเหล็ก ครบตามความต้องการของร่างกาย โดยที่เสียค่าใช้จ่ายน้อยที่สุด ในการแก้ปัญหานี้ อย่างแรกที่เราควรจะรู้คือปริมาณสารอาหารที่มีอยู่ในแต่ละประเภท นอกจากนี้เราควรรู้ปริมาณสารอาหารแต่ละชนิดที่เราควรจะได้รับ รวมถึงราคาของอาหารแต่ละประเภท ข้อมูลทั้งหมดที่เราต้องการสามารถเขียนลงในตารางได้ดังนี้
อาหาร (ประเภท) | |||||
1 | 2 | 3 | 4 | ปริมาณสารอาหารที่ต้องการ | |
โปรตีน | 80 | 120 | 60 | 100 | 700 |
วิตามิน | 30 | 0 | 10 | 10 | 250 |
เหล็ก | 15 | 10 | 20 | 5 | 300 |
ราคา (ต่อหน่วย) | 40 | 65 | 20 | 50 |
ตารางข้างต้นแสดงพารามิเตอร์ต่างๆ สำหรับปัญหาข้างต้น เราจะเห็นได้ว่าอาหารประเภทที่ 1 มีโปรตีนอยู่ 80 กรัม วิตามิน 30 กรัม และ เหล็ก 20 กรัม โดยที่อาหารประเภทนี้มีราคา 40 บาท ในทำนองเดียวกัน อาหารประเภทที่ 2 มีราคา 65 บาทมีสารอาหารโปรตีน 120 กรัม วิตามิน 0 กรัม และ เหล็ก 10 กรัม ปริมาณสารอาหารแต่ละชนิดที่ร่างกายเราต้องการมีดังนี้ โปรตีนเราต้องการอย่างน้อย 700 กรัม วิตามิน 250 กรัม และ เหล็ก 300 กรัม ตัวแปรตัดสินใจ คือปริมาณสารอาหารในแต่ละประเภทที่ควรจะบริโภค กำหนดให้ตัวแปรเหล่านี้คือ แทนปริมาณอาหารในแต่ละประเภท จุดมุ่งหมายคือต้องการหาค่าตัวแปร โดยที่ร่างกายจะต้องได้ปริมาณสารอาหารแต่ละชนิดครบตามความต้องการ โดยที่เสียค่าใช้จ่ายน้อยที่สุด
เมื่อเราได้ตัวแปรและค่าพารามิเตอร์ต่างๆแล้วขั้นตอนไปก็คือหาสมการกำหนดเป้าหมาย ซึ่งคือผลรวมทั้งหมดราคาของอาหารทุกประเภท จากตารางข้างต้น ราคาของอาหารประเภทที่ 1 มีค่าเท่ากับ 40x1 ราคาของอาหารประเภทที่ 2 มีค่าเท่ากับ เราสามารถหาราคาของอาหารประเภทที่ 3 และ 4 ได้ เราจะได้ว่าค่าใช้จ่ายทั้งหมดคือ จุดประสงค์ของสมการกำหนดเป้าหมายคือลดค่าใช้จ่ายให้น้อยที่สุด นั่นคือเราต้องการหาค่า ที่ทำให้ มีค่าต่ำสุด สมการเป้าหมายคือ
เมื่อเราได้สมการกำหนดเป้าหมายแล้วขั้นตอนไปคือหาสมการแสดงขอบข่าย ซึ่งแสดงเงื่อนไขและข้อจำกัดต่างๆ ในปัญหานี้เงื่อนไขคือ ร่างกายต้องได้รับสารอาหารแต่ละชนิดครบถ้วน เมื่อพิจารณาสารอาหารประเภทโปรตีน ถ้าเราทานอาหารประเภทที่ 1 จำนวน หน่วย เราจะได้โปรตีนเป็นจำนวน กรัม ในขณะเดียวกัน ถ้าเราทานอาหารประเภทที่ 2 จำนวน หน่วย เราจะได้โปรตีนเป็นจำนวน กรัม ดังนั้นโปรตีนทั้งหมดที่เราจะได้รับคือ เนื่องจากร่างกายต้องการโปรตีนอย่างน้อย 700 กรัม สมการแสดงขอบข่ายของโปรตีน คือ
สำหรับสมการแสดงขอบข่ายของวิตามินและธาตุเหล็กสามารถเขียนได้ดังนี้
นอกจากนี้เพื่อให้ได้ค่าตัวแปรที่สมเหตุสมผล ค่า ไม่ควรเป็นลบ นั่นคือ
ซึ่งเราจะเรียกว่า non-negativity constraints
เมื่อนำปัญหาข้างต้นมาเขียนให้อยู่ในรูปแบบโปรแกรมเชิงเส้นซึ่งประกอบไปด้วยสมการกำหนดเป้าหมายและสมการแสดงขอบข่ายสามารถเขียนได้ดังนี้
จะเห็นได้ว่าจะปัญหาสารอาหารทางโภชนาการเราสามารถเขียนให้อยู่ในรูปของปัญหาทางคณิตศาสตร์ได้ซึ่งเราจะศึกษาและวิเคราะห์หาคำตอบต่อไป
จากปัญหาสารอาหารทางโภชนาการข้างต้น เราสามารถพิจารณาอาหารประเภทต่างๆ มากขึ้นหรือพิจารณาสารอาหารเพิ่มเติม เช่น พิจารณาอาหาร 150 ประเภท และ สารอาหาร 15 ชนิด ในกรณีนี้เราต้องการตัวแปร 150 ตัวแปร และ สมการแสดงขอบข่าย 15 อสมการ นอกเหนือจาก non-negativity constraints.
รูปแบบแทนระบบของปัญหานี้เราสามารถเขียนให้อยู่ในรูปแบบอย่างย่อได้ดังนี้
กำหนดให้ m แทนจำนวนชนิดของสารอาหาร และ n แทนจำนวนประเภทของอาหาร
แทนจำนวนของสารอาหาร ที่อยู่ในอาหารประเภท
แทนปริมาณขั้นต่ำของสารอาหารชนิด ที่ร่างกายต้องการ
แทนราคาของอาหารประเภท
แทนปริมาณของอาหารประเภท ที่ร่างกายบริโภค
โดยมี เป็นสมการกำหนดเป้าหมาย
ปัญหาสารอาหารทางโภชนาการสามารถเขียนให้อยู่ในรูปของปัญหาทางคณิตศาสตร์ในรูปแบบของโปรแกรมเชิงเส้นได้ดังนี้
ตัวอย่าง Cutting stock problem
ตัวอย่างนี้พบได้ทั่วๆไปในทางอุตสาหกรรมในการสั่งซื้อสิ่งค้าแล้วนำมาตัดแบ่ง เช่นในการสั่งซื้อไม้หรือม้วนกระดาษซึ่งอาจจะซื้อมาเป็นขนาดใหญ่แล้วนำมาตัดแบ่งเป็นขนาดต่างๆ ตามความต้องการ แล้วแต่การใช้งาน เป้าหมายคือต้องตัดกระดาษอย่างไร จึงจะประหยัดทรัพยากรมากที่สุด นั่นคือใช้กระดาษน้อยที่สุดในการตัด โดยกระดาษที่ตัดเป็นขนาดต่างๆ จะต้องมีเพียงพอต่อความต้องการของลูกค้า เช่นเราสั่งซื้อกระดาษที่มีขนาดความกว้าง 100 นิ้ว ในแบบที่ 1 เราจะตัดกระดาษให้มีขนาดความกว้าง 25 นิ้วเป็นจำนวน 2 ม้วน ขนาดความกว้าง 15 นิ้วเป็นจำนวน 3 ม้วน และขนาด 5 นิ้วเป็นจำนวน 1 ม้วน ในแบบที่ 2 เราจะตัดกระดาษให้มีความกว้าง 35 นิ้วจำนวน 2 ม้วนและ ขนาด 15 นิ้วจำนวน 3 ม้วน
ปัญหาการตัดกระดาษสามารถเขียนให้อยู่ในรูปแบบโปรแกรมเชิงเส้นในรูปทั่วๆไปได้ดังนี้
กำหนดให้ m แทนจำนวนขนาดที่ต่างๆ กันทั้งหมดที่มีความกว้างตามที่ลูกค้าต้องการ
n แทนจำนวนทั้งหมดของแพทเทริน์ที่เราต้องการตัด
แทนจำนวนม้วนกระดาษที่มีความกว้างของขนาดที่ i จากการตัดแบบที่ j
แทนจำนวนม้วนกระดาษทั้งหมดของขนาดที่ i ที่ลูกค้าต้องการ
xj แทนจำนวนม้วนกระดาษที่ใช้ในการตัดแบบที่ j
โดยมี z เป็นสมการกำหนดเป้าหมาย
เราจะเห็นได้ว่าปัญหาการตัดกระดาษสามารถเขียนให้อยู่ในรูปของโปรแกรมเชิงเส้นได้ดังนี้
ในตัวอย่างต่อไปเราจะเปลี่ยนปัญหาในการผลิตสินค้าต่างๆ เขียนให้เป็นปัญหาทางคณิตศาสตร์ในรูปแบบของโปรแกรมเชิงเส้น
ตัวอย่าง ปัญหาการตัดสินใจในการผลิตสินค้า
โรงงานแห่งหนึ่งมีเครื่องจักรชนิดต่างๆ ซึ่งสามารถใช้ในการผลิตสินค้าชนิดต่างๆ ได้ อย่างไรก็ตามเครื่องจักรแต่ละชนิดมีขีดจำกัดไม่เท่ากัน และเครื่องจักรแต่ละชนิดสามารถผลิตสินค้าได้เพียงบางชนิดเท่านั้น โรงงานแห่งนี้ควรจะผลิตของแต่ละชนิดเป็นจำนวนเท่าใดเพื่อให้มี่รายได้สูงสุด โดยที่เครื่องจักรแต่ละชนิดไม่ทำงานเกินกำลัง
อย่างเช่นโรงงานแห่งหนึ่งมีเครื่องจักรอยู่ 3 ประเภท เครื่องกลึง เครื่องตัดและ เครื่องเจาะ ซึ่งใช้ในการผลิตสินค้า 4 ชนิด ในตารางแสดงจำนวนชั่วโมงที่ต้องใช้เครื่องจักรต่างๆ ผลิตสินคัาแต่ละชนิด ขีดจำกัดของการทำงานของเครื่องจักรในแต่ละวัน โรงงานควรผลิตสินค้าแต่ละชนิดเป็นจำนวนเท่าใดจึงจะมีรายได้สูงสุด
เครื่องกลึง | เครื่องตัด | เครื่องเจาะ | ราคาที่ขายได้ | |
สินค้าชนิดที่ 1 | 2 | 3 | 1 | 6500 |
สินค้าชนิดที่ 2 | 1 | 1 | 3 | 4000 |
สินค้าชนิดที่ 3 | 1 | 2 | 1 | 3000 |
ขีดจำกัดการทำงานของเครื่องจักร | 15 | 20 | 18 |
กำหนดให้ แทนจำนวนของสินค้าของชนิด i ที่ควรผลิต
ในกรณีที่มีเครื่องจักรทั้งหมด m ชนิด และต้องการผลิตสินค้าทั้งหมด n ประเภท
ถ้า แทนจำนวนของสินค้าประเภท j ควรจะผลิต
[/tex]แทนจำนวนชั่วโมงของเครื่องจักรที่ i ที่ใช้ในการผลิตสินค้าประเภท j
แทนจำนวนชั่วโมงที่เป็นขีดจำกัดของเครื่องจักร i
แทนราคาต่อหน่วยในการผลิตสินค้าประเภท j
เป้าหมายคือเราต้องการหาจำนวนการผลิตของสินค้าแต่ละประเภทโดยให้ได้รายได้มากที่สุดและจำนวนชั่วโมงของเครื่องจักรที่ใช้ในการผลิตแต่ละเครื่องไม่เกินขีดจำกัด
เราจะเห็นว่า คือรายได้ที่ได้จากการผลิตสินค้าประเภท j คือจำนวนชั่วโมงที่ใช้ในการผลิตสินค้าประเภท j ของเครื่องจักร i
ตัวอย่าง ปัญหาการขนส่ง (transportation problem)
กำหนดให้มีโรงงาน 2 โรงงานที่มีกำลังการผลิต 230 หน่วย และ 150 หน่วย ต้องการที่จะส่งสินค้าไปยังร้านค้าย่อย 4 กลุ่ม โดยร้านค้าแต่ละร้านมีความต้องการสินค้า 80, 100, 60, และ 130 ตามลำดับ โรงงานแห่งนี้ควรจะจัดส่งสินค้าอย่างไรโดยให้เสียค่าใช้จ่ายน้อยที่สุด โดยที่สามารถส่งของให้ร้านค้าย่อยทุกๆร้านได้ตามความต้องการ ค่าขนส่งจากโรงงานไปยังร้านค้าต่างๆ ได้แสดงในตารางข้างล่างนี้
ถึงร้านค้า | |||||
1 | 2 | 3 | 4 | ||
จาก โรงงาน | 1 | 65 | 40 | 30 | 15 |
2 | 10 | 35 | 40 | 60 |
กำหนดให้ แทนจำนวนสินค้าที่ส่งจากโรงงาน i ถึงร้านค้า j ตัวอย่างเช่น แทนจำนวนสินค้าที่ส่งจากโรงงาน 1 ไปยังร้านค้า 1
สมการเป้าหมายซึ่งคือค่าใช้จ่ายทั้งหมดที่ใช้ในการขนส่ง สามารถเขียนได้ดังนี้
ในการจัดส่งสินค้าจากโรงงานไปยังร้านค้าต่างๆ ปริมาณการขนส่งสินค้าจากโรงงานแต่ละแห่งไม่ควรเกินกำลังการผลิต เราจะเห็นได้ว่า
คือจำนวนสินค้าที่โรงงานที่ 1 ส่งไปยังร้านค้าต่างๆ เนื่องจากกำลังการผลิตของโรงงานนี้เท่ากับ 230 หน่วย ดังนั้น สมการแสดงขอบข่ายของโรงงาน 1 คือ
สมการแสดงขอบข่ายของโรงงานที่ 2 คือ
นอกจากนี้ข้อกำหนดในการจัดส่งสินค้าคือร้านค้าแต่ละร้านต้องได้รับสินค้าครบตามความต้องการ สำหรับร้านค้าที่ 1 ร้านค้าต้องการสินค้า 80 หน่วย ดังนั้นจำนวนที่ได้รับต้องไม่น้อยกว่า 80 หน่วย นั่นคือ
นอกจากนี้จำนวนสินค้าที่ส่งจากโรงงานไปยังร้านค้าต่างๆ ต้องไม่เป็นลบ ดังนั้น
ดังนั้นเราสามารถเขียนโปรแกรมเชิงเส้นของปัญหาข้างต้นได้ดังต่อไปนี้
[Unparseable or potentially dangerous latex formula. Error 6 ]
เมื่อจัดตั้งรูปแบบแทนระบบของปัญหาให้เป็นรูปแบบโปรแกรมเชิงเส้นได้แล้ว เราจะมาหาผลลัพธ์ของปัญหาเหล่านี้
การหาผลลัพธ์ของรูปแบบแทนระบบของปัญหา (Model Solution)
หลังจากสร้างรูปแบบของโปรแกรมเชิงเส้น การแก้ปัญหาโปรแกรมเชิงเส้นสามารถทำได้หลายวิธีในที่นี้จะกล่าวถึง วิธีกราฟ และวิธีการของ simplex
โดยมากระบบของปัญหาทางการโปรแกรมเชิงเส้น จะมีตัวแปรซึ่งเป็นองค์ประกอบของระบบจำนวนมากซึ่งมีซับซ้อนมาก การหาผลลัพธ์จึงมักจะใช้คอมพิวเตอร์ช่วยในการคำนวน ในปัจจุบันได้มีการพัฒนาโปรแกรมคอมพิวเตอร์สำเร็จรูปเพื่อใช้ในการแก้ปัญหาโปรแกรมเชิงเส้น เช่น Lindo, LPSolver อย่างไรก็ตามเราจำเป็นต้องเรียนรู้ถึงลักษณะของปัญหาง่ายๆ ให้เข้าใจเป็นขั้นตอนเพื่อความเข้าใจในการแก้ปัญหาซับซ้อนต่อไป สำหรับปัญหาที่มีเพียง 2 ตัวแปร วิธีกราฟเป็นวิธีง่ายๆ ซึ่งสามารถจะหาคำตอบ
วิธีกราฟ (Graphical Method)
วิธีกราฟนี้เป็นวิธีที่เข้าใจได้ง่ายสำหรับปัญหาที่มี 1 หรือ 2 ตัวแปร
ตัวอย่าง พิจารณาโปรแกรมเชิงเส้นต่อไปนี้
การแก้ปัญหาโปรแกรมเชิงเส้นโดยวิธีกราฟมีขั้นตอนต่อไปนี้
1. วาดกราฟของสมการแสดงขอบข่ายทั้งหมด (สมการข้อจำกัด และ non-negativity constraints)
2. ระบุพื้นที่ที่เป็นสอดคล้องกับข้อจำกัดทั้งหมด นั่นคือคำตอบของสมการแสดงขอบข่ายทั้งหมดอยู่บนพื้นที่นี้พื้นที่นี้เรียกว่า (feasible region)
เราจะเห็นได้ว่าค่าของตัวแปร และ ที่อยู่ในพื้นที่ที่แรงเงามีค่าที่สอดคล้องกับข้อจำกัดที่กำหนด
3. วาดกราฟของสมการกำหนดเป้าหมายโดยการกำหนดให้สมการกำหนดเป้าหมายมีค่าต่างๆ พร้อมทั้งหาทิศทางการเปลี่ยนค่าของสมการกำหนดเป้าหมาย
สมการ เป็นเส้นตรงโดยที่จุดต่างๆ บนเส้นตรงจะให้ค่า z เดียวกัน เมื่อกำหนดค่า z ค่าใหม่สมการที่ได้จะเป็นเส้นตรงที่ขนานกับเส้นเดิม จากกราฟข้างต้นจุด ทุกๆจุดที่อยู่บนเส้นตรง จะมีค่าของสมการกำหนดเป้าหมายเท่ากับ 2 ในขณะเดียวกันสำหรับจุด ที่อยู่บนเส้นตรง จะมีค่าของสมการกำหนดเป้าหมายเท่ากับ 5 เราจะเห็นได้ว่าเมื่อค่าของสมการกำหนดเป้าหมายเพิ่มขึ้นเรื่อยๆ เส้นตรงจะเลื่อนขึ้นไปทางขวามือ ดังแสดงในกราฟ
4. ในการหาคำตอบของโปรแกรมเชิงเส้นสามารถทำได้โดยการเปลี่ยนค่าของสมการกำหนดเป้าหมาย ถ้าสมการกำหนดเป้าหมายต้องการหาค่าสูงสุด คำตอบของโปรแกรมเชิงเส้นข้างต้นคือค่าของตัวแปร และ x2 ที่ทำให้ค่าของสมการกำหนดเป้าหมายมีค่าสูงสุดโดยที่ค่าของตัวแปรนั้นจะต้องอยู่ในพื้นที่ที่แรงเงาด้วย
จากกราฟข้างต้น ในการหาค่าสูงสุดของสมการกำหนดเป้าหมายทำได้โดยเลื่อนเส้นตรงไปทางขวาจนสุดเขตพื้นที่ที่แรงเงา จะเห็นได้ว่า ค่าของ และ ที่ทำให้ค่าของสมการกำหนดเป้าหมายมีค่าสูงสุดคือ โดยที่ค่าของสมการกำหนดเป้าหมายมีค่าเท่ากับ 22/3 ถ้าเราต้องการหาค่าต่ำสุดของสมการกำหนดเป้าหมายทำได้โดยเลื่อนเส้นตรงไปทางซ้ายจนสุดพื้นที่แรงเงา ค่าของ และ ที่ทำให้ค่าของสมการกำหนดเป้าหมายมีค่าต่ำสุดคือ
เนื่องจากสมการแสดงขอบข่ายของแต่ละสมการเป็นเส้นตรงจะทำให้พื้นที่ของจุดที่สอดคล้องกับข้อจำกัดทั้งหมด เป็น polygon จากตัวอย่างข้างต้นพบว่าค่าของ และ ที่ทำให้สมการกำหนดเป้าหมายมีค่าที่ดีที่สุดจะอยู่ที่จุดยอดจุดใดจุดหนึ่งของสมการแสดงขอบข่ายเหล่านั้น จากข้อสังเกตุนี้เราสามารถแก้โปรแกรมเชิงเส้นได้โดยหาจุดยอดทุกๆ จุดบนพื้นที่ที่แรงเงาหาค่าของสมการกำหนดเป้าหมายของจุดเหล่านั้น และเปรียบเทียบหาคำตอบ จากตัวอย่างข้างต้นจะได้ว่า
จุดยอด | ค่าของสมการกำหนดเป้าหมาย |
(0,0) | 0 |
(0,1) | 4 |
(2/3, 5/3) | 22/3* |
(2,1) | 6 |
(3,0) | 3 |
จะเห็นได้ว่าในกรณีนี้ค่าของสมการกำหนดเป้าหมายมีค่าสูงสุดเท่ากับ 8 เมื่อ และ หรือ และ จากกราฟเราจะเห็นได้ว่าคำตอบทั้งหมดคือจุดทุกๆจุดของ x1 และ x2 ที่อยู่บนเส้นตรง โดยที่ มีค่าอยู่ระหว่าง 2/3 และ 2
ตัวอย่าง พิจารณาโปรแกรมเชิงเส้นต่อไปนี้
จากกราฟจะเห็นได้ว่าพื้นที่ของอยู่สอดคล้องกับข้อจำกัดทั้งหมดมีขอบเขตไม่จำกัด (unbounded region) นอกจากนี้ค่าของสมการกำหนดเป้าหมายซึ่งเป็นเส้นตรงที่มีค่าเพิ่มขึ้น เส้นตรงจะเลื่อนไปทางขวามือ เราจะเห็นว่าค่าของสมการกำหนดเป้าหมายเพิ่มขึ้นไปเรื่อยๆไม่มีขีดจำกัด นั่นคือ ผลลัพธ์ไม่มีขอบเขตจำกัด ถ้าต้องการหาค่าสมการกำหนดเป้าหมายที่มีค่าต่ำสุด ค่าของสมการกำหนดเป้าหมายมีค่าต่ำลงเมื่อเส้นตรงเลื่อนไปทางซ้ายมือ เมื่อเลื่อนเส้นตรงไปทางซ้ายมือสุดขอบพื้นที่ ค่าของสมการกำหนดเป้าหมายมีค่าเท่ากับ 0 ที่จุดยอด
ข้อจำกัดของวิธีกราฟคือสามารถใช้กับปัญหาที่มีเพียงหนึ่งหรือสองตัวแปรเท่านั้น แต่กราฟสามารถทำให้เราเห็นภาพชัดเจนว่าส่วนใดเป็นพื้นที่ที่สอดคล้องกับข้อจำกัดทั้งหมด นั่นคือจุดทุกๆจุดในพื้นที่เหล่านี้เป็นคำตอบของสมการแสดงขอบข่าย ซึ่งกราฟสามารถบอกให้เราทราบว่าปัญหาโปรงแกรมเชิงเส้นไม่มีคำตอบถ้ากราฟไม่มีพื้นที่ที่สอดคล้องกับข้อจำกัดทั้งหมด นอกจะนี้พื้นที่ที่สอดคล้องกับข้อจำกัดทั้งหมดมีขอบเขตจำกัด คำตอบที่ให้ค่าของสมการกำหนดเป้าหมายที่ดีที่สุด (อาจจะเป็นค่าต่ำสุดหรือสูงสุดแล้วแต่จุดประสงค์ของปัญหา) จะอยู่ที่จุดยอด
ในกรณีพื้นที่ที่สอดคล้องกับข้อจำกัดทั้งหมดมีขอบเขตไม่จำกัด เราไม่สามารถสรุปได้ว่าค่าของสมการแสดงขอบข่ายมีขอบเขตไม่จำกัดหรือ ค่าที่ดีที่สุดของสมการกำหนดเป้าหมายจะอยู่ที่จุดยอด ดังตัวอย่างข้างต้น
จากการวิเคราะห์ผลจากเรขาคณิตที่ได้จากกราฟ ทำให้พัฒนาวิธีการทางพีชคณิตเพื่อนำมาใช้ในการหาคำตอบของปัญหาที่มีมากกว่า 2 ตัวแปร วิธีการแก้ปัญหาทางโปรแกรมเชิงเส้นมีหลายวิธีแต่ที่นิยมใช้กันมากคือ Simplex method
Simplex Method
วิธีนี้มีการพัฒนาจากวิธีทางพีชคณิตที่อาศัยทฤษฎีของเมทริกซ์เข้าร่วมจัดรูปแบบปัญหาให้มีระบบยิ่งขึ้น ช่วยให้ลังเกตความเปลี่ยนแปลงตัวแปรได้ง่ายและสามารถเข้าใจแนวทางที่ตัวแปรแต่ละตัวจะเปลี่ยนไปอย่างมีเหตุมีผล วิธีดังกล่าวจะเริ่มต้นการเปลี่ยนตัวแปรต่างๆให้มีผลต่อสมการกำหนดเป้าหมายโดยมีผลแนวโน้มสู้เป้าหมายในทางที่เร็วที่สุด การจัดรูปสมการเข้าเป็นตารางแล้วดำเนินการตามขั้นตอนที่ถูกต้องจะต้องทำให้ได้ผลลัพธ์ตามเป้าหมาย ผลลัพธ์ที่ดีที่สุดอาจจะมีได้หลายๆ คำตอบ
ขั้นตอนของวิธีการ simplex method สามารถสรุปง่ายๆ ได้ดังนี้
1. ขั้นตอนเริ่มต้น เริ่มจากการหาคำตอบเริ่มต้นนั้นคือคำตอบที่อยู่ในพื้นที่ที่เป็นคำตอบของสมการแสดงขอบข่ายคำนวนหาค่าของสมการกำหนดเป้าหมาย
2. ขั้นตอนทำซ้ำ เลื่อนไปสู่จุดยอดที่อยู่ติดกันบนพื้นที่ที่สอดคล้องกับข้อจำกัดทั้งหมด ถ้าค่าของสมการกำหนดเป้าหมายให้ผลลัพธ์ที่ดีกว่า (ทำซ้ำข้อ 2 จนกว่าเงื่อนไขในข้อ 3 จะเป็นจริง)
3. ขั้นตอนการตรวจสอบค่าที่ดีสุด จุดยอดที่ได้จะเป็นคำตอบถ้าไม่มีจุดยอดใดๆที่ติดกันบนพื้นที่ที่สอดคล้องกับข้อจำกัดทั้งหมดที่ให้ผลลัพธ์ที่ดีกว่า
ขั้นตอนเริ่มต้น
ในแก้ปัญหาโปรแกรมเชิงเส้นสำหรับ simplex method ก่อนอื่นเราต้องจัดรูปแบบของปัญหาให้อยู่ในรูปแบบมาตราฐานของโปรแกรมเชิงเส้น ซึ่งมีลักษณะดังต่อไปนี้
การเปลี่ยนรูปแบบดั้งเดิมให้เป็นรูปแบบมาตราฐานของโปรแกรมเชิงเส้นสามารถทำได้ดังนี้
1. ถ้าปัญหาต้องการที่จะสมการกำหนดเป้าหมายมีค่าสูงสุด
เราสามารถเปลี่ยนให้เป็นปัญหาที่มีสมการกำหนดเป้าหมายต่ำสุดได้โดย
เช่น
2. ในกรณีที่สมการแสดงขอบข่ายอยู่ในรูปของเครื่องหมาย เช่น
เราสามารถเปลี่ยนให้อยู่ในรูปของสมการได้โดย
โดยที่ตัวแปรที่เพิ่มขึ้นเราเรียกว่าตัวแปรขาด หรือ slack variable
เช่น
3. ในกรณีที่สมการแสดงขอบข่ายอยู่ในรูปของเครื่องหมาย เช่น
เราสามารถเปลี่ยนให้อยู่ในรูปของสมการได้โดย
โดยที่ตัวแปร เรียกว่าตัวแปรเกิน หรือ surplus variable และ เรียกว่าตัวแปรเทียม artificial variable เช่น
4. ในกรณีที่ เราสามารถเปลี่ยนให้อยู่ในรูปแบบเพิ่มเติมโดยกำหนดให้
5. ในกรณีที่ ไม่มีข้อจำกัด นั่นคือ สามารถเป็นทั้งบวกและลบรวมทั้งศูนย์ เราสามารถเปลี่ยนโดยกำหนดให้ และ
6. ในกรณีที่ทางซ้ายมือเป็นค่าสัมบูรณ์ เราสามารถเปลี่ยนให้อยู่ในรูปของ และ
ตัวอย่างเช่น
โดยที่ เป็นตัวแปรขาด เป็นตัวแปรเกินและ เป็นตัวแปรเทียม
ขั้นตอนเริ่มต้นของวิธี simplex method เริ่มจากหาคำตอบหรือผลลัพธ์เริ่มต้นที่อยู่ในพื้นที่ที่สอดคล้องกับข้อจำกัด ตัวอย่างเช่นพิจารณาโปรแกรมเชิงเส้นต่อไปนี้
จากตัวอย่างข้างต้นเราจะเห็นได้ว่า เป็นผลลัพธ์เริ่มต้น ตัวแปรแบ่งได้ออกเป็นสองประเภทคือ ตัวแปรมูลฐาน หรือ basic variables ซึ่งเป็นตัวแปรที่ไม่ใช่ศูนย์ในผลลัพธ์เริ่มต้น และตัวแปรที่ไม่เป็นมูลฐาน หรือ non-basic variables นั่นคือตัวแปรที่มีค่าเท่ากับศูนย์ในผลลัพธ์เริ่มต้น
จะเห็นได้ว่าการเพิ่มตัวแปรขาดและตัวแปรเกิน ช่วยให้หาคำตอบเริ่มต้นได้ง่ายขี้น โดยกำหนดให้ตัวแปรดั้งเดิมป็นตัวแปรไม่เป็นมูลฐาน และให้ตัวแปรเพิ่มเป็นตัวแปรมูลฐาน หลังจากได้คำตอบเริ่มต้น เราจะดำเนินการขั้นตอนที่ 2 นั่นคือ ขั้นตอนทำซ้ำ
PS. ช่วยเข้าปัยAddเปนเพิ่ลหน่อยดิ
7 ความคิดเห็น
ยากจังเลย
PS. ดีดี
กำลังเรียนอยู่พอดีเลยอะ จะสอบแล้วด้วย101
อีกอย่างยังไม่ได้เรียนด้วย~ >\\\\\^;;
PS. เงยหน้าขึ้นรับแสงตะวัน แล้วคุณจะไม่มีวันพบกับเงามืด
ยาก ๆเรียนแล้วไม่เข้าหัวเลยง่า
Thank you very much ^^
PS. ยอดนักสืบ ม.ปลายตะวันออก VS เทพเจ้าแห่งโลกตะวันออก Forever...D2B
เรียนแล้ว
มาเรียนที่มหาวิทยาลัยเกริก สาขาการจัดการโลจิสติกส์สิค่ะ ที่นี่อาจารย์และพี่ๆๆดูแลกันมากค่ะ กำลังเป็นที่ต้องการของตลาดมากค่ะ จบแล้วรับรองค่ะว่ามีงานทำแซงหน้าสาขาอื่นกันเลย และกำลังจะมีสาขาน้องใหม่เปิดค่ะคือสาขาการบิน ลองมาเรียนกันน่ะค่ะ รับลองค่ะว่าจะไม่ผิดหวัง พี่ๆโลจิสติกส์รออยู่ค่ะ
โทรศัพท์: 02-552-3500-9, 02-970-5820 email :http://www.krirk.ac.th/
รายชื่อผู้ถูกใจความเห็นนี้ คน
แจ้งลบความคิดเห็น
คุณต้องการจะลบความคิดเห็นนี้หรือไม่ ?