КАТЕГОРИИ: Архитектура-(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.14. Рассмотрим задачу = 0,4X1+ 0,3X2 + 0,1X3 + 0,1X5 + 0,2X6 (3.71) 2X2 + 2X3 + 4X4 + X5 = 150 X1 + X2 + 2X5 = 200 (3.72) X1 + X3 + 2X6 = 300 ; j = 1,...,6 (3.73) Так как ограничения (3.72) рассматриваемой ЗЛП уже имеют вид строгих равенств, то для приведения ее к каноническому виду достаточно только изменить знак функции на противоположный и рассмотреть задачу нахождения –0,4X1 – 0,3X2 – Рассмотрим расширенную матрицу А системы уравнений (3.72) Так как матрица А не содержит единичной подматрицы порядка 3, то она не является К-матрицей ЗЛП и, следовательно, к задаче (3.71)–(3.73) не может быть применен симплекс-метод. Рассмотрим метод отыскания исходного опорного плана (К-матрицы)- метод искусcтвенного базиса.
Пусть в ЗЛП (3.18) расширенная матрица системы линейных уравнений (3.63) не является К-матрицей. Рассмотрим следующую вспомогательную задачу: найти вектор , максимизирующий функцию (3.74) при условиях , (3.75) , , , , . (3.76) Переменные называются искусственными переменными вспомогательной задачи (ВЗ) (3.74–3.76). Обозначим множество планов ВЗ. Очевидно, что множество 0, так как вектор , а функция 0 ограничена сверху, следовательно, ВЗ (3.74–3.76) всегда разрешима, т.е. существует вектор такой, что = () = d. Рассмотрим расширенную матрицу системы (3.75)
, (3.77) которая является К-матрицей ВЗ (3.74–3.76), т.е. ВЗ может быть решена симплекс-методом. Предположим, что ВЗ решена симплекс-методом, на S-й итерации которого получен ее оптимальный опорный план = , () = d, (3.78) определяемый К-матрицей ВЗ. . (3.79) Очевидно, что матрица (3.80) является расширенной матрицей системы линейных уравнений, равносильной системе (3.63).
Теорема 3.14. Если () = d = 0, то вектор =(,…, ) является опорным планом ЗЛП (3.18), если () = d < 0, то множество планов ЗЛП (3.18) пусто. Из теоремы 3.14 следует, что при решении ВЗ (3.74–3.76) симплекс-методом могут представиться следующий три случая: 1. На S-й итерации симплексного метода ни одна из искусственных переменных не является базисной, (, ), т.е. матрица = (3.61) является К-матрицей ЗЛП (3.18), а план =(, …, ) – опорным планом ЗЛП (3.18), определяемым этой К-матрицей. 2. На S-й итерации симплексного метода в числе базисных оказались искусственные переменные, например, , p m, т.е. = n + 1, = n + 1, …, = n + p, причем . Тогда вектор является вырожденным оптимальным опорным планом вспомогательной задачи линейного программирования, а матрица (3.61) содержит p < m единичных столбцов и не является К-матрицей основной задачи. Однако в этом случае матрицу можно преобразовать в К-матрицу основной задачи линейного программирования, определяющую ее исходный опорный план. Для этой цели рассмотрим любую r -ю строку из первых Р строк матрицы (). Среди элементов () этой строки есть хотя бы один элемент, отличный от нуля, так как в противном случае ранг матрицы А меньше m. Выберем этот элемент в качестве направляющего и совершим один шаг метода Жордана–Гаусса преобразования матрицы с выбранным направляющим элементом. В результате базисная искусственная переменная будет заменена одной из основных переменных , а элементы (n + 1) столбца матрицы не изменятся. После р таких шагов метода Жордана–Гаусса матрица будет преобразована в К-матрицу основной задачи линейного программирования, определяющую ее исходный опорный план = (, …, ). Очевидно, этот опорный план будет вырожденным. 3. На S-й итерации симплексного метода в числе базисных оказались искусственные переменные , p m, причем хотя бы одна не равна нулю. В этом случае множество Р планов ЗЛП (3.18) пусто.
Дата добавления: 2014-12-29; Просмотров: 431; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |