Исследование методов декомпозиции некоторых задач линейного и выпуклого программирования

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

Оглавление
Введение
1. О некоторых взаимосвязанных задачах математике
ской экономики и процессах согласования их решений
1.1. Две классические задачи
1.2. Обобщенная транспортная задача
1.3. Производственные модели
1.4. Производственно-территориальные комплексы
1.5. О некоторых оценках и аппроксимации блочных условий
2. Декомпозиция задачи лииейногор(|ммиРован;и<я: с0 связующими ограничениями и пёрёйёшшми
2.1. Постановка задали: в общем виде
2.2. Прямой и двойственный процессы
2.3. Достаточное условие оптимальности решения
2.4. Объединенная .производственно-транспортная задала
3. О согласовании локальных и глобальных оптимальных, планов
3.1. Постановка задачи
3.2. Первый вариант разложения глобальной задачи
3.3. Второй вариант разложения: глобальной задачи
Заключение.
Список; литературы

Введение,
Актуальность темы. Разработка методов декомпозиции оптимизационных задач началась в конце 50 х начале 60 х г.г. (для
задач линейного программирования со специальной структурой ограничений) и продолжалась в трудах многих исследователей, поскольку разложение ’’большой” задачи рассматривалось как эффективное средство преодоления ограничений по ресурсам памяти и быстродействия ЭВМ. Этот аспект исследований остается актуальным (несмотря на появление мощных пакетов прямого решения задач математического программирования различных типов) в связи с проблемой решения взаимосвязанных задач, организацией параллельных вычислений и т.п. приложений.
Однако уже в первых работах, посвященных методам декомпозиции, отмечалась возможность их применения к изучению проблемы децентрализации решений — более общим образом — механизмов формирования, развития и функционирования разнообразных иерархических систем: производственных, экономических, социальных и т.д. С этой точки зрения становятся существенными тонкие детали поведения, связанные с конкретными особенностями и внутренней структурой исследуемого объекта (как, например, в механике — не общая система уравнений Ньютона, а следствия, скажем, для абсолютно твердого тела).
В диссертации в качестве объекта приложений разрабатываемых методов изучаются механизмы получения и согласования (в рамках глобальной задачи более общего характера) оптимальных отраслевых планов, правда, не в наиболее общей возможной, постановке, а когда

целочисленные переменные не используются и задала остается выпуклой. В действительности, здесь возникает еще одна проблема
более адэкватного описания отраслевой задачи, поскольку классическая производственно-транспортная задача с одним видом транспор
та носит оценочный характер. Сопоставление отраслевых и глобальных задач (в любых разумных постановках) однако показывает, что каких-либо математических структур типа классических блоков со связующими ограничениями здесь выделить нельзя. Свободными же параметрами в отраслевых задачах (не имеющими ясной физической основы) являются показатели потребностей в продукции и затрат, т.е. элементы функционала и правой части задачи: одновременно.
Математический аналог такого рода неопределенности возникает в классической схеме блочной задачи линейного программирования со связующими ограничениями и переменными. Однако известно, что в общем случае для ее декомпозиции можно предложить только трехуровневую схему Данцига-Вулфа, Соответственно, возникает вопрос: нет ли в практических задачах каких-то особенностей, использование которых позволило бы эту схему упростить. Такая особенность нашлась. Оказалось, что в рассматриваемых в диссертации задачах (прямо или после эквивалентных преобразований) удается получить систему, у которой на пересечении блоков, соответствующих связующим: ограничениям и переменным, оказывается подматрица с нулевыми: элементами. Такого рода системы и оказались математическим объектом проведенных в диссертации исследеваний. Следует отметить, однако, что приложение к конкретным задачам связано с весьма тонкими структурными особенностями, формирующих их соотношений, выявление которых представляет самостоятельный интерес и позволяет понять внутренние (и не всегда очевидные) свойства
образом, (1.59) и (1.63) будут выполняться автоматически, (1.60) — в силу неравенства г > - 0, а (1.64) т.к. % > Д - 0. □
Следствие 1.9.1. Если для оптимальных решений двойственных задал: (1.58)—(1.65) выполняется условие 1ё > 0, то множество допустимых в блочной производственной задаче пар векторов 0, (/ отделяется от их недопустимых значений неравенством:
р10 - Й > - Л - т1$. (1.66)
Неравенство же еЩ > 0 имеет место тогда и только тогда, когда выполняется условие
а] -С! > тах{0, (1.67)
Доказательство. Если (1.67) имеет место, то ё)Ц > 0, так как из (1.67) а) - 0 > 0, а из (1.60) Щ > Ц - 0 и далее снова из (1.67) и (1.59) е) > а) - (I -1-Д-] - Д > 0. Если же выполняется неравенство еЩ > 0, то по дополняющей ыежесткости условий (1.63) И (1.64) р1 = = 1} а значит а]- - 0 = Щ > 0 в (1.60). Но так как и ё) > 0, то
из (1.59) Щ > Д* - 0, откуда и получаем (1.67). Отсекающее же свойство неравенства (1.66) следует из равенства оптимальных значений функционалов (1.58) и (1.65). □
Этим следствием: описывается случай, в известной мере, противоположный рассматривавшемуся в теореме 1.7: полные потребности в продукте а] не только превосходят его импорт 0, но и разница между ними оказывается больше возможного превышения объема производства продукта Д* над экспортом: 0. Оказывается, что систему материальных потоков внутри пункта нельзя сбалансировать если при любом возможном способе использования его внутренних ресурсов появляется хотя бы один продукт с указанными свойствами.