 |
<script language="JavaScript" src="http://www.vcharkarn.com/javafeed/article/18966" type="text/javascript"></script> |
|
โปรแกรมเชิงเส้น (Linear Programming)
โปรแกรมเชิงเส้นเป็นเทคนิคที่รู้จักกันแพร่หลายและเป็นส่วนหนึ่งของการวิจัยในหลายๆด้าน นักบริหาร วิศวกรหรือนักวิทยาศาสตร์ในหลายๆ หน่วยงานได้ประยุกต์ใช้วิธีการทางโปรแกรมเชิงเส้น เพื่อให้เกิดประโยชน์สูงสุด
post ครั้งแรก: Sun 8 July 2007, 8:48 pm ปรับปรุงล่าสุด: Wed 18 July 2007, 11:33 pm
|
หน้าที่ 3 - การจัดตั้งรูปแบบแทนระบบของปัญหา (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 ]
เมื่อจัดตั้งรูปแบบแทนระบบของปัญหาให้เป็นรูปแบบโปรแกรมเชิงเส้นได้แล้ว เราจะมาหาผลลัพธ์ของปัญหาเหล่านี้
*หมายเหตุ
งานเขียนชิ้นนี้ ได้รับการคุ้มครองสิทธิตามพระราชบัญญัติคุ้มครองสิทธิทางปัญญา โดยลิขสิทธิเป็นของผู้เขียน ที่ให้เกียรตินำเผยแพร่ผ่าน วิชาการ.คอม เรามีความยินดีและอนุญาตให้ทำซ้ำหรือเผยแพร่ต่อเพื่อประโยชน์ทางการศึกษาเท่านั้น กรุณาให้เกียรติผู้เขียน โดยอ้างชื่อผู้เขียนและ วิชาการ.คอม (www.vcharkarn.com) ทุกครั้งที่ทำการเผยแพร่ต่อ ห้ามนำส่วนหนึ่งส่วนใดไปเผยแพร่ต่อในสื่อที่เอื้อประโยชน์ทางธุรกิจก่อนได้รับอนุญาต ขอขอบคุณที่ร่วมกันช่วยสร้างให้สังคมไทยเป็นสังคมแห่งปัญญา
จำนวน 1 ความเห็น, หน้า่ | -1-
ความเห็นเพิ่มเติมที่ 1 26 ก.ค. 2550 (09:33) อยากได้โจทย์ตัวอย่างพร้อมเฉยลเกี่ยวกับเรื่อง simulation ค่ะ ขอบคุณค่ะ