При решении задач планирования развития отраслей и регионов, проектирования сложных объектов важное место занимают проблемы производственно-транспортного типа. К задачам такого рода относятся, например, задачи размещения производственных предприятий, складов, технических средств с учетом капитальных и эксплуатационных затрат, транспортных издержек. Близкие по типу задачи возникают при проектировании коммуникационных сетей дорог, продуктопроводов, теплои электроснабжения, связи и т. д.
В настоящее время накоплен значительный опыт в теоретическом исследовании этих задач, в разработке алгоритмов их решения, а также в их практическом использовании.
Задачи производственно-транспортного относятся к трудно решаемым задачам математического программирования ввиду их многоэкстремальности, наличия дискретных переменных и большой размерности, встречающихся на практике задач. По этим причинам в настоящее время эффективные алгоритмы решения разрабатываются с учетом специфики того или иного класса задач размещения, определяемой видом целевой функции и системой ограничений. Расширение области применения моделей производственно-транспортного типа происходит в результате разработки более эффективных алгоритмов решения уже изученных классов задач, совершенствования средств вычислительной техники, что позволяет увеличить размерность решаемых на практике задач и, при усложнении постановки, разработки новых или совершенствования существующих методов решения получающихся классов задач.
Один из таких классов образуют задачи размещения с типовыми мощностями. Модели размещения с типовыми мощностями описывают ситуацию, когда в каждом пункте могут размещаться источники мощности нескольких различных типоисполнений, отличающихся различными затратами на их создание и эксплуатацию в зависимости от фактической загрузки источника. При этом в каждом пункте может допускаться размещение нескольких источников мощностей различных типоисполнений. Требуется определить количество и места размещения источников мощностей различного, объёмы производства и перевод продукции с тем, чтобы суммарные производственно-транспортные затраты были минимальны при соблюдении балансовых ограничений на производство и потребление. Такие модели отражают существующую практику широкого применения типовых проектных решений.
Другим недостаточно изученным и часто встречающимся на практике классом задач производственно-транспортного планирования являются задачи размещения с неделимыми потребителями, которые характеризуются тем, что каждый потребитель может прикрепляться только к одному пункту производства.
Существующие алгоритмы, разработанные для решения известных классов задач размещения, как правило, нельзя непосредственно использовать для решения задач размещения с типовыми мощностями или неделимыми потребителями.
Поэтому целью работы, которая представляется актуальной и практически значимой, является изучение задач размещения с типовыми мощностями и задач с неделимыми потребителями, разработка точных и приближенных алгоритмов, позволяющих решать практические задачи.
Научная новизна и теоретическая значимость диссертации состоит в том, что в ней
— даны постановки классов задач размещения с типовыми мощностями и с неделимыми потребителями для неубывающих нелинейных функций производственных затрат, изучены свойства этих задач. Проведено исследование, показывающее, что задачи с типовыми мощностями могут быть сведены к задаче размещения с неубывающими функциями производственных затрат. Для важных частных случаев линейных и постоянных эксплуатационных затрат изучено поведение и разработаны алгоритмы формирования соответствующих функций производственных затрат;
— показано, что задача размещения с типовыми мощностями и линейными функциями эксплуатационных затрат может быть сформулирована как многоиндексная задача размещения, которая, в свою очередь, сводится к задаче условной минимизации супермодулярной функции на прямом произведении булевых решеток. Изучены поведение и свойства супермодулярных функций на абстрактных булевых решетках. Рассмотрена задача условной минимизации супермодулярной функции на булевой решетке, т. е. задача минимизации при наличии дополнительных ограничений. Показано, что если ограничения задаются изотонными вещественными функциями, определенными на решетке, то для ее решения применим метод последовательных расчетов с некоторыми дополнительными правилами отбраковки. Сформулирован алгоритм последовательных расчетов для задач такого типа;
— разработан комбинаторный алгоритм решения задач с неделимыми потребителями, сочетающий в себе идеи аппроксимационно-комбинаторного метода и метода ветвей и границ. Аппроксимирующая задача при этом используется для формирования дополнительных правил отбраковки неперспективных вариантов и оценки точности в случае приближенного решения. Приведен большой набор нижних оценок целевой функции, используемых в правилах отбраковки. Разработаны варианты алгоритма, ориентированные на получение приближенных решений. Рассмотрены вопросы численной реализации алгоритмовуказаны практические задачи, решаемые с помощью разработанных алгоритмов. Дано подробное описание решения задачи формирования оптимальных схем электроснабжения.
Практическая значимость диссертации заключается в том, что предложенные в ней методы и алгоритмы решения задач размещения с типовыми мощностями и неделимыми потребителями разработаны до уровня вычислительных схем и программных реализаций и могут быть использованы для решения прикладных задач.
Работа состоит из введения, четырех разделов и заключения.
В первом разделе даются постановки задач размещения с типовыми мощностями и различными системами ограничений, устанавливается связь между рассматриваемыми и некоторыми из известных типов задач размещения. Здесь же приводится краткий обзор наиболее изученных классов задач размещения и методов их решения. Для случая эксплуатационных затрат, линейно зависящих от объемов производства изучены свойства и разработаны алгоритмы формирования функций производственных затрат, которые являются кусочно-линейными неубывающими функциями.
Во втором разделе изучается задача размещения с типовыми мощностями, линейными функциями эксплуатационных затрат и непрерывной транспортной составляющей. Показано, что она сводится к многоиндексной задаче размещения, определяемой как задача минимизации супермодулярной функции на прямом произведении булевых решеток. Изучены поведение и свойства супермодулярных функций на абстрактных булевых решетках. Сформулирован и обоснован алгоритм последовательных расчетов для минимизации супермодулярных функций на конечных булевых решетках общего вида. Рассмотрена задача условной минимизации супермодулярной функции на булевой решетке, т. е. задача минимизации при наличии дополнительных ограничений. Обоснована применимость метода последовательных расчетов с дополнительными правилами отбраковки для решения задач условной минимизации супермодулярных функций на булевых решетках в случае, когда ограничения задаются изотонными вещественными функциями. Показано, что к таким задачам сводятся задачи размещения с типовыми мощностями и некоторыми дополнительными ограничениями, например ограничениями на суммарную мощность предприятий, размещенных в данном пункте или на их количество.
В третьем разделе рассматривается задача размещения с произвольными неубывающими функциями производственных затрат и неделимыми потребителями. Раздел состоит из трёх подразделов. В первом описывается комбинаторный алгоритм решения задачи, алгоритм решения, сочетающий в себе идеи аппроксимационно-комбинаторного метода и метода ветвей и границ. Исходная задача формулируется как задача минимизации целевой функции, заданной на конечном множестве прикреплений потребителей к пунктам производства и строится аппроксимирующая задача, для которой имеется эффективный алгоритм отыскания множества решений, отличающихся от оптимального не более чем на заданную величину Я>0 — множества-близких решений. Аппроксимирующая задача при этом используется для формирования дополнительных правил отбраковки неперспективных вариантов и оценки точности в случае получения приближенного решения. Формулируются и обосновываются правила отбраковки, используемые в алгоритме. Во втором подразделе исследуются свойства нижних оценок целевой функции на подмножествах решений и строятся некоторые типы таких оценок. Нижние оценки целевой функции используются для отбраковки тех из множества-близких решений, которые заведомо не улучшают уже достигнутого временно-оптимального (рекордного) значения. Приведен большой набор таких оценок. В третьем описывается ещё один алгоритм решения задач с неделимыми потребителями, применяемый для случая кусочно-линейных функций производственных затрат. Этот алгоритм также основан на идее аппроксимационно-комбинаторного метода и отличается от алгоритма раздела 3.1 типом аппроксимирующей задачи. Для его реализации строится сепарабельная нижняя оценка транспортной составляющей и аппроксимирующая задача рюкзачного типа, множество /¿—близких решений которой определяется модифицированным алгоритмом динамического программирования.
Четвертая раздел посвящен рассмотрению различных аспектов численной реализации алгоритма решения задачи размещения с неделимыми потребителями. Здесь рассматривается возможность получения нижней оценки разности значений целевых функций исходной и аппроксимирующей задач и использования этой оценки для уточнения аппроксимирующей задачи, что позволяет уменьшить необходимый для решения исходной задачи объём множества Я8 близких вариантов. Описываются различные модификации исходного алгоритма раздела 3.1, ориентированные на получение приближенных решений с оценками их погрешности. Рассматриваются некоторые особенности вычислительных процедур расчета параметров аппроксимирующей и оценочных функций, прикладные задачи формирования оптимальных схем электроснабжения. Описывается общая модель задачи формирования схем электроснабжения на различных уровнях, из которой конкретные задачи получаются отбрасыванием тех или иных групп ограничений. Показывается, что эти задачи являются задачами с типовыми мощностями и неделимыми потребителями и сводятся к задаче, рассмотренной в разделе 3. Описывается алгоритм формирования функций производственных затрат, приводятся некоторые результаты вычислительных экспериментов. 9
ЗАКЛЮЧЕНИЕ
.
В результате выполненных исследований получены следующие основные результаты.
1. Рассмотрена общая модель производственно-транспортного типа — задача размещения с типовыми производственными мощностями. Показано, что в рамках этой модели могут формулироваться как хорошо известные задачи размещения, так и ряд новых, изучению свойств и методов решения которых посвящена настоящая работа. Рассмотрены два подхода к решению задач с типовыми производственными мощностями и линейными функциями эксплуатационных затрат.
Первый из них основан на сведении задачи с типовыми мощностями к задаче размещения с нелинейными неубывающими функциями производственных затрат. Изучены свойства и разработаны алгоритмы формирования функцийпроизводственных затрат для случая, когда эксплуатационные затраты постоянны или линейно зависят от объемов производства. Показано, что в этом случае функции производственных затрат являются кусочно-линейными (кусочно-постоянными) и дата решения ряда задач размещения с такими функциями применимы разработанные метода: метод последовательных расчётов, метод построения последовательности планов и т. д.
При втором подходе задача с типовыми мощностями формулируется как многоиндексная задача размещения, которая сводится к минимизации супермодулярной функции на декартовом произведении булевых решеток, для решения которой также применим алгоритм последовательных расчётов, сформулированный с учетом её многоиндексности. Показано, что второй подход является более эффективным, так как приводит к задаче, определённой на множестве, содержащем меньшее по сравнению с первым, количестве элементов.
2. Изучены поведение и свойства супермодулярных функций на абстрактных булевых решетках. Сформулирован алгоритм последовательных расчетов для минимизации супермодулярных функций на конечных булевых решетках общего вида, составными частями которого являются схема перебора, последовательно формирующая все элементы решетки и согласованные с ней правила отбраковки. Введено понятие финального правила отбраковки, согласующегося с описанной схемой и показано, что правила отбраковки метода последовательных расчетов являются финальными.
3. Рассмотрена задача условной минимизации супермодулярной функции на булевой решетке, т. е. задача минимизации при наличии дополнительных ограничений. Показано, что если ограничения задаются изотонными вещественными функциями, определенными на решетке, то область определения задачи минимизации является М-замкнутым множеством. Изучены свойства М-замкнутых множеств, позволяющие обосновать применимость метода последовательных расчетов для задач условной минимизации супермодулярных функций на булевых решетках. Сформулировано дополнительное правило отбраковки, согласованное со схемой перебора алгоритма последовательных расчетов. Отдельно рассмотрен класс задач условной минимизации, в которых ограничения задаются с помощью изотонных модулярных функций. Показано, что при решении прикладных задач, связанных с размещением предприятий, с помощью этого класса задач удается описать целый ряд практически значимых ситуаций.
4. Дана общая постановка нелинейной производственно-транспортной задачи с неделимыми потребителями. Сформулирован ряд правил отбраковки и алгоритм решения, сочетающий в себе идеи аппроксимационно-комбинаторно-ш метода и метода ветвей и границ. Аппроксимирующая задача при этом используется для формирования дополнительных правил отбраковки неперспективных вариантов и оценки точности в случае приближенного решения. Приведен большой набор нижних оценок целевой функции (оценочных функций) для возможных продолжений данного частичного плана.
5. Для задач с неделимыми потребителями и кусочно-линейными функциями производственных затрат рассмотрен еще один подход к решению, позволяющий использовать технику динамического программирования в рамках аппроксимационно-комбинаторного метода, для чего строится аппроксимирующая задача рюкзачного типа. Построение такой задачи связано с построением сепарабельной аппроксимации целевой функции. Показано, что последняя также сводится к задаче рюкзачного типа, эффективно решаемой методом динамического программирования.
6. Разработана система алгоритмов для точного и приближенного решения задач размещения с неделимыми потребителями. Каждый алгоритм определяется соответствующим набором параметров, причем система построена таким образом, что предыдущий алгоритм является частным случаем последующих. Для каждого из алгоритмов обоснованы оценки погрешности получаемых решений. На основе вычислительного опыта предложена двухэтапная стратегия решения задач большой размерности.
7. Разработанные методы применены для решения прикладной задачи формирования оптимальных схем электроснабжения. Показано, что не смотря на внешние различия, эта задача может быть отнесена к классу задач размещения с типовыми мощностями и неделимыми потребителями, а различия носят такой характер, что могут быть учтены при формировании соответствующих функций производственных затрат.
Приведены некоторые результаты вычислительных экспериментов.