ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 1, с. 83-87
== КОМПЬЮТЕРНЫЕ МЕТОДЫ =
УДК 519.847
МНОГОКРИТЕРИАЛЬНЫЕ МНОГОИНДЕКСНЫЕ ЗАДАЧИ ОБЪЕМНО-КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ
© 2007 г. М. X. Прилуцкий
Нижний Новгород, Нижегородский государственный универсистет Поступила в редакцию 04.07.06 г.
Рассматриваются задачи объемно-календарного планирования как многокритериальные многоиндексные задачи транспортного типа. Предлагаются вычислительные схемы решения поставленных задач путем осуществления направленного поиска оптимальной вершины многомерного многозначного куба.
Введение. Широкий класс задач принятия решений связан с проблемой эффективного планирования и управления производственными системами. Типичным представителем таких задач является задача объемно-календарного планирования для подразделений предприятия с единичным и мелкосерийным характером производства. Сформулируем подобную задачу не в общей постановке, с учетом всех зависимостей и связей (как в [1, 2]), а с некоторой степенью идеализации. Вместо технологических требований, которые обычно задаются сетевыми структурами, учитываются этапы изготовления продукции, а вместо конкретных работ с их длительностями - объемные показатели, связанные с совокупностями работ, входящих в соответствующие этапы изготовления продукции. Содержательно задача объемно-календарного планирования формулируется следующим образом. Требуется распределить общий план предприятия в объемных характеристиках (нормо-часы, рубли, условные тонны) по различным показателям: группам оборудования, периодам планирования, этапам изготовления, потребляемым ресурсам, видам продукции. Показатели искомого плана делятся на жесткие, требующие обязательного выполнения, и желательные, к достижению которых нужно стремиться. Жесткие показатели формализуются в виде ограничений, а желательные - в виде критериев оптимальности. Тогда задача объемно-календарного планирования ставится как многокритериальная задача (учет желательных показателей) с ограничениями (учет жестких показателей), которые в рассматриваемой идеализации являются линейными.
Пусть 7 = 1, т - номера подразделений предприятия, у = 1, п - заказов, к = 1,5 - изделий, t = 1, д -периодов планирования. Обозначим через ЬуЫ объем работ, оставшийся невыполненным в 7-м подразделении по у-му заказу и к-му изделию в период планирования £ ёи - объем работ, который
может быть достигнут в 7-м подразделении в период планирования £ Гук - объем работ, который должен быть осуществлен по у-му заказу и к-му изделию; у - обязательный объем работ в период планирования t по заказу у для изделия к; -
необходимый объем работ поу-му заказу, 7 = 1, т,
у = 1, п , к = 1, 5 , t = 1, д .
Предположим, что dit, Гук и у - жесткие, а ^ -желательные показатели искомого плана. Тогда формально задача объемно-календарного планирования будет заключаться в определении таких величин (объем работ, который будет выполнен в 7-м подразделении по у-му заказу и к-му изделию в период планирования 0, 7 = 1, т ,у = 1, п ,
к = 1,5, t = 1, д, для которых соблюдаются следующие ограничения:
п 5
XX У й dгt, 7 = 1 т, t = 1 д
у=1 к=1
(объем работ, реализуемый по всем заказам и изделиям в 7-том подразделении в период планирования t, не должен превышать мощности этого подразделения в рассматриваемом периоде планирования),
т д
XX ху* * у у =1 п, к =15
7 = 1 t = 1
(запланированный объем работ по к-му изделию заказа у должен быть выполнен в подразделениях предприятия в течение всего периода планирования),
т
XХуы * Гун, у = 1, п, к = 1, 5, t = 1, д
7 = 1
83
6*
84
ПРИЛУЦКИЙ
(запланированный объем работ по к-му изделию заказа у в момент планирования ъ должен быть выполнен в подразделениях предприятия),
0 < у ^ Ьцкь
1 = 1, т, у = 1, п, к = 1, s, t = 1, q
(естественные ограничения на переменные, формализующие требование запрета выпуска внеплановой продукции), с учетом минимизируемых критериев
X X X у
V = 1 к =11 =1
у = 1, п,
задаваемых функциями, неотрицательными по обе стороны от нуля и в нуле принимающими нулевые значения. Эти функции определяют оценки отклонений искомых показателей от желательных показателей плана. В качестве таких функций могут быть выбраны кусочно-линейные, а свертку можно провести как линейную комбинацию этих функций. В этом случае для формальной постановки задачи необходимо, чтобы пользователь указал углы наклона линейных участков функций и коэффициенты свертки. Однако, как показал опыт внедрения [3, 4], пользователь может лишь указать границы для величин отклонений, в которых эти величины являются "отличными", "очень хорошими", "хорошими", "удовлетворительными" и др. Тогда функции отклонений /у(х), у = 1, п , должны быть кусочно-постоянными, разбивающими множество величин отклонений по каждому критерию на области "качества" отклонений. Такими свойствами обладают функции, область значений которых задается множеством целых неотрицательных чисел от 0 до р - 1 (0 - "отлично", 1 - "очень хорошо", и т.д.). При разных схемах выбора жестких и желательных показателей искомого плана, по-разному ставятся задачи объемно-календарного планирования.
К особенностям рассматриваемых задач относятся:
параметры математической модели являются многоиндексными, причем число индексов может быть различным в зависимости от рассматриваемой задачи,
ограничения математической модели представляют собой систему линейных алгебраических неравенств транспортного типа, каждое из которых получается суммированием по некоторым индексам,
критерии оптимизационных задач задаются в виде ступенчатых функций, аргументами которых также являются суммы значений варьируемых параметров по некоторым индексам.
1. Общая математическая модель. В наиболее общем виде задача объемно-календарного планирования может быть поставлена следующим образом. Заданы булевы матрицы А и В, соответственно, размерностей т х к и п х к, действитель-„ „ »
ный неотрицательный вектор с размерности т и
векторная функция ¥ (у), определенная на множестве п-мерных векторов из Я" со значениями из
{0, 1, ...,р - 1}. Введенная функция ¥(у) отображает пространство Я" на множество вершин п-мерного р-ичного куба. Требуется найти вектор
* " л > ^ >
х, удовлетворяющий ограничениям Ах < с с учетом минимизируемых критериев ¥(Вх). Полученная задача является п-критериальной задачей с линейными ограничениями и частными критериями оптимальности, структура которых зависит от вида функции ¥(у). Система ограничений
АХ < С эквивалентна совокупности линейных алгебраических неравенств транспортного типа
X ХУ < С>
1 = 1, т,
} 6 А (1)
в которой А(/) - множество индексов, соответствующих 1-й строке булевой матрицы А, 1 = 1, т, а вектор ВХ имеет координаты
X Ху, 1 = 1, п,
У 6 в (1)
где В(1) - множество индексов, отвечающих 1-й строке булевой матрицы В, 1 = 1, п . Относительно
векторной функции ¥( у) можно сделать следующие допущения:
Для любой вершины п-мерного р-ичного куба г множество векторов у, удовлетворяющих неравенству ¥(у) < г, является параллелепипедом в пространстве Як, ребра которого параллельны базисным векторам Як.
Если г = (р - 1,р - 1, ...,р - 1), то множество
векторов, определяемых ограничениям ¥( у) < г, совпадает с Як.
Выразим функцию ¥(у) следующим образом. Для каждой компоненты 1 рассмотрим совокупность вложенных друг в друга сегментов 5 , 5 с
С 5,
¥
ъ +1
ti = 0, р -2, р > 1, 1 = 1, п. Тогда
у
V 6 в (1)
= если X
у 6 В (1)
Ху 6 ^
но
X Ху Й
1 6 В (1)
£у . После проделанных преобразований задача объемно-календарного планирования формулируется так: требуется найти вектор Х, удовлетво-
ряющий ограничениям
X
У 6 А (7)
х,- < < с, 7 = 1, т , с
учетом минимизируемых критериев Г
t1 6 {0, 1, ...,р - 1}, 7 = 1, п .
у
V 6 В(7) У
2. Алгоритм решения. Сведем поставленную многокритериальную задачу к однокритериаль-ной путем задания на множестве вершин п-мерно-го р-ичного куба линейного порядка п, для которого должно выполняться: если для вершин куба
ц и V, определяемых векторами пространства Я",
справедливы условия ц * V (покомпонентно), то
ц п V. Это можно сделать, так как множество значений критериев (значений векторной функции
Г (у)) является конечным множеством. Тогда задача объемно-календарного планирования будет
1
заключаться в поиске такого к-мерного вектора х , связанного ограничением X х0 < с7,7 = 1, т , что
У 6 А (7)
для любого Х , для которого X Ху < с, 7 = = 1,
У 6 А (7)
>0 >
выполняется отношение Г( Вх ) пГ( Вх ).
совместность систем двусторонних линейных алгебраических неравенств транспортного типа.
3. Поиск оптимальной вершины многомерного многозначного куба. Для решения можно предложить следующую вычислительную схему. На первом шаге выбирается вершина куба I* = (р - 1, = р - 1, ...,р - 1) и рассчитываетсяАI* ), что равносильно проверке на совместность системы S(I * ): X х- < с, 7 = 1, т. Если система несовместна, ис-
У 6 А (7)
ходная задача не имеет решения. Если система совместна, то выбирается некоторая вершина ку-
т
Каждой вершине куба г = (гх, г2, .••, 1п) поставим в соответствие систему S( I) линейных алгебраических неравенств, всегда включающую в себя
совокупность ограничений X х- < с7,7 = 1, т , и
У 6 А (7)
в зависимости от вершины куба набор двусторон-
них ограничений
X
У 6 В(7)
Х, 6
^, 7 = 1, п. Зададим
ба I и определяется _ДI1), что эквивалентно оценке совместности системы £( I1). В зависимости от значения _Д I1), осуществляется переход к следующей вершине и т.д. Процесс вычислений должен быть конечен. Из всех просмотренных вершин куба отыскивается оптимальная вершина
>0 „ >0 1 >0 > >
I , для которойдI ) = 1 и I пI при всех I, таких,
что А I) = 1. Решением исходной задачи объемно-календарного планирования будет любой допустимый план совместной системы S( I0). В качестве порядка п, определенного на множестве вершин п-мерного р-ичного куба, выберем лексикографическое отношение, предполагающее I пI тогда и только тогда, когда существует 7, 1 < 7 < п,
>1 >2
что для координат векторов I , I выполняется:
II = I2, к = 1, 2, ..., 7 - 1, и I1 < I2. А
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.