Транспортная задача в условиях неопределенности

Abstract

Досліджено ефективність застосування запропонованих А.А. Павловим загальних теоретичних положень для знаходження компромісного вирішення одного класу задач комбінаторної оптимізації в умовах невизначеності на прикладі вирішення транспортної задачі лінійного програмування. Досліджуваний клас задач характеризується тим, що: 1) критерій оптимізації є зваженою лінійною згорткою довільних числових характеристик допустимого розв’язку; 2) існує ефективний алгоритм розв’язання задачі в детермінованій постановці, який не дозволяє змінювати структуру обмежень; 3) під невизначеністю розуміється неоднозначність значень вагових коефіцієнтів, що входять в критерій оптимізації. Компромісні розв’язки знаходяться по одному з п’яти критеріїв. Сформульовано математичну модель транспортної задачі, в якій невизначеність обумовлена тим, що на етапі реалізації вирішення матриця питомих вартостей перевезень може приймати одне з декількох можливих значень. Описано практичні ситуації, що призводять до такої моделі. Метод знаходження компромісного розв’язку проілюстровано на прикладах кількох індивідуальних транспортних задач в умовах невизначеності. Дослідження підтвердило ефективність застосування на практиці загальних теоретичних положень і дозволило істотно розширити клас задач комбінаторної оптимізації в умовах невизначеності, для яких застосовано ці теоретичні результати.

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. 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 the deterministic formulation that does not allow changing the structure of constraints; 3) as the uncertainty, we understand the ambiguity of values of the weight coefficients included in the optimization criterion. We search for compromise solutions according to one of the five criteria. A mathematical model of the transportation problem is formulated, in which the uncertainty means that the matrix of transportation costs-per-unit can take one of several possible values at the stage of the solution implementation. Practical situations which lead to such a model are described. We illustrate the method of finding a compromise solution by several transportation problem instances under uncertainty. The research confirmed the efficiency of practical application of the general theoretical principles and allowed one to expand significantly the class of combinatorial optimization problems under uncertainty for which these theoretical results are applicable.