Operation Research(OR) Part1 For Industrail Engineering


*จากการหาสมการความสัมพันธ์ต่างๆนาๆตามข้อทั้ง 4 ข้อ
เราสามารถวาดกราฟเพื่อหาคำตอบได้
โดยเขียนเงื่อไข ข้อจำกัดที่ได้มาวาดกราฟแล้วหาพื้นที่ที่ต้องการ
แล้วเราจะได้จุดต่างๆบนแราฟที่อยู่บริเวณขอบแรงเงา (พื้นที่เเรงเงาเราได้มาจากส่วนที่ต้องการทับการจากพวก ค่าจำกัด น้อยกว่าเท่ากับ มากกว่าเท่ากับ)
แล้วนำจุดต่างๆมาแทนค่าลงสมการ Z เพื่อหา Max || Min *

การหาผลลัพธ์ของการโปรแกรมเชิงเส้นตรง
การหาผลลัพธ์เหมาะที่สุดโดย

  • Simplex: ใช้เมื่อสมการ (Subject To) เป็น <= ทั้งหมด และเพื่อง่ายไม่หลากวิธีให้ใช้เป็น Maximize (การเปลี่ยนค่า Min >>>> Max หรือสลับ
ให้ × สมการด้วย -1 โดยที่คูณหลังจากเพิ่มตัวแปรต่างๆเสร็จเรียบร้อยเเล้ว และตอนท้ายคำตอบต้องคูณกลับคืนด้วย) วิธีการทำดังนี้
  1. พิจารณาว่าตัวแปรตัดสินใจ (ซึ่งดูว่าตัวแปรไหนมีผลกับสมการ Z บ้าง) แล้วปรับผลลัพธ์สมการ (Subject to) ป็นจำนวนเต็มบวก
  2. เปลี่ยนให้อยู่ในรูปแบบมาตรฐานของการโปรแกรมเชิงเส้นตรง คือ ทำให้สมการ (Subject To) เป็นเครื่องหมายเท่ากับ โดย +ตัวแปรเเต่ละสมการเพิ่มในด้านที่น้อยกว่า เรียก ตัวแปรที่เพิ่มว่า ตัวแปรหย่อน
  3. แทนค่า เเละคำนวนค่าต่างๆลงตาราง ทำตามตารตางในตัวอย่างถัดไป
  4. ทำการหาค่า 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 :
  1. หาค่า C bar ว่าหลักไหน มากที่สุด (ในที่นี้คือ 3) และต้องเป็น + ด้วย
  2. นำค่า b แต่ละเเถวมาหารด้วย ค่าเเต่ละแถวเดียวกันของหลักที่ได้ C bar มากสุด
  3. จากนั้นเทียบกันว่า ค่าไหนน้อยสุด ไม่นับ ค่าติดลบ (จะได้ Infinity)
  4. จากนั้น แทนค่าตัวแปรของหลักที่มีจุด Pivot ลงช่อง มูลฐาน ในแถวเดียวกัน พร้อม เปลี่ยนตัวสัมประสิทธิ์ จากนั้นทำให้แปลงค่า Pivot Point = 1 และค่าที่เหลือในหลักนั้นแปลงให้ = 0
ดังนี้
 *กรณีที่หาจุด Pivot  ข้นตอนที่ 3. ค่าน้อยสุดเท่ากัน เราสามารถเลือกได้ว่าจะใช้จุดไหนก่อน (เนื่องจากจุดอีกจุดก็จะต้องตามมาอยู่ดี)
*กรณีที่หาจุด 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
  1. ทำการ +- สมการ Subject To ให้เรียบร้อย แล้วดูที่สมการที่เป็น = (Subj. To) ซึ่งถ้ามันจะยังไม่เข้ารูป โคนาโนนิคอล เราจึงต้อง +ตัวแปรเข้าไปอีก
แล้วไป +ใส่สมการ Z ด้วย ตอนบวกใส่ Z จะต้อง *Mตัวแปรที่+ไปตัวเดียว  
  1. ตัวแปรที่เพิ่มเข้ามาคือ ตัวแปรเทียม เอาไว้ใช้ให้เข้ารูประบบคาโนนิคอล เพื่อคำนวณตามเเบบ Simplex ต่อไป
  2. หากอยู่ในรูป Min ก็ *-1 เป็น Max หลังจากที่ +ตัวแปรMเข้าไปเเล้ว
Eg.


คือถ้ามี -ตัวแปร เพิ่มมา เราจะต้อง +ตัวแปรเพิ่ม แล้วไป+ตัวนี้ที่มี M เป็นสัมประสิทลงสมการวัตถุประสง แล้วสมการถัดไปต้องบวก ตัวแปร ที่ต้องใส่ M ในสมการวัตถุประสง



จากการเปลี่ยน Min to Max จะมีวิธีการดูตรงข้ามกันที่ C bar , Z ที่จาก +  to  - ส่วนคำตอบจะเท่ากัน(X) และตอนตอบเราจึงต้อง × -1 ใส่ Z ที่เป็น Maximize ให้เป็น M

  • Branch and Bound Method: ใช้กรณีที่เราต้องการคำตอบเป็น จำนวนเต็ม  โดยมีวิธีดังนี้
  1. ทำการหาคำตอบของผลลัพธ์ด้วยวิธีต่างๆจนได้ผลลัพธ์มาก่อน (ตัวแปรตัดสินใจ(X),ค่าผลลัพธ์(Z))
  2. ได้คำตอบเป็น จุดทศนิยม แล้วให้ปัดขึ้น-ลง ให้เป็นจำนวนเต็มไม่ซ้ำกัน เพื่อแยกพิจารณาว่าค่าไหนเหมาะสม
  3. แยก bound ที่1 จะเป็นของ Z แยกเป็น Upper bound (ค่า Z ที่มีค่ามากสุด) and Lower bound (Z=-infinity เนื่องจากยังไม่เเตก bound ออก), (กรณี Objective: Maximize หากเป็น Minimize ก็คิดหา Lower bound ที่มีค่า Z น้อยที่สุดแทน)
  4. Bound ที่2 และ bound ที่3 จะเป็นการพิจารณากรณีตัวแปรตัดสินใจถูกปัดค่าขึ้นและปัดลง โดยกำหนดขอบเขตตัวแปรตัดสินใจเพิ่ม ซึ่งให้ใช้เครื่องหมาย >= และ <= ตามลำดับ
  5. จากนั้นทำวิธีเดิมในการหาคำตอบ ถ้าเกิดตัวแปรตัดสินใจ bound ไหน ตรงตามเงื่อนไง ก็จะหยุดหาผลลัพธ์ เเละจะเรียกว่า Fathoming เเต่ถ้ามี bound ไหนไม่เป็นไปตามเงื่อนไงคืออาจจะเป็นจุดทศนิยมเกิดขึ้นมาใหม่ ก็จะเเยก bound เพิ่มเพื่อหาแบบเดิมต่อไปจนได้ผลลัพธ์ที่ต้องการ
  6. นำผลลัพธ์ที่ได้ทั้งหมดมาเปรียบเทียบกัน เพื่อให้สอดคล้องกับเงื่อนไขเเละ Objective Fn.
  7. ****ถ้าหากสมการมีเพียง2ตัวแปร เราควรจะหาคำตอบของสมการด้วยวิธีวาดกราฟ
Eg.
วาดกราฟตามเงื่อนไขทีละขั้นตอน โดยกำลังหนดลูกศรเเละระบุสมการที่มาโดยระเอียด
การจะหาค่า Z ก็สามารถเเทนค่าแต่ละจุดที่อนุ่ในบริเวณภายใต้เงื่อนไขลง สมการ Z ทีละจุดเพื่อเทียบว่า ค่าZไหนมากน้อยกว่ากัน
การหาค่าตัวแปรที่ไม่ทราบค่าก็สามารถแทนอีกตัวแปร =0 แล้วแก้สมการ
สมการเส้นตรง Z=3X1 + 2X2 เกิดจากการกำหนดค่า Z แล้วให้ตัวแปรตัวนึง =0 เพื่อหาเส้นตรง








Reversed Simplex (ฉบับปรับปรุง)










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

ความคิดเห็น

บทความที่ได้รับความนิยม