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


1. จากรูปแบบโมเดลคณิตศาสตร์ของโปรแกรมเชิงเส้น
Max   Z = c1x1 + c2x2 + c3x3
a11x1 + a12x2 + a13x3 < b1
a21x1 + a22x2 + a23x3 < b2
a31x1 + a32x2 + a33x3 < b3

เขียนสมการเพื่อเพิ่มเติมตัวแปรช่วย ได้ดังนี้
Z -- c1x1 -- c2x2 -- c3x3 = 0
a11x1 + a12x2 + a13x3 + x4 = b1
a21x1 + a22x2 + a23x3 + x5 = b2
a31x1 + a32x2 + a33x3 + x6 = b3

ในการคำนวณต้องสร้างตารางผลลัพธ์เบื้องต้น ซึ่งผลที่ได้จะเป็นดังนี้

สังเกตุว่าตารางสัมประสิทธ์ของตัวแปรในส่วนเพิ่มเติมมีลักษณะเป็นแมทริกซ์แบบ indentity คือ มีค่าเพียง 0 และ 1 และ ค่า 1 มีค่าแทยง

2. หากพิจารณาค่าต่าง ๆ ในตารางที่เขียนขึ้นมา ซึ่งถือว่าเป็นการหาผลลัพธ์เบื้องต้น ดังนั้นจึงต้องพิจารณาผลลัพธ์ดังนี้

2.1 เริ่มต้นพิจารณาว่าตัวแปรเปลี่ยน x1, x2, x3 จะเริ่มจากเป็น 0 คือ x1, x2, x3 เป็น 0 โดยเป็นจุดเริ่มต้นต้องมีค่ามากกว่าหรือเท่ากับศูนย์

2.2 ค่าของสมการเป้าหมายซึ่งได้จาก z - c1x1 - c2x2 - c3x3 = 0 จะมีค่าทำให้   z   =   0   ด้วย

2.3 ค่าตัวแปรที่เพิ่มเข้า อ่านจากผลลัพธ์ได้
x4   =   b1
x5   =   b2
x6   =   b3
3. พิจารณาทดสอบผลลัพธ์ดูว่า ได้ผลลัพธ์ดีที่สุดแล้วหรือยัง จะเห็นว่า บางครั้งแม้แต่ผลลัพธ์เบื้องต้นก็เป็นผลลัพธ์ที่ดีที่สุดได้ แต่เราจะใช้วิธีทดสอบ

การทดสอบโดยใช้ให้ตัวแปร x1, x2, x3 โดยแทนค่า เช่น เริ่มจาก x1, x2, x3 = 0 จะได้ z = 0 จะเห็นว่า ค่า x1, x2, x3 แปรเปลี่ยนไปก็จะได้ค่าเปลี่ยนแปลงไป เช่น ถ้าเพิ่มค่า x3 z = c3x3   จะทำให้ค่า z เปลี่ยนไป
4. สิ่งที่ต้องการคือ ต้องการทำให้สมการเป้าหมายมีค่าเพิ่มขึ้น โดยพิจารณาหาตัวแปรที่เพิ่มค่า การเพิ่มค่าตัวแปรพิจารณาจากการให้ค่าตัวแปรแล้วสมการเป้าหมายเพิ่มค่าได้มากสุด

นอกจากนี้ยังต้องพิจารณาจากชุดตัวแปรเพิ่ม โดยการลดค่าตัวแปรเพิ่ม โดยเน้นว่าจะลดค่าตัวไหนก่อน คำตอบของผลลัพธ์ยังคงเป็นไปได้

เริ่มต้นจากค่า x4 = b1   x5 = b2   x6 = b3

ในการที่จะทำให้ x2 มีค่าเพิ่มขึ้น จะต้องหาค่าตัวที่ลดลงเพื่อเพิ่มค่าให้ x2 ได้มากที่สุดภายใต้เงื่อนไข โดยการลดค่าของตัวแปรเพิ่มต้องไม่ใช้ค่าติดลบ จากสมการเงื่อนไขจึงต้องพิจารณาการลดค่า x4, x5, x6 การลดค่าจะลดตัวไหนจะต้องเลือกให้อยู่ภายใต้เงื่อนไขทั้งหมด

การพิจารณาจะพิจารณาจากผลหารที่เกิดจากผลลัพธ์ค่าตัวแปรในตารางและแถวตั้งของค่าตัวแปรเปลี่ยนที่จะเพิ่มค่า  x2 จะได้ผลหารเป็น
b1/a12 b2/a22 b3/a32 เลือกผลหารน้อยสุด แสดงเป็นตัวลดค่าของตัวแปรเพิ่มตามแนวนอน คือ x4x5หรือ x6 เช่น ถ้าพิจารณาแล้วพบว่า   b2/a22 น้อยสุด ตัวแปรที่จะลดคือ   x5

พิจารณาได้ b2/a22 มีค่าน้อยสุด เราเลือกที่ x2 เพื่อเพิ่มค่า และลดค่า x5

หากเมื่อดูจากแถว x5 ในแนวนอน จากค่าที่เราเปลี่ยน >a22x2 + x5 = b2 โดยที่ขณะนี้ x1x3 ยังเท่ากับศูนย์อยู่

เมื่อลดค่า x5 ให้เป็น 0 x2 จะเท่ากับ b2 a22 เราจึงแทนค่า x ด้วย b2/a22 ในตาราง โดยวิธีหารแถวนอนของตัวแปรอินพุต และแถวนอนของตัวแปรเอาท์พุต ซึ่งจะได้ค่าเป็น 1 เราเรียนจุดนี้ว่าจุด pivot

จากจุด pivot เราทำให้สัมประสิทธ์อื่นในแนวสดมภ์ เป็น 0 ผลจะทำให้ z มีค่าสูงขึ้น

ให้ทำซ้ำไปจนกว่าจะได้ผลลัพธ์ดีที่สุด


ที่มา: รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์