Линейное программирование решение базисное

Симплексный метод. Существует много алгоритмов, позволяющих решать задачи линейного программирования. Наиболее эффективным показал себя симплексный метод (метол последовательного улучшения плана). Это итерационный метод, позволяющий получить точное решение задачи. Его сущность сводится к упорядоченному перебору базисных решений задачи. [c.198]

Однако возможны случаи, когда сформулированное выше предположение и, следовательно, приведенный вывод основных, соотношений симплексного метода не подтверждаются. Задачи, в которых имеется линейная зависимость менее чем m -f 1 векторов-столбцов матрицы ограничений, называются вырожденными задачами линейного программирования. Теоретически при их решении симплексным методом может возникнуть зацикливание", обусловленное тем, что значение линейной формы не изменяется при переходе к новому базисному решению. [c.454]

Ответ на первый вопрос дает теория линейного программирования [75]. Из нее известно, что вектор х = х . .., х ) является вершиной многогранника решений тогда и только тогда, когда х является допустимым базисным решением. [c.184]

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

Исходная задача (2.28) в результате фиксации варьируемых векторов на некоторых номинальных значениях может быть приведена к обычной задаче линейного программирования с фиксированными параметрами. Далее стандартной симплекс-процедурой осуществляется решение задачи с фиксированными параметрами. На /-Й итерации выявляется несовместность системы ограничений (2.28) при номинальных значениях Лу = йу. В этом случае базисное решении 1-1 игерации [c.33]

В оптимальном решении значение искусственной переменной xn+ni+i должно быть в точности равно нулю, для чего необходимо, чтобы базисный вектор, соответствующий этой переменной, был исключен из окончательного базиса. При использовании симплексного метода в этом случае необходимо предусмотреть специальный контроль за исключением базисного вектора, отвечающего искусственной переменной хп+т+1, что вносит определенные неудобства при решении задач линейного программирования на вычислительных машинах. [c.439]

В линейном программировании пользуются понятием об опорных решениях. К ним относят такие базисные решения, у которых все базисные переменные являются положительными, так как обычно в задачах линейного программирования нужно, чтобы x >0. Довольно очевидно, хотя может быть и доказано [8], что оптимальное решение совнадает с одним из опорных. Является ли базисное решение опорным, легко установить по виду единичного базиса — системы (VI.31). Поскольку с1 ,. .., <1 определяют значения базисных переменных, то если среди (1 есть отрицательные величины, базисное решение не будет опорным. Можно перейти от такого базисного решения к опорному следующим образом выберем из с1 отрицательное наибольшее по абсолютной величине, и вычтем уравнение для с1 из остальных, включаюпщх отрицательные Тогда свободные члены разностных уравнений станут положительными. [c.202]

Признаком неограниченности целевой функции на допустимом множестве решений является следующее утверждение если для некоторого базисного решения существует хотя бы одна внебазисная переменная х , для которой < О н ai, с О, то целевая функция задачи линейного программирования не ограничена снизу на допустимом множестве. [c.187]

Очевидно, что не всякое базисное решение является оптимальным решением задачи линейного программирования. Однако оптимальное решение невырожденной задачи всегда должно быть базисным для системы уравнений (VIII, 42), и, таким образом, задача отыскания оптимального решения заключается в переборе только базисных решений системы уравнений (VIII, 42), среди которых отыскивается оптимальное. [c.420]

Справочник химика 21

Химия и химическая технология