วิชาการ.คอม - โปรแกรมเชิงเส้น (Linear Programming) (การหาผลลัพธ์ของรูปแบบแทนระบบของปัญหา (Model Solution))

โปรแกรมเชิงเส้น (Linear Programming)

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

ผู้เขียน: ดร. ระวี สุวรรณเดโชไช ชมแล้ว: 29,788 ครั้ง

post ครั้งแรก: Sun 8 July 2007, 8:48 pm ปรับปรุงล่าสุด: Wed 18 July 2007, 11:33 pm

อยู่ในส่วน: เขียนโปรแกรม

สารบัญ

หน้า : 1 บทนำ
หน้า : 2 รูปแบบแทนระบบทางคณิตศาสตร์ของโปรแกรมเชิงเส้น
หน้า : 3 การจัดตั้งรูปแบบแทนระบบของปัญหา (Model Formulation)
หน้า : 4 การหาผลลัพธ์ของรูปแบบแทนระบบของปัญหา (Model Solution)
หน้า : 5 Simplex Method

หน้าที่ 4 - การหาผลลัพธ์ของรูปแบบแทนระบบของปัญหา (Model Solution)

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

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

วิธีกราฟ (Graphical Method)
วิธีกราฟนี้เป็นวิธีที่เข้าใจได้ง่ายสำหรับปัญหาที่มี 1 หรือ 2 ตัวแปร

ตัวอย่าง พิจารณาโปรแกรมเชิงเส้นต่อไปนี้

$\displaystyle{\begin{array}{rc}\textrm{Max}&z=x_1+4x_2\ \textrm{Subject to}&{\begin{array}{rcl}x_1+x_2&\leq&3\x_1+2x_2&\leq&4\-x_1+x_2&\geq&1\x_1\geq0,x_2&\geq&0\end{array}}\end{array}}$

การแก้ปัญหาโปรแกรมเชิงเส้นโดยวิธีกราฟมีขั้นตอนต่อไปนี้
1. วาดกราฟของสมการแสดงขอบข่ายทั้งหมด (สมการข้อจำกัด และ non-negativity constraints)
2. ระบุพื้นที่ที่เป็นสอดคล้องกับข้อจำกัดทั้งหมด นั่นคือคำตอบของสมการแสดงขอบข่ายทั้งหมดอยู่บนพื้นที่นี้พื้นที่นี้เรียกว่า (feasible region)

45307

เราจะเห็นได้ว่าค่าของตัวแปร x_1

และ

ที่อยู่ในพื้นที่ที่แรงเงามีค่าที่สอดคล้องกับข้อจำกัดที่กำหนด

3. วาดกราฟของสมการกำหนดเป้าหมายโดยการกำหนดให้สมการกำหนดเป้าหมายมีค่าต่างๆ พร้อมทั้งหาทิศทางการเปลี่ยนค่าของสมการกำหนดเป้าหมาย

45308

สมการ

เป็นเส้นตรงโดยที่จุดต่างๆ บนเส้นตรงจะให้ค่า z เดียวกัน เมื่อกำหนดค่า z ค่าใหม่สมการที่ได้จะเป็นเส้นตรงที่ขนานกับเส้นเดิม จากกราฟข้างต้นจุด (x_1,x_2)

ทุกๆจุดที่อยู่บนเส้นตรง x_1+4x_2=2

จะมีค่าของสมการกำหนดเป้าหมายเท่ากับ 2 ในขณะเดียวกันสำหรับจุด (x_1,x_2)

ที่อยู่บนเส้นตรง x_1+4x_2=5

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

4. ในการหาคำตอบของโปรแกรมเชิงเส้นสามารถทำได้โดยการเปลี่ยนค่าของสมการกำหนดเป้าหมาย ถ้าสมการกำหนดเป้าหมายต้องการหาค่าสูงสุด คำตอบของโปรแกรมเชิงเส้นข้างต้นคือค่าของตัวแปร x_1

และ x2

ที่ทำให้ค่าของสมการกำหนดเป้าหมายมีค่าสูงสุดโดยที่ค่าของตัวแปรนั้นจะต้องอยู่ในพื้นที่ที่แรงเงาด้วย

45309

จากกราฟข้างต้น ในการหาค่าสูงสุดของสมการกำหนดเป้าหมายทำได้โดยเลื่อนเส้นตรงไปทางขวาจนสุดเขตพื้นที่ที่แรงเงา จะเห็นได้ว่า ค่าของ x_1

และ

ที่ทำให้ค่าของสมการกำหนดเป้าหมายมีค่าสูงสุดคือ x_1=2/3,x_2=5/3

โดยที่ค่าของสมการกำหนดเป้าหมายมีค่าเท่ากับ 22/3 ถ้าเราต้องการหาค่าต่ำสุดของสมการกำหนดเป้าหมายทำได้โดยเลื่อนเส้นตรงไปทางซ้ายจนสุดพื้นที่แรงเงา ค่าของ x_1

และ

ที่ทำให้ค่าของสมการกำหนดเป้าหมายมีค่าต่ำสุดคือ x_1=0,x_2=0

เนื่องจากสมการแสดงขอบข่ายของแต่ละสมการเป็นเส้นตรงจะทำให้พื้นที่ของจุดที่สอดคล้องกับข้อจำกัดทั้งหมด เป็น polygon จากตัวอย่างข้างต้นพบว่าค่าของ x_1

และ

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

45312

จุดยอด	ค่าของสมการกำหนดเป้าหมาย
(0,0)	0
(0,1)	4
(2/3, 5/3)	22/3*
(2,1)	6
(3,0)	3

จะเห็นได้ว่าในกรณีนี้ค่าของสมการกำหนดเป้าหมายมีค่าสูงสุดเท่ากับ 8 เมื่อ x_1=2/3

และ

หรือ

และ

จากกราฟเราจะเห็นได้ว่าคำตอบทั้งหมดคือจุดทุกๆจุดของ x1 x_1

และ x2

ที่อยู่บนเส้นตรง 2x_1+4x_2=8

โดยที่

มีค่าอยู่ระหว่าง 2/3 และ 2

ตัวอย่าง พิจารณาโปรแกรมเชิงเส้นต่อไปนี้

$\displaystyle{\begin{array}{rc}\textrm{Max}&z=x_1+4x_2\ \textrm{Subject to}&{\begin{array}{rcl}-3x_1+x_2&\leq&3\-x_1+x_2&\geq&-2\-2x_1+x_2&\leq&5\x_1\geq0,x_2&\geq&0\end{array}}\end{array}}$

45313

จากกราฟจะเห็นได้ว่าพื้นที่ของอยู่สอดคล้องกับข้อจำกัดทั้งหมดมีขอบเขตไม่จำกัด (unbounded region) นอกจากนี้ค่าของสมการกำหนดเป้าหมายซึ่งเป็นเส้นตรงที่มีค่าเพิ่มขึ้น เส้นตรงจะเลื่อนไปทางขวามือ เราจะเห็นว่าค่าของสมการกำหนดเป้าหมายเพิ่มขึ้นไปเรื่อยๆไม่มีขีดจำกัด นั่นคือ ผลลัพธ์ไม่มีขอบเขตจำกัด ถ้าต้องการหาค่าสมการกำหนดเป้าหมายที่มีค่าต่ำสุด ค่าของสมการกำหนดเป้าหมายมีค่าต่ำลงเมื่อเส้นตรงเลื่อนไปทางซ้ายมือ เมื่อเลื่อนเส้นตรงไปทางซ้ายมือสุดขอบพื้นที่ ค่าของสมการกำหนดเป้าหมายมีค่าเท่ากับ 0 ที่จุดยอด (x_1,x_2)=(0,0)

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

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

จากการวิเคราะห์ผลจากเรขาคณิตที่ได้จากกราฟ ทำให้พัฒนาวิธีการทางพีชคณิตเพื่อนำมาใช้ในการหาคำตอบของปัญหาที่มีมากกว่า 2 ตัวแปร วิธีการแก้ปัญหาทางโปรแกรมเชิงเส้นมีหลายวิธีแต่ที่นิยมใช้กันมากคือ Simplex method

<<< หน้าก่อนนี้ (หน้า 3)

หน้าถัดไป (หน้า 5) >>>

^*หมายเหตุ งานเขียนชิ้นนี้ ได้รับการคุ้มครองสิทธิตามพระราชบัญญัติคุ้มครองสิทธิทางปัญญา โดยลิขสิทธิเป็นของผู้เขียน ที่ให้เกียรตินำเผยแพร่ผ่าน วิชาการ.คอม เรามีความยินดีและอนุญาตให้ทำซ้ำหรือเผยแพร่ต่อเพื่อประโยชน์ทางการศึกษาเท่านั้น กรุณาให้เกียรติผู้เขียน โดยอ้างชื่อผู้เขียนและ วิชาการ.คอม (www.vcharkarn.com) ทุกครั้งที่ทำการเผยแพร่ต่อ ห้ามนำส่วนหนึ่งส่วนใดไปเผยแพร่ต่อในสื่อที่เอื้อประโยชน์ทางธุรกิจก่อนได้รับอนุญาต ขอขอบคุณที่ร่วมกันช่วยสร้างให้สังคมไทยเป็นสังคมแห่งปัญญา

จำนวน 1 ความเห็น, หน้า่ | -1-