On solving linear programming problems with embedded network structure

W pracy przedstawiony jest uniwersalny algorytm rozwiązywania zagadnień optymalnej dystrybucji w sieci transportowej, poddanej dodatkowym ograniczeniom liniowym, czyli tzw. zadań programowania liniowego z wbudowaną strukturą sieciową. Algorytm ten funkcjonuje na zasadzie pierwotnej metody sympleksowej i opiera się na dekompozycji bazy na cztery bloki. Czynnikiem decydującym o efektywności algorytmu jest sposób realizacji operacji z udziałem bloku sieciowego. Dlatego szczególny nacisk położony jest w pracy na zaprojektowaniu struktur danych uwzględniających specyfikę tego bloku i pozwalających wykorzystać ją w pełni na poziomie implementacji.

A special partitioning algorithm for solving linear programming problems with embed-ded network structure is presented. As an example of such a problem the minimum-cost network flow problem under additional linear constraints can be considered. This algorithm is a primal simplex basis partitioning method that uses special updating and labeling procedures to accelerate computations involving the network linear programming interface. These procedures are discribed in detail to develop an efficient implementation of the method.