Россия
Россия
Россия
Оптимизация технологических процессов генерации и распределения электроэнергии между потребителями с целью снижения ее потерь в сетях передачи от трансформаторных подстанций на объекты электротехнического комплекса водного транспорта является важной, наукоемкой проблемой, требующей наиболее рациональных схем электроснабжения, компенсации реактивной мощности, выбора и поддержания экономичных эксплуатационных режимов с применением цифры на этапах выполнения проектно-конструкторских работ и ввода в эксплуатацию. Для поиска оптимальных решений в инструментах MATLAB предложены способы, базирующиеся на функциях линейного и квадратичного программирования. Специфика структурирования транспортных задач в терминах линейного и квадратичного программирования состоит в том, что в процессе вычислений необходимо учитывать цифровые массивы линейных ограничений в форме равенств и неравенств, представленных в двоичной системе счисления. Это позволяет предложить алгоритм для выполнения вычислительных операций по трем заданным векторам: функции потерь, ограничениям-неравенствам и ограничениям-равенствам. При сохранении структуры модели алгоритм обеспечивает мониторинг материальных потоков при вариации численных значений элементов целевой функции, а также в случаях количественных изменений (например, стоимости единицы электроэнергии в течение суток) с соблюдением синтаксиса функции linprog. Функция quadprog позволяет учесть изменения стоимости перевозок при возникновении нелинейной связи между переменными состояния путем выбора структуры положительно определенной симметрической матрицы квадратичной компоненты критерия качества. Предложены программы в кодах MATLAB для практического использования и приведены примеры, подтверждающие корректность разработанных схем алгоритмизации.
алгоритм, операционные исследования, линейное программирование, квадратичное программирование, транспортная задача, 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. Барышников С. О., Дмитриенко Д. В., Сахаров В. В., Чертков А. А. Модели и алгоритмы управления объектами водного транспорта в условиях цифровой трансформации: моногр. СПб.: Занев. площадь, 2022. 520 c.
2. Гоглачев А. И., Классификация потокового временного ряда на основе нейросетевых технологий и поведенческих шаблонов // Вестн. Юж.-Урал. гос. ун-та. Сер.: Вычислительная математика и информатика. 2024. Т. 13. № 3. С. 79–94.
3. Данилова С. В., Валинурова А. А., Балабанова Н. В. Применение задачи линейного программирования для решения частных задач банковской деятельности // Соврем. наукоем. технологии. Регион. прил. 2022. № 1 (69). С. 46–53.
4. Соколинская И. М. Численная реализация метода поверхностного движения для решения задач линейного программирования // Вестн. Юж.-Урал. гос. ун-та. Сер.: Вычислительная математика и информатика. 2024. Т. 13. № 3. С. 5–31.
5. Чертков А. А., Каск Я. Н., Сабуров С. В. Автоматизация поиска маршрутов рентабельных грузоперевозок средствами целочисленного программирования MATLAB // Вестн. Гос. ун-та мор. и реч. флота им. адм. С. О. Макарова. 2021. Т. 13. № 4. С. 496–504.
6. Кольцов М. A. Решение задачи Сильвестра в MATLAB // Избранные лекции по экстремальным задачам / под ред. В. Н. Малоземова. СПб.: Изд-во ВВМ, 2017. Ч. 1. С. 195–199.
7. Дужински Р. Р., Торопцев Е. Л. Задача квадратичного программирования в динамическом межотраслевом балансе // Вестн. Северо-Кавказ. федерал. ун-та. 2017. № 2. С. 54–60.
8. Жорняк А. Г., Морозова Т. А. Специализированный дистрибутив python (x,y) языка программирования python для научных и инженерных вычислений // Науч.-техн. вестн. Поволжья. 2022. № 7. С. 39–42.
9. Соколинский Л. Б., Ольховский Н. А., Свириденко А. Б. Прямые мультипликативные методы для разреженных матриц. Квадратичное программирование // Компьютер. исслед. и моделирование. 2018. Т. 10. № 4. С. 407–420.
10. Журбенко Н. Г., Измаилов А. Ф., Усков Е. И. Гибридная глобализация сходимости метода последовательного квадратичного программирования, стабилизированного вдоль подпространства // Вестн. Тамбов. ун-та им. Г. Р. Державина. Сер.: Естественные и технические науки. 2019. Т. 24. № 126. С. 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. V. 356. P. 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. V. 318. P. 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. V. 21. P. 1665–1690.
14. Stojkovic N., Stanimirovic P. Initial point in primal-dual interior point method // Facta Universitatis. Series Mechanics, Automatic Control and Robotics. 2021. V. 3. N. 11. P. 219–222.
15. Wang H., Zhang S. Computer aided tolerancing of composite elevator assembly involving clamping forces coordination // Procedia CIRP. 2018. V. 75. P. 256–260.
