Везде
Сведение динамической модели рынка разработки программного обеспечения к блочной задаче выпуклого программирования
Оглавление
Аннотация Оценить Содержание публикации
Библиография Комментарии
Поделиться
QR
Метрика
Сведение динамической модели рынка разработки программного обеспечения к блочной задаче выпуклого программирования
Аннотация
Код статьи
S042473880024879-5-1
DOI
10.31857/S042473880024879-5
Тип публикации
Статья
Статус публикации
Опубликовано
Авторы
Лесик Илья Александрович 
Должность: старший инженер
Аффилиация: НПО «РусБИТех»
Адрес: Москва, Российская Федерация
Перевозчиков Александр Геннадиевич
Должность: старший научный сотрудник
Аффилиация: НПО «РусБИТех»
Адрес: Российская Федерация
Выпуск
Том 59 № 1
Страницы
119-130
Аннотация

В статье предлагается метод сведения дискретной динамической модели рынка разработки программного обеспечения к блочной задаче выпуклого программирования. Задачу можно решить методом последовательных приближений, основанным на принципе сжимающих отображений, если отказаться от целочисленности элементов матрицы назначения. Равновесные цены можно рассчитать напрямую, и поэтому не требуется вариационной постановки внутренней задачи определения равновесных цен, основанной на теореме Дебре. Функции изменения фазовых координат можно взять выпуклыми, например норма разности в квадрате, и не учитывать постоянных затрат при каждом переключении управления, которое исключается из уравнений динамики системы. Полученная блочная задача выпуклого программирования допускает декомпозицию с помощью замораживания переменных связи с соседними блоками на уровне предыдущей итерации. Показано, что оператор в правой части полученного рекуррентного уравнения является сжимающим при достаточно общих условиях. Это позволяет обосновать метод последовательных приближений для решения полученной задачи, основанный на принципе сжимающих отображений. Приводится модельный пример его использования в динамическом расширении транспортной задачи по стоимости.

Ключевые слова
транспортная задача по стоимости, динамическое расширение задачи, исключение управлений, декомпозиция задачи, принцип сжимающих отображений, метод последовательных приближений
Классификатор
Получено
08.11.2022
Дата публикации
29.03.2023
Всего подписок
15
Всего просмотров
174
Оценка читателей
0.0 (0 голосов)
Цитировать Скачать pdf
Доступ к дополнительным сервисам
Дополнительные сервисы только на эту статью
Преимущества сервисов
100 руб. / 1.0 SU
Дополнительные сервисы на весь выпуск”
Преимущества сервисов
910 руб. / 15.0 SU
Дополнительные сервисы на все выпуски за 2023 год
Преимущества сервисов
2730 руб. / 61.0 SU
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,∑j=1nxij=ai,    ∑i=1mxij=bj,    i=1,...,m,    j=1,...,n, (1)
11 где предполагается, что
12 ∑i=1mai=∑j=1nbj, (2)
13 и минимизирующие функцию
14 I(x)=-∑i=1m∑j=1nAijxij. (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 ∑i=1m∑j=1n(Pj-Qi)xij=∑j=1nPj∑i=1mxij-∑i=1mQi∑j=1nxij=∑j=1nPjbj-∑i=1mQiai≥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=0T-1-∑i=1m(t)∑j=n(t)nAijxij(t)+K∑i=1m∑j=1nuij2(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)=∑j=n(t)nxij(t),i=1,...,m(t),    bj(t)=∑i=1m(t)xij(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)≥∑j=n(t)nxij(t),i=1,...,m(t),    bj(t)≥∑i=1m(t)xij(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=0T-1-∑i=1m(t)∑j=1n(t)Aijxij(t)+K∑i=1m∑j=1nuij+(t), (12)
46 где верхняя срезка разности равна
47 uij+(t)=maxuij(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=0T-1-∑i=1m(t)∑j=n(t)nAijxij(t)+K∑i=1m∑j=1nΔxij2(t). (15)
53 Этот показатель необходимо минимизировать при ограничениях
54 x∈B≜∏t=-1T-1B(t). (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).

Библиография

1. Ашманов С.А. (1981). Линейное программирование. М.: Наука.

2. Васильев Ф.П. (1981). Методы решения экстремальных задач. М.: Наука.

3. Васин А.А., Григорьева О.М., Лесик И.А. (2017). Синтез транспортной системы много-узлового конкурентного рынка с переменным спросом // Прикладная математика и информатика: труды факультета ВМК МГУ имени М.В. Ломоносова. Под ред. В.И. Дмитриева. М.: МАКС Пресс. № 55. С. 74–90.

4. Васин А.А., Григорьева О.М., Лесик И.А. (2018). Задача оптимизации транспортной системы энергетического рынка. В сб.: IX Московская международная конференция по исследованию операций (ORM2018). Труды. А.А. Васин, А.Ф. Измаилов (отв. ред.). С. 247–251.

5. Васин А.А., Григорьева О.М., Цыганов Н.И. (2017). Оптимизация транспортной системы энергетического рынка // Доклады Академии наук. Т. 475. № 4. С. 377–381.

6. Васин А.А., Морозов В.В. (2005). Теория игр и модели математической экономики. М.: МАКС Пресс.

7. Корбут А.А., Финкильштейн Ю.Ю. (1969). Дискретное программирование. Под. ред. Д.Б. Юдина. М.: Наука.

8. Лесик И.А., Перевозчиков А.Г. (2016). Определение оптимальных объемов производства и цен реализации в линейной модели многопродуктовой монополии // Экономика и математические методы. Т. 52. № 1. C. 140–148.

9. Лесик И.А., Перевозчиков А.Г. (2020). Динамическая модель инвестиций в научные исследования олигополии // Экономика и математические методы. Т. 56. № 2. C. 102–114.

10. Лесик И.А., Перевозчиков А.Г. (2021). Динамическая модель рынка разработки программного обеспечения на основе задачи о назначении на узкие места // Экономика и математические методы. Т. 57. № 4. C.108–116.

11. Лесик И.А., Перевозчиков А.Г. (2022). Статическая модель рынка разработки программного обеспечения на основе транспортной задачи с квадратичными добавками по стоимости // Экономика и математические методы, 58, 3, 146–160.

12. Макаров В.Л., Рубинов Ф.М. (1973). Математическая теория экономической динамики и равновесия. М.: Наука.

13. Мезоэкономика развития (2011). Под ред. Г.Б. Клейнера. М.: Наука.

14. Перевозчиков А.Г., Лесик И.А. (2014). Нестационарная модель инвестиций в основные средства предприятия. В сб.: Прикладная математика и информатика: труды факультета ВМК МГУ имени М.В. Ломоносова. Под ред. В.И. Дмитриева. М.: МАКС Пресс, 46, 76–88.

15. Поляк Б.Т. (1983). Введение в оптимизацию. М.: Наука.

16. Сергиенко А.М., Симоненко В.П., Симоненко А.В. (2016). Улучшенный алгоритм назначения для планировщиков заданий в неоднородных распределительных вычислительных системах // Системнi дослiдженiя та информацiйни технологии. № 2. С. 20–35.

17. Устюжанина Е.В., Дементьев В.Е., Евсюков С.Г. (2021). Транзакционные цифровые платформы: задача обеспечения эффективности // Экономика и математические методы. Т. 57. № 1. C. 5–18.

18. Цурков В.И. (1981). Декомпозиция в задачах большой размерности. М.: Наука.

19. Debreu G. (1954). Valuation equilibrium and Pareto optimum. Proceedings of the National Academy of Sciences of the USA, 40, 588–592.

20. 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.

Комментарии

Сообщения не найдены

Написать отзыв
Перевести