A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem

A combination of a new kind of dual relaxation with the signature idea provides a non-dual signature method for the assignment problem. The dual relaxation is also extended to transportation problems. The algorithms, which consist of consecutive stages each one being a set of simplex type pivots, can be considered as a generalization of the dual simplex method. From the computational point of view, the algorithms possess a new monotonic property, namely, during a stage of the algorithms the per unit improvement of the objective function is non-decreasing.