Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

การแก้ปัญหากำหนดการเชิงเส้นด้วยวิธีซิมเพล็กซ์

No description
by

Prapatsorn Khosonsuntithum

on 21 April 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of การแก้ปัญหากำหนดการเชิงเส้นด้วยวิธีซิมเพล็กซ์

วิธีซิมเพล็กซ์
คือ การแก้ปัญหาระบบอสมการโดยการกระทำซ้ำๆกันเริ่มจากคำตอบ มูลฐานเริ่มต้นที่เป็นไปได้ แล้วเปลี่ยนตัวแปรมูลฐานใหม่ครั้งละ 1 ตัว โดยพิจารณาจากตัวแปรที่ไม่เป็นมูลฐาน เรียกตัวแปรมูลฐานใหม่นี้ว่า ตัวแปรมูลฐานเข้า (Entering Basic Variable) สำหรับตัวแปรมูลฐานเดิมที่ถูกแทนที่ด้วยตัวแปรมูลฐานใหม่จำกำหนด
ให้เป็นตัวที่ไม่เป็นมูลฐาน เรียกตัวแปรนี้ว่า ตัวแปรมูลฐานออก (Leaving Basic Variable) การแก้ปัญหาโดยวิธีซิมเพล็กซ์ จะต้องมีการสร้างรูปแบบกำหนดการเชิงเส้นให้อยู่ในรูปแบบมาตรฐาน คือ เปลี่ยนข้อจำกัดที่อยู่ในรูปอสมการให้เป็นสมการที่สมมูลกัน
เขียนข้อจำกัดให้อยู่ในรูปสมการข้อจำกัดที่สมมูลกันโดยใช้ตัวแปรขาด (Slack Variable)
(1) แปลง Original LP model ให้อยู่ในรูป Standard form
1.1 - ถ้าข้อจำกัดเป็นอสมการแบบ  ให้บวก LHS ด้วย slack variable
- ถ้าข้อจำกัดเป็นสมการแบบ  ให้ลบ LHS ด้วย surplus variable แล้วบวก LHS ด้วย artificial variable
- ถ้าข้อจำกัดเป็นสมการ () ให้บวก LHS ด้วย artificial variable
1.2 - ให้สัมประสิทธิ์ของ slack variables และ surplus variables ใน objective function เป็นศูนย์เสมอ
- ให้สัมประสิทธิ์ของ artificial variables ใน objective function
มีค่าเป็น +M สำหรับปัญหา Minimization และ
มีค่าเป็น -M สำหรับปัญหา Maximization

ขั้นตอนการแก้ปัญหา LP ด้วยวิธีซิมเพล็กซ์
(2) การหา Initial Basic Feasible Solution (IBFS)
2.1 กำหนดให้ decision variables และ surplus variables (ถ้ามี) มีค่าเป็นศูนย์ นั่นคือ decision variables และ surplus variables จะกลายเป็น nonbasic variables ส่วนตัวแปรอื่น ๆ ที่เหลือจะเป็น basic variable
2.2 จำนวน basic variables จะเท่ากับจำนวนข้อจำกัด
(3) สร้างตารางซิมเพล็กซ์โดยใช้ข้อมูลใน (1) และ (2) จากนั้นให้คำนวณหาค่าในแถว Zj และ แถว (Cj – Zj)

ขั้นตอนการแก้ปัญหา LP ด้วยวิธีซิมเพล็กซ์
การแก้ปัญหากำหนดการเชิงเส้น
ด้วยวิธีซิมเพล็กซ์

(4)พิจารณาว่าคำเฉลยในตารางนั้นเป็น optimal แล้วหรือยัง โดยมีหลักการพิจารณาดังนี้
4.1
-สำหรับปัญหา Max. จะได้ optimal solution เมื่อ (Cj – Zj)  0 สำหรับทุกค่าของ j
-สำหรับปัญหา Min. จะได้ optimal solution เมื่อ (Cj – Zj)  0 สำหรับทุกค่าของ j
ถ้าคำเฉลยที่ได้เป็น optimal แล้ว ให้เอาค่าของ variables ต่าง ๆ (ทั้ง basic และ nonbasic variables) และค่า Z จากตารางสุดท้ายมาตอบ
4.2 กรณีที่คำเฉลยที่ได้ยังไม่เป็น optimal ให้พิจารณาหา entering variable ดังนี้
- สำหรับปัญหา Max. เลือก Xj ที่ค่า (Cj – Zj) เป็นบวกมากที่สุดมาเป็น entering variable
- สำหรับปัญหา Min. เลือก Xj ที่ค่า (Cj – Zj) เป็นลบและมีค่าต่ำสุดมาเป็น entering variable
เมื่อมี entering variable เข้ามาใน Basis หนึ่งตัว ก็จะต้องมี departing variable หนึ่งตัวออกไปจาก Basis เช่นกัน
4.3 การพิจารณาว่า basic variable ตัวใดจะต้องเป็น departing variable
(นั่นคือ กลายไปเป็น nonbasic variable ในตารางต่อไป) นั้น เราจะพิจารณาดูที่ test ratio.
Basic variable ตัวใดที่มี test ratio ต่ำสุด basic variable ตัวนั้นจะต้องออกไปจาก Basis และกลายมาเป็น nonbasic variable ในตารางต่อไป
4.4 การกำหนด Pivot element
Pivot element คือ สมาชิกที่อยู่ในแถวนอนที่ test ratio มีค่าต่ำสุด และอยู่ในแถวตั้ง
ของ Xj ที่เป็น entering variable


ขั้นตอนการแก้ปัญหา LP
ด้วยวิธีซิมเพล็กซ์
(5) การสร้างตารางใหม่ด้วยวิธีการพิวิต (Pivoting)
5.1 ใช้ pivot element เป็นศูนย์กลางการเปลี่ยนจากตารางหนึ่งไปสู่อีกตารางหนึ่ง
5.2 คำนวณหาค่าในแถว Zj
5.3 คำนวณหาค่าในแถว (Cj – Zj)

(6) ทำตามขั้นตอนที่ (4) ซ้ำอีก

ขั้นตอนการแก้ปัญหา LP
ด้วยวิธีซิมเพล็กซ์
Full transcript