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

 Описывается применение ТЗНД для построения цифровых платформ на рынке разработки программного обеспечения для загрузки заданий исполнителям.

 

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

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

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 Acad-emy 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 Sys-tems. EuroSys, 12. New York, 365–378.

Комментарии

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

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