Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 28
Текст из файла (страница 28)
Поскольку нз и столбцов матрицы А можно выбрать г линейно независимых столбцов не более чем С„" способамн (С"„— число сочетаний из и элементов по т), то из теоремы 1 следует, что число угловых точек множества (3) конечно. Кроме того, как увидим ниже (см. теоремы 6.1, 6.2), если 1/чь 8 п гп1(с, и) ) — со,то эта нижняя грань достигается хотя бы в одной угловой точке множества (3).
Это значит, что каноническую задачу (1А4) можно попытаться решить следующим образом: 1) найти все угловые точки множества (3) — для этого можно, например, рассмотреть Сэ систем вида (5) и проверить, будут ли выбранные столбцы А;, ..., А; „линейно независимы н будут ли соответствующие решения системы (5) неотрицательными; 2) вычислить значение функции У(и)= <с, и> в каждой нз угловых точек, число которых, как мы знаем, конечно, п определить наименьшее из ннх. Однако такой подход к решению задачи (1.14) практически не применяется, так как даже в задачах не очень болыпой размерности число угловых точек может быть столь большим, что простой перебор всех угловых точек множества (3) может оказаться невозможным за разумное время даже при использовании самых быстродействующих ЭВМ.
Тем не менее идея перебора угловых точек множества оказалась весьма плодотворной и послужила основой ряда методов решения канонической н других задач линейного программирования. Одним пз таких методов является так называемый сиэпг- сихшлккс-мктод лекс-метод. 11азвание этого метода связано с тем, что он впервые разрабатывался применительно к задачам линейного программирования, в которых множество У представлял собой симплекс в а в":у — (=э',..., "~: эО,»; '=1); *дб 1=1 обобщен на случай более общих множеств У, но первоначальное название за ним так и сохранилось; в литературе этот метод также называют методом последовательного улучшения плана. Оказывается, с помощью симплекс-метода можно осуществить упорядоченный (направленный) перебор угловых точек множества (3), при котором значение функции <с, и> убывает прп переходе от одной угловой точки к другой, и при этом, рассмотрев лишь относительно небольшое число угловых точек, удается выяснить, имеет ли задача (1Л4) решение, и если имеет, то найти его.
Кроме того, как увидим ниже, симплекс-метод мо»кет быть использован также и для определепия угловой точки множества (3). 5 3. Симплекс-метод 1. Перейдем к описанию симплекс-метода для решенпя канонической задачи (1.14): <с, и>- 1п1; ишь=(ишЕ": иэ0, Аи=Ы. (1) В (1Л4) предполагалось, что матрица А имеет размер тХп. Тогда г = гапд А ( ппп (т; п). Предполагая, что из системы (Аи)'=Ь' (1=1, ..., т) исключены линейно зависимые уравнения, можем считать, что матрица А имеет размер г Х и, где г= гапдА. Тогда г(п. Если г= и, то система Аи = Ь будет иметь единственное решение и н множество У будет либо пустым (если не соблюдается ограничение и ~ О), либо будет состоять нз одной точки (если и ~ О) — в этом случае задача минимизации функции У(и) на У становится малосодержательпой.
Поэтому будем считать г (и. Тогда система Аи = Ь запишется в виде а„и' +... + а,„и" = Ь1, а„,и'+... + а„„и" = Ь', (2) где г =гащА (и. Пусть известна некоторая угловая точка и = (и', ..., о") множества У. Перенумеровав при необходимости переменные, без умалеш|я общности дальнейших рассмотрений можем считать, что столбцы Л„..., Л, матрицы А являются базисом точки и, П4 ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ [ГЛ. 3 а переменные и', ..., и' — базиснымп переменными. Обозначим и=, и=, с= ., А;= 1 г1 '' ггпу Тогда систему (2) можно переписать кратко так: А,и'+...+А„и" +Аг+1игы+....+А„и" = = Вй+ А„+,и""'+... + А„и" = Ь.
(3) и+ ~ В 1Аьи = В 'Ь = о~~0. А=г+1 (4) Обозначим: (В-'А,)' = т,„ — з-я координата вектор-столбца В 'А, (з-1, ..., г, й =г+1, ..., п). Тогда уравнение (4) можно запи- сать в покоординатной форме и1 + у иг+1 ( + у НП Р1 и' + Рз,„.ьти"+' (- ... +Р1 и" = о', из + у1,пьти"+' + ... + у1пип = О1, (5) и" + уг гььи+1 -~- ... + у ип = Рп Перенося в (4) и (5) слагаемые с пебазпсными переменнымп вправо, получаем выражение базисных переменных через небазисные в векторной форме: и и = о — ~ч~~ В 1ААи а=г+1 (6) Поскольку столбцы А„..., А, липейпо независимы, то бсьВй О и, следовательно, существует обрап1ая матрица В '.
Кроме того, согласно теореме 2.1 небазпсные координаты Р"+', ..., Р угловой точки о равны нулю, так что о = ~О ], где 8 ~ О. Тогда пз (3) следует, что базисные координаты 8 удовлетворяют системе Вй = Ь, откуда имеем й = В 'Ь ~ О. Учитывая последнее равенство, умножим систему (3) на В ' слева и получим следующее соотнопгение между базисными переменными й и небазисными переменными и'+', ..., и": с1ю1плвкс-31ктод 115 п соответственно в покоордннатпой форме: и' = в' — 7«,.гги"+' —...
— 7,„и" —... — 7 .и", н ц (г «+ги 7«хи . 71 и (7) П' '= Р' — 7«, г+1П ° ° ° '1 ЬП ° ° ° 7 1П ° Подчеркнем, что системы (3) — (7) являются эквивалентными переформулировкамн исходной системы (2). Заметим также, что если заранее знать номера базисных переменных, то для получения из (2) соотношений (7) можно воспользоваться известными методамн (4, 54] (напрпмер, схемой Жордана).
О том, как определить угловую точку п номера ее базисных переменных и как привести систему (2) к виду (7), будет рассказано в з 5. Пользуясь соотношениями (6) плп (7), функцпю Х(и) = «« = (с, и) = ~ сгм1 можно выразить через небазнсные пере- пенные: .у (11) = с, 1« — ~ В ~А1и'~)+ ~~ с1и1 = а=«+1 1=г+1 = (с, 1«) — У ((с, В 'Л1) — с1) и'. 1=г+1 Поскольку <с, й> = <с, и> = У(и), то у()=у() — Х йнп, 1=г+1 (8) где гз1= (с, В 'Л1) — с1 = ~ с,7,1 — с1.
(9) Кстати заметим, что величины гхг имеют смысл н прп 1=1, ... ..., г; тогда гхг= <сь е,> — с«= О, так как по определению обратной матрицы В 'Лг= ег (1=1, ..., г), где ег — 1-й столбец единичной матрицы порядка гХ г. Входящие в (5), (8) величины 7„, вг, гхг удобно записать в виде табл. 1, которую принято называть симплекс-таблицей, соответствующей угловой точке и.
Для дальнейшего полезно заметить, что величины 7.,=(В 'А,)', Ьг= <с, В 'Лг> — с, полностью определяются заданием А, с и базиса угловой точки и не зависят от Ь. Таким образом, каноническая задача (1) может быть теперь сформулирована в равносильной форме через небазисные переменные: минимизировать функцгпо (8) прп условиях (6) (нли (7)) н, кроме того, и > О. Конечно, от такой переформулировки 116 ЭЛЕМЕНТЫ ЛИНЕИНОГО ПРОГРАММИРОВАНИЯ [Гл. 3 задача (1) проще не стала, но в новой ее формулировке, оказывается, легче проследить за тем, как изменнется функция Х(и) при изменении небазисных переменных, и можно попытаться выбрать этп переменные так, чтобы в новой точке и ей У было 7(н1)< У(э). Однако если мы начнем изменять все пебазисные Таблица 1 и ~спобокные иа чпены Бааненые неренен- ные и' иа ... иа ,и ,е+1 иа О Ть„+1 У1п о и' О Те .+1 те, и+1 и О тпа - ТМ Функция " А у(р) переагенные снизу, то вряд ли сможем проследить н за изменением функции У(и) и за соблюдением ограничений и~О.
Поэтому мы попробуем изменить лишь одну из небазисных переменных, скажем, переменную иа (г+ 1 < к < и), а остальные небазисные переменные положим равными нулю. Тогда из соотношений (7) получим и = э — 7,аи, ..., ие = ое — 7ыи, ..., и' = н — 7ми, ... и" =й — 7 и' и"+'=...=иа-'=на+'=...=и" =0 (10) или короче й=б — (В 'Аа)иа, и1=0, у=г+1, ..., п, уеьй, (11) а функция (8) заппшетсн в виде Х(и) = у(о) — Лана. (12) Наша ближайшая задача: выбрать номер й. (г+1 < 11 < и) и величину иа ~ О так, чтобы новая точка ш, у которой й-я координата равна и', а остальные координаты определяются равенствами (10), удовлетворяла требованиям Аю = Ь (н1 > 0), Х(н1) < -бу(о) (будет еще лучше, если удастся получить У(н1)<У(о)).
Что касается первого требования Ана= Ь, то как видно из соотношений (7), равносильных (2), оно будет выполняться при любом выборе и". Анализируя знаки величии Лм 7„, нетрудно выяснить можно ли удовлетворить оставшимся двум требова- спмплвкс-мктод И7 ниям: и >О, Х(й)<э" (э), и указать правило выбора нужного номера к и нужной величины и'>О. Л именно, рассмотрим следующие трп взаимоисключающих случая 1 — 111. Случай 1. Справедливы неравенства Л,=(с, В 'А;) — с;<О, 1=г+1, ..., и, т. е. в нижней строке симплекс-таблицы 1 все йп неположительны. Как видно нз (12), тогда невозможно добиться неравенства У(и) < У(и) прп взятом выше специальном способе изменения переменных (10) ни при каких й (г+ 1 < 7г < п) и и' > О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
