67219

Автор(ы): 

Автор(ов): 

2

Параметры публикации

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

Тезисы доклада

Название: 

Аппроксимация целевой функции задач теории расписаний

Электронная публикация: 

Да

ISBN/ISSN: 

978-5-317-06593-5

Наименование конференции: 

  • Международный молодежный научный форум «ЛОМОНОСОВ-2021»

Наименование источника: 

  • Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2021»

Город: 

  • Москва

Издательство: 

  • МАКС Пресс

Год издания: 

2021

Страницы: 

34
Аннотация
Рассматривается линейная аппроксимация для задачи одного прибора теории расписаний: предполагается, что существует линейная относительно моментов окончания обслуживания требований целевая функция. Расписания, построенные «вручную», являются оптимальными относительно этой целевой функции. Аппроксимируются неизвестные значения весовых коэффициентов целевой функции, что сводится, как будет показано, к решению системы линейных неравенств относительно этих коэффициентов. Была сформулирована и доказана лемма о выпуклом множестве M точек гиперпространства, которые касаются каждой грани прямоугольного параллелепипеда P. Тогда центр O параллелепипеда P является внутренней точкой множества M. Данная лемма позволяет сделать вывод о равносильности исходной и введенной системы уравнений, что впоследствии необходимо для построения алгоритма аппроксимации весовых коэффициентов для случая одновременно поступающих на прибор требований. Матрица системы линейных неравенств в этом случае, как будет показано, приобретает специальный вид: она является разреженной (большинство элементов являются нулевыми) и содержит значительное число зависимых неравенств. В связи с этим метод решения прежде всего основывается на исключении зависимых неравенств из системы. Используются и некоторые общие свойства линейных систем неравенств. Результатом алгоритма является набор таких весовых коэффициентов , , что для каждого из N заданных примеров оптимальное расписание, найденное для аппроксимированных значений весовых коэффициентов либо полностью совпадает с его заданным оптимальным расписанием, соответствующим неизвестному истинному набору весовых коэффициентов , либо имеет с ним одинаковое значение целевой функции.

Библиографическая ссылка: 

Барашов Е.Б., Правдивец Н.А. Аппроксимация целевой функции задач теории расписаний / Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2021». М.: МАКС Пресс, 2021. С. 34.