Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 8
Текст из файла (страница 8)
ввиде низ при условиях (2) (3) хз — хз + 2хз — — 2, — хз+ х, — хз — — 1, хт)О(у — -1, 2, 3), Перепишем условия (1), (2) и (3) следующим образом: (1') (2') (3') з — х,— хз — х,= О, х, — хз т 2х, — хз + 2хз — хз = 2 Система (1'), (2') и (3') состоит из трех уравнений с четырьмя неизвестньзми. Применяя метод исключения Гаусса, получим сле- дующудо систему: (1") (2") (3") + Зхз — 8„ х, +Зхз= б хз л- хз =- 3- 15 31 5 хз= ш(п (— (3' 1)=3 5 5 Если хз — — —., то х, = 5 — 3 — = О. Представим теперь 3 ' ' 3 в диагональной форме относительно з, х, и хз: з — жз = 3, 1 5 чгхз= 4 ' систему 1 3 х! +хз 4 3 Такая система называется диагояазьяой формой относительно неизвестных з, хз и хз.
Решение з = 8, хз = 5, хз = 3, хз = 0 непосредственно следует из записи в диагональной форме. Заметим, что х, и хз называются базисными переменными, а х, — пебазисной переменной (см. 3 1.5). Так случилось, что в полученном решении х, и хз неотрицательпы, т. е. полученное решение является допустимым, а з = 8. Иа уравнения (1") видно, что, если увеличивать хз, з будет умень-.
шаться; можно выразить з через х, непосредственно: з = 8 — Зх,. Поскольку требуется минимизировать з, увеличим хз, насколько это возможно. Из (2") и (3") видно, что х, нельзя увеличивать неограниченно, так как тогда х, и хз станут отрицательными. В пазпезз случае х, = 5 — Зхз, х, = — 3 — х,. Таким образом, максимальное значение хз, оставляющее х, и хз неотрицательными, получается из условия гл. з.
симплгкс-мктод Непосредственно отсюда получаем решение г =- 3, х, = 4!3, хз =- 5!3, хс .— — О. Если теперь х, будет принимать положительные значения, то величина г будет увеличиваться; таким образом, з = 3 является минимальным значением для з. Способ, примененный для решения задачи (1) — (3) и' есть симплекс-метод, только недостаточно систематически описанный. Прея'де чем воспользоваться методом, необходимо ответить на ряд вопросов. 1.
Пусть дана система уравнений. Рассмотрим пространство решений этой системы. Пространством решений является множество всех точек, удовлетворяющих системе уравнений. Если число переменных равно числу уравнений и матрица коэффициентов невырожденная, то пространство решений состоит нз одной точки, так как система имеет единственное регпение. Если переменных больше, чем уравнений, то пространством решений обычно является прямая, плоскость или пространство более высокой размерности.
Говорят, что две системы совместных уравнений эквивалентны, если опи имеют одно и то же пространство решений. Ткогвмл 2.1. Процедура исключения Гаусса не изменяет пространства решений системы совместных уравнений. Доклзлтнльство. Процедура исключения Гаусса состоит нз двух элементарных операций: а. умножение уравнения Е, на ненулевую константу Й, н замена уравнения Е, уравнением ЙсЕ~,' б. слон'ение уравнений Е,и Ее и замена уравнения Ез уравнением Е~ + Ем Очевидно, если Е, (х) = О, то Й~Е, (х) =- О, и обратно. Из условия Е, (х) =- 0 н Ез (х) = 0 следует, что Е, (х) + Ез (х) = О и Е, (х) = 0 и обратно.
Таким образом, метод исключения не из- ' меняет пространства решений. Например, системы уравнений Е~ (х) + Ез (х) = 0 ~ ~ Е~ (х) = 0 Й~Е~ (х)=0 ) ( Ез(х)=0 эквивалентны. П. В рассмотренном примере мы начинали с допустимого решения х, = — 5, х, = 3, и допустимость сохранялась на протяжении всего процесса. Если бы мы выбрали диагональную форму относительно г, х, и х„то получили бы — Зхз х, — Зхз =- — 4, хе+хе= 3, 2.Е ВВЕДЕНИЕ откуда 2 = — 1, х! =- — 4, еэ =- 3.
Обсуждение процедуры нахождения допустимого начального решения будет проведено в з 2.3. 1П. Если 2-уравнение принимает вид (4) 2 — аы ю+2Х +! — ае, и+2 — ° а. — аэаХ„= аээ где а,! ) 0 (1 .= т + 1,..., п), то почему аээ есть минима22ьное значение 2? Предположим, система представлена в диагональной форме относительно других переменных.
Нельзя ли получить 2-уравнение / РЪ 2 — аэ, „!2х~ц ! — аэ. т!-эхе+2 — .. — азах,', = аоа, (4 ) где аш>~0 и аю<аээ? И почему мы всегда должны представлять систему в диагональной форме? Имеется по крайней мере два способа ответить на эти вопросы. Сначала дадим ответ, для которого не требуется материала первой главы. Заметим, что пространство решений системы линейных уравнений не изменяется при процедуре исключения Гаусса.
Такии образом, решение, удовлетворяющее уравнению (4), является решением исходной системы. В уравнении (4) все переменные неотРиЦательны, слеДовательпо, аэ! ЯвлЯетсЯ ни2кней гРаниЦей 2, если пе рассматривать остальных уравнений диагональной формы относительно 2, е„..., х . (Ограничения пе могут уменьшить пинснюю границу минимизируемой функции.) Если из остальных уравнений диагональной формы следует, что е! ) 0 (1 =- 1,..., В2), то аээ действительно ЯвлЯетсЯ минимальным значением функции Используя материал гл. 1,можно дать другой ответ па поставленные вопросы.
Рассуждения при этом будут более длинными, однако они имеют прозрачный геометрический смысл. Целевая функция 2, если она линейаа, изобран(ается гиперплоскостью. Остальные уравнения также явля!отея гиперплоскостями, и их пересечение вместе с условиями е! ) 0 определяет пространство решений. Поскольку гиперплоскости выпуклы„их пересечение тоже выпукло, и следовательно, пространство решений есть выпуклое множество. Для линейной функции, являющейся выпуклой и определенной на выпуклом множестве, локальный минимум совпадает с глобальным. Уравнение (4) определяет локальный минимум 2.
Кроме того, базисное ре2пение определяет вершину (или крайнюю точку) выпуклого мно кества, а мы знаем, что линейная функция, являясь вогнутой, достигает своего минимума в крайней точке (по теореме 1.13, если существует оптимальное решение, то существует и базисное оптимальное решение). Поэтому мы представляем систему в диагональной форме (относительно определенных переменных), что дает пам базисное решение.
гл. г, симплккс-мвтод 48 2.2. Таблица симплекс-метода рассмотрим линейную программу в канонической форме: минимизировать и г= ~~~ с(х( (=! при условиях и а((х(=Ь! ((=1, ..., и) (т<н), (.=! х(>0 (('=1, ..., и). в диагонал ьной форме относительно — г, Ь; обозяачают коэффициенты диагональной Представим задачу х„,' ..., х„,(с;, а(; и формы) ! сиги = — го ст+! хт+! (!(, т(-(х~ь! + + аг, ти(Хт+! + +ае,х„= Ь(, -; — а!или = Ьг. х! хг хт+ат,т+(хт.и+ ° ° ° +атихи = Ьт. 1Ч. На каком основании мол но утверждать, что метод конечен? Поскольку мы переходим от одного базиса к другому и существует (П ! лишь конечное число базисов (не более ! ) ), конечность гарантирована, если только базисьь не будут повторяться.
Если величина г все время строго уменьшается,то различным значениям г соответствуют разные базисы, что обеспечивает конечность. Однако в задаче на некотором шаге можно получить Ь; = О. Поскольку величина целевой функции изменяется па с; ш(п ~='1, преобразовааы) ние может не изменить целевой функции. Если одному и тому же г соответствует несколько базисов, возможно возникновение зацикливания (И02), (9)). Процедура, обеспечивающая конечность, будет рассмотрена в з 2.4. Ч. Пусть выбрана переменная с положительным коэффициентом в г-уравнепии, а в столбце, соответствующем этой переменной, пет ни одного положительного члена, Тогда значение этой переменной можно сделать сколь угодно большим, причем остальные переменные останутся неотрицательными.
Следовательно, г может принимать любые отрицательные значения, т. е. задача не имеет конечного решения. 2.2. ТАБЛ11ПА СИМПЛЕКС-МЕТОДА 49 Базисным репгением является 2=2». х;=-Ьг (1.=1, ..., яг), х +,—— ... —— -хо=О. Допустим, что все Ь; > О, т. е. Мы получили начальное базисное решение. 11ерепишем диагональную форму в следующем виде: хо +аз, тыхты -Ь ° .. - -аепхп .— --азз Хг ~ аг, т»1Хт»1 ~ ...
+апХп =ого хг -~-аг, т«гхт+1 + ° ° ° +агпхп = ого х»1 ~ ат. »г»!хт+1 где хз=- — 2 аез — — 2»* аз-=с аг»=Ь1. записывается в виде таблицы 1 Хг тг ... Хт З + ат„хп = а,ю, Такая форма обычно хз Верхняя строка таблицы представляет собой выражение хз через все переменные. Каждая строка таблицы задает уравнение, свободный член которого записан в самом левом столбце таблицы.
Слева от таблицы записаны тонущие базисные переменные. Мы начали с таблицы, в которой а;з ) О (г = 1,..., т). Если зто условие выполнено, то таблица называется прямо допусягильой, поскольку базисные переменные, равные аю, дают допустимое решение исходной задачи. Если аз ) О (у = 1,..., и), то таблица называется доойстоенно допустимой, поскольку соответствующее решение является допустимым решением двойственной задачи '). Если одновременно аз; ) О (~ = 1, ..., и) и аж ~ )О (г = = 1,..., т), то решение оптимально.
Симплексный алгоритм можно описать по шагам. О. Начать с таблицы, где а,з ) О (г = 1, ..., т). 1. Если все а„. ) О, конец. Текущее решение является оптимальным. В противном случае среди а»2 ~ О выбрать минималь- 1) Термины «двойственно допустимый» и «двойственная задача» будут объяснены в гл. 3. Здесь условия е„; ) 0 означают, что значение г пе может быть уменыпено зз счет возрастания любой пебазисной переменной от нуля. 4 т.хт гл. 3. сими:1ккс-мктод иый.
Пусть а«, = поп а„. ( О, т. с. ૄ— минимальный отрицательный элемент. Столбец в называется ведущим столбцом. 2. Среди а1,)О найти а„„такое, что — "«=ппп — 1«(1=1,... авв в а1в ..., т), т. е. среди поло»кительных элементов столбца в найти дающий минимум отношению — '" . Элемент а„, называется ведусчв щим элементом, Строка г называется ведущей строкой.
3. Использовать процедуру исключения Гаусса так, чтобы все коэффициенты в в-м столбце, кроме а„„стали нулевыми, а авв стал единицей. Заменить базисную поременпу»о х„на х, слева от таблицы. Вернуться к шагу 1. Пример 1. Рассмотрим задачу: минимизировать з =11 — х,— х« — х», при условиях х1 + х, — х, + 2х, = 2, х,— х»+2х,— х» =1, х;)О (у=1, ...в 5). Перепишем се в следующем виде: х» = — 11, 2х, = 2, — х, — х«вЂ” х1 +х» — х,+ т, — х» + 2х«вЂ” х» — — 1. Полученная запись является диагональной формой относительно — з, х1, х,. Запишем х1, х» слева от табл. 2.1, чтобы показать, что Алгоритм работает и в том случае, когда на гааге 1 выбирается л»обое а«; = с; < О.
Критерий ш1п с; ( О использовался по аналогии с «паискорейшнм» спуском. На шаго 2 операция отыскания ппп — 1«для выбора ведущей строки называется проверкой отноа1в щения. Опа используется для получения в результате преобразования а1» ) О. Шаги алгоритма повторяются до тех пор, пока на 1-и шаге все элементы нулевой строки пе станут неотрицательными. Тогда, если положить в текущей таблице базисные переменные, записанные слева от таблицы, равными а;«, будет получено оптимальное решение. Решим пример, используя симплсксную таблицу.
51 2.2. ТАБЛИЦА СИМПЛЕКС-МЕТОДА Таблица 2.1 1 х! х2 хз х4 хз Хг они являются баэиснызси переменными этой таблицы. Волн положить базисные переменные равными числам из О-го столбца, то получим допустимое решение. В О-й строке имеется три отрицательных элемента с одним н тем же значением (в т 2.3 будет дано правило выбора в таких случаях). Произвольно в качестве ведущего выберем столбец при х,. В этом столбце имеется только один положительный элемент аз! = 2; выберем его в качестве ведущего. В таблице он обозначен звездочкой.
Разделив все элементы ведущей строки на ведущий влемент, получим на месте аз! единицу. Затем применим процедуру исключения Гаусса, чтобы сделать аы = О (2 = 0,1). Результат приведен в табл. 2.2. Заметим, что в этой таблице переменная хз Таблица 2.2 Таблица 2,2 Х! Х2 Хз Х! 1 х! х2 хз х4 ;22 заменила в базисе хз (стала базисной). Среди отрицательных элементов О-й строки можно выбрать либо х„ либо хз. Произвольно выберем в качестве ведущего третий столбец. В третьем столбце только элемент а22 положителен, он и выбирается в качестве ведущего элемента. Результат соответствующего преобразования показан в табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
