Везде
Market static model for software development based on a transport problem with quadratic cost additions
Table of contents
Annotation Estimate Publication content
References Comments
Share
QR
Metrics
Market static model for software development based on a transport problem with quadratic cost additions
Annotation
PII
S042473880021697-5-1
DOI
10.31857/S042473880021697-5
Publication type
Article
Status
Published
Authors
Ilya Lesik 
Occupation: Senior Engineer
Affiliation: Joint-Stock Company «Scientific and Production Association Russian basic information technology
Address: Moscow, Russian Federation
Aleksandr Perevozchikov
Occupation: Senior Research Scholar
Affiliation: Joint-Stock Company «Scientific and Production Association Russian basic information technology
Address: Russian Federation
Edition
Volume 58 Issue 3
Pages
94-101
Abstract

The authors propose to formulate a market continuous static model for software development based on the transport problem with quadratic cost additions. In contrast to the existing transport problem with fixed cost surcharges, the authors propose a statement that minimizes the sum of transportation costs, which may contain non-fixed additions proportional to the squares of the volumes of appointments. Thus, a quadratic formulation of the transport problem with non-fixed additions is proposed. It is shown that transport problem with quadratic additions can be reduced to a convex programming problem, which can be solved numerically by the subgradient method, or by the conjugate gradient method for the dual problem. The authors describe the interpretation of transport problem with quadratic additions as an assignment problem with non-fixed price discounts, taking into account the difference between the wholesale and retail prices. This makes possible to apply the set task to build digital platforms in the software development market for loading assignments to performers.

Keywords
transport problem with quadratic cost additions, reduction to a convex programming problem, Polyak's method, dual problem, conjugate directions method.
Received
11.03.2022
Date of publication
22.09.2022
Number of purchasers
11
Views
178
Readers community rating
0.0 (0 votes)
Cite   Download pdf
1 ВВЕДЕНИЕ
2 В статье рассматривается задача определения оптимальных планов назначения исполнителей по работам в статической модели рынка разработки программного обеспечения (РПО) на базе транспортной задачи (ТЗ) с квадратичными добавками (КД) по стоимости. В отличие от существующей ТЗ с фиксированными добавками (ФД) по критерию минимума стоимости (Корбут, Финкильштейн, 1969) предлагается использовать постановку, которая вместо фиксированных добавок может иметь нефиксированные добавки (НД), пропорциональные квадратам объемов назначения. Таким образом, предлагается постановка ТЗ с квадратичными добавками (КД) по стоимости.
3 Такие добавки возникают в задачах о назначении (ЗН) с линейными скидками (ЛС) по цене, учитывающими разницу между оптовой и розничной ценой. Соответствующие доходы, получающиеся умножением цены на объем назначения, будут содержать уже квадратичную часть. В существующих платформах PBS1, LSF2 (Platform LSF 7 Update 6, 2009), NQE1, I-SOFT (Ding et al., 2012), EASY3, LoadLeveler4 для решения транспортной задачи и ее частного случая — задачи о назначениях — рассматривается в основном статический вариант задачи с горизонтом планирования один период. Поэтому в настоящей работе мы сосредоточились на ТЗ с КД по стоимости. Такая схема будет более общей, чем построенная на основе ТЗ с ЛД, поскольку предполагает наличие переменной части дохода, пропорциональной квадрату объема поставок по соответствующему маршруту. Для цифровых платформ (ЦП) на рынке РПО цена интерпретируется как цена одного дня для каждого назначения, которая может учитывать скидку на объем поставки. Таким образом, учитывается не только базовая розничная цена, но и скидка на опт. Оптимизация производится в интересах цифровой платформы, которая является своего рода оптовым поставщиком и хотела бы продавать свой ресурс в розницу насколько это возможно. Ставиться задача максимизации дохода. Это позволяет учесть разницу между оптовой и розничной ценой, которая может быть для каждого назначения определена построением соответствующего линейного тренда по ретроспективным данным. Таким образом предложенная ТЗ с КД является уточнением классической ТЗ по стоимости в части разницы между оптовыми и розничными ценами.
1. 1 Официальный сайт компании Altair Engineering, Inc. PBS Works (2006) (http://www.pbsworks.com/).

2. Официальный сайт компании Platform Computing Corporation. Platform LSF 7 Update 6 (2009). An overview of new features for Platform LSF administrors.  (http://www. platform.com/workload-management/ whotsnew_lst7u6.pdf).

3. Официальный сайт продукта Condor: «What is Condor?», 2006. ( >>>>

4. Официальный сайт компании «Интерфейс»: IBM Tivoli Workload Scheduler LoadLeveler (2007). ( >>>> ).
4 Практическая значимость работы связана с применением предложенной статической модели для распределения ресурсов и заданий на рынке разработки программного обеспечения (РПО) для создания соответствующих цифровых трансакционных платформ (ЦТП) (Устюжанина, Дементьев, Евсюков, 2021). Несмотря на постоянное увеличение объема сделок, на рынке РПО отсутствуют глобальные платформы универсальных платформ распределения заданий PBS, LSF, NQE, I-SOFT, EASY, LoadLeveler, которые могли бы быть использованы в динамическом алгоритме загрузки заданий хотя бы для получения начального плана, который в динамической модели является элементом управления. Это приводит к большому числу посредников в цепочке, ведущей от заказчика к исполнителю, что уменьшает стоимость работ для исполнителя до 10 раз по сравнению со стоимостью, которую готовы были платить заказчики. Таким образом, создание цифровой платформы на рынке РПО могло бы привести к более справедливому распределению доходов и увеличению величины общественного благосостояния. Максимизация же последнего равносильна, как известно, определению глобального равновесия на рынке РПО в соответствии с теоремой Дебре (Debreu, 1954).
5 В общетеоретическом плане концепция равновесия (Макаров, Рубинов, 1973) на распределенном рынке однородного товара относится к мезоэкономике (Мезоэкономика развития, 2011) и лежит в основе синтеза транспортной системы многоузлового конкурентного рынка с переменным спросом и предложением, рассмотренная в работах (Васин, Григорьева, Лесик, 2017; Васин, Григорьева, Лесик, 2018; Васин, Григорьева, Цыганов, 2017).
6 Основным результатом работы являются определение и исследование статической ТЗ с КД по времени. Показано, что поставленная непрерывная задача может быть сведена к задаче выпуклого программирования, которую можно решить методом Б.Т. Поляка, описанным в (Поляк, 1983), либо методом сопряженных переменных для двойственной задачи. Это позволяет применить поставленную задачу для построения цифровых платформ (ЦП) на рынке разработки программного обеспечения (РПО) для загрузки заданий исполнителям.
7 1. ПОСТАНОВКА ТЗ С КД ПО ЦЕНЕ
8 Пусть, как в обычной транспортной задаче (ТЗ), через i=1,  ...,  m обозначены пункты производства (разработчики ПО) некоторого однородного товара (человеко-дней при стандартном 8-часовом дне чистого рабочего времени, определяемого по таймеру), через j=1,  ...,  n  — пункты его потребления (заказчики ПО). Даны величины: ai>0  — объем производства в пункте производства i; bj>0  — объем потребления в пункте потребления j, отнесенные к одному дню (горизонту планирования). Ищутся величины xij≥0 (объем «перевозок» из пункта i в пункт j, удовлетворяющие обычным транспортным ограничениям
9 xij≥0,    ∑j=1nxij=ai,    ∑i=1mxij=bj,    i∈M={1,...,m},    j∈N={1,...,n}, (1)
10 где предполагается, что ∑i=1mai=∑i=1nbj , и максимизирующие функцию
11 ∑ijxijcij(xij), (2)
12 cij(xij)=max(dij-cijxij,0). (3)
13 Здесь dij — базовые розничные цены одного дня производителя с учетом прибыли цифровой платформы, например 30%; cijxij — скидка к цене на оптовую поставку объема xij . Поскольку нет смысла назначать xij больше, чем величина dij/cij , можно считать выполненными ограничения
14 xij≤dij/cij. (4)
15 Таким образом, задача (1)–(3) сводится к задаче квадратичного программирования:
16 ∑ij(dijxij-cijxij2)→max (5)
17 при ограничениях (1), (4), которую можно решить методом Поляка (Поляк, 1983) или методом сопряженных направлений (см. там же) для двойственной задачи, если исключить из (1) n+m-1 зависимых переменных. Далее будем считать, что ограничения (1), (4) совместны.
18 2. ИСКЛЮЧЕНИЕ ЗАВИСИМЫХ ПЕРЕМЕННЫХ
19 Исключим зависимые переменные. Например,
20 xij≥0,    xi1=ai-∑j=2nxij≥0,    x1j=bj-∑i=2mxij≥0,    i=1,...,m;    j=2,...,n, (6)
21 при этом появляется m+n-1 дополнительных неравенств помимо условия неотрицательности переменных. Подставляя (6) в показатель (5), получим выражение
22 I(x)=(d11-c11x11)x11+∑i=2m(di1-ci1xi1)xi1+∑j=2n(d1j-c1jx1j)x1j+∑i=2m∑j=2n(dij-cijxij)xij=d11--c11a1-∑j=2nbj-∑i=2mxija1-∑j=2nbj-∑i=2mxij+∑i=2mdi1-ci1ai-∑j=2nxijai-∑j=2nxij++∑j=2nd1j-c1jbj-∑i=2mxijbj-∑i=2mxij+∑i=2m∑j=2ndij-cijxij)xij→max (7)
23 при ограничениях
24 d11c11≥a1-∑j=2nbj-∑i=2mxij=a1-∑j=2nbj+∑i=2m∑j=2nxij≥0,di1ci1≥xi1=ai-∑i=2mxij≥0,    d1jc1j≥x1j=bj-∑i=2mxij≥0,dijcij≥xij≥0,    i=2,...,m;    j=2,...,n. (8)
25 Такую задачу максимизации (7), (8) можно решить методом Поляка.
26 3. ПЕРЕХОД К ДВОЙСТВЕННОЙ ЗАДАЧЕ
27 Предположим для простоты, что рассматривается задача с неуравновешенным балансом
28 xij≥0∑i=1mxij≤ai,    ∑i=2mxij≤bj,    i∈M={1,...,m},    j∈N={1,...,n}. (9)
29 Ограничения (4) несущественны и их можно опустить. Вместо максимизации показателя (5) можно минимизировать обратную функцию
30 J(x)=-I(X)=∑ijcijxij2-dijxij. (10)
31 Задача (9), (10) является частным случаем общей задачи квадратичного программирования
32 minx∈Q[0,5Cx,x)-d,x],
33 Где
34 Q=xAx≤b), (11)
35 C=2pdiagdij0/Mij∈Emn×mn,    d=p1-cij0∈Emn,    x∈Emn,b=a-b-o-∈Em+n+mn,    C-1=12pdiagMijdij0,    A∈E(m+n+mn)×mn. (12)
36 Двойственная задача имеет вид (Поляк, 1983, с. 196–197):
37 miny≥00,5C-1d-ATy),d-ATy+b,y —(13)
38 и может быть решена конечным методом сопряженных направлений из (Поляк, 1983, с. 194–195). Здесь y∈Em+n+mn . Решение предыдущей задачи получается по формуле x*=C-1d-ATy*).
39 4. ПРИМЕР ТОЧНОГО РЕШЕНИЯ ЗАДАЧИ
40 Пример 1. Предположим, что
41 cij=54ai/bj123432243 , dij=54ai/bj3/21/25/3115/3111
42 и ограничения (4) несущественны и их можно опустить. Тогда
43 I(x)=[c11-d11{a1-(b2-x22)-(b3-x23)}]{a1-(b2-x22)-(b3-x23)}+[c21--d21(a2-x22-x23)](a2-x22-x23)+[c12-d12(b2-x22)](b2-x22)++[c13-d13(b3-x23)](b3-x23)+[c22-d22x22]x22+[c23-d23x23]x23→max (14)
44 при ограничениях
45 a1-(b2-x22)-(b3-x23)≥0,    a2-x22-x23≥0,b2-x22≥0,    b3-x23≥0,    x22,x23≥0, (15)
46 или
47 a2≥x22+x23≥b2+b3-a1,    b2≥x22≥0,    b3≥x23≥0, (16)
48 или с учетом значения параметров
49 4≥x22+x23≥2,    4≥x22≥0;    3≥x23≥0. (17)
50 Найдем значения компонентов градиента показателя (14):
51 I'x22(x)=-d11(a1-b2-b3+x22+x23)+[c11-d11(a1-b2-b3+x22+x23)]+d21(a2-x22-x23)--[c21-d21(a2-x22-x23)]+d12(b2-x22)-[c12-d12(b2-x22)]+[c22-2d22x22]=(c22+c11--c21-c12)+2[d21a2+d12b2+d11(b2+b3-a1)]-2x22[d11-d21-d12+d22]-2x23[d11+d21],
52 I'x23(x)=-d11(a1-b2-b3+x22+x23)+[c11-d11(a1-b2-b3+x22+x23)]+d21(a2-x22-x23)--[c21-d21(a2-x22-x23)]+d13(b3-x23)-[c13-d13(b3-x23)]+[c23-2d23x23]=(c11-c21--c13+c23)+2[d11(b2+b3-a1)+d21a2+d13b3]-2x22(d11+d21)-2x23(d11+d21+d13+d23).
53 Найдем точку максимума показателя (14) внутри допустимой области, для чего приравняем нулю производные
54 I'x22(x)=-2x22-5x23+7=0;    I'x23(x)=-5x22-35x23/3+20=0. (18) Умножая первое уравнение на 7, а второе — на 3 и вычитая, получаем 7I'x22(x)-3I'x23(x)=x22-11=0⇒ x22=11. Отсюда x22=11⇒x23=-15/5=-3.
55 Изобразив найденную точку на плоскости, убеждаемся, что она вне области (17), изображенной на рис. 1, и ближайшей к ней является точка (4, 0), которая, следовательно, и является решением задачи.
56

Рис. 1. Допустимая область
57 Собирая все найденные xij , получим приближенное решение квадратичной задачи
58 xij=54ai/bj203040243.
59 На основе этого решения квадратичной задачи можно тестировать метод Поляка, используя на каждой итерации формулы для компонентов градиента показателя.
60 5. МЕТОД СУБГРАДИЕНТНОГО ПОДЪЕМА ДЛЯ НАХОЖДЕНИЯ РЕШЕНИЯ
61 Рассмотрев задачу максимизации (7), (8), приходим к задаче выпуклого программирования на множестве допустимых значений, заданной системой неравенств:
62 Fk(x)≥0,    k=1,...,l —(28)
63 с линейными функциями Fk(x) и условие принадлежности объемлющему параллелепипеду W :
64 xij∈Wij=0,aij    ∀(i,j), (29)
65 которую можно свернуть в одно скалярное неравенство при помощи функции
66 mink=1,...,lFk(x)≥0. (30)
67 Такую задачу можно решить методом Поляка (Поляк, 1983):
68 xijk+1=PWij(xijk+λkνijk)    ∀(i,j),    k=0,1,...,νk∈∂I(xk),F(xk)≥0,∂F(xk),F(xk)<0,    λk→+0,    ∑k=0∞λk=∞, (31)
69 где k — номер шага; λk — программный шаг метода; PWij(xij)  — оператор проектирования на компоненту Wij объемлющего параллелепипеда W . Очевидно, что множество допустимых решений X ограничено и имеет внутренние точки. Тогда согласно результатам (Поляк, 1983, с. 259) справедлива следующая теорема сходимости.
70 Теорема 2. Последовательность в методе (31) сходится к множеству решений задачи минимизации (27).
71 Замечание. Для получения значения основного показателя в узле, заданном подмножеством B, решается задача минимизации штрафной функции JB(x) вместо IB(x) в (27) на всем множестве X .
72 ЗАКЛЮЧЕНИЕ
73 В работе предложена практически значимая методология определения загрузки работ по исполнителям на рынке РПО, обеспечивающих учет скидок на опт. Основным результатом работы является постановка ТЗ с КД по стоимости, сведение ее к задаче квадратичного программирования, из которой следует, что ее можно решить методом Поляка. Рассмотрен модельный пример решения ТЗ с КД по стоимости, который можно использовать для тестирования метода Поляка. Получена двойственная постановка задачи и метод сопряженных градиентов для ее решения.
74 Практическая значимость работы определяется применением в трансакционных платформах на рынке РПО для загрузки заданий по терминологии, обоснованной в работе (Устюжанина, Дементьев, Евсюков, 2021). Построена статическая модель загрузки заданий с двумя группами агентов — компаниями–разработчиками ПО и компаниями–заказчиками ПО, которые могут опередить свои резервные цены на рынке повременной аренды разработанного ПО в двухсекторной модели экономики (Васин, Морозов, 2005). Дискриминируемыми агентами являются компании–заказчики ПО, которые оплачивают услуги оператора платформы в виде процентных надбавок, включенных оператором в цену работы компаний–разработчиков По. Имеются в виду платформы-рынки, взаимодействие экономических агентов на которых носит эпизодический характер разовых сделок. Предполагается удаленное взаимодействие, т.е. возможность коммуникации между агентами, находящимися на любом расстоянии друг от друга.
75 Допускается возможность маштабирования, что означает теоретическое отсутствие ограничений для расширения поля взаимодействия (числа пользователей). Такое расширение возможно за счет перекрестного сетевого эффекта, когда численность одного вида пользователей влияет на численность другого вида (спрос порождает предложение, и наоборот). Предполагается возможность ТПЦ оказывать влияние на объем коммуникации через уровень и структуру цен. Исходя из базовых характеристик поля взаимодействия платформа РПО относится к двусторонним рынкам. Для одноранговых (peer-to-peer) (Устюжанина, Дементьев, Евсюков, 2021) ТЦП, к которым относятся платформы на рынке РПО, организующих торговые трансакции, непосредственными агентами являются поставщики — агенты, разрабатывающие ПО, и потребители — агенты, использующие разработанное ПО для повременной сдачи в аренду.
76 Операторы платформы на рынке РПО могут получать доход в виде платы пользователей за покупку, которые, в свою очередь, получат доход в виде платы за временное использование разработанных ПО в двухсекторной модели экономики (Васин, Морозов, 2005), цена которого определяет резервные цены потребителей. Следует отметить, что настоящая статья является продолжением серии статей (Перевозчиков, Лесик, 2014, 2016, 2020, 2021), в части замены базовой статической ТЗ с НД по стоимости ТЗ с НД по времени, которая может служить фундаментальной основой для построения соответствующих цифровых платформ.

References

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 Academy 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 Systems. EuroSys, 12, 365–378. New York.

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 programming. 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 Mathematical 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 equilibrium. 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 Methods, 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). A dynamic model of software development based on the problem of assignment to bottlenecks. Economics and Mathematical Methods, 56, 4, 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 Information Technologies, 2, 20–35 (in Russian).

17. Sukharev A.G., Timokhov V.V., Fedorov V.V. (1986). Course in optimization methods. 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 Russian).

19. 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. Dmitriev (ed.). Moscow: MAKS Press, 55, 74–90 (in Russian).

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

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

22. Vasin A.A., Grigor’eva O.M., Cyganov N.I. (2017). Optimization of the transport system of the energy market. Doklady Akademii Nauk, 475, 4, 377–381 (in Russian).

Comments

No posts found

Write a review
Translate