Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 27
Текст из файла (страница 27)
3.3 составленная пз отрезков каких-либо координатных осей и прямых аих+ аиу = Ь' (1 = 1, ..., т). Это многоугольное множество может быть как ограниченным (рнс.3.2) — тогда сг' представляет собой выпуклый многоугольник, так и неограниченным (рис. 3.3). 108 элементы линейнОГО пРОГРАммиРОВАния !ГЛ.
3 Пусть а — какое-либо значение функции»(и) = (с, и> = с,х-г+ с,у. Тогда уравнение с,х + с,у = а (2) аадает линию уровня функции»(и), соответствующую ее значению а, и на плоскости определяет прямую, перпендикулярную вектору с=(со с»)тьО. При из- У ° ~г менении а от — до прямая (2), смещаясь параллельно самой себе, «зачертит» («заме—:У тет») всю плоскость. При этом вектор с указывает направление, в котором следует смещать прямую (2), чтобы увеличивать значение функции» (и) = (с, и). а г Если У вЂ” многоугольник (ом, | рис. 3.2), то при изменении а от — до»» прямая (2) при некотором значении а = Х„ впервые коснется П и будет иметь с сг' общую точку и«(на рис.
3.2 — 3.5 прямая (2) представлена при а = а, ( У„< (а»(а»). Ясно, что (с, и ) = Х«=1В1(с, и), т. е. и« вЂ” реп»ение задачи (1). Возможен случай, когда прямая (2) при первом касании с многоугольником П будет иметь не одну общую точку .а ' г г иа'=,' Р, аг аг Рис. 3.6 Рис. 3.6 с 5г, а целую сторону (рис. 3.4) — это может случиться, если (г' имеет сторону, перпендикулярную вектору с. Если многоугольное множество (г не ограничено, то наряду со случаями, когда при первом касании прямая (2) будет иметь с П одну общую точку ие (см.
рис. 3.3) или сторону (рис. 3.5), з 2~ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ. УГЛОВЫЕ ТОЧКИ 109 возмоясна ситуация, когда прямая (2) при всех а ( — < а < <и,< ) имеет общую точку с П (рис. З.б) — тогда 1п1(с, и) = = — оо(первого касания прямой (2) с П нет), т. е. задача (1) пе имеет решения. Из рассмотренных случаев задачи (1) видно, что задача линейного программирования может ие иметь пи одного решения (см.
рис. ЗА, 3.6), может иметь лишь одно решение (см. рис. 3.2, 3.3), может иметь бесконечно много решений (см. рис. 3.4, 3.5). Апалогично можно показать, что множество П в задаче (1.15) при п = 3 является мяогогранпым множеством, и дать геометрическую иптерпретацию этой задачи. Предлагаем читателю самостоятельно рассмотреть этот случай, а также исследовать задачу (1.14) при и = 2, 3. 2. На примере рассмотренной выше задачи (1) нетрудно усмотреть, что если задача (1) имеет решение, то среди решений найдется хотя бы одна угловая точка (вершила) многоугольного мпоя'ества П. Ниже мы увидим, что это ке случайпо: и в более общей задаче линейного программировапия, оказывается, нижняя грань функции <с, и) ка (у достигается в угловой точке множества.
Определение 1. Точка и множества О' называется угловой точкой (вершиной, крайней точкой, экстремальной точкой) мпожества О', если представление п= ии, +(1 — сс)и, при ио и, ~ я П и О < и < 1 возможно лишь при и, = и,. Ипаче говоря, и— угловая точка мпожества П, если опа не является внутренней точкой никакого отрезка, прияадленгащего множеству П. Например, угловыми точками многоугольника на плоскости или параллелепипеда в пространстве являются пх вершины; все граничные точки шара будут его угловыми точками; замкнутое полупространство или пересечепие двух замкнутых полупрострапств яе имеют пи одной угловой точки. В задачах линейпого программирования понятие угловой точки играет фундамептальную роль и лежит в основе многих методов решевия таких задач.
В дальнейшем мы будем подробно исследовать каноническую задачу (1.14). Поэтому начнем с изучения свойств угловых точек множества П = (и ы Е": и > О, А и = Ъ), (3) где А — матрица размера т Х и, А Ж О, Ъ вЂ” вектор из Е . Ниже будет показало, что множество (3), если опо непусто, имеет хотя бы одпу угловую точку (см. теорему 5.1). Возникает вопрос, как узнать, будет ли та или иная точка мпожества (3) угловой точкой? Приведем один достаточно простой алгебраический критерий угловой точки мпожества (3).
Для этого вначале обозначим хй столбец матрицы А через А; и запишем систему уравнений 1[О элемегты лш!ейного пРОГРлммиРОВлнпя [Гл. з Аи = Ь в следующей эквивалентной форме: А,и'+... + А„и" = Ь. (4) Т е о р е м а 1. Пусть множество У определено условиями (3), А ть О, г = ганя А — рана матрицы А. Для того чтобы точка п = (и', ..., п")ш У была угловой точкой множества У, необходимо и достаточно, чтобы су[цвствовали помере уэ ..., у, (1(у1(п, 1=1, ..., г) такие, что Л; и" + ...
+А;„и'"= Ъ; п'= О, 7'Ф/1, (=1,, г, (5) причем столбцы А,,, ..., А,„линейно независимы. Доказательство. Необходимость. Пусть п — угловая точка множества У. Если и = О, то из условия Ош П следует, что Ь = О. Поскольку А ть О, то г = ганя А > 1 и существуют линейно независимые столбцы А;,,..., А;„. Отсюда имеем А; О+... ...+А; 0= О, Для случал э=О соотношения (5) доказаны.
Пусть теперь иьь 0 н пустьо", ..., и'" — все положительные координаты точки ш Отсюда и пз условия АР = Ь с учетом представления (4) имеем А и'1+ ... +А, о'"=Ь, и'=О, /Ф/1, 1=1,...,/с. (6) Покажем, что столбцы А;,, А;„линейно независимы. ~1' ' ' '' Пусть при некоторых я„..., я, имеет место равенство я,А + ... + яьА;„= О. (7) Возьмем точкУ п+ = (о+,..., и+) с кооРдинатами о = и + сир, 'р 'р Р.'Р = 0 при 1 Ф/„(у=1, ..., /г) и точку о' = (о', ..., и") с кооРДинатами Р э=и" — ЕЯр, о' = 0 пРи /~/р(Р = 1, ..., К). Поскольку овр)0(р=1,..., Ь), то при достаточно малых е ~ 0 будем иметь и+>О, п >О.
Кроме того, умножая (7) на е или — е и складывая с (6), приходим к равенствам Аи+ — — Ь, Ап = Ь. Таким образом, иэ, о ш П. Очевидно, и=(и++и )/2, т. е. и =яи++(1 — я)и прн я=1/2. По определению угловой точки это возможно лишь прн о+ = Р- = Р, что в сво[о очередь означает, что я, =... = я, = О. Таким ооразом, равенство (7) возмоя[по только при я, =... = я,=О.
Линейная независимость столбцов 41 ..., 41 доказана Отсюда следует что Ь< Если к = г, то соотношения (6) равносильны (5). Если к (г, то добавим к столбцам А;, ..., А;„новые столбцы А; т, ..., А1 матрицы А так, чтобы система А;, ..., Л,„, А;,, ..., А; была линейно независимой, а при дооавлении любого другого столбца А[ эта система становилась линейно зависимой. Тогда система А;, ..., А;, образует некоторый базис линейной оболочки векто- 1' з 21 ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ. УГЛОВЫЕ ТОЧКП ров Ао ..., А„. Размерность линейной оболочки векторов А„... ..., А„равна рангу матрицы А, так что в = г =гапяА. Добавив к первому равенству (6) столбцы А;„+,, ..., А;„, умноженные соответственно на Р'"+' = О, ..., о" = О, из (6) получим соотношения (5). Необходимость доказана.
Д о с т а т о ч н о с т ь. Пусть некоторая точка Р = (Р', ..., и") удовлетворяет условиям (5), где Ау, ..., А;, — линейно независимы, г = ганя А. Пусть Р = ии, + (1 — а) и, при некоторых о„и,ш (у, 0< а<1. Покажем, что такое представление возможно только при Р,=Р,=Р.
Сразу же заметим, что если Р' О, то из этого представленпя с учетом неравенств 0<а<1, Р',~)0, Рз ) )0 получим 0 ( ии', + (1 — сс) Р', = РУ = О, что возможно лишь при Р', = О22 = РУ = О. Таким образом, для получения равенства Р= Р, = Р, остается еще доказать, что Р, = оз = Ру и при у у тех у, для которых Р') О. По условию (5) у точки Р положительными могут быть лишь координаты РУ2, ...,РУ".
Произведя при необходимости перенумерацию переменных, можем считать, что ОУ1)0, ...,РУ")О, ОУ"+' = О, ..., о'" = 0 (случаи й= 0 или У2 =г здесь не исключаются). Тогда (4) можно переписать в виде А; Р'г+... + Аузг'в= = Ь. Кроме того, учитывая, что по доказанному Р, = Р, = 0 при всех узьу, (р=1, ..., Уе), равенства АР,=Ь также можно записать в виде А; вл -~- ... + Ауьо~~ = Ь (у = 1, 2). Вспомним, что векторы Ау,, А; линейно независимы. Поэтому вектор Ь 1' может линейно выражаться через А;, ..., А; единственным способом.
Это значит, что РУР = Р,~ = Р2Г для р = 1, ..., й. Тем самым установлено, что и = о, = иь Следовательно, Р— угловая точка множества уу. Определение 2. Систему векторов А;,, ..., Ау„, входящих в первое из равенств (5), называют базисом угловой точки Р, а соответствующие им переменные Р'5 ..., и" — базисными координатами угловой точки ш Если все базисные координаты угловой точки положительны, то такую угловую точку называют невырожденной Если же среди базисных координат Р'~, ..., Р'"— хотя бы одна равна нулю, то такая угловая точка называется выроаеденной.
При фикспровапном базисе Ау, ..., А;„переменные и'1, ..., и'" называются базисными переменными угловой точки, а остальные переменные и' — небазисными (свободными) переменными. Из теоремы 1 следует, что невырожденпая угловая точка ооладает единственным базисом — ее базис составляют столбцы с теми Ромерамн, которым соответствуют положительные коорди- В2 элементы линеиного пГОГРАммнРОВАння ~гл. 3 наты угловой точки. Если угловая точка вырожденная, то она может обладать несколькими базпсамн. В самом деле, если ьэ') ~0, ..., г'з) 0 (й(г=гапйА), а остальные координаты и1 угловой точки в равны нулю, то, как видно из доказательства теоремы 1, в базис такой точки обязательно войдут столбцы А;,, ..., А;, а остальные базисные столбцы А,з+м ..,, А...
входящие в представление (5), могут быть выбраны, вообще говоря, различными способами. Пример 1. Пусть У=(и=(и', и', и', и')ыЕ": й~О, 2 ..3 3+ в 3 ~ 2+ з значим Аг = [Т], Аз — — [ 1], Аз — — [1], Аз = [з], Ь = [~ ]. Нетрудно видеть, что точки и,=(2, 1, О, О) и и,=(0, 5/3, О, 4/3) являются невырогкденпымп угловымн точками множества У, причем точке и, соответствует базис А„Ам а точке и,— базис А„А,; угловая точка из=(0, О, 1, 0) вырожденная и ей соответствуют базисы А„А, или А„А, или А„А,; точка и,= =(5, О, О, — 2) не является угловои для множества 1/, так как и, Ф (/.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
