On solving linear programming problems with embedded network structure

• Autorzy: Krystian Zorychta
• Języki publikacji: EN

Abstrakty

EN

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.

PL

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.

Słowa kluczowe

EN

Linear programming

• Wydawca: Polish Mathematical Society
• Czasopismo: Mathematica Applicanda
• Rocznik: 1991
• Tom: 19
• Numer: 33

Daty

wydano

1991

online

2016-10-28

Twórcy

autor

Krystian Zorychta

Identyfikatory

DOI

10.14708/ma.v19i33.1776