Operation Research(OR) Part1 For Industrail Engineering
*จากการหาสมการความสัมพันธ์ต่างๆนาๆตามข้อทั้ง
4 ข้อ
เราสามารถวาดกราฟเพื่อหาคำตอบได้
โดยเขียนเงื่อไข
ข้อจำกัดที่ได้มาวาดกราฟแล้วหาพื้นที่ที่ต้องการ
แล้วเราจะได้จุดต่างๆบนแราฟที่อยู่บริเวณขอบแรงเงา
(พื้นที่เเรงเงาเราได้มาจากส่วนที่ต้องการทับการจากพวก ค่าจำกัด น้อยกว่าเท่ากับ
มากกว่าเท่ากับ)
แล้วนำจุดต่างๆมาแทนค่าลงสมการ Z เพื่อหา Max ||
Min *
การหาผลลัพธ์ของการโปรแกรมเชิงเส้นตรง
การหาผลลัพธ์เหมาะที่สุดโดย
- Simplex: ใช้เมื่อสมการ (Subject To) เป็น <= ทั้งหมด และเพื่อง่ายไม่หลากวิธีให้ใช้เป็น Maximize (การเปลี่ยนค่า Min >>>> Max หรือสลับ
ให้ × สมการด้วย -1 โดยที่คูณหลังจากเพิ่มตัวแปรต่างๆเสร็จเรียบร้อยเเล้ว
และตอนท้ายคำตอบต้องคูณกลับคืนด้วย) วิธีการทำดังนี้
- พิจารณาว่าตัวแปรตัดสินใจ (ซึ่งดูว่าตัวแปรไหนมีผลกับสมการ Z บ้าง) แล้วปรับผลลัพธ์สมการ (Subject to) ป็นจำนวนเต็มบวก
- เปลี่ยนให้อยู่ในรูปแบบมาตรฐานของการโปรแกรมเชิงเส้นตรง คือ ทำให้สมการ (Subject To) เป็นเครื่องหมายเท่ากับ โดย +ตัวแปรเเต่ละสมการเพิ่มในด้านที่น้อยกว่า เรียก ตัวแปรที่เพิ่มว่า ตัวแปรหย่อน
- แทนค่า เเละคำนวนค่าต่างๆลงตาราง ทำตามตารตางในตัวอย่างถัดไป
- ทำการหาค่า Z ที่เหมาะสมผ่านตาราง ตามตัวอย่างต่อไปนี้
Eg. 1.
*จำนวนเเถวของมูลฐาน = จำนวนสมการ Sub. To
ค่า b คือค่าผลลัพธ์ของเเต่ละสมการ
ช่องมูฐานได้มาจากตัวแปรที่มีรูปแบบ
มีการเทียบจาก พวก รูปแบบ Matrix
1 0 0
0 1 0
0 0 1 ใส่มูลฐานเฉพาะค่าที่ เต็ม
+1
ตามหลักคานิเคิล
ค่าใต้ตัวแปรต่างๆ ของ Cj คือค่าสัมประสิทธิ์
คำนวณ C bar : หลัก X1 = 3 - [0*(-1)+0*3+0*1] = 3
หลัก
X2 = 2 -
[0*2+0*2+0*(-1)] = 2
ทำต่อๆไปจนครบทุกช่อง
หาจุด Pivot :
- หาค่า C bar ว่าหลักไหน มากที่สุด (ในที่นี้คือ 3) และต้องเป็น + ด้วย
- นำค่า b แต่ละเเถวมาหารด้วย ค่าเเต่ละแถวเดียวกันของหลักที่ได้ C bar มากสุด
- จากนั้นเทียบกันว่า ค่าไหนน้อยสุด ไม่นับ ค่าติดลบ (จะได้ Infinity)
- จากนั้น แทนค่าตัวแปรของหลักที่มีจุด Pivot ลงช่อง มูลฐาน ในแถวเดียวกัน พร้อม เปลี่ยนตัวสัมประสิทธิ์ จากนั้นทำให้แปลงค่า Pivot Point = 1 และค่าที่เหลือในหลักนั้นแปลงให้ = 0
ดังนี้

*กรณีที่หาจุด Pivot ข้นตอนที่ 3. เเล้ว
ค่ามูลฐานเกิดมีค่า 0/ค่าสักอย่าง ให้หยุดทำต่อเเล้วสรุปว่า
ซึ่งเราเรียกผลลัพธ์มูลฐานที่เป็นไปได้ที่
มีตัวแปรมูลฐานหนึ่งหรือมากกว่าหนึ่งตัวเท่ากับศูนย์ว่าสภาวะซ้อนสถานะ (Degeneracy)
ซึ่งหาคำตอบไม่ได้
*กรณีที่หาจุด Pivot ข้นตอนที่ 3. แล้วเกิดมีค่า
ติดลบทุกๆค่า จะสรุปได้ว่า ปัญหานี้จะให้ผลลัพธ์ไร้ขอบเขต
ทำให้ค่าเเต่ละเเถวในหลักเดียวกับ Pivot Point = 0 ทั้งหมด
โดยการหาแบบ matrix โดยหลักในที่นี้คือ
ตัวแปรทั้ง 5 แล้วมีแถวคือ Cbi
ทำการหาค่า C bar ใหม่
แล้วใช้วิธีเดิม หาจุด Pivot เพิ่อ ให้ค่า C bar ทุกหลักที่เป็นตัวแปรตัดสินใจ
(ที่ไม่รวมตัวแปรที่เพิ่มมาเพราะ
ต่อให้คำนวณยังไง ตัวแปรพวกนั้นก็ไม่มีผลกับค่า Z)
*กรณีที่ C bar ของตัวแปรหย่อน (ในที่นี้คือ X5) = 0 แล้วตัวแปรนั้นไม่ได้อยู่ในตัวแปรมูลฐาน
จะสรุปได้ว่า
แสดงว่าปัญหาการโปรแกรมเชิงเส้นตรงนี้มีผลลัพธ์เหมาะที่สุดหลายค่า
(คือ ตัวแปรเเต่ละตัวจะมีค่าไม่เท่ากันขณะที่ค่า Z
เท่าเดิม) หาคำตอบอื่น
โดย ทำ Pivot point ที่หลักนั้น
โดยที่ ไม่ทำให้
ตัวเลขที่ป็น 0 0 1, 0 1 0, 1 0 0. ของตัวแปรตัดสิน ที่ทำการ Pivot point ไปแล้วมีค่าแบบคาโนนิคอล
*เราต้องทำให้ค่า C bar
= 0 ให้ได้ทั้งหมด โดยหาจุด Pivot ยกเว้น C bar = ติดลบ ไม่ต้องหา Pivot
point
- Big-M Simplex: ใช้เมื่อสมการขอบข่ายไม่อยู่ตามระบบคาโนนิคอล (โดยไม่สนว่าสมการ Subject To จะมีเครื่องหมายผลลัพธ์เป็นอย่างไร)
มีวิธีการทำดังนี้ *กรณีสมการวัตถุประสงค์เป็น
Maximize
- ทำการ +- สมการ Subject To ให้เรียบร้อย แล้วดูที่สมการที่เป็น = (Subj. To) ซึ่งถ้ามันจะยังไม่เข้ารูป โคนาโนนิคอล เราจึงต้อง +ตัวแปรเข้าไปอีก
แล้วไป +ใส่สมการ Z ด้วย ตอนบวกใส่ Z จะต้อง *Mตัวแปรที่+ไปตัวเดียว
- ตัวแปรที่เพิ่มเข้ามาคือ ตัวแปรเทียม เอาไว้ใช้ให้เข้ารูประบบคาโนนิคอล เพื่อคำนวณตามเเบบ Simplex ต่อไป
- หากอยู่ในรูป Min ก็ *-1 เป็น Max หลังจากที่ +ตัวแปรMเข้าไปเเล้ว
Eg.
คือถ้ามี
-ตัวแปร เพิ่มมา เราจะต้อง +ตัวแปรเพิ่ม แล้วไป+ตัวนี้ที่มี M
เป็นสัมประสิทลงสมการวัตถุประสง แล้วสมการถัดไปต้องบวก ตัวแปร ที่ต้องใส่ M
ในสมการวัตถุประสง
จากการเปลี่ยน Min to Max จะมีวิธีการดูตรงข้ามกันที่
C bar , Z ที่จาก + to - ส่วนคำตอบจะเท่ากัน(X)
และตอนตอบเราจึงต้อง × -1 ใส่ Z ที่เป็น Maximize ให้เป็น M
- Branch and Bound Method: ใช้กรณีที่เราต้องการคำตอบเป็น จำนวนเต็ม โดยมีวิธีดังนี้
- ทำการหาคำตอบของผลลัพธ์ด้วยวิธีต่างๆจนได้ผลลัพธ์มาก่อน (ตัวแปรตัดสินใจ(X),ค่าผลลัพธ์(Z))
- ได้คำตอบเป็น จุดทศนิยม แล้วให้ปัดขึ้น-ลง ให้เป็นจำนวนเต็มไม่ซ้ำกัน เพื่อแยกพิจารณาว่าค่าไหนเหมาะสม
- แยก bound ที่1 จะเป็นของ Z แยกเป็น Upper bound (ค่า Z ที่มีค่ามากสุด) and Lower bound (Z=-infinity เนื่องจากยังไม่เเตก bound ออก), (กรณี Objective: Maximize หากเป็น Minimize ก็คิดหา Lower bound ที่มีค่า Z น้อยที่สุดแทน)
- Bound ที่2 และ bound ที่3 จะเป็นการพิจารณากรณีตัวแปรตัดสินใจถูกปัดค่าขึ้นและปัดลง โดยกำหนดขอบเขตตัวแปรตัดสินใจเพิ่ม ซึ่งให้ใช้เครื่องหมาย >= และ <= ตามลำดับ
- จากนั้นทำวิธีเดิมในการหาคำตอบ ถ้าเกิดตัวแปรตัดสินใจ bound ไหน ตรงตามเงื่อนไง ก็จะหยุดหาผลลัพธ์ เเละจะเรียกว่า Fathoming เเต่ถ้ามี bound ไหนไม่เป็นไปตามเงื่อนไงคืออาจจะเป็นจุดทศนิยมเกิดขึ้นมาใหม่ ก็จะเเยก bound เพิ่มเพื่อหาแบบเดิมต่อไปจนได้ผลลัพธ์ที่ต้องการ
- นำผลลัพธ์ที่ได้ทั้งหมดมาเปรียบเทียบกัน เพื่อให้สอดคล้องกับเงื่อนไขเเละ Objective Fn.
- ****ถ้าหากสมการมีเพียง2ตัวแปร เราควรจะหาคำตอบของสมการด้วยวิธีวาดกราฟ
Eg.
วาดกราฟตามเงื่อนไขทีละขั้นตอน
โดยกำลังหนดลูกศรเเละระบุสมการที่มาโดยระเอียด
การจะหาค่า Z ก็สามารถเเทนค่าแต่ละจุดที่อนุ่ในบริเวณภายใต้เงื่อนไขลง
สมการ Z ทีละจุดเพื่อเทียบว่า ค่าZไหนมากน้อยกว่ากัน
การหาค่าตัวแปรที่ไม่ทราบค่าก็สามารถแทนอีกตัวแปร =0 แล้วแก้สมการ
สมการเส้นตรง Z=3X1 + 2X2 เกิดจากการกำหนดค่า
Z แล้วให้ตัวแปรตัวนึง =0 เพื่อหาเส้นตรง
Reversed Simplex (ฉบับปรับปรุง)




จบไปเเล้วสำหรับ Part แรก เจอกัน Part ต่อไปฮะ อย่าลืมติดตามกันนะ
ความคิดเห็น
แสดงความคิดเห็น