Cтраница 1
Начальное базисное решение включает упомянутые выше свободные переменные; это решение приведено в таблице на рис. 5.3 ( см. также разд. [1]
Начальное базисное решение в симплекс-методе Данцига определяется по следующему правилу: за начальные базисные переменные берутся те т переменных, при которых коэффициенты в уравнениях (11.2) образуют единичную матрицу. [2]
Легко видеть, что начальное базисное решение, построенное по методу северо-западного угла, является вырожденным. В этой же таблице приведено и начальное базисное решение, которое является невырожденным. [3]
Предположим, что нам известно начальное базисное решение хв и соответствующие ему матрица базиса В и вектор коэффициентов целевой функции св. Такое решение, если оно существует, может быть получено в результате выполнения начальной фазы общей процедуры симплекс-метода. [4]
Рассмотрим пример, из которого видно, что начальное базисное решение не всегда может быть определено. [5]
Сейчас мы уже подготовлены к рассмотрению алгоритма для получения начального базисного решения. [6]
Метод искусственного базиса позволяет построением единичной подматрицы порядка m сразу получить начальное базисное решение приравниванием значений переменных, образующих единичную подматрицу, правым частям соответствующих уравнений. Остальные переменные задачи при этом полагаются равными нулю. [7]
Метод искусственного базиса позволяет построением единичной подматрицы порядка т сразу получить начальное базисное решение приравниванием значений переменных, образующих единичную подматрицу, правым частям соответствующих уравнений. Остальные переменные задачи при этом полагаются равными нулю. [8]
Распределительный метод определения оптимального решения транспортной задачи заключается в том, что, отправляясь от некоторого начального базисного решения, последовательно1 переходим к другим базисным решениям с меньшим значением линейной формы и через конечное число шагов приходим к оптимальному решению. [9]
Задача ЛП записывается в стандартной форме, а в ограничения добавляются необходимые искусственные переменные ( как и в М - методе) для получения начального базисного решения. Решается задача ЛП минимизации суммы искусственных переменных с исходными ограничениями. Если минимальное значение этой новой целевой функции больше нуля, значит, исходная задача не имеет допустимого решения, и процесс вычислений заканчивается. Напомним, что положительные значения искусственных переменных указывают на то, что исходная система ограничений несовместна. Если новая целевая функция равна нулю, переходим ко второму этапу. [10]
Задача ЛП записывается в стандартной форме, а в ограничения добавляются необходимые искусственные переменные ( как и в М - методе) для получения начального базисного решения. Решается задача ЛП минимизации суммы искусственных переменных с исходными ограничениями. Если минимальное значение этой новой целевой функции больше нуля, значит, исходная задача не имеет допустимого решения, и процесс вычислений заканчивается. Напомним, что положительные значения искусственных переменных указывают на то, что исходная система ограничений несовместна. Если новая целевая функция равна нулю, переходим ко второму этапу. [11]
Сформулированная задача решается следующим образом. Определяют любое начальное базисное решение задачи (18.1) - (18.3) и вычисляют матрицу, обратную матрице В, составленной из базисных векторов. Если начальный базис найти трудно, то вводят искусственные переменные. [12]
Легко видеть, что начальное базисное решение, построенное по методу северо-западного угла, является вырожденным. В этой же таблице приведено и начальное базисное решение, которое является невырожденным. [13]
Поскольку расчет произведения матриц требует значительно меньших вычислительных затрат, чем определение обратной матрицы, преимущества представления обратной матрицы нового базиса в виде произведения обратной матрицы исходного базиса на дополнительную очевидны. К этому следует добавить, что для начального базисного решения часто имеется единичная матрица, для которой обратная матрица также единична. Поэтому и на первом шаге решения задачи линейного программирования симплексным методом не требуется вычислять обратную матрицу. [14]
Поскольку расчет произведения матриц требует значительно меньших вычислительных затрат, чем определение обратной матрицы, преимущества представления обратной матрицы исходного базиса на дополнительную очевидны. К этому следует добавить, что для начального базисного решения часто имеется единичная матрица, для которой обратная матрица также единична. [15]