Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 30
Текст из файла (страница 30)
Аналогично можно показать, что множество Х в задаче (1.21) при и = 3 является многогранным множеством, и дать геометрическую интерпрета- цию этой задачи. Предлагаем читателю самостоятельно рассмотреть этот случай, а также исследовать задачу (1.15) при и = 2, 3. 2. На примере рассмотренной выше задачи (1) нетрудно усмотреть, что если задача (1) имеет решение, то среди решений найдется хотя бы одна угловая точка (вершина) многоугольного множества Х. Ниже мы увидим, что это не случайно: и в более общей задаче линейного программирования, оказывается, нижняя грань функции (с, х) на Х достигается в угловой точке множества, Определение 1.
Точка е множества Х называется угловой точ- кой (вершиной, крайней точкой, экстремальной точкой) множества Х, если представление е=ае +(1 — а)е, при е„е, Е Х и 0<а <1 возможно лишь при е, =е . Иначе говоря, е — угловая точка множества Х, если она не явля- ется внутренней точкой никакого отрезка, принадлежащего множеству Х. Например, угловыми точками многоугольника на плоскости или паралле- лепипеда в пространстве являются их вершины; все граничные точки шара будут его угловыми точками; при и > 2 замкнутое полупространство или пересечение двух замкнутых полупространств не имеют ни одной угловой точки.
В задачах линейного программирования понятие угловой точки играет фундаментальную роль и лежит в основе многих методов решения таких (б) задач. В дальнейшем мы будем подробно исследовать каноническую задачу (1.15). Поэтому начнем с изучения свойств угловых точек множества Х =(хе Е™ч х~)0, Ах= 6), (3) где А — матрица размера гп х и, А ~0, Ь вЂ” вектор из Е™.
Ниже будет показано, что множество (3), если оно непусто, имеет хотя бы одну угловую точку (см. теорему 4.1). Возникает вопрос, как узнать, будет ли та или иная точка множества (3) угловой точкой? Приведем один достаточно простой алгебраический критерий угловой точки множества (3). Для этого вначале обозначим 3'-й столбец матрицы А через А, и запишем систему уравнении Ах = Ь в следующей эквивалентной форме: А,х'+... + А„х" = Ь. (4) Т е о р е м а 1. Пусть множество Х определено условиями (3), А фо, т = гаппА — ранг матрицы А. Для того чтобы точка е = (е',..., е") Е Х была угловой точкой множества Х, необходимо и достаточно, чтобы существовали номера д'„...,2'„, 1 < д', < п, 1= 1,..., г, такие, что А, ьз+...+А, е' =Ь; е'=О, т~т„1=1,..., г, (5) причем столбцы А,,, А,, линейно независимы.
Доказательство. гтеобходимость. Пусть е — угловая точка множества Х. Если е =О, то из условия 0 е Х следует, что Ь = О. Поскольку А ~0, то г = гапяА > 1 и существуют линейно независимые столбцы А,,, А, Отсюда имеем Аз О+... + Ат 0=0. Для случаи е =0 соотношения (5) доказаны. Пусть теперь е ф 0 и пусть е'1,..., ея — все положительные координаты точки е. Отсюда и из условия Ае = Ь с учетом представления (4) имеем А, ея +...
+ Аз е" = 6; е' = О, 3' ф ~'„1 = 1,...,?с. Покажем, что столбцы А,,, А. линейно независимы. Пусть при некоторых а„..., а„имеет место равенство сс, А, +... + а Ат = О. (7) Возьмем точку е+ — — (е„',..., е„") с координатами е" = е" + га, е' = 0 при 2' ф 2',, р = 1,..., к, и точку е = (е',..., е') с координатами е' = е"— — га,, е'' = 0 при 2 ф 2', р = 1,..., Ь. Поскольку е" > О, р = 1,..., Ь, то при достаточно малых г > 0 будем иметь е+ > О, е > О. Кроме того, умножая (7) на г или — г и складывая с (6), приходим к равенствам Ае = Ь, Ае = Ь. Таким образом, е+, е е Х.
Очевидно, е = (е, + е )/2, т. е. е = ае„+ (1— — сс)е при а = 1/2. По определению угловой точки это возможйо лишь при е„= е = е, что в свою очередь означает, что с~, =... = сс =О. Таким образом, равенство (7) возможно только при а, =... = а„= О. Линейная независимость столбцов А,,, А.
доказана. Отсюда следует, что й < г. Если?с=г, то соотношения (6) равносильны(5). Если й<г, то добавим к столбцам А,,, А,. новые столбцы А,,..., Аз матрицы А так, чтобы система А,,,А,,А,,,Ат была линейно независимой, а при добавлении 104 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ $2. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ. УГЛОВЫЕ ТОЧКИ 105 любого другого столбца А? эта система становилась линейно зависимой. Тогда система А,,, Ау образует некоторый базис линейной оболочки векторов А„...,А„. Размерность линейной оболочки векторов А„...,А„равна рангу матрицы А, так что з=т=гаппА.
Добавив к первому равенству (6) столбцы А,, А ., умноженные соответственно на е"" = О,..., е' = О, ьн' из (6) получим соотношения (5). Тем самым необходимость доказана. Достаточность. Пусть некоторая точка е=(е',...,е") удовлетворяет условиям (5), где А,,; Ау — линейно независимы, т = гапКА.
Пусть е = сге! +(1 — сг)е при некоторых е„ез Е Х, О < гх < 1. Покажем, что такое представление возможно только при е, = е, = е. Сразу же заметим, что если е' = О, то из этого представления с учетом неравенств 0 < сг < 1, е!' ) О, ез > 0 получим 0 < сге!'+ (1 — сг)ез' = е' =О, что возможно лишь при е,' = е1 = е!' =О. Таким образом, для получения равенства е = е, = е, остается еще доказать, что е! = ез = е' и при тех «', для которых е! > О. По условию (5) у точки е положительными могут быть лишь координаты е',..., е'. Произведя при необходимости перенумерацию переменных, можем считать, что е" > О,..., е" > О, ел н = О,..., е' = 0 (случаи 6 = 0 или Ь = т здесь не исключаются). Тогда (4) можно переписать в виде Але" +...+Ау е' = 6.
Кроме того, учитывая, что подсказанному е,' =еб =0 при всех «' ф»',, р = 1,..., ?с, равенства Ае! = 6 также можно записать в виде А?ей+... + Ау ей = 6, з' =1, 2. Вспомним, что вектоРы А,,, Ау л линейно независимы. Поэтому вектор Ь может линейно выражаться чеРез Ау,, Ау единственным способом. Это значит, что ет = е," = е'" длЯ р = 1,..., 6. Тем самым установлено, что е = е, = е,. Следовательно, ив угловая точка множества Х. С) О п р е д е л е н и е 2, Систему векторов А,,, А, входящих в первое из равенств (5), называют базисом угловой точки е, а соответствующие им переменные е?,..., е' — базисными координатами угловой точки е.
Если все базисные координаты угловой точки положительны, то такую угловую точку называют невырождвнной. Если же среди базисных координат е",..., е' — хотя бы одна равна нулю, то такая угловая точка называется вырожденной. При фиксированном базисе А,,, Ау переменные м",..ч и' называютсЯ базиснььми пеРеменными Угловой точки, а остальные переменные м' — нвбазисными (свободными) переменными. Из теоремы 1 следует, что невырожденная угловая точка обладает единственным базисом — ее базис составляют столбцы с теми номерами, которым соответствуют положительные координаты угловой точки.
Если угловая точка вырожденная, то она может обладать несколькими базисами. В самом деле, если ей > О,..., е" > О, й < т = гапяА, а остальные координаты е' угловой точки е равны нулзо, то, как видно из доказательства теоремы 1, в базис такой точки обязательно войдут столбцы А,,..., А., а остальные базисные столбцы Ау,, А., входящие в представление (О), могут быть выбраны, вообще говоря, различными способами.
Поскольку из п столбцов матрицы А можно выбрать т линейно независимых столбцов не более чем С„" способами (С„" — число сочетаний из п элементов по т), то из теоремы 1 следует, что число угловых точек множества (3) конечно. Пример 1. Пусть Х =~х=~х!, хз, хз, х4)ЕЕ4: х')О, ?'=1,...,4 х' + хз+ Зхз + х' = 3, х' — х + х + 2х' = 1). Обозначим А,=, А,=, А,=, А,=, Ь= ь, что точки х, = (2, 1, О, 0) и х = (О, 5/3, О, 4/3) явля- ными угловыми точками множества Х, причем точке базис А„А, а точке х — базис А„А,; угловая точка ожденная и ей соответствуют базисы А „А„или А, А, х, = (5, О, О, — 2) не является угловой для множества Х, Нетрудно видет ются невырожден х, соответствует х, = (О, О, 1, 0) выр или Аз, А„; точка так как х,(ь Х.
Упражнения 1. При каких значениях параметра азздзчз: у(х)=х +ах -~1п(, хеХ=(хеЕ: х>0, ив ! 2 2. — хх > 1, х' + 2хз > 4) имеет решение? Нс имеет решения? Имеет единственное решение? Нарисуйте график функции у„= У,(а) = 1п1 1"(х), Грзфичсски изобразите множество Х,(а) = =(хи Х: У(х) =У„(а)) при различных а. 2. Найти ясс угловые точки и их бззисы для множеств; Х! — — (х е Е; х л О, х — 2х — х = О, -х + Зх + х = 1), 4, ! 2 3 ! 2 З Хз — — (хеЕ !х>0, х +х +х +х =1, -х +2х +х +х =П, З.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
