เทคนิคการสร้างแถวสำหรับแก้ไขปัญหาการจัดสรรเงินลงทุนเชิงจัดหมู่
คำสำคัญ:
ปัญหาการจัดสรรเงินลงทุนเชิงจัดหมู่, เทคนิคการสร้างแถว, โปรแกรมเชิงเส้นขนาดใหญ่, ตัวแบบทางคณิตศาสตร์บทคัดย่อ
งานวิจัยนี้มีวัตถุประสงค์เพื่อศึกษาการจัดสรรเงินลงทุนเชิงจัดหมู่ที่ศึกษาทุกทางเลือกการลงทุนภายใต้ทรัพยากรที่จำกัด โดยใช้เทคนิคการสร้างแถว จำนวนเงื่อนไขของทางเลือก (Combinatorial Constraints) ในตัวแบบทางคณิตศาสตร์เท่ากับ 2N-1 เงื่อนไข เมื่อ N คือจำนวนโครงการ ในกรณีที่ปัญหาการจัดสรรเงินทุนมีหลายโครงการทำให้จำนวนเงื่อนไขเกิดขึ้นมากตามไปด้วยส่งผลให้ตัวแบบทางคณิตศาสตร์มีขนาดใหญ่และอาจไม่สามารถหาคำตอบได้ ผู้วิจัยจึงใช้เทคนิคการสร้างแถว (Row Generation) เพื่อลดจำนวนเงื่อนไขในปัญหาการจัดสรรเงินลงทุนเชิงจัดหมู่ให้เหลือเฉพาะเงื่อนไขที่จำเป็นในการหาคำตอบ ผลของงานวิจัยพบว่า การแก้ปัญหาโดยใช้เทคนิคการสร้างแถวใช้เวลาน้อยกว่าการใช้โปรแกรมเชิงเส้นเมื่อมีจำนวนของโครงการตั้งแต่ 12 โครงการขึ้นไป ยกตัวอย่างเช่น กรณีที่มี 20 โครงการ การหาคำตอบด้วยวิธีเชิงเส้นใช้เวลามากกว่า 48 ชั่วโมง กรณีที่มี 50 โครงการ การหาคำตอบด้วยเทคนิคการสร้างแถวใช้เวลาไม่เกิน 5 นาที
เอกสารอ้างอิง
[2] G. Dantzig, R. Fulkerson, and S. Jonhson, “Solution of a large-scale travelling-salesman problem”, Journal of the Operation Research Society of America, pp. 393-410, 1954.
[3] C. Gilmore, and E. Gomory, “A linear programming approach to the cutting-stock problem”, Operations Research, Vol. 9, No. 11, pp. 849–859, 1961.
[4] M. Gamache, F. Soumis, G. Marquis, and J. Desrosiers, “A Column generation approach for large-scale aircrew rostering problems”, Operations Research, Vol. 47, pp. 247-263, 1999.
[5] P. Charnsethikul, “A column generations approach for the products mix based semi-infinite linear programming model”. International Journal of Management Science and Engineering Management, Vol. 6, No. 2, 105-108, 2011.
[6] H. M. Weingartner, “Criteria for programming investment project selection”, Journal of Industrial Economics, Vol. 11, pp. 65–76, 1966.
[7] H. M. Weingartner, “Capital budgeting of interrelated projects: survey and synthesis”, Management Science, Vol. 12, pp. 485-516, 1966.
[8] M. Padberg M, M.J. Wilczak, “Optimal project selection when borrowing and lending rates differ”, Mathematical and Computer Modelling, Vol. 29, pp. 63-78, 1999.
[9] P. K. De, D. Acharya, K. C. Sahu, “A chance-constrained goal programming model for capital budgeting”, Journal of the Operational Research Society, Vol. 33, pp. 635-638, 1982.
[10] M. A. Odijk, “A constraint generation algorithm for the construction of periodic railway timetables”, Transportation Research, Vol. 30, No. 6, pp. 455-464, 1995.
[11] L. Williams, J. Fisher, and A. Willsky, “A constraint generation integer programming approach to information theoretic sensor resource management”, IEEE/SP 14th Workshop on Statistical Signal Processing, pp. 59-63, 2007.
[12] F. Croce, C. Koulamas, and V. T'kindt, “A constraint generation approach for the two-machine flow shop problem with jobs selection”, Combinatorial Optimization: Third International Symposium (ISCO 2014), pp. 198-207, 2014.
[13] A. C. Suyabatmaz, G. Sahin. “A column-and-row generation algorithm for a crew planning problem in railways”. Operations Research Proceedings, pp.335-340, 2011.
[14] İ Muter, Ş Birbil, and K. Bülbül, “Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows”, Mathematical Programming, Vol. 142, No. 1-2, pp. 47-82, 2013.
