On the ways of estimation of plans’ number for transport problem
Table of contents
Share
Metrics
On the ways of estimation of plans’ number for transport problem
Annotation
PII
S042473880012408-7-1
DOI
10.31857/S042473880012408-7
Publication type
Article
Status
Published
Authors
I. Pogodin 
Affiliation: Naval Polytechnic Institute
Address: Russian Federation, St. Petersburg
Pages
116-120
Abstract

Due to the significant expansion of the range of problems forming the class of so-called "transport tasks", including access to non-linear ones, it is advisable to have estimates of the number of all permissible plans, among which the optimal ones are chosen.Estimates are made of a number of possible plans for solving closed transportation problems for matrices of various dimensions and structures. About fifty examples of different transport tasks were analyzed as a basis for the study. It was found that by redistributing among themselves, for example, only the capacities of manufacturers and the constancy of their total sum, the number of possible plans for the problem monotonously decreases with an increase of their relative standard deviation value. From the analysis of particular empirical dependencies for matrices of various structures, analytical generalizations are obtained for the simplest situations. Received that for tasks: (a) with dimensions (2×M) and (N×2) directly analytical calculation of the number of plans is possible; (b) with matrices of arbitrary sizes and structures, a computer algorithm of (M) nested cycles is required; (c) with equal powers and equal capacities, a probabilistic way of estimation is possible, the results of which correlate with the exact ones at the level of about 0.8. The task may be of interest in evaluating the effectiveness of various optimization methods.

Keywords
transport problem plans, deliver, customer, delivery, capacity, limitations of transportation
Received
01.12.2020
Date of publication
16.12.2020
Number of purchasers
6
Views
106
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
100 RUB / 1.0 SU
Whole issue
792 RUB / 15.0 SU
All issues for 2020
2534 RUB / 50.0 SU
1 ВВЕДЕНИЕ
2 Транспортная задача , задача о назначениях и другие распределительные задачи обычно являются частными задачами линейного программирования , у истоков создания которого еще в 1930-е годы стоял академик Л.В. Канторович (Канторович, 1939), который, в частности, начал делать метрологические оценки количества вычислений, необходимых для решения транспортных задач классическими методами. Однако даже для таких относительно простых задач характерно большое число переменных решения . Для транспортных задач , имеющих практическое значение, применение общих методов может стать неэффективным. Кроме того, ряд современных модификаций транспортных задач (например, (Ассаул, 2019)) вообще выводят их из класса задач линейного программирования. Платой за универсальность методов и задач часто является снижение их эффективности, заключающееся в медленной сходимости, высоком объеме вычислений и т.п. (Худокормов, 1994).
3 Рассматриваемая задача оценки числа всех возможных планов замкнутой транспортной задачи может представлять интерес для оценки и сравнения степени эффективности различных, порой весьма трудоемких и приближенных, методов оптимизации при решении широкого класса транспортных и сводимых к ним задач с различными критериями оптимальности (Ассаул, 2019), например по сравнению со способом прямого перебора всех планов без какой-либо подготовки. Здесь становится уместным знать и сравнить трудоемкость прямого перебора всех планов, т.е. их число, подобно тому, как в статистических задачах обычно проводится сравнение с исключительно случайными условиями или с нормальным законом распределения. Кроме того, на практике встречаются чрезвычайные ситуации поиска исчезнувших из поля зрения в нескольких районах (одушевленных или неодушевленных) существ или предметов по местам их возможной концентрации также в различных районах, и когда требуется оценить число подлежащих рассмотрению (опросу) связей.
4 МЕТОДЫ ИССЛЕДОВАНИЯ И РАСЧЕТА
5 Если рассматривать только базисные планы транспортной задачи, то в качестве грубой верхней (существенно завышенной) оценки их числа можно принять, например, число сочетаний из (N×M) по (N+M–1) CMNM+N-1 (здесь N – число производителей, M – число заказчиков), которое зависит только от размеров задачи.
6 Как показало практическое рассмотрение более 50 замкнутых транспортных задач с размерами от ((N = 2)(M = 2)) до ((N = 3)(M = 4)) (табл. 1), полное число (Y) всех их возможных планов варьируется на 2 порядка (от 2 до 186), существенно зависит как от размеров таблицы N×M, так и от значений мощностей и емкостей. Однако попытка построить по массиву рассмотренных 54 матриц общую регрессионную зависимость вида YNαMβSγDδ, где S = N×A = M×B — полный поток (сумма значений мощностей или емкостей), D — сумма дисперсий мощностей и емкостей, оказалась несостоятельной (например, оценки α и β различаются вдвое и т.п.).
7 Таблица 1. Примеры фактического числа допустимых планов (Y) для задач с матрицами размером N×M и произвольным распределением мощностей ( Ai) и емкостей ( Bj )
8
{Ai}/{Bj} Y {Ai}/{Bj} Y {Ai}/{Bj} Y {Ai}/{Bj} Y {Ai}/{Bj} Y {Ai}/{Bj} Y
N×M=2×2 N×M=2×2 N×M=2×2 N×M=2×2 N×M=2×2 N×M=2×2
8,2/8,2 3 6,4/6,4 5 7,3/7,3 4 9,1/9,1 2 9,1/8,2 2 9,1/7,3 2
9,1/6,4 2 8,2/7,3 3 8,2/6,4 4 5,5/5,5 6 9,1/5,5 2 8,2/5,5 3
7,3/5,5 4 6,4/5,5 5 6,4/8,2 3 3,3/1,5 2 3,3/2,4 3 3,3/3,3 4
6,6/1,11 2 6,6/2,10 3 6,6/3,9 4 6,6/4,8 5 6,6/5,7 6 6,6/6,6 7
N×M=2×3 N×M=2×3 N×M=2×3 N×M=2×3 N×M=2×3 N×M=2×3
3,3/1,2,3 5 3,3/1,1,4 3 3,3/2,2,2 8 1,5/2,2,2 3 2,4/2,2,2 6 6,6/1,1,10 4
6,6/1,2,9 6 6,6/1,3,8 8 6,6/1,4,7 10 6,6/1,5,6 12 6,6/2,3,7 12 6,6/2,4,6 15
6,6/2,5,5 15 6,6/2,8,2 9 6,6/4,4,4 21 4,8/4,4,4 15 3,9/4,4,4 10 2,10/4,4,4 6
N×M=2×3 N×M=2×3 N×M=2×3 N×M=2×3 N×M=2×3 N×M=2×3
1,11/4,4,4 3 1,7/1,3,4 3 2,6/1,3,4 5 3,5/1,3,4 7 4,4/1,3,4 8 2,3/1,2,2 5
3,3/2,2,2 13 N×M=3×3 N×M=3×3 N×M=3×3 N×M=3×3 N×M=3×4
2×4 1,2,3/4,1,1 8 6,3,3/3,4,5 80 2,3,4/1,2,6 18 3,5,7/1,6,8 39 3,4,7/1,2,5,6 186
10,18/5,6,8,9 262
9 Однако для каждого подкласса матриц одинакового размера и полного потока искомое число планов Y обнаруживает уверенную статистическую тенденцию к уменьшению по мере увеличения различий (неравномерности, выражаемой, например, суммой их дисперсий D) среди групп значений мощностей и емкостей (рис. 1).
10 Рис. 1. Зависимость числа планов от суммы дисперсий мощностей и емкостей (для задач: а) 2×2 при S = 10 (r = –0,86); б) 2×3 при S = 12 (r = –0,74))
11 Это обстоятельство позволяет предположить, что в случае получения необходимых оценок числа планов для равномерных задач с одинаковыми значениями в группах мощностей (A) и емкостей (B) переход к конкретной задаче уже без этого условия можно получить по соответствующим регрессионным номограммам (см. рис. 1), предварительно скорректировав (интерполяцией) задачу от равномерной к реальным размерам матрицы соответствующего вида, либо использовать эту величину просто в качестве верхней оценки количества планов конкретной задачи. Во всех этих расчетах удобнее производителей и заказчиков располагать в порядке возрастания их мощностей и емкостей.
12 Для задач хотя бы с одним малым размером матриц число планов рассчитывается точно и достаточно просто.
13 1. При (2×2): Y = U = min(A1B1) + [1]; прибавлять единицу в квадратных скобках следует только если поставка Х11 может принимать значение «0», а это, в свою очередь, возможно, если А1 = D12 и В1 = D21.
14 2. При (3×3) (N = M = 3) число планов U определяется всевозможными сочетаниями значений четырех поставок (i, j, k, l) в левом верхнем углу таблицы:
15 max(0, A1D13, B1D31) ≤ i D11,max(0, A1i, A1D13) ≤ j D12,
16 max(0, B1i, B1D31) ≤ k D21,max(0, B2jD32, A2kD23) ≤ l D22
17 и может быть найдено сразу (т.е. без применения более сложной процедуры) в виде
18 Y=U=ijk(D22-max(0,B2-j-D32,A2-k-D23)).
19 3. При (N×2) (или (2×M)) в равномерных задачах также может быть получена точная оценка U = Y (пример для M = 4), которая будет получена как частный случай
20 Y=i=0Dj=max(0,(A-2D-i))min(D,(A-i))k=max(0,(A-D-j-i))min(D,(A-j-i))1.
21 4. Для матриц с произвольными размерами N×M и без условия равномерности распределений мощностей {Ai} и емкостей {Bj} можно обобщить п.п. (2) и (3) и точно рассчитать число планов. Однако для этого потребуется создать достаточно громоздкий (индивидуальный для каждой структуры N×M) алгоритм в виде вложенных однотипных N1×M1 циклов с накоплением единиц в первоначально обнуленном сумматоре S=S+1 в самом внутреннем цикле. При этом для индекса Ii, j, связанного с перевозкой в ячейке с адресом (i, j), следует организовать цикл по этому индексу, начиная с max(0,(Ai-s=j+1MDi,s-s=1j-1Ii,s),(Bj-s=i+1NDs,j-s=1i-1Is,j)) ) до min(Di,j,(Ai-s=1jIi,s),(Bj-s=1iIs,j))) , где Di,jmin(Ai,Bj) . Построенный таким образом алгоритм пригоден для различных значений мощностей {Ai} и емкостей {Bj}замкнутой транспортной задачи.
22 5. Для матриц с совершенно произвольными размерами N×M и равномерными распределениями мощностей {A} и емкостей {B} начнем с распределения заявок одного из участников какой-нибудь группы (например, поставщика) по соответствующим участникам из другой группы (заказчикам), что эквивалентно известной задаче о числе способов совершенно свободного (без ограничений) размещения S шаров по M ящикам (Генкин, 1994; Сергеев, 2011), в которой условно вводится (M–1) разделителей между M ящиками, расположенными в линию. После этого находят номера (M–1) позиций разделителей среди (S+M–1) мест, вариантом которых будет CS+M-1M-1 (число сочетаний из (S+M –1) по (M –1)).
23 Заметим, что если в каком-то одном произвольном из M ящиков оказалось U>DminA,B шаров, то для размещения остальных (SU) шаров вариантов будет CA-U+M-2M-2 , поскольку U шаров уже не требуется размещать и разделителей между остальными ящиками (кроме выбранного) потребуется (M –2). Такой недопустимо переполненной ячейкой может оказаться любая из M в рассматриваемой строке поставщика, а значит, можно предположить, что из величины CS+M-1M-1 следует вычесть M таких величин (CA-U+M-2M-2) . Однако, к примеру, переполнение может появиться более чем в одной ячейке строки, а следовательно, среди вычитаемых могут появиться повторяющиеся планы и вычитать предстоит несколько иное (большее) число планов. То же искажение дублированием некоторых планов может влиять на величину CS+M-1M-1 : Z=CA+M-1M-1-Mq=D+1ACA-q+M-2M-2 . Поскольку посчитать это измененное из-за дублирований уменьшенное число вычитаемых планов представляется затруднительным, это обстоятельство является недостатком предлагаемой вычислительной модели. Оценку для одной такой линейки можно получить простым перебором с ограничениями, как это сделано выше в (п. 3).
24 Наличие другой такой линейки (поставщика), если она не последняя (см. выше п.3), требует повторения этой процедуры, проделанной для первой рассмотренной линейки.
25 Далее рассмотрим создание планов для всей таблицы из построенных строчных планов. На примере одного столбца видно, что из n возможных планов по столбцам условию равенства суммы по столбцам величине B будут удовлетворять только m планов, т.е. можно говорить о вероятности p=m/n того, что построенные планы по столбцам проходят через фильтр условия заказчика. Снова используем модель распределения q шаров (q = 0, ..., ND) по N ящикам, а также (ND – j) шаров (j = (D+1), ..., ND) по N1 ящикам и получим
26 n=q=0NDCq+N-1N-1, m=q=DNDCq+N-1N-1-Nj=D+1NDC(ND)-j+N-2N-2.
27 Поскольку такие вероятности отбора планов по столбцам с суммой, равной B, считаем независимыми во всех M столбцах, то для оценки числа K планов всей задачи получаем K=Z(m/n)M.
28 Таблица 2. Примеры фактического числа допустимых планов (Y) и рассчитанного вероятностным способом (K) для задач с матрицами размером N×M и равномерным распределением мощностей ( Ai=A) и емкостей ( Bj=B )
29
Обозначения и параметры транспортной задачи N=2 N=2 N=2 N=2 N=2 N=2 N=2 N=3 N=3 N=3 N=3
M=2 M=2 M=3 M=4 M=2 M=3 M=4 M=3 M=3 M=3 M=4
S=4 S=6 S=6 S=8 S=8 S=12 S=16 S=6 S=9 S=12 S=12
A=2 A=2 A=3 A=4 A=4 A=6 A=8 A=2 A=3 A=4 A=4
B=2 B=3 B=2 B=2 B=4 B=4 B=4 B=2 B=3 B=4 B=3
D=2 D=2 D=2 D=2 D=4 D=4 D=4 D=2 D=3 D=4 D=3
Реальное число допустимых планов Y 3 7 7 19 5 19 85 8 18 80 415
Полное число расчетных (фиктивных) планов K 4, 8 16, 9 7, 4/ 9, 6 9, 8/ 23, 4 16, 9 64, 6/ 365 3302/ 306 57, 4 298 1253 2490/ 5938
30 РЕЗУЛЬТАТЫ
31 Такие модельные расчеты были проведены для 16 примеров равномерных задач (см. табл. 2) и, по-видимому, по указанной выше причине (присутствие неисключенных дублирующих планов) обнаружены, как правило, завышение оценок K над точным числом планов Y, а также несовпадение оценок для задач с транспонированными матрицами. Тем не менее можно построить регрессионную зависимость вида Yapr=1,88K0,62 , прогнозы Yapr числа планов по которой ожидаются коррелирующими с точным числом планов на уровне r = 0, 84 (рис. 2).
32 Рис. 2. Связь точного числа планов Y с оценкой, прогнозируемой по формуле Yapr=1,98K0,58 в логарифмическом (слева) и линейном (справа) масштабах
33 Анализ оценок числа возможных планов решения замкнутых транспортных задач для матриц различной размерности и структуры обнаружил, что при перераспределении между собой только мощностей производителей и постоянстве их суммы число возможных планов задачи монотонно уменьшается с увеличением их относительного среднеквадратического отклонения. Для матриц различной структуры получены аналитические обобщения в простейших ситуациях, а также более универсальный компьютерный алгоритм. Предложен вероятностный путь оценки числа планов равномерных задач. Сформирована обучающая база для дальнейших исследований.

References

1. Assaul V.N., Pogodin I.E. (2019). About the transport task with environmental criteria. Economics and Mathematical Methods, 55, 1, 87–93 (in Russian).

2. Genkin S.A., Itenberg I.V., Fomin D.V. (1994). Leningrad mathematical circles. Kirov: ASA (in Russian).

3. Kantorovich L.V. (1939). Mathematical methods of organizing and planning production. Lenin-grad: Publishing House of Leningrad State University, 67 (in Russian).

4. Sergeev A.N., Petrosyan G.A., Tulyakova E.V. (2011). Theory of probability and mathematical statistics. Saint Petersburg: AF (in Russian).

5. Khudokormov A.G. (1994). The history of economic studies. Part II. Textbook. Ed. by A.G. Khu-dokormov. Moscow: Publishing House of Moscow State University (in Russian).