Minimization Method for Solution of Transport and Economic Problem
Table of contents
Share
Metrics
Minimization Method for Solution of Transport and Economic Problem
Annotation
PII
S042473880006777-3-1
DOI
10.31857/S042473880006777-3
Publication type
Article
Status
Published
Authors
Yury Churin 
Occupation: Associate professor at the Higher Mathematics Department
Affiliation: Kostroma State Agricultural Academy (KSAA)
Address: Kostroma, Russian Federation
Pages
117-123
Abstract

The method of minimization of function which represents the sum of modules of the binomial being the differences of an independent variable and a set of these numbers is considered. Such function determines the sum of the distances measured by length of an arch of some set line from the points belonging to this line to some point (on the same line). Need of minimization of this function can arise for solution of the following question. On the thoroughfare (the railroad, the highway, the river, etc.) there are operating manufacturing enterprises, and it is necessary to deliver their products for further processing to the enterprise which is planned to be located on this highway. It is required to define location of this enterprise proceeding from a condition of the smallest transportation costs.

Keywords
number module, function minimization, function derivative
Received
21.10.2019
Date of publication
16.12.2019
Number of purchasers
23
Views
329
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
720 RUB / 15.0 SU
All issues for 2019
2534 RUB / 30.0 SU
1 Постановка задачи. На транспортной магистрали (железная дорога, шоссе, река и т.п.) расположены производственные предприятия, продукцию которых необходимо доставлять для дальнейшей переработки на предприятие, располагающееся на этой же магистрали. Требуется определить местоположение этого предприятия, исходя из условия наименьших транспортных расходов.
2 Подобная задача может возникнуть при определении расположения на данной магистрали электростанции, снабжающей энергией предприятия, находящиеся на этой же магистрали (при условии передачи энергии по линии, совпадающей с этой магистралью).
3 При подготовке материала статьи был обследован большой объем литературных источников, но ни в учебной литературе, ни в справочной и специальной подобная методика исследования функций такого вида отсутствует.
4 В общем виде формулировка такой задачи состоит в следующем. В n-мерном эвклидовом пространстве задана несамопересекающаяся сплошная линия L, имеющая начальную точку M0 , направление отсчета и масштаб (обобщение понятия «числовая ось»), и множество n точек МiL (i =1,,n). Положение каждой точки определяется координатой хi, которая равна длине дуги L=M0Mi^ , x1<<xn . Расстояние между двумя смежными точками MiMi+1^=xi+1-xi . Каждой точке xi xi сопоставлено число ai>0 ai>0 , которое применительно к приведенной выше формулировке условия задачи определяет или стоимость транспортировки объема производимой за данный период предприятием i продукции, или стоимость его энергоснабжения, отнесенной к единице пути доставки, на перерабатывающее (энергоснабжающее) предприятие. Тогда если обозначить через х координату на линии L этого предприятия, число aix-xi будет стоимостью транспортировки продукции предприятия i в точку х. Требуется найти на линии L точку xL, в которой функция Fx=i=1naix-xi принимает свое наименьшее значение.
5 Естественно, что такая задача при небольшом n может быть решена путем непосредственного подсчета значений функции Fx в заданных точках. Если же число точек достаточно велико, такой подсчет требует много времени и целесообразно использовать предлагаемую ниже методику.
6 Сначала был рассмотрен более простой случай, когда все числа ai равны единице, т. е. исследована функция fx=i=1nx-xi , минимум которой точка, сумма расстояний от которой до данных точек имеет наименьшее значение. Очевидно, что для упрощения решения такой задачи и с целью наглядности линия L может быть представлена прямой (развернута в прямую), что, естественно, не может повлиять на ход исследования и выводы. Тогда функция fx в области x1;xn кусочно-линейна, непрерывна и не дифференцируема в точках xi . Исследование других свойств для произвольного числа n точек оказалось объемным, и его нецелесообразно помещать в статью.
7 Далее необходимо определить и сравнить угловые коэффициенты ki;i+1 функции fx на частичных интервалах xi;xi+1,    i=1,,n (при n>3 ):
8 k1,2=f(х2)-f(х1)/х2-х1,  ...,kn-1,n=f(хn)-f(хn-1)/хn-хn-1,
9 где fxj=i=1nxj-xi,    j=1,  ...,  n. Анализ значений угловых коэффициентов показал следующее.
10 При любом нечетном n имеем k1,2=kn-1,n ; при этом k1,2<0,kn-1,n>0 ; k3,2=kn-2,n-1 ; k3,2<0, kn-2,n-1>0;... . Очевидно, что на некоторой части интервала 1;    n функция fx убывает, а на другой возрастает. Нарушение условия монотонности происходит в точке x¯ i, i=0,5(n + 1). Эта точка делит ряд i=1nxi на две части с одинаковым числом членов в каждой части (т.е. является медианой этого ряда) и является точкой минимума функции fx .
11 При четном n на интервале xn/2;xn/2+1 функция fx постоянна и в любой его точке принимает наименьшее значение.
12 Результаты исследования представлены на рис. 1, где показаны 2 интервала xi;xi+1i<0,5n+1 и xn-i-1;xn-i  i>0,5n+1 и элементы графика fx , одной из особенностей которых является равенство углов αi и αn-i (i =1,…, n–1).
13 Приведем конкретные примеры, иллюстрирующие результаты исследования.
14 Рис. 1. Элементы графика функции y = f(x)
15 Рис. 2. График функции f(x) к примеру 1Рис. 3. График функции f(x) к примеру 2
16 Пример 1 (рис. 2).
17
I 1 2 3 4 5
xi 0 1 2 5 6
f(xi) 14 11 10 13 16
x1=0;x2=1;x3=2;x4=5;x5=6;n=5; fx=x+x-1+x-2+x-5+x-6.
18 Точка минимума x-=2;    f(2)=10 .
19 Пример 2 (рис. 3).
20
I 1 2 3 4
xi 0 1 3 8
f(xi) 12 10 10 20
x1=0;x2=1;x3=3;x4=8;n=4; fx=x+x-1+x-3+x-8
21 Точки минимума принадлежит отрезку 1;    3;    fmin=10.
22 Когда анализируется функция Fx=i=1naix-xi , решение в общем виде представляет большие сложности и целесообразно применить следующие соображения. Сначала следует найти точку минимума функции F¯x=i=1naix-xi2, которая имеет единственную точку минимума, расположенную достаточно близко к точке мнимума функции F(x).
23 Затем, приравнивая к нулю производную F¯x , получаем ее критическую точку: x¯=i=1naixi/i=1nai, которая определяет единственную точку минимума функции F¯x , так как F-x=2i=1nai>0 . В общем случае точка x- может не совпадать с минимумом функции F(x), но может служить ее первым приближением.
24 Дальнейшие соображения основаны на изложенном выше решении задачи для функции fx=i=1nx-xi. Для определения искомой точки следует найти значение функции F(x) в двух соседних точках слева и справа от x- : xi<x-<xi+1 .
25 Если Fxi=Fxi+1 , очевидно, что x- является точкой, принадлежащей интервалу минимизации Fx:xi;xi+1 . Если Fxi<Fi+1 , следует найти Fxi-1 . Если Fxi-1<Fxi , надо вычислить Fxi-2 и т.д. пока значения Fx не начнут возрастать, т.е. будет выполняться условие Fxk-1>Fxk<Fxk+1 . Тогда xk — точка минимума (при нечетном n). Если на очередном шаге Fxk-1=Fxk , то xk-1;xk будет интервалом минимизации Fx (при четном n). Если это условие не будет иметь места, точкой минимума Fx будет xk . При Fxi>Fxi+1 следует поступать аналогично, но двигаться вправо от точки xi .
26 Для наглядности приведем примеры и графики функции Fx .
27 Пример 3 (рис. 4).
28
i 1 2 3 4 5
ai 5 1 1 1 1
xi 0 1 2 5 6
Fx=5x-0+1x-1+1x-2+1x-5+1x-6 , x-=5×0+1×1+1×2+1×5+1×6/5+1+1+1+1=1.
29 F(1)=15; F(2)=18; F(0)=14. Искомая точка x=0.
30 Пример 4 (рис. 5).
31
i 1 2 3 4 5
ai 1 1 1 1 5
xi 0 1 2 5 6
Fx=x+x-1+x-2+x-5+5x-6, x-=1×0+1×1+1×2+1×5+5×6/1+1+1+1+5=4,
32 F(2)=26; F(5)=17; F(6)=16. Искомая точка: x=6.
33

Рис. 4. График F(x) к примеру 3 [[[image6]]]Рис. 5. График F(x) к примеру 4

34 Пример 5 (рис. 6).
35
i 1 2 3 4 5
ai 1 1 1 5 1
xi 0 1 2 5 6
Fx=x+x-1+x-2+5x-5+x-6 , x¯=1×0+1×1+1×2+5×5+1×6/1+1+1+5+1=3.
36 F(2)=22; F(5)=13; F(6)=20. Искомая точка: x=5.
37 Пример 6 (рис. 7).
38
i 1 2 3 4
ai 3 1 1 3
xi 0 1 2 8
Fx=3x+x-1+x-2+3x-8, x-=3,375
39 F(2)=25; F(8)=37; F(1)=25; F(0)=27. Следовательно, F(x) имеет интервал минимизации 1;    2.
40

Рис. 6. График F(x) к примеру 5 [[[image8]]] Рис. 7. График F(x) к примеру 6

41 Пример 7 (рис. 8).
42
i 1 2 3 4
ai 1 5 1 1
xi 0 1 2 5
F(x) 12 6 10 28
Fx=x+5x-1+x-2+x-5, x-=1,5.
43 F(1)=6; F(2)=10; F(0)=12. Следовательно, F(x) имеет наименьшее значение при x=1.
44

Рис. 8. График F(x) к примеру 7

45 Как видно из примера 7, при четном n функция F(x) (в отличие от функции f(x)) может иметь только одну точку, где она принимает наименьшее значение (пример 6). Остальные свойства ее такие же, как у функции f(x).
46 Дополнительно проведенные расчеты показали, что поиск точки минимума функции F(x), исходя из найденного значения точки минимума функции F¯x , требует, как правило, не более 3–4 шагов, что в случае большего числа точек хi существенно сокращает объем вычислений при определении значений функции F(x) в каждой точке.
47 Таким образом, в результате исследования получен простой метод, не требующий большого объема вычислений, при решении важных хозяйственных задач на транспорте с наименьшими материальными затратами.