Processing math: 27%
Везде
Reducing the dynamic model of the software development market to a block problem of convex programming
Table of contents
Annotation Estimate Publication content
References Comments
Share
QR
Metrics
Reducing the dynamic model of the software development market to a block problem of convex programming
Annotation
PII
S042473880024879-5-1
DOI
10.31857/S042473880024879-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 59 No. 1
Pages
119-130
Abstract

The authors propose to reduce a discrete dynamic model of the software development market to a block problem of convex programming, which can be solved by successive approximations based on contraction mapping, in case of abandoning the integer elements of the destination matrix. However, there are also peculiarities: equilibrium prices can be calculated directly and therefore a variational formulation of the internal problem of determining equilibrium prices based on Debreu's theorem is not required. The functions of phase coordinates’ change can be taken as convex, for example, the norm of the difference squared, and do not take into account the fixed costs for each control switch, which is excluded from the equations of system’s dynamics. The resulting block problem of convex programming allows decomposition by freezing the connection variables with neighboring blocks at the level of the previous iteration. It is shown that the operator on the right side of the resulting recurrent equation is compressive under fairly general conditions. This allows the authors to prove successive approximations for solving the resulting problem, based on the principle of contraction mapping. The authors give the model example of its use in the dynamic expansion of the transport problem according to the value.

Keywords
transport problem according to the value, problem’s dynamic expansion, exclusion of controls, problem’s decomposition, the principle of contraction mapping, the method of successive approximations
Received
08.11.2022
Date of publication
29.03.2023
Number of purchasers
15
Views
193
Readers community rating
0.0 (0 votes)
Cite   Download pdf
1 ВВЕДЕНИЕ
2 В статье рассматривается задача определения оптимальных планов назначения исполнителей по работам в динамическом расширении транспортной задачи (ТЗ) по стоимости, поставленная в работе (Лесик, Перевозчиков, 2021). Управление формально осуществляется приращением планов, которые исключаются из уравнений динамики. Поэтому на каждом шаге показатель оптимальности, кроме транспортных расходов и фиксированных доплат, включает норму приращения планов и минимизация этого показателя позволяет уменьшить расходы и стабилизировать распределение ресурсов по работам. Полученная блочная задача выпуклого программирования допускает декомпозицию через замораживание переменных связи с соседними блоками на уровне предыдущей итерации. Это дает возможность обосновать метод последовательных приближений для решения полученной задачи, основанный на принципе сжимающих отображений.
3

В существующих платформах PBS1, LSF2 (Platform LSF 7 Update 6, 2009), NQE3, I-SOFT (Ding et al., 2012), EASY4, LoadLeveler5 для решения транспортной задачи и ее частного случая задачи о назначениях рассматривается в основном статический вариант задачи с горизонтом планирования один период. Неэффективность такого подхода особенно сильно проявляется в глобальных вычислительных системах, так как в системах такого типа ресурсы и заявки являются неоднородными (Сергиенко, Симоненко В., Симоненко А., 2016). Все это делает актуальной задачу динамического распределения исполнителей по заданиям, поставленную и изученную в настоящей работе.

1. PBS Works. Официальный сайт компании Altair Engineering, Inc. (http://www.pbsworks.com/).

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

3. Cм. сноску 1.

4. What is Condor? Официальный сайт продукта Condor (http://www.cs.wisc.edu/condor/description.html).

5. IBM Tivoli Workload Scheduler LoadLeveler. Официальный сайт компании «Интерфейс» (http://www.interface.ru/home.asp?artId=6283).
4 Практическая значимость работы позволяет внедрить предложенную схему декомпозиции динамической модели в распределение ресурсов и заданий на рынке разработки программного обеспечения (РПО) для создания соответствующих цифровых транзакционных платформ (ЦТП) (Устюжанина, Дементьев, Евсюков, 2021). Несмотря на постоянное увеличение объема сделок, на рынке РПО отсутствуют глобальные платформы по типу указанных выше универсальных платформ распределения заданий PBS, LSF, NQE, I-SOFT, EASY, LoadLeveler, которые могли бы быть использованы в динамическом алгоритме загрузки заданий хотя бы для получения начального плана, который в динамической модели является элементом управления. Это увеличивает число посредников в цепочке, ведущей от заказчика к исполнителю, что уменьшает получаемую исполнителем оплату произведенных работ до 10 раз по сравнению со стоимостью, которую готовы были платить заказчики (цену предложения). Таким образом, создание цифровой платформы на рынке РПО могло бы привести к более справедливому распределению доходов и увеличению величины общественного благосостояния. Максимизация же последнего равносильна, как известно, определению глобального равновесия на рынке РПО в соответствии с теоремой Дебре (Debreu, 1954).
5 В общетеоретическом плане концепция равновесия (Макаров, Рубинов, 1973) на распределенном рынке однородного товара относится к мезоэкономике (Мезоэкономика развития, 2011) и лежит в основе модели синтеза транспортной системы многоузлового конкурентного рынка с переменным спросом и предложением, рассмотренной в работах (Васин, Григорьева, Лесик, 2017, 2018; Васин, Григорьева, Цыганов, 2017). К особенностям метода можно отнести то обстоятельство, что равновесные цены вычисляются напрямую, и поэтому не требуется вариационной постановки внутренней задачи. Функции изменения фазовых координат можно взять выпуклыми, например норма разности в квадрате, и не учитывать постоянных затрат при каждом переключении управления. Такая постановка изучается в настоящей работе. Имея динамическое расширение задачи о назначении (ЗН) на узкие места (УМ), можно определить дополнительную прибыль транспортной системы (цифровой платформы) за счет использования фьючерсов.
6 Основным результатом работы является декомпозиция динамического расширения транспортной задачи по стоимости при отказе от целочисленности элементов матрицы назначения и построение методов последовательных приближений ее решения на основе алгоритма Поляка.
7 1. Классическая транспортная задача по стоимости
8 Пусть, как в обычной транспортной задаче, через i=1,  ...,  m обозначены пункты производства (разработчики программного обеспечения (ПО)) некоторого однородного товара (человеко-дней при стандартном 8-часовом дне чистого рабочего времени, определяемого по таймеру), через j=1,  ...,  n  — пункты его потребления (заказчики ПО). Даны величины: ai≥0  — объем производства в пункте производства i; bj≥0  — объем потребления в пункте потребления j, отнесенные к одному дню (горизонту планирования).
9 Ищутся величины xij объемов перевозок из пункта i в пункт j, удовлетворяющие обычным транспортным ограничениям
10 xij≥0,∑nj=1xij=ai,    ∑mi=1xij=bj,    i=1,...,m,    j=1,...,n, (1)
11 где предполагается, что
12 ∑mi=1ai=∑nj=1bj, (2)
13 и минимизирующие функцию
14 I(x)=-∑mi=1∑nj=1Aijxij. (3)
15 Здесь Aij — эффективность соответствующего назначения.
16 Таким образом, задача (1)–(3) является частным случаем обычной ТЗ, которую можно решить точно при помощи соответствующего пакета, реализующего венгерский метод (Корбут, Финкильштейн, 1969, с. 307) расстановки пометок, подробно описанный в (Ашманов, 1981), имеющим сложность O(N3) (Сергиенко и др., 2016), где N=n+m — общее число вершин соответствующего двудольного графа.
17 Конкретно для рынка РПО будем предполагать выполненными следующие предположения:
18
  1. за единицу берется один программист, работающий полный день (8 часов);
  2. горизонт планирования — 1 день;
  3. прибыли заказчиков и исполнителей по контакту (i,j) равны разности цен Pj-Qi одного рабочего дня спроса Pj и предложения Qi (последняя с учетом прибыли платформы, например 30%), умноженной на число кодировщиков xij , где Pj≥P≥Qi, P  — равновесная цена. Всего
19 (Pj-Qi)xij. (4)
20 Замечание. С учетом балансовых ограничений прибыли участников рынка разработки ПО не будут зависеть от распределения xij .
21 В самом деле,
22 ∑mi=1∑nj=1(Pj-Qi)xij=∑nj=1Pj∑mi=1xij-∑mi=1Qi∑nj=1xij=∑nj=1Pjbj-∑mi=1Qiai≥0. (5)
23 Поэтому для оптимизации распределения применяется критерий (3), где в качестве полезности назначений Aij можно взять рейтинг соответствующего соединения (например, долю всех предыдущих соединений в их общем количестве за определенный период по ретроспективной информации). Это указывает на то, что желательно использовать ранее зарекомендовавшие себя пары «исполнитель – заказчик».
24 2. Динамическое расширение ТЗ по стоимости
25 Динамическое расширение ТЗ по стоимости можно получить по схеме, предложенной в работе (Васин, Григорьева, Лесик, 2018). При этом равновесные цены можно вычислить впрямую и поэтому не требуется вариационной постановки внутренней задачи. И функции изменения фазовых координат можно взять выпуклыми, например норма разности в квадрате, и не учитывать постоянных затрат при каждом переключении управления.
26 Запишем постановку динамической задачи, следуя работе (Лесик, Перевозчиков, 2021). Оказывается, что у основной системы нет начальных условий (по крайней мере вначале, а затем за начальное условие можно брать текущее значение плана). Далее для определенности будем считать, что начальное значение плана не определено. Поэтому введем еще (–1)-шаг и соответствующую компоненту управления с нулевыми начальными условиями:
27 xij(t+1)=xij(t)+uij(t),    t=-1,0,...,T-1,    xij(-1)=0,    i=1,...,,m;    j=1,...,n. (6)
28 Через ai(t),bj(t) обозначим запасы и потребности в ресурсах в соответствии с первоначальными заявками. Можно считать, что управляющие воздействия ограничены условиями -Mij(t)≤uij(t)≤Mij(t+1)    ∀i,j, где Mij(t)=min(ai(t),bj(t)) .
29 Множество допустимых управлений [u(t),t=-1,0,...,T-1], u(t)=(uij(t),    i=1,...,m;    j=1,...,n) , удовлетворяющих этому условию, обозначим через
30 W=∏T-1t=-1W(t),W(t)=∏i,j‍Wij(t),Wij(t)=[-Mij(t),Mij(t+1)].
31 Показатель эффективности определим в виде интегрального функционала
32 J(x,u)=∑T-1t=0{-∑m(t)i=1∑nj=n(t)Aijxij(t)+K∑mi=1∑nj=1u2ij(t)}, (7)
33 где K>0 — достаточно большая штрафная константа за изменение элемента плана, связанная с необходимостью перераспределения некоторых исполнителей по работам.
34 Предполагается, что цены в заявках постоянны и упорядочены по неубыванию:
35 Q1≤Q2≤...≤Qm,    P1≤P2≤...≤Pn, (8)
36 Qi≤P(t)≤Pj,    i=1,...,m(t);    j=n(t),...,n, (9)
37 где P(t),  m(t),  n(t)  — равновесная цена и максимальные и минимальные значения индексов i,j , удовлетворяющих неравенствам (9) в момент времени t=-1,  0,  ...,  T-1 . Тогда балансовые ограничения имеют вид фазовых ограничений:
38 ai(t)=∑nj=n(t)xij(t),i=1,...,m(t),    bj(t)=∑m(t)i=1xij(t),j=n(t),...,n,    xij(t)≥0,t=-1,0,...,T-1. (10)
39 В силу линейности уравнений динамики (6) и выпуклости функции (7) по совокупности переменных в силу результатов (Васильев, 1981) справедлива следующая теорема.
40 Теорема 1. Функционал (7) представляет собой выпуклую функцию управления.
41 Далее для простоты будем рассматривать задачу с неуравновешенным балансом, когда
42 ai(t)≥∑nj=n(t)xij(t),i=1,...,m(t),    bj(t)≥∑m(t)i=1xij(t),j=n(t),...,n,    xij(t)≥0,    t=0,...,T-1. (11)
43 В этом случае условие (2) может не выполняться. Обозначим множества точек x(t) , удовлетворяющих (11), через B(t) .
44 Иногда вместо (7) используется недифференцируемый выпуклый показатель
45 J(x,u)=∑T-1t=0{-∑m(t)i=1∑n(t)j=1Aijxij(t)+K∑mi=1∑nj=1u+ij(t)}, (12)
46 где верхняя срезка разности равна
47 u+ij(t)=max(uij(t),  0), (13)
48 uij(t)=xij(t+1)-xij(t)=Δxij(t). (14)
49 То есть дополнительные расходы по выводу исполнителя на заказчика связаны только с увеличением объема xij назначения, а не с его уменьшением.
50 3. Декомпозиции динамической ТЗ по стоимости
51 Заменим в показателе (7) компоненты управления при помощи их выражения (14) через приращение фазовых координат
52 L(x)=∑T-1t=0{-∑m(t)i=1∑nj=n(t)Aijxij(t)+K∑mi=1∑nj=1Δx2ij(t)}. (15)
53 Этот показатель необходимо минимизировать при ограничениях
54 x∈B≜ (16)
55 Рассмотрим вспомогательную задачу для компонент x(t) :
56 Lt(x)=K∑i=1m∑j=1n(xij(t)-xij(t-1))2-∑i=1m(t)∑j=n(t)nAijxij(t)+K∑i=1m∑j=1n(xij(t)-xij(t+1))2==Kx(t)-x(t-1)2-A(t),x(t)+Kx(t)-x(t+1)2→min (17)
57 при фиксированных x(t-1),x(t+1) и ограничениях
58 x(t)∈B(t). (18)
59 Здесь A(t) — соответствующая подматрица матрицы A. Для удобства изложения схемы декомпозиции A(t),x(t) рассматриваются как вектор-строки, где в качестве компонент стоят строки.
60 Предполагается по умолчанию, что слагаемые в (17), содержащие x(-1),  x(T), отсутствуют. Справедлива следующая лемма.
61 Лемма 1. Для любого решения x задачи минимизации (15) при ограничениях (16) его компоненты являются решением вспомогательной задачи (17)–(18).
62 Градиент показателя (17) по x(t) при фиксированных x(t-1),x(t+1) имеет вид
63 ∇x(t)Lt(x(t))=2K(x(t)-x(t-1))-A(t)+2K(x(t)-x(t+1)). (19)
64 Получив градиенты (19), для решения вспомогательной задачи можно воспользоваться методом проекции градиента с постоянным шагом (Поляк, 1983, с. 185):
65 xk+1(t)=PB(t)(xk(t)-a∇x(t)Lt(xk(t)),    k=0,  1,  ..., (20)
66 где k — номер шага; a>0 — постоянный шаг метода; PB(t)(⋅)  — оператор проектирования на компоненту B(t) множества допустимых управляющих воздействий W(t) . Очевидно, что внутренности множеств B(t) не пустоты. Тогда согласно результатам (Поляк, 1983, с. 185) справедлива следующая теорема сходимости.
67 Теорема 2. Пусть L>0 , где L>0  — константа Липшица градиента (19) на множестве B . Тогда последовательность xk(t) в методе (20) сходится к множеству решений задачи минимизации (17) при ограничениях (18).
68 Рассмотрим диагональный процесс:
69 xk+1(t)=PB(t)(xk(t)+a∇x(t)Lt(xk)    ∀t,    k=0,1  ,.... (21)
70 Введем норму x=maxtx(t). Тогда константа L>0 будет ограничивать норму полного градиента показателя L(x) на множестве B и теорема сходимости будет справедлива для процесса (21), который представляет собой покомпонентную запись метода проектирования градиента в задаче минимизации показателя (15) при ограничениях (16).
71 Таким образом, метод проекции градиента осуществляет декомпозицию исходной задачи на вспомогательные.
72 Модель позволяет учесть скидки на опт (Лесик, Перевозчиков, 2022) и посреднические менеджерам за вывод недостающих кодеров. В этом случае (15) превращается в
73 L(X)=∑t=0T-1∑i=1m(t)∑j=n(t)nAijxij2(t)+K∑i=1m∑j=1nΔxij+(t),
74 т.е. квадратичная форма соответствует уже скидкам на опт, а кусочно-линейная — посредническим менеджерам за вывод недостающих кодеров. Соответственно меняется частный показатель:
75 Lt(X)=K∑i=1m∑j=1nΔxij+(t-1)+Ax(t),x(t)+K∑i=1m∑j=1nΔxij+(t+1),
76 где A(t)=aP(t)E , где — норма скидки на опт, — равновесная цена текущего периода, E — единичная матрица соответствующей размерности,  — посреднические менеджерам. Это равенство имеет экономический смысл, поскольку складываются денежные величины. Например, равенство (17)
77 Lt(x)=Kx(t)-x(t-1)2-A(t),x(t)+Kx(t)-x(t+1)2
78 имеет смысл только в методе штрафных функций, поскольку абстрактная полезность, взятая со знаком «минус», складывается с абстрактным штрафом.
79 Замечание. Абстрактная полезность может быть нелинейной, например, логарифмической по закону логарифма:
80 xijAij(xij)=aijln(1+xij)≈aij(xij-0,5xij2)=aij(1-0,5xij)xij;    xij∈(-1,1];
81 что можно интерпретировать как переменную полезность Aij(xij)=aij(1-0,5xij) (Лесик, Перевозчиков, 2022).
82 На практике наиболее применим денежный показатель, который можно связать с равновесной ценой дня:
83 Lt(x)=bP(t-1)∑i=1m∑j=1nΔxij+(t-1)+aP(t)x(t)2+bP(t+1)∑i=1m∑j=1nΔxij+(t+1).
84 К нему максимально близок показатель с логарифмом
85 Lt(x)=bP(t-1)∑i=1m∑j=1nΔxij+(t-1)-∑i=1m(t)∑j=n(t)nAijln1+xij+bP(t+1)∑i=1m∑j=1nΔxij+(t+1)
86 в силу приближенного равенства Aijln(1+xij)≈Aij(xij-0,5xij2).
87 При Aij=2aP(t) последний эквивалентен показателю по стоимости, в силу того что сумма линейных частей равна константе в силу балансовых ограничений.
88 4. Случай не дифференцируемого показателя
89 Иногда вместо (15) используется недифференцируемый выпуклый показатель (12), который при исключении управлений принимает вид
90 L(x)=∑t=0T-1-∑i=1m(t)∑j=1n(t)Aijxij(t)+K∑i=1m∑j=1nΔxij+(t),
91 где Δxij+(t)=maxxij(t+1)-x(t),    0 .
92 Как и в разд. 3, будем рассматривать задачу с неуравновешенным балансом (11). Введем функции:
93 fit(x(t))=∑j=n(t)nxij(t)-ai(t)≤0,i=1,...,m(t);    ft(x(t))=maxifit(x(t)),f(x)=maxtft(x(t));gjt(x(t))=∑i=1m(t)xij(t)-bj(t)≤0,j=n(t),...,n;    gt(x(t))=maxjgjt(x(t)),g(x)=maxtgt(x(t));F(x)=max(f(x),g(x)).
94 Рассмотрим задачу минимизации (21) на множестве допустимых значений, заданном агрегированным неравенством
95 F(x)≤0 (22)
96 и условием принадлежности объемлющему параллелепипеду
97 x∈V=⊗tVt,Vt=⊗i,jVijt,Vijt=0,Mij(t). (23)
98 Эту задачу можно решить методом Поляка (Поляк, 1983):
99 xk+1=PV(xk-λkνk),    k=0,1,...,νk∈∂L(xk),    F(xk)≤0,∂F(xk),    F(xk)>0,    λk→+0,    ∑k=0∞λk=∞, (24)
100 где k — номер шага; λk — программный шаг метода; PV(x)  — оператор проектирования на объемлющий параллелепипед V ; ∂J(x),∂F(x) — субдифференциалы выпуклых функций J(x),F(x) . Очевидно, что множество допустимых решений X ограничено и имеет внутренние точки. Тогда согласно результатам (Поляк, 1983, с. 259) справедлива следующая теорема сходимости.
101 Теорема 3. Последовательность xk в методе (24) сходится к множеству решений задачи минимизации (21) при ограничениях (22), (23).
102 Возможен, как в дифференцируемом случае, метод проекции субградиента:
103 xk+1(t)=PB(t)(xk(t)-λkνx(t)(xk)    ∀t,    k=0,1,..., (25)
104 где vx(t)(xk)  — компонента x(t) субградиента функции Lt(xk)
105 Lt(x)=K∑i=1m∑j=1nΔxij+(t-1)-∑i=1m(t)∑j=1n(t)Aijxij(t)+K∑i=1m∑j=1nΔxij+(t+1) ,
106 λk — программный шаг метода, удовлетворяющий условиям (24).
107 Очевидно, что субградиенты vx(x) ограничены в совокупности на ограниченном замкнутом множестве В в силу полунепрерывности сверху субградиентного отображения x→vx(x) . Тогда согласно результатам (Поляк, 1983, с. 187) справедлива следующая теорема сходимости.
108 Теорема 4. Последовательность xk в методе (25) сходится к множеству решений задачи минимизации (17) при ограничениях (18).
109 Как и метод проекции градиента, метод (25) осуществляет декомпозицию задачи минимизации (17) при ограничениях (18), в отличие от алгоритма Поляка (24).
110 5. Пример точного решения задачи
111 Пример 1. Предположим, что в задаче с уравновешенным балансом
112 cij(0)=54ai(0)/bj(0)123432243, cij(1)=24ai(1)/bj(1)123432240,     T=2 .
113 Шаг 0.
114 Тогда, исключая зависимые переменные из условий (10), приходим к задаче
115 I0(x(0))=c11{a1(0)-(b2(0)-x22(0))-(b3(0)-x23(0))}+c21(a2(0)-x22(0)-x23(0))++c12(b2(0)-x22(0))+c13(b3(0)-x23(0))+c22x22(0)+c23x23(0)=29-2x22(0)-4x23(0)→max (26)
116 при ограничениях
117 a1(0)-(b2(0)-x22(0))-(b3(0)-x23(0))≥0,a2(0)-x22(0)-x23(0)≥0,b2(0)-x22(0)≥0,b3(0)-x23(0)≥0,x22(0),x23(0)≥0, (27)
118 Или
119 a2(0)≥x22(0)+x23(0)≥b2(0)+b3(0)-a1(0),b2(0)≥x22(0)≥0,b3(0)≥x23(0)≥0, (28)
120 или с учетом значения параметров (рис. 1)
121 4≥x22(0)+x23(0)≥2,3≥x23(0)≥0. (29)
122

Рис. 1. Допустимая область на нулевом шаге
123 Найдем точку максимума показателя (26) при ограничениях (29) геометрически. Получим точку статически-оптимального решения x22(0)=2,x23(0)=0. Собирая все найденные xij , запишем статически-оптимальное решение задачи на нулевом шаге:
124 xij(0)=54ai(0)/bj(0)023220243. (30)
125 Шаг 1. Исключая зависимые переменные, приходим к задаче
126 I1(x)=c11{a1(1)-(b2(1)-x22(1))}+c21(a2(1)-x22(1))+c12(b2(1)-x22(1))++c22x22(1)=22-2x22(1)→max (31)
127 при ограничениях
128 a1(1)-(b2(1)-x22(1))≥0,a2(1)-x22(1)≥0,b2(1)-x22(1)≥0,x22(1)≥0, (32)
129 Или
130 a2(1)≥x22(1)≥b2(1)-a1(1),b2(1)≥x22(1)≥0, (33
131 или с учетом значения параметров
132 4≥x22(1)≥2. (34)
133 Найдем точку максимума показателя (31) при ограничениях (34) геометрически. Получим точку статически-оптимального решения x22(1)=2. Собирая все найденные xij , запишем статически-оптимальное решение задачи на шаге 1:
134 xij(1)=24ai(1)/bj(1)020220240. (35)
135 Замечание. Приведенный пример получается динамическим расширением примера из (Лесик, Перевозчиков, 2022) и дает точное решение динамического расширения ТЗ по стоимости с исходной матрицей на два шага. На каждом шаге найденное оптимальное решение статической задачи по времени является решением по стоимости, причем решение второй задачи будет сужением первого 2×3 на подматрицу 2×2, поэтому штраф за наращивание компонент решения
136 ∑i=1m∑j=1nmaxxij(1)-xij(0);0=∑i=1m∑j=1nΔxij+(0);Δxij+(0)=maxΔxij(0);0 (36)
137 будет равен нулю, т.е. минимальным. Эта задача содержит 2 + 1 = 3 независимых переменных и может быть решена методом проекции градиента и служить для проверки его практической сходимости.
138 Для решения вспомогательной задачи проектирования множества B(t) на каждом шаге можно использовать конечный метод сопряженных градиентов из (Поляк, 1983, с. 195) применительно к двойственной задаче (там же, с. 297).
139 Задача проектирования может быть поставлена как задача:
140 mind,x+12γx-a2,    Ax≤b, (37)
141 Где
142 d=0-,    γ=1. (38)
143 Двойственная задача имеет вид:
144 min0,5γd+ATy2-y,Aa-b,    y≥0=min0,5Αy,y-y,e≜f(y),    y≥0, (39) где
145 Α=AAT,    e=Aa-b. (40)
146 Исходная точка минимума связана с точкой минимума двойственной задачи формулой
147 x*=a-γATy*+d=a-ATy*. (41)
148 Градиент показателя (46) задается формулой
149 ∇f(y)=Αy-e (42)
150 Пример 2. Рассмотрим задачу проектирования точки a=(3,3)T на допустимое множество статической задачи на нулевом шаге в примере 1. Из рис. 1 видно, что проекцией будет точка (2,2)T .
151 Матрица A ограничений (29), векторы b,y будут иметь вид
152 A=1-1001-11-1;    b=4-230;    y=y1y2y3y4 .
153 Матрица Α=AAT и вектор e равны
154 Α=2-211-22-111-11-1-11-11,    e=2-40-3.
155 Метод сопряженных направлений:
156 y0=0000,    ∇f(y0)=-e=-2403.
157 Множество индексов I0 и шаг β0 равны I0=i,yi0=0,∇f(y0)i>0=2,  4;β0=0 . Сопряженный градиент
158 p0,pi0=-∇f(y0)i,    i∉I0,0,    i∈I0
159 равен p0=2000,    y1=y0+α0p0=2α0000≥0,    α0∈[0,∞) .
160 Найдем производную функции F(α0)≜f(y0+α0p0) :
161 F'α0(α0)=∇f(y0+α0p0),p0==Α2α0000+-2403,2000=α04-42-2+-2403,2000=8α0-4=0⇒α0*=0,5. Отсюда
162 y1=y0+0,5p0=1000,    ∇f(y1)=Αy1-e=2-21-1-2-40-3=0212.
163 Множество индексов I1 и шаг β1 равны I1=I0∪i,yi1=0=2,3,4; I1≠I0 ⇒β1=0⇒y2=y1=y*. Отсюда
164 x*=a-ATy*=33-1-1001-11-11000=33-11=22,
165 что совпадает с ранее найденной точкой.
166 Пример 3. В условиях примера 2 сделаем один шаг метода проекции субградиента (25). Тогда общий показатель (21) имеет вид:
167 L(x)=-(29-2x22(0)-4x23(0))-(22-2x22(1))+max[x22(1)-2-(x22(0)+x23(0)-2)]++max[4-x22(1)-(4-x22(0))]+max[4-x22(1)-(4-x22(0)-x23(0))]++max[x22(1)-x22(0)] (43)
168 при ограничениях (29) и (34):
169 4≥x22(0)+x23(0)≥2,    3≥x23(0)≥0,     4≥x22(1)≥2.
170 В качестве начальных координат возьмем точку
171 x0(0)=x220(0)x230(0)=13,    x0(1)=x220(1)=4.
172 В этой точке только последний максимум в (43) положителен, поэтому субградиенты вычисляются по формулам:
173 νx(0)(x0)=24+-10=14,    νx(1)(x0)=2+1=3.
174 Теперь можно сделать первый шаг метода проекции субградиента:
175 x1(0)=ΡB(0)(x0(0)-λ0νx(0)(x0))=ΡB(0)13-114=ΡB(0)0-1=1,50,5,x1(1)=ΡB(1)(x0(1)-λ0νx(1)(x0))=ΡB(1)(4-1×3)=2.
176 Если нанести полученную точку на рис. 1, видно, что она близка к аналитическому решению модельного примера динамической задачи, полученному в примере 1: x22(0)=2,    x23(0)=0, x22(1)=2.
177 ЗАКЛЮЧЕНИЕ
178 В настоящей работе предложена практически значимая методология распределения загрузки работ по исполнителям на рынке РПО, обеспечивающих стабилизацию планов назначения за счет уменьшения изменения этих планов. Показано, что задача определения оптимальных приращений планов сводится к блочной задаче выпуклого программирования и может быть решена методом проекции градиента в дифференцируемом случае и методом Поляка в негладком случае. Основным результатом работы является декомпозиция задачи на основе метода проекции градиента или метода Поляка.
179 Результаты работы позволяют применять их в транзакционных платформах на рынке РПО для динамической загрузки заданий (согласно терминологии, обоснованной в работе (Устюжанина, Дементьев, Евсюков, 2021)).
180 В статье построена динамическая модель загрузки заданий с двумя группами агентов — компаниями–разработчиками ПО и компаниями–заказчиками ПО, которые могут опередить свои резервные цены на рынке повременной аренды разработанного ПО в двухсекторной модели экономики (Васин, Морозов, 2005). Дискриминируемыми агентами являются компании–заказчики ПО, которые оплачивают услуги оператора платформы в виде процентных надбавок, включенных оператором в цену работы компаний–разработчиков По. Имеются в виду платформы-рынки, взаимодействие экономических агентов на которых имеет эпизодический характер разовых сделок. Предполагается удаленное взаимодействие, т.е. возможность коммуникации между агентами, находящимися на любом расстоянии друг от друга. Допускается возможность масштабирования, т.е. теоретическое отсутствие ограничений для расширения поля взаимодействия (числа пользователей). Такое расширение возможно за счет перекрестного сетевого эффекта, когда численность одного вида пользователей влияет на численность другого вида (спрос порождает предложение, и наоборот).
181 Предполагается возможность ЦТП оказывать влияние на объем коммуникации через уровень и структуру цен. Исходя из базовых характеристик поля взаимодействия, платформа РПО относится к двусторонним рынкам. Для одноранговых (peer-to-peer) (Устюжанина, Дементьев, Евсюков, 2021) ТЦП, к которым относятся платформы на рынке РПО, организующие торговые трансакции, непосредственными агентами являются поставщики — агенты, разрабатывающие ПО, и потребители — агенты, использующие разработанное ПО для повременной сдачи в аренду. Операторы платформы на рынке РПО могут получать доход в виде платы пользователей за покупку. Пользователи получат доход в виде платы за повременное использование разработанных ПО в двухсекторной модели экономики (Васин, Морозов, 2005). Цены на такое ПО определяют резервные цены потребителей, по терминологии, принятой в указанной работе.
182 Настоящая статья является продолжением серии статей (Перевозчиков, Лесик, 2014; Лесик, Перевозчиков, 2016, 2020) о динамическом расширении статических моделей рынка с рынка инвестиций на рынок разработки программного обеспечения и использует разработанный там инструментарий, который может служить фундаментальной основой для построения соответствующих цифровых платформ. Предложенная схема динамического расширения задачи переносится на транспортную задачу с переменными коэффициентами, изученную в работе (Лесик, Перевозчиков, 2022).
183 В общетеоретическом плане схема решения динамической задачи, предложенная в настоящей статье, может считаться схемой декомпозиции, основанной на численном методе решения (Цурков, 1981, с. 111).

References

1. Ashmanov S.A. (1981). Linear programming. Moscow: Nauka (in Russian).

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 7th ACM European Conference on Computer Systems. EuroSys, 12. New York, 365–378.

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

5. Lesik I.A., Perevozchikov A.G. (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).

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

7. Lesik I.A., Perevozchikov A.G. (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).

8. Lesik I.A., Perevozchikov A.G. (2022): Market’s static model for software development based on a transport problem with quadratic cost additions. Economics and Mathematical Methods, 58, 3, 94–101 (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. In: Applied mathematics and computer science: Proceedings of the Faculty of Computational mathematics and cybernetics of Lomonosov Moscow State University. V.I. Dmitriev (ed.). Moscow: MAKS Press, 46, 76–88 (in Russian).

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

13. 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).

14. Tsurkov V.I. (1981). Decomposition in large-dimensional problems. Moscow: Nauka (in Russian).

15. 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).

16. Vasil’ev F.P. (1981). Methods for solving extreme problems. Moscow: Nauka (in Russian).

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

18. 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).

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

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

Comments

No posts found

Write a review
Translate