Internet & Web Application

ปัญหาโปรแกรมเชิงคณิตศาสตร์ (Mathematical Programming)

จำไม่ได้ว่า ได้มาจากไหนแต่คิดว่า เป็นคำอธิบายที่ดีสำหรับ Linear Programming, Interger Programming, Dynamic Programming, Probabilistic Programming, และ Nonlinear Programming

เทคนิคหรือวิธีการที่ใช้ในปัญหาโปรแกรมเชิงคณิตศาสตร์

เทคนิคหรือวิธีการที่สำคัญๆ และการศึกษากันมากได้แก่

1. โปรแกรมเส้นตรง (Linear Programmimg : LP)

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

ตัวแบบของปัญหาการโปรแกรมเชิงเส้นเขียนได้ดังนี้

ค่าสูงสุด (หรือค่าต่ำสุด) Z = f (x1, x2,…,xn) = Σnj = 1c j x j (1.4)

โดยมีข้อจำกัด

g i (x1, x2,…,xn) = Σnj = 1 a i jx i j { £ , = , ³ } bi i = 1, 2,…,m (1.5)

x j ³ 0 j = 1, 2,…,n (1.6)

ในเมื่อ cj, bi และ a i j เป็นค่าคงที่ ทุกๆ i และ j

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

2. โปรแกรมเลขจำนวนเต็ม (Integer Programming)

เป็นโปรแกรมเชิงคณิตศาสตร์ที่มีข้อจำกัดของตัวแปรว่าจะต้องเป็นเลขจำนวนเต็มที่ไม่มีค่าเป็นลบ นั่นคือ

x j = 0,1,2,… ทุกค่า j (1.7)

ปัญหาโปรแกรมเชิงจำนวนเต็มที่สำคัญ ได้แก่ ปัญหาการขนส่ง ปัญหาการมอบหมายงาน ปัญหาการจัดสรรงบประมาณ ปัญหาการจัดลำดับงาน เป็นต้น เทคนิคที่ใช้ในการหาคำตอบต่อปัญหาเหล่านี้ ไม่มีเทคนิคที่จัดว่าเป็นเทคนิคที่มีประสิทธิภาพโดยเฉพาะ แต่จะมีเทคนิคหลายแบบ แต่ละแบบจะเหมาะสมกับลักษณะของปัญหาหนึ่ง เช่น ใช้วิธีการขนส่ง (Transportation Method) กับปัญหาการขนส่ง หรือใช้วิธีการแจงนับ (Implicit Enumeration) กับปัญหาการเลือกโครงการที่ลงทุน เป็นต้น

3. โปรแกรมพลวัต (Dynamic Programming)

ใช้ในการแก้ปัญหาที่จะต้องตัดสินใจติดต่อกันเป็นขั้นตอนหลายๆ ขั้นตอน ลักษณะของปัญหาจะมีฟังก์ชัน f g 1, g 2, …,g m เป็นฟังก์ชันของตัวแปร x1, x2,…,xn ที่เป็นอิสระต่อกัน สามารถแยกเป็นปัญหาย่อยของแต่ละตัวแปร ซึ่งเรียกว่า ขั้นตอน การหาคำตอบต่อปัญหาทั้งหมด จำเป็นต้องสร้างตัวแบบทางคณิศาสตร์ขึ้นมาให้เหมาะสมกับปัญหาย่อยแต่ละปัญหาโดยเฉพาะ ปัญหาทั้งหมดจะแยกเป็นปัญหาย่อย (ขั้นตอน) โดยที่ ตัวแบบของแต่ละปัญหาย่อยจะได้มาจากการเปลี่ยนตัวแบบปัจจุบัน เป็นตัวแบบที่เกี่ยวข้องกับตัวแบบของปัญหาย่อยต่อไป ฟังก์ชันที่แสดงความเกี่ยวข้องของตัวแบบ เรียกว่า ฟังก์ชันความสัมพันธ์ต่อเนื่อง (recursive function) เทคนิคการตัดสินใจจึงขึ้นอยู่กับปัญหาที่ต้องการหาค่าที่ดีที่สุดในแต่ละปัญหาย่อย (ขั้นตอน) ซึ่งเกี่ยวข้องกับตัวแปรที่ต้องการหาค่าที่ดีที่สุดเพียงตัวเดียวเท่านั้น การคำนวณในขั้นตอนต่างๆ จะถูกเชื่อมโยงด้วยการคำนวณแบบต่อเนื่อง ในลักษณะที่ให้คำตอบที่เป็นไปได้ดีที่สุด ต่อปัญหาทั้งหมด เทคนิคของการคำนวณจะขึ้นอยู่กับ หลักของค่าดีที่สุด นั่นคือนโยบายที่ดีที่สุด ที่มีหลักเกณฑ์ว่า ไม่ว่าจุดเริ่มต้นและตัวแปรตัดสินใจจะเป็นอย่างไร ตัวแปรตัดสินใจที่เหลือต้องประกอบกันขึ้นเป็นนโยบายที่ดีที่สุดกับผลที่มาจากการตัดสินใจครั้งแรก

ตัวอย่าง2.6 นายเกษมมีเงินอยู่ 5,000 บาท เขาสนใจการลงทุนกับหุ้น 2 ประเภท หุ้นแต่ละประเภท มีราคา หุ้นละ 100 บาทเท่ากัน ผลตอบแทนของหุ้นคือ 40 และ 80 จงเขียนตัวแบบทางคณิตศาสตร์

เราจะแยกการแก้ปัญหาเป็น 2 ขั้นตอน นั่นคือ แยกปัญหาเดิมเป็นปัญหาย่อย 2 ปัญหา จะได้ตัวแบบของ แต่ละปัญหา ดังนี้

1. ขั้นตอนหรือปัญหาย่อย 1

ค่าสูงสุด f 1 (x, x1) = 40x1 – x12

โดยมีข้อจำกัด x1 £ x £ 50

x1 = 0, 1, 2, …

2. ขั้นตอนหรือปัญหาย่อย 2

ค่าสูงสุด f 2 (x, x2) = 80x2 – x22 + f 1* (50 – x2 )

โดยมีข้อจำกัด x2 £ 50

x2 = 0, 1, 2, …

ในเมื่อ f 1* (50 – x2 ) เป็นค่าสูงสุดของฟังก์ชันเป้าหมายในขั้นตอนที่ 1 ณ จุด x2 = 50 – x2

4. โปรแกรมเชิงน่าจะเป็น (Probabilistic Programming)

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

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

5. โปรแกรมที่ไม่เป็นเส้นตรง (Nonlinear Programming)

เป็นโปรแกรมเชิงคณิตศาสตร์ที่ใช้หาคำตอบ กรณีที่ตัวแปรตัดสินใจมีความสัมพันธ์กันในลักษณะที่ไม่เป็นเส้นตรง จะมีฟังก์ชัน

ค่าที่ดีที่สุด Z = f (X1,X2,…Xn) (1.1)

โดยมีข้อจำกัด gI (X1,X2,…Xn){ £ , = , ³ } bi i = 1, 2,…,m (1.2)

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

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

ค่าที่ดีที่สุด Z = Σnj = 1cj x j – ½ Σnj = 1 Σnk = 1 q jk x j x k (1.8)

โดยมีข้อจำกัด Σnj = 1 a i jx i j { £ , = , ³ } bi i = 1, 2,…,m (1.9)

x j ³ 0 j = 1, 2,…,n (1.10)

ในเมื่อ cj, bI ,a i j และ q jk เป็นค่าคงที่ q jk = q jk

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

Del.icio.us : , , , , , ,

Advertisements
มาตรฐาน

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s