The Transportation Problem under Uncertainty

摘要

The efficiency of applying the general theoretical positions proposed by A.A. Pavlov to find a compromise solution for one class of combinatorial optimization problems under uncertainty by the example of solving the transportation linear programming problem is studied. The studied class of problems is characterized as follows: 1) the optimization criterion is a weighted linear convolution of arbitrary numerical characteristics of a feasible solution; 2) there exists an efficient algorithm to solve the problem in deterministic formulation that does not allow one to change the constraints structure; 3) by the uncertainty is meant the ambiguity of values of the weight coefficients included in the optimization criterion. We search for compromise solutions according to one of five criteria. A mathematical model of transportation problem is formulated in which uncertainty is caused by the fact that the matrix of transportation costs-per-unit can take one of several possible values at the stage of solution implementation. Practical situations which lead to such a model are described. The method of finding the compromise solution is illustrated by the examples of some individual transportation problems under uncertainty. The research confirmed the efficiency of practical application of the general theoretical principles and allowed us to expand significantly the class of combinatorial optimization problems under uncertainty for which these theoretical results are applicable.