Распределение ресурсов в иерархических системах транспортного типа с интервальными значениями критериев оптимальности
Задача поиска оптимальной вершины многомерного многозначного куба. Решение задачи проверки на совместность систем двусторонних линейных алгебраических неравенств транспортного типа. Построение корневого дерева, моделирующего систему ограничений.
| Рубрика | Математика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 28.07.2017 |
| Размер файла | 165,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Нижегородский государственный университет им. Н.И. Лобачевского
Распределение ресурсов в иерархических системах транспортного типа с интервальными значениями критериев оптимальности
М.Х. Прилуцкий, У.С. Колосовская
Аннотация
Рассматривается проблема многокритериального распределения ресурсов в иерархических системах транспортного типа с интервальными значениями критериев оптимальности. Строится общая математическая модель, в рамках которой ставятся задачи многокритериальной оптимизации. Решение поставленных задач находится путем поиска «оптимальных» вершин многомерного многозначного куба, где каждая вершина куба определяет свою систему линейных алгебраических двусторонних неравенств транспортного типа. Решение многокритериальной задачи осуществляется сведением её к однокритериальной, путем задания на множестве вершин многомерного многозначного куба некоторых порядков. В основе предлагаемых схем решения лежит процесс последовательной проверки на совместность системы, описывающей ограничения на допустимые значения распределяемого ресурса. В качестве примера прикладной задачи рассматривается задача объемно-календарного планирования для подразделений предприятия.
Ключевые слова: иерархическая система транспортного типа, распределение ресурсов, многоиндексная система линейных алгебраических неравенств, многокритериальная оптимизация, многомерный многозначный куб.
Введение
Широкий класс прикладных задач связан с проблемой эффективного распределения ограниченных ресурсов. При постановке задач распределения ресурсов обычно задаются директивные показатели, к достижению определённых значений которых необходимо стремиться. Учет этих показателей осуществляется с помощью так называемых контролируемых ограничений, от выполнения которых зависит эффективность функционирования системы, что приводит к постановке многокритериальных многоиндексных задач транспортного типа.
В работе для формализации критериев оптимальности предлагается указывать границы для величин отклонений от заданных директивных показателей, в которых эти величины являются «отличными», «очень хорошими», «хорошими», «удовлетворительными» и др. Отсюда следует, что функции отклонений от директивных показателей должны быть кусочно-постоянными. Тогда такие функции разбивают множество величин отклонений по каждому критерию на области качества отклонений.
В работе предлагаются эффективные алгоритмы решения поставленных многокритериальных задач путем поиска «оптимальных» вершин некоторых подмножеств многомерного (по количеству критериев) многозначного (по количеству областей качества отклонений) куба [1], где каждая вершина куба определяет свою систему линейных алгебраических двусторонних неравенств транспортного типа.
В качестве примера многокритериальной многоиндексной задачи транспортного типа рассмотрим задачу объемно-календарного планирования для подразделений предприятия [2-6].
Необходимо определить на заданный период планирования программу производства в объёмных показателях, удовлетворяющую некоторым заданным характеристикам. Пусть I - множество номеров подразделений предприятия, J - множество номеров заказов, K - множество номеров изделий, S - множество номеров деталей, T - множество номеров тактов планирования. Обозначим через aijkst объём работ, оставшийся невыполненным в подразделении i по заказу j изделию k детали s в такт планирования t; Bjkst - объем работ, запланированный к выполнению по заказу j изделию k детали s в такт t; и - минимальный и максимальный объем работ, который должен быть выполнен по изделию k детали s в такт t, ; и - минимальный и максимальный объем работ, который должен быть выполнен такт t по изделию k, ; и - минимальный и максимальный объем работ, который должен быть выполнен всеми подразделениями в такт t в планируемом периоде, ; G - общий объем запланированных работ; i I, j J, k K, s S, t T.
Тогда формально задача объёмно-календарного планирования для подразделений предприятия может быть поставлена как задача определения таких величин xijkst (объём работ, который будет выполнен в подразделении i по заказу j изделию k детали s в такт планирования t), i I, j J, k K, s S, t T, для которых выполняются ограничения:
(1)
(2)
(3)
(4)
(5)
, (6)
с учетом минимизируемых критериев, которые в рассматриваемой постановке определяются контролируемыми ограничениями системы. В качестве контролируемых ограничений, могут выступать, например, ограничения на объемы работ, которые должны быть выполнены по тактам планирования.
В качестве других примеров могут быть рассмотрены: задача объемно-календарного планирования при проведении лесотранспортных работ [7], задача транспортно-технологического освоения лесосырьевой базы [8], многопродуктовая транспортная задача с промежуточными пунктами [4], задача переработки газового конденсата [9].
Для всех таких задач общим является то, что варьируемые параметры математической модели являются многоиндексными; ограничения математической модели представляют собой систему линейных алгебраических в общем случае двусторонних неравенств транспортного типа (коэффициенты перед переменными принадлежат множеству {0, 1, -1}), каждое из которых получается суммированием по некоторым индексам; функции, формализующие критерии оптимальности, определяются контролируемыми ограничениями.
Функции критериев мы будем задавать в виде кусочно-постоянных функций, которые разбивают множество величин отклонений по каждому критерию на области качества отклонений. Будем считать, что функции, определяющие критерии оптимальности, имеют одинаковую область значений, равную множеству целых чисел от 0 до p (0 - «превосходно», 1 - «отлично», 2 - «очень хорошо», и т.д., p - «удовлетворительно»).
Постановка многокритериальной задачи
Перенумеровав переменные и ограничения рассматриваемой задачи, получим:
, (7)
где 0 ? Ai ? Bi < ?, Q(i) - множество индексов, по которым происходит суммирование для ограничения i, , xj - объемы распределяемого ресурса (для задачи объёмно-календарного планирования - это объемы выполняемых работ), а q - число всех ограничений, , . Не уменьшая общности, будем считать, что первые n ограничений являются контролируемыми и определяют критерии рассматриваемой многокритериальной задачи распределения ресурсов.
Как и в [6], рассмотрим функцию , определенную на множестве RN со значениями из {0, 1, …, p}. Для каждого контролируемого ограничения i рассмотрим совокупность вложенных друг в друга сегментов , , , , . Тогда , если но . Введенная функция отображает пространство RN на множество вершин n-мерного (по числу контролируемых ограничений) p + 1-ичного куба (по количеству областей "качества" отклонений от заданных величин).
Общая задача распределения ресурсов ставится следующим образом: требуется найти вектор , удовлетворяющий ограничениям (7), с учетом минимизируемых критериев , , .
Задача поиска оптимальной вершины многомерного многозначного куба
Решение поставленной многокритериальной задачи будем осуществлять сведением её к однокритериальной. Для этого зададим на множестве вершин куба некоторый полный порядок р. При этом поиск решения будем осуществлять на различных подмножествах вершин куба, которые определяются в зависимости от условий постановок конкретных прикладных задач.
Множество вершин n-мерного -ичного куба обозначим V(p+1),n. Каждой вершине куба поставим в соответствие систему линейных алгебраических неравенств, всегда включающую в себя совокупность неконтролируемых ограничений из (7), и n ограничений, зависящих от вершины куба: если , то ограничение с номером i преобразуется в ограничение , . Пусть также заданы вершина куба , l-ая координата которой определяет предельно допустимое значение l-ого критерия оптимальности; и вершина куба , l-ая координата которой определяет значение l-ого критерия оптимальности, к которому необходимо стремиться, . Полагаем, что , и . Через обозначим множество таких вершин куба, координаты которых принимают значения из соответствующего интервала, определяемого заданными вершинами куба , . Таким образом, нас будут интересовать только те вершины куба, которые принадлежат множеству .
Тогда задача распределения ресурсов будет заключаться в определении такого N-мерного вектора , для которого , и для любого , для которого , выполняется отношение , при условиях , , . Здесь и далее вершину будем называть оптимальной вершиной на множестве .
Зададим также на множестве вершин куба двузначную функцию , принимающую значение 1, если система совместна и 0 в противном случае. Для функции выполняется: если для вершин куба и имеет место (покомпонентно), то , отсюда функция является монотонной. Таким образом, для решения задачи распределения ресурсов необходимо уметь решать две задачи: задачу поиска оптимальной вершины многомерного многозначного куба и задачу проверки на совместность систем двусторонних линейных алгебраических неравенств транспортного типа.
Решение задачи поиска оптимальной вершины многомерного многозначного куба
В качестве порядка р выберем лексикографическое отношение порядка: тогда и только тогда, если , , .
В [6] предложен алгоритм решения задачи поиска оптимальной вершины многомерного многозначного куба для случая, когда , а . Для множества вершин этот алгоритм включает в себя следующие шаги. На первом шаге среди вершин вида , находится такое значение , , которое обеспечивает , и , для всех тех , для которых . На втором шаге среди вершин вида аналогично находится вторая координата оптимальной вершины, . На -ом шаге находим искомую оптимальную на множестве вершину. Так как функция является монотонной, то, используя на каждом шаге двоичный поиск по соответствующей этому шагу координате вершины куба, алгоритм решения поставленной задачи будет включать в себя порядка проверок совместности систем ограничений типа (7).
Иногда при функционировании системы могут возникать дополнительные условия, тогда нас может интересовать не всё множество вершин , а только некоторое его подмножество W. В этом случае будем рассматривать задачу поиска оптимальной на подмножестве W вершины. Рассмотрим следующую схему построения множества W.
Пусть дополнительными условиями для рассмотренной задачи объёмно-календарного планирования являются следующие условия:
, (8)
- общий объем выполненных работ в текущий такт не должен превышать объема, работ, выполненного в предыдущий такт. Данные условия являются естественными в случае, когда работы последующего такта планирования напрямую зависят от объёмов работ, выполненных на текущем такте планирования.
Для построения множества W, в силу , можем найти координату с наименьшим по порядку номером s такую, что: и . Далее, используя двоичный поиск по координате s (согласно изложенной выше схеме поиска оптимальной вершины куба) найдём значение .
Вначале полагаем: , , . Затем найдём такое значение s1, что , . Если s1 не найдено, завершаем процесс построения множества W. В противном случае, если i - текущий шаг построения множества W, , тогда i-ая вершина W имеет вид: , ; , откуда в силу , следует, что , и, значит, справедливо , . Множество W содержит не более n элементов.
Для решения задачи поиска оптимальной вершины среди вершин множества W, предложим следующую вычислительную процедуру. В силу , , организуем двоичный поиск по элементам множества W и найдём такое наибольшее значение i, которое обеспечивает , . Тогда , причём , если . Алгоритм решения поставленной задачи будет включать в себя порядка log2|W| проверок совместности систем ограничений типа (7).
Решение задачи проверки на совместность систем двусторонних линейных алгебраических неравенств транспортного типа
В общем случае для исследования вопроса совместности системы типа (7) можно воспользоваться классическими вычислительными методами линейной алгебры [10]. Также возможно применить хорошо зарекомендовавший себя [2] релаксационный метод ортогональных проекций Агмона-Моцкина [11-12]. Однако, учитывая транспортную специфику рассматриваемых систем, для их проверки на совместность можно воспользоваться специальными, более эффективными методами ([2]).
Так для задачи объёмно-календарного планирования система (1)-(6) моделируется корневым ориентированным деревом, в котором ограничение (1) соответствует корню дерева, ограничения (6) - листьям, ограничения (2)-(5) - промежуточным вершинам дерева. Согласно [13], для исследования совместности этой системы может быть использована теорема о «приведенных границах». Тогда проверка на совместность системы ограничений (1)-(6) потребует линейного числа операций относительно переменных рассматриваемой задачи.
Численный пример
Рассмотрим задачу объемно-календарного планирования для подразделений предприятия, где I = {1, 2}, J = {1}, K = {1}, S = {1, 2}, T = {1, 2}, и система ограничений имеет вид:
Система 1.
; (9)
, (10)
; (11)
, (12)
,,,; (13)
,,,; (14)
,, , , (15)
, , , . (16)
Соответствующее этой системе дерево изображено на рис. 1.
Рис. 1 Корневое ориентированное дерево, моделирующее систему ограничений (9)-(16)
транспортный многозначный алгебраический неравенство
Пусть в качестве контролируемых ограничений выступают ограничения (10)-(11) на объемы работ, которые должны быть выполнены по тактам планирования. Пусть совокупности вложенных интервалов для контролируемых ограничений (10)-(11) имеют вид: [8, 8] ? [8, 9] ? [8, 12] ? [8, 13] ? [8, 14] и [11, 13] ? [10, 13] ? [8, 13] ? [6, 13] ? [5, 13], соответственно.
Здесь p = 4 и задача моделируется двумерным пятеричным кубом, каждая вершина которого определяется двумерным вектором с компонентами из множества {0, 1, 2, 3, 4}. Будем предполагать, что контролируемое ограничение (10) лексикографически предпочтительнее ограничения (11). Пусть также и .
Прежде чем приступить к решению задачи 1, проверим на совместность систему 2, которая отличается от системы 1 только ограничением (11), которое теперь имеет вид . Согласно теореме о «приведенных границах» [13] система 2 совместна, поэтому можем начать поиск оптимальной вершины куба.
На первом шаге работы алгоритма среди вершин вида (н1, 3), н1 {0, 1, 2, 3, 4}, найдём наименьшую по лексикографическому порядку вершину куба. Рассмотрим вершину куба (2, 3). Соответствующая этой вершине система ограничений 3 отличается от системы 2 только ограничением с номером (10), которое теперь имеет вид ы кубаой вершины но на рис. 4.аодит суммирование . Воспользовавшись теоремой о «приведенных границах» [13], можем установить совместность системы 3. Рассмотрим вершину куба (0, 3). Соответствующая этой вершине система ограничений 4 отличается от системы 3 только ограничением с номером (10), которое теперь имеет вид ы кубаой вершины но на рис. 4.аодит суммирование . Согласно теореме о «приведенных границах» [13] система 4 совместна.
На втором шаге работы алгоритма аналогичным образом определим, что оптимальной (по введённому лексикографическому порядку) вершиной будет вершина (0, 3). Оптимальным решением задачи является следующее решение: , , , , , , , .
Заключение
В статье рассмотрена проблема распределения ресурсов в иерархических системах транспортного типа. Решение поставленной многокритериальной задачи осуществляется сведением её к однокритериальной, путем задания на множестве вершин многомерного многозначного куба некоторых порядков, при этом поиск решения осуществляется на различных подмножествах вершин куба. В качестве примера прикладной задачи, формализуемой как задача распределения ресурсов в иерархических системах транспортного типа, рассмотрена задача объемно-календарного планирования для подразделений предприятия.
Литература
1. Прилуцкий М.Х., Костюков В.Е. Оптимизационные задачи объёмно-календарного планирования для нефтеперерабатывающих предприятий // Системы управления и информационные технологии. 2007. №2.1(28). С. 188-192.
2. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи распределения ресурсов в иерархических системах // Автоматика и телемеханика. 2006. №6. С. 194-205.
3. Прилуцкий М.Х., Власов С.Е. Многокритериальные задачи объемного планирования. Лексикографические схемы // Информационные технологии. 2005. №7. С. 61-66.
4. Афраймович Л.Г., Прилуцкий М.Х. Поиск потока в несовместных транспортных сетях // Управление большими системами. 2009. №24. С. 147-168.
5. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи оптимального планирования производства // Автоматика и телемеханика. 2010. №10. С. 148-155.
6. Прилуцкий М.Х. Многокритериальные многоиндексные задачи объёмно-календарного планирования // Известия академии наук. Теория и системы управления. 2007. №1. С. 78-82.
7. Кузнецов А.В., Скрыпник В.И., Крупко А.М. Принципы подхода к объемному календарному планированию при проведении лесотранспортных работ // Инженерный вестник Дона, 2012, №2 URL: ivdon.ru/ru/magazine/archive/n2y2012/881.
8. Шегельман И.Р., Кузнецов А.В., Скрыпник В.И., Баклагин В.Н. Методика оптимизаций транспортно-технологического освоения лесосырьевой базы с минимизацией затрат на заготовку и вывозку древесины // Инженерный вестник Дона, 2012, №4 URL: ivdon.ru/magazine/archive/n4p2y2012/1284.
9. Prilutskii, M.Kh. and V.E. Kostyukov, 2012. Optimization models of gas and gas condensate processing. Automation and Remote Control, 72(8), pp. 345-349.
10. Черников С.Н. Линейные неравенства. М.: Наука, 1968. 488 с.
11. Agmon, S., 1954. The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6(3), pp. 382-392.
12. Motzkin, T.S. and I.J. Schoenberg, 1954. The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6(3), pp. 393-404.
13. Прилуцкий М.Х. Распределение однородного ресурса в иерархических системах древовидной структуры // Труды международной конференции «Идентификация систем и задачи управления SICPRO'2000». М.: Институт проблем управления им. В.А. Трапезникова РАН, 2000. С. 2038-2049.
Размещено на Allbest.ru
Подобные документы
Основные понятия теории систем уравнений. Метод Гаусса — метод последовательного исключения переменных. Формулы Крамера. Решение систем линейных уравнений методом обратной матрицы. Теорема Кронекер–Капелли. Совместность систем однородных уравнений.
лекция [24,2 K], добавлен 14.12.2010Однородные системы линейных неравенств и выпуклые конусы. Применение симплекс-метода для отыскания опорного решения системы линейных неравенств, ее геометрический смысл. Основная задача линейного программирования. Теорема Минковского, ее доказательство.
курсовая работа [807,2 K], добавлен 03.04.2015Задачи вычислительной линейной алгебры. Математическое моделирование разнообразных процессов. Решение систем линейных алгебраических уравнений большой размерности. Метод обратной матрицы и метод Гаусса. Критерии совместности и определенности системы.
курсовая работа [220,0 K], добавлен 21.10.2011Рассмотрение систем линейных алгебраических уравнений общего вида. Сущность теорем и их доказательство. Особенность трапецеидальной матрицы. Решение однородных и неоднородных линейных алгебраических уравнений, их отличия и применение метода Гаусса.
реферат [66,4 K], добавлен 14.08.2009Решение системы линейных уравнений методом Гауса. Преобразования расширенной матрицы, приведение ее к треугольному виду. Средства матричного исчисления. Вычисление алгебраических дополнений матрицы. Решение матричного уравнения по правилу Крамера.
задача [26,8 K], добавлен 29.05.2012Предикатное представление условий непересечения многоугольников. Алгоритм непересечения многоугольника и полосы. Определение направления обхода вершин многоугольника. Решение систем линейных алгебраических уравнений. Построение интерактивной оболочки.
дипломная работа [800,2 K], добавлен 10.11.2012Алгоритм решения задач по теме "Матрицы". Исследование на совместность системы линейных алгебраических уравнений, пример их решения по правилу Крамера. Определение величины угла при вершине в треугольнике, длины вектора. Исследование сходимости рядов.
контрольная работа [241,6 K], добавлен 19.03.2011Симплексный метод как универсальное решение задач линейного программирования. Применение метода Жордана-Гаусса для системы линейных уравнений в канонической форме. Опорное решение системы ограничений. Критерий оптимальности. Задача канонической формы.
презентация [2,0 M], добавлен 11.04.2013Графический и симплексный методы решения ОЗЛП. Построение функции цели, образующая совместно с системой ограничений математическую модель экономической задачи. Нахождение неотрицательного решения системы линейных уравнений. Решение транспортной задачи.
лабораторная работа [322,9 K], добавлен 10.04.2009Существование и способ построения фундаментального набора решений для систем, состоящих из одного или нескольких неравенств. Метод последовательного уменьшения числа неизвестных. Системы однородных и неоднородных произвольных линейных неравенств.
курсовая работа [69,8 K], добавлен 09.12.2011
