Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 10
Текст из файла (страница 10)
Если $ =- О и в базис входят некоторые искусственные переменные с нулевым значением, то можно заменить искусственные переменные в базисе гл. 2, симплекс-метод 58 на исходные путем эквивалентного преобразования. Если после преобразования все искусственные переменные из базиса выведены, то полученный вырожденный базис служит начальным базисом для второй фазы. Если же искусствеппу2о переменную х„' певозмоя по вывести из базиса преобразованием из-за того, что аы = 0 для всех у, то зто означает, что исходпая система избыточна. Для примера рассмотрим такие два уравнения: х, + ха+ хэ — — 10, 2х2+ 2ха+ 2хз = 20.
Система, состоящая из этик уравнений, очевидно, избыточна. Используем искусственные переменные для исследования избыточности системы. Получим х,' + х1+ х,+ хз — — 10, х,' + 2х, + 2х + 2х = 20. В коппс первой фазы $ = 0 и одна из искусственных переменных х', (г = 1, 2) войдет в базис с нулевым значением. Преобразование не сможет вывести из базиса переменную х„", поскольку а„= 0 для 1 = 3, 4, 5, что и показывает избыточность системы уравнепий. Рассмотрим стандартные приемы получения начального допустимого базисного решения. Не теряя общности, мы можем рассматривать ограничения задачи линейного программирования в следующем виде: ~~ ацх2 ~~ Ь; где Ь; ) О. Если ограничение представляет собой равенство ~~~ а;,х2 =Ьо то можно добавить искусственную переменнуго а Ч1 х; - ~ - ~ а;2х2 = Ьь Если ограничение представляет собой перавонство 1 ~, а;,хт(ЬМ то добавляется слабая переменная, превращающая неравенство в равенство и используемая в качестве начальной базисной переменной: ~ а2тх2+ г; = Ь;.
2.2. нАПАльныи допустииыи БАзис и Выгождкнность 59 Рассмотрим систевву пв ограничений а11Х1 +а12хг -[ ... +а1аха ) Ь„ Я21Х1 1 Я22Х2 + ° ~'аг Ха )~Ь2 Лт Х1[-а~гхг-'.-" +ЛааХ„) Ь . Пусть дм=тахЬ; (1=1, ..., ш). Тогда можно добавить пв сла- 1 бых и одну искусственную переменные: -'- х' = Ь1, + х" =- Ьг, (4) аПХ1 [-а,гХ2 + ... +а1аՄ— г, а21хв + аггхг +... + ат,х„— гг ЮЖ,Х1+ ЛЖ2Х2-[-... + Л~аХ„ — г,„+ х" =- Ь Пусть Еы Ев,..., Ем обозначают соответствующие уравнения системы (4). Тогда Š— Е1, Š— Ег, ..., Š— Е 1, Е суть уравнения, эквивалентные уравнениям системы (4), с неотрицательными правымн частями Ьм — Ь1, ..., Ь вЂ” Ь Ь соответственно.
Переменные г1, 22,..., г 1, х' можно использовать в качестве начальных базисных переменпых. Рассмотрим доказательство конечносси симплекс-метода, проблему вырожденпости и процедуру, используемую в том случае, когда проверка отношения приводит к нулевому результату (т. е. а10 проверка отношения дает швп — 'а = 0). Для этого необходимо а1в ввести лексикографическое унорядоченне векторов. Вектор называется ленсикоградвичесли положительным (опврицательнвш), если его первая отличная от нуля компонента положительна (отрицательна). Так, вектор [О, О, 2, — 7, 4[ лексикографически положителен, а [О, — 3, 7, 4, 8[ лексикографически отрицателен.
Запись х ~- 0 показывает, что вектор х лексикографически половкителен. Будем говорить, что вектор х, лексикографически больше вектора хв, если (х, — х,) >- О. Так, вектор [О, О, 2, — 7, 4[ лексико- графически больше, чем вектор [О, — 3, 7, 4, 8[, поскольку их разность [О, 3, — 5, — 11, — 4[ лексикографически положительна. Вспомним, что симплекс-метод состоит в систематическом переборе различных базисов, последовательно улуч1пающих целевую функцию до тех пор, пока пе будет получен оптимальный базис. Коли в симплекс-методе ни один базис пе будет выбран дважды, то алгоритм конечен. Заметим, что все элевгенты пулевой строки в симплексной таблице однозначно определяются базисом.
Коли значение ( — 2), записываемое в верхнем левом углу симплексной таблицы, все время увеличивается, то различным значениям ( — 2) соответствуют различные базисы, т. е. в этом случае симплекс- гл. з. снмплккс-мктод метод представляет собой конечный алгоритм, поскольку сущегаз ствует конечное число базисов, не превышающее ( ) .
Таким вав образом, значения ( — з), соответствующие базисам, задают линейный порядок на множестве базисов. Пусть з и г' — значения функции цели в двух следующих друг за другом таблицах. Значение ( — з) может пе измениться при переходе от одной таблицы к другой, если базисное решение вырождено, поскольку проверка отношения дает ппп — = О ага авв и ( — з') = ( — з) — О аа, = ( — з). Когда зто происходит, необходимо принять меры предосторожности для того, чтобы один и тот же базис не повторился и тем самым была бы гарантирована конечность.
Пусть в начальной таблице все строки, кроме, быть моясет, нулевой, лексикографически положительные. (Если нет, то можно добавить искусственные переменные или переставить местами столбцы и переобозначить переменные.) Тогда конечность будет обеспечена, если припять следующее, пенного более сложное нравило выбора ведущего элемента. При выборе ведущего столбца выбирается любое ав ( О, в то время как в обычном снмплекс-методе использовалось а„такое, что ш1п св = с, ( О. Допустим, что в качестве ведущего выбран г-й столбец.
Тогда среди строк с ам ) О (~ = 1,..., т), поделенных на а;„выбирается лексико- графически минимальная. Строка становится ведущей, т. е, лексикографически минимальныи вектор ( —, —,..., — ! опре] ава ан а~а ) !.аы .ы .ы ! деляет ведующую строку. Заметим, что первая компонента этого вектора получается из обычной проверки отношений. Другими словами, если проверка отношений приводит к нулевому результату, то проверяются отношения с числителем, взятым из следующего столбца, и так до тех пор, пока не будет получен ненулевой результат. Если принять это усложненное правило выбора ведущего элемента, то необходимо доказать два свойства: 1) в каждой таблице все строки, кроме, быть может, пулевой, лексикографически положительны; 2) нулевая строка лексикографнчески возрастает после каждой итерации.
Для того чтобы доказать свойство 1, вычтем аы ! — "а, ьавв ' — "в, ..., — ""1 из каждой строки в с аы)О. Поскольку ьавв авв аы 1 —,..., — ! лексикографически болыпе, чем ! —, —,..., ва ! агав ав а !-авв авв а„в эта разность, являющаяся вьй строкой в следующей таблице, лексикографнчески положительна. Для строк с авв(О эта разность есть фактически сумма двух лексикографически положи- Х4. СИМПЛККС-МКТОД В МАТРИЧНОЙ ФОРМК ЗАПИСИ б1 тельных строк н дает лексикографическн положительную строку. Для доказательства свойства 2 заметим, что к нулевой строке прибавляется г-я строка, умноясенная на ~ ~' ~. Поскольку г-я !.
!. строка лексикографически полоясительна, нулевая строка лексико- графически возрастает после каядой итерапии. Пулевая строка к последовательности симплекспых таблиц слуясит для установления линейного порядка на множестве всех базисов. В случае кырожденпостн, несмотря на то, что значение ( — 2) остается Постоянным, асе базисы, соответствующие этому значению ( — 2), упорядочены. Таким образом, ни один базис не мовкет повториться, а значит, симплекс-метод конечен. Рассмотрим для примера следующую таблицу: Нулевой столбец 4- Нулевая строка В качестве ведущего столбца можно выбрать четвертый или пятый столбец, поскольку оба они имеют одинаковые отрицательные относительные оценки ( — 3). Если выбирается четвертый столбец, то ведущей строкой становится первая.
Если выбирается пятый столбец, то ведущей строкой преобразования выбирается вторая строка. Существу4от прнмеръ4, построенные таким образом, что если при нулевом результате в проверке отпошепия всегда выбирать к качестве ведущей строки перву4о из строк-кандидатов, то обычный процесс может быть бесконечным.
2.4. Симплекс-метод к матричной форме записи Рассмотрим задачу линейного программирования: минимизировать г = сх — асо при условиях Ах =Ь, х)0. гл. х симплвнс метОд Эту задачу мо'кно представить в следующем виде: (2) 11усть аоо с аоо а ос Матрица Аа состоит из т + 1 строк и и + 1 столбцов.
Итерация симплекс-метода, рассмотреппая в этой главе, зквивалептпа умножению уравнения (2) слева на следующую квадратную матрицу: 1, (аоо ) а„ ( ~п~з ) где г Ф О и з чь О. Если все столбцы матрицы А разделить на базисные В и небазисные Х, то соотпогпение (2) можно записать как (4) где св и ск — соответствующие компоненты вектора с; хв и хн— базисные и небазисные переменные.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
