КАТЕГОРИИ: Архитектура-(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.37) где - размерность ЗЛП по числу оптимизационных переменных; - n -мерный вектор-столбец оптимизационных переменных; - n -мерная вектор-строка коэффициентов целевой функции; D – множество допустимых решений ЗЛП в n -мерном Евклидовом пространстве; - - мерная матрица коэффициентов основных ограничений (матрица условий ЗЛП, рис.1.13). Исходя из условий формирования ЗЛП и правил перехода к канонической форме записи, можно утверждать, что всегда . Крайний случай при совместной системе линейно независимых уравнений соответствует вырожденному случаю, когда ни о какой оптимизации (как о выборе лучшего решения из множества допустимых решений) речи не идет. Тогда решение ЗЛП – это просто решение системы линейных уравнений (конечно, если это решение удовлетворяет условию ). Для строк и столбцов матрицы условий будем использовать следующие обозначения: - i -ая строка матрицы А, - j -ый столбец матрицы А; - m-мерный вектор-столбец правых частей ограничений. Кроме того, в линейном программировании для определения параметров канонической формы ЗЛП используются следующие структуры данных: - расширенная матрица условий ЗЛП. Ее размерность - (m+ 1 ,n); - расширенный вектор-столбец правых частей ограничений размерности (m+ 1). Базисом (B) ЗЛП с матрицей условий A(mxn), имеющей ранг m, называется система расположенных в определенном порядке m линейно независимых векторов столбцов этой матрицы: . Для обозначения номера столбца здесь используется так называемая соподчиненная индексация, в которой ji определяет номер столбца матрицы А, включенного в базис, а i - порядковый номер, определяющий положение этого столбца в базисе.
Например, при и для , , . Если B определен, то ему в ЗЛП ставятся в соответствие следующие структуры данных: - - базисное множество (система номеров столбцов матрицы А, или, что одно и то же, номеров оптимизационных переменных, включенных в определенном порядке в базис); - В -квадратная m-мерная базисная матрица, составленная из базисных векторов–столбцов матрицы условий (ранг этой матрицы r(B)=m вследствие линейной независимости включенных в нее столбцов); - B-1 - обратная по отношению к В матрица, в которой (В) - i-ая строка, (В) - j-ый столбец, (В)[i,j] - (i, j) – ый элемент; - - m -мерная вектор-строка коэффициентов целевой функции при базисных переменных; - - расширенная базисная матрица размерности (m+ 1)´(m+ 1); - расширенная обратная базисная матрица: , (1.38) вид которой получен из путем применения правил поблочного обращения. Для отдельных частей этой матрицы будем использовать следующие обозначения: - i-ая строка (в частности, , - j-ый столбец, - (i, j) – ый элемент;
- А(В) - (m´n)–мерная матрица коэффициентов разложения векторов-столбцов матрицы условий A по векторам базиса: (1.39) Покажем, что это действительно так. Для произвольного l -ого вектора-столбца матрицы A(B) на основании соотношения (1.39) можно записать: или, что одно и то же, Таким образом, имеет место следующее важное и в дальнейшем широко используемое соотношение , (1.40) из которого и следует, что столбец состоит из коэффициентов разложения вектора-столбца al по векторам базиса.
Из (1.40) становится также очевидным, что для для векторов-столбцов , включенных в базис, соответствующие вектора и матрицы А (В) (1.41) где - вектор-столбец, у которого i-ая компонента равна единице, а остальные имеют нулевые значения. Таким образом, из столбцов , располагая их в порядке, соответствующем базису, составляется единичная m – мерная матрица:
- расширенная матрица : . (1.42) Для отдельных частей этой матрицы будем использовать следующие обозначения: - i-ая строка, - j-ый столбец, - (i, j) – ый элемент. Видим, что - это (m+ 1)´ n –мерная матрица. Ее верхняя часть представляет собой уже известную матрицу A(B), а последняя строка этой матрицы (1.43) в линейном программировании называется строкой симплекс-разностей. Для этой строки также будем использовать следующее обозначение , где симплекс-разность, соответствующая j- ому столбцу (j- ой переменной) ЗЛП в соответствии с (1.43) равна (1.44) Сущность симплекс-разностей будет рассмотрена ниже при обосновании метода решения ЗЛП, называемого симплекс-методом.
Дата добавления: 2014-01-15; Просмотров: 633; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |