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