เรื่องเกี่ยวกับ linear programming รบกวนผู้เชี่ยวเลขด้วยครับ.............

ผมมี สมการจุดประสงค์อ่ะครับ ดังนี้


C = 30x + 90y + 120s + 60t โดยมีข้อมูลต่างๆดังนี้ ครับ


x,y,s,t >= 0


x + y >= 40


s + t >= 45


x + s >= 30


y + t >= 35




นี่อ่ะครับ ใครช่วยทำให้ดูอย่างละเอียดฟน่อยนะครับ ขอบคุณมากครับ คิดมาหลายสัปดาห์แล้ววววว...... (ไม่ออกอ่ะสิ)
30 พ.ย. 2544 15:32
27 ความเห็น
15963 อ่าน


ความคิดเห็นที่ 1  ทอทหาร (Guest)

ต้องการ Simplex วิธีไหนล่ะครับ


1. ถ้าใช้ Big-M method ก็จะทำ 5 รอบ (ตรวจสอบจากโปรแกรม)


2. ถ้าใช้ Duality ก็ทำ 3 รอบ (ตรวจสอบจากโปรแกรม)


3. Two-Phase ยังไม่ได้ลองครับเพราะต้องทำด้วยมือ




อันนี้ผมเดาเอาว่าโจทย์ต้องการหา minimize นะครับ เพราะว่าไม่ได้บอกมาครับ ว่าต้อง Maximize หรือ Minimize ก็คงบอกวิธีที่ต้องการมา และ โจทย์ต้องการ Maximize หรือ Minimize ครับ แล้วผมจะแสดงวิธีทำให้ดูครับ




ถ้าต้องการ โปรแกรมไปลองใช้ที่สะดวกหน่อยครับ คือ WinQSB ครับ จะใช้ Big-M Method ในการหาค่า max หรือ min ครับ ก็ลองไป download ใช้ได้ที่นี่ครับ http://academic-services.com/download/software/winqsb.zip ใช้ไม่ยากครับ




ปล. -- ก็ตามหาผมได้ที่ตาม e-mail หรือ จะเข้าไปฝากข้อความใน webboard ของผมได้ที่ http://thai-military.net ครับ
27 พ.ย. 2544 23:40


ความคิดเห็นที่ 2 thetorque (Guest)

ลืมไปครับ หา minimize ครับผม
28 พ.ย. 2544 00:38


ความคิดเห็นที่ 3 ทอทหาร (Guest)

แล้วจะใช้วิธีอะไรครับ ใน 3 ข้อในความคิดเห็นที่ 1 น่ะครับ เพราะจะได้ทำถูกครับ เอาเป็นว่าเคยใช้วิธีไหนดีกว่าครับ ผมจะได้อธิบายได้สะดวกกว่าครับ เพราะว่า คิดว่าถ้าไม่เคยใช้ ก็คงจะสื่อสารลำบากนิดหน่อยครับ เพราะว่าอธิบายด้วยการเขียนเนี่ยไม่สะดวกเท่า การพูดครับ




ปล. ถ้าเคยใช้ Duality แล้ว นะครับ การใช้ Complementary Conditions จะสะดวกมากครับ ส่วน Big-M ก็จะยุ่งยากนิดหน่อยครับ แต่ก็เป็นวิธีเดียวกับ Simplex ทั่ว ๆ ไปครับ เพียงแต่เราต้องใส่ ตัวแปรเพิ่ม สองตัวไม่ใช้ตัวเดียวเพราะว่า เงื่อนไข เป็น >= ครับ สำหรับ Two Phase นั้นก็คิดว่าจะทำนานที่สุดในกรณีนี้มั้งครับ เพราะต้องทำสองขั้นตอนครับ
28 พ.ย. 2544 01:23


ความคิดเห็นที่ 4 มะนาว (Guest)

4 ตัวแปร... อืม ใช้มือทำไม่ได้เหรอครับ?
28 พ.ย. 2544 10:11


ความคิดเห็นที่ 5 thetorque (Guest)

แฮะๆ คือว่า ผมไม่เคยทำพวกที่มี 4 ตัวแปรเลยอ่ะครับ 3 ก็ยังไม่เคย ไม่รู้จะเริ่มยังไง เอาเป็นว่า ท่านพี่ๆ ทั้งหลายช่วยเลือกวิธีที่ เป็นพื้นฐานที่สุดก็แล้วกันนะครับผม.......
28 พ.ย. 2544 11:58


ความคิดเห็นที่ 6 ทอทหาร (Guest)

เอาอย่างนี้ครับ การแก้ปัญหา Linear Programming: LP ถ้ามีตัวแปรมากกว่า 2 ตัว เราจะนิยมใช้ วิธีการที่เรียกว่า Simplex นะครับ ผมแนะนำว่าคงต้องไปอ่านหนังสือ ดูก่อนครับ ว่าเราจะต้องทำอย่างไร ผมคงจะอธิบายทั้งหมดลำบาก เอาอย่างนี้ครับ ผมไปหาเวบภาษาไทยมาให้จาก schoolnet เป็นบทความจากอาจารย์ ยืนครับ คิดว่าน่าจะทำความเข้าใจได้ง่ายนะครับ ลองไปอ่านดูนะครับ มีปัญหาแล้วกลับมาถามดีกว่าครับ




ลองเข้าไปอ่านดูก่อนนะครับที่ http://www.school.net.th/library/snet2/knowledge_math/simplex/simplex.htm
28 พ.ย. 2544 12:35


ความคิดเห็นที่ 7 มะนาว (Guest)

เริ่มจากค่าที่เป็นไปได้ของตัวแปรต่างๆก่อนนะ


เช่น อาจจะให้ อืม x=40, y=40, s=45, t=45


ค่า objective ที่ได้ก็คือ 12900


จาก function C = 30x + 90y + 120s + 60t


เราจะได้กำไรที่สุดเวลาลดค่า s ใช่เปล่า


1. ลองลดค่า s ลงให้มากที่สุดจนกว่า constraint จะไม่ให้อ่ะ


constraints ที่มีก็คือ s+t>=45, กับ x+s>=30 (รวมถึง s>=0)


เราสามารถลด s จนถึง 0 ได้เลย เพราะว่าทุกอย่างยัง satisfy อยู่


ค่าตอนนี้ก็คือ x=40, y=40, s=0, t=45, C=7500




2. ต่อมาพิจารณา C ก็จะพบว่า เราจะกำไรสุดถ้าเราลดค่าของ y


constraints ที่เกี่ยวก็คือ x+y>=40, y+t>35


เราก็สามารถลดค่า y=0 ได้เช่นเดียวกัน


ค่าตอนนี้ก็คือ x=40, y=0, s=0, t=45, C=3900


ตอนนี้ constraint ที่เป็น = แล้วก็คือ


x+y=40, s+t=45, s=0, y=0




3. ต่อมาเราก็พิจารณา ค่าของ C เราต้องการลดค่าของ t


constraints ที่เกี่ยวก็คือ s+t>=45 กับ y+t>=35


สังเกตุว่า s+t=45 ซึ่งแปรว่าเราลดค่าของ t ไม่ได้แล้ว ถ้าไม่เพิ่มค่าของ s


แต่ว่า ทุกๆ unit ของค่าของ t ที่เราลดได้เราจะกำไรไป 60


แต่เราต้องเสีย 120 ไปกับค่าของ s ดังนั้นมันไม่คุ้มที่จะลดค่าของ t




4. ลองลดค่า x


เราก็มีเงื่อนไขว่า x+y>=40 แต่ตอนนี้ x+y=40 แล้ว


และด้วยเหตุผลเดียวกับข้อ 3. ทำให้มันไม่คุ้มที่จะลดค่าของ x อีก




5. สรุปคือเราไม่สามารถจะ "ขยับ" ค่าของ x,y,s,t


เพื่อที่จะเปลี่ยน objective ให้ดีขึ้นได้อีกแล้ว


=> ตอนนี้เราอยู่ที่ local optimum แล้ว




เนื่องจากเงื่อนไขเป็น linear และ objective เป็น linear


local optimum = global optimum


ได้คำตอบจนได้




วิธี simplex ที่คุณทอทหาร บอกก็ใช้ idea แบบนี้แหล่ะครับ


ปรับค่าของ ตัวแปรไปเรื่อยๆ แต่มันจะยุ่งกว่านี้หน่อยนะครับถ้าตัวแปรเยอะๆ
28 พ.ย. 2544 13:38


ความคิดเห็นที่ 8 มะนาว (Guest)

เฮือก เพิ่งเข้าไปดูตาม link ที่ทอทหารให้มาครับ


ไม่คิดว่าใน schoolnet จะมีเรื่องพวกนี้อยู่ด้วย สมัยเป็นนักเรียนนี่ไม่เคยได้รู้เลยครับ


ปล. คุณทอทหารครับ เข้า http://thai-military.net มิได้ขรับ
28 พ.ย. 2544 13:56


ความคิดเห็นที่ 9 ทอทหาร (Guest)

ก็ผ่านเอากระทู้มาฝาก ผมเคยตอบไว้ในหว้ากอมานานแล้วครับ เพื่อช่วยให้เกิดความเข้าใจมากยิ่งขึ้นครับ http://pantip.inet.co.th/cafe/wahkor/topicstock/X1145223.html




ผมเองมีปัญหา ที่จะอธิบายในคำศัพท์บางที่เป็น Technical Term แล้วจะใช้ภาษาไทยทดแทนครับ อย่าหาว่าอย่างโน้นอย่างนี้เลยนะครับ เพราะผมเองก็ไม่ทราบจริง ๆ ครับ สำหรับ เรื่องของคุณมะนาวที่กล่าวถึงนั้นเป็น เรื่องของ Sensitivity Analysis ครับ ซึ่งก่อนที่เราจะทำ Sensitivity Analysis ได้นั้นเราต้องทราบ ว่า Basic Feasible Solution: BFS (ไม่รู้ว่าภาษาไทยใช้อะไร) ที่นำมาพิจารณานั้น optimum ครับ ซึ่งโดยส่วนใหญ่เราก็จะใช้ Simplex ในการหาครับ ถ้าเราไม่ใช้ Simplex เลย เราก็คงต้องใช้ การแทนค่าจากจุดตัด (extreme point) ของ constraint ทั้งหมด แล้วมาหาดูว่า ค่าใดน้อยที่สุด ค่านั้นก็จะคือ global optimum ครับ




สำหรับ simplex นั้นจะเป็นวิธีการที่เป็น heuristic ครับ คือไม่รับประกันว่าเราจะหา optimal solution จริง ๆ หรือที่เรียกว่า global optimum ครับ แต่ก็เป็นวิธีที่เรียกได้ว่าแพร่หลาย และสะดวกที่สุดครับ
28 พ.ย. 2544 14:13


ความคิดเห็นที่ 10 ทอทหาร (Guest)

เรื่อง http://thai-military.net ผมก็เข้าได้นิครับ เพราะว่า server ตั้งอยู่ที่ apartment ของผมเองครับ เปิด 24 ชม. 7 วันครับ ตอนนี้ server ก็ไม่มีปัญหาอะไรครับ ถ้าเข้าไม่ได้ลอง http://37th.net ดูสิครับ ส่วนใหญ่ผมไม่ค่อยได้เขียนเรื่องวิชาการลงในเวบผมหรอกครับ ผมจะเขียนเรื่องราวเกี่ยวกับทหารมากกว่าครับ แต่ก็ยินดีครับ ที่จะแวะมาเยี่ยมเยียนครับ
28 พ.ย. 2544 14:17


ความคิดเห็นที่ 11 fahcram (Guest)

อืม Simplex ยังเป็น Heuristicอีกเหรอครับ




Simplex นี่ก็หา จุด opt ได้เพียงแต่มีปัญหาที่จุด degenerate เท่านั้นเอง ถึงแม้ coplexity จะไม่ดี แต่โดยเฉลี่ยแล้ว Simplex ก็ทำงานได้ดีแล้วนะครับ




อยากให้ช่วยอธิบายหน่อยครับว่าทำไม Simplex ไม่รับประกันว่าจะหา global opt ได้นะครับ
30 พ.ย. 2544 04:35


ความคิดเห็นที่ 12 มะนาว (Guest)

ผมว่าถ้าเป็น linear programming นะครับ


Simplex หา global optimal ได้แน่ๆ ครับ


(ถ้าจัดการไม่ให้มัน cycling ได้---เพราะบางทีมันเอาตัวแปรเข้าตัวแปรออกแล้วติดลูปได้


ต้องมีวิธีว่าจะเอาตัวไหนเข้าก่อนเข้าหลังอ่ะครับ)


เพราะว่า ปัญหาเป็น convex optimization, ถ้าหา local optima ได้ก็ได้ global optima ด้วย




ผมคิดว่าเค้าหมายความว่าถ้าพูดถึงปัญหา optimization ทั่วไปมากกว่าหรือเปล่า?
30 พ.ย. 2544 09:59


ความคิดเห็นที่ 13 GGG (Guest)

Use Excel:


Choose Tool --> Solver




If you don't have solver, tool -> add-in--> solver






The answer


X = 40 t= 45 s,y =0


c = 3900
30 พ.ย. 2544 10:24
Solver




If you don't have solver, tool -> add-in--> solver






The answer


X = 40 t= 45 s,y =0


c = 3900
--> 

ความคิดเห็นที่ 14 ทอทหาร (Guest)

ก็ต้องขออภัยที่ไม่ได้เข้ามาดูหลายวันครับ เพราว่างานยุ่งนิดหน่อยครับ สำหรับเรื่อง heuristic กับ algorithm ก็ต้องขออภัยครับ ที่ไม่ได้แยกระหว่าง 2 domains คือ ระหว่าง Linear Programming Problem: LPP กับ Non-Linear Programming Problem: NLPP ครับ เพราะโดยความเป็นจริงแล้ววิธีการเแบบ simplex นั้น จะใช้ได้ทั้ง 2 domains ใน LPP นั้นจะใช้เรียกว่า simplex method ส่วนที่ใช้ใน NLPP ก็จะเรียกว่า convex simplex method ทั้งสองจะใช้หลักการเดียวกันคือ การหาค่า Basic Variable: BV ออกนำไปสลับกับ Non Basic Variable: NBV แล้วนำ NBV ที่เลือกมาเป็น BV แล้วก็หาไปเรื่อย ๆ optimum point ไปเรื่อย ๆ ใน domain ของ LPP simplex จะเป็น algorithm เพราะว่าจะหาค่า global optimal ได้เสมอ ครับ แต่ ใน NLPP นั้นจะเป็น heuristic เพราะไม่จำเป็นว่าจะต้องหา global optimal เจอ พอเจอ local ก็จะหยุด ผมเองเวลานึกถึง simplex ก็ไม่ได้นึกถึงแต่ LPP อย่างเดียว แต่นึกถึงกรณีอื่น ๆ ด้วย ครับ ก็เลยเขียนไปว่า เป็น heuristic ครับ แต่ถ้าระบุว่าเป็น ใน LPP แล้วก็จะเป็น algorithm ครับ ขอบคุณครับ ที่ช่วยทักท้วงครับ
1 ธ.ค. 2544 15:32


ความคิดเห็นที่ 15 ขอโจทย์หน่อย (Guest)

อยากได้โจทย์เรื่อง simplex เป็นภาษาอังกฤษหน่อยค่ะ
10 ก.พ. 2549 15:46


ความคิดเห็นที่ 16 Megabyte (Guest)

C = 30x + 90y + 120s + 60t

C = (30x + 30y)+ 60y + 60s + (60s + 60t)

C = 30(x+y) + 60(s+t) + 60(y+s)



#x + y >= 40 ดังนั้น x + y น้อยที่สุด= 40 => x+y=40

#s + t >= 45 ดังนั้น s + t น้อยที่สุด= 45 => s+t=45



C = 30*40 + 60*45 + 60(y+s)

C = 3900 + 60(y+s)



#x,y,s,t >= 0 ดังนั้น (y+s) น้อยที่สุด= 0 => y,s=0



C = 3900 + 60*0

C = 3900 ; y,s=0; x=40; t=45;
10 ก.พ. 2549 21:50


ความคิดเห็นที่ 17 โดย a_Vcharkarn

วิธี Big M ครับ อธิบายเท่าที่จะพิมพ์ไหว
1. กรอกสัมประสิทธิ์จากสมการที่โจทย์บอกมาลงในตารางให้ได้ตามstep1
2. หัวตาราง
{C-30X-90Y-120S-60T-MA1-MA2-MA3-MA4=0}
เป็นสมการ C นี่เอง ใช้วิธี Big M จะมีตัวแปร M, A1, A2, A3, A4 เพิ่มขึ้นมาจาก ซิมเพลกซ์พื้นฐาน (ซิมเพลกซ์พื้นฐานมีแค่ แสลกซ์(slack) S1, S2, S3, S4)
3. เริ่มแรก สัมประสิทธิ์หน้า A1, A2, A3 & A4 เท่ากับ -M ให้ทำลายสัมประสิทธิ์หน้า ตัวแปรพวกนี้ ให้เป็น0
4. จะminimizeค่าC จึงให้มองหาใน {-30+2M, -90+2M, -120+2M, -60+2M, -M, -M, -M, -M, 0, 0, 0, 0} ตัวไหนเป็นค่าบวกบ้าง? ตอบ->{-30+2M, -90+2M, -120+2M, -60+2M} เป็นบวก ตัวไหนมีค่าสูงสุดให้เริ่มออฟติไมซ์ก่อนตามSimplex algorithmใช่ไหม? -30+2M มีค่าเป็นบวกสูงสุดมากกว่าใคร เพราะฉะนั้นทำก่อน...
5. ใช้บรรทัดที่3 เป็นพิวอทโรว์(Pivot Row) ก็จะผ่านจากStep1 ไป Step 2
-30+2M ถูกRow operation ไปด้วย 30-2M เหลือ 0
6. Step2
{-90+2M, -60+2M, M-30} สามตัวนี้เท่านั้นมีค่าบวกซึ่งเราจะต้องออฟติไมซ์มันซะ คอลัมน์อื่นๆปล่อยเอาไว้ไม่ต้องทำไร
7. -60+2M เป็นค่าบวกสูงที่สุดในสามตัวนี้ เพราะฉะนั้นจะพิวอทที่คอลัมน์นี้
8. step 3 เหลือ {M-30, M-60} เป็นค่าบวกที่จะออฟติไมซ์, M-30 มีค่ามากกว่าจึงทำก่อน
9. step มีค่าบวก สองค่า {M-120, M-60} M-60 เป็นค่าบวกที่มากกว่าจึงออฟติไมซ์คอลัมน์นี้
10. พิจารณา {0, -60, -60, 0, -30, -60, 0, 0, 30-M, 60-M, -M, -M} พบว่า ไม่เหลือค่าบวกแล้ว ดังนั้น 3,900 จึงเป็นค่าCminimum ของสมการทั้งหลายที่เขียนมาข้างต้น
11. [S3, S4, X, T]=[10, 10, 40, 45] ตัวแปรอื่นๆ ได้แก่ [Y, S, S1, S2, A1 ,A2, A3, A4]=[0,0,0,0,0,0,0,0]
12. สังเกตว่า ค่าC ตั้งต้นจาก 150M ->900+90M ->3000+20M ->3300+10M ->3,900 สัมประสิทธิ์หน้าMน้อยลงทุกๆstep(ค่าCกำลัง decrease ลงๆๆๆตาม Simplex Algorithm)
13. อธิบายหยาบๆ หากไม่เข้าใจก็โปรดอภัยด้วยครับ
28 ก.ค. 2549 01:56


ความคิดเห็นที่ 18 leechunmoo@hotmail.com (Guest)

คห.ที่7 หลักการของ simplex จะไม่เหมือนกับการวาดกราฟน่ะครับ โดยหลักการของ simplex จะเริ่มจากจุดที่เป็น solution ใดๆแล้ววิ่งไปจุกที่เป็น optimal โดยอาศัย ทบ. ที่ว่า จุด optimal จะอยู่ที่จุดตัดของระนาบ(หาข้อมูลต่อน่ะครับพูดไม่ถูก)

เช่นถ้ามี 3 ตัวแปรก็จะอยู่ตรงจุดที่มีอย่างน้อย 3 ระนาบตัดผ่านกันที่จุดเดียวซึ่งเราเรียกจุดพวกนี้ว่า extrem point และ optimal จะอยู่ในเซตของ extrem point ทั้งหมด เมื่อทำการ simplex ก็จะวิ่งไปที่ extrem point แต่ละจุดจนเจอจุด optimal
28 ก.ค. 2549 10:04


ความคิดเห็นที่ 19 leechunmoo@hotmail.com (Guest)

สำหรับคนที่ยังไม่รู้น่ะครับ Big-M , twophase, simplex ปกติแตกต่างกันตรงที่ว่า simplex ปกติ ซึงเราจะรู้ว่าอสมการเงื่อนไขไม่ใช่เซตว่าง เช่นพวก ทุกอสมการ <= ค่าบวกใดๆ จะมี 0 เป็นsolutionของสมการ ดังนั้นเราจึงมักเริ่มที่จุด 0 แต่ถ้ามีอสมการหนึ่ง <= ค่าลบใดๆ จะทำให้เราไม่ทราบว่าอสมการเงื่อนไขมี solution หรือไม่ ดังนั้นถ้าเราทราบจุดที่เป็นsolution แล้วเราก็ใช้simplex ปกติได้โดยไม่ต้องใช้Big-M , twophaseโดยเริ่มที่จุดนั้นๆ แต่เราไม่สามารถทราบได้ดังนั้นเราจึงมี 2 วิธีเพื่อแก้ปัญหาคือ Big-M , twophase โดยหลักการของ twophase phase1 จะวิ่งหา solution ก่อน จากนั้น phase2 จะวิ่งหาจากจุดที่เป็น solution ไปหา optimal โดยใช่ simplex ปกติ แต่twophase จะมีปัญหาในการเขียนโปรแกรมซึ่งสามารถเขียนได้ยาก จึงมีการพัฒนา Big-M ขึ้นมาเพื่อสะดวกในการเขียนมากกว่าโดยมีหลักการคือ อสมการเงื่อนไขถ้าไม่ใช่ set ว่างจะสามารถหาค่า M ค่าหนึ่งที่ใหญ่มากพอที่ทำให้เงื่อนไขเป็นจริงได้ เราจึงกำหนดตัวแปร M ขึ้นมาบวกที่อสมการ(ย้ายมาด้านซ้ายมือจึงเป็นลบนะครับ)จากนั้นก็ใช้ simplex ปกติ
28 ก.ค. 2549 10:29


ความคิดเห็นที่ 20 kerada_9@hotmail.com (Guest)

อยากได้ข้อมูลเกี่ยวกับการใช้ และรายล่ะเอียดเกี่ยวเกี่ยววิธีการต่างๆ นี้ค่ะ Dual Simplex, M method ,Bound method,

เข้าไปที่ไนหอ่ะคะถึงหาข้อมูลได้ ที่Google ไม่มีนะ
31 ส.ค. 2549 16:21

แสดงความคิดเห็น

กรุณา Login ก่อนแสดงความคิดเห็น