Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Пусть в ЗЛП (3.18) расширенная матрица системы линейных уравнений (3.36) не является К-матрицей. Рассмотрим следующую вспомогательную задачу: найти вектор , максимизирующий функцию
(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.36).
Теорема 1.7. Если () = d = 0, то вектор =(,…, )
является опорным планом ЗЛП (3.18), если () = d < 0, то множество планов ЗЛП (3.18) пусто.
Из теоремы 1.7 следует, что при решении ВЗ (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) пусто.
Дата публикования: 2015-10-09; Прочитано: 218 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!