С учетом возможностей современных ППП, использующих модифицированный симплекс-метод с мультипликативным представлением матрицы, отнесение очередного вектора к классу векторов, обеспечивающих совместность или несовместность, требует проведения всего нескольких итераций после модификации обобщенной матрицы [c.207]
Общие требования к реализации моделей. Предложенные модели решения задач маневрирования излишними и сверхнормативными запасами в зависимости от номенклатур ресурсов, по которым предполагается реализация модели, допускают непрерывное решение либо требуют целочисленного решения. Например, решение задачи о перераспределении ресурса, измеряемого в тоннах, допускает непрерывное решение, а решение задачи для ресурса, представляющего собой совокупность неделимых объектов (измеряемого в штуках), требует целочисленного решения. Следует отметить, что все предложенные модели допускают декомпозицию по ресурсам, т. е. в одной модели по перераспределению конкретного ресурса или даже в модели обменных операций по одноименной продукции требования к искомым переменным величинам модели одинаковы и могут быть непрерывные либо целочисленные. Ограничения всех моделей линейны, а критерии могут быть как линейными, так и нелинейными. Решения приведенных моделей перераспределения ресурсов можно получить одним из ниже перечисленных методов прямой симплекс-метод, симплекс-метод с введением искусственного базиса, модифицированный симплекс-метод. [c.183]
В распоряжении вычислительных центров, как правило, имеются стандартные программы для решения на ЭВМ задач линейного программирования. По существу большинство из них реализует методы, эквивалентные описанному в этой книге методу последовательного улучшения плана. В зарубежной литературе он известен под названием модифицированного симплекс-метода. Упомянем публикации программ [c.222]
Описанный вариант симплекс-метода не является единственным. На практике обычно употребляется более совершенный вариант — модифицированный симплекс-метод, связанный с использованием двойственной задачи (оценок) и по существу близкий к описанному выше методу последовательного улучшения плана. [c.35]
МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД [c.50]
Вычислительная схема, основанная на преобразовании обратных матриц. Анализируя вычислительную процедуру симплекс-метода с позиций оценки трудоемкости, нетрудно заметить, что наиболее критичным в этом плане является э ап пересчета значений А и b при переходе от одного базисного плана к другому (п. 3 алгоритма). Однако в том случае, когда число ограничений задачи m явно меньше количества переменных я, можно добиться существенной экономии , выполняя на очередной итерации q преобразование Жордана—Гаусса не над матрицей Л(р(<7)), а над матрицей Дч(р(<7)). При этом учитывается и то, что при необходимости, применяя формулу (1.26), всегда можно получить Л(р(<7>) по Д Чр(<7)). Более того, для выполнения описанных выше действий симплекс-процедуры нам в действительности не требовалась матрица Л(р(<7)) целиком. Реально в ней использовались только строка оценок а0(р(<7)) и ведущий столбец аЧр О. Данные соображения положены в основу вычислительной схемы симплекс-метода, основанной на преобразовании обратных матриц, которую также называют модифицированным симплекс-методом. Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича. [c.50]
Вычислительной схеме модифицированного симплекс-метода соответствует система таблиц 7] и T q). Таблица 7J (рис. 1.7) является общей для всех итераций и служит для получения [c.50]
По аналогии с п. 1.4.1 опишем формальную схему алгоритма модифицированного симплекс-метода. [c.51]
В завершение подчеркнем, что в силу приведенных выше преимуществ именно модифицированный симплекс-метод реально применяется в программном обеспечении, предназначенном для решения канонических задач линейного программирования. [c.53]
Пример решения ЗЛП модифицированным симплекс-методом. Приведем решение рассмотренной ранее задачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3 [c.53]
Еще раз вернемся к таблице Т (рис. 1.8), получаемой на финальной итерации процедуры модифицированного симплекс--метода. Более подробно рассмотрим нулевую строку матрицы A 4p(<7)), для которой было введено обозначение 80(р(/7)). Поэлементно она может быть записана в следующем виде [c.62]
Таким образом, существенным преимуществом модифицированного симплекс-метода является то, что он позволяет одновременно найти оптимальные планы как прямой, так и двойственной задачи. [c.63]
В заключение отметим, что в настоящем параграфе был рассмотрен вариант двойственного алгоритма, соответствующий стандартному симплекс-методу. Нетрудно догадаться, что существует и вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием обратных матриц), но, поскольку этот вопрос представляет интерес в основном с точки зрения техники организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным описанием данной версии алгоритма можно ознакомиться в [1]. Отметим лишь, что она обладает теми же принципиальными преимуществами, что и модифицированный симплекс-метод. [c.77]
Модифицированный симплекс-метод — вычислительная схема, связанная с преобразованием обратных матриц. [c.79]
Сформулируйте основные отличия модифицированного симплекс-метода по отношению к стандартному. [c.81]
Перечислите преимущества модифицированного симплекс-метода. [c.81]
Будет ли отличаться количество итераций при решении одной и той же задачи при решении ее стандартным и модифицированным симплекс-методом [c.81]
Метод разложения (декомпозиции) был разработан для решения задач линейного программирования большой размерности, имеющих блочную структуру. Его вычислительная процедура главным образом основана на идеях модифицированного симплекс-метода. Однако значение метода Данцига—Вулфа состоит не только и (не столько) в его вычислительных преимуществах, сколько в возможности дать содержательную экономическую интерпретацию. Метод предусматривает разложение исходной задачи (5.6)—(5.9) на локальные задачи, соответствующие обособленным частям объединения (в данном случае предприятиям), и главную задачу (соответствует объединению в целом и связывает эти локальные задачи). [c.179]
Р. Б. Д у б и н а, К. Е. Ч е р н и н. Программа образования и записи на М. Б. матрицы для модифицированного симплекс-метода.— Сборник программ для ЭВМ Урал . Л., Аркт. и антаркт. ин-т, 1966. [c.223]
Среди методов нахождения оптимального решения наибольшее распространение приобрёл метод последо-ват. улучшения допустимого решения (МНУ), к-рый имеет большое число вычислит, реализаций (симплекс-метод, пли симплексный метод, метод обратной матрицы, пли модифицированный симплекс-метод, мультипликативный метод, метод потенциалов для траисп. задачи и др.). При использовании вычислит, машин МНУ даёт возможность решать задачи Л. п. общего вида с сотнями ограничений и практически любым числом переменных, а задачи спец. вида — с тысячами ограничений (способы часто не хранятся в памяти, а воспроизводятся алгорифмичоски). [c.357]
Описанный вариант симплекс-метода не является единственным. На практике обычно употребляется более совершенный вариант — модифицированный симплекс-метод, связанный с использованием двойственной задачи (о. о. оценок). Существуют и другие методы решения задач линейного программирования. Упомянем и коротко поясним один из них — метод блочного программирова- [c.42]
Общая задача линейного программирования не может быть решена обычными методами классического анализа. Поэтому для ее решения применяются специальные методы, дающие вычислительную схему, которая позволяет за конечное число шагов (итераций) найти оптимальное решение. Для решения указанных задач могут быть использованы следующие математические методы 1) последовательного улучшения, 2) распределительный, 3) модифицированный распределительный, 4) разрешающих множителей, 5) матричный, 6) симплекс метод, 7) индексный, 8) графо-аналитический и др. [c.188]
Р. А. Звягина. Программа реализации на М-20 модифицированного L симплекс-метода с узкоблочной матрицей.—Оптимальное планирование. Новосибирск, 1966, вып. 4. [c.223]
Смотреть страницы где упоминается термин Модифицированный симплекс-метод
: [c.26] [c.52] [c.170]Смотреть главы в:
Математические исследования операций в экономике -> Модифицированный симплекс-метод