วิชาการ.คอม - โปรแกรมเชิงเส้น (Linear Programming) (Simplex Method)

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

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

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

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

หน้าที่ 5 - Simplex Method

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

ขั้นตอนของวิธีการ simplex method สามารถสรุปง่ายๆ ได้ดังนี้
1. ขั้นตอนเริ่มต้น เริ่มจากการหาคำตอบเริ่มต้นนั้นคือคำตอบที่อยู่ในพื้นที่ที่เป็นคำตอบของสมการแสดงขอบข่ายคำนวนหาค่าของสมการกำหนดเป้าหมาย
2. ขั้นตอนทำซ้ำ เลื่อนไปสู่จุดยอดที่อยู่ติดกันบนพื้นที่ที่สอดคล้องกับข้อจำกัดทั้งหมด ถ้าค่าของสมการกำหนดเป้าหมายให้ผลลัพธ์ที่ดีกว่า (ทำซ้ำข้อ 2 จนกว่าเงื่อนไขในข้อ 3 จะเป็นจริง)
3. ขั้นตอนการตรวจสอบค่าที่ดีสุด จุดยอดที่ได้จะเป็นคำตอบถ้าไม่มีจุดยอดใดๆที่ติดกันบนพื้นที่ที่สอดคล้องกับข้อจำกัดทั้งหมดที่ให้ผลลัพธ์ที่ดีกว่า

ขั้นตอนเริ่มต้น

ในแก้ปัญหาโปรแกรมเชิงเส้นสำหรับ simplex method ก่อนอื่นเราต้องจัดรูปแบบของปัญหาให้อยู่ในรูปแบบมาตราฐานของโปรแกรมเชิงเส้น ซึ่งมีลักษณะดังต่อไปนี้

$\displaystyle{\begin{array}{rc}\textrm{Min}&z=c_1x_1+c_2x_2+\ldots+c_nx_n\ \textrm{Subject to}&{\begin{array}{rcl}a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n&=&b_1\a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n&=&b_2\ \vdots \qquad\qquad\qquad& & \vdots \a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n&=&b_m\x_1\geq0,x_2\geq0,\ldots,x_n&\geq&0 \end{array}}\end{array}}$

การเปลี่ยนรูปแบบดั้งเดิมให้เป็นรูปแบบมาตราฐานของโปรแกรมเชิงเส้นสามารถทำได้ดังนี้

1. ถ้าปัญหาต้องการที่จะสมการกำหนดเป้าหมายมีค่าสูงสุด

$\displaystyle{\textrm{Max}\,z=\sum_jc_jx_j}$
เราสามารถเปลี่ยนให้เป็นปัญหาที่มีสมการกำหนดเป้าหมายต่ำสุดได้โดย

$\displaystyle{\textrm{Min}\,z’=-\textrm{Max}\,z=-\sum_jc_jx_j}$

เช่น $\textrm{Max}\,2x_1-3x_2+4x_3\Rightarrow \textrm{Min}\,-2x_1+3x_2-4x_3$

2. ในกรณีที่สมการแสดงขอบข่ายอยู่ในรูปของเครื่องหมาย $\leq$ เช่น
$a_{i1}x_1+a_{i2}x_2+\ldots +a_{in}x_n\leq b_i$
เราสามารถเปลี่ยนให้อยู่ในรูปของสมการได้โดย $a_{i1}x_1+a_{i2}x_2+\ldots +a_{in}x_n+x_{n+1}=b_i$
โดยที่ตัวแปรที่เพิ่มขึ้นเราเรียกว่าตัวแปรขาด หรือ slack variable
เช่น $2x_1-3x_2+4x_3\leq 3\rightarrow 2x_1-3x_2+4x_3+x_4=3$

3. ในกรณีที่สมการแสดงขอบข่ายอยู่ในรูปของเครื่องหมาย $\geq$ เช่น

$a_{i1}x_1+a_{i2}x_2+\ldots +a_{in}x_n\geq b_i$
เราสามารถเปลี่ยนให้อยู่ในรูปของสมการได้โดย

$a_{i1}x_1+a_{i2}x_2+\ldots +a_{in}x_n-x_{n+1}+x_{n+2}=b_i$
โดยที่ตัวแปร $x_{n+1}$ เรียกว่าตัวแปรเกิน หรือ surplus variable และ $x_{n+2}$ เรียกว่าตัวแปรเทียม artificial variable เช่น $2x_1-3x_2+4x_3\geq3\rightarrow 2x_1-3x_2+4x_3-x_4+x_5=3$

4. ในกรณีที่ $x_i\leq 0$ เราสามารถเปลี่ยนให้อยู่ในรูปแบบเพิ่มเติมโดยกำหนดให้ $\displaystyle{x_i^\prime =-x_i,x_i^\prime \geq 0}$

5. ในกรณีที่ x_i

ไม่มีข้อจำกัด นั่นคือ x_i

สามารถเป็นทั้งบวกและลบรวมทั้งศูนย์ เราสามารถเปลี่ยนโดยกำหนดให้ $x_i=x_i^\prime - x_i^{\prime\prime} , x_i\geq 0$ และ $-x_i\geq 0$

6. ในกรณีที่ทางซ้ายมือเป็นค่าสัมบูรณ์ $|a_1x_1+a_2x_2|\leq b$ เราสามารถเปลี่ยนให้อยู่ในรูปของ $a_1x_1+a_2x_2\leq b$ และ $-a_1x_1-a_2x_2\leq b$

ตัวอย่างเช่น

$\displaystyle{\begin{array}{rcl}{\begin{array}{rc}\textrm{Max}&2x_1+3x_2-4x_3\textrm{Subject to}&2x_1+x_2\geq5\&x_1-x_2-x_3\leq3\&x_1+x_3=4\&x_1\geq0,x_2\leq0,x_3\end{array}}&\Rightarrow&{\begin{array}{rc}\textrm{Min}&-2x_1-3x_2+4(x^{\prime}_3-x^{\prime\prime}_3)\textrm{Subject to}&2x_1+x_2-x_4+x_5=5\&x_1-x_2-(x^\prime_3-x^{\prime\prime}_3)+x_6=3\&x_1\geq0,x_2\geq0,x^\prime_3\geq0,x^{\prime\prime}_3\geq0,\&x_4\geq0,x_5\geq0,x_6\geq0\end{array}}\end{array}}$

โดยที่ x_4

เป็นตัวแปรขาด x_5

เป็นตัวแปรเกินและ x_6

เป็นตัวแปรเทียม

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

$\displaystyle{\begin{array}{rcl}{\begin{array}{rc}\textrm{Min}&-3x_1-x_2-3x_3\textrm{Subject to}&2x_1+x_2+x_3\geq2\&x_1+2x_2+x_3\leq5\&2x_1+2x_3+x_3\leq6\&x_1\geq0,x_2\leq0,x_3\leq0\end{array}}&\Rightarrow&{\begin{array}{rc}\textrm{Min}&z\textrm{Subject to}&{\begin{array}{rcl}z=3x_1+x_2+3x_3&=&0x_1+x_2+x_3+x_4&=&2\x_1+2x_2+x_3\qquad+x_5&=&5x_1+2x_2+x_3\qquad\qquad+x_6&=&6\x_1\geq0,x_2\geq0,x_3\geq0,&&\x_4\geq0,x_5\geq0,x_6\geq0&&\end{array}} \end{array}}\end{array}}$

จากตัวอย่างข้างต้นเราจะเห็นได้ว่า x_4=2,x_5=5,x_6=6,x_1=x_2=x_3=0

เป็นผลลัพธ์เริ่มต้น ตัวแปรแบ่งได้ออกเป็นสองประเภทคือ ตัวแปรมูลฐาน หรือ basic variables ซึ่งเป็นตัวแปรที่ไม่ใช่ศูนย์ในผลลัพธ์เริ่มต้น (x_4,x_5,x_6)

และตัวแปรที่ไม่เป็นมูลฐาน หรือ non-basic variables นั่นคือตัวแปรที่มีค่าเท่ากับศูนย์ในผลลัพธ์เริ่มต้น (x_1,x_2.x_3)

จะเห็นได้ว่าการเพิ่มตัวแปรขาดและตัวแปรเกิน ช่วยให้หาคำตอบเริ่มต้นได้ง่ายขี้น โดยกำหนดให้ตัวแปรดั้งเดิมป็นตัวแปรไม่เป็นมูลฐาน และให้ตัวแปรเพิ่มเป็นตัวแปรมูลฐาน หลังจากได้คำตอบเริ่มต้น เราจะดำเนินการขั้นตอนที่ 2 นั่นคือ ขั้นตอนทำซ้ำ

(กำลังปรับปรุงเพิ่มเติม เร็วๆนี้)

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

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

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

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