Алгоритмы решения задач размещения предприятий с типовыми производственными мощностями

• Автор: Монтлевич, Владимир Михайлович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Москва
• Количество страниц: 100 с.

СОДЕРЖАНИЕ.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
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. Задачи формирования оптимальных схем электроснабжения

4.4. Результаты вычислительных экспериментов
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

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

некоторого элемента х>0 имеется более одного представления: х= у Р~
РеРх
= / *Р Не теряя общности можно считать, чтоР аР и р*еР Р ,
~ х X г X X * X X*
реРх
откуда р*<х,р*>-0 и р*= ( у р)лр*= = у (р л р*)=0. Противоречие пока-реРх реРх
зывает однозначность представления х и следование с) из Ь).
Покажем, что из с) следует d). Пусть xeL, х= у р, где реРх <=> р£х, Р
PzPx
множество всех атомов решетки. Если РХ=Р, то х= 1 и единственным дополнением будет элемент О. Иначе положим /V х - у р. Для любого реР
РтРх.
р<х илир<х', откуда xvx — /, Пусть О <р*< хлх', тогдар*<х, х=( у p)v р*, что
реРх
противоречит однозначности представления х. Значит хлх-0 и х' - дополнение к х. Единственность дополнения следует из единственности представления 1.
В силу конечности L каждый элемент х>0 либо сам является атомом, либо содержит хотя бы один атом. Для доказательства, достаточно рассмотреть максимальную цепь, связывающую О и х, первый ненулевой элемент которой будет атомом решетки. Тогда а) вытекает из d) в силу теоремы Биркгофа-Уорда (31, стр.162).
Определение 2.12. Вещественная функция Е(х), определенная на решетке
L называется супермодулярной, если для всех x,yeL F(x)+F(y) Определение 2.13. Точку х eh будем называть точкой локального миниму-
ма функции F(x), определенной на решетке L, если для любого у ух и любого z, x>-z выполняются условия: F(x) Сформулируем некоторые свойства супермодулярных функций на решетках. Теорема 2.5. Если в булевой решетке I. лу - точка глобального минимума супермодулярной функции F(x), Xi&QXz, ТО
a) для любого x b) для любого х, удовлетворяющего условию хлх2=0 F{X2) 1'= x,v x'/jSx/v х'=> x;v х'= /, где х' - дошл-