Один из методов округления решения в задаче управления парком грузовых вагонов

Белоусов Федор А.

doi:10.33276/S265838870023767-6

Русский

Войти Регистрация

Главная>Выпуск 4>Один из методов округления решения в задаче управления парком грузовых вагонов

Один из методов округления решения в задаче управления парком грузовых вагонов

Оглавление

Аннотация Оценить Содержание публикации

Библиография Комментарии

Один из методов округления решения в задаче управления парком грузовых вагонов

Аннотация

Код статьи

S265838870023767-6-1

DOI

10.33276/S265838870023767-6

Тип публикации

Статья

Статус публикации

Опубликовано

Авторы

Белоусов Федор Анатольевич Связаться с автором

Должность: Доцент
Аффилиация: Государственный академический университет гуманитарных наук
Адрес: г. Москва, Мароновский пер., 26

Выпуск

Том 5 Выпуск 4

Аннотация

В работе рассматривается один из методов округления нецелочисленного решения в задаче оптимального управления парком грузовых полувагонов на заданном интервале времени, которая сводится к решению задачи линейного программирования большой размерности. Существует целый ряд хорошо известных методов получения целочисленного решения либо методов округления, которые могут быть применены к произвольной задаче линейного программирования, однако, как это часто бывает, общие методы не всегда применимы к частным задачам. Такие задачи могут требовать индивидуального подхода, и рассматриваемая проблема относится к такому типу задач. Основным ограничением рассматриваемой задачи является ее огромная размерность, которая на практике может достигать нескольких десятков миллионов переменных. Главная идея представленного подхода состоит в получении нецелочисленного решения на первом этапе, затем это решение переводится в формат цепочек маршрутов, после чего решается новая целочисленная задача, но уже на имеющемся множестве цепочек маршрутов. Новая задача характеризуется относительно маленькой размерностью и дает целочисленный ответ не позже чем за несколько секунд.

Ключевые слова

железнодорожные грузоперевозки, оптимальное планирование, линейное программирование, методы округления, теория расписаний

Классификатор

Получено

29.12.2022

Дата публикации

30.12.2022

Всего подписок

Всего просмотров

278

Оценка читателей

0.0 (0 голосов)

Цитировать Скачать pdf

ГОСТ	Белоусов Ф. А. Один из методов округления решения в задаче управления парком грузовых вагонов // Вестник ЦЭМИ РАН. – 2022. – T. 5. – Выпуск 4. URL: https://cemi.jes.su/s265838870023767-6-1/. DOI: 10.33276/S265838870023767-6
MLA	Belousov, Fedor "One of the methods of rounding solutions in the problem of managing a fleet of freight railcars." Herald of CEMI. 5.4 (2022). DOI: 10.33276/S265838870023767-6
APA	Belousov F. (2022). One of the methods of rounding solutions in the problem of managing a fleet of freight railcars. Herald of CEMI. vol. 5, no. 4 DOI: 10.33276/S265838870023767-6

Доступ к дополнительным сервисам

Дополнительные сервисы только на эту статью

Преимущества сервисов

100 руб. / 1.0 SU

Библиография

1. Белоусов, Ф. А. Моделирование и оптимизация планов грузовых железнодорожных перевозок, выполняемых транспортным оператором / Ф. А. Белоусов, И. В. Неволин, Н. К. Хачатрян // Бизнес-информатика. – 2020. – Т. 14, № 2. – с. 21–35. – URL : https://bijournal.hse.ru/data/2020/06/29/1610380184/BI%202_2020%20RU-21-35.pdf (дата обращения : 05.12.2022).

2. Белоусов, Ф. А. Снижение размерности в задаче оптимального управления парком грузовых вагонов с использованием беспилотных локомотивов / Ф. А. Белоусов, И. В. Неволин, Н. К. Хачатрян // Бизнес-информатика. – 2022. – Т. 16, № 2. – с. 7–20. – URL : https://bijournal.hse.ru/data/2022/06/30/1639228675/1.pdf (дата обращения : 05.12.2022).

3. Лазарев, А. А. Задача управления парком грузовых железнодорожных вагонов / А. А. Лазарев, Р. Р. Садыков // XII Всероссийское совещание по проблемам управления (ВСПУ 2014) ( Москва, 16–19 июня 2014) / ИПУ РАН. – Москва, 2014. – с. 5083–5093.

4. Sadykov, R. Solving a freight railcar flow problem arising in Russia / R. Sadykov, A. Lazarev, V. Shiryaev, A. Stratonnikov // Proceedings of 13th Workshop on Algorithmic Approach for Transportation Modelling, Optimization, and Systems (ATMOS’13) (Leibniz, Germany, 5 September 2013). – p. 55–67. – URL : https://drops.dagstuhl.de/opus/volltexte/2013/4244/pdf/6.pdf (дата обращения : 05.12.2022).

5. Desaulniers, G. Column generation / G. Desaulniers , J. Desrosiers , M. Solomon. – New York: Springer, 2005. – URL : https://link.springer.com/book/10.1007/b135457 (дата обращения : 05.12.2022).

6. Ahuja, Ravindra K. Capacity Scaling Algorithm / Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. // Network Flows: Theory, Algorithms and Applications. — Prentice Hall, 1993. – p. 210-211.

7. Fukasawa, Ricardo. Solving the freight car flow problem to optimality / Ricardo Fukasawa, Marcus Poggi de Aragão, Oscar Porto, and Eduardo Uchoa // Electronic Notes in Theoretical Computer Science. – 2002. – 66(6). – p. 42–52. – URL : https://www.sciencedirect.com/science/article/pii/S1571066104805280?via%3Dihub (дата обращения : 05.12.2022).


1	Введение	<p style="padding-left: 30px;"><strong>Введение</strong></p> <p style="padding-left: 30px;"><strong>Введение</strong></p>

2	В статье рассматривается модель, которая изучалась автором в коллективе с другими соавторами [1; 2]. В указанных работах рассматриваются методы решения задачи, которые в общем случае в качестве ответа дают нецелочисленный результат. Однако на практике при составлении плана передвижения грузовых вагонов нецелочисленные решения по понятным причинам не применимы. Поэтому требуются либо методы, которые сразу дают целочисленное решение, либо методы округления полученного нецелочисленного решения.	В статье рассматривается модель, которая изучалась автором в коллективе с другими соавторами [1; 2]. В указанных работах рассматриваются методы решения задачи, которые в общем случае в качестве ответа дают нецелочисленный результат. Однако на практике при составлении плана передвижения грузовых вагонов нецелочисленные решения по понятным причинам не применимы. Поэтому требуются либо методы, которые сразу дают целочисленное решение, либо методы округления полученного нецелочисленного решения. В статье рассматривается модель, которая изучалась автором в коллективе с другими соавторами [1; 2]. В указанных работах рассматриваются методы решения задачи, которые в общем случае в качестве ответа дают нецелочисленный результат. Однако на практике при составлении плана передвижения грузовых вагонов нецелочисленные решения по понятным причинам не применимы. Поэтому требуются либо методы, которые сразу дают целочисленное решение, либо методы округления полученного нецелочисленного решения.

3	Если говорить о способах, которые сразу дают точное целочисленное решение, то известно, что такие задачи относятся к классу NP-полных задач. Поэтому все методы, связанные с поиском целочисленных решений, главным образом основаны на итерационном решении линейной релаксации различных модификаций исходной задачи (то есть на каждой итерации находится нецелочисленное решение), и такие методы не гарантируют нахождение точного решения. Среди наиболее известных методов можно выделить метод ветвления и границ и метод Гомори. В условиях нашей задачи, которая характеризуется большой размерностью, напрямую такие подходы неприменимы, поскольку итерационный расчет целочисленного решения связан с большим временем, затраченным на поиск решения, что является неприемлемым для оперативного управления логистикой предприятия.	Если говорить о способах, которые сразу дают точное целочисленное решение, то известно, что такие задачи относятся к классу NP-полных задач. Поэтому все методы, связанные с поиском целочисленных решений, главным образом основаны на итерационном решении линейной релаксации различных модификаций исходной задачи (то есть на каждой итерации находится нецелочисленное решение), и такие методы не гарантируют нахождение точного решения. Среди наиболее известных методов можно выделить метод ветвления и границ и метод Гомори. В условиях нашей задачи, которая характеризуется большой размерностью, напрямую такие подходы неприменимы, поскольку итерационный расчет целочисленного решения связан с большим временем, затраченным на поиск решения, что является неприемлемым для оперативного управления логистикой предприятия. Если говорить о способах, которые сразу дают точное целочисленное решение, то известно, что такие задачи относятся к классу NP-полных задач. Поэтому все методы, связанные с поиском целочисленных решений, главным образом основаны на итерационном решении линейной релаксации различных модификаций исходной задачи (то есть на каждой итерации находится нецелочисленное решение), и такие методы не гарантируют нахождение точного решения. Среди наиболее известных методов можно выделить метод ветвления и границ и метод Гомори. В условиях нашей задачи, которая характеризуется большой размерностью, напрямую такие подходы неприменимы, поскольку итерационный расчет целочисленного решения связан с большим временем, затраченным на поиск решения, что является неприемлемым для оперативного управления логистикой предприятия.

4	В работах [3; 4] рассматривается похожая постановка транспортной задачи, которую авторы решают с помощью метода генерации колонок. Они также получают нецелочисленные решения. В отличие от них мы в своем подходе не прибегаем к этому методу в силу того, что возможны трудности с его применением в случае, если исходная задача будет усложняться за счет учета новых типов ограничений. Поэтому в данной работе представлен другой, в чем-то более простой, подход получения нецелочисленного решения исходной задачи. Тем не менее, в предлагаемом методе округления заимствуются некоторые идеи метода декомпозиции Данцига-Вульфа и, соответственно, метода генерации колонок [5].	В работах [3; 4] рассматривается похожая постановка транспортной задачи, которую авторы решают с помощью метода генерации колонок. Они также получают нецелочисленные решения. В отличие от них мы в своем подходе не прибегаем к этому методу в силу того, что возможны трудности с его применением в случае, если исходная задача будет усложняться за счет учета новых типов ограничений. Поэтому в данной работе представлен другой, в чем-то более простой, подход получения нецелочисленного решения исходной задачи. Тем не менее, в предлагаемом методе округления заимствуются некоторые идеи метода декомпозиции Данцига-Вульфа и, соответственно, метода генерации колонок [5]. В работах [3; 4] рассматривается похожая постановка транспортной задачи, которую авторы решают с помощью метода генерации колонок. Они также получают нецелочисленные решения. В отличие от них мы в своем подходе не прибегаем к этому методу в силу того, что возможны трудности с его применением в случае, если исходная задача будет усложняться за счет учета новых типов ограничений. Поэтому в данной работе представлен другой, в чем-то более простой, подход получения нецелочисленного решения исходной задачи. Тем не менее, в предлагаемом методе округления заимствуются некоторые идеи метода декомпозиции Данцига-Вульфа и, соответственно, метода генерации колонок [5].

5	Основная идея метода генерации колонок состоит в переходе от задачи, сформулированной в терминах потоков, которая в английской литературе носит название multi-commodity flow (MCF) [6] к задаче, сформулированной в терминах готовых цепочек маршрутов. При этом алгоритм является итерационным, и на каждой итерации множество цепочек маршрутов постоянно увеличивается. По всей видимости, из-за большого количества полученных цепочек могут возникать проблемы с поиском целочисленного решения в задаче, сформулированной в терминах цепочек маршрутов. Основная идея подхода, изложенного в данной работе, состоит в нахождении нецелочисленного решения MCF задачи, после чего данное решение разбирается на цепочки решений, что дает относительно небольшое множество таких цепочек, затем на основе этого множества решается целочисленная задача, сформулированная в терминах цепочек маршрутов.	Основная идея метода генерации колонок состоит в переходе от задачи, сформулированной в терминах потоков, которая в английской литературе носит название multi-commodity flow (MCF) [6] к задаче, сформулированной в терминах готовых цепочек маршрутов. При этом алгоритм является итерационным, и на каждой итерации множество цепочек маршрутов постоянно увеличивается. По всей видимости, из-за большого количества полученных цепочек могут возникать проблемы с поиском целочисленного решения в задаче, сформулированной в терминах цепочек маршрутов. Основная идея подхода, изложенного в данной работе, состоит в нахождении нецелочисленного решения MCF задачи, после чего данное решение разбирается на цепочки решений, что дает относительно небольшое множество таких цепочек, затем на основе этого множества решается целочисленная задача, сформулированная в терминах цепочек маршрутов. Основная идея метода генерации колонок состоит в переходе от задачи, сформулированной в терминах потоков, которая в английской литературе носит название multi-commodity flow (MCF) [6] к задаче, сформулированной в терминах готовых цепочек маршрутов. При этом алгоритм является итерационным, и на каждой итерации множество цепочек маршрутов постоянно увеличивается. По всей видимости, из-за большого количества полученных цепочек могут возникать проблемы с поиском целочисленного решения в задаче, сформулированной в терминах цепочек маршрутов. Основная идея подхода, изложенного в данной работе, состоит в нахождении нецелочисленного решения MCF задачи, после чего данное решение разбирается на цепочки решений, что дает относительно небольшое множество таких цепочек, затем на основе этого множества решается целочисленная задача, сформулированная в терминах цепочек маршрутов.

6	Еще одна похожая постановка транспортной задачи, реализованная для практического применения одним из крупнейших железнодорожных операторов Латинской Америки, представлена в работе [7]. Основное отличие от постановок задач, которые рассматриваются в работах [1; 2] и работах [3; 4] состоит в том, что если в [7] оптимальное планирование осуществляется исходя из известного расписания движения грузовых поездов, то в [1; 2] и [3; 4] решение ищется исходя из известных нормативов времени движения грузовых и порожних вагонов по всем заданным маршрутам. Авторы работы [7] предлагают методы получения целочисленного решения MCF задачи, при этом применяют для этого стандартный метод ветвления и границ. Основная идея, позволяющая авторам [7] использовать стандартный метод поиска целочисленного решения, состоит в разработке и применении специальных препроцессинговых алгоритмов, которые снижают размерность задачи более чем в сто раз по сравнению с ее исходным вариантом. В чем-то схожие препроцессинговые алгоритмы по отношению к рассматриваемой в данной работе модели описаны в статье [2]. Однако изначально размерность задачи настолько велика, что даже заметное снижение ее размерности не позволяет прибегать к прямому использованию стандартных методов целочисленного поиска.	Еще одна похожая постановка транспортной задачи, реализованная для практического применения одним из крупнейших железнодорожных операторов Латинской Америки, представлена в работе [7]. Основное отличие от постановок задач, которые рассматриваются в работах [1; 2] и работах [3; 4] состоит в том, что если в [7] оптимальное планирование осуществляется исходя из известного расписания движения грузовых поездов, то в [1; 2] и [3; 4] решение ищется исходя из известных нормативов времени движения грузовых и порожних вагонов по всем заданным маршрутам. Авторы работы [7] предлагают методы получения целочисленного решения MCF задачи, при этом применяют для этого стандартный метод ветвления и границ. Основная идея, позволяющая авторам [7] использовать стандартный метод поиска целочисленного решения, состоит в разработке и применении специальных препроцессинговых алгоритмов, которые снижают размерность задачи более чем в сто раз по сравнению с ее исходным вариантом. В чем-то схожие препроцессинговые алгоритмы по отношению к рассматриваемой в данной работе модели описаны в статье [2]. Однако изначально размерность задачи настолько велика, что даже заметное снижение ее размерности не позволяет прибегать к прямому использованию стандартных методов целочисленного поиска. Еще одна похожая постановка транспортной задачи, реализованная для практического применения одним из крупнейших железнодорожных операторов Латинской Америки, представлена в работе [7]. Основное отличие от постановок задач, которые рассматриваются в работах [1; 2] и работах [3; 4] состоит в том, что если в [7] оптимальное планирование осуществляется исходя из известного расписания движения грузовых поездов, то в [1; 2] и [3; 4] решение ищется исходя из известных нормативов времени движения грузовых и порожних вагонов по всем заданным маршрутам. Авторы работы [7] предлагают методы получения целочисленного решения MCF задачи, при этом применяют для этого стандартный метод ветвления и границ. Основная идея, позволяющая авторам [7] использовать стандартный метод поиска целочисленного решения, состоит в разработке и применении специальных препроцессинговых алгоритмов, которые снижают размерность задачи более чем в сто раз по сравнению с ее исходным вариантом. В чем-то схожие препроцессинговые алгоритмы по отношению к рассматриваемой в данной работе модели описаны в статье [2]. Однако изначально размерность задачи настолько велика, что даже заметное снижение ее размерности не позволяет прибегать к прямому использованию стандартных методов целочисленного поиска.

7	Описание исходной постановки транспортной задачи	<p style="padding-left: 30px;"><strong>Описание </strong><strong>исходной постановки транспортной задачи</strong></p> <p style="padding-left: 30px;"><strong>Описание </strong><strong>исходной постановки транспортной задачи</strong></p>

8	Для начала рассмотрим постановку исходной задачи, которая изучалась в работах [1; 2]. Здесь мы не будем детально её разбирать, в указанных работах это сделано, для нас более интересным является алгоритм получения другой постановки, с помощью которой из имеющегося нецелочисленного решения можно будет рассчитывать целочисленное.	Для начала рассмотрим постановку исходной задачи, которая изучалась в работах [1; 2]. Здесь мы не будем детально её разбирать, в указанных работах это сделано, для нас более интересным является алгоритм получения другой постановки, с помощью которой из имеющегося нецелочисленного решения можно будет рассчитывать целочисленное. Для начала рассмотрим постановку исходной задачи, которая изучалась в работах [1; 2]. Здесь мы не будем детально её разбирать, в указанных работах это сделано, для нас более интересным является алгоритм получения другой постановки, с помощью которой из имеющегося нецелочисленного решения можно будет рассчитывать целочисленное.

9	Постановка задачи, представленная в работах [1; 2] как MCF задача, имеет следующий вид:	Постановка задачи, представленная в работах [1; 2] как MCF задача, имеет следующий вид: Постановка задачи, представленная в работах [1; 2] как MCF задача, имеет следующий вид:

10	${P C}^{T} \cdot K ⟶ \underset{K \geq 0}{m a x}, (1)$	<math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msup><mrow><mi>P</mi><mi>C</mi></mrow><mrow><mi>T</mi></mrow></msup><mo>⋅</mo><mi>K</mi><mo>⟶</mo><munder><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi></mrow><mrow><mi>K</mi><mo>≥</mo><mn>0</mn></mrow></munder><mo>,</mo><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mfenced separators="\|"><mrow><mn>1</mn></mrow></mfenced></math> <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msup><mrow><mi>P</mi><mi>C</mi></mrow><mrow><mi>T</mi></mrow></msup><mo>⋅</mo><mi>K</mi><mo>⟶</mo><munder><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi></mrow><mrow><mi>K</mi><mo>≥</mo><mn>0</mn></mrow></munder><mo>,</mo><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mfenced separators="\|"><mrow><mn>1</mn></mrow></mfenced></math>

11	${{(A}_{o u t} - A}_{i n}) \cdot K = S_{0}, (2)$	<math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><msub><mrow><mo>(</mo><mi>A</mi></mrow><mrow><mi>o</mi><mi>u</mi><mi>t</mi></mrow></msub><mo>-</mo><mi>A</mi></mrow><mrow><mi>i</mi><mi>n</mi></mrow></msub><mo>)</mo><mo>⋅</mo><mi>K</mi><mo>=</mo><msub><mrow><mi>S</mi></mrow><mrow><mn>0</mn></mrow></msub><mo>,</mo><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mfenced separators="\|"><mrow><mn>2</mn></mrow></mfenced></math> <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><msub><mrow><mo>(</mo><mi>A</mi></mrow><mrow><mi>o</mi><mi>u</mi><mi>t</mi></mrow></msub><mo>-</mo><mi>A</mi></mrow><mrow><mi>i</mi><mi>n</mi></mrow></msub><mo>)</mo><mo>⋅</mo><mi>K</mi><mo>=</mo><msub><mrow><mi>S</mi></mrow><mrow><mn>0</mn></mrow></msub><mo>,</mo><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mfenced separators="\|"><mrow><mn>2</mn></mrow></mfenced></math>

12	$A_{Q} \cdot K \leq Q, (3)$	<math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>A</mi></mrow><mrow><mi>Q</mi></mrow></msub><mo>⋅</mo><mi>K</mi><mo>≤</mo><mi>Q</mi><mo>,</mo><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mfenced separators="\|"><mrow><mn>3</mn></mrow></mfenced></math> <em> </em> <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>A</mi></mrow><mrow><mi>Q</mi></mrow></msub><mo>⋅</mo><mi>K</mi><mo>≤</mo><mi>Q</mi><mo>,</mo><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mi> </mi><mfenced separators="\|"><mrow><mn>3</mn></mrow></mfenced></math> <em> </em>

13	где $K$ – вектор, который мы ищем, каждый элемент этого вектора соответствует определенному маршруту, стартующему и заканчивающемуся в определенные дни расчетного периода. Другими словами, элементы вектора $K$ отвечают за дуги в пространственно-временном графе.	где <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mi>K</mi></math> – вектор, который мы ищем, каждый элемент этого вектора соответствует определенному маршруту, стартующему и заканчивающемуся в определенные дни расчетного периода. Другими словами, элементы вектора <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mi>K</mi></math> отвечают за дуги в пространственно-временном графе. где <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mi>K</mi></math> – вектор, который мы ищем, каждый элемент этого вектора соответствует определенному маршруту, стартующему и заканчивающемуся в определенные дни расчетного периода. Другими словами, элементы вектора <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mi>K</mi></math> отвечают за дуги в пространственно-временном графе.

14	$P C$ – вектор, положительные элементы которого соответствуют ставкам за груженые рейсы, отрицательные – тарифам за порожние перегоны вагонов. Произведение ${P C}^{T} \cdot K$ соответствует прибыли от управления парком вагонов.	<math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mi>P</mi><mi>C</mi></math> – вектор, положительные элементы которого соответствуют ставкам за груженые рейсы, отрицательные – тарифам за порожние перегоны вагонов. Произведение <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msup><mrow><mi>P</mi><mi>C</mi></mrow><mrow><mi>T</mi></mrow></msup><mo>⋅</mo><mi>K</mi></math> соответствует прибыли от управления парком вагонов. <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mi>P</mi><mi>C</mi></math> – вектор, положительные элементы которого соответствуют ставкам за груженые рейсы, отрицательные – тарифам за порожние перегоны вагонов. Произведение <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msup><mrow><mi>P</mi><mi>C</mi></mrow><mrow><mi>T</mi></mrow></msup><mo>⋅</mo><mi>K</mi></math> соответствует прибыли от управления парком вагонов.

15	$A_{o u t}$ – матрица, отвечающая за исходящие маршруты для каждой из станций.	<math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>A</mi></mrow><mrow><mi>o</mi><mi>u</mi><mi>t</mi></mrow></msub></math> – матрица, отвечающая за исходящие маршруты для каждой из станций. <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>A</mi></mrow><mrow><mi>o</mi><mi>u</mi><mi>t</mi></mrow></msub></math> – матрица, отвечающая за исходящие маршруты для каждой из станций.

16	$A_{i n}$ – матрица, отвечающая за входящие маршруты для каждой станции. Ограничение (2) является балансовым ограничением, его выполнение гарантирует то, что от станции в каждый момент времени поедет ровно столько вагонов, сколько туда в этот момент времени приехало плюс те вагоны, которые приехали на эту станцию из прошлого расчетного периода (из прошлого месяца).	<math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>A</mi></mrow><mrow><mi>i</mi><mi>n</mi></mrow></msub></math> – матрица, отвечающая за входящие маршруты для каждой станции. Ограничение (2) является балансовым ограничением, его выполнение гарантирует то, что от станции в каждый момент времени поедет ровно столько вагонов, сколько туда в этот момент времени приехало плюс те вагоны, которые приехали на эту станцию из прошлого расчетного периода (из прошлого месяца). <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>A</mi></mrow><mrow><mi>i</mi><mi>n</mi></mrow></msub></math> – матрица, отвечающая за входящие маршруты для каждой станции. Ограничение (2) является балансовым ограничением, его выполнение гарантирует то, что от станции в каждый момент времени поедет ровно столько вагонов, сколько туда в этот момент времени приехало плюс те вагоны, которые приехали на эту станцию из прошлого расчетного периода (из прошлого месяца).

17	$S_{0}$ – вектор, характеризующий начальное количество вагонов на каждой станции в каждый момент модельного времени. Элемент вектора равен положительному целому значению, если на данную станцию в данный момент времени из прошлого расчетного периода (из прошлого месяца) пребывают вагоны в количестве равном значению данного элемента. В противном случае, если на данную станцию в данный момент времени вагоны из прошлого расчетного периода не прибывают, то значение элемента вектора равно нулю. Неотрицательный элемент вектора $S_{0}$ характеризует станцию, которая в связке с моментом времени прибытия туда вагонов называется источником.	<math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>S</mi></mrow><mrow><mn>0</mn></mrow></msub></math> – вектор, характеризующий начальное количество вагонов на каждой станции в каждый момент модельного времени. Элемент вектора равен положительному целому значению, если на данную станцию в данный момент времени из прошлого расчетного периода (из прошлого месяца) пребывают вагоны в количестве равном значению данного элемента. В противном случае, если на данную станцию в данный момент времени вагоны из прошлого расчетного периода не прибывают, то значение элемента вектора равно нулю. Неотрицательный элемент вектора <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>S</mi></mrow><mrow><mn>0</mn></mrow></msub></math> характеризует станцию, которая в связке с моментом времени прибытия туда вагонов называется источником. <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>S</mi></mrow><mrow><mn>0</mn></mrow></msub></math> – вектор, характеризующий начальное количество вагонов на каждой станции в каждый момент модельного времени. Элемент вектора равен положительному целому значению, если на данную станцию в данный момент времени из прошлого расчетного периода (из прошлого месяца) пребывают вагоны в количестве равном значению данного элемента. В противном случае, если на данную станцию в данный момент времени вагоны из прошлого расчетного периода не прибывают, то значение элемента вектора равно нулю. Неотрицательный элемент вектора <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>S</mi></mrow><mrow><mn>0</mn></mrow></msub></math> характеризует станцию, которая в связке с моментом времени прибытия туда вагонов называется источником.

18	$Q$ – вектор, отвечающий за максимальные объемы по каждой из имеющихся заявок.	<math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mi>Q</mi></math> – вектор, отвечающий за максимальные объемы по каждой из имеющихся заявок. <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mi>Q</mi></math> – вектор, отвечающий за максимальные объемы по каждой из имеющихся заявок.

19	$A_{Q}$ – матрица, отвечающая за учет груженых рейсов. Ограничение (3) отвечает за то, чтобы объем выполненных заявок не превышал заданного объема заявок.	<math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>A</mi></mrow><mrow><mi>Q</mi></mrow></msub></math> – матрица, отвечающая за учет груженых рейсов. Ограничение (3) отвечает за то, чтобы объем выполненных заявок не превышал заданного объема заявок. <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><msub><mrow><mi>A</mi></mrow><mrow><mi>Q</mi></mrow></msub></math> – матрица, отвечающая за учет груженых рейсов. Ограничение (3) отвечает за то, чтобы объем выполненных заявок не превышал заданного объема заявок.

20	Нам хотелось бы найти целочисленное решение $K$ поставленной задачи (1) – (3). Но, как уже было сказано выше, применять напрямую целочисленные методы решения к данной задаче нецелесообразно, поскольку решатся она будет очень долго. На практике размерность такой задачи может доходить до 60 миллионов переменных и выше. Поэтому искать мы будем нецелочисленное решение, такая задача называется линейной релаксацией исходной задачи (1) – (3).	Нам хотелось бы найти целочисленное решение <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mi>K</mi></math> поставленной задачи (1) – (3). Но, как уже было сказано выше, применять напрямую целочисленные методы решения к данной задаче нецелесообразно, поскольку решатся она будет очень долго. На практике размерность такой задачи может доходить до 60 миллионов переменных и выше. Поэтому искать мы будем нецелочисленное решение, такая задача называется линейной релаксацией исходной задачи (1) – (3). Нам хотелось бы найти целочисленное решение <math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mi>K</mi></math> поставленной задачи (1) – (3). Но, как уже было сказано выше, применять напрямую целочисленные методы решения к данной задаче нецелесообразно, поскольку решатся она будет очень долго. На практике размерность такой задачи может доходить до 60 миллионов переменных и выше. Поэтому искать мы будем нецелочисленное решение, такая задача называется линейной релаксацией исходной задачи (1) – (3).

Библиография

Комментарии

Войти через