Везде
Market’s static model for software development based on a transport problem with non-fixed time additions
Table of contents
Annotation Estimate Publication content
References Comments
Share
QR
Metrics
Market’s static model for software development based on a transport problem with non-fixed time additions
Annotation
PII
S042473880019969-4-1
DOI
10.31857/S042473880019969-4
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: Moscow, Russian Federation
Edition
Volume 58 Issue 2
Pages
97-111
Abstract

 

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

 

Keywords
transport problem with non-fixed time additions, approximation of the classical transport problem, geometric interpretation, branch-and-bound method, lower estimates of the criterion, ε-optimal version of the branch-and-bound method.
Received
04.05.2022
Date of publication
18.06.2022
Number of purchasers
11
Views
455
Readers community rating
0.0 (0 votes)
Cite   Download pdf
1

ВВЕДЕНИЕ
2 В статье рассматривается задача определения оптимальных планов назначения исполнителей по работам в статической модели рынка разработки программного обеспечения (РПО) на базе транспортной задачи (ТЗ) с фиксированными добавками (ФД) по времени. В отличие от существующей ТЗ с ФД по критерию минимума стоимости (Корбут, Финкильштейн, 1969) мы предлагаем использовать минимаксный критерий, как в классической ТЗ по времени, но с временами, которые кроме фиксированных добавок могут содержать часть, пропорциональную объемам назначения, т.е. гибридную постановку ТЗ с ФД по стоимости и классической ТЗ по времени. Такие задачи возникают при ограниченности суммарного объема транспортных средств, которые приходится использовать многократно, и при наличии некоторой фиксированной добавки, возникающей с учетом задержки принятия логистических решений цифровой платформой. В существующих платформах PBS1, LSF2, NQE, I-SOFT (Ding et al., 2012), EASY3 (What is Condor? 2006), LoadLeveler4 (IBM Tivoli Workload Scheduler LoadLeveler, 2007) для решения транспортной задачи и ее частного случая — задачи о назначениях — рассматривается в основном статический вариант с горизонтом планирования, равным одному периоду. Поэтому в настоящей работе мы сосредоточились на ТЗ с НП по времени. Такая схема будет более общей, чем построенная на основе ЗН на УМ, поскольку предполагает наличие переменной части времени, пропорциональной объемам поставок по соответствующему маршруту.
1. PBS Works (официальный сайт компании Altair Engineering, Inc, 2006, >>>>

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

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

4. IBM Tivoli Workload Scheduler LoadLeveler (официальный сайт компании «Интерфейс», 2007, >>>>
3 Для цифровых платформ на рынке РПО частные показатели интерпретируются как цена одного дня для каждого назначения, которая может учитывать скидку на объем поставки. Таким образом, учитывается не только базовая розничная цена, но и скидка на опт. Оптимизация производится в интересах цифровой платформы, которая является как бы оптовым поставщиком и хотела бы продавать свой ресурс в розницу насколько это возможно. В результате возникает максиминная задача максимизации наименьшей цены поставки. Это позволяет учесть разницу между оптовой и розничной ценой, которая может быть для каждого назначения определена построением соответствующего линейного тренда по ретроспективным данным. Поэтому предложенная ТЗ с НД является уточнением ЗН на УМ в части разницы между оптовыми и розничными ценами.
4 Практическая значимость работы связана с использованием статической модели для распределения ресурсов и заданий на рынке РПО для создания соответствующих цифровых трансакционных платформ (Устюжанина, Дементьев, Евсюков, 2021). Несмотря на постоянное увеличение объема сделок, на рынке РПО отсутствуют глобальные платформы по типу указанных выше универсальных платформ распределения заданий PBS, LSF, NQE, I-SOFT, EASY, LoadLeveler. Такие платформы могли быть применены в динамическом алгоритме загрузки заданий хотя бы для получения начального плана, который в динамической модели является элементом управления. Это приводит к большому числу посредников в цепочке, ведущей от заказчика к исполнителю, что влечет уменьшение стоимости работ для исполнителя до 10 раз по сравнению со стоимостью, которую готовы были платить заказчики. Таким образом, создание цифровой платформы на рынке РПО могло бы привести к более справедливому распределению доходов и росту общественного благосостояния. Максимизация же последнего равносильна, как известно, определению глобального равновесия на рынке РПО в соответствии с теоремой нобелевского лауреата Дебре (Debreu, 1954).
5 В общетеоретическом плане концепция равновесия (Макаров, Рубинов, 1973) на распределенном рынке однородного товара относится к мезоэкономике (Мезоэкономика развития, 2011) и лежит в основе синтеза транспортной системы многоузлового конкурентного рынка с переменным спросом и предложением (Васин, Григорьева, Лесик, 2017, 2018; Васин, Григорьева, Цыганов, 2017).
6 Основным результатом работы являются исследование статической ТЗ с НД по времени. Показано, что поставленная дискретно-непрерывная задача может быть аппроксимирована сверху классической ТЗ по времени, которую можно получить и по схеме, разработанной в (Balinski, 1961). Приводится точный алгоритм метода ветвей и границ (МВГ) и модельный пример его использования. Рассматривается ε-оптимальная версия метода ветвей и границ, полученная по аналогии с решением многомерной задачи о назначениях (Корбут, Финкильштейн, 1969) и особенности ее использования.
7

1. ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ С НЕФИКСИРОВАННЫМИ ДОБАВКАМИ ПО ВРЕМЕНИ
8 Пусть, как в обычной транспортной задаче, i=1,  ...,  m — пункты производства некоторого однородного товара, j=1,  ...,  n  — пункты его потребления. Даны величины: ai>0  — объем производства в пункте производства i ; bj>0  — объем потребления в пункте потребления j , отнесенные к одному периоду времени (горизонту планирования).
9 Требуется составить план перевозок x=xij объемов перевозок из пункта i в пункт j , удовлетворяющий обычным транспортным ограничениям
10 xij≥0,∑j=1nxij=ai,∑i=1mxij=bj,    i∈M={1,...,m},    j∈N={1,...,n} (1)
11 и минимизирующий общее время перевозки
12 I(x)=max(i,j):xij>0τij(xij)→inf, (2)
13 где предполагается, что ∑i=1mai=∑j=1nbj , а частные временные показатели под знаком максимума задаются формулами
14 τij(xij)=0,    xij=0;Tij+tijxij/Vij,    xij>0; (3)
15 Tij — постоянные затраты времени, необходимые для организации перевозки по данному маршруту; tij — время перевозки за одну ездку; Vij — суммарный объем транспортных средств на данном маршруте; xij/Vij — число поездок, необходимое для перевозки объема xij .
16 Простейшие примеры показывают, что функция связанного максимума (3) может быть разрывной (Федоров, 1979). При этом справедлива следующая лемма.
17 Лемма 1. Функция связанного максимума I(x) полунепрерывна снизу в допустимой области (1).
18 Доказательство. Пусть дана последовательность xn→x0 и B(x0)=(i,j):xij0>0 , тогда для всех достаточно больших выполняются неравенства xijn>0    ∀(i,j)∈B(x0)⇒B(xn)⊇B(x0), откуда следует
19 max(i,j)∈B(xn)fij(xij)≥max(i,j)∈B(x0)fij(xij)⇒limx→∞infI(xn)≥limx→∞infmax(i,j)∈B(x0)fij(xij)=I(x0).
20 Причем последнее равенство верно в силу непрерывности частных показателей.
21 Замечание 1. В силу доказанного утверждения инфимум в постановке задачи (1)–(3) можно заменить на минимум.
22 Задачу (1)–(3) назовем транспортной задачей с нефиксированными добавками (ТЗНД) по времени, в отличие от транспортной задачи с фиксированными доплатами (ТЗФД) по стоимости (Корбут, Финкильштейн, 1969).
23

2. АППРОКСИМАЦИЯ ЗАДАЧИ
24 Введение дополнительных целочисленных переменных в ТЗНД (1)–(3) по времени позволит нам свести задачу к классической ТЗ по времени. Для ТЗФД такой способ был указан в (Balinski, 1961), и он подходит для ТЗНД (1)–(3) по времени, но в нем будут присутствовать некоторые особенности. Положим Mij=minai,bj,    i=1,...,m,    j=1,...,n.
25 Рассмотрим частично-целочисленную задачу минимизации
26 max(i,j)(Tijyij+tijxij/Vij)→min (4)
27 при условиях (1) и дополнительных условиях
28 yij=0,1;    xij≤Mijyij. (5)
29 Тогда задача (1), (4), (5) эквивалентна исходной задаче (1)–(3) и может быть аппроксимирована сверху (по значению) классической ТЗ по времени:
30 max(i,j)(Tijyij+tijxij/Vij)≤max(i,j)(Tij+tijMij/Vij)yij=max(i,j);xij>0(Tij+tijMij/Vij)→min (6) при условиях (1). Справедлива следующая лемма.
31 Лемма 2. Задача (1)–(3) аппроксимируется сверху по значению обычной транспортной задачей (1), (6) по времени.
32 Замечание 2. В частном случае задачи о назначениях Mij=1 задача (1)–(3) эквивалентна обычной ТЗ (1), (4), (7) по времени, в чем легко убедиться непосредственной проверкой.
33 Замечание 3. В частности, когда ai≡1,    bi≡1    (m=n), имеем задачу о назначениях на узкие места (Форд, Фалкерсон, 1966).
34

3. МЕТОД ВЕТВЕЙ И ГРАНИЦ
35 Для точного решения дискретно-непрерывной задачи (1)–(3) разобьем допустимое многогранное множество на непустые грани и возьмем их относительные внутренности (Сухарев, Тимохов, Федоров, 1986). Каждая такая грань получается фиксированием подмножеством B⊂M×N пар индексов (i,j) , на которых соответствующие переменные удовлетворяют условиям:
36 xij>0,    (i,j)∈B , xij=0,    (i,j)∉B. (7)
37 Положим
38 IB=infx∈X-Bmax(i,j)∈Bτij(xij). (8)
39 Здесь XB⊆X — подмножество допустимых решений X ограничений (1), удовлетворяющих дополнительным ограничениям (7). Поскольку относительные внутренности непустых граней непусты (XB≠ϕ) (Сухарев, Тимохов, Федоров, 1986, с. 65), то замыкание X-B подмножества XB⊆X получается заменой строгих неравенств (7) нестрогими (Федоров, 1979, с. 30):
40 xij≥0,    (i,j)∈B, xij=0,    (i,j)∉B, (9)
41 задача (1), (7), (8) равносильна задаче
42 IB=minx∈X-BIB(x)=minx∈X-Bmax(i,j)∈Bτij(xij). (10)
43 Задача (1), (9), (10) является задачей выпуклого программирования, поэтому исходная задача (1)–(3) сводится к решению задач выпуклого программирования на непустых гранях. Справедлива следующая лемма.
44 Лемма 3. Минимальное значение I общего показателя в задаче (1)–(3) получается как наименьшее значение IB задачи (10) по всем B⊂M×N .
45 Поскольку это комбинаторная задача, то в общем случае для точного решения необходимо использовать метод ветвей и границ. Узлы поискового орграфа можно отождествить с подмножествами B-⊂M×N , дополняющими множества B в M×N . Ориентированной дугой связываются любые два подмножества B'-⊇B''- , отличающихся одним элементом.
46 Спрашивается, как получить нижние оценки в ТЗНД по времени. Для этого можно снять все ограничения xij=0 в данном узле поискового орграфа, но оставить тот же критерий с теми же функциями и в том же количестве под знаком максимума, который следует минимизировать на всем допустимом множестве X . Тогда показатель не изменится, а множество расширится, в результате минимум станет меньше. Полученная задача является задачей выпуклого программирования, которая может быть решена методом Б.Т. Поляка (Поляк, 1983).
47 Для вычисления IB в узлах поискового орграфа можно снять равенства в ограничениях (9) при помощи штрафной функции (Федоров, 1979):
48 LB(x)=∑(i,j)∈B-xij2. (11)
49 Тогда приходим к показателю
50 JB(x)=IB(x)+CLB(x) , (12)
51 который также следует минимизировать на всем допустимом множестве X . Здесь C>0  — достаточно большая константа.
52 В силу линейности частных показателей в (10) и выпуклости (11) показатель (12) представляет собой выпуклую функцию такого же типа, как при вычислении нижних оценок.
53 Теперь мы выясним, сколько может быть нулевых переменных xij . Поскольку имеем mn-m-n+1=(m-1)(n-1) независимых переменных, то нулевых переменных может быть не более (m-1)(n-1) и размерность граней может принимать соответственно значения 0,  1  ,...,  (m-1)(n-1)-1 в невырожденном случае.
54

4. ПРИМЕР ТОЧНОГО РЕШЕНИЯ ЗАДАЧИ
55 Пример 1. Предположим, что a=(5,  4),    b=(2,  4,  3) , а исходные матрицы имеют вид:
56 T=123432 , t=325245 , V=243243, (13)
57 тогда
58 M=243243.
59 Рассмотрим сначала основной случай, когда все xij>0 . Тогда, исключая зависимые переменные в первом столбце и первой строке, приходим к показателю
60 I(x)=maxT11+t11a1-(b2-x22)-(b3-x23)/V11,    T21+t21(a2-x22-x23)/V21,T12+t12(b2-x22)/V12,T13+t13(b3-x23)/V13,    T22+t22x22/V22,    T23+t23x23/V23→min (14)
61 при ограничениях
62 a1-(b2-x22)-(b3-x23)≥0,    a2-x22-x23≥0,    b2-x22≥0,    b3-x23≥0,    x22,  x23≥0,
63 или a2≥x22+x23≥b2+b3-a1,    b2≥x22≥0,    b3≥x23≥0, или с учетом значения параметров
64 4≥x22+x23≥2,    4≥x22≥0;    3≥x23≥0. (15)
65

Рис. 1. Допустимая область независимых переменных в примере 1
66 С учетом значений параметров общий показатель (14) примет вид:
67 I(x)=max[3(x22+x23)/2-2],    [8-x22-x23],[4-x22/2)],    [8-5x23/3],    [3+x22],    [2+5x23/3]→min. (16)
68 Мы видим, что согласно (15) значение 4 входит в область значений всех частных показателей, стоящих под знаком максимума в (16) (рис. 1). Построим линии уровней частных показателей с этим значением, тогда из соображений, в какую сторону будут сдвигаться линии при росте значения переменных, решение задачи локализуется в конфликтной области
69 4≥x22+x23,    x22≥1;    2,4≥x23≥1,2.
70 Перебирая возможные варианты уравнивания соответствующих частных показателей, убеждаемся, что единственное решение соответствует системе
71 8-53x23=3+x22⇒103x23=6⇒x23=1,8;2+53x23=3+x22⇒3+x22=5⇒x22=2.
72 При этом общее значение уравненных частных показателей равно 3+x22≈3+2=5. Не вошедший в тройку уравненных показателей частный показатель будет 8-x22-x23=8-3,8=4,2<5, следовательно, остальные частные показатели, не вошедшие в четверку конфликтующих, будут заведомо иметь значения меньше 5, что и требовалось проверить.
73 Замечание 4. Аналогично разбираются остальные случаи, когда какие-то xij=0 . Это соответствует одномерным отрезкам границы и вершинам, т.е. 5+5=10 случаев! Согласно лемме 3 решение ТЗНД по времени сводится к ее решению на всех гранях.
74 Приведем соответствующие расчеты и вычислим нижние оценки в узлах поискового орграфа, необходимые в примере размера 2×3 работы МВГ, и значения критерия в полученных точках для отсева неперспективных вариантов и их наследников.
75 0-мерные грани
76 Узел 1.
77 x22=4,    x23=0⇒τ11=3(x22+x23)/2-2=4;    τ12=4-x22/2=2;τ13=8-5x23/3=8;    τ21=8-x22-x23=4;    τ22=3+x22=7;    τ23=2+5x23/3=2;x11=x22+x23-2=2;    x12=4-x22=0;    x13=3-x23=3;    x21=4-x22-x23=0;x22=4;    x23=0⇒max(4,8,7)=8>5.
78 Нижняя оценка получается в результате решения задачи
79 max(3(x22+x23)/2-2,    8-5x23/3,    3+x22)→min. (17)
80 Здесь минимум берется по всей допустимой области значений переменных. Минимум достигается на прямой 8-5x23/3=3+x22⇔x22+5x23/3=5 , когда общее значение 3+x22 минимально, т.е. при x22=0⇒x23=3 , когда 3+x22=3 . Это и есть минимальное значение показателя в задаче (17), равное нижней оценке в узле 1.
81 Точка, в которой достигается нижняя оценка, имеет два нуля x22,x13=0 , поэтому значение критерия равно максимуму показателей для других переменных max(2,5;4;5;7)=7 .
82 Узел 2.
83 x22=2,    x23=0⇒τ11=1,5(x22+x23)-2=1;    τ12=4-0,5x22=3;    τ13=8-5x23/3=8;τ21=8-x22-x23=6;    τ22=3+x22=5;    τ23=2+5x23/3=2;x11=x22+x23-2=0;    x12=4-x22=2;    x13=3-x23=3;x21=4-x22-x23=0;    x22=2;x23=0;⇒max(3,8,6,5)=8>5.
84 Нижняя оценка получается в результате решения задачи
85 max(4-x22/2,    8-5x23/3,    8-x22-x23,    3+x22)→min. (18)
86 Здесь минимум берется по всей допустимой области значений переменных. Перебирая возможные варианты уравнивания соответствующих частных показателей, убеждаемся, что единственное решение соответствует системе
87 8-5x23/3=8-x22-x23⇒x22=5-5x23/3=75/21=1,429;3+x22=8-x22-x23⇒2x22+x23=5⇒x23=15/7≈2,143.
88 При этом общее значение уравненных частных показателей равно 8-x22-x23≈4,429, не вошедший в тройку уравненных показателей (18) — 4-x22/2≈3,285<4,429. Значит, остальные частные показатели будут заведомо меньше 4,429 , что и требовалось проверить. Это и есть минимальное значение показателя в задаче (18), равное нижней оценке в узле 2.
89 Точка, в которой достигается нижняя оценка, не имеет нулей xij , поэтому значение критерия равно максимуму показателей для всех переменных max(3,358;3,286;4,428;4,428;4,428;5,572)=5,572 .
90 Узел 3.
91 x22=0,x23=2⇒τ11=3(x22+x23)/2-2=1;    τ12=4-x22/2=4;    τ13=8-5x23/3=14/3;τ21=8-x22-x23=6;    τ22=3+x22=3;    τ23=2+5x23/3=16/3;    x11=x22+x23-2=0;x12=4-x22=4;    x13=3-x23=1;    x21=4-x22-x23=2;    x22=0;x23=2⇒max(4,    14/3,    6,    16/3)=6>5.
92 Нижняя оценка получается в результате решения задачи
93 max(4-x22/2,    8-5x23/3,    8-x22-x23,    2+5x23/3)→min. (19)
94 Здесь минимум берется по всей допустимой области значений переменных. Перебирая возможные варианты уравнивания соответствующих частных показателей, убеждаемся, что единственное решение соответствует системе
95 8-5x23/3=8-x22-x23⇒x23=18/10=1,8;2+5x23/3=8-x22-x23⇒8-x22-x23=5⇒x22=1,2.
96 При этом общее значение уравненных частных показателей равно 8-x22-x23=5, не вошедший в тройку уравненных показателей (19) — 4-0,5x22=3,4<5. Значит, остальные частные показатели будут заведомо меньше 5, что и требовалось проверить. Это и есть минимальное значение показателя в задаче (19), равное нижней оценке в узле 3.
97 Точка, в которой достигается нижняя оценка, не имеет нулей xij , поэтому значение критерия равно максимуму показателей для всех переменных max(2,25;  3,4;  5;  5;  4,2;  5)=5 . Узел 4.
98 x22=0,x23=3⇒τ11=3(x22+x23)/2-2=5/2;    τ12=4-x22/2=4;    τ13=8-5x23/3=3;τ21=8-x22-x23=5;    τ22=3+x22=3;    τ23=2+5x23/3=7;    x11=x22+x23-2=1;x12=4-x22=4;    x13=3-x23=0;    x21=4-x22-x23=1;    x22=0;x23=3⇒max(5/2,  4,  5,  7)=7>5.
99 Нижняя оценка получается в результате решения задачи
100 max(3(x22+x23)/2-2,    4-x22/2,    8-x22-x23,    2+5x23/3)→min. (20)
101 Здесь минимум берется по всей допустимой области значений переменных. Минимум достигается на прямой 8-x22-x23=2+5x23/3⇔x22+8x23/3=6 , когда общее значение 2+5x23/3 минимально, т.е. при x23=1,2 , когда x22=2,8 и 2+5x23/3=4 . Это и есть минимальное значение показателя в задаче (20), равное нижней оценке в узле 4.
102 Точка, в которой достигается нижняя оценка, не имеет нулей xij , поэтому значение критерия равно максимуму показателей для всех переменных max(4;2,6;6;4;5,8;4)=6 .
103 Узел 5.
104 x22=1,x23=3⇒τ11=3(x22+x23)/2-2=4;    τ12=4-x22/2=7/2;    τ13=8-5x23/3=3;τ21=8-x22-x23=4;    τ22=3+x22=4;    τ23=2+5x23/3=7;    x11=x22+x23-2=2;x12=4-x22=3;    x13=3-x23=0;    x21=4-x22-x23=0;    x22=1;    x23=3⇒max(4,  7/2,  4,  7)=7>5.
105 Нижняя оценка получается в результате решения задачи
106 max3(x22+x23)/2-2,    4-x22/2,    3+x22,    2+5x23/3→min. (21)
107 Здесь минимум берется по всей допустимой области значений переменных. Минимум достигается на прямой 3+x22=2+5x23/3⇔x22=5x23/3-1 , когда общее значение 3+x22 минимально, когда x22+x23=2 , откуда 8x23/3=3 ⇒x23=9/8=1,125 ⇒x22=2-x23=0,875 и 3+x22=3,875 . Это и есть минимальное значение показателя в задаче (21), равное нижней оценке в узле 5. При этом 4-x22/3≈3,562<3,875 , что и требовалось проверить.
108 Точка, в которой достигается нижняя оценка, имеет два нуля x13=0 , поэтому значение критерия равно максимуму показателей для других переменных max(4;3,5;4;4;7)=7 .
109 1-мерные грани
110 Узел 6.
111 2<x22<4,    x23=0⇒τ11=3(x22+x23)/2-2<4;    τ12=4-x22/2<3;    τ13=8-5x23/3=8;τ21=8-x22-x23<6;    τ22=3+x22<7;    τ23=2+5x23/3=2;    x11=x22+x23-2=x22->0;x12=4-x22>0;    x13=3-x23=3;    x21=4-x22-x23=4-x22>0;    x22>2;x23=0;⇒max(4,  3,  8,  6, 7,  8)=8>5.
112 Нижняя оценка:
113 max(3(x22+x23)/2-2,    4-x22/2,    8-5x23/3,    8-x22-x23,    3+x22)→min, (22)
114 минимум берется по всей допустимой области значений переменных. Перебирая возможные варианты уравнивания соответствующих частных показателей, убеждаемся, что единственное решение соответствует системе
115 8-5x23/3=8-x22-x23⇒x22=5-5x23/3=75/21=1,429;3+x22=8-x22-x23⇒2x22+x23=5⇒x23=15/7≈2,143.
116 При этом общее значение уравненных частных показателей равно 8-x22-x23≈4,429,
117 а не вошедшие в тройку уравненных показателей (22)
118 3(x22+x23)/2-2≈3,358<4,429,4-x22/2≈3,285<4,429.
119 Значит, остальные частные показатели будут заведомо меньше 4,429 , что и требовалось проверить. Это и есть минимальное значение показателя в задаче (22), равное нижней оценке в узле 6.
120 Точка, в которой достигается нижняя оценка, не имеет нулей xij , поэтому значение критерия равно максимуму показателей для всех переменных max(3,358;3,286;4,428;4,428;4,428;5,572)=5,572 , как в вершине 2.
121 Узел 7.
122 x22,x23>0,    x22+x23=2⇒τ11=3(x22+x23)/2-2=1;    τ12=4-x22/2<4;14/3<τ13=8-5x23/3<8;    τ21=8-x22-x23=6;    3<τ22=3+x22<5;2<τ23=2+5x23/3<16/3;    x11=x22+x23-2=0;    x12=4-x22>2;    x13=3-x23>1;    x21=4-x22-x23=2;    x22>0;x23>0;    ⇒max(6,8-5x23/3)→inf,0<x23<2⇒6=8-5x23/3,    x23=6/5⇒max=6>5.
123 Нижняя оценка
124 max(4-x22/2,  8-5x23/3,  8-x22-x23,  3+x22,  2+5x23/3)→min (23)
125 равна 5. Это показывается так же, как в основном случае, когда все переменные положительны. Основной случай обозначим узлом 11, чтобы в построенном орграфе дуги вели от вершин с меньшими номерами к большим. Введем еще начальный узел (узел 0), с которым соединим узлы 1–5. Кроме того, каждый узел соединим с терминальным узлом такого же номера, но пометим их индексом «0» и будем приписывать им значения терминального узла в случае его раскрытия, т.е. получения всех непосредственно следующих за ним узлов поискового орграфа (рис. 2).
126

127 Рис. 2. Поисковый орграф в примере 1
128 Перебирая возможные варианты уравнивания соответствующих частных показателей, убеждаемся, как в основном варианте, что имеется только единственное решение x23=1,8;    x22=2 . При этом общее значение уравненных частных показателей равно 5. Значит, остальные частные показатели, не вошедшие в четверку конфликтующих, будут заведомо меньше 5, что и требовалось проверить.
129 Узел 8.
130 (x22+x23)-2<7/2;    τ12=4-x22/2=4;    3<τ13=8-5x23/3=14/3<5;τ21=8-x22-x23<6;    τ22=3+x22=3;    16/3<τ23=2+5x23/3<7;    x11=x22+x23-2>0;x12=4-x22=4;    x13=3-x23>0;    x21=4-x22-x23>0;    x22=0;x23>2    ⇒max(8-x23,2+5x23/3)→inf,    2<x23<3⇒8-x23=2+5x23/3,    x23=18/8⇒inf=8-x23=5,75>5.
131 Нижняя оценка:
132 max(3(x22+x23)/2-2,    4-/2x22,    8-5x23/3,    8-x22-x23,    2+5x23/3)→min, (24)
133 минимум берется по всей допустимой области значений переменных. Перебирая возможные варианты уравнивания соответствующих частных показателей, убеждаемся, как и в вершине 2, что единственное решение соответствует системе
134 8-5x23/3=8-x22-x23⇒6=10x23/3⇒x23=18/10=1,8;2+5x23/3=8-x22-x23⇒x22+8x23/3=6⇒x22=1,2.
135 При этом общее значение уравненных частных показателей равно 8-x22-x23=5, а не вошедшие в тройку уравненных показателей (24) будут
136 3(x22+x23)/2-2=2,5<5;    4-x22/2=3,6<5.
137 Значит, остальные частные показатели, не вошедшие в четверку конфликтующих, будут заведомо меньше 5, что и требовалось проверить. Это и есть значение минимальное показателя в задаче (24), равное нижней оценке в узле 8.
138 Точка, в которой достигается нижняя оценка, не имеет нулей xij , поэтому значение критерия, как в вершине 3, равно максимуму показателей для всех переменных max(2,25;3,4;5;5;4,2;5)=5 .
139 Узел 9.
140 x22=3,    0<x23<1⇒τ11=3(x22+x23)/2-2<4;    τ12=4-x22/2=2,5;τ13=8-5x23/3>6/3;    τ21=8-x22-x23<5;    τ22=3+x22=6;    τ23=2+5x23/3<6/3;x11=x22+x23-2>1;    x12=4-x22=1;x13=3-x23>2;    x21=4-x22-x23>0;x22=3;0<x23<1;    ⇒max(8-5x23/3)→inf,    0<x23<1⇒inf=6/3>5.
141 Нижняя оценка:
142 max(3(x22+x23)/2-2,    4-x22/2,    8-5x23/3,    8-x22-x23,    3+x22,    2+5x23/3)→min. (25)
143 Минимум берется по всей допустимой области значений переменных. Это совпадает с основным случаем 11. Поэтому нижняя оценка в вершине 9, совпадающая с минимумом в (25), равна 5. Перебирая возможные варианты уравнивания соответствующих частных показателей, убеждаемся, как в основном варианте, что единственное решение x23=1,8; x22=2 . При этом общее значение уравненных частных показателей равно 5. Значит, остальные частные показатели, не вошедшие в четверку конфликтующих, будут заведомо меньше 5, что и требовалось проверить.
144 Узел 10.
145 1<x22<4,    0<x23<3,    x22+x23=4⇒x22=4-x23,    τ11=3(x22+x23)/2-2=4;τ12=4-x22/2<3,5;    τ13=8-5x23/3<8;    τ21=8-x22-x23=4;    τ22=3+x22<7;τ23=2+5x23/2<7;    x11=x22+x23-2=2;    x12=4-x22>0;    x13=3-x23>0;x21=4-x22-x23=0;    x22>1;    x23>0⇒max(4,    8-5x23/2,    3+x22=7-x23,    2+5x23/2)→inf,0<x23<3⇒2+5x23/2=7-x23⇒x23=15/8⇒inf=7-x23=41/8>5.
146 Нижняя оценка:
147 max(3(x22+x23)/2-2,    4-x22/2,    8-5x23/3,    3+x22,    2+5x23/3)→min. (26)
148 И она равна 5. Это показывается так же, как в основном случае, когда все переменные положительны. Убеждаемся, как в основном варианте, что единственное решение x23=1,8; x22=2. При этом общее значение уравненных частных показателей равно 5. Значит, остальные частные показатели, не вошедшие в четверку конфликтующих, будут заведомо меньше 5, что и требовалось проверить.
149 Процесс раскрытия вершин в примере 1 в классической схеме метода ветвей и границ с использованием правила отсева из (Финкильштейн, 1976) приведен на рис. 3. Через косую черту около узлов указана нижняя оценка, перед чертой стоит значение общего показателя в точке, в которой достигается нижняя оценка. Классическое правило отсева состоит в том, что на каждом шаге отбрасываются узлы со значениями не меньше текущего рекорда r .
150

Рис. 3. Классическая схема метода ветвей и границ: рекорд — r=5 , точность — ε=0 , граница отсева — b=r=5
151 Замечание 5. Сокращение МВГ было вызвано тем, что к этому времени на этапе определения решения уже отброшены все пустые грани прямым методом перебора граней, что эквивалентно этому решению, но служит для наглядности описания МВГ. Это позволяет проиллюстрировать МВГ в полноформатном модельном примере 2×3 и, в частности, получить контрпример супер- (суб-) модулярности ТЗНД по времени (Хачатуров и др., 20212).
152 Процесс раскрытия вершин в примере 1 в ε-оптимальной схеме метода ветвей и границ с использованием правила отсева из (Финкильштейн, 1976) приведен на рис. 4. Обобщенное правило отсева состоит в том, что на каждом шаге отбрасываются узлы со значениями не меньше текущего рекорда r , умноженного на 1+ε .
153

154 Рис. 4. Классическая схема метода ветвей и границ: рекорд — r=5 , точность — ε=0,15=15%, граница отсечения — b=(1+ε)r=5,75
155

5. КОНТРПРИМЕР СУБМОДУЛЯРНОСТИ
156 Напомним, что функция C=C(ω) , определенная на 2J, называется супер- (суб-) модулярной, если ∀δ,ν∈2J выполняется неравенство C(δ)+C(γ)≤(≥)C(δ∪γ)+C(δ∩γ).
157 Пример 2. Для краткости будем обозначать тип θ(x) узла в примере 1 x=(x11,...,x23) по знакам соответствующих компонент, определяемых функцией θ(x)=(signx11,...,signx23) . Тогда θ(x) можно отождествить с индикаторной функцией подмножества пар индексов, B(x)=(i,j):xij>0 и применять к ним теоретико-множественные операции объединения и пересечения.
158 1. Пусть δ=1, θ(δ)=(1,1,1,1,1,0), γ=2, θ(γ)=(0,1,1,1,1,1) . Тогда θ(δ)∪θ(γ)=(1,1,1,1,1,1)=θ(6), θ(δ)∩θ(γ)=(0,1,1,1,1,0)=θ(2) и C(δ)+C(γ)=8+6≥C(δ∪γ)+C(δ∩γ)=5+2 , где C(γ)=I(B(γ)) и x отождествляется с номером γ вершины поискового орграфа МВГ.
159 2. Пусть δ=3, θ(δ)=(1,1,1,1,0,1), γ=5, θ(γ)=(0,1,1,1,1,1) . Тогда θ(δ)∪θ(γ)=(1,1,1,1,1,1)=θ(6), θ(δ)∩θ(γ)=(0,1,1,1,0,1)=θ(3) и C(δ)+C(γ)=5, 750+5,125≤C(δ∪γ)+C(δ∩γ)=5+6 .
160

6. МЕТОД СУБГРАДИЕНТНОГО СПУСКА ДЛЯ НАХОЖДЕНИЯ НИЖНИХ ОЦЕНОК

161 Рассмотрим задачу нахождения нижней оценки в узле B- :
162 I_B=minx∈XIB(x)=minx∈Xmax(i,j)∈Bτij(xij). (27)
163 Показатель (27) представляет собой выпуклую функцию. Исключая зависимые переменные из балансовых ограничений, как мы это делали в примере 1, приходим к задаче выпуклого программирования на множестве допустимых значений, заданной системой неравенств:
164 Fk(x)≤0,    k=1,...,l (28)
165 с линейными функциями Fk(x) и условием принадлежности объемлющему параллелепипеду W :
166 xij∈Wij=0,aij    ∀(i,j), (29)
167 которую можно свернуть в одно скалярное неравенство при помощи функции максимума
168 maxk=1,...,lFk(x)≤0. (30)
169 Эту задачу можно решить методом Б.Т. Поляка (Поляк, 1983):
170 xijk+1=PWij(xijk-λkνijk)    ∀(i,j),    k=0,1,...,νk∈∂IB(xk),F(xk)≤0,∂F(xk),F(xk)>0,    λk→+0,    ∑k=0∞λk=∞, (31)
171 где k  — номер шага; λk  — программный шаг метода; PWij(xij)  — оператор проектирования на компоненту Wij объемлющего параллелепипеда W . Очевидно, что множество допустимых решений X ограничено и имеет внутренние точки. Тогда согласно результатам (Поляк, 1983, с. 259) справедлива следующая теорема сходимости.
172 Теорема 2. Последовательность xk в методе (31) сходится к множеству решений задачи минимизации (27).
173 Замечание 6. Для получения значения основного показателя в узле, заданном подмножеством B , решается задача минимизации штрафной функции JB(x) вместо IB(x) в (27) на всем множестве X .
174

7. ПРИЛОЖЕНИЕ К ТЗНД ПО ЦЕНЕ
175 Пусть, как в обычной транспортной задаче, через i=1,  ...,  m обозначены пункты производства (разработчики ПО) некоторого однородного товара (человеко-дней при стандартном 8-часовом дне чистого рабочего времени, определяемого по таймеру), через j=1,  ...,  n  — пункты его потребления (заказчики ПО). Даны величины: ai>0  — объем производства в пункте производства i , bj>0  — объем потребления в пункте потребления j, отнесенные к одному дню (горизонту планирования).
176 Ищутся величины xij≥0 (объем перевозок из пункта i в пункт j), удовлетворяющие обычным транспортным ограничениям (1) и минимизирующие функцию
177 max(i,j):xij>0cij(xij) ,(32)
178 Где
179 cij(xij)=0,    xij=0max(dij-cijxij,    0),    xij>0. (33)
180 Здесь dij  — базовые розничные цены одного дня производителя с учетом прибыли цифровой платформы, например 30%; cijxij  — скидка к цене на оптовую поставку объема xij .
181 Введением дополнительных целочисленных переменных ТЗНД (1), (32), (33) по времени может быть сведена к классической ТЗ по времени. Способ такого сведения был указан в (Balinski, 1961) для ТЗФД, он проходит и для ТЗНД (1), (32), (33) по времени с некоторыми особенностями.
182 Рассмотрим частично-целочисленную задачу
183 min(i,j)max(dijyij-cijxij,0)→max (34)
184 при условиях (1) и дополнительных условиях (5).
185 Тогда задача (1), (5), (34) эквивалентна исходной задаче (1), (32), (33) и может быть аппроксимирована снизу (по значению) классической ТЗ по времени:
186 min(i,j)max(dijyij-cijxij,0)≥min(i,j)max(dij-cijMij)yij,0)=min(i,j);xij>0max(dij-cijMij,0)→max (35)
187 при условиях (1). Таким образом, задача (1), (32), (33) аппроксимирована снизу обычной ТЗ (1), (5), (35) по времени, которую можно решить венгерским методом расстановки пометок.
188

ЗАКЛЮЧЕНИЕ
189 В работе предложена практически значимая методика определения загрузки работ по исполнителям на рынке РПО, обеспечивающая учет скидок на опт. Основным результатом работы является постановка ТЗНД по времени, доказательство полунепрерывности общего показателя, из которого следует, что достигается его инфинум на ограниченном замкнутом множестве допустимых решений. Предложена геометрическая интерпретация решения задачи как минимума значений на непустых гранях и метод штрафов для их нахождения. Показано, что аналогично строятся нижние оценки показателя в методе ветвей и границ по непустым граням. Получена аппроксимация исходной задачей обобщенной задачей о назначения на узкие места методом (Balinski, 1961), которую можно решить модифицированным методом расстановки пометок, описанным в работе (Сергиенко, Симоненко, Симоненко, 2016), имеющим сложность O(NlgN) , где N=m+n . Приведены числовые примеры всех задач и алгоритмов их решения.
190 Практическая значимость работы определяется применением в трансакционных платформах на рынке РПО для загрузки заданий по терминологии, обоснованной в работе (Устюжанина, Дементьев, Евсюков, 2021). Построена статическая модель загрузки заданий с двумя группами агентов — компаниями–разработчиками ПО и компаниями–заказчиками ПО, которые могут опередить свои резервные цены на рынке повременной аренды разработанного ПО в двухсекторной модели экономики (Васин, Морозов, 2005). Дискриминируемыми агентами являются компании–заказчики ПО, которые оплачивают услуги оператора платформы в виде процентных надбавок, включенных оператором в цену работы компаний–разработчиков По. Имеются в виду платформы-рынки, взаимодействие экономических агентов на которых носит эпизодический характер разовых сделок. Предполагается удаленное взаимодействие, т.е. возможность коммуникации между агентами, находящимися на любом расстоянии друг от друга.
191 Допускается возможность масштабирования, что означает теоретическое отсутствие ограничений для расширения поля взаимодействия (числа пользователей). Такое расширение возможно за счет перекрестного сетевого эффекта, когда численность одного вида пользователей влияет на численность другого вида (спрос порождает предложение, и наоборот). Предполагается, что цифровые трансакционные платформы могут оказывать влияние на объем коммуникации через уровень и структуру цен. Исходя из базовых характеристик поля взаимодействия, платформа РПО относится к двусторонним рынкам. Для одноранговых (peer-to-peer) (Устюжанина, Дементьев, Евсюков, 2021) цифровых трансакционных платформ, к которым относятся платформы на рынке РПО, организующих торговые трансакции, непосредственными агентами являются поставщики — агенты, разрабатывающие ПО, и потребители — агенты, использующие разработанное ПО для повременной сдачи в аренду.
192 Операторы платформы на рынке РПО могут получать доход в виде платы пользователей за покупку, которые, в свою очередь, имеют доход в виде платы за временное пользование разработанных ПО в двухсекторной модели экономики (Васин, Морозов, 2005), цена которого определяет резервные цены потребителей.
193 В заключение следует отметить, что настоящая статья является продолжением серии статей (Перевозчиков, Лесик, 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 Acad-emy of Sciences of the USA, 40, 588–592.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Comments

No posts found

Write a review
Translate