Market’s static model for software development based on a transport problem with non-fixed time additions
Table of contents
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
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
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
0
Views
109
Readers community rating
0.0 (0 votes)
Cite Download pdf 100 RUB / 1.0 SU

To download PDF you should sign in

Full text is available to subscribers only
Subscribe right now
Only article and additional services
Whole issue and additional services
All issues and additional services for 2022
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 xij0,j=1nxij=ai,i=1mxij=bj,    iM={1,...,m},    jN={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 Доказательство. Пусть дана последовательность xnx0 и 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)limxinfI(xn)limxinfmax(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;    xijMijyij. (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. В частности, когда ai1,    bi1    (m=n), имеем задачу о назначениях на узкие места (Форд, Фалкерсон, 1966).
34

3. МЕТОД ВЕТВЕЙ И ГРАНИЦ

35 Для точного решения дискретно-непрерывной задачи (1)–(3) разобьем допустимое многогранное множество на непустые грани и возьмем их относительные внутренности (Сухарев, Тимохов, Федоров, 1986). Каждая такая грань получается фиксированием подмножеством BM×N пар индексов (i,j) , на которых соответствующие переменные удовлетворяют условиям:
36 xij>0,    (i,j)B , xij=0,    (i,j)B. (7)
37 Положим
38 IB=infxX-Bmax(i,j)Bτij(xij). (8)
39 Здесь XBX — подмножество допустимых решений X ограничений (1), удовлетворяющих дополнительным ограничениям (7). Поскольку относительные внутренности непустых граней непусты (XBϕ) (Сухарев, Тимохов, Федоров, 1986, с. 65), то замыкание X-B подмножества XBX получается заменой строгих неравенств (7) нестрогими (Федоров, 1979, с. 30):
40 xij0,    (i,j)B, xij=0,    (i,j)B, (9)
41 задача (1), (7), (8) равносильна задаче
42 IB=minxX-BIB(x)=minxX-Bmax(i,j)Bτij(xij). (10)
43 Задача (1), (9), (10) является задачей выпуклого программирования, поэтому исходная задача (1)–(3) сводится к решению задач выпуклого программирования на непустых гранях. Справедлива следующая лемма.
44 Лемма 3. Минимальное значение I общего показателя в задаче (1)–(3) получается как наименьшее значение IB задачи (10) по всем BM×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/V23min (14)
61 при ограничениях
62 a1-(b2-x22)-(b3-x23)0,    a2-x22-x230,    b2-x220,    b3-x230,    x22,  x230,
63 или a2x22+x23b2+b3-a1,    b2x220,    b3x230, или с учетом значения параметров
64 4x22+x232,    4x220;    3x230. (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 4x22+x23,    x221;    2,4x231,2.
70 Перебирая возможные варианты уравнивания соответствующих частных показателей, убеждаемся, что единственное решение соответствует системе
71 8-53x23=3+x22103x23=6x23=1,8;2+53x23=3+x223+x22=5x22=2.
72 При этом общее значение уравненных частных показателей равно 3+x223+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=0max(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+x22x22+5x23/3=5 , когда общее значение 3+x22 минимально, т.е. при x22=0x23=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-x23x22=5-5x23/3=75/21=1,429;3+x22=8-x22-x232x22+x23=5x23=15/72,143.
88 При этом общее значение уравненных частных показателей равно 8-x22-x234,429, не вошедший в тройку уравненных показателей (18) — 4-x22/23,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=2max(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-x23x23=18/10=1,8;2+5x23/3=8-x22-x238-x22-x23=5x22=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=3max(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/3x22+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=3max(4,  7/2,  4,  7)=7>5.
105 Нижняя оценка получается в результате решения задачи
106 max3(x22+x23)/2-2,    4-x22/2,    3+x22,    2+5x23/3min. (21)
107 Здесь минимум берется по всей допустимой области значений переменных. Минимум достигается на прямой 3+x22=2+5x23/3x22=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/33,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-x23x22=5-5x23/3=75/21=1,429;3+x22=8-x22-x232x22+x23=5x23=15/72,143.
116 При этом общее значение уравненных частных показателей равно 8-x22-x234,429,
117 а не вошедшие в тройку уравненных показателей (22)
118 3(x22+x23)/2-23,358<4,429,4-x22/23,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<26=8-5x23/3,    x23=6/5max=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<38-x23=2+5x23/3,    x23=18/8inf=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-x236=10x23/3x23=18/10=1,8;2+5x23/3=8-x22-x23x22+8x23/3=6x22=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<1inf=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=4x22=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>0max(4,    8-5x23/2,    3+x22=7-x23,    2+5x23/2)inf,0<x23<32+5x23/2=7-x23x23=15/8inf=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+6C(δγ)+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,125C(δγ)+C(δγ)=5+6 .
160