กำหนดการเชิงเส้น: กำหนดการเชิงเส้น 3

จุดประสงค์การเรียนรู้

เมื่อศึกษาหน่วยนี้แล้วนักศึกษาควรมีความสามารถในสิ่งต่อไปนี้

1. นักศึกษาบอกความหมายของกำหนดการเชิงเส้นได้

2. นักศึกษามีความรู้ความเข้าใจกราฟของสมการและอสมการเชิงเส้นสองตัวแปร

3. นักศึกษาสามารถหาสมการจุดประสงค์ได้

4. นักศึกษาสามารถหาอสมการข้อจำกัดได้

5. นักศึกษาประยุกต์ใช้แบบจำลองทางคณิตศาสตร์ โดยใช้กราฟได้

ความหมายของกำหนดการเชิงเส้น

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

ตัวอย่างปัญหากำหนดการเชิงเส้น

1. ผู้ขายสินค้าต้องเลือกชนิดของสินค้าที่จะนำมาขาย เพื่อให้ขายได้ผลกำไรมากที่สุด

2. ผู้จัดรายการโทรทัศน์ต้องการเลือกแบบรายการแสดงเพื่อให้ผู้ชมรายการแสดงมากที่สุด

3. ต้องการจ้างคนงานก่อสร้างเพื่อให้งานเสร็จตามเวลาที่กำหนดในราคาต่ำสุด

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

1. สมการจุดประสงค์ (สร้างจากความต้องการที่เกี่ยวกับมากที่สุด น้อยที่สุด)

2. อสมการข้อจำกัด (สร้างจากเงื่อนไขอื่น ๆ ที่เป็นส่วนประกอบเพื่อให้ได้ความต้องการที่เกี่ยวกับมากที่สุด น้อยที่สุด

การหาคำตอบของกำหนดการเชิงเส้น

การหาคำตอบของกำหนดการเชิงเส้น ดำเนินการดังนี้

1. นำปัญหามาสร้างแบบจำลองคณิตศาสตร์ ประกอบด้วย

1.1 สมการจุดประสงค์

1.2 กลุ่มอสมการเงื่อนไข

1.3 ตัวแปรทุกตัวมากกว่าหรือเท่ากับศูนย์

2. เขียนกราฟของอสมการข้อจำกัด ของทุกอสมการ แล้วแรเงา บริเวณที่หาคำตอบได้(feasible region) ได้แก่บริเวณที่ผลลัพธ์ของตัวแปรทั้งสองเป็นคำตอบได้

3. เขียนจุดยอดมุม (extreme points) ของรูปสี่เหลี่ยมที่เกิดจากการแรเงา

4. ตรวจสอบว่าจุดยอดมุมตามข้อ 3 จุดใดที่ให้ค่าสูงสุดหรือต่ำสุด ตามที่โจทย์กำหนดโดยการแทนค่าหรือ

5. การตรวจสอบโดยการเลื่อนเส้นตรงที่สร้างจากสมการจุดประสงค์ที่ผ่านจุด (0,0) เข้าไปในบริเวณที่หาคำตอบได้ จุด (x,y) จุดแรกที่พบจะให้ค่าต่ำสุดจุดสุดท้ายของ (x,y) ที่พบจะให้ค่าสูงสุด

การสร้างแบบจำลองทางคณิตศาสตร์

ตัวอย่างที่ 1 ในการผลิตสินค้า 2 ชนิด ชนิดที่หนึ่งได้กำไร 5 บาท ต่อชิ้น ชนิดที่สองได้กำไร 7 บาทต่อชิ้น สินค้าชนิดที่หนึ่งต้องใช้เวลาผลิต 3 นาที และใช้วัตถุดิบ 10 หน่วย ชนิดที่สองใช้เวลาผลิต 4 นาที และใช้วัตถุดิบ 8 หน่วย สมมุติว่าโรงงานมีเครื่องจักรที่จำกัด จะผลิตสินค้าทั้งสองชนิดพร้อม ๆ กัน ไม่ได้ และทำการผลิตเพียงวันละ 7 ชั่วโมง มีวัตถุดิบเพียงพอที่จะผลิตได้วันละ 200 หน่วย ถ้าต้องการผลิตให้ได้กำไรมากที่สุด ในแต่ละวัน จงสร้างตัวแบบจำลองทางคณิตศาสตร์กำหนดการเชิงเส้นแทนปัญหาการผลิตสินค้านี้

วิธีทำ

	สินค้าชนิดหนึ่ง	สินค้าชนิดที่สอง
เวลาที่ใช้ผลิตวัตถุดิบ	3 นาที/ชิ้น 10 หน่วย	4 นาที/ชิ้น 8 หน่วย	วันละไม่เกิน7 ชั่วโมง มีไม่เกิน200หน่วย
กำไร	5 บาท	7 บาท

ให้ เป็นจำนวนสินค้าชนิดที่หนึ่งที่ผลิต

ให้ เป็นจำนวนสินค้าชนิดที่สองที่ผลิต

ดังนั้น กำหนดการเชิงเส้น จะมีตัวแบบจำลองทางคณิตศาสตร์ดังนี้

ให้ค่าสูงสุดของ P = 5 + 7 (กำไร)

เมื่อ 3+ 4 420 (เวลา)

10+8 200 (วัตถุดิบ) และ 0, 0

ตัวอย่างที่ 2 จงหาค่าสูงสุดของ P ตามเงื่อนไขที่กำหนดให้

P = 4x+5y

x+2y 16

3x+ y 18

x 0

y 0

วิธีทำ

P = 4x+5y

x+2y 16

3x+ y 18

x 0

y 0

จะได้กราฟของอสมการข้อจำกัดดังนี้ (มีกราฟเป็นรูปสี่เหลี่ยมตามที่แรเงาซึ่งรวมถึงด้านทั้งสี่ด้วย)

หาพิกัดของจุด B ให้ x+2y = 16 ………….(1)

3x+ y = 18 ………….(2)

(1)×3, 3x+6y = 48 ………….(3)

(3)-(2) 5y = 30

y = 6

แทนค่า y = 6 ใน (1)

x + 12 = 16

x = 16-12 = 4

จะได้พิกัดของจุด B คือ (4,6)

ตรวจสอบจุดมุม O,A,B และ C ของ สี่เหลี่ยม OABC เพื่อดูค่า Z

จุดมุม (x, y)	P = 4x +5y
O(0,0) A(6,0) B(4,6) C(0,8)	0 24 46 40

ตัวอย่างที่ 3 ช่างตัดเสื้อมีผ้าไหมสีพื้น 16 เมตร ผ้าไหมลายดอก 15 เมตร และผ้าฝ้าย 11 เมตร ถ้าต้องการนำผ้าไหมและผ้าฝ้ายดังกล่าวมาตัดชุดกลางวันและชุดราตรีโดยชุดกลางวันแต่ละชุดใช้ผ้าไหมสีพื้น2 เมตร ผ้าไหมลายดอก 1 เมตร ผ้าฝ้าย 1 เมตร และขายได้กำไรตัวละ 300 บาท ส่วนชุดราตรีแต่ละชุดใช้ผ้าไหมสีพื้น 1 เมตร ผ้าไหมลายดอก 3 เมตร ผ้าฝ้าย 2 เมตร และขายได้กำไรตัวละ 500 บาท ช่างตัดเสื้อผ้าควรตัดชนิดละกี่ชุด เมื่อขายจะทำให้ได้กำไรมากที่สุดและกำไรมากที่สุดเท่าใด

วิธีทำ ตัวแปรคือจำนวนชุดกลางวันและชุดราตรี โดยมีผ้าที่จะใช้ตัดให้ได้กำไรที่สุดเป็น

P บาท โดยชุดกลางวัน x ชุด ตัดชุดราตรี y ชุด

P = 300x+500y

สมการ P = 300x+500y เรียกว่า “สมการจุดประสงค์”

ตัดชุดกลางวัน x ชุด แต่ละชุดใช้ผ้าไหมสีพื้น 2x เมตร ผ้าไหมลายดอก 1x เมตร ผ้าฝ้าย 1x เมตร

ตัดชุดราตรี y ชุด แต่ละชุดใช้ผ้าไหมสีพื้น 1y เมตร ผ้าไหมลายดอก 3y เมตร ผ้าฝ้าย 2y เมตร

มีผ้าไหมสีพื้น 16 เมตร ผ้าไหมลายดอก 15 เมตร และผ้าฝ้าย 11 เมตร

2x + y 16

x+ y 15

x+2y 11

ทั้งนี้ x 0 , y 0

อสมการทั้งหมดนี้เรียกว่า “ อสมการข้อจำกัด” แบบจำลองทางคณิตศาสตร์สำหรับข้อนี้

คือ P = 300 x+500y

2x + y 16

x+ y 15

x+2y 11

x 0

y 0

นำอสมการทั้งหมดนี้เขียนกราฟ

จาก P = 300 x+500y

ณ จุด A(0, 0); P = 0 ณ จุด B(8, 0); P = 2,400

ณ จุด C(7, 2); P = 3,100 ณ จุด D(0, 5.5); P = 2,750

ค่าสูงสุด = 3,100 ณ จุด C (7,2)

ให้ตัดชุดกลางวัน 7 ชุด

ตัดชุดราตรี 2 ชุด ได้กำไรมากที่สุด 3,100 บาท

ตัวอย่างที่ 4 เจ้าของกิจการต้องการทำความสะอาดตู้ 5 ตู้ โต๊ะ 12 ตัวและชั้นหนังสือ 18 ชั้น เขามีคนงาน 2 คน คนแรกสามารถทำความสะอาดตู้ได้ 1 ตู้ โต๊ะ 3 ตัว และชั้นหนังสือ 3 ชั้น ภาย ในเวลา 1ชั่วโมง คนที่สองสามารถทำความสะอาดตู้ได้ 1 ตู้ โต๊ะ 2 ตัว และชั้นหนังสือ 6 ชั้น ภาย ในเวลา 1 ชั่วโมง คนแรกได้ค่าแรงชั่วโมงละ 25 บาท คนที่สองได้ค่าแรงชั่วโมงละ 22 บาท เพื่อจะเสียค่าแรงน้อยที่สุดเจ้าของกิจการควรจ้างทำคนละกี่ชั่วโมง

วิธีทำ

ให้คนแรกทำ x ชั่วโมง

คนที่สองทำ y ชั่วโมง

โดยเสียค่าแรงน้อยที่สุด P บาท

P = 25x+22y

คนแรกทำ x ชั่วโมง จะทำความสะอาดตู้ได้ 1x ตู้ โต๊ะ 3x ตัว และชั้นหนังสือ 3x ชั้น

คนที่สองทำ y ชั่วโมง จะทำความสะอาดตู้ได้ 1y โต๊ะ 2y ตัว และชั้นหนังสือ 6y ชั้น

x + y 5

3x +2y 12

3x +6y 18

x 0

y 0

(x, y)	P = 25 x+ 22 y
(0, 6) (2, 3) (4, 1) (6, 0)	132 116 122 150

ค่าต่ำสุด = 116 ณ B(2,3) จ้างคนแรกทำงาน 2 ชั่วโมง

จ้างคนที่สองทำงาน 3 ชั่วโมง

ตัวอย่างที่ 5 ในการผลิตปุ๋ยชนิดหนึ่งต้องการผลิตให้ได้ต้นทุนถูกที่สุด โดยให้ปุ๋ยที่ได้มีแร่ธาตุ N-P-K อย่างน้อย 9,5 และ 6 หน่วย ตามลำดับในปุ๋ย 100 ปอนด์ ของสารอาหาร x และ 100 ปอนด์ของสารอาหาร y ให้แร่ธาตุ N – P – K ตามตารางและสมมุติราคาสารอาหาร x และ y เป็น 3 บาทและ5 บาท ต่อ 100 ปอนด์ ตามลำดับ ดังนั้น จะต้องใช้สารอาหาร x และสารอาหาร y อย่างละเท่าไร

แร่ธาตุ	น้ำหนัก		จำนวนที่ต้องการอย่างน้อย
แร่ธาตุ	สารอาหาร x	สารอาหาร y	จำนวนที่ต้องการอย่างน้อย
N (ไนโตรเจน) P (ฟอสฟอรัส) K (โปตัสเซียม)	1 หน่วย 1 หน่วย 2 หน่วย	3 หน่วย 1หน่วย 1 หน่วย	9 หน่วย 5 หน่วย 6 หน่วย
ราคาสารอาหาร ต่อ 100 ปอนด์	3 บาท	5 บาท

วิธีทำ

ให้ x แทนจำนวนหน่วยของสารอาหาร x ที่ใช้ในหน่วย 100 ปอนด์ และให้ y แทนจำนวนหน่วยของสารอาหาร y ที่ใช้ในหน่วย 100 ปอนด์ เขียนข้อมูลที่ได้ในตัวแบบกำหนดการเชิงเส้น ได้ดังนี้

ให้ค่าต่ำสุดของ C = 3x + 5y

x +3y 9

x + Y 5

2 x +y 6 และ x 0, y 0

เขียนกราฟแสดงขอบเขตที่เป็นไปได้ ดังต่อไปนี้

ขอบเขตที่เป็นไปได้ คือส่วนที่แรเงามี A,B,EและF เป็นมุมที่เป็นไปได้จะสามารถแก้สมการหาพิกัดของมุมทั้งสี่ได้อย่างง่าย และหาค่า C = 3x + 5y ที่สอดคล้องกับค่า (x,y) ณ มุมทั้งสี่ที่หาได้ดังตารางต่อไปนี้

มุม	พิกัดของมุมที่เป็นไปได้	ค่า C = 3x + 5y
A B E F	(9,0) (3,2) (1,4) (0,6)	27 19 23 30

ดังนั้นผลเฉลยเหมาะที่สุด คือ ค่า C ต่ำที่สุดอยู่ที่มุม B(3,2) นั่น คือ จะต้องซื้อสารอาหาร x จำนวน 300 ปอนด์ สารอาหาร y จำนวน 200 ปอนด์ และจะเสียค่าใช้จ่ายต่ำสุดเพียง 19 บาท

ข้อสังเกต จากแผนการหาส่วนผสมปุ๋ยตามตัวอย่างนี้ จะพบว่าในส่วนผสมดังกล่าว เราได้ธาตุ N และ P พอดีกับจำนวนขั้นต่ำที่ต้องการ แต่ได้แร่ธาตุ K เพิ่มขึ้นกว่าจำนวนขั้นต่ำถึง 2 หน่วย

ตัวอย่างที่ 6 บริษัทผลิตกระดาษโรเนียวแห่งหนึ่ง มีโรงงานผลิตกระดาษ 2 แห่ง แต่ละแห่งผลิตกระดาษที่มีคุณภาพแตกต่างกัน 3 ชนิด คือ ชนิดเลว ปานกลาง และชนิดดี บริษัทต้องการผลิตกระดาษต้องการผลิตกระดาษคุณภาพชนิดเลว 16 ตัน ชนิดปานกลาง 5 ตัน และชนิดดี 20 ตันทั้งนี้ เพราะต้องการผลิตให้พอดีกับปริมาณที่ลูกค้าสั่งซื้อ ค่าใช้จ่ายในการผลิตกระดาษจากโรงงานที่ 1 วันละ 25,000 บาทโรงงานที่ 2 วันละ 50,000 บาท ซึ่งแต่ละโรงงานจะผลิตกระดาษแต่ละวันได้ ดังต่อไปนี้

โรงงานที่ 1 ผลิตกระดาษคุณภาพชนิดเลวได้ 8 ตัน ปานกลางได้ 1 ตัน และชนิดดีได้ 2 ตัน

โรงงานที่ 2 ผลิตกระดาษคุณภาพชนิดเลวได้ 2 ตัน ปานกลางได้ 1 ตัน และชนิดดีได้ 7 ตัน

จงสร้างตัวแบบกำหนดการเชิงเส้นแทนปัญหานี้โดยต้องการหาเวลาการผลิต (หน่วยเป็นวัน) ที่เหมาะสมเพื่อให้ประหยัดค่าใช้จ่ายที่สุด

วิธีทำ สร้างตารางแสดงข้อมูลต่าง ๆ จากโจทย์ ได้ดังต่อไปนี้

	ปริมาณกระดาษที่ผลิตต่อวัน(ตัน)			ค่าใช้จ่ายต่อวัน(บาท)
	ชนิดเลว	ชนิดปานกลาง	ชนิดดี	ค่าใช้จ่ายต่อวัน(บาท)
โรงงาน 1 โรงงาน 2	8 2	1 1	2 7	25,000 50,000
ความต้องการ	16	5	20

ให้ x₁แทนจำนวนที่ผลิตกระดาษของโรงงานที่ 1

ให้ x₂แทนจำนวนที่ผลิตกระดาษของโรงงานที่ 2

ดังนั้นตัวแบบกำหนดการเชิงเส้นจะได้ ดังต่อไปนี้

ให้ค่าต่ำสุด P = 25,000 x₁+50,000 x₂ (ค่าใช้จ่าย)

เมื่อ 8x₁+2x₂ 16 (ปริมาณกระดาษชนิดเลว)

x₁+x₂ 5 (ปริมาณกระดาษชนิดปานกลาง)

2x₁+7x₂20 (ปริมาณกระดาษชนิดดี)

x₁ 0, x₂0

เขียนกราฟของเงื่อนไขบังคับได้ดังต่อไปนี้

ขอบเขตที่เป็นไปได้เป็นเซตอนันต์ ซึ่งประกอบด้วยจุดมุมที่เป็นไปได้ต่อไปนี้ (0,8),(1,4),(3,2) และ (10,0)

เปรียบเทียบค่า P ณ จุดมุมทั้งสี่ดังต่อไปนี้

มุม

ค่า P = 25,000 x₁+50,000 x₂

(0,8)

กำหนดการเชิงเส้น

กำหนดการเชิงเส้น

วันอังคารที่ 16 ธันวาคม พ.ศ. 2557

กำหนดการเชิงเส้น 3

ไม่มีความคิดเห็น:

แสดงความคิดเห็น