Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 17
Текст из файла (страница 17)
Пусть заданы исходная таблица н матрица В ', соответствующая 29-й таблице. Какие элементы 29-й таблицы необходимы для 'того, чтобы получать матрицу В л, соответствующую 30-й таблице? Такими элементамн явлин~тон компоненты нсбаэиспого столбца из 29-й таблицы, который должен сыть введен в базис, и Ь из 29гй таблицы.
Вектор аз является кандидатом для ввода в бааис, если сэ (0 '). Таким образом, необходимо вычислить с; данной (29-й) таблицы, выбрать среди них с„(0 п затем вычислить а, .= В лае и Ь =- В "Ь. Это дает возможность найти В ' для сле- л) рассматривается задача минимизации.— лерам. реди ;.к ввкдвнив дующей таблицы. Приведенные рассуждения лежат в основе модифицированного симплекс-метода.
Ыодифицировапшай симплекс-метод сохраняет исходную таблицу, а на каждой итерации определяются: строка относительных оценок с, вводимый в базис вектор н текущее значение Ь. Эта информация вместе с обращением текущего базиса определяет В-' для следующей таблицы. Если имеются В-', а; в Ь (сведенные в таблицу размера (т + 1) Х ~ (т +. 2)), то с помощью проверки отношения мол.ко определить ведущий элемент н лровзвести преобразование таблицы, чтобы получить В ' для следующей таблицы. Таким образом, на каждой итерации вычисляется не более чем и — т относительных оценок се, столбец Ь и вектор а;.
Поскольку исходная таблица содержит единичную матрицу размера т Х т, а все относительные оценки, соответствующие столбцам этой матрицы, равны нулю, то в дальнейших вычислениях па месте единичной матрицы будут появляться элемепты матрицы В х, а на месте относительных оценок — элементы вектора ( — л) для текущей таблицы (см. з 2.4). Зная я и В х данной таблицы, можяо найти с~ по формуле са = = ст — пар Если с; неотрицательпо, то ае вычислять пе следует.
Найдя с, ( О, вычислим соответствующий ему вектор аз для введения в базис. Заметим„что В исходной таблице обращением единичной матрицы является сама матрица, а я = О, поскольку я = с„В х и с„= О. Поэтому к единичной матрице в исходной таблице можно добавить столбец П,О,...,01: Это делается для того, чтобы исходная таблица использовалась так же, как и все другие. Решим сначала следующий числовой пример, используя обычный снмплекс-метод, а затем тот же самый пример решим при помощи модифицированного симплекс- метода: максимизировать хэ 102 гл.
з, модиФициговлнпыи симплккс-мвтод при условиях хо +2хз — 2х,— х,=О, — 2хз+ хе+ 'хе=4 хз ', Зх, — хе -,'- 2х, = 2, х; > 0 (1 = 1, ..., 5). Таблица 5.1 х) является исходной. Заметим, что рассматриваемая матрица В» — единичная, следовательно, ее обращением будет тоже единичная матрица. Приведенный числовой пример решается обычным симплекс-методом, как показано в табл. 5.2, 5.3, 5.4 (обратите внимание на небольшое видоизменение формы таблиц). Для проверки убедимся, что для бавпса В» последней таблицы и его обращения В* х выполняется условие В* ° В*-' —.- 1 '): 01 — 2.032=010 Для того чтобы выявить основную структуру модифицированного сизшлекс-алгоритма, достаточно переписать только часть исходной таблицы так, как если бы это была й-я итерация,ипоказать, что остальная часть может быть получена из имегощейся информации (табл.
5.5) и исходной таблицы (исходная табл. 5.1 должна храниться все время). Имеем В*= — 0 1 0 сз=.сз — паз=[1, О, 0) [2, — 2, 3) =2, с,=с,— Яа,=[1, О, О[[ — 2,1, — 1[= 2, се=с,— па,=[1, О, О) [ — 1, 1, 2[= 1з) з) Вместо ( — ее) стоит х„т. к.
исходная задача максимизация зе эквивалентна задаче минимизации ( — ее).— Прин. ред. ') В каждой таблице па месте, где в исходной таблице был начальный базис (в столбцах под хе, хо...), формируется обратная матрица текущего базиса.— Прим. ред. з) В данном примере при вычислении е используется тот факт, что сЕ = О дчя всех ) Ф О. В силу етого е; — с вВ-'а. = Р,ад, когДа ие — базисная переменная и ) ча О; р, — первая строка матрицы В-'.— Прим. ред. гоа Гл. м модиФнциРОВАнныи симплекс-метод тидлиза й.л хо хо хг хз хо хо ьснстаааы Стрииа аао хи «ок х! хг Таким образом, з базис должон быть кводон вектор а,*, =-Во 'а"о —..
0 1 0 1 =. 1 и-гбо 0 1 0 б 4 Поскольку аы =. 1 — единственная положительная компонента вектора ао*, то вектор ао выводится иа базиса. Исключение по строкам с ведущим элементом аы — — 1 эквивалентно умножению слева на матрицу 8 =(в*-'(ь*) 6 Таким образом, получаем следующую таблицу (табл. 5.6). Обращением нового базиса является матрица 2, 0) [О, 1, О) = 2, 2, 0) (2, — 2, 3) = — 2 2, 0) ( — 1, 1, 2] = 1.
2.1. ВВВДЗНИК Для контроля вычислзыз сз и са: сз —:(1, 2, 0) [О, О, Ц= О, с,.=(1, 2, 0) [ — 2, 1, — Ц =-О. Табаа24а 6,6 Кз КаНЕ2заяа242 ХЗ К1 Хз ХЗ К4 бзаРЕКа зяеаак ХО хз В базис следует ввести 1=[0 1 О] [ — 2].=.[ — 2]. Поскольку азз = 1 — единственная положительная компонента вектора а,', то из базиса выводится аз. Исключение по строкам с ведущим элементом лзз эквивалентно умножению слева матрицы условий на матрицу =[О 12], 1 4 2 0 3 2 0 1 1 с, =- (1, 4, 2) [ О, 1, 0[ = 4, с, = (1, 4, 2) [ О, О, Ц.= 2, сз = (1, 4, 2) [ — 1, 1, 2[ =- 7. Для контроля Вычислиз! сз сз.
сз = (1* 4 2) [ 2 — 2 3[ =- О сз=-(1, 4, 2) [ — 2, 1, — Ц=О. Гл. 3. модиФицигованный симплккс-метод 1ос Полученное решение ха =- 20, хг = 16, хз .=- 6 оптимально. Заметим, что в модифицированнои симплекс-методе не обязательно вычислять все сд Как только найдено сз (О, соответствующий столбец может быть введен в базис. 5.2. Изменение исходной информации Поскольку исходные данные задачи линейного программирования не всегда задаются точно, важно знать, как изменение информации.влияет на решение задачи.
Пусть исходная задача имеет вид: минимизировать з =- свхв + скхк при условиях Вхз -(. Ххк =- Ь, х„, х, > О. Рассмотрим ха в качестве базисных переменных. Тогда задачу (1) можно представить в эквивалентной форме (2): минимизировать г = саВ 'Ь-',-(ек — сзВ 'й() хк при условиях хз-1 В 'г(хк =В 'Ь, ха, хк) О. (2) Если хз — оптимальное решение, то 1) ха= В 1Ь> О, т. о. хл прямо допустимо, 2) ск — саВ '1т'> О, т. о. хв двойственно допустимо. Следует заметить, что прямая допустимость ке зависит от вектора с, а двойственная допустимость не зависит от вектора Ь.
Рассмотрим следующие виды изменения информации: 1. Вектор ограничений Ь изменяотся на Ь + АЬ. Поскольку условие двойственной допустимости це зависит от Ь, решение исходной задачи ха остается двойственно допустимым. Решение исходной задачи хв будет также прямо допустимым, если В 'Ь+В-'АЬ>0, (6) Таким образом, поскольку оптимальный базис В исходной задачи определяет двойственно допустимое решение задачи с указанным изменением информации, его можно использовать для пахон;дения оптимального решения, продолжая решепке двойственным симплекс-методом. 2. Вектор с заменяется па с -1- Л (са, ск). Оптимальное решение исходной аадачи остается прямо допустимым.
Оно будет УПРАЖНЕНИЯ $07 также двойственно допустимым, если (ск — свВ 'М) + (Исл — ИсзВ 'р)) > О. (4) Если Исз=0, то условие (4) примет вид Е, — наг > — Иегз (5) 3. Если к условиям исходной задачи добавить новый стол- боЦ а„+, с Ценой е„чо то оптимальное Решение хв останетсЯ оптимальным, если е„.„— яа„ы > О.
Упражнения Решите следующие примеры при помощи модифицированного симплекс-метода. 1. ''Минимизировать з = х, + 6Х, — 7х, + хз + 5хз при условиях з хг — хг — ,'— 2хз 4 Хг+ 3хз 4 х,>0 (у 2. Максимизировать зг = 78хг + 21хз — 124Х, 1 — хз 3 — хе+ха =-5, =-1, ..., 5). + бх„+ 17х, + 10х, прп условиях хз + хз — Зхз + 2хт — хз — Зхз =- 33, бхз — хз + хз + хв — 2хг + '4хз хз + 4хг + хз — 5хз + хз + хз х, > О, 7 =- 1, ..., 9. =- 27, = 86, (Оепвепм ш = 1786, х, — — 92,5, хз .— — 53, хз .— — 33; хг -— — 0 для остальных 7'.) 3.
Рассмотрим задачу линейного программирования: Их =- Ц шах(сх ~, где А ость (тХп)-матрица. х>0 ) В модифицированном симплекс-методе проверка этого условия в точности совпадает с операцией оценивания столбца с целью выяснить, требуется лн вводить его в базис. 1оа гл, ь, модиэицигованныи симплекс-мктод Предположим, что х„— оптимальное базисное решение и В— бааисная матрица етого решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
