close

Вход

Забыли?

вход по аккаунту

...конфликтными зонами (мотивами) для должности;pdf

код для вставкиСкачать
Научный журнал «Известия КГТУ», №35, 2014 г.
УДК 519.85+330.45
РЕШЕНИЕ ЗАДАЧИ МИНИМИЗАЦИИ ЭКСПЛУАТАЦИОННЫХ РАСХОДОВ
НА МОРСКОМ ТРАНСПОРТЕ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
С.М. Алексеева, Ф.А. Куксов, О.Ю. Алексеева
SOLVING THE PROBLEM OF MINIMIZATION OF WORKING COSTS
ON SEA TRANSPORT IN CONDITIONS OF INDEFINITENESS
S.M. Alekseeva, F.A. Kuksov, O.Yu. Alekseeva
Исследуется некорректная расстановочная параметрическая задача минимизации эксплуатационных расходов в логистическом процессе контейнерных
перевозок на морском транспорте при неточной информации относительно суточных эксплуатационных расходов для n судов по m линиям. Существующий математический аппарат, используемый логистическими компаниями, не всегда соответствует поставленным практическим задачам, не учитывает специфические математические понятия и нюансы, невнимание к которым может привести к большим потерям. Поэтому существует необходимость создания методик, алгоритмов,
которые при использовании современного математического аппарата и компьютерной техники позволят оптимизировать деятельность компаний, в том числе,
сократить расходы по перевозке. В результате исследования построена модель
некорректной транспортно-логистической задачи управления транспортным процессом, разработаны алгоритм и методика минимизации эксплуатационных расходов с привлечением систем «Matlab» и «Mathcad» [1, 2]. На базе разработанного
алгоритма создана программа минимизации эксплуатационных расходов с использованием языка программирования С#. Написанная программа апробирована
на модельной задаче для Балтийского контейнерного терминала с тремя выбранными контейнерными судами, совершающими курсирование по двум линиям: Калининград–Роттердам и Калининград–Гамбург, на которых судовые суточные
эксплуатационные расходы могут колебаться в определенных пределах. Построенная методика минимизации эксплуатационных судовых расходов в условиях
неопределенности с использованием средств программирования выгодно отличается простотой и доступностью. Так как графический интерфейс программы разрабатывался на языке С#, он делает адаптирование этой программы для пользователя максимально корректным. Поэтому данная методика позволяет оптимизировать деятельность компаний, в том числе, сократить расходы по перевозке и повлиять на привлекательность этих компаний.
оптимальное планирование, некорректная задача, оптимальное управление, моделирование, минимизация эксплуатационных расходов, параметрическое
программирование
The incorrect collocational parameter problem of minimization of working costs
in a logistic process of container carriage on sea transport while inadequate information
concerning daily operating costs for n vessels on m lines. The existing mathematic al
apparatus used by logistic companies doesn’t always fit assigned practical tasks, doesn’t
229
Научный журнал «Известия КГТУ», №35, 2014 г.
take into consideration specific mathematical notions and nuances, inattention to which
may lead to great losses. Therefore, there’s a necessity of creating methods and algorithms which while using modern mathematical apparatus and computing technics allow
to optimize companies activities, including cutting down transportation expenses. As
the result of research the model of the incorrect transportation logistic task of managing
the transportation process was built, the algorithm and the method of minimization of
working costs with the usage of “Mathlab” and “Mathcad” systems were developed [1].
On the basis of the developed algorithm the program of minimization of working costs
with the usage of the programming language C# was created. This program is approved
on the model task for the Baltic container terminal with three chosen container vessels
making plying along two routes Kaliningrad-Rotterdam and Kaliningrad – Hamburg on
which vessel daily operating costs may fluctuate in defined limits. The developed method of minimization of working costs in the conditions of indefiniteness with the usage
of the programming aid profitably differs in simplicity and accessibility. As the program
graphic interface was developed on the language C#, that makes this program adaptation maximally correct for a user. Therefore, this method allows to optimize companies
activities, including minimization of transportation costs, and to influence on these
companies attractiveness.
optimum planning, an incorrect problem, optimal control, modeling, minimization of working costs parametric programming
Рассмотрим расстановочную задачу минимизации эксплуатационных расходов для n судов по m линиям при неточной информации относительно суточных эксплуатационных расходов. Заметим, что они зависят от типа и мощности
судна, цен на топливо, географии перехода и в общем случае реально не являются точно определенными.
Для данного эксплуатационного периода T известны объемы перевозок,
производительность судов и интервальные эксплуатационные расходы судов на
этих линиях (табл. 1).
Таблица 1. Объемы перевозок, производительность судов и интервальные
эксплуатационные расходы n судов на m линиях
Table 1. Volumes of transportations, productivity of vessels and interval working costs
of n vessels on m lines
Суда
1
2
…
n
Объем
перевозок
Производительность судов,
млн. т-миль / сут
1-я
2-я
m…
линия
линия
линия
p1m
p11
p12
…
p2m
p21
p22
…
…
…
…
…
pnm
pn 1
pn 2
…
v1
v2
…
Эксплуатационные расходы,
тыс. усл. ед. / сут
1-я
2-я
m…
линия
линия
линия
a11 b11
a12 b12
a1m b1m
…
a21 b21
a22 b22
a2 m b2 m
…
…
…
…
…
an2 bn2 …
an1 bn1
anm bnm
vm
Рассмотрим матрицы производительности судов, эксплуатационных расходов, объема перевозок:
229
Научный журнал «Известия КГТУ», №35, 2014 г.
P
p11
p21
p12
p22
...
pn 2
pn 1
... p1m
... p2 m
Ý
... pnm
v
вид:
,
v1
a11 b11
a21 b21
an 1 bn 1
v2
a12 b12
a22 b22
...
an 2 bn 2
... a1m b1m
... a2 m b2 m
,
... anm bnm
... vm .
Матрица колебания суточных расходов с параметром t, 0 t 1 имеет
Ý(t )
a11 (b11 a11 )t
a21 (b21 a21 )t
an 1 (bn 1
a12 (b12 a12 )t ... a1m (b1m a1m )t
a22 (b22 a22 )t ... a2 m (b2 m a2 m )t
.
...
an 1 )t an 2 (bn 2 an 2 )t ... anm (bnm anm )t
Обозначим x ij - время работы i-го судна на j-й линии, элементы матрицы
эксплуатационных расходов Э(t): eij (t ) aij (bij aij )t , 0 t 1.
Имеем задачу линейного программирования
f (t , xij ) e11 (t )x11 ... e1m (t )x1m ... en1 (t )xn1 ... enm (t )xnm
(1)
- целевая функция, которую нужно минимизировать,
ограничения – неравенства:
x11
x12 ... x1m
T;
x21
x22 ... x2 m
T;
xn1 xn2 ... xnm
T;
(2)
…
ограничения – равенства:
p11 x11
p21 x21 ... pn1 xn1
v1 ;
p12 x12
p22 x22 ... pn2 xn2
v2 ;
(3)
…
p1m x1m
p2 m x2 m ... pnm xnm
vm ;
(i = 1…n, j = 1…m).
(4)
Ограничения - неравенства (2) выражают требование выполнить перевозки
в заданный эксплуатационный период, а ограничения - равенства (3) – выполнить
заданный объем перевозок на каждой линии. Задача содержит n m переменных,
коэффициенты целевой функции линейно зависят от параметра t, ограничений неравенств и ограничений - равенств в задаче соответственно n и m [3, 4].
Рассматриваемая задача минимизации эксплуатационных судовых расходов в условиях неопределенности (1) – (4) является некорректной, так как не удовлетворяет третьему условию корректности – требованию устойчивости решения
[5]. Действительно, изменяя параметр t с шагом, например, 0.1, и каждый раз
решая оптимизационную задачу, можем для некоторых промежутков t наблюдать устойчивость оптимального плана и непрерывное изменение значения целевой функции относительно параметра, а вблизи некоторых так называемых критических значений t - существенное изменение оптимального плана при малых
изменениях параметра, т.е. его неустойчивость.
xij
0
229
Научный журнал «Известия КГТУ», №35, 2014 г.
Рассмотрим, например, модельную задачу минимизации эксплуатационных расходов для выбранных трех контейнерных судов по двум линиям Калининград–Роттердам и Калининград–Гамбург при условии, что судовые суточные эксплуатационные расходы на этих линиях могут колебаться в определенных пределах (табл. 2).
Таблица 2. Объемы перевозок, производительность судов и интервальные эксплуатационные расходы судов
Table 2. Volumes of transportations, productivity of vessels and interval working costs
of vessels
Суда
Производительность
судов, млн. т-миль / сут
Эксплуатационные
расходы, тыс. долл. / сут
1-я линия
Гамбург
2-я линия
Роттердам
1-я линия
2-я линия
Эксплуатационный
период,
сут
“Delta
Hamburg”
“Barbara”
1
1.5
12 - 18
24
300
0.5
1
9 - 12
12 - 18
300
“Matfen”
1.2
1
15
12 - 15
300
Объем перевозок,
млн. тонно-миль
360
60 тыс.
TEU
480
80 тыс.
TEU
Введя параметр t, 0 t 1, получаем следующую расстановочную параметрическую задачу:
Z (12 6t )x11 24x12 (9 3t )x21 (12 6t )x22 15x31 (12 3t )x32 min ; (5)
x11
x12
300;
x21
x31
x22
x32
300;
300;
x11 0, 5x21 1, 2 x31 360;
1, 5x12 x22 x32 480;
xij 0 (i= 1,2,3; j=1,2).
(6)
(7)
(8)
Применяя возможности математической системы «Mathcad» [6], решим
оптимизационную задачу при t=0. Ищем минимум целевой функции, используя
встроенную функцию minimize в составе блока решения, открываемого словом
Given. Имеем оптимальный план (300; 0; 0; 230; 50; 250). Изменяя параметр t с
шагом 0.1 и решая оптимизационную задачу для всех следующих t, для t=0.1
имеем такой же оптимальный план (300; 0; 0; 230; 50; 250), а для t=0.2 оптимальный план существенно изменился: (216; 0; 0; 300; 120; 180). Следовательно, вблизи значения t = 0.2 небольшое изменение параметра привело к существенному
изменению оптимального плана, и далее наблюдаем неустойчивость оптимального плана. Данное значение t может быть найдено с помощью блока Given-Find
229
Научный журнал «Известия КГТУ», №35, 2014 г.
как абсцисса точки пересечения соответствующих прямых, выражающих зависимость значений целевой функции от параметра (рисунок):
1.45 10
1.405 10
1.36 10
f ( t 300 0 0 230 50 250 )
f ( t 216 0 0 300 120 180 )
1.315 10
1.27 10
f ( t 0 120 0 300 300 0)
1.225 10
f ( t 0 300 0 30 300 0)
1.18 10
1.135 10
1.09 10
1.045 10
1 10
4
4
4
4
4
4
4
4
4
4
4
0
0.1
0.2
0.3
0.4
0.5
t
0.6
0.7
0.8
0.9
1
Рис. Нахождение критических значений параметра t
Fig. Finding the critical values of t parameter
Получили критическое значение t=0.143, в окрестности которого оптимальный план неустойчив. Меняя далее параметр t с шагом 0.1, наблюдаем, что
вблизи значений t = 0.5 и t = 0.7 небольшие изменения параметра привели к существенным изменениям оптимального плана. Соответствующие планы: (0; 120;
0; 300; 300; 0) и (0; 300; 0; 30; 300; 0). Данные значения t находим как абсциссы
точек пересечения соответствующих прямых, выражающих зависимость значений
целевой функции от параметра. Получаем значения t=0.451 и t=0.667. Следовательно, исследование задачи привело к разделению промежутка 0 t 1 на четыре
промежутка [0; 0.143], [0.143; 0.451], [0.451; 0.667], [0.667; 1], в которых имеем
различные оптимальные планы, представляющие собой время постановки каждого судна на каждую линию, и для каждого промежутка оптимальные интервальные эксплуатационные расходы. Например, при 0 t 0.143 контейнерное судно
«Delta Hamburg» ставится на линию Калининград-Гамбург на 300 сут, контейнерное судно «Barbara» - на линию Калининград - Роттердам на 230 сут, контейнерное судно «Matfen» - на линию Калининград-Гамбург на 50 сут, контейнерное
судно «Matfen» - на линию Калининград - Роттердам на 250 сут, в резерве остается контейнеровоз «Barbara» на 70 сут. При этом оптимальные эксплуатационные
расходы в целом составят от 10 млн. 110 тыс. долл. до 10 млн. 670 тыс. долл.
Аналогично для трех других промежутков можно сделать соответствующие выводы о времени постановки каждого судна на каждую линию и об оптимальных
интервальных эксплуатационных расходах.
Таким образом, при планировании в условиях неточной информации следует провести анализ устойчивости решения оптимизационной задачи (1) - (4),
229
Научный журнал «Известия КГТУ», №35, 2014 г.
цель которого состоит в определении области значений параметра, в пределах которого решение остается оптимальным.
Для решения этой задачи написана и апробирована программа минимизации эксплуатационных расходов для n судов по m линиям ( n 10, m 10 ) с использованием языка программирования С# [7, 8], создан графический интерфейс
программы. Программа создана на базе разработанной методики минимизации
эксплуатационных расходов с привлечением систем «Matlab» и «Mathcad» и
апробации этой методики [1, 2]. Графический интерфейс программы нативен
стандартным и, следовательно, понятен для пользователя. Для пользователя
имеются окна ввода данных производительности судов, эксплуатационных расходов для этих судов, изменяющиеся в известных пределах объема перевозок. На
выходе – таблица, в которой обозначены изменение параметра, значение целевой
функции, оптимальные планы. Разработанная программа минимизации эксплуатационных расходов содержит подпрограмму симплекс-метода, также являющуюся авторской. Мы не использовали метод искусственного базиса, который применяется, например, в онлайн-решениях задач симплекс-методом. Опорное же
решение находится избавлением от 0-строк:
- инициализируется массив-таблица S размером (n m 1) (m n 1) , а
также два линейных массива-шапки X и Y длиной n m и n m соответственно;
- с помощью циклического преобразования и использования локальных
переменных массивы P (данные о судах и их производительности), EA (данные о
минимальных эксплуатационных расходах) и EB (данные о максимальных эксплуатационных расходах) размещаются следующим образом: в верхний левый
угол помещается массив P, далее в правую строку – по очереди массив VT, в
верхний промежуток между P и VT попеременно вставляются значения из EA и из
значения формулы (EA t EB) . Нижняя строка-это Z-строка;
- далее происходит алгоритм удаления 0-строк: пока минимальное значение Y-шапки будет равно 0 (шапка состоит из чисел, переменной x1 соответствует
число 1, 0-строке - число 0, вследствие чего при существовании этого нуля программа будет пытаться от него избавиться). Выбирается максимально число из 0строки, назовём его pickedY. При делении выбранного элемента из строки pickedY
на число из VT (которое уже находится в S) получаем минимальное число. Выбранная строка (индекс) будет назваться pickedX. Далее происходит вызов метода,
который преобразует таблицу с помощью симплекс преобразования (9). Меняем
значения (по выбранному элементу) из X и Y, меняется число из Y с индексом
pickedY и число из X с индексом pickedX. Если ключевая строка pickedX совпадает
с выбранным номером 0-строки, то тогда длина таблицы уменьшается на 1 и мы
избавляемся от одной из 0-строк;
- приходим к базисному решению путём преобразования столбцов с отрицательным разрешающим элементом;
- получаем оптимальное решение путём преобразования строк с отрицательным разрешающим элементом;
- далее имеем готовую таблицу. Получаем из неё план (10). Переходим к
следующему t.
double[,] newS=new double[dlina,visota];
for(int i=0;i<dlina;i++){
for(int j=0;j<visota;j++){
(9)
229
Научный журнал «Известия КГТУ», №35, 2014 г.
int tipCell=0;
if(j==pickedY){tipCell+=1;}
if(i==pickedX){tipCell+=2;}
switch(tipCell){
case0:{newS[i,j]=S[i,j]S[(int)pickedX,j]*S[i,pickedY]/S[(int)pickedX,pickedY];break;}
case 1:{newS[i,j]=S[i,j]/S[(int)pickedX,pickedY];break;}
case 2:{newS[i,j]=-S[i,j]/S[(int)pickedX,pickedY];break;}
default:{newS[(int)pickedX,pickedY]=1/S[(int)pickedX,pickedY];break;}
}
}
}
return newS;
(10)
double[] Xr=new double[n*m+1];
for(int i=0;i<Y.Length-1;i++){
int tt=Y[i];
if(!(tt>n*m)){
Xr[tt-1]=S[dlina-1,i];
}
}
Xr[Xr.Length-1]=S[dlina-1,visota-1].
Для рассмотренной модельной задачи (5) - (8) имеем следующие результаты (табл. 3).
Таблица 3. Изменение параметра, значение целевой функции, оптимальные планы
Table 3. The parameter change, the value of target function, optimum plans
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
10503
10879
11243
11606
11880
12060
12186
12204
12222
12240
12245
300
0
0
230
50
250
300
0
0
230
50
250
216
0
0
300
120
180
216
0
0
300
120
180
216
0
0
300
120
180
0
120
0
300
300
0
0
120
0
300
300
0
0
300
0
30
300
0
0
300
0
30
300
0
0
300
0
30
300
0
0
300
0
30
300
0
Здесь первая строка показывает изменение параметра, вторая - значения
целевой функции, в строках с третьей по восьмую по столбцам - соответствующие
данным значениям параметра оптимальные планы.
К решению задач типа (1) - (5) можно применить, например, известный метод потенциалов [9, 10]. Решение начинают с поиска оптимального плана для
начального значения параметра t, т.е. при t = 0. Далее, записывая в клетки матрицы слагаемые, содержащие параметр t в коэффициентах целевой функции, рассчитывают соответствующие потенциалы, которые будут линейными функциями
параметра t. Записывая неравенства, выражающие условие потенциальности свободных клеток, получают те неравенства, из которых определяется промежуток
для параметра t, в нем достигнутый оптимальный план остается оптимальным.
При этом, если найденный промежуток не покрывает заданного, то, по-видимому,
следует производить новую итерацию метода потенциалов, вводя в план одну из
тех свободных клеток, в которых нарушается потенциальность при соответству-
229
Научный журнал «Известия КГТУ», №35, 2014 г.
ющем увеличении параметра t. Очевидно, исследование такой задачи представляет собой нелегкий и кропотливый процесс. Нам представляется, что построенная
нами методика минимизации эксплуатационных судовых расходов в условиях неопределенности с использованием средств программирования выгодно отличается
простотой и доступностью.
СПИСОК ИСПОЛЬЗОВАННЫХ ЛИТЕРАТУРНЫХ ИСТОЧНИКОВ
1. Alekseeva, O.Yu, Alekseeva, S.M. The procedure of minimization of working costs in logistical process of container transportations on sea transport in the conditions of incomplete definiteness of the initial information //In the World of Scientific
Discoveries. No. 2.1(50), 2014. - C. 583 - 601.
2. Алексеева, О.Ю. Моделирование управления в морских и инженерных
задачах с использованием пакетов прикладных программ / О.Ю. Алексеева,
С.М. Алексеева // Современные методы теории краевых задач: материалы Воронежской весенней математической школы "Понтрягинские чтения - XXIII", секция «Смежные проблемы прикладной и инженерной математики». – Воронеж:
Издательско-полиграфический центр Воронежского государственного университета, 2012. - С. 5-6
3. Васильев, Ф.П. Линейное программирование / Ф.П. Васильев,
А.Ю. Иваницкий. - Москва: Изд-во «Факториал», 1998. - 176 с.
4. William, H. Model Building in Mathematical Programming. Wiley, New
York, 1990. - 432 p.
5. Тихонов, А.Н. Методы решения некорректных задач / А.Н. Тихонов,
В.Я. Арсенин. - Москва: Наука, 1986. - 288 с.
6. Дьяконов, В.П. Компьютерная математика. Теория и практика /
В.П. Дьяконов. - Москва: Нолидж, 2001. - 1295 с.
7. Пахомов, Б.И. C# для начинающих / Б.И. Пахомов. –
Санкт-Петербург[Saint-Petersburg], «БХВ-Петербург», 2014.
8. Ben, Watson. С# 4.0 How-To, Indiana 46240 USA, Pearson Education, 2010.
9. Шварцман, А.П. Математические методы управления и планирования на
морском транспорте / А.П. Шварцман, Э.П. Громовой. - Москва: Изд-во «Транспорт», 1970. - 383 с.
10. Таха, Хемди А. Введение в исследование операций / Таха Хемди А. –
7-е изд.: пер. с англ. – Москва: Издательский дом "Вильямс", 2005. - 912 с.
REFERENCES
1. Alekseeva O.Yu, Alekseeva S.M. The procedure of minimization of working
costs in logistical process of container transportations on sea transport in the conditions
of incomplete definiteness of the initial information. In the World of Scientific Discoveries. No, 2.1(50), 2014. pp. 583-601.
2. Alekseeva O.Yu., Alekseeva S.M. Sovremennye metody teorii kraevykh
zadach [Modern methods of the theory of boundary problems]. Materialy Voronezhskoy
vesenney matematicheskoy shkoly "Pontryaginskie chteniya-23", sektsiya “Smezhnye
problemy prikladnoy i inzhenernoy matematiki” [Materials of Voronezh spring mathematical school “Pontryagin lections-23”, the section “Related problems of Applied and
229
Научный журнал «Известия КГТУ», №35, 2014 г.
Engineering Mathematics”]. Izdatel'sko-poligraficheskiy tsentr Voronezhskogo gosudarstvennogo universiteta [the Printing and Publishing centre of Voronezh State University]. Voronezh, 2012, pp. 5-6
3. Vasil'ev F. P., Ivanitskiy A. Yu. Lineynoe programmirovanie [Linear programming]. Moscow, izdatel'stvo “Faktorial”, [”Factorial” Publishing]. 1998, 176 p.
4. William H. Model Building in Mathematical Programming. Wiley, New
York, 1990, 432 p.
5. Tikhonov A.N., Arsenin V.Ya. Metody resheniya nekorrektnykh zadach
[Meth-ods of solving incorrect problems]. Moscow, “Nauka” [“Science”]. 1986, 288 p.
6. D'yakonov V.P. Komp'yuternaya matematika. Teoriya i praktika [Computing
Mathematics. The theory and practice]. Moscow, Nolidzh. 2001, 1295 p.
7. Pakhomov B.I. C# dlya nachinayushchikh [C# for beginners]. SaintPetersburg, «BKhV-Peterburg», 2014.
8. Ben Watson. S# 4.0 How-To, Indiana 46240 USA, Pearson Education, 2010.
9. Shvartsman A.P., Gromovoy E.P. Matematicheskie metody upravleniya i planirovaniya na morskom transporte [Mathematical methods of management and planning on sea transport]. Moscow, izd. “Transport” [“Transport” Publ.]. 1970, 383 p.
10. Takha Khemdi A. Vvedenie v issledovanie operatsiy, 7-e izdanie. Per. s
angl. [Introduction into operations investigation, 7th edition. Translated from English].
Moscow, izdatel'skiy dom "Vil'yams" [Publishing House “William”]. 2005, 912 p.
ИНФОРМАЦИЯ ОБ АВТОРАХ
Алексеева Светлана Михайловна – Калининградский государственный технический университет, кандидат физико-математических наук, доцент кафедры
высшей математики; e-mail: [email protected]
Alekseeva Svetlana Mikhailovna – Kaliningrad State Technical University,
Ph.D in Physics and Mathematical Sciences, Associate Professor of the Department
of Higher Mathematics; e-mail: [email protected]
Куксов Филипп Александрович – Балтийская государственная академия рыбопромыслового флота, студент радиотехнического факультета;
e-mail: [email protected]
Kuksov Filipp Aleksandrovich – Baltic Fishing Fleet State Academy, student
of the radio-technical faculty; e-mail: [email protected]
Алексеева Ольга Юрьевна – компания «Realore Studios», QA-инженер;
e-mail: [email protected]
Alekseeva Ol’ga Yur’evna – Company «Realore Studios», QA-engineer;
e-mail: [email protected]
229
1/--страниц
Пожаловаться на содержимое документа