อสมการสมเหตุสมผลและการแปลงเพื่อหาผลเฉลยสำหรับปัญหาการกำหนดงานนัยทั่วไปอย่างมีประสิทธิภาพ

สายฝน เทียมแก้ว

Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/16016

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	กรุง สินอภิรมย์สราญ	-
dc.contributor.author	สายฝน เทียมแก้ว	-
dc.contributor.other	จุฬาลงกรณ์มหาวิทยาลัย. คณะวิทยาศาสตร์	-
dc.date.accessioned	2011-09-26T08:57:55Z	-
dc.date.available	2011-09-26T08:57:55Z	-
dc.date.issued	2550	-
dc.identifier.uri	http://cuir.car.chula.ac.th/handle/123456789/16016	-
dc.description	วิทยานิพนธ์ (วท.ม. )--จุฬาลงกรณ์มหาวิทยาลัย, 2550	en
dc.description.abstract	ปัญหาการกำหนดงานนัยทั่วไป เป็นปัญหากำหนดการจำนวนเต็มประเภทหนึ่ง ซึ่งหาผลเฉลยโดยใช้วิธีขยายและจำกัดเขตทั่วไป แต่สำหรับปัญหาการกำหนดงานนัยทั่วไปมีโครงสร้างของตัวแบบที่เฉพาะเจาะจง ซึ่งมีแนวโน้มในการปรับปรุงจำนวนรอบการคำนวณด้วยวิธีขยายและจำกัดเขต วิทยานิพนธ์ฉบับนี้ เรานำเสนอหลักการปรับปรุงจำนวนรอบการคำนวณของวิธีขยายและจำกัดเขต โดยใช้วิธีเพิ่มอสมการอย่างสมเหตุสมผลและการแปลงปัญหา การใช้อสมการอย่างสมเหตุสมผล ช่วยลดบริเวณที่เป็นไปได้ของกำหนดการเชิงเส้นผ่อนปรน โดยไม่กำจัดผลเฉลยที่เป็นไปได้ของปัญหาการกำหนดงานนัยทั่วไป การแปลงปัญหา กำหนดจุดเริ่มต้นใหม่ให้กับปัญหาการกำหนดงานนัยทั่วไป ซึ่งเป็นตัวแทนผลเฉลยที่ดีกว่าจุดเริ่มต้นเดิม เราใช้ซอฟต์แวร์เปิด GLPK (GNU Linear Programming Kit) เพื่อเปรียบเทียบจำนวนรอบการคำนวณระหว่างวิธีขยายและจำกัดเขตแบบเดิมกับวิธีแบบใหม่ของเรา งานวิจัย เราใช้จำนวนรอบการคำนวณน้อยกว่า 40% เมื่อเทียบกับวิธีขยายและจำกัดเขตแบบเดิม	en
dc.description.abstractalternative	The generalized assignment problem is one of the integer programming problem that has been solved by the general branch-and-bound. Due to a special structure of the generalized assignment problem, it is possible to improve the number of iterations of the branch-and-bound method. In this thesis, we improve the number of branch-and-bound iterations by applying the valid inequalities and transformation. The valid inequalities reduce feasible region of the linear programming relaxation but maintain integer feasible solutions. Transformation defines a new starting point for the generalized assignment problem, which is a better candidate than the original starting point. We use open source GLPK (GNU Linear Programming Kit) to compare the number of iterations between the original branch-and-bound method with our methodology, our method uses 40% less iterations than the original branch-and-bound method.	en
dc.format.extent	962551 bytes	-
dc.format.mimetype	application/pdf	-
dc.language.iso	th	es
dc.publisher	จุฬาลงกรณ์มหาวิทยาลัย	en
dc.relation.uri	http://doi.org/10.14457/CU.the.2007.218	-
dc.rights	จุฬาลงกรณ์มหาวิทยาลัย	en
dc.subject	อสมการ	en
dc.subject	การโปรแกรมเชิงเส้น	en
dc.title	อสมการสมเหตุสมผลและการแปลงเพื่อหาผลเฉลยสำหรับปัญหาการกำหนดงานนัยทั่วไปอย่างมีประสิทธิภาพ	en
dc.title.alternative	Valid inequalities and transformations for efficient solving the generalized assignment problem	en
dc.type	Thesis	es
dc.degree.name	วิทยาศาสตรมหาบัณฑิต	es
dc.degree.level	ปริญญาโท	es
dc.degree.discipline	วิทยาการคณนา	es
dc.degree.grantor	จุฬาลงกรณ์มหาวิทยาลัย	en
dc.email.advisor	krung@math.sc.chula.ac.th	-
dc.identifier.DOI	10.14457/CU.the.2007.218	-
Appears in Collections:	Sci - Theses

Files in This Item:

File	Description	Size	Format
Saiphon_Th.pdf		939.99 kB	Adobe PDF	View/Open

Show simple item record