Многоиндексные задачи объёмно-календарного планирования транспортного типа
Математическая модель объёмно-календарного планирования. Алгоритм решения задач. Поиск оптимальной вершины многомерного многозначного куба, допустимой циркуляции в транспортной сети. Проверка на совместность систем линейных неравенств транспортного типа.
| Рубрика | Экономико-математическое моделирование |
| Вид | статья |
| Язык | русский |
| Дата добавления | 28.03.2012 |
| Размер файла | 117,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
МНОГОИНДЕКСНЫЕ ЗАДАЧИ ОБЪЁМНО-КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ ТРАНСПОРТНОГО ТИПА
д.т.н., профессор М.Х. Прилуцкий
Нижегородский госуниверситет
Содержание
- Введение
- 1. Общая математическая модель объёмно-календарного планирования
- 2. Алгоритм решения задачи объёмно-календарного планирования
- 3. Задача поиска оптимальной вершины многомерного многозначного куба
- 4. Задача проверки на совместность систем линейных неравенств транспортного типа
- 5. Задача поиска допустимой циркуляции в транспортной сети
- Литература
Введение
Задача объёмно-календарного планирования математически может быть описана либо в наиболее общем виде с учетом всех возможных ограничений и связей, либо с той или иной степенью идеализации. Будем рассматривать такую задачу не в общей постановке, с учетом всех зависимостей и связей ([1-3]), а с некоторой степенью идеализации. Вместо технологических требований, которые обычно задаются сетевыми структурами, будем рассматривать этапы изготовления продукции, а вместо конкретных работ с их длительностями - объемные показатели, связанные с совокупностями работ, входящих в соответствующие этапы изготовления продукции. Содержательно задача объемно-календарного планирования формулируется следующим образом. Требуется распределить общий план предприятия в объёмных характеристиках (нормо-часы, рубли, условные тонны) по различным показателям: группам оборудования, периодам планирования, этапам изготовления, потребляемым ресурсам, видам продукции. Показатели искомого плана делятся на "жесткие", выполнение которых обязательно, и "желательные", к выполнению которых нужно стремиться. Жесткие показатели формализуются в виде ограничений, а "желательные" - в виде критериев оптимальности. Тогда задача объёмно-календарного планирования ставится как многокритериальная задача (учет "желательных" показателей) с ограничениями (учет "жестких" показателей), которые в рассматриваемой идеализации являются линейными. К особенностям рассматриваемых задач объёмно-календарного планирования относится: параметры математической модели являются многоиндексными, причем число индексов может быть различным, в зависимости от рассматриваемой задачи; ограничения математической модели представляют собой систему линейных алгебраических неравенств транспортного типа, каждое из которых получается суммированием по некоторым индексам; критерии оптимизационных задач задаются в виде ступенчатых функций, аргументами которых так же являются суммы значений варьируемых параметров по некоторым индексам.
Пусть:
s=1,…,S - номера подразделений предприятия,
j=1,…,J - номера заказов,
i=1,…, I - номера изделий,
t=1,…,T - номера периодов планирования.
К показателям искомого плана могут относиться, например, величины: At - объем работ, который может быть выполнен в t-ом периоде планирования, Bjt - объем работ, который должен быть выполнен по j-му заказу в период t, Cjit - объем работ, который должен быть выполнен по i-му изделию j-го заказа в период t, Dsj - объём работ, который может быть выполнен по заказу j в подразделении s, Ej - объём работ, который необходимо выполнить по заказу j, asjit - объём работ, оставшийся невыполненным в подразделении s по изделию i заказа j в период t, . Показатели искомого плана могут быть и другие, формулируемые с использованием введенных выше индексов. Пусть к “жестким” показателям искомого плана относятся показатели At, Cjit и Dsj, а Bjt и Ej являются “желательными" показателями. Тогда задача объемно-календарного планирования формулируется следующим образом:
требуется определить такие величины xsjit - объем работ, который будет выполнен в подразделении s по изделию i заказа j в период планирования t, для которых выполняются соотношения:
(1)
(2)
; (3)
0 xsjit asjit, ; (4)
с учетом минимизируемых критериев:
; (5)
. (6)
Здесь ограничения (1) означают, что объёмы работ по всем заказам, всем изделиям, который будет выполнен во всех подразделениях, не должен превышать общего объёма работ, который может быть выполнен в период t; ограничения (2) означают, что запланированные объемы работ по каждому заказу, каждому изделию в каждом такте планирования должны быть были выполнены; ограничения (3) означают, что в объёмы работ, запланированные к выполнению по всем заказам и всем тактам планирования, не должны превышать объёмов работ, которые могут быть выполнены по соответствующим изделиям в соответствующих подразделениях; ограничения (4) являются естественными условиями на переменные. Функции и , являются функциями оценок отклонений объемов выполняемых работ от заданных величин Bjt и Ej, - "желательных" показателей искомого плана, . В качестве таких функций в классических постановках обычно выбираются линейные или кусочно-линейные, а свертка для таких задач выбирается в виде их линейной комбинации. Однако опыт решения таких задач показал [4], что пользователь затрудняется задавать углы наклона линейных участков функций и коэффициенты свертки. Пользователю проще указать лишь границы величин отклонения, в которых они определяют понятие "отлично", "хорошо", "допустимо", "недопустимо" и др. Отсюда, такие функции должны быть кусочно-постоянными, разбивающими множество величин отклонений по каждому критерию на области "качества" отклонений. Такими функциями могут быть функции, область значений которых задается множеством целых неотрицательных чисел от 0 до p-1 (0 - "отлично", 1 - "очень хорошо", и т.д.). При разных схемах выбора "жестких" и "желательных" показателей искомого плана, по-разному ставятся задачи объёмно-календарного планирования.
К особенностям рассматриваемых задач объёмно-календарного планирования относятся:
· параметры математической модели являются многоиндексными, причем число индексов может быть различным, в зависимости от рассматриваемой задачи,
· ограничения математической модели представляют собой систему линейных алгебраических неравенств транспортного типа, каждое из которых получается суммированием по некоторым индексам,
· критерии оптимизационных задач задаются в виде ступенчатых функций, аргументами которых так же являются суммы значений варьируемых параметров по некоторым индексам.
математическая модель транспортный планирование
1. Общая математическая модель объёмно-календарного планирования
В наиболее общем виде задача объёмно-календарного планирования может быть поставлена следующим образом. Заданы булевы матрицы A и B, соответственно, размерностей mЧk и nЧk, действительный неотрицательный вектор размерности m и векторная функция, определенная на множестве n-мерных векторов из со значениями из {0,1,…,p-1}. Введенная функция отображает пространство на множество вершин n-мерного p-ичного куба. Требуется найти вектор, удовлетворяющий ограничениям A? с учетом минимизируемых критериев . Полученная задача является n-критериальной задачей с линейными ограничениями и частными критериями оптимальности, вид которых зависит от вида функции. Система ограничений A? эквивалентна системе линейных алгебраических неравенств транспортного типа , , где R (i) - множество индексов, соответствующих i-ой строке булевой матрицы А, , а вектор имеет координаты , , где G (i) - множество индексов, соответствующих i-ой строке булевой матрицы В, . Относительно векторной функции можно сделать следующие допущения:
· Для любой вершины n-мерного p-ичного куба , множество векторов , удовлетворяющих неравенству ?, является параллелепипедом в пространстве , ребра которого параллельны базисным векторам .
· Если = (p-1,p-1,…,p-1), то множество векторов, удовлетворяющих ограничениям ?, совпадает с .
Определим функцию следующим образом. Для каждой компоненты i рассмотрим совокупность вложенных друг в друга сегментов , , , p?1, . Тогда , если но . После проделанных преобразований задача объёмно-календарного планирования ставится следующим образом: требуется найти вектор, удовлетворяющий ограничениям , , с учетом минимизируемых критериев , , .
2. Алгоритм решения задачи объёмно-календарного планирования
Решение поставленной многокритериальной задачи будем осуществлять сведением её к однокритериальной, путем задания на множестве вершин n-мерного p-ичного куба некоторого линейного порядка , для которого должно выполняться: если для вершин куба и , задаваемых векторами пространства , выполняются условия (покомпонентно), то . Это можно сделать, так как множество значений критериев (значения векторной функции ) является конечным множеством. Тогда задача объёмно-календарного планирования будет заключаться в определении такого k-мерного вектора , для которого , , и для любого , для которого, , выполняется отношение .
Каждой вершине куба поставим в соответствие систему линейных алгебраических неравенств, всегда включающую в себя совокупность ограничений , , и, в зависимости от вершины куба, совокупность двусторонних ограничений . Зададим на множестве вершин куба двузначную функцию , принимающую значение 1, если система совместна и 0 в противном случае. Для функции выполняется: если для вершин куба и имеет место (покомпонентно), то , отсюда функция является монотонной.
Таким образом, для решения задачи объёмно-календарного планирования необходимо уметь решать две задачи: задачу 1 - поиска оптимальной вершины многомерного многозначного куба и задачу 2 - проверки на совместность систем двусторонних линейных алгебраических неравенств транспортного типа.
3. Задача поиска оптимальной вершины многомерного многозначного куба
Для решения задачи 1 можно предложить следующую вычислительную схему. На первом шаге выбирается вершина куба и вычисляется , что равносильно проверке на совместность системы : ,. Если система несовместна, то исходная задача не имеет решения. Если система совместна, то выбирается некоторая вершина куба и вычисляется , что равносильно проверке на совместность системы . В зависимости от значения , выбирается следующая вершина и т.д. Процесс вычислений должен быть конечен. Из всех просмотренных вершин куба выбирается оптимальная вершина, т.е. такая вершина , для которой и для всех , для которых . Решением исходной задачи объёмно-календарного планирования будет любой допустимый план совместной системы . В качестве порядка , определенного на множестве вершин n-мерного p-ичного куба, выберем лексикографическое отношение, т.е. тогда и только тогда, когда существует такое i, 1?i?n, что для координат векторов выполняется: , k=1,2,…, i-1, и . Алгоритм поиска оптимальной вершины куба при лексикографическом порядке для монотонной функции состоит из n шагов. На первом шаге среди вершин вида (,p-1,…,p-1) находится такое значение , , для которого и ?, для всех тех , для которых . На втором шаге среди узлов вида (,,p-1,…,p-1) аналогично находится вторая координата оптимальной вершины. На n-ом шаге находим искомую оптимальную вершину куба. Общее число вычислений функции имеет порядок .
Замечание
В случае, если размерность куба больше, чем количество вложенных сегментов, можно модифицировать описанный выше алгоритм, осуществляя двоичный поиск не по значениям координат, а по координатам куба. Тогда оценка числа вычислений функции будет иметь порядок .
4. Задача проверки на совместность систем линейных неравенств транспортного типа
Для решения задачи 2 - проверки на совместность систем линейных алгебраических неравенств , в общем случае можно использовать классические вычислительные методы линейной алгебры ([5]), однако, то, что ограничения задачи являются транспортного типа, позволяет для их решения предложить специальные алгоритмы.
В общем случае может быть представлена в виде системы линейных алгебраических неравенств транспортного типа с двусторонними ограничениями , над k-мерным евклидовым пространством . Здесь q=m+n; =0 и =, если ; и - границы сегмента с номером i, если ; - множество индексов, по которым осуществляется суммирование i-ого ограничения, . Если - произвольный k-мерный вектор,. удовлетворяющий всем q ограничениям системы, то задача решена. Пусть s - первое по порядку ограничение, условия которого нарушены. Построим вектор по следующему правилу:
и перейдем к следующему (s+1) - ому ограничению. Так для всех ограничений. Если система совместна, то последовательность векторов , найденных по выше описанной схеме, при сходится к допустимому решению системы. Предложенный алгоритм является обобщением релаксационного метода ортогональных проекций Агмона-Моцкина ([6,7]) на случай двусторонних систем линейных алгебраических неравенств транспортного типа.
Замечание.
Предложенный алгоритм является итерационным, поэтому для его реализации необходимо задавать два параметра - число шагов работы алгоритма и точность решения задачи. Если за указанное число шагов с заданной точностью допустимое решение не будет найдено, то делается предположение о несовместности исходной системы.
5. Задача поиска допустимой циркуляции в транспортной сети
Так как в рассматриваемых задачах объёмно-календарного планирования варьируемые параметры являются многоиндексными, а ограничения представляют собой систему линейных алгебраических неравенств транспортного типа, каждое из которых получается суммированием по некоторым индексам, то для удобства изложения материала можно воспользоваться формализацией, предложенной в [8] при постановке многоиндексных транспортных задач линейного программирования.
Пусть ; - некоторый параметр (индекс), , ; . Обозначим через = - набор значений индексов, , . Каждому поставим в соответствие действительное число , . Совокупность таких чисел для всех возможных значений индексов обозначим через . Пусть , тогда через FN (s) = будем обозначать набор . Пусть , . Тогда множество допустимых решений задачи объёмно-календарного планирования может быть описано следующим образом: , где М - заданное множество, и задача 2 будет заключаться в определении, пусто ли множество D (M), . Будем предполагать, что и - целые числа, . Тогда будем говорить, что система ограничений, определяющая множество D (M), сводится к задаче L - поиска допустимой циркуляции в транспортной сети ([9]), если некоторое подмножество компонент допустимого решения задачи L образует допустимое решение системы ограничений, определяющей множество D (M), и система ограничений не совместна, если не имеет допустимого решения задача L. Так как система ограничений, определяющая D (M) зависит от множества М, , будем решать задачу поиска таких множеств M, при которых система ограничений, определяющая множество D (M), сводится к задаче L. Оказывается ([10]), что для того, чтобы система ограничений, определяющая множество D (M), сводилась к задаче L достаточно, чтобы существовало такое разбиение , множества M, для которого и
Таким образом, если для множества М существует соответствующее разбиение, то может быть построена транспортная сеть с двусторонними пропускными способностями дуг, поиск допустимой циркуляции в которой может быть осуществлен путем построения соответствующей транспортной сети (с односторонними пропускными способностями дуг) и решения для нее задачи поиска максимального потока, например, модифицированным алгоритмом расстановки пометок ([11]). Если допустимый поток в сети с двусторонними пропускными способностями существует, то соответствующая система ограничений D (M) совместна. Так как вычислительная сложность модифицированного алгоритма расстановки пометок имеет порядок O (|V|3), где V - множество узлов транспортной сети, то вопрос о совместности систем ограничений типа D (M) решается за порядка O (|V|3) арифметических операций.
Замечание.
Для задачи объёмно-календарного планирования, рассмотренной во введении, c учетом критериев оптимальности, M={{s,j, i},{s},{i,t},{s, i},{s, i,t},,} и существует разбиение M1={{s,j, i},{s, i},{s},}, M2={{s, i,t},{i,t}}, для которого выполняются условия сводимости. Тем самым для проверки совместности систем типа , соответствующих рассматриваемой задаче, можно строить транспортные сети с двусторонними пропускными способностями и решать задачи поиска допустимых потоков в построенных сетях. На последнем шаге работы алгоритма требуется построить максимальный поток, который и определит оптимальное решение исходной задачи.
Литература
1. Батищев Д.И., Гудман Э.Д., Норенков И.П., Прилуцкий М.Х. Метод декомпозиций для решения комбинаторных задач упорядочения и распределения ресурсов // Информационные технологии. 1997, N1.
2. Батищев Д.И., Гудман Э.Д., Норенков И.П., Прилуцкий М.Х. Метод комбинирования эвристик для решения комбинаторных задач упорядочения и распределения ресурсов. // Информационные технологии. 1997, N2.
3. Прилуцкий М.Х., Кумагина Е.А. Задача упорядочения работ как задача о назначениях // Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. 1999, вып.21.
4. Прилуцкий М.Х., Власов С.Е. Оптимальное распределение ресурсов в задачах календарного и объемно-календарного планирования // Труды Нижегородского государственного технического университета. Системы обработки информации и управления. 2004, вып.11.
5. Черников С.Н. Линейные неравенства. Москва. Наука. 1968.
6. Motzkin T. S., Schoenberg I. J. The relaxation method for linear inequalities // Caned. J. Moth. 1954. V.6. №3.
7. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах // Автоматика и телемеханика. 1996, №2.
8. Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. Москва. Радио и связь, 1982.
9. Форд Л., Фалкерсон Д. Потоки в сетях. Москва. МИР, 1966.
10. Прилуцкий М.Х., Афраймович Л.Г. Условия совместности многоиндексных систем транспортного типа. "Электронный журнал "Исследовано в России", 70, стр.762-767, 2005г. http://zhurnal. ape. relarn.ru/2005/070. pdf
11. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Москва. Мир, 1985.
Размещено на Allbest.ru
Подобные документы
Изучение порядка постановки задач и общая характеристика методов решения задач по календарному планированию: модель с дефицитом и без дефицита. Анализ решения задачи календарного планирования с помощью транспортной модели линейного программирования.
курсовая работа [154,0 K], добавлен 13.01.2012Описание задачи линейного целочисленного программирования. Общий алгоритм решения задач с помощью метода границ и ветвей, его сущность и применение для задач календарного планирования. Пример использования метода при решении задачи трех станков.
курсовая работа [728,8 K], добавлен 11.05.2011Решение задач линейного программирования на примере ПО "Гомсельмаш". Алгоритм и экономико-математические методы решения транспортной задачи. Разработка наиболее рациональных путей, способов транспортирования товаров, оптимальное планирование грузопотоков.
курсовая работа [52,3 K], добавлен 01.06.2014Основные подходы и способы решения транспортной задачи, ее постановка и методы нахождения первоначального опорного решения. Математическая модель транспортной задачи и алгоритм ее решения методом потенциалов. Составление опорного плана перевозок.
курсовая работа [251,0 K], добавлен 03.07.2012Общие свойства бильярдных систем, методы их исследования. Математическая модель бильярда, решение математической проблемы бильярда, или проблемы траектории. Типичные задачи на переливание, условие разрешимости задач, алгоритм и примеры их решения.
реферат [687,4 K], добавлен 07.09.2009Алгоритм решения оптимизационной задачи линейного программирования (ЗЛП) – планирования производства симплекс методом и при помощи средства "Поиск решения" в Microsoft Excel. Описание работы, графический интерфейс и схема программы для решения ЗЛП.
дипломная работа [2,3 M], добавлен 19.09.2010Методики решения аналитической задачи оценки функционирования жилищно-коммунального хозяйства региона. Математическая модель, метод и алгоритм решения задачи планирования вывоза бытовых отходов на заводы по их переработке. Ввод дополнительной информации.
автореферат [755,5 K], добавлен 23.03.2009Особенности решения задач линейного программирования симплекс-методом. Управляемые параметры, ограничения. Изучение метода потенциалов в процессе решения транспортной задачи. Создание концептуальной модели. Понятие стратификации, детализации, локализации.
лабораторная работа [869,0 K], добавлен 17.02.2012Построение модели планирования производства. Использование инструментального средства "Поиск решения" для решения задачи линейного программирования. Решение оптимальной задачи, с использованием методов математического анализа и возможностей MathCad.
лабораторная работа [517,1 K], добавлен 05.02.2014Математическая постановка и алгоритм решения транспортной задачи. Сбалансированность и опорное решение задачи. Методы потенциалов и северо-западного угла. Блок-схема. Формы входной и выходной информации. Инструкция для пользователя и программиста.
курсовая работа [113,8 K], добавлен 10.11.2008
