Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 20
Текст из файла (страница 20)
Таким образом, взяв О: 0 < О ~ 0«, получим допустимое решение я' вадачи (2) со значение»«целевой функции не меньшим, чем при решении я. Исходя из полученного решения я' можно снова определить множество э' =(1 ) я ૠ— с, = О). Указанный процесс может быть продолжен до тех пор, пока либо будут получены оптимальные регпения аадач (1) и (2), либо выяснено, что задача (1) не имеет допустимых решений ').
Пример 1. Рассмотрим аадачу: найти минимум х=х,— ', хэ+2х»+Ох, т) Очевидно, О, > О.— Прим. рад. и с) если «расширение» задачи (4) — найти шш 2„' э; при условиях »=« а а Ах + 1х = В, э, э«> О,— кевырождеко, то а) суммарная невязка на каждом шаге укаэанного процесса монотонно уменьшается; б) эа конечное число шагов (переходов от одного базисного решения «расширенной» задачи к другому) будет получено овтимальное решение или установаена пераэрешииость аадачн (1).— Прям. Р«Э.
6.2. лгямосдвойстзвнный мгтод 121 при условиях 2х~ — ха + Зх — 2хс = 3, — х, ' Зха — 4ха+4хс=1, х1) О (1=1, 2, 3, 4). Двойственная задача к (6) имеет вид найти максимум ю = Зяа + яа при условиях 2яа — яа ( 1, — я, +Зла(1, Зя, — 4яа (2, (7) — 2яа + 4яа ( 8. $=х~+хэ при ограничениях ха= 3, а ха=1~ х'а>0 (1=1, 2).
(8) Выпишем оптимальное решение задачи, двойственной к задаче (8): (я„яа) =(1, 1), а целевая функция 5=4. Г с1 — яа1ч с,— (0,0)а, 1 О,=п(п [ ) — ' 1 1* ' — и (для наг~0). ! =„, 1 (1, 1) а Таким образом, новое допустимое решопие задачи (7) имеет вид я и+Оси (О, 0)+ —,(1, 1) ( —, —,) . Подставляя значения я' в условия (7), видим„что второе ограничение превращается в равенство. Поэтому вспомогательная задача принимает следующий вид: найти минимум аь ха+ ха 1 Вектор (яы яа) = (О, 0) — допустимое реапение аадачи (7).
При таких значениях вектора ат все ограничения задачи (7) выполняются как строгко неравенства, поэтому множество индексов Х пусто. Выпишем условия вспомогательной задачи: минимизировать 122 ГЛ. З. МЕТОД ОДНОВРЕМЕННОГО РЕШЕНИЯ при условиях — х +х~з=З, Зхз+х2=1, (9) Хз, ХЫ Хз аз О. Оптимальным решением аадачи, двойственной к вспомогательной (9), будет л=(1, '/,) с яЬ=-$='з/з. а,— ( /„'/з) аз 1 — /, З (1 з/з) аз з/з 10 ' Вновь полученное допустимое решение— зз = ( /2 /2) -(- /зз (1~ /3) = ( /з~ /з) Подставляя полученный результат в условия задачи (7), видим что первое и второе ограничения выполняются как равенства.
Остальные ограничения превращаются в строгие неравенства. Следовательно, новая вспомогательная задача имеет вид: минимизировать Ь=ХЗ+Хз при условиях 2х, — х, , 'хз = 3, хз + Зхз + хз 1 а а хо хз, хы хз> О. (10) хз — — 2, хз = 1 прн $ = 0 — оптимальное решение задачи (10). Это означает, что (х„хз, х„х,) = (2, 1, О, 0) — оптимальное решение задачи (6). Заметим, что выполнены условия дополняющей пежесткости: (сз — па,) хз = (1 — (з/з, з/з) [ 2, — Ц) . 2 = О, (сз — паз)хз=(1 — ('/„'/з)[ — 1, 3]) 1=0, (сз — паз)хз=(2 — ("з* '/з)[ 3 — 4[) 0=0 (с,— паз)х,=(8 — (з/„з/з)[ — 2, 4[) 0=0. Зная идею рассмотренного метода, опишем процесс решения примера еще раз с помощью таблиц, подобных симплексным. Таблица 6.17 включает в себя нсходнузо целевую функцию задачи (6), а также функцию $, представляющую собой сумму невязок. Заметим, что в $-строке звездочкой помечены две позиции, расположенные над единичной матрицей.
Числа, появляющиеся в этих позициях в следующих таблицах, равны значениям 1 — пз и 1 — яз соответствеппо. 5.2. ПРЯМО-ДВОЙСТВЕННЫЙ МЕТОД 223 Вычитая из $-строки третью и четвертую строки, получим табл. 6.18, которая является стандартной для минимизации $ с х1 и гг в качестве исходных базисных переменных. Поскольку все коэффициенты в г-строке неотрицательные, л = (О, 0)— допустимое решение задачи (7). Умножая соответствующим образом третью и четвертую строку на (О, 0) и вычитая их из г-строки, получаем ту л«е самую г-строку.
(В вычитапии пе участвуют элементы, соответствующие искусственным переменным.) Результат вычитания не изменит табл. 6.18. Поскольку все коэффициенты г-строки неотрицательны, ни один из столбцов под г„хг, г» и г« не может быть использован во вспомогательной задаче. Вспомогательная задача «заключена» в первых трех столбцах и последних трех строках табл. 6Л8. Иа этой подтаблицы видно, что $ = 4 и 1 — я1 — — О, 1 — лг = 0 или я1 — — 1, я» = 1.
Заметим, что значения ( — ла») записаны в позициях $-строки, а значения (с1— — ла1) — в позициях г-строки. Таким образом, значение 61 определяется, как О,= пп'в — '='= пйп(! — ~, ~ — ~) = Умножая з-строку на 1/2 и прибавляя г-строку, получим табл. 6.19 (в сложении не участвуют алементы, соответствующие переменным х1 н 22). Эта процедура равносильна с/ — на1+ 61 ( — йа1), или с1 — (н + 61н) ап или с, — н'ая Теперь, поскольку коэффициент в г-строке под х» равен нулю, этот столбец может быть использован во вспомогательной задаче. Преобразовав последние три строки табл. 6.19 при помощи итерации симплекс-метода, получим табл.
6.20. Вследствие того что все коэффициенты в $-строке под х1, хг и г» неотрицательны, $ = 10/3 — решепие вспомогательной задачи и оптимальное ре1нение м задачи, двойственной к вспомогательной, задается 1 — я1 = 0 и 1 — яг = 2/3. Иначе говоря, я1 = 1 и л, = 1/3. Значение О, определится следующим образом: =- (! ";! 1 ";!)=ь (я1 "11) ( /2 /2) + /15 (1 /2) ( /5 /5) Прибавляя $-строку, умпожеппую на ЗЛО, к г-строке (исключая элементы, соответствующие искусственным переменным), получим табл. 6.21.
Теперь, поскольку коэффициенты в г-уравнении под х1 и хг равны нул»о, соответствующие им столбцы могут быть использованы во вспомогательной задаче. В табл. 6.21 эти столбцы помечены стрелками. Применяя итерацию симплекс-метода к последним трем строкам табл. 6.21, получим табл. 6.22. Поскольку $ = О, эта таблица оптимальна при г = 3, х1 = 2, х» = 1, х»=0, г,=О. ГЛАВА 7 ПРИНЦИП ДЕКОМПОЗИЦИИ 7.1. Принцип декомпозиции (Данциг и Вулф (46), (47!) Обычным приемом в матричном исчислении является разбиение большой матрицы на несколько блоков, с тем чтобы производить дальнейшие вычисления с каждым из блоков.
Подобный прием бывает особенно удобен, когда некоторые подматрицы имеют специальную структуру, например представляют собой единичные или нулевые матрицы. Последнее замечание относится к тому случаю в линейном программировании, когда матрица А имеет специальную структуру. Необходимо подчеркнуть, что принцип декоашозиции, описанный ниже, менглет использоваться для любой матрицы А, но достоинства этого метода становятся наиболее очевидными, когда матрица А имеет специальную структуру. Рассмотрим задачу линейного программирования: минимизировать а=сх нри условиях Ах=Ь, х)0, Во многих случаях матрица А имеет структуру, показанную на рис.
7.1, где коэффициенты, стоящие вне указанных блоков, равны нулю. Такую структуру может иметь линейная программа, составленная для большой фирмы с несколькими филиалами. Для каждого филиала составлена своя линейная программа, т. е. А;х; = Ьц а для управления всей фирмой выписапа матрица ограничений, включающая все ограничения, относящиеся к филиалам. Некоторые из матриц А; могут быть пустыми, например, в том случае, когда в фирме имеются отделы, но участвующие непосредственно в сфере производства, скажем отдел управления кадрами (отсюда А, — пусто), но в матрице ограничений, относящейся ко всей фирме, эти отделы присутствуют.
Заметим, что вектор Ь задачи (1) также разбивается на р + 1 векторов Ь„..., Ьр. Подобным же образом вектор с разбивается на р вектор-строк см сю... ср. Поэтому задачу (1) мо'нно переписать в следующем виде: минимизировать р з= ~ с;хт э=1 ГЛ. Ь ПРИ1ГПИП ДЕКОМПОЗИПИИ 126 при условиях Р в~~~~ Бух! = Ью 2=1 Атхз = Ь| (! = 1, ..., р), (27 х7> О. Каждое из подмножеств ограничений А7хт =- Ь1 определяет выпуклое многогранное мнояоество ЮР Предположим, что 51 — ограни- о! '!2 о "3 1-в Ьо Лво т! ЛОР А Р я с. 7 1.
чено, и через х!в (1 =-1, ..., 31) обозначим крайние точки многогранника ЯР Тогда любое реп!ение х; можно представить в виде в7 хт =. ~3 ) !тх!1, с;7 = с1хн в1 Л!7> О. Допустим, что известны все хнь Положим ! ! 7 =- Езх!Ь Тогда задачу (2) можно переписать в виде мипиллизировать Р г= ~~~~~ Я~ сыйи 2=1 1=1 ,ь, !Ь2 11'3 ! ! ! ГЛ. 7. ПРИНЦИП ДЕКОМПОЗИЦИИ 128 Относительная оценка отрицательна, т. е.
если сц = сц — (я, н) [!ц, ет] < О. Пусть 12 = (П1 Н2 ' ' '1 "1Р)' Тогда сц = сц — П1ц — ня 'Среди небазисных векторов могут быть векторы из множеств о1, 52 и т. д. Если минимальная относительная оценка для каждого о1. неотрицательпа, т. е. сц О, то текущее решение оптимально. Поэтому станем искать в каждом Ят вектор с минимальной отно.сительной оценкой. Поскольку в данном Ят компоненты я1 одни и те же для всех векторов, то реп1им следующую задачу: найти шш (сц — п1ц) = шш (с — я1 .) хц 1 1 при условии хц й 312 (Другими словами, мы хотим найти вершину многогранника Бн в которой с; — п1; достигает минимума.) Полученная задача является задачей линейного программирования: минимизировать (с; — я)ц) хт при условиях А~х1=Ь1ч х1>~0. (6) Поскольку целевая функция задачи (6) липейпа, минимум ее всегда достигается в вершине, т.
е. в некоторой х1;. Если (с1 я1 ')хц я1(01) то вектор [1ц, е;) должен быть введен в базис, для чего выполняется обычная итерация симплекс-метода. Следует отметить одну особенность. Если вектор Пц, е;) должен быть введен в базис, то, прежде чем выполнять итерацию симплекс-метода, этот вектор необходимо умножить на обращение текущего базиса В 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
