Cтраница 2
Таким образом, были представлены варианты координирующей задачи с одним и р ограничениями, соответствующие совместному и изолированному представлению диагональных блоков исходной задачи. Хотя наиболее предпочтительным представляется вариант координирующей задачи с р ограничениями, при решении конкретных задач может оказаться более эффектным использование иного варианта такой задачи. [16]
Сравнив его с заключительной таблицей ограниченной координирующей задачи, убедимся, что полученное двойственное решение является оптимальным. [17]
На основе этой информации центр решает координирующую задачу, в результате чего определяются глобально оптимальные показатели работы элементов. Эти показатели передаются элементам и позволяют сформировать локальные задачи элементов. При решении этих задач формируются детализированные планы элементов. [18]
Эта задача, эквивалентная исходной, называется координирующей задачей. Она имеет только nii l строк по сравнению с ( m, m2) строками исходной задачи и большое число столбцов. Если тz - достаточно большое число, то число столбцов, равное числу крайних точек S2, будет измеряться многими тысячами. [19]
Некоторые пояснения к блок-схеме: 1) суженная координирующая задача - суть задача ЛП; она имеет базисное допустимое решение и конечное максимальное значение, например oft; 2) решением подзадач находится точка Хт 1, удовлетворяющая проверяемому условию, добавление этой новой точки к суженной координирующей задаче может улучшить решение. [20]
Допустимость исходной задачи приводит к тому, что координирующая задача также имеет допустимое решение. Из компактности S вместе с непрерывностью ft и gi следует, что подзадача i имеет оптимальное решение, поскольку она имеет допустимое. [21]
Характерной особенностью этого метода является использование так называемой координирующей задачи, которая по сравнению с исходной имеет небольшое число строк ( не намного превышающее число связывающих ограничений) и, вообще говоря, очень много столбцов. При этом для решения координирующей задачи не требуется задание всех столбцов в явном виде. Они генерируются в процессе использования симплекс-метода. Поэтому такой подход мы называем методом генерации столбцов. Алгоритм включает итерационный обмен между множеством независимых подзадач, целевые функции которых включают варьируемые параметры, и координирующей задачей. В подзадачи вводится ряд параметров ( двойственные переменные, оценки), получаемые при решении координирующей задачи. В свою очередь в координирующую задачу вводятся решения подзадач, которые оптимальным образом комбинируются и служат для получения новых оценок. Последние вновь вводятся в подзадачи, и итеративный процесс продолжается вплоть до этапа, на котором удовлетворяется критерий оптимальности. Такая процедура имеет изящную экономическую интерпретацию: ее, например, можно понимать как процедуру децентрализованного планирования, когда основной планирующий ( управляющий) орган системы координирует функционирование отдельных подсистем с помощью цен на ограниченные ресурсы. [22]
Идея добавления более чем одного ограничения соответствует сокращенной координирующей задаче в принципе декомпозиции Данцига - Вулфа, в которой более чем одно из предложений подзадач может входить в базис. [23]
Задача ( 2 17) - (2.20) называется координирующей задачей. [24]
Вычислительные эксперименты показали, что использование на каждом шаге координирующей задачи р п приводит к улучшению сходимости метода Данцига - Вулфа. [25]
В этом случае разделим систему т ограничений на суженную координирующую задачу, включающую R ( R С т) линейных ограничений, и подзадачу, куда входят остальные ( т - R) линейных ограничений, а также условия неотрицательности переменных. Такая декомпозиция ( разложение) задачи нередко целесообразна по двум причинам. Во-первых, размерность задачи, определяемая числом ограничений т, может оказаться слишком большой для той ЭВМ. Во-вторых, т - R ограничений, входящие в S. Поскольку имеются разные способы разложения задачи линейного программирования, приводимое ниже изложение является скорее пояснением, чем исчерпывающим рассмотрением подхода. [26]
Можно доказать, что оптимальные значения ch целевой функции суженной координирующей задачи монотонно возрастают, сходясь к оптимальному значению с целевой функции исходной задачи. [27]
Пусть a [ S [ J Т - оптимальное решение координирующей задачи, полученное описанным способом, а / - соответствующее оптимальное базисное множество. [28]
Заметим, что подобный подход применим и в случае, когда координирующая задача имеет только одно ограничение. В этом случае генерируются k столбцов ( k l) с отрицательными характеристическими разностями, с использованием которых формируется ограничение координирующей задачи. Опыт показывает, что такой прием улучшает сходимость алгоритма. Описанный выше прием может быть применен и при использовании общего метода декомпозиции Данцига - Вулфа. [29]
Опишем / - ю итерацию алгоритма, на которой поочередно решаются координирующая задача центра и локальные задачи элементов. [30]