![]() КАТЕГОРИИ: Архитектура-(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) |
Условие устойчивости двойственных оценок
В предыдущем параграфе мы предполагали, что при изменении столбца свободных членов Теорема 1. Пусть матрица
Матрица
- где Рассмотрим с этой точки зрения решение задачи (1) п.1.8 симплекс-методом. Как мы видели выше (см. пп.1.8-1.9), переход от одной симплекс-таблицы к другой (операция однократного замещения) осуществляется с помощью элементарных преобразований Гаусса, и, следовательно, в силу теоремы 1 с помощью умножения на некоторую матрицу перехода. Рассмотрим подробнее переход от первой симплекс-таблицы к последней симплекс-таблице. Переместим в первой симплекс-таблице ((4) п.1.8) столбец
Соответствующую матрицу обозначим
Соответствующую матрицу обозначим
Как было отмечено выше, каждый столбец последней симплекс-таблицы получается из соответствующего столбца первой симплекс-таблицы умножением на матрицу перехода
Поскольку
Итак, оказалось, что матрица перехода
Векторное равенство (6) равносильно двум равенствам. Первое равенство соответствует первым
где - подматрица матрицы исходной системы ограничений, стоящая в столбцах
столбцы свободных членов первой и последней симплекс-таблицы соответственно. Второе равенство соответствует последней строке равенства (6) и фактически означает, что
где Заменим теперь свободные члены
удовлетворяющие условию устойчивости двойственных оценок:
Применим к новой исходной симплекс-таблице те же самые элементарные преобразования, что и к исходной. В результате мы получим новую последнюю таблицу, которая на самом деле окажется симплексной. Действительно, все столбцы этой таблицы кроме, быть может последнего, совпадут с соответствующими столбцами прежней последней симплекс-таблицы, и, следовательно соответствующая система ограничений будет иметь разрешенный вид, а целевая функция будет зависеть только от свободных переменных. Поскольку матрица перехода от первой к последней таблице не изменится, то последний столбец свободных членов, согласно (7) и (11) определяемый равенствами:
в силу (12) окажется неотрицательным. Это значит, что на самом деле получена новая симплекс-таблица. При этом все элементы, стоящие в индексной строке кроме, возможно, свободного члена (равного, кстати, значению целевой функции) останутся теми же самыми и, следовательно, будут неотрицательны. Последнее означает, что соответствующее опорное решение является оптимальным. При этом базисные переменные нового оптимального решения будут теми же, что и у старого оптимального решения. Как было отмечено выше, соответствующее новое оптимальное значение целевой функции определяется согласно (10):
Пусть новые значения Тогда новый вектор роста двойственной задачи также бесконечно мало отличается от старого вектора роста
Сравнивая (14) и (16), получаем, что
Поскольку последнее равенство должно выполняться для любых неотрицательных
Таким образом, действительно в столбцах балансовых переменных Итак, мы видим, что при изменениях ресурсов, удовлетворяющих условию устойчивости (12), новое оптимальное решение Пусть в нашем примере
и (13) будет иметь вид:
Как видим, условие устойчивости (12) выполнено. Новое оптимальное решение
в которой старый столбец свободных членов
Можно также воспользоваться формулой:
где
Дата добавления: 2014-12-26; Просмотров: 1346; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |