A Study On The Transportation Problem

Based on researches of standard transportation problem and its efficient algorithms, this thesis provides the general form of the loose constrained transportation problem and the method of transforming it into standard transportation problem.The transportation problem is a very important linear programming problem in Operational Research and Optimization, and it is of great applicable and theoretical value. On one hand, with concepts such as feasible basis and feasible spanning tree, a strongly feasible basis can be achieved for one basic feasible solution only. If basic feasible solution doesn't degenerate, there is only one strongly feasible basis for it; if it does degenerate, there are more than one strongly feasible basis for it. We can prove the proposition with the concept of potential differ-ence sum:If all the feasible basis we get from tableau method are strongly feasible basis, they are different. We can employ first rule in tableau method to make sure the premise for above proposition is true, thus degeneracy problem is solved and Finite Termination can be achieved for the algorithm. According to the relations between feasible spanning tree and feasible so-lution, the algorithm will be transformed from simplex table into feasible spanning tree, then analogous star expression and parent node expression will be employed and realized with one dimension array, all operations of tableau method can be executed in these methods efficiently. Detailed procedures and code will be provided for further studies and application. On the other hand, compared with the standard transportation problem, there is a phenomenon of "the more, the less" in the loose constraint transportation problem. Based on previous researches, through transforming equality constraint into inequality constraint, a general form for loose constraint transportation problem is achieved. For general form of the transportation problem, previous solution is classification, which is very complex. Considering the characteristic of efficiency in the standard transportation problem algorithm, this thesis provides a method of transform-ing the loose constraint transportation problem into the standard transportation problem. Then introducing the loose constraint transportation problem, transformed the standard transporta-tion problem and their regularization problem. Employing various methods such as coordinate projection, rectangular transformation etc., provides the relation between the best solutions for these two problems mentioned above, and sets ranges for those parameters involved.