Warianty tytułu
Algorytm rozwiązywania pewnej klasy odcinkami liniowymi, wielotowarowych problemów transportowych
Języki publikacji
Abstrakty
The main notation and a general scheme of solution of the problem are given in [4]. We briefly repeat the main moments. We call a point critical if linearity of the cost function is violated at it. The sets of critical points are described by linear equations which we call critical equations. We call a critical equation that contains only one variable the main one and this variable - the main variable. We call a point feasible if it satisfies problem condition (2). We call a feasible point a vertex if it is a critical point and satisfies no less than N = M-R = (L-T+l)*n linearly independent critical equations (R is a rank of system equations (2)). If the vertex satisfies more than N critical equations, then we call it degenerate. A set of points, satisfying N - 1 linearly independent critical equations of those that are satisfied by the vertex x, is called a critical line connected with the vertex. An arc load vector which satisfies at least one critical equation of the arc cost function is called a critical one. The method of problem solving is based on generation of such a sequence of vertices in which any two adjacent vertices belong to the same critical line, and the values of the cost function are diminishing as long as the vertex with the lowest value of function among all the adjacent vertices is reached [4]. We may distinguish such stages in solution of the problem [4]: formation of critical equations of the cost function; determination of the maximal number of critical lines connected with any vertex; finding of the initial vertex; realisation of the transition procedure from one vertex to another. A concrete expression of critical equations and the number of critical lines, connected with separate vertices naturally depend on a concrete piecewise-linear function. Meanwhile the transition procedure to another vertex is less dependent on concrete properties of piece-wise-linear functions. The procedure which really realised the stage of transition is described in detail in [4]. (fragment of text)
Problem rozważany w opracowaniu należy do klasy problemów programowania odcinkami liniowych. Poszczególne przypadki tego zagadnienia, tj. zagadnienie separowalne lub wypukłe, zostały dokładnie przeanalizowane i łatwo je rozwiązać w sensie lokalnego rozwiązania. Rozwiązania tych problemów opierają się zwykle na ich redukcji do problemu liniowego lub liniowego całkowitoliczbowego [1,2], Jednak ogólny problem programowania odcinkami liniowego programowania nie został dokładnie zbadany, ponieważ trudno jest rozwinąć efektywną, skończoną metodę dla znalezienia lokalnego rozwiązania dla wielotowarowego problemu transportowego, odcinkami liniowego, które nie jest separowalne ani wypukłe. Zaprezentowano skończony algorytm, który pozwala na znalezienie lokalnego rozwiązania dla specjalnej klasy wielotowarowych problemów transportowych. Algorytm ten jest konkretną realizacją metody opisanej w [4] dla przypadku, kiedy wydatki na transport zależą od całkowitej ilości wszystkich przewożonych produktów. (abstrakt oryginalny)
Rocznik
Numer
Strony
67--83
Opis fizyczny
Twórcy
autor
- Academy of Law Vilnius
Bibliografia
- Bazaraa M.S., Shetty C.M. (1979): Nonlinear Programming. Theory and Algorithms. John Willey and Sons, New York.
- Stenbrink P.A. (1978): Optimization of Transport Network. John Willey and Sons. London-New York-Sydney-Toronto.
- Christofidies N. (1976): Graph Theory. An Algorithmic Approach. Academic Press, New York.
- Dievulis G.: A Multicommodity transport flow problem with a special cost function as a problem of piecewise - linear programming.
- Dievulis G.: A method of contour optimisation for transport flow distribution.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171284849
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.