Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 9
Текст из файла (страница 9)
2.3. Заметим, что переменная хз заменила в базисе х!. В табл. 2.3 пет отрицательных чисел, аз; ) О (! = 1, ..., 5), т. е. опа оптимальна. Оптимальным реп2епиез! является х, =- 5, х, .= 3, х! = хз = =х,=О. 52 гл, 2. симплекс-нето;! Пример 2. Рассмотрим задачу: минимизировать з = х, -~х хз + 2хз + 8хю 2х, — хз + Зхз — 2х, = 3, — х, + Зх, — 4хз -',- 4х,:= 1, х; ) О (у =- 1,..., 4). при условиях (1) (2) Это представление не является диагональной формой относительно каких-либо переменных. Пусть хз и хз — начальные базисные переменные.
Умножив уравнение (1) на 4 и сложив с уравнением (2), умноженным предварительно па 3, получим Зхз + бх + 4хз — — 1о, что равносильно 5, 5 15 — Х, ' — Хз '-Ха=в 4 4 ' 4 (3) Умпонцив уравнение (1) на 2 и сложив с уравнением (2), получим Зх1+хз+2хз=7 илн, эквивалентно, 3, 1 7 — х,— ' — хз+хз= — ° 2 2 ' 2 (4) Используя уравнения (3) и (4), запизпезз информацию о задаче в виде табл. 2.4. Поскольку в нулевой строке относительные Таблича 2.4 1 хз .хз хз 1 Таблица 2.5 хз х хз хз хз оценки, соответствующие базисным переменным, ненулевые, умножпм первузо строку на 8, а вторую — на 2 и вычтем ик нз нулевой строки.
Результат приведен в табл. 2.5. Поскольку наименьшая отрицателызая оценка располояцена в столбце под х„введем в базис переменную хо Проверка отног15!5 7!31 щения дает ппп ( — ~ —, — ~ — ) ='/з т. е. '~з доляцен стать веду- (4/4 ' 2/27 щим элементом. Результат преобразования приведен в табл. 2.6. 2.З. НАЧАЛЬНЫЙ ДОПУСТИМЫЙ БАЗИС Н ВЫРОЖДЕННОСТЬ 53 Кдинственной отрицательной оценкой является — 6; переменная хе долп;на быть введена в базис.
Из проверки отношения ш!п( —./ —,, — / — ) =1 следует, что ведущим элементом должен (б/б З/З)= Ф стать 'уе. Результат преобразования показан в табл. 2.7. Таблии,а 2.б Таблица 2.Т 1 л2 Ха ХД Х4 1 х2 *а ла Поскольку все элементы а„у (у =- 1, 2, 3, 4) неотрицательны, табл. 2.7 оптимальна. Оптимальным ре2пением является г = 3, х2=2, хе=1 хз=х,=О. 2.3.
Начальный допустимый бааис и вырсжденность В этом параграфе будет изучена техника получения начального допустимого базиса. Пусть задача линейного программирования записана в канонической форме: минимизировать з=. ~З ~суху У=-! при условиях ~ а;,ху.=-Ь; (1=1, ..., Пт), ху > О (у =- 1, ..., П). Все Ь, можно сделать неотрицательными, умножив, если надо, соответствующее уравнение на — 1.
Тогда можно добавить в каждое уравнение искусственную переменную х",') таким образом, чтобы нз искусственных переменных образовать начальный базис х', .Ранх2 ~-а22хз -... -'-а,„ха =-Ь„ -;.аа,х, -' азсха +... '-асах„=. Ь2, х'„-( аанх2 (-атехе+. +омах„=Ь„. ') Искусственные Переменные должны быть веотрнцательнынн. гл.
2. симплекс-мвтод Искусственные переменные можно получить из слабых переменных, используемых для превращения неравенств в уравнения. Действительно, если исходные ограничения задачи линейного программирования заданы в виде неравенств ~э ао ат(бь то, добавив слабую переменную в каждое неравенство, получим ~ %тх1 + Й .= К Если Ь, ) О, то а; можно использовать в качестве начальных базисных переменных. Различие между искусственными переменными х", и слабыми переменными г, состоит в следующем. В оптимальном решении задачи все искусственные переменные долл1ны быть равными пулю, поскольку в исходной задаче таких переменных нет.
С другой стороны, вполне возмо'кно, что в оптимальном решении слабые переменные будут иметь положительные значения. Для того чтобы искусственные переменные стали равными нулю, можно представить целевую функцию следующим образом: з =- ~ оттт+ ,'~~~ М;*1ю где М; — достаточно большие положительные числа. (В задаче максимизации М; доли."ны быть большими по абсолютной величине отрицательными числами.) Этот способ, называемый методом штрафа, предложеп Чарнесоы, Купером и Хендерсоном ~26!.
Идея метода соответствует тому, что искусствепныз1 переменным придаются заведомо большие цепы. Такой способ приводит ь нулевым значениям искусственных переменных в оптимальном решении. Существует и другой способ получения начального допустимого базиса. В этом способе, как и в первом, в качестве начальных базисных переменных используются искусственные переменные. Рассматривается новая целевая функция $, представляющая собой сумму искусственных переменных. Требуется минимизировать с, используя з-уравнекие как одно из ограничений. Если исходная система уравнений имеет допустимое решение, то все искусственные переменные должны стать равными ну:по. Следовательно, минимальное значение 5 = ~ х,' должно быть равно пулю. Если 1 шгв $:> О, то исходная система уравнений не имеет допустимых рев1ений. Если пап $ = О, то можно опустить целевую функцию $ = ~ х', и использовать оптимальный базис $-формы в качестве 2.2.
ИАИАльнын дОпустимый БАзис и выиожденпость 55 2 = С,Х, + САХ, + ... + СЗХп при условиях Ь1~ = Ьг~ аяХ, -', аагхг +... +а,пХЗ а21Х! + а2222 Лс .. ! а2пХ ат1хыг ат2х2 чс + отпхп = Ьт где все Ь| пеотрицательны, Если ввести искусственные переменные функцию ~= Ххм х," и новую целевую то получим задачу: минимизировать $=х,'+хг'+... +х', при условиях — 2 + с1Х1 т сгхг + ° ~ спхп = О, +аПХ, +агата + ..
+а,пХп =Ь„ +а22Х2 + а,гхг +... +аз„хп = Ь„ х,' х," (2) ХтЛ-ат2хг-( атгХ2-Г .. +атпяп=Ьт Если вычесть получим все уравнения, содержащие Ь„из $-формы, +2(2х, +с(гхг — , '... +д„х„ Р сгх2 + с2хг + ° ° ° + спхп = О, + аох, + аггхг +... + а,пхп = Ь„ х" 1 (3) Хт + ат!Х1+ атгхг + ° ° + от пап =- Ьт начального допустимого базиса для минимизации 2. В литературе такой способ называется двухфазовым симплекс-методом. На первой фазе метода находится допустимый базис путем минимизации $, па второй — минимизируется 2 и получается оптимальный базис ((37)).
Рассмотрим в качестве примера следующуго задачу линейного программирования: минимизировать гл, г, симплекс-метОд где с(д = — (ам + ао! + ° ° + а!в!). $о =- (Ь! + Ьо +... + Ь„). Система (3) является диагональной формой относительно — $, — г, х,', „х'. Первая фаза симплекс-метода состоит в минимизации Е при условиях (3). На знак г ограничений не накладызается.
В процессе вычислений, как только искусственная переменная становится пебазисной и ее коэффициент е $-форме положителен, сама переменная и соответству!оп!Ий ей вектор-столбец из дальнейших вычислений исключазотся. Посмотрим, почему это возможно. Заметим, что псе таблицы, получа!ощнеся при работе алгоритма, экзивалептны '). В процессе вычислений па первой фазе имеем $ = ~о+ ,'р о(дхд--' ~"„4хо!, где !з! = О и Й! ) О. Если положить небазисные переменные ху и х;" разными нулю, а $ =- $о, то получим решение. Если задача имеет допустимое решение, то $ = $о = О.
Ото!ода следует, что никакая искусственная переменная х! с !з! ~ О ие может входить в базис с положительным значением. Выше было показано, что искусственные переменные можно испольаозать для выяснения совместности системы уравнений. Покажем, как с помощью искусственных переменных решается вопрос об избыточности системы. Рассмотрил! детально проблему зыронсденности и ее связь с избыточностью. Вспомним, что базисное решение получается иа решения уравнения Вхз = Ь, где  — квадратная подматрица матрицы А, Ах =- Ь.
Если одна или более компонент вектора хЬ равна нулю, это означает, что Ъ моокно выразить через т — 1 или меньшее число векторов. Существует дза случая, когда это возможно. 1. Ранг матрицы А меньше т, т. е. шобая система т столбцов матрицы А липейпо зависима. Используя те же рассуждения, что и в теореме 1.9, можно показать, что в этом случае, если существует базисное решение, то существует вырожденное базисное решение. 2. Ранг матрицы В равен т, но Ъ лежит е выпуклом конусе, натянутом на подмножество векторов из В.
Рассмотрим систему уравнений Ах = Ь (А есть (т х н)-матрица, т ., и) без искусственных переменных. Если система уразпенийизбыточна и совместна, это означает, что ракг строк матрицы А равен рангу строк матрицы [А, Ь] и мепыпе т.
В частности, ранг строк подматрицы В меньше т. Поскольку ранг строк матрицы равен рангу ') То есть описывают одпу н ту же задачу,— Прим. род. 2,» нАчАльный допустимый БАзис и Выгож»»кнность 5т столбцов, любая система т столбцов матрицы В линейно зависима. Из рассмотренного выше случая 1 следует, что любое базисное решение вырождено. Таким образом, избыточность влечет за собой вырожденность любого базисного решения. Обратное неверно Рассмотрим следующу»о систему уравнений: 2х, — х» =3, 4х, — 'х» С-2х»=6, бх» +хз +Зх,=О.
Любое базисное решение вырождено, по система неизбыточна, поскольку она содержит невырожденпу»о матрицу третьего порядка, составленную из первых трех сточбцов. Причина вырожденности здесь та я»е, что в случае 2. Если получено невырожденное базисное решение, значит, существует певырождепная подматрица В матрицы А. Это означает, что система Ах =- Ь пеизбыточна. Таким образом, если существует невырон»денное базисное решение, то система пеизбыточна. С другой стороны, пеизбыточность системы еще не гарантирует существования невырожденного базисного решения.
Расса»отрим для примера следующую систему: + х,=-2, х» -, '2х,=4, — х, +Зх =6. — х, Система неизбыточна, поскольку ее матрица содержит подматрнцу — 1. Первые три столбца не дают допустимого базиса, а любой допустимый базис, содерн.ащий четвертый столбец, вырожден. Таким образом, существовапне невырождепного базисного реп»ения показывает, что система неизбыточпа; существование же выроя»денного базисного решения нли тот факт, что все базисные решения выроя<дены, не помогут выяснению вопроса об избыточности системы. Для этой цели можно использовать искусственные перемонные.
Введение искусственных переменных пе только дает нам начальный базис в симплексном алгорнтмо; их также можно использовать для выяснения совместности и избыточности исходной системы уравнений. Если в конце первой фазы $ ) О, то у исходной системы нет ни одного допустимого решения, т. е. исходная система несовместна. Если н»е в= О н в базис не входят искусственные переменные, то можно начать вторую фазу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
