КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Переход от одной К-матрицы ЗЛП к другой к-матрице
Пусть известна К-матрица . (3.45) Обозначим через вектор номеров базисных (единичных) столбцов матрицы , – вектор, компоненты которого есть базисные компоненты опорного плана, определяемого матрицей , и могут быть отличны от нуля. Остальные (n-m) компонент опорного плана, определяемого матрицей , равны нулю. Очевидно, что векторы и полностью задают опорный план, определяемый матрицей . Например, пусть = , тогда = (3, 1, 6); = = (1, 2, 4) и, следовательно, опорный план, определяемый , имеет вид = (2, 0, 1, 0, 0, 4). Итак, пусть К-матрица (3.45) определяет невырожденный опорный план . (3.46) Выберем в матрице столбец , не принадлежащий единичной подматрице, т.е. , , и такой, что в этом столбце есть хотя бы один элемент больше нуля. Пусть . Считая направляющим элементом, совершим над матрицей один шаг метода Жордана–Гаусса. В результате получим новую матрицу , (3.47) в которой столбец стал единичным, но которая может и не быть К-матрицей, так как среди величин могут быть отрицательные. Условия выбора направляющего элемента , позволяющие получить новую К-матрицу , т.е. обосновывающие способ перехода от опорного плана к опорному плану , составляют содержание следующей теоремы, которая была доказана выше: Теорема 3.8 Пусть в K -м столбце К-матрицы - есть хотя бы один строго положительный элемент (, ). Тогда с помощью одного шага метода Жордана–Гаусса можно построить новую К-матрицу , выбрав направляющий элемент из условия . (3.48) Определение. Величину , (3.49) где – вектор, компонентами которого являются коэффициенты линейной функции при базисных () переменных опорного плана, определяемого матрицей , назовем j-й симплекс-разностью матрицы . Если столбец является единичным в матрице , то =0.
Пусть и – опорные планы, определяемые матрицами и соответственно. Тогда очевидно, что (3.50) , (3.51) где К – номер столбца , вводимого в базис при получении матрицы из . определяется по формуле (3.48). Теорема 3.9. Пусть в матрице есть и в столбце (, ) есть хотя бы один строго положительный элемент. Тогда от матрицы можно перейти к матрице , причем f () f (). (3.52) Доказательство. Так как в столбце матрицы есть строго положительный элемент, то согласно теореме 3.1 от матрицы можно перейти к новой матрице ЗЛП, выбрав направляющий элемент из условия (3.48). Неравенство (3.52) вытекает из выражения (3.51), так как , а 0. Теорема доказана. Теорема 3.10. (критерий оптимальности опорного плана). Пусть все симплекс-разности матрицы неотрицательные. Тогда опорный план , определяемый матрицей , является оптимальным. Доказательство. По условию теоремы , или . (3.52) Пусть – произвольный план задачи линейного программирования. Умножим левую и правую части (3.52) на , тогда в силу неотрицательности получим . (3.53) Согласно (3.53) имеем или , что и доказывает теорему. Теорема 3.11. Пусть в матрице есть и в столбце (, ) нет ни одного строго положительного элемента. Тогда ЗЛП (3.18) не имеет конечного решения. Доказательство. Пусть k-я симплекс-разность матрицы , (3.54) и все (3.55) Матрица определяет опорный план Рассмотрим вектор у которого
где – любое положительное число. Остальные компонент вектора положим равными нулю. В силу условия (3.55) компонент вектора неотрицательные. Легко убедиться в том, что компоненты вектора удовлетворяют и функциональным ограничениям задачи линейного программирования, т.е. вектор – план задачи линейного программирования при любом положительном . Имеем:
или окончательно (3.56) Так как , то из (3.56) следует, что для любого числа всегда можно найти план ЗЛП, для которого
т.е. линейная форма не ограничена сверху на множестве планов. Теорема доказана.
Дата добавления: 2014-12-29; Просмотров: 422; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |