ON THE SUBMODULARITY OF THE PROFIT FUNCTION IN A PROBLEM OF TRANSPORT PLANNING

In this paper the possibility of using the method of successive calculations to solve the transportation problem on the maximum profit is investigated. The feature of this problem is that a set of consumers isn’t defined and gets out from wider set of possible consumers by the criterion of a maximum of profit. Profit is calculated on the basis of consumer demand and prices, which are determined by the contract between the consumer and the company carrying out transportation. It is shown that this problem is reduced to maximization of the profit function defined on the set of all subsets of consumers. The submodularity of profit function is proved, that justified application of method of successive calculations to solve this problem.

дискретная оптимизация, частично упорядоченное множество, решетка, субмодулярность, супермодулярность, метод последовательных расчетов, задача размещения предприятий, транспортная задача,