Cтраница 1
Блочные задачи со связывающими переменными возникают тогда, когда основную часть технологических способов можно представить в виде непересекающихся подмножеств способов. [1]
Такой метод решения блочной задачи называется методом разложения Данцига - Вулфа. [2]
Такие задачи называются блочными задачами со связывающими переменными, и они являются слабо связанными, если число переменных типа я значительно меньше числа остальных переменных. Легко показать, что методы решения подобных задач могут быть использованы для решения прямых блочно-диагональных задач и наоборот. [3]
Задача оптимизации сводится к блочной задаче линейного программирования. Для ее решения в составе АСУ НПП разработан пакет прикладных программ [58], который эксплуатируется на ряде предприятий отрасли. С его помощью на ЭВМ рассчитан оперативный план при оптимизации его на максимум выпуска товарной продукции в стоимостном выражении и минимум энергозатрат для конкретного НПЗ. [4]
Поэтому применение описанного там способа решения к блочной задаче мы подробно рассматривать не будем. [5]
Подставив ( 16) в связывающие ограничения и целевую функцию исходной блочной задачи, получим задачу, для решения которой может быть использован принцип декомпозиции. [6]
Так как штрафная добавка обычно разрушает сепарабельность целевой функции, задача 1а не распадается в сумму блочных задач. Следовательно, для достижения декомиозиционности в схеме метода штрафов нужно организовать выполнение процедуры нижнего уровня, чтобы решение задачи 1а получалось в результате оптимизации отдельных блоков. [7]
В линейном программировании такими задачами являются транспортная или, в более общем слу11ае, д вухком-понентная задача, блочные задачи с односторонним и двусторонним окаймлением, а также задачи с многоступенчатым блочным строением. Эти задачи и методы их решения играют существенную роль в приложениях, и именно им в основном посвящена книга. Методы решения перечисленных специальных задач излагаются единообразно как реализации общего метода последовательного улучшения ( симплекс-метода), описание которого дается в начале книги. Таким образом, явно в книге не затронуты другие общие конечные методы линейного программирования, например метод сокращения невязок. [8]
Условия его сходимости даются, например, теоремой 5.2. Процесс, 6.21) является новым итеративным алгоритмом декомпозиции для блочной задачи линейного программирования. [9]
Несмотря на это принцип разложения позволяет вскрыть многие закономерности процесса поиска оптимального решения п с этой точки зрения может служить теоретической основой для разработки специфических алгоритмов, использующих особенности структуры блочных задач. [10]
Излагая конкретизацию методов для различных случаев окаймления, мы будем считать, что хранятся обратные матрицы D0 [ JS, / J для всех s от 2 до р, поскольку это наиболее типичный вариант блочной задачи. Ниже предполагается, что задачу мы решаем методами, описанными в предыдущем параграфе. Не повторяя сам метод, для различных случаев окаймления рассмотрим его особенности, обусловленные блочностью специальной матрицы. [11]
Решение задачи динамического распределения производственной программы на базе полученной выше динамической модели, обладающей большой размерностью для промышленных предприятий, требует наличия достаточно мощных по быстродействию и объему оперативной памяти ЭВМ и хорошо отработанных стандартных программ для решения блочных задач большой размерности. Дело осложняется также тем, что в задачах такого типа распространены случаи несовместимости системы ограничений, связанные с невозможностью учесть основные факторы при определении директивных заданий на уровне управления отраслью. Возникновение таких ситуаций приводит к необходимости, как было показано выше, корректировки исходных данных модели и повторного решения задачи. [12]
В дальнейшем ( 11) будет использовано нами в качестве определения квазивогнутости функций. Так как в следующем параграфе при рассмотрении блочной задачи со связующими ограничениями предполагается, что ограничения подзадачи образуют ограниченное множество, сформулируем и докажем для этого случая теорему. [13]
Если S - множество / з-векто-ров с неотрицательными целочисленными компонентами, a F и / - линейны, то ( 1) - ( 3) окажется хорошо известной задачей частично-целочисленного линейного программирования. Если А имеет блочно-диагональную структуру, f и F - линейные функции и S - EP или ( Ер), то возникает блочная задача, аналогичная задаче из § 2.5. Во всех этих случаях существенным является аддитивность вхождения функции у в ограничения и целевой функционал. Алгоритм разбиения Бендерса [18] ( см. § 6.3) специально построен для решения подобных задач. [14]
Здесь матрицы Л -, коэффициенты целевой функции ct и векторы правых частей Ь - все являются непрерывными функциями вектора связывающих переменных, у. Если у фиксировано, то задача становится линейной относительно xt, так что естественно настраивать переменные у и xt отдельно. Проблемы этого типа представляют собой нелинейное обобщение блочных задач ЛП. Это обобщение рассматривается в первой части данной главы. [15]