Russian Federation
Russian Federation
Russian Federation
Optimization of technological processes of generation and distribution of electricity between consumers in order to reduce its losses in transmission networks from transformer substations to the facilities of the electrical complex of water transport is an important, science-intensive problem that requires the most rational power supply schemes, compensation of reactive power, selection and maintenance of economical operating modes using digital at the stages of design and engineering work and commissioning. To find optimal solutions, MATLAB tools offer methods based on linear and quadratic programming functions. The specificity of structuring transport problems in terms of linear and quadratic programming is that in the process of calculations it is necessary to take into account digital arrays of linear constraints in the form of equations and inequalities represented in the binary number system. This makes it possible to propose an algorithm for performing computational operations on three given vectors: loss functions, constraints - of inequalities, and constraints - of equalities. While maintaining the structure of the model, the algorithm provides monitoring of material flows with variations in the numerical values of the elements of the objective function, as well as in cases of quantitative changes (for example, the cost of a unit of electricity during the day) in compliance with the syntax of the linprog function. The quadprog function allows you to take into account changes in the cost of transportation when a nonlinear relationship occurs between state variables by selecting the structure of a positively defined symmetric matrix of the quadratic component of the quality criterion. Programs in MATLAB codes for practical use are proposed and examples are given confirming the correctness of the developed algorithmization schemes.
algorithm, operational research, linear programming, quadratic programming, transport problem, MATLAB
Введение
Транспортные задачи встречаются на любом виде транспорта и представляют собой математические модели транспортирования товарных единиц различного назначения в транспортной сети [1]. Под товарными единицами подразумеваются любые виды продукции, которые необходимо транспортировать по сети при минимизации критерия оценки качества совершения транспортной работы [2]. Критериями качества могут быть затраты энергии на выполнение транспортной работы, максимизация прибыли, максимизация производительности технологического процесса, рациональное использование электроэнергии на производстве и др. [3, 4].
Для решения транспортных задач в вычислительной среде MATLAB используют метод линейного программирования, реализуемый с помощью специальной функции linprog следующего вида:
|
[x, J] = linprog (f, A, B, Aeq, Beq, lb, ub), |
(1) |
где слева от знака равенства содержится вектор x, при котором обеспечивается минимум, являющийся вектором переменных состояния, скалярное число J - численное значение минимума критерия качества, возвращенное linprog. В правой части функции - вектор-строка f, элементы которой содержат затраты на транспортирование одной единицы товарной продукции от источников к потребителям [5]. Затем, согласно (1), следуют попарно матрицы и векторы, служащие для введения линейных ограничений, причем последовательность ввода должна сохраняться (по умолчанию) идентичной структуре (1). Далее следуют ограничения на элементы вектора состояния lb и ub (нижняя и верхняя границы). Заметим, что в правой части функции linprog вектор x формально отсутствует. Вместе с тем его размерность при поиске минимума (либо максимума) критерия качества определяется по размерности f, а также по векторам lb и ub. Число элементов векторов f и x равно k.
Таким образом, задача заключается в определении xij, количества товарных единиц, которые необходимо транспортировать от источника при условии, что запасы будут доставлены потребителю в требуемых объемах, а спрос удовлетворен при минимальных общих затратах.
В приложении методов линейного программирования транспортная задача, вероятно, была одной из первых значимых задач, изученных в этой области. В общем, задача может быть выражена с помощью формулировки линейной модели и решена с использованием симплекс-алгоритма [6]. Однако благодаря особой структуре линейной модели ее можно решить более эффективным способом, используя стандартную форму задачи квадратичного программирования [7], которую рассмотрим ниже.
Метод квадратичного программирования реализуется в среде MATLAB с помощью специальной функции quadprog следующего вида:
x = quadprog (H, f, A, B, Aeq, Beq, lb, ub),
в которую, в отличие от функции linprog, добавлен новый аргумент, представляющий матрицу H. К матрице Н предъявляются следующие требования: она должна быть симметрической и положительно определенной, что проверяется по ее собственным значениям, которые должны быть больше нуля. Для симметрической матрицы характерно свойство: H = HT.
В результате параметры H, f, A, B, Aeq, Beq, lb и ub вводятcя в квадратичную функцию в виде обязательных либо опциональных компонент, в том числе пустых матриц []. Крайне важно, чтобы порядок переменных был одинаков для соответствующих параметров, согласно синтаксису quadprog [8].
Методы и материалы исследования
Раздел методов и материалов представлен в формате примеров, содержащих одну и ту же модель с девятью переменными состояния, но различными исходными данными. Во всех случаях использованы идентичные структуры матриц А и Aeq, состоящие из нулей и единиц, согласно алгоритму,
и приводящие к корректным решениям транспортной задачи. Фактически установлен «шаблон» для моделей транспортных задач, подлежащих решению в кодах MATLAB [6].
В математической постановке модель транспортной задачи, согласно алгоритму линейного программирования, может быть выражена как нахождение набора xij, где i = 1, ..., m, j = 1, ..., n, для удовлетворения требований к поставкам и спросу при минимальных затратах на распределение [9, 10]. Соответствующая линейная модель выглядит так:
|
z = f ∙ x; |
(2) |
|
A ∙ x ≤ B; |
(3) |
|
Aeq ∙ x = Beq; |
(4) |
|
lb ≤ x ≤ ub. |
(5) |
Модель (2) с ограничениями (3)–(5) можно представить в терминах транспортной задачи [5] как совокупность целевой функции:
ограничений
и условия
xij ≥ 0.
Первые m ограничений соответствуют лимитам поставок, при которых запасы товарных единиц, доступных в каждом источнике отправления,
не должны превышаться. Следующие n ограничений обеспечивают удовлетворение требований к товарным единицам в пунктах назначения (спросу потребителей). Элементы вектора переменных состояния не должны быть отрицательными, поскольку продукция доставляется только от m источников n потребителям [11, 12].
Транспортная задача касается перевозки любого продукта из источников (пунктов отправления) в пункты назначения при соблюдении требований к материальным потокам, определенных синтаксисом linprog. Специфика транспортных задач состоит в том, что в функции (1) матрицы A и Aeq могут быть представлены в двоичной системе счисления (состоять из чисел 0 и 1), что позволяет составить простые коды для их оценки и предложить программные средства для получения оптимальных решений. В этом случае достаточно задания только трех векторов: f, B и Beq.
Рассмотрим пример решения транспортной задачи на основе линейного программирования с реализацией в среде MATLAB (файл sah353zb.m).
Задаем исходные данные:
f = [8 11 1 4 5 2 7 3 10 4 3 5];
B = [120 97 69]';
Beq = [54 32 25 15]'.
Составляем матрицы коэффициентов ограничений по поставкам A и по потребностям Aeq соответственно:
A = [1 1 1 1 0 0 0 0 0 0 0 0;
0 0 0 0 1 1 1 1 0 0 0 0;
0 0 0 0 0 0 0 0 1 1 1 1];
Aeq = [1 0 0 0 1 0 0 0 1 0 0 0;
0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0;
0 0 0 1 0 0 0 1 0 0 0 1].
Построим составную матрицу W = [A; Aeq] для определения ранга транспортной задачи с помощью функции ranc:
W = [A; Aeq];
Ff = rank (W).
Сформируем векторы нижней lb и верхней ub границ переменных xij
lb = [0 0 0 0 0 0 0 0 0 0 0 0]';
ub = [].
Решение получим с использованием функции линейного программирования linprog:
[X, J] = linprog (f, A, B, Aeq, Beq, lb, ub).
Из приведенного файла следует, что модель транспортной задачи содержит число источников, число пунктов назначения, запасы, потребности и затраты на транспортировку одной единицы продукции. Важно отметить, что вычисления выполнены по трем заданным векторам (см. файл) и в итоге получен вектор состояния, при котором обеспечен минимум критерия качества:
X = [0 0 25 4 54 32 0 11 0 0 0 0].
Минимум критерия качества составил
J = f ∙ X = 408.
Пример 1. Модель сбалансированной транспортной задачи (при равенстве суммарных запасов и потребностей) с тремя источниками и тремя потребителями:
f = [4 4 2 5 3 1 3 6 4];
A = [1 1 1 0 0 0 0 0 0;
0 0 0 1 1 1 0 0 0;
0 0 0 0 0 0 1 1 1];
B = [30; 20; 40];
Aeq = [1 0 0 1 0 0 1 0 0;
0 1 0 0 1 0 0 1 0;
0 0 1 0 0 1 0 0 1];
Beq = [45 35 10]';
lb = zeros (9, 1);
ul = [];
[X, fval] = linprog (f, A, B, Aeq, Beq, lb, []).
% Наиболее эффективное решение:
Xх = [5 25 0 0 10 10 40 0 0];
J = 280.
Пример 2. Модель несбалансированной транспортной задачи (суммарные запасы превышают потребности) с тремя источниками и тремя потребителями:
f = [1 2 4 4 2 6 6 1 3];
B = [80 70 50]'.
% Структура модели:
A = [1 1 1 0 0 0 0 0 0;
0 0 0 1 1 1 0 0 0;
0 0 0 0 0 0 1 1 1];
Aeq = [1 0 0 1 0 0 1 0 0;
0 1 0 0 1 0 0 1 0;
0 0 1 0 0 1 0 0 1];
Beq = [50 80 50]';
lb = zeros (9, 1);
ub = [];
[X, fval] = linprog (f, A, B, Aeq, Beq, lb, []).
% Наиболее эффективное решение:
X = [50 30 0 0 50 0 0 0 50];
J = 360.
Покажем адаптацию классической транспортной задачи о перевозках к задаче оптимального распределения мощностей судовых или наземных подстанций (дизель-генераторных агрегатов) соответствующим потребителям электроэнергии. С этой целью создадим модель структуры с тремя источниками и четырьмя потребителями. Решение транспортной задачи начинается с рассмотрения производственной матрицы (таблица), в которой представлены все ресурсы, подлежащие перевозкам. В таблице содержатся мощности трех подстанций, которые следует распределить между потребителями при минимальных потерях, определяемых критерием качества. Видно, что при рассмотрении задачи экономии электроэнергии в терминах транспортной задачи слово «перевозки» трансформировалось в термин «распределение». В каждой ячейке производственной матрицы приведены элементы вектора состояния xij и удельная стоимость потерь электроэнергии aij при передаче, а также суммарные показатели по строкам и столбцам соответствующими ограничениями.
Производственная матрица
Production matrix
|
Источники электроэнергии (3 подстанции) |
Потребители электроэнергии |
Мощность подстанций, кВт |
||||
|
П1 |
П2 |
П3 |
П4 |
|||
|
Удельная стоимость потерь электроэнергии |
||||||
|
St1 |
a11 = 0,3 x11 |
a12 = 0,9 x12 |
a13 = 0,2 x13 |
a14 = 0,3 x14 |
630 |
|
|
St2 |
a21 = 0,4 x21 |
a22 = 0,5 x22 |
a23 = 1,0 x23 |
a24 = 0,1 x24 |
1 000 |
|
|
St3 |
a31 = 0,6 x31 |
a32 = 0,8 x32 |
a33 = 0,6 x13 |
a34 = 0,4 x14 |
400 |
|
|
Мощность, необходимая |
Sp1 = 800 |
Sp2 = 200 |
Sp3 = 600 |
Sp4 = 300 |
Суммарная мощность = 2 030 кВт |
|
|
|
Итого: Sp = SSpi = 1 900 кВт |
|
|
|||
|
Функция потерь: f = [0,3 0,9 0,2 0,3; 0,4 0,5 1,0 0,1; 0,6 0,8 0,6 0,4] |
|
|||||
Специфика транспортной задачи линейного программирования в приложении к распределению мощности между источниками и потребителями состоит в том, что запасы источников по мощности не должны быть меньше потребной энергии на период планирования. Поэтому режимы в открытой задаче с недопоставкой мощности потребителям должны быть исключены.
Вычисления выполним, используя файл sah353zb.m:
[X, J] = linprog (f, A, B, Aeq, Beq, lb, ub),
где, согласно алгоритму,
A = [1 1 1 1 0 0 0 0 0 0 0 0;
0 0 0 0 1 1 1 1 0 0 0 0;
0 0 0 0 0 0 0 0 1 1 1 1];
B = [630 1000 400]';
Aeq = [1 0 0 0 1 0 1 0 1 0 0 0 ;
0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0;
0 0 0 1 0 0 0 1 0 0 0 1];
Beq = [800 200 600 300]'.
Получено оптимальное решение:
X = [30 0 600 0 500 200 0 300 270 0 0 0];
J = 621.
W = [1 1 1 1 0 0 0 0 0 0 0 0;
0 0 0 0 1 1 1 1 0 0 0 0;
0 0 0 0 0 0 0 0 1 1 1 1;
1 0 0 0 1 0 1 0 1 0 0 0;
0 1 0 0 0 1 0 0 0 1 0 0
0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1].
Ранг: W = [A; Aeq] равен 6.
Далее рассмотрим модель транспортной задачи, решаемой с использованием квадратичного программирования, реализуемого с помощью функции quadprog. В математической постановке модель транспортной задачи в форме стандартной задачи квадратичного программирования может быть выражена как нахождение набора xij, где i = 1, ..., m, j = 1, ..., n для удовлетворения требований к поставкам и спросу при минимальных затратах на распределение [13, 14]. Соответствующая экономико-математическая модель выглядит так:
при условии
Ax ≤ B;
Aeqx = Beq;
lb ≤ x ≤ ub.
Использован следующий синтаксис функции:
x = quadprog (H, f, A, B, Aeq, Beq, lb, ub).
При этом целевая функция f является выпуклой только тогда, когда матрица H положительно полуопределена [15]. Следует обратить внимание на то, что условие Ax ≤ B применяется поэлементно к левой и правой частям неравенства. Причем вектор x не передается в решатель, поскольку он является внутренней переменной, по которой проводится оптимизация, т. е. решатель не несет явной информации о самом векторе x. Все задается явно, через переданные параметры.
Приведем пример задачи квадратичного программирования и рассмотрим программные средства MATLAB для ее решения со следующими исходными данными:
H = diag (v),
где вектор
v = 0,01ones (12, 1),
f = [8 11 1 4 5 2 7 3 10 4 3 5].
В функции
[x, J] = quadprog (H, f, A, B, Aeq, Beq, lb, [])
матрицы А и Aeq составим по предлагаемому алгоритму так, чтобы они состояли из нулей и единиц
с правыми границами:
B = [120 97 69]' и Beq = [54 32 25 15]',
что соответствует структуре, состоящей из трех источников и четырех потребителей. Зададим нижнюю границу вектора переменных состояния:
b = zeros (12, 1).
Получим оптимальное решение:
x = [0 0 25 4 54 32 0 11 0 0 0 0];
J = 431,5100.
Согласно quadprog, критерий качества состоит из двух составляющих: линейной и нелинейной. Линейную компоненту определим по формуле
f · x = 408,0000.
Нелинейная составляющая:
1/2 · x' · H · x = 23,5100.
Таким образом, за счет нелинейной составляющей решения удалось более эффективным способом учесть дополнительные затраты на поставку, используя стандартную форму задачи квадратичного программирования.
Результаты исследования
Получим решение ранее рассмотренной задачи по экономичному распределению электроэнергии от трех подстанций к четырем потребителям согласно данным производственной матрицы (см. таблицу) с помощью квадратичного программирования и сравним его с решением той же задачи, полученным с применением линейного программирования.
Для представления структуры квадратичной модели рассмотрим ее отдельные значимые программные фрагменты.
Сначала определяемся с выбором структуры положительно определенной симметрической матрицы квадратичной компоненты критерия качества:
v = 0,001ones (12, 1);
H = diag (v).
Построим вектор целевой функции
f = [0,3 0,9 0,2 0,3 0,4 0,5 1,0 0,1 0,6 0,8 0,6 0,4].
Составим матрицы А и Aeq по предлагаемому алгоритму так, чтобы они состояли из нулей и единиц со значениями B и Beq их правых границ:
A = [1 1 1 1 0 0 0 0 0 0 0 0;
0 0 0 0 1 1 1 1 0 0 0 0;
0 0 0 0 0 0 0 0 1 1 1 1];
B = [630 1 000 400]';
Aeq = [1 0 0 0 1 0 0 0 1 0 0 0;
0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0;
0 0 0 1 0 0 0 1 0 0 0 1];
Beq = [800 200 600 300]'.
Зададим нижнюю границу вектора переменных состояния:
lb = zeros (12, 1).
Применяем функцию квадратичного программирования, аргументы которой составлены выше и построим составную матрицу W для определения ранга транспортной задачи с помощью функции rank:
[X, J] = quadprog (H, f, A, B, Aeq, Beq, lb, []);
W = [A; Aeq];
r = rank (W).
Оптимальное решение имеет вид:
X = [30 0 600 0 500 200 0 300 270 0 0 0];
J = 661,6900.
Линейная компонента критерия равна f · X = =621,000 единиц; расчетная часть квадратичной составляющей:
1/2 · X' · H · X = 40,6900.
Отметим, что на выходе функция quadprog выдает оптимальный план X задачи, а также экстремальное значение целевой функции fval. В случае несимметричной матрицы H среда MATLAB заменяет ее на (H + Hᵀ) / 2, что не приводит к изменениям значения целевой функции.
Обсуждение
Применение инструментов MATLAB для решения транспортных задач с использованием предложенных машинных программ, содержащих матрицы ограничений, определенных синтаксисом функций линейного и квадратичного программирования, позволило получить структуры файлов, возвращающих искомый результат по трем исходным данным: векторам f, B, Beq. В файлах предусмотрен мониторинг материальных потоков в автоматическом режиме. В результате при превышении спроса над предложениями операции приостанавливаются.
Разработанные файлы можно использовать для получения оптимальных решений при быстро протекающих технологических процессах с вариациями элементов вектора f в допустимых пределах, что необходимо для мониторинга кранового оборудования портов при обработке судов [7].
Эти и другие вопросы по совершенствованию технологических операций могут подлежать широкому обсуждению.
Заключение
В условиях цифровой трансформации значительно изменились способы и технические приемы применения цифры для решения практических задач [3]. Созданы вычислительные среды для цифровой обработки больших объемов информации на кардинально новом уровне, что способствует дальнейшему развитию методов и средств автоматизации технологических и производственных процессов на транспорте [5].
Представленная работа посвящена алгоритмизации и программной интерпретации транспортной задачи математического программирования с применением инструментов linprog и quadprog вычислительной среды MATLAB. Предложен алгоритм для вычисления матриц линейных ограничений, состоящих из нулей и единиц, что позволяет использовать в качестве аргументов этих инструментов всего три вектора f, B и Beq, представляющие исходные данные для решения транспортной задачи. Разработаны программы в кодах MATLAB и представлены решения задач, подтверждающие корректность вычислительных операций.
1. Baryshnikov S. O., Dmitrienko D. V., Saharov V. V., Chertkov A. A. Modeli i algoritmy upravleniya ob"ektami vodnogo transporta v usloviyah cifrovoj transformacii: monografiya [Models and algorithms for managing water transport facilities in the context of digital transformation: monograph]. Saint Petersburg, Zanevskaya ploshchad' Publ., 2022. 520 p.
2. Goglachev A. I., Klassifikaciya potokovogo vremennogo ryada na osnove nejrosetevyh tekhnologij i povedencheskih shablonov [Classification of a streaming time series based on neural network technologies and behavioral patterns]. Vestnik Yuzhno-Ural'skogo gosudarstvennogo universiteta. Seriya: Vychislitel'naya matematika i informatika, 2024, vol. 13, no. 3, pp. 79-94.
3. Danilova S. V., Valinurova A. A., Balabanova N. V. Primenenie zadachi linejnogo programmirovaniya dlya resheniya chastnyh zadach bankovskoj deyatel'nosti [Application of the linear programming problem to solve particular banking problems]. Sovremennye naukoemkie tekhnologii. Regional'noe prilozhenie, 2022, no. 1 (69), pp. 46-53.
4. Sokolinskaya I. M. Chislennaya realizaciya metoda poverhnostnogo dvizheniya dlya resheniya zadach linejnogo programmirovaniya [Numerical implementation of the surface motion method for solving linear programming problems]. Vestnik Yuzhno-Ural'skogo gosudarstvennogo universiteta. Seriya: Vychislitel'naya matematika i informatika, 2024, vol. 13, no. 3, pp. 5-31.
5. Chertkov A. A., Kask Ya. N., Saburov S. V. Avtomatizaciya poiska marshrutov rentabel'nyh gruzoperevozok sredstvami celochislennogo programmirovaniya MATLAB [Automation of the search for cost-effective cargo transportation routes using MATLAB integer programming]. Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S. O. Makarova, 2021, vol. 13, no. 4, pp. 496-504.
6. Kol'cov M. A. Reshenie zadachi Sil'vestra v MATLAB. Izbrannye lekcii po ekstremal'nym zadacham [Solving the Sylvester problem in MATLAB. Selected lectures on extreme tasks]. Pod redakciej V. N. Malozemova. Saint Petersburg, Izd-vo VVM, 2017. Part 1. Pp. 195-199.
7. Duzhinski R. R., Toropcev E. L. Zadacha kvadratichnogo programmirovaniya v dinamicheskom mezhotraslevom balanse [The problem of quadratic programming in a dynamic intersectoral balance]. Vestnik Severo-Kavkazskogo federal'nogo universiteta, 2017, no. 2, pp. 54-60.
8. Zhornyak A. G., Morozova T. A. Specializirovannyj distributiv python (x,y) yazyka programmirovaniya python dlya nauchnyh i inzhenernyh vychislenij [A specialized python (x,y) distribution of the python programming language for scientific and engineering computing]. Nauchno-tekhnicheskij vestnik Povolzh'ya, 2022, no. 7, pp. 39-42.
9. Sokolinskij L. B., Ol'hovskij N. A., Sviridenko A. B. Pryamye mul'tiplikativnye metody dlya razrezhennyh matric. Kvadratichnoe programmirovanie [Direct multiplicative methods for sparse matrices. Quadratic programming]. Komp'yuternye issledovaniya i modelirovanie, 2018, vol. 10, no. 4, pp. 407-420.
10. Zhurbenko N. G., Izmailov A. F., Uskov E. I. Gibridnaya globalizaciya skhodimosti metoda posledovatel'nogo kvadratichnogo programmirovaniya, stabilizirovannogo vdol' podprostranstva [Hybrid convergence globalization of a sequential quadratic programming method standardized along a subspace]. Vestnik Tambovskogo universiteta imeni G. R. Derzhavina. Seriya: Estestvennye i tekhnicheskie nauki, 2019, vol. 24, no. 126, pp. 150-165.
11. Crisci S., Ruggiero V., Zanni L. Steplength selection in gradient projection methods for box-constrained quadratic programs. Applied Mathematics and Computation, 2019, vol. 356, pp. 312-327.
12. Serafino D., Ruggiero V., Toraldo G., Zanni L. On the steplength selection in gradient methods for unconstrained optimization. Applied Mathematics and Computation, 2018, vol. 318, pp. 176-195.
13. Stefanova M., Minevich O., Baklanov S., Petukhova M., Lupuleac S., Grigor'ev B., Kokkolaras M. Convex optimization techniques in compliant assembly simulation. Optimization and Engineering, 2020, vol. 21, pp. 1665-1690.
14. Stojkovic N., Stanimirovic P. Initial point in primaldual interior point method. Facta Universitatis. Series Mechanics, Automatic Control and Robotics, 2021, vol. 3, no. 11, pp. 219-222.
15. Wang H., Zhang S. Computer aided tolerancing of composite elevator assembly involving clamping forces coor-dination. Procedia CIRP, 2018, vol. 75, pp. 256-260.
