Гомори

Cтраница 3

В этом случае экономико-математическая модель задачи размещения сформулирована в целочисленной постановке и для своего решения требует применения специальных математических методов, например метода Гомори. [31]

Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна - Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [32]

Другое замечание касается того, что если величина Я, получаемая указанным выше способом, может быть увеличена так, чтобы [ а0 Я ] и [ а / Я ] ( a, 0) оставались без изменения, то отсечение Гомори можно усилить, несмотря на то, что нулевой столбец уменьшится на ту же величину. [33]

Как уже было отмечено в разд. Гомори и Ху [14] показали, что 5 лежит целиком или в Х0, или в Х0, так что возможны только два указанных выше случая. [34]

Название методы отсечений связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами. Гомори, используется при решении полностью целочисленных задач. [35]

Граф из примера. [36]

Как уже было отмечено в разд. Гомори и Ху [14] показали, что St лежит целиком или в Х0, или в Х0, так что возможны только два указанных выше случая. [37]

Отсечения Гомори являются полностью целочисленными неравенствами, если они выражены через исходные небазисные переменные. Таким образом, их можно представить как часть исходной полностью целочисленной матрицы АО, а приведенные выше рассуждения можно использовать для доказательства следующей теоремы. [38]

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

Правило выбора К, описанное выше, позволяет сделать ведущий элемент равным - 1, при этом будет сохраняться двойственная допустимость таблицы и в то же время нулевой столбец будет максимально лексикографически уменьшаться. Следует заметить, что отсечение Гомори не является самым сильным возможным неравенством. Оно также может быть сильнее или слабее самого производящего неравенства. [40]

Дело в том, что универсальные методы линейного программирования - симплексный, распределительный и другие, не обеспечивают выполнения условия целочис-ленности. Но ввиду сложности алгоритмизации на ЭВМ метода Гомори в практических задачах оптимизации размещения либо исключают из модели это условие, либо решают задачу каким-либо из универсальных методов линейного программирования с последующим доведением результатов решения до целочисленных значений вручную. [41]

Возникает большое число таких ограничений, по одному на каждый разрез, отделяющий каждую пару узлов. В качестве первого шага для преодоления этой трудности Гомори и Ху указывают, что если ( 7) удовлетворяется для некоторого подмножества дуг в сети, то оно удовлетворяется для всех дуг. Развитие состоит в следующем. Результат состоит в следующем. [42]

Вычеркивание ведущей строки каждый раз после преобразования может создать неверное впечатление, будто при этом теряется существенная информация. Вычеркивание слабых переменных, соответствующих введенным ранее отсечениям Гомори, после того как эти переменные снова становятся базисными, стало обычным приемом. Если as соответствует талой слабой переменной Гомори, то вычеркивание ведущей строки равносильно вычеркиванию слабой переменной. [43]

J, обеспечивающие конечность процесса решения задачи (7.19) - (7.21), были впервые предложены Гомори. В следующем параграфе излагается так называемый первый алгоритм Гомори, содержащий в себе все основные идеи методов отсечения. [44]

В дискретной задаче для расчета экономически оптимальных допусков применяют линейное программирование с дискретными переменными в общем и линейное программирование с переменными, имеющими значение нуля или единицы; известен ряд алгоритмов суммирования допусков, и могут быть использованы вычислительные машины. Из частных алгоритмов с переменными, равными либо нулю, либо единице, в отрасли эффективны алгоритмы суммирования 0 - 1 Балаша, Гомори. [45]

Страницы: 1 2 3 4