Cтраница 1
Любая задача линейного программирования с конечным оптимальным решением имеет базисное допустимое решение, которое является оптимальным. В - подматрица размерности ( ( га 1) ХО базисной матрицы, соответствующая этим компонентам. [1]
Поскольку любая задача линейного программирования, в какой бы форме она ни была записана, может быть приведена к эквивалентной канонической задаче, то симплексный метод является в определенном смысле универсальным методом в линейном программировании. [2]
Матрица любой задачи линейного программирования может быть приведена к такому виду при р в результате соответствующего разбиения ограничений на два подмножества, поскольку стандартную задачу можно записать в виде. [3]
В любой задаче линейного программирования число неизвестных п конечно. [4]
Теоретически позволяет решать любые задачи линейного программирования. Рассмотрим идеи, лежащие в основе свмилакс - метода. [5]
В общем случае любая задача линейного программирования сводится к так называемой симметричной игре. [6]
Основным вычислительным методом, применяющимся для решения любой задачи линейного программирования, является симплекс-метод. С его помощью мы можем, определив первое основное допустимое решение ( крайнюю точку), отыскать минимальное основное допустимое решение за конечное число шагов. Эти шаги, или итерации, состоят в том, что мы находим новое основное допустимое решение, для которого соответствующее значение целевой функции будет меньше ( или в худшем случае равно) значения целевой функции для предыдущего решения. [7]
Существуют и другие общие методы, позволяющие найти решение любой задачи линейного программирования в обозримое число шагов. [8]
Полученные при этом выводы, конечно, будут справедливы для любой задачи линейного программирования. [9]
Это является ключевой идеей при разработке общего алгебраического симплекс-метода для решения любой задачи линейного программирования. [10]
В заключение сделаем некоторые теоретические выводы, которые опираются на возможность сведения любой задачи линейного программирования со смешанными ограничениями к рассматриваемой несимметричной канонической форме ( см. гл. [11]
Мы пока не установили, может ли симплексный метод привести к решению любой задачи линейного программирования за конечное число итераций. Этот вопрос обсуждается в следующем разделе. Однако если предположить, что сходимость имеет место, то оказывается справедливой следующая важная теорема. [12]
Согласно вышеизложенному алгоритму может быть составлена программа для ЭВМ, с помощью которой можно решить любую задачу линейного программирования. [13]
В этой главе рассматриваются только конечные методы, позволяющие с помощью конечного числа арифметических действий для любой задачи линейного программирования получить точное решение или же установить, что в этой задаче оптимальных векторов не существует. Указанные методы основаны на достаточном признаке оптимальности, который был установлен в § 3 предыдущей главы и затем конкретизирован в § 6 для задач в несимметричной канонической форме. В последнем случае, как мы видели, признак оптимальности имеет особенно простой вид и, следовательно, основанные на нем методы имеют более простую структуру. Поэтому изложение методов нам будет удобно вести для задач в указанной канонической форме. А так как к последней может быть приведена произвольная пара задач со смешанными ограничениями, то общность рассуждений при этом не теряется. [14]
Итак, с теоретической точки зрения наличие симплекс-метода не решает вопроса об алгоритмической сложности линейного программирования: Можно ли любую задачу линейного программирования решить за полиномиальное время. Эта проблема имеет значительную теоретическую важность, ибо оптимальное значение линейной программы является хорошо характеризуемой с помощью теоремы двойственности функцией входа. Было время, когда оптимальное значение линейной программы являлось кандидатом номер один на роль хорошо характеризуемой функции, которая не может быть вычислена за полиномиальное время. [15]