169.74 Kb.Название Дата конвертации29.09.2012Размер169.74 Kb.Тип 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. Линейное программирование Основные определения и теоремы Линейное программирование Основные определения и теоремы Определение 1. Задача, в которой требуется минимизировать (или максимизи]ровать) линейную форму при условии, что , , или , , и , , называется задачей линейного программирования в произвольной форме записи. Определение 2. Задача в матричной форме вида (1) называется симметричной формой записи задачи линейного программирования. Определение 3. Задача линейного программирования вида (2) называется канонической формой записи задачи линейного программирования. Любую задачу линейного программирования можно привести к кано]ни]ческой форме. Если система ограничений задана в форме , то можно, введя дополнительные переменные, привести ее к виду , , , где . Если же ограничения в задаче заданы в форме , то , , . Рассмотрим задачу с ограничениями . Эту систему ограничений можно представить в виде системы . Введем следующие обозначения: , , , , , , , . Тогда задачу линейного программирования можно записать в виде: , . Векторы называются векторами условий, а сама задача линейного программирования называется расширенной по отношению к исходной. Пусть и - допустимые множества решений исходной и расширенной задач соответственно. Тогда любой точке множества соответствует единственная точка множества и наоборот. В общем случае, допустимое множество исходной задачи есть проекция множества расширенной задачи на подпространство исходных переменных. Определение 4. Набор чисел , удовлетворяющий огра]ни]чениям задачи линейного программирования называется ее планом. Определение 5. Решением задачи линейного программирования называется ее план, минимизирующий (или максимизирующий) линейную форму. Введем понятие базисного решения. Из матрицы расширенной задачи выберем линейно независимых векторов-столбцов, которые обозначим как матрицу , а через обозначим матрицу из оставшихся столбцов. Тогда , и ограничения расширенной задачи линейного программирования можно записать в виде: . (3) Очевидно, что столбцы матрицы образуют базис -мерного пространства. Поэтому вектор и любой столбец матрицы можно представить в виде линейной комбинации столбцов матрицы . Умножим (3) на слева , (4) и найдем отсюда : . (5) Придавая различные значения, будем получать различные решения . Если положить , то . (6) Решение (6) называют базисным решением системы из уравнений с неизвестными. Если полученное решение содержит только положительные компоненты, то оно называется базисным допустимым. Особенность допустимых базисных решений состоит в том, что они являются крайними точками допустимого множества расширенной задачи. Если среди компонент нет нулевых, то базисное допустимое решение называется невырожденным. Определение 6. План задачи линейного программирования будем называть опорным, если векторы условий с положительными коэффициентами линейно независимы. То есть опорный план это базисное допустимое решение расширенной системы, угловая точка многогранника решений. Определение 7. Опорное решение называется невырожденным, если оно содержит положительных компонент (по числу ограничений). Невырожденный опорный план образуется пересечением гиперплоскостей из образующих допустимую область. В случае вырожденности в угловой точке многогранника решений пересекается более гиперплоскостей. Теорема 1: (основная теор
Линейное программирование Основные определения и теоремы
Линейное программирование Основные определения и теоремы
Комментариев нет:
Отправить комментарий