    
Раздел: Документация
0 ... 32 33 34 35 36 37 38 ... 162 В гл. 4 было показано, что с помощью элементарных преобразований совместную систему лине иных уравнений АХт = С можно привести к виду, содержащему базис переменных и некоторый набор свободных переменных. При этом нулевые значения свободных переменных будут однозначно определять значения базисных переменных. Поэтому имеет место следующее определение. С~Определение~) Базисным решением системы АХТ~ С называется такое ее решение (ai, «г.....ап) еЛг"1, для которого множество всех переменных, соответствующих ненулевым координатам в а, целиком содержится в некотором базисе переменных. (Этот базис можно получить из системы АХ = С элементарными преобразованиями.) Базисное решение системы АХТ = С, в котором все ненулевые координаты положительны, называется опорным планом задачи (16.1)-(16.2). План, в котором все координаты нулевые, также будем называть опорным. Теорема 16.1. План задачи (16.1) - (16.2) является опорным, если и только если он является вершиной полиэдра планов. Доказательство. Проведем доказательство при условии, что матрица С имеет хотя бы одну ненулевую координату. Пусть ct= (ct,ai, ar, 0,0), a, > 0, /= I,г - опорный план задачи (16.1)- (16.2), который не является вершиной полиэдра планов. В этом случае (см.существуют такие различные планы (3 и у, что а- \$ + (1 -Х}у для некоторого числа X е (0,1). Как и при доказательстве леммы 16.1 можно показать, что (3 = (р,Р2,Рп 0, 0), ji -(yi,y2j ...,Yn 0, 0). Это означает, что в планах и у все переменные, соответствующие положительным координатам, целиком содержатся в том же базисе переменных, что и переменные .tb соответствующие положительным координатам опорного плана а. Но значения базисных переменных однозначно определяются нулевыми значениями свободных переменных. Отсюда следует, что СС = р = уь аг = рг= у„ т.е. а=р = у Получено противоречие. Пусть теперь... , 0, ... , 0)- вершина полиэдра планов, причем /= 1, Докажем, что а-- базисное решение системы АХГ= С и, следовательно, опорный план задачи (16.1)-(16.2). Из леммы 16.1 следует, что первые г столбцов матрицы А линейно независимы. Из следствия 5.3 вытекает, что система xfy +... +xrbr = 0 имеет единственное (нулевое) решение. Поэтому, как бы не применялся алгоритм метода Гаусса к этой системе, всегда будет получаться единственный базис переменныхЭто означает, что в случае применения к системе х,Ь, +... +xrbr+xrilbA +... + xrb== с" такого алгоритма метода Гаусса, при котором на первых шагах в качестве разрешающих будут выбираться только столбцы с номерами 1,..., г, мы обязательно придем к базису этой системы, содержащему хи ...,хг(в этом базисе могут быть и другие переменные). Поэтому в плане а все ненулевые координаты соответствуют переменным, входящим в некоторый базис системы, т. е. а - опорный план. Доказательство теоремы при условии, что матрица С нулевая, провести самостоятельно. Теорема доказана. Из теоремычто опорный план и вершина полиэдра планов одно и тоже. Следствне 16.1. Если система (16.2) имеет решение, то задача (16.1) - (16.2) имеет хотя бы один опорный план. Это следствие фактически доказывается в задаче Т16.11, в которой приводится один из способов нахождения начального опорного плана задачи (16.1)- (16.2) (см. гл. 17). Лемма 16.2. ПустьДх,, .г,,)-линейная функция. Тогда для любых двух точек М. V. Лу\\ любых двух чисел А, ц/(Ш + u/V) =Х/(М) + Ц Д), Доказательство леммы дано в задаче Теорема Еслиимеет оптимальный план, то существует полиэдра, которая является оптимальным планом. Доказательство. Проведем доказательство при условии, что матрица С имеет хотя бы один ненулевой элемент.что задача не имеет оптимальных планов, являющихся вершинами полиэдра, определяемого условиями (16.2). Среди оптимальных планов выберем такой план а = (а,, сс2, а,., О, .... 0), который содержит наименьшее число положительных координат. Из леммы следует, что векторы-столбцызависимы. Для такого случая при леммы 16.1 было показано существование точек вида а ± ц3, где ... , 0, 0), являющихся планами задачидля любых чисел иО. при которых координаты в а ± ц(3 неотрицательны. В частности, точка а - ц В- план, если ц равно числу ,u.= mm - или числу u,2=Tiax- (по крайней мере одно из чисел ухи Из существует). При этом а - ц,р будет содержать по крайней мере на одну положительную координату меньше, чем а, / = 1, 2. Поэтому план а~ не может быть оптимальным, т. е. /а) >/Ta-Li,p) =/(а)-ц/(р)(16.4) (последнее равенство следует из леммы Вернемся теперь к планам а±цр. В силу леммы 16.2 J{a) >/(а + цР)-J(a) ± u/(P), W /(РКО откуда { , 0<дДр)< 0, что возможно только при /(р) =0. Но тогда из (16.4) следует,что невозможно. Получено противоречие. Доказатель- ство теоремы при условии, что матрица С нулевая, дано в задаче Т16.10. Теорема доказана. Следствие 16.2. Если множество планов задачи (16.1)-(16.2) многогранник, то существует вершина, которая является оптимальным планом этой задачи. Доказательство. В силу утверждения 14.1 и следствия 15.3 многогранник планов является замкнутым ограниченным множеством, и поэтому из теоремы 15.2 следует, Компьютерный раздел Встроенная функция гапк{А) определяет наибольшее число линейно независимых столбцов матрицы А, т. е. ранг матрицы А. Встроенная функция augmenА2 , . . AN), аргументы Al, Д2, . . ЛТУкоторой -• матрицы с одинаковым числом строк, формирует матрицу (A1 A2 ...AN) С тем же числом строк (матрицы Al, А2, - • АТУразмещаются последовательно слева направо).
Встроенная функция maximize (f, v) (minimize( f,v)) определяет вектор v, обеспечивающий функции f(v) максимальное (минимальное) значение. Перед использованием этих функций необходимо задать начальные (стартовые) значения координатам вектора v. Если даны дополнительные ограничения, то эти функции должны завершать так называемый блок решения, начинающийся ключевым словом Given. Пример использования функции maximize приведен ниже: f(z):= sin<z„) + cos (z" (z, - I)2 -4 Given x < xl := Maximize(f,x) xl := fl.575 8.405 x 10"* Программирование в Mathcad осуществляется с помощью подпанели Программирование (Programming) (рис. 16.1), для вызова которой следует щелкнуть по кнопке $51 панели Математика (Math). Эта подпанель содержит 10 кнопок. Щелчок по что задача (16.1) - (16.2) имеет оптимальный план. В силу теоремы 16.2 в этом случае существует оптимальный план, который является вершиной многогранника планов. Следствие 16.3. Если некоторые вершины полиэдра планов задачи (16.1) -(16.2) являются оптимальными планами, то любая их выпуклая комбинация также является оптимальным планом. Доказательство следствия см. в задаче Т16.2. 0 ... 32 33 34 35 36 37 38 ... 162 |
