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

Предлагается постановка непрерывной статической модели рынка разработки программного обеспечения (РПО) на базе транспортной задачи (ТЗ) с квадратичными добавками (КД) по стоимости. В отличие от существующей ТЗ с фиксированными доплатами (ФД) по стоимости предлагается постановка по минимизации суммы стоимостей транспортировки, которые могут содержать нефиксированные добавки (НД), пропорциональные квадратам объемов назначений. Таким образом, предлагается квадратичная постановка ТЗ с НД. Показано, что ТЗ с КД может быть сведена к задаче выпуклого программирования, которую можно численно решить субградиентным методом либо методом сопряженных градиентов для двойственной задачи. Приводится интерпретация ТЗ с КД как задачи о назначении (ЗН) с нефиксированными скидками (НС) по цене, учитывающими разницу между оптовой и розничной ценой. Это позволяет применить поставленную задачу для построения цифровых платформ (ЦП) на рынке разработки программного обеспечения (РПО) для загрузки заданий исполнителям.

Ключевые слова
транспортная задача с квадратичными добавками по стоимости, сведение к задаче выпуклого программирования, метод Б.Т.Поляка, двойственная задача, метод сопряженных направлений
Классификатор
Получено
11.03.2022
Дата публикации
22.09.2022
Всего подписок
11
Всего просмотров
179
Оценка читателей
0.0 (0 голосов)
Цитировать   Скачать 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), в части замены базовой статической ТЗ с НД по стоимости ТЗ с НД по времени, которая может служить фундаментальной основой для построения соответствующих цифровых платформ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

14. Сухарев А.Г., Тимохов, В.В., Федоров В.В. (1986). Курс методов оптимизации. М.: Наука.

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

16. Федоров В.В. (1979). Численные методы максимина. М.: Наука.

17. Финкильштейн Ю.Ю. (1976). Приближенные методы и прикладные задачи дискретного программирования. М.: Наука.

18. Форд Л., Фалкерсон Д. (1966). Потоки в сетях. М.: Мир.

19. Хачатуров В.Р., Хачатуров Р.В., Хачатуров Р.В. (2012). Оптимизация супермодулярных функций (супермодулярное программирование) // Журнал вычислительной математики и математической физики. Т. 52. № 6. С. 999–1000.

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

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

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

Комментарии

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

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