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ตัวแปรที่+ไปตัวเดียว  

2. ตัวแปรที่เพิ่มเข้ามาคือ ตัวแปรเทียม เอาไว้ใช้ให้เข้ารูประบบคาโนนิคอล เพื่อคำนวณตามเเบบ Simplex ต่อไป
3. หากอยู่ในรูป 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 ต่อไปฮะ อย่าลืมติดตามกันนะ