    
Раздел: Документация
0 ... 34 35 36 37 38 39 40 ... 162 Т16.8. Свести задачу ЛП Ш-1-> min АЛ" =С Х>0 к канонической. Т16.9. Доказать, что точка а = (0, 0, ..... 0) является вершиной полиэдра, определенного условиями АХт = О, X > 0. Т16.10. Доказать теорему 16.2 при условии, что матрица С нулевая. T16.ll. Рассмотрим следующую задачу ЛП: g(x , ..., д„, V ь •, }„,) = -У I-У2 -на множестве планов •АХ +EY =С X > 0, Y > 0 . max (16.5) (16.6) где А,X, С такие же матрицы, как и в (16.2), У= (Уь Ум), Е-единичная матрица порядка вд. Доказать: 1) если оптимальное значение целевой функции g задачи (16.5)- (16.6) меньше нуля, то множество планов (\6.2) пусто; 2) если оптимальное значение целевой функции g задачи (16.5) -(16,6) равно нулю и (3 = (р,,..., p„,yi.....у,,,)- оптимальный опорный план, то точка а=(рь.... Р„) является опорным планом задачи П16.1. Найти вершины полиэдра планов, определенных системой: 2Х + х2 +- 2.xу + 4х4 - .Vj = - л] + х2 + 2ху + 2х4 - х5 = 3 х, >0, / = 1,...,5 (16.7) Общая формулировка задач К16.1-К16.11 Опираясь на утверждение задачи Tl6.ll, найти неотрицательное базисное решение системы уравнений АХ = С, где /2.8 I 1 3 2.89 3.678 4 2 К16.1. С = (15, 6.9,29) К16.4. Сг = (6, 7.5,34) К16.7. С=(6,21,5) К16.10. Ст = (3.2,2.9, 31) 1.8 -2 1.9 2 -1 1 3 4 4.6 -1/2 5.55 К16.2. Сг= (15, 23,29) К16.5. Ст= (1, 8.3, 4.5) K16.ll. Ст = (14, 11.2, 8.2) К16.3. Ст= (5, 9, 13) К16.6. Ст-(7,2.7, 11) К16.9. Ст=(13, 3.4,2.9) Ответы, указания, решения Т16.1. Функция/может быть записана в матричной форме DX\ гдеХ= (хь х2, х„), D = {du..., d„). Тогда ДШ+ц N) =D(KM +ц N? = =ШМТ +ц Шт=А,ДЛ/) + \\f[N) (см. теорему 3.1). Т16.2. Указание: воспользоваться задачей Т16.1. Т16.3. Указание: воспользоваться задачей Т16.!. Т16.4. Указание: воспользоваться тем, что выпуклая комбинация планов также является планом. Т16.5. Ответ: если (ct], а?,..., ап) - решение неравенства, то для любого неотрицательного числа сс„ точка (аoil,о,,, а„+0- решение системы. Обратно, если (о., <х2,а,,, а„+ ]) - решение системы, то точка (а,], оь? ! a,,) -решение неравенства. Т16.7. Указание: каноническая запись будет такой: di(y\-Z]) +...+ dp(yp-zp)dp ,Л;, + ...+ d,X„ -» max ajyx-zu+ ...+ aip(yp+ ...+ alllx„+t=cl, i = \,...,k a,\(}\~z\+ - + а,,,(У,, ~+P-a, !•< x+--i- + a:»x» =c<> i = k + \,...,m >0, z;>0,7 = \,...,p, it >0, j = },....k x j = p + 1,..., n T16.8. Указание: целевая функция канонической задачи следующая: -DX1 -> max Т16.9. Предположим, что точка а не является вершиной полиэдра. Тогда из задачи Т14.2 следует, что существуют две такие различные точки р и у, принадлежащие полиэдру, и числа А.) > 0 и А.2 > О, А + Хг = 1 > для которых выполняется равенство Лр + Л.2У =а = (0, 0). Но, так как среди координат точек р и у нет отрицательных, последнее равенство невозможно. T16.I0. Указание. Среди планов существует план а со всеми нулевыми координатами. В этом случае по определению план а опорный и является вершиной полиэдра планов в силу задачи Т16.9. Если же план а содержит ненулевую координату, то доказательство производится так, как и ранее (см. доказательство теоремы 16.2). Т16.П. 1)Пусть (а,, а,,)- некоторый план задачи (16.1)-(16.2). Тогда точка а = (ось а,„ 0, 0) из Af" "- план задачи (16.5) - (16.6). Однако g(a) = 0, а это противоречит тому, что оптимальное значение функции g отрицательно. 2)Поскольку #(Р) -0, топ = ..=УМ = 0 и а = (Р....., Р„) - план задачи (16.1)-(16.2). Так как координаты плана р, соответствующие столбцам матрицы Е, равны 0, то положительные координаты планов соответствуют одним и тем же столбцам матрицы А. Поскольку план р опорный, то в силу леммы 16.1 и теоремы 16.1 эти столбцы линейно независимы. Поэтому из тех же утверждений вытекает то, что стопорный план задачи (16.1)-(16.2). Следует отметить, что один из опорных планов задачи (J6.5) - (]6.6) очевиден при условии, что С>0: это точка (0, О, с,, с,„). (А ГО П16.1. Поскольку столбцы Я= и й2=[ линейно независимы, то по лемме 16.1 они могут определять вершину полиэдра. В этом случае координаты вершины долж- [2а. +а, =4 ны иметь вид (а5. а,, 0, 0, 0) и система (16.7) превращается в систему < [а, +аг = 3 Решив последнюю, получаем а = 1, Ш = 2. Поэтому точка (1, 2, 0, 0, 0) является вершиной полиэдра. w (A m м Повторив эти рассуждения для пар векторов а\ -\\) и a=\l) 2 =\}) и a=\iy щ- jj и a4=2J получим еще три вершины полиэдра: точки (1,0,1,0,0), (0,2,0,0.5,0), (0,0, 1,0.5,0). Пары векторови,и, - Pi (~ Л = I I линейно зависимы и поэтому по лемме 16.1 не могут определять вершину. определяют вершину полиэдра, то ее координаты имеют вид 0, 0, 0, Решив [2а. -а, = 4 систему j, получим at- 1, «5-2. Так как среди координат точки (1, 0, 0, 0, -2) есть отрицательные, то эта точка не является планом. По той же причине планом не является точка (0, 0, 0, 0.5, -2). Рассмотрим линейно независимые векторы я, = и а5 = 1 \\. Если эти векторы Общий алгоритм решения задач К16.1 - К16.11 с помощью Mathcad Ввести матрицы А, с. Определить размеры матриц, задать начальные значения переменных и целевую функцию для решения вспомогательной задачи ЛП в соотйетствии с утверждениями задачи ORIGIN : = 1 n:=cols(A)m;=rows(A)il=l;nХ±:=0j: = l;m Y-.,=0 f(X,Y) ~* - / Y 0 ... 34 35 36 37 38 39 40 ... 162 |
