ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ЗАДАЧЕ МАРШРУТИЗАЦИИ: ДЕКОМПОЗИЦИОННЫЙ ВАРИАНТ

Standard

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ЗАДАЧЕ МАРШРУТИЗАЦИИ: ДЕКОМПОЗИЦИОННЫЙ ВАРИАНТ. / Ченцов, Александр Георгиевич ; Ченцов, Павел Александрович.
In: Вестник российских университетов. Математика, Vol. 27, No. 137, 2022, p. 95-124.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{693e3e546f95445ebef1a99538d0b1fd,

title = "ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ЗАДАЧЕ МАРШРУТИЗАЦИИ: ДЕКОМПОЗИЦИОННЫЙ ВАРИАНТ",

abstract = "Исследуются вопросы применения аппарата динамического программирования (ДП) в задаче маршрутизации с ограничениями и функциями стоимости, допускающими зависимость от списка заданий. Предполагается заданным бинарное разбиение множества заданий, т. е. выделены две группы заданий; задания первой группы должны быть выполнены раньше, чем начнется выполнение заданий второй группы. В каждой из групп могут присутствовать условия предшествования. Данная постановка может быть связана, в частности, с вариантом листовой резки зонами на машинах с ЧПУ, где две вышеупомянутые группы заданий образуют зоны, намеченные на этапе раскроя. В общем случае для построения оптимального решения применяется двухэтапный вариант ДП. Стыковка этапов осуществляется посредством отождествления терминальной компоненты критерия предваряющей задачи с функций экстремума финальной задачи. Склеивание оптимальных решений предваряющей и финальной задач доставляет, как показано в статье, оптимальное решение совокупной задачи. На основе теоретических конструкций построен алгоритм, реализованный на ПЭВМ; проведен вычислительный эксперимент.",

author = "Ченцов, {Александр Георгиевич} and Ченцов, {Павел Александрович}",

note = "The work was performed as part of research conducted in the Ural Mathematical Center with the financial support of the Ministry of Science and Higher Education of the Russian Federation (Agreement number 075-02-2021-1383).",

year = "2022",

doi = "10.20310/2686-9667-2022-27-137-95-124",

language = "Русский",

volume = "27",

pages = "95--124",

journal = "Вестник российских университетов. Математика",

issn = "2686-9667",

publisher = "Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования {"}Тамбовский государственный университет им. Г.Р. Державина{"}",

number = "137",

}

RIS

TY - JOUR

T1 - ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ЗАДАЧЕ МАРШРУТИЗАЦИИ: ДЕКОМПОЗИЦИОННЫЙ ВАРИАНТ

AU - Ченцов, Александр Георгиевич

AU - Ченцов, Павел Александрович

N1 - The work was performed as part of research conducted in the Ural Mathematical Center with the financial support of the Ministry of Science and Higher Education of the Russian Federation (Agreement number 075-02-2021-1383).

PY - 2022

Y1 - 2022

N2 - Исследуются вопросы применения аппарата динамического программирования (ДП) в задаче маршрутизации с ограничениями и функциями стоимости, допускающими зависимость от списка заданий. Предполагается заданным бинарное разбиение множества заданий, т. е. выделены две группы заданий; задания первой группы должны быть выполнены раньше, чем начнется выполнение заданий второй группы. В каждой из групп могут присутствовать условия предшествования. Данная постановка может быть связана, в частности, с вариантом листовой резки зонами на машинах с ЧПУ, где две вышеупомянутые группы заданий образуют зоны, намеченные на этапе раскроя. В общем случае для построения оптимального решения применяется двухэтапный вариант ДП. Стыковка этапов осуществляется посредством отождествления терминальной компоненты критерия предваряющей задачи с функций экстремума финальной задачи. Склеивание оптимальных решений предваряющей и финальной задач доставляет, как показано в статье, оптимальное решение совокупной задачи. На основе теоретических конструкций построен алгоритм, реализованный на ПЭВМ; проведен вычислительный эксперимент.

AB - Исследуются вопросы применения аппарата динамического программирования (ДП) в задаче маршрутизации с ограничениями и функциями стоимости, допускающими зависимость от списка заданий. Предполагается заданным бинарное разбиение множества заданий, т. е. выделены две группы заданий; задания первой группы должны быть выполнены раньше, чем начнется выполнение заданий второй группы. В каждой из групп могут присутствовать условия предшествования. Данная постановка может быть связана, в частности, с вариантом листовой резки зонами на машинах с ЧПУ, где две вышеупомянутые группы заданий образуют зоны, намеченные на этапе раскроя. В общем случае для построения оптимального решения применяется двухэтапный вариант ДП. Стыковка этапов осуществляется посредством отождествления терминальной компоненты критерия предваряющей задачи с функций экстремума финальной задачи. Склеивание оптимальных решений предваряющей и финальной задач доставляет, как показано в статье, оптимальное решение совокупной задачи. На основе теоретических конструкций построен алгоритм, реализованный на ПЭВМ; проведен вычислительный эксперимент.

UR - https://elibrary.ru/item.asp?id=48161200

UR - http://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=85160519192

U2 - 10.20310/2686-9667-2022-27-137-95-124

DO - 10.20310/2686-9667-2022-27-137-95-124

M3 - Статья

VL - 27

SP - 95

EP - 124

JO - Вестник российских университетов. Математика

JF - Вестник российских университетов. Математика

SN - 2686-9667

IS - 137

ER -

ID: 29950914