Minimax under transportation constraints
The book is a true monograph written on the topic of a special type of transportation problems. Within the book the balanced transportation problem with minimax criterion is considered. From the beginning, the authors direct their attention to the study of truncated polyhedra of the transportation problem. They try to answer the question, whether there exists a solution satisfying transportation constraints for given capacities and demands, so that no value of the associated variables exceeds a given bound. The authors derive an irreducible system of conditions based on the characteristic functions and prove that under these conditions the set of feasible solutions of the problem is nonempty. They develope algorithms that are able to find a solution of the bounded transportation problem. Together with the study, hereditary and uniform properties of transportation problem solution are introduced and proofs of necessity and sufficiency are given. In the next part of the book, integer transportation matrices are studied. A technique of problem reduction has been developed here and an algorithm for integer solution is given. Further, terms of extremal vector pairs and matrices are introduced for the instances, where transportation problem solutions consist of zeros and ones. Properties of these structures were broadly studied within the last part of the book. Here operations and metrics and defined kernel and hull on a set of zero-one transportation matrices are established and their properties are revealed. It is shown that the extremal matrices of a given dimension form a polyhedron and theorems are proved stating conditions under which a transportation problem solution is a vertex of the polyhedron or belongs to a face of it. To make the study of the individual chapters easier, the authors provide a number of examples and exercises, which clarify the terms and algorithms.
scientific article; zbMATH DE number 1321110