Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Понятие базиса, переход от одного базисного решения к другому




Векторы А1, А2, …, АS являются линейно-независимыми, если равенство k1A1+k2A2+…+kSAS=0 выполняется только при k1=k2=…=kS=0. Признаком линейной независимости векторов является ненулевое значение определителя, составленного из этих векторов, так как однородная система имеет единственное (нулевое) решение только при таком определителе. Если есть система линейно-независимых векторов, то любой другой вектор может быть выражен в виде их линейной комбинации и притом единственным образом: Ap=a1A1+a2A2+…+aSAS, pÏ[1, S].

В канонической форме условия записываются в виде Пусть система имеет базисное решение: Тогда (1)

Так как система совместна, то ее определитель не равен нулю, векторы являются линейно-независимыми. Система m линейно-независимых векторов, соответствующих базисным переменным, - базис. Каждой экстремальной точке соответствует своё базисное решение и свой базис.

Теперь, имея исходные базисное решение и базис , построим новое базисное решение. Смежные вершины отличаются по составу базисных переменных только одной. Поэтому новое решение можно получить путем замены одной небазисной переменной на базисную (r, rÏ[1,m]), принимающая в новом решении некоторое положительное значение В новом решении условия также должны выполняться: (2)

Задача состоит в том, чтобы определить X(1)по X(0). Выразим вектор Ar через исходный базис: Ar=A1a1r+A2a2r+…+Amamr -> qAr=qA1a1r+qA2a2r+…+qAmamr . (3)

Вычитая (3) из (1), получим:

(4)

Сравнивая (1) и (2), видим, что правые части равны, а левые содержат одну и ту же систему векторов. Поэтому коэффициенты при одноименных векторах должны совпадать. Получаем: Для допустимости решения X(1)необходимо, чтобы q было ограничено сверху:

Теперь решение всегда будет допустимым, но число ненулевых переменных в нем может превышать m, так как добавлена xr, а значит, оно может быть небазисным. Если же в качестве значения q выбрать q0, то одна из переменных станет равной нулю, а решение - базисным. Пусть минимум q0 достигается на переменной xk. Тогда базисные переменные в новом опорном решении будут вычисляться по формулам:

Этому решению соответствует новый базис {Ai}(1)={A1,…,Ak-1,Ar, Ak+1,…,Am}. Таким образом, переход к новому базисному решению произошел путем замены переменной Xk на Xr, соответсвенно в базисе - Ak на Ar.

Рассмотрим возможные ситуации при переходе от одного решения к другому. Как было показано выше, при существовании положительных коэффициентов air достигается новое базисное решение (смежная вершина), что иллюстрируется рис. а. Если же все air неположительны, величина q, а это значениевводимой переменной, не ограничена сверху. Следовательно, введение такой переменной не приведет к получению базисного решения (достижению новой вершины). Это признак того, что соответствующее ребро допустимого множества, а значит, и само множество оказываются неогранниченными (рис. б).

При вычислении q0 минимум может достигаться более чем на одном индексе. При этом обнуляется более одной переменной из входящих в исходное решение. Следовательно, в новом решении будут базисные переменные с нулевым значением, что означает попадание в вырожденное базисное решение.

Если исходное решение вырожденное и нулевой переменной соответствует коэффициет akr>0, то q0=0 и значения переменных не изменяются. Однако состав базиса и базисных переменных изменится - произойдет замена на







Дата добавления: 2015-04-19; просмотров: 1174. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2020 год . (0.002 сек.) русская версия | украинская версия