Market’s static model for software development based on a transport problem with non-fixed time additions

 
PIIS042473880019969-4-1
DOI10.31857/S042473880019969-4
Publication type Article
Status Published
Authors
Occupation: Senior Engineer
Affiliation: Joint-Stock Company Scientific and Production Association "Russian basic information technology"
Address: Moscow, Russian Federation
Occupation: Senior Research Scholar
Affiliation: Joint-Stock Company Scientific and Production Association "Russian basic information technology"
Address: Moscow, Russian Federation
Journal nameEkonomika i matematicheskie metody
EditionVolume 58 Issue 2
Pages97-111
Abstract

 

The authors describe the formulation of the market’s discrete-continuous static model for software development based on a transport problem with non-fixed time additions. In contrast to the existing transport problem with fixed cost surcharges, it is proposed to formulate a minimax setting in time with times that may contain a part that proportionate to the volumes of appointments. Thus, the authors come up with the idea of a hybrid formulation of transport problem with fixed cost surcharges and classical transport problem in time. Such problems arise when the total volume of vehicles which have to be used repeatedly on each route is limited, plus the fixed addition that arises taking into account the delay in making logistics decisions. It is shown that the set a discrete-continuous problem can be approximated from above by the classical transport problem in time, which can also be obtained according to the scheme used in the work by Balinski. The authors also describe an exact algorithm of the branch-and-bound method, based on the geometric interpretation of the problem, which decomposes into subproblems on non-empty faces of the polyhedral set of feasible solutions, which areconvex programming problems that can be numerically solved by the subgradient method described in work by Polyak. The calculation of the lower estimates of the criterion proposed in the work is reduced to the same problems. It is shown that the function of the best values of the criterion on the edges is not sub- or supermodular, as a function of a subset of pairs of indices corresponding to the positive values of the transportation volumes, which makes it impossible to use supermodular programming methods. In connection with the latter, the authors also describe the  optimal polynomial version of the branch-and-bound method, obtained by analogy with the solution of the multidimensional assignment problem, and a numerical example of its use. The authors describe interpretation of transport problem with non-fixed additions as a generalized assignment problem with non-fixed price discounts, taking into account the difference between the wholesale and retail prices. The authors come up with the ideaof the application for building digital platforms in the software development market for loading tasks for performers.

 

Keywordstransport problem with non-fixed time additions, approximation of the classical transport problem, geometric interpretation, branch-and-bound method, lower estimates of the criterion, ε-optimal version of the branch-and-bound method.
Received04.05.2022
Publication date18.06.2022
Number of characters33257
Cite  
100 rub.
When subscribing to an article or issue, the user can download PDF, evaluate the publication or contact the author. Need to register.

Number of purchasers: 0, views: 269

Readers community rating: votes 0

1. Balinski M.L. (1961). Fixed-cost transportation problems. Naval Res. Log. Quart., 8, 1, 41–54.

2. Debreu G. (1954). Valuation equilibrium and pareto optimum. Proceedings of the National Acad-emy of Sciences of the USA, 40, 588–592.

3. Ding X., Wang K., Gibbons P.B., Zhang X. (2012). BWS: Balanced work stealing for time-sharing multicores. Proceedings of the 7-th ACM European Conferens on Computer Sys-tems. EuroSys, 12. New York, 365–378.

4. Fedorov V.V. (1979). Numerical methods of maximin. Moscow: Nauka (in Russian).

5. Finkilstein Y.Y. (1976). Approximate methods and applied problems of discrete program-ming. Moscow: Nauka (in Russian).

6. Ford L., Fulkerson D. (1966). Flows in networks. Moscow, Mir (in Russian).

7. Khachaturov V.R., Khachaturov R.V., Khachaturov R.V. (2012). Optimization of supermodular functions (supermodular programming). Journal of Computational Mathematics and Ma-thematical Physics, 52, 6, 999–1000 (in Russian).]

8. Korbut A.A., Finkilstein Y.Y. (1969). Discrete programming. D.B. Yudin (ed.). Moscow: Nauka (in Russian).

9. Makarov V.L., Rubinov F.M. (1973). Mathematical theory of economic dynamics and equili-brium. Moscow: Nauka (in Russian).]

10. Mesoeconomics of development (2011). G.B. Kleiner (ed.). Moscow: Nauka (in Russian).

11. Perevozchikov A.G., Lesik I.A. (2014). Non-stationary model of investment in fixed assets of the enterprise // Applied mathematics and computer science: Proceedings of the Faculty of Computational mathematics and cybernatics of Lomonosov Moscow State University. V.I. Dmitriev (ed.). Moscow: MAKS Press, 46, 76–88 (in Russian).

12. Perevozchikov A.G., Lesik I.A. (2016). Determination of optimal production volumes and sales prices in a linear model of a multi-product monopoly. Economics and Mathematical Me-thods, 52, 1, 140–148 (in Russian).

13. Perevozchikov A.G., Lesik I.A. (2020). A dynamic model of investment in scientific research of an oligopoly. Economics and Mathematical Methods, 56, 2, 102–114 (in Russian).

14. Perevozchikov A.G., Lesik I.A. (2021). Dynamic model of the software development market based on the assignment problem on pain points. Economics and Mathematical Methods, 56, 2, 102–114 (in Russian).

15. Polyak B.T. (1983). Introduction to optimization. Moscow: Nauka (in Russian).

16. Sergienko A.M., Simonenko V.P., Simonenko A.V. (2016). Improved assignment algorithm for task schedulers in heterogeneous distributed computing systems. System Research and In-formation Technologies, 2, 20–35 (in Russian).

17. Sukharev A.G., Timokhov V.V., Fedorov V.V. (1986). [Course in optimization me-thods. Moscow: Nauka (in Russian).

18. Ustyuzhanina E.V., Dement’ev V.E., Evsyukov S.G. (2021). Transactional digital platforms: the task of ensuring efficiency. Economics and Mathematical Methods, 57, 1, 5–18 (in Rus-sian).

19. Vasin A.A., Grigor’eva O.M., Cyganov N.I. (2017). Optimization of the transport system of the energy market. Proceedings of the USSR Academy of Sciences, 475, 4, 377–381. (in Russian).

20. Vasin A.A., Grigor’eva O.M., Lesik I.A. (2017). Synthesis of the transport system of a multi-node competitive market with variable demand. Applied Mathematics and computer science: Proceedings of the Faculty of Computational mathematics and cybernatics of Lomonosov Moscow State University. V.I. Dmitrievedit (ed.). Moscow: MAKS Press, 55, 74–90 (in Russian).

21. Vasin A.A., Grigor’eva O.M., Lesik I.A. (2018). The problem of optimizing the transport system of the energy market. In: IX Moscow International Conference on Operations Research (ORM2018). Proceedings. A.A. Vasin, A.F. Izmailov (Resp. Eds.), 247–251 (in Russian).

22. Vasin A.A., Morozov V.V. (2005). Game theory and models of mathematical economics. Moscow: MAKS Press (in Russian).

Система Orphus

Loading...
Up