Алгоритмы решения задач размещения предприятий с типовыми производственными мощностями тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

1. ЗАДАЧИ РАЗМЕЩЕНИЯ С ТИПОВЫМИ ПРОИЗВОДСТВЕННЫМИ МОЩНОСТЯМИ.

1.1. Постановки производственно-транспортных задач при условиях использования типовых производственных мощностей и неделимости потребителей.

1.2. Основные положения применяемых методов.

1.3. Свойства функций производственных затрат для некоторых задач размещения с типовыми мощностями.

2. МИНИМИЗАЦИЯ СУПЕРМОДУЛЯРНЫХ ФУНКЦИЙ НА БУЛЕВЫХ РЕШЕТКАХ И РЕШЕНИЕ МНОГОИНДЕКСНЫХ ЗАДАЧ РАЗМЕЩЕНИЯ.

2.1. Основные определения и свойства супермодулярных функций на булевых решетках.

2.2. Алгоритм последовательных расчетов для конечных булевых решеток.

2.3. Условная минимизация на булевых решетках.

2.4. Многоиндексные задачи размещения и задачи с типовыми мощностями.

3. АЛГОРИТМЫ РЕШЕНИЯ ПРОИЗВОДСТВЕННО-ТРАНСПОРТНЫХ ЗАДАЧ ПРИ УСЛОВИИ НЕДЕЛИМОСТИ ПОТРЕБИТЕЛЕЙ.

3.1. Правила отбраковки и алгоритмы решения.

3.2. Оценочные функции.

3.3. Использование алгоритмов динамического программирования при решении задачи.

4. ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ И ПРИКЛАДНЫЕ ЗАДАЧИ РАЗМЕЩЕНИЯ С НЕДЕЛИМЫМИ ПОТРЕБИТЕЛЯМИ.

4.1. Уменьшение объема перебора, приближенные алгоритмы и стратегии решения.

4.2. Особенности численной реализации.

4.3. Задачи формирования оптимальных схем электроснабжения.

При решении задач планирования развития отраслей и регионов, проектирования сложных объектов важное место занимают проблемы производственно-транспортного типа. К задачам такого рода относятся, например, задачи размещения производственных предприятий, складов, технических средств с учетом капитальных и эксплуатационных затрат, транспортных издержек. Близкие по типу задачи возникают при проектировании коммуникационных сетей дорог, продуктопроводов, тепло- и электроснабжения, связи и т.д.

В настоящее время накоплен значительный опыт в теоретическом исследовании этих задач, в разработке алгоритмов их решения, а также в их практическом использовании.

Задачи производственно-транспортного относятся к трудно решаемым задачам математического программирования ввиду их многоэкстремальности, наличия дискретных переменных и большой размерности, встречающихся на практике задач. По этим причинам в настоящее время эффективные алгоритмы решения разрабатываются с учетом специфики того или иного класса задач размещения, определяемой видом целевой функции и системой ограничений. Расширение области применения моделей производственно-транспортного типа происходит в результате разработки более эффективных алгоритмов решения уже изученных классов задач, совершенствования средств вычислительной техники, что позволяет увеличить размерность решаемых на практике задач и, при усложнении постановки, разработки новых или совершенствования существующих методов решения получающихся классов задач.

Один из таких классов образуют задачи размещения с типовыми мощностями. Модели размещения с типовыми мощностями описывают ситуацию, когда в каждом пункте могут размещаться источники мощности нескольких различных типоисполнений, отличающихся различными затратами на их создание и эксплуатацию в зависимости от фактической загрузки источника. При этом в каждом пункте может допускаться размещение нескольких источников мощностей различных типоисполнений. Требуется определить количество и места размещения источников мощностей различного, объёмы производства и перевод продукции с тем, чтобы суммарные производственно-транспортные затраты были минимальны при соблюдении балансовых ограничений на производство и потребление. Такие модели отражают существующую практику широкого применения типовых проектных решений.

Другим недостаточно изученным и часто встречающимся на практике классом задач производственно-транспортного планирования являются задачи размещения с неделимыми потребителями, которые характеризуются тем, что каждый потребитель может прикрепляться только к одному пункту производства.

Существующие алгоритмы, разработанные для решения известных классов задач размещения, как правило, нельзя непосредственно использовать для решения задач размещения с типовыми мощностями или неделимыми потребителями.

Поэтому целью работы, которая представляется актуальной и практически значимой, является изучение задач размещения с типовыми мощностями и задач с неделимыми потребителями, разработка точных и приближенных алгоритмов, позволяющих решать практические задачи.

Научная новизна и теоретическая значимость диссертации состоит в том, что в ней

- даны постановки классов задач размещения с типовыми мощностями и с неделимыми потребителями для неубывающих нелинейных функций производственных затрат, изучены свойства этих задач. Проведено исследование, показывающее, что задачи с типовыми мощностями могут быть сведены к задаче размещения с неубывающими функциями производственных затрат. Для важных частных случаев линейных и постоянных эксплуатационных затрат изучено поведение и разработаны алгоритмы формирования соответствующих функций производственных затрат;

- показано, что задача размещения с типовыми мощностями и линейными функциями эксплуатационных затрат может быть сформулирована как многоиндексная задача размещения, которая, в свою очередь, сводится к задаче условной минимизации супермодулярной функции на прямом произведении булевых решеток. Изучены поведение и свойства супермодулярных функций на абстрактных булевых решетках. Рассмотрена задача условной минимизации супермодулярной функции на булевой решетке, т.е. задача минимизации при наличии дополнительных ограничений. Показано, что если ограничения задаются изотонными вещественными функциями, определенными на решетке, то для ее решения применим метод последовательных расчетов с некоторыми дополнительными правилами отбраковки. Сформулирован алгоритм последовательных расчетов для задач такого типа;

- разработан комбинаторный алгоритм решения задач с неделимыми потребителями, сочетающий в себе идеи аппроксимационно-комбинаторного метода и метода ветвей и границ. Аппроксимирующая задача при этом используется для формирования дополнительных правил отбраковки неперспективных вариантов и оценки точности в случае приближенного решения. Приведен большой набор нижних оценок целевой функции, используемых в правилах отбраковки. Разработаны варианты алгоритма, ориентированные на получение приближенных решений. Рассмотрены вопросы численной реализации алгоритмов; указаны практические задачи, решаемые с помощью разработанных алгоритмов. Дано подробное описание решения задачи формирования оптимальных схем электроснабжения.

Практическая значимость диссертации заключается в том, что предложенные в ней методы и алгоритмы решения задач размещения с типовыми мощностями и неделимыми потребителями разработаны до уровня вычислительных схем и программных реализаций и могут быть использованы для решения прикладных задач.

Работа состоит из введения, четырех разделов и заключения.

В первом разделе даются постановки задач размещения с типовыми мощностями и различными системами ограничений, устанавливается связь между рассматриваемыми и некоторыми из известных типов задач размещения. Здесь же приводится краткий обзор наиболее изученных классов задач размещения и методов их решения. Для случая эксплуатационных затрат, линейно зависящих от объемов производства изучены свойства и разработаны алгоритмы формирования функций производственных затрат, которые являются кусочно-линейными неубывающими функциями.

Во втором разделе изучается задача размещения с типовыми мощностями, линейными функциями эксплуатационных затрат и непрерывной транспортной составляющей. Показано, что она сводится к многоиндексной задаче размещения, определяемой как задача минимизации супермодулярной функции на прямом произведении булевых решеток. Изучены поведение и свойства супермодулярных функций на абстрактных булевых решетках. Сформулирован и обоснован алгоритм последовательных расчетов для минимизации супермодулярных функций на конечных булевых решетках общего вида. Рассмотрена задача условной минимизации супермодулярной функции на булевой решетке, т.е. задача минимизации при наличии дополнительных ограничений. Обоснована применимость метода последовательных расчетов с дополнительными правилами отбраковки для решения задач условной минимизации супермодулярных функций на булевых решетках в случае, когда ограничения задаются изотонными вещественными функциями. Показано, что к таким задачам сводятся задачи размещения с типовыми мощностями и некоторыми дополнительными ограничениями, например ограничениями на суммарную мощность предприятий, размещенных в данном пункте или на их количество.

В третьем разделе рассматривается задача размещения с произвольными неубывающими функциями производственных затрат и неделимыми потребителями. Раздел состоит из трёх подразделов. В первом описывается комбинаторный алгоритм решения задачи, алгоритм решения, сочетающий в себе идеи аппроксимационно-комбинаторного метода и метода ветвей и границ. Исходная задача формулируется как задача минимизации целевой функции, заданной на конечном множестве прикреплений потребителей к пунктам производства и строится аппроксимирующая задача, для которой имеется эффективный алгоритм отыскания множества решений, отличающихся от оптимального не более чем на заданную величину Я>0 - множества ^-близких решений. Аппроксимирующая задача при этом используется для формирования дополнительных правил отбраковки неперспективных вариантов и оценки точности в случае получения приближенного решения. Формулируются и обосновываются правила отбраковки, используемые в алгоритме. Во втором подразделе исследуются свойства нижних оценок целевой функции на подмножествах решений и строятся некоторые типы таких оценок. Нижние оценки целевой функции используются для отбраковки тех из множества ^-близких решений, которые заведомо не улучшают уже достигнутого временно-оптимального (рекордного) значения. Приведен большой набор таких оценок. В третьем описывается ещё один алгоритм решения задач с неделимыми потребителями, применяемый для случая кусочно-линейных функций производственных затрат. Этот алгоритм также основан на идее аппроксимационно-комбинаторного метода и отличается от алгоритма раздела 3.1 типом аппроксимирующей задачи. Для его реализации строится сепарабельная нижняя оценка транспортной составляющей и аппроксимирующая задача рюкзачного типа, множество /¿-близких решений которой определяется модифицированным алгоритмом динамического программирования.

Четвертая раздел посвящен рассмотрению различных аспектов численной реализации алгоритма решения задачи размещения с неделимыми потребителями. Здесь рассматривается возможность получения нижней оценки разности значений целевых функций исходной и аппроксимирующей задач и использования этой оценки для уточнения аппроксимирующей задачи, что позволяет уменьшить необходимый для решения исходной задачи объём множества Я8 близких вариантов. Описываются различные модификации исходного алгоритма раздела 3.1, ориентированные на получение приближенных решений с оценками их погрешности. Рассматриваются некоторые особенности вычислительных процедур расчета параметров аппроксимирующей и оценочных функций, прикладные задачи формирования оптимальных схем электроснабжения. Описывается общая модель задачи формирования схем электроснабжения на различных уровнях, из которой конкретные задачи получаются отбрасыванием тех или иных групп ограничений. Показывается, что эти задачи являются задачами с типовыми мощностями и неделимыми потребителями и сводятся к задаче, рассмотренной в разделе 3. Описывается алгоритм формирования функций производственных затрат, приводятся некоторые результаты вычислительных экспериментов. 9

ЗАКЛЮЧЕНИЕ.

В результате выполненных исследований получены следующие основные результаты.

1. Рассмотрена общая модель производственно-транспортного типа - задача размещения с типовыми производственными мощностями. Показано, что в рамках этой модели могут формулироваться как хорошо известные задачи размещения, так и ряд новых, изучению свойств и методов решения которых посвящена настоящая работа. Рассмотрены два подхода к решению задач с типовыми производственными мощностями и линейными функциями эксплуатационных затрат.

Первый из них основан на сведении задачи с типовыми мощностями к задаче размещения с нелинейными неубывающими функциями производственных затрат. Изучены свойства и разработаны алгоритмы формирования функций- производственных затрат для случая, когда эксплуатационные затраты постоянны или линейно зависят от объемов производства. Показано, что в этом случае функции производственных затрат являются кусочно-линейными (кусочно-постоянными) и дата решения ряда задач размещения с такими функциями применимы разработанные метода: метод последовательных расчётов, метод построения последовательности планов и т.д.

При втором подходе задача с типовыми мощностями формулируется как многоиндексная задача размещения, которая сводится к минимизации супермодулярной функции на декартовом произведении булевых решеток, для решения которой также применим алгоритм последовательных расчётов, сформулированный с учетом её многоиндексности. Показано, что второй подход является более эффективным, так как приводит к задаче, определённой на множестве, содержащем меньшее по сравнению с первым, количестве элементов.

2. Изучены поведение и свойства супермодулярных функций на абстрактных булевых решетках. Сформулирован алгоритм последовательных расчетов для минимизации супермодулярных функций на конечных булевых решетках общего вида, составными частями которого являются схема перебора, последовательно формирующая все элементы решетки и согласованные с ней правила отбраковки. Введено понятие финального правила отбраковки, согласующегося с описанной схемой и показано, что правила отбраковки метода последовательных расчетов являются финальными.

3. Рассмотрена задача условной минимизации супермодулярной функции на булевой решетке, т.е. задача минимизации при наличии дополнительных ограничений. Показано, что если ограничения задаются изотонными вещественными функциями, определенными на решетке, то область определения задачи минимизации является М-замкнутым множеством. Изучены свойства М-замкнутых множеств, позволяющие обосновать применимость метода последовательных расчетов для задач условной минимизации супермодулярных функций на булевых решетках. Сформулировано дополнительное правило отбраковки, согласованное со схемой перебора алгоритма последовательных расчетов. Отдельно рассмотрен класс задач условной минимизации, в которых ограничения задаются с помощью изотонных модулярных функций. Показано, что при решении прикладных задач, связанных с размещением предприятий, с помощью этого класса задач удается описать целый ряд практически значимых ситуаций.

4. Дана общая постановка нелинейной производственно-транспортной задачи с неделимыми потребителями. Сформулирован ряд правил отбраковки и алгоритм решения, сочетающий в себе идеи аппроксимационно-комбинаторно-ш метода и метода ветвей и границ. Аппроксимирующая задача при этом используется для формирования дополнительных правил отбраковки неперспективных вариантов и оценки точности в случае приближенного решения. Приведен большой набор нижних оценок целевой функции (оценочных функций) для возможных продолжений данного частичного плана.

5. Для задач с неделимыми потребителями и кусочно-линейными функциями производственных затрат рассмотрен еще один подход к решению, позволяющий использовать технику динамического программирования в рамках аппроксимационно-комбинаторного метода, для чего строится аппроксимирующая задача рюкзачного типа. Построение такой задачи связано с построением сепарабельной аппроксимации целевой функции. Показано, что последняя также сводится к задаче рюкзачного типа, эффективно решаемой методом динамического программирования.

6. Разработана система алгоритмов для точного и приближенного решения задач размещения с неделимыми потребителями. Каждый алгоритм определяется соответствующим набором параметров, причем система построена таким образом, что предыдущий алгоритм является частным случаем последующих. Для каждого из алгоритмов обоснованы оценки погрешности получаемых решений. На основе вычислительного опыта предложена двухэтапная стратегия решения задач большой размерности.

97

7. Разработанные методы применены для решения прикладной задачи формирования оптимальных схем электроснабжения. Показано, что не смотря на внешние различия, эта задача может быть отнесена к классу задач размещения с типовыми мощностями и неделимыми потребителями, а различия носят такой характер, что могут быть учтены при формировании соответствующих функций производственных затрат.

Приведены некоторые результаты вычислительных экспериментов.

1. В.П.Черенин. Решение некоторых комбинаторных задач оптимального планирования методом последовательных расчетов. //Научно-методические материалы экономико-математического семинара ЛЭММ АН СССР. М.: 1962, вып.2.

2. В.Р.Хачатуров. Определение оптимального и всех близких к нему вариантов размещения предприятий с ограниченными объемами производства //Изв. АН Каз.ССР, сер. физ.-матем., 1967, №3, с. 38-43.

3. В.Р.Хачатуров. Некоторые вопросы и приложения к задачам размещения метода последовательных расчетов. -Дис. .канд.физ.-мат. наук. М., ЦЭМИ АН СССР. 1968.

4. Оптимизационные задачи производственно-транспортного планирования /В.С.Михалевич, В.А.Трубин, Н.З.Шор. -М.:Наука, 1986. 260 с.

5. Вычислительные методы выбора оптимальных проектных решений /В.С.Михалевич, Н.З.Шор, Л.АГалустова и др. -Киев: Наукова думка, 1977.

6. Математические модели формирования оптимальных схем электроснабжения при автоматизированном проектировании /Веников В.А., Глазунов A.A., Тю-ханов Ю.М. Электричество. 1983. №1. с. 17-22.

7. Ю.М.Тюханов. Математическая модель группировки электроприемников по силовым пунктам //Промышленная энергетика. 1980. №8. с.21-22.

8. Ю.П.Зайченко, А.В.Швецов. Решение задачи о размещении вычислительных мощностей на территории отдельного экономического региона //Автоматика. 1984. №5. с.50-55.

9. Е.Н.Федотов. Структурная оптимизация цеховых электрических сетей //Известия высших учебных заведений. Электромеханика. 1985. №7. с.44-49.

10. Ю.С.У.Калдыбаев. Алгоритмы решения некоторых производственно-транспортных задач с условиями неделимости потребителей. Дис. .канд. физ.-мат. наук. -М., ВЦ АН СССР, 1976.

11. В.Р.Хачатуров. Аппроксимационно-комбинаторный метод и некоторые его приложения. //Журнал вычислительной математики и математической физики. 1974. № , т.14. с.1464-1487.

12. В.П.Черенин, В.Р.Хачатуров. Решение методом последовательных расчетов одного класса задач о размещении производства. // Экономико-математические методы. М.:1965. Вып.П.99

13. В.Р.Хачатуров. Алгоритм и программа решения задачи размещения предприятий с неограниченными объемами производства // Экономика и математические методы. 1967. №2.

14. В.Р.Хачатуров. Аппроксимационно-комбинаторный метод и его приложениядля решения задач регионального программирования. Дис. .д-ра. физ.-мат. наук. -М, ВЦ АН СССР, 1984.

15. В.Р.Хачатуров, А.Л.Шахазизян. Исследование свойств и минимизация супермодулярных функций на решетке, являющейся прямым произведением цепей. М.: ВЦ АН СССР, 1985. 30 с.

16. В.А.Емеличев, В.И.Комлик. Метод построения последовательности планов для решения задач дискретной оптимизации. М.: Наука. 1981.

17. Дискретные задачи производственно-транспортного типа /А.Е.Бахтин, А.А.Колоколов, З.В.Коробкова. Новосибирск: Наука. 1978.

18. В.М.Монтлевич. Супермодулярность и минимизация функций на булевых решетках. //Нелинейное моделирование и управление. Международный семинар, Самара, Университет Наяновой, 30.09-01.10 1998г. Тез. докл., с.94-95.

19. В.Р.Хачатуров, В.М.Монтлевич. Минимизация супермодулярных функций на дистрибутивных решетках. ВЦ РАН. Москва, 1999 г., 54 с.

20. В.Р.Хачатуров., В.М.Монтлевич. Решение нелинейных производственно-транспортных задач с неделимыми потребителями. М.: ВЦ АН СССР, 1987. 23 с.

21. В.Р.Хачатуров., В.Э.Лорер. Исследование и минимизация супермодулярных функций на атомарных решетках. М.: ВЦ АН СССР, 1987. 40 с.

22. Н.Д.Астахов. Некоторые динамические задачи размещения и алгоритмы их решения. Дис. .канд. физ.-мат. наук. -М., ВЦ АН СССР, 1976.

23. В.Р.Хачатуров. Математические методы регионального программирования. М.: Наука, 1989.

24. В.И.Цурков. Декомпозиция в задачах большой размерности. М.: Наука, 1981.

25. Математические модели формирования оптимальных схем электроснабжения при автоматизированном проектировании /Веников В.А., Глазунов A.A., ТюхановЮ.М. Электричество. 1983. №1. с. 17-22.

26. В.М.Монтлевич. Решение задачи оптимального размещения ВЦКП аппрок-симационно-комбинаторным методом //Сетеметрия, анализ и моделирование информационно-вычислительных сетей. Куйбышев: КуГУ.

27. В.Р.Хачатуров., Астахов Н.Д. Динамические задачи размещения, модели и методы решения // Экономика и математические методы. 1976. №1.

28. Н.Д.Астахов, В.М.Монтлевич. О решении многоиндексных задач размещения алгоритмом последовательных расчетов. //Изв. АН СССР. Техническая кибернетика. 1988, №3, с.53-58.

29. Г.Биркгоф. Теория решеток. М.: Наука, 1984.

30. Т.Ху. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.

31. В.М.Монтлевич, Е.Н.Федотов. Оптимизация параметров и структуры электрической сети в САПР электроснабжения. Тезисы докл. Всесоюзной научно-технической конференции "Повышение эффективности и качества электроснабжения". Киев, 1990 г.

32. Ю.Ф.Лыков, Е.Н.Федотов, И.В.Юрченко, В.М.Монтлевич. САПР систем промышленного электроснабжения. Учеб. пособ., Куйбыш. политехи, ин-т. Куйбышев, 1990, 77с.

33. В.М.Монтлевич. Задачи размещения предприятий с типовыми мощностями и неделимыми потребителями. // Журнал вычислительной математики и математической физики. 1999.