An Improved Labeling Algorithm for Transportation Simplex Method.

Abstract

The transportation problem is one of the special problems in the linear programming model. Which can be written in the form of linear programming model, and be able to solve the problems with simplex algorithm. This research focus on developing program computer to solve the transportation problem by using the transportation simplex method. Solve the reduced cost coefficient without using the simplex tableau, but only the help from looping step method. Computer electronic cannot be making a decision with complex human thought so it needs to be consider using the appropriate way to solve the problem. The solver too using is labeling algorithm from network flow. This research will improve the labeling algorithm calling this “Improved Labeling Algorithm”. Then using it to solve the transportation problem which must be a problem in the form of a balanced transportation problem. The researcher will test it with 45 problems by divined it into three groups. Group 1, 15 questions with the problem of constant demand. Group 2, 15 questions with the problem of constant production. Group 3, 15 questions with the problem of increasing the size of node of demand and node of supply. After the that the researcher will find the weak point of the program for anyone who interested to study and improve it further. The result of the research shown that the solution from the program give the appropriate answer for the problem using in the test. The researcher will also using excel solver to confirm the and prove the answer if it was true.

ปัญหาการขนส่งเป็นปัญหาพิเศษลักษณะหนึ่งของแบบจำลองกำหนดการเชิงเส้น ซึ่งสามารถเขียนให้อยู่ในรูปแบบของแบบจำลองกำหนดการเชิงเส้นได้ และสามารถแก้ปัญหาได้ด้วยขั้นตอนวิธีซิมเพล็กซ์ งานวิจัยนี้มุ้งเน้นการพัฒนาโปรแกรมคอมพิวเตอร์เพื่อช่วยในการแก้ไขปัญหาการขนส่ง ด้วยวิธีซิมเพล็กซ์ของตัวแบบปัญหาการขนส่ง ซึ่งจะต้องทำการหาค่าสัมประสิทธิ์ค่ารีดิวซ์คอสต์ แต่ไม่สามารถใช้ตารางซิมเพล็กซ์ได้ ต้องใช้ขั้นตอนในการวนลูปเข้ามาช่วย เนื่องจากคอมพิวเตอร์ไม่สามารถมองออกได้ว่าควรไปทางซ้ายหรือทางขวา ควรขึ้นหรือลง จึงได้พิจารณาถึงขั้นตอนวิธีการไหลในข่ายงานที่เหมาะสมที่จะนำมาแก้ไขปัญหา คือขั้นตอนวิธีของลาเบล โดยงานวิจัยนี้จะทำการปรับปรุงขั้นตอนวิธีลาเบล โดยเรียกขั้นตอนวิธีนี้ว่า Improved Labeling Algorithm หลังจากนั้นนำมาพัฒนาเป็นโปรแกรมเพื่อช่วยในการแก้ไขปัญหาการวางแผนการผลิตรวม โดยจะต้องเป็นปัญหาในรูปแบบของปัญหาการขนส่งแบบสมดุล ผู้วิจัยจะทำการทดลองกับปัญหาทั้งหมด 45 ข้อ เพื่อทดสอบโปรแกรม โดยแบ่งเป็นปัญหาความต้องการสินค้าคงที่จำนวน 15 ข้อ ปัญหาความสามารถในการผลิตคงที่จำนวน 15 ข้อ และปัญหาที่ทำการเพิ่มลดขนาดโหนดของความต้องการสินค้าและโหนดของความสามารถในการผลิตจำนวน 15 ข้อ จากนั้นทำการหาจุดอ่อนของโปรแกรม สำหรับผู้ที่สนใจจะศึกษาและพัฒนาต่อไป ผลการวิจัยพบว่า ผลเฉลยที่ได้จากการทดสอบของโปรแกรมเป็นผลเฉลยที่เหมาะสมที่สุดในทุกโจทย์ปัญหาที่นำมาทำการทดสอบครั้งนี้ โดยผู้วิจัยทำการทดสอบเทียบกับการใช้ Excel Solver เพื่อยืนยันความถูกต้องของผลเฉลย