Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 18
Текст из файла (страница 18)
а) Пусть вектор Ъ заменен на Ъ -~ Хо', где Х вЂ” 'скаляр, а о— ненулевой вектор из Ь . Найдите условие, при котором базис В является оптимальным для любого Х ) О. б) Пусть вектор с заменен на с + Хй, где й — ненулевой вектор из Е"', у которого компоненты, отвечающие базисным столбцам, равны нулю. Найдите условие, при котором базис В является оптимальным для всех Х ) О. Объясните свои ответы. ГЛАВА 6 МЕТОД ОДНОВ1 ЕМЕННОГО РЕШЕНИЯ Ш ЯМОЙ И ДВОЙСТВЕННОЙ ЗАДАЧ,~ 6.1.
Взаимный метод решения прямой и двойственной задач (Ванинский и Гоморгг 171 и Тралл 1184]) хо аоо ( аоох о + аогхг ~ ° ° ° + аоохи при условиях — хоп -'=ам —.анхг +а1гхг .~. ° ° ° -( атхо и О, ...;-а ох„(0, л>0, х„>0, — хоом = а~о -ь аоихг+ а~гхг+ и двойст пенна я: максимизировать Уо = аоо -~ агоУ и - агоУо ог ~ ° + атоУо+го при условиях >О, >О, Уо+ о Уота уоо >О, Уг=-аоо —, анУоы (- аг1Уо г —, ° ° +аоаУ~~~>0 (2) Уо = — аоо ! аооуо+о+агозо г "' ° ° +ао оУо~о1)~0.
Таблица 6.1 представляет собой компактну~о форму записи обеих задач. Опа содержит веге пеобходиггу~о информацийке о задачах (1) и (2); х,, хг,..., хо — небазисные переменные прямой Сппплекспые таблицы, описанные в предыдущих главах, состоялп нз (т + 1) х (т -',— и -'г 1) нли (т -,'- и + 1) х (и + 1) элементов. В этой главе рассматривается таблица раамера (т + 1) Х (и — ' 1), которая обобщает ранее рассмотренные таблицы. Лусть дана пара двойственных задач: прямая: минимизировать ГЛ. О. МЕТОД ОДНОВРЕМЕННОГО РЕШЕНИЯ ' !го Габлаяа б'.1 х! = ао = — *а.!! Уаы =Уа =Уо 'У! задачи, а у„+!,.у„+„..., у„тм — небазисные переменные двой- ственной. Базисные переменные обеих задач выражены через соответствующие небазисные переменные.
Рассмотрим два типич- ных уравнения из таблицы: а о — , 'аях, +... л-ацх! + ... +агах„= — ходи' (3) ао;+ацу„,-'- ...— ', ацуал!+... +а,„;у„, =уы Если ац — ненулевой элемент (! ~ О, ! Ф 0), то он может быть испольаован в качестве ведущего. Это означает, что переменная х! заменит в базисе хал!, а У„+, заменит в базисе пеРеменпУго УР Поделив уравнения (3) на ац и выделив ху и у„+о получим а!а ...—, :— х„;+,„+ — х„= — х;, ац ац 1 ам! а.УУ ' а" У"т~ ац и ао ац — + — ху ац ац (4) аоц а! ! — — — — уау!— ац Выражения (4) можно испольаовать для исключения небаэисных переменных х! и у„т! в любом уравнении из табл. 6.1.
Результаты преобразования можно проследить по табл. 6.2 и 6.3, где а— ведущий элемент, )о — произвольный элемепт ведущей строки, у — произвольный» элемент ведущего столбца, б — элемент из того же столбца, что и р, и из той яое строки, что у. Все переменные, кроме соответствующих ведущему столбцу и веду!цей строке, остаются после преобразования на прежних местах.
Базисные решения для обеих аадач можно получить иэ таблицы, положив небазисные переменные равными пулю. Текущие небаэисные переменные записываются сверху или слева от таблицы. Напри»!Ор, табл. 6.4 получается иа табл. 6.! после одной итерации.
Соответствующие базисные решения имеют вид',— х,',.~! —— П2 г;1. а .мнтод Одпонгвминпого Ркшвпия Базисное решение прямо допустимо, если а'„< О (1 = 1,..., т), и двойственно допустимо, если а„'; > О (1 = 1,..., и). Если одновременно а';о < О (1 =- 1,..., т) н а,'1 >~ О (1 =- 1,..., и), то получено оптимальное решение обеих задач. Для примера рассмотрим табл. 6.5. Одна итерация с помеченным звездочкой водущим элементом приводит к оптимальной табл. 6.6.
Заметим; что табл. 6.5 прямо допустима, поскольку а1„< О (1 = 1, 2), но условие двойственной допустилюсти пе выполнено, так как аоб О для некоторых 1. Симплекс-метод, используемый для решения прямой и двойственной задач, можно рассматривать как конечную последовательность таблиц, эквивалентных паре двойствопных задач. Каждая таблица получается из предыдущей за олпу итерацию с использованием ранее описанного правила выбора ведущего эломепта.
В результате либо получается оптимальная таблица, либо обпаруживаетсн несовместность ограничений. Пусть 1бб и 8 обозначают соответственно неотрицательные и неположительные элементы. Тогда послодпяя в последовательности таблиц может быть лишь одной пз следующих: 6.7, 6.8, 6.9. Таблица 6.8. Ограничснин ириной задачи носониостны Таблица 6.9.
Ограничении двойственной задачи иссивмостны Таблица 6.7. Оитнмал ьнан таблица (эс) а„ , а;- Указанное правило выбора ведущего элелсепта сохраняет пряму1о допустимость ка11дой таблицы из последовательпости таблиц и обычно умепынает значение аоо. В вырожденном случае а„о = О, т. е. после итерации зпачепие а,„не изменяется. Начальная таблица прямого сиашлекс-метода прямо допустима, т.
е. а;о < О (1 > 1). В нУ:1евой стРоке вь1биРаетсЯ ао; < О. (Если аоб >'О для всех 1 > 1, то таблица оптимальна.) Если а11 < О. для всех 1, то система ограничений двойственной задачи несовместна, а целевая функция прямой задачи па множестве решений не ограничена.
Если аы > О для некоторого 1, то н качество ведущего выбирается элемент аы по правилу зл. ВЭАимный метОд Решвния 11з Доказательство конечности симплекс-метода основывается на том, что существует не более ( ) различных возможных мнозкеств базисных переменных. В случае вырожденности, чтобы избежать зацикливания, можно ввести лексикографическоо упорядочение векторов х. Начальнан таблица двойственного симплекс-метода двойственно допустима, т. е. аа~ 0 (у ) 1). В нулевом столбце выбирается аш ) О. Если ац ~ )0 для всех у, то система ограничений прямой аадачи несовместна, а целевая функция двойственной задачи на множестве допустимых решений не ограничена. Если ац ( 0 для некоторого у, то ведущий элемент ам выбирается по правилу — "= шш! — "~ (ац(О).
ам . ~ ац (6) Правило проверки отношения сохраняет двойственную допустимость последовательности таблиц и обычно увеличивает значение ааа. Используя в качестве начальной любую таблицу, можно с помощью метода одновременного реп~ения прямой н двойственной задач укааать последовательность итераций, которая приводит к одному из трех видов симплексной таблицы, представленных табл. 6.7, 6.8 или 6.9. Для обоснования этого факта необходимо ввести следующие определения и обозначения. Верхшою строку таблицы Т обозначим через Л (Т) и будем называть характеристической строкой, а левый столбец обозначим через С (Т) и назовем характеристическим столбцом.
Левый верхний элемент таблицы Т назовем характеристическим и обозначим через 8 (Т). Характеристическая строка )т (Т) без 8 (Т) обозначается через Л' (Т), а характеристический столбец С (Т) без г7 (Т) — через С' (Т). Таким образом, таблица Т является прямо допустимой, если С (Т) ( О, и двойственно допустимой, если В' (Т): О.
Если начальнан таблица прямо или двойственно допустима, то использование соответственно прямого или двойственного симплекс-метода приведет к заключительной таблице одного из трех видов: табл. 6.7, 6.8 или 6.9. Если начальная таблица Т, не является прямо или двойственно допустимой, то выделим такую последовательность таблиц Тц ... ..., Т„, что 1) каждая таблица ТА является подтаблицей в ТА „ 2) все Т, (1 нечетно) прямо допустимы и 3) все Тт (у четно) двойственно допустимы. Например, если Т, не является прямо допустимой, то выделим такие строки в Т„что а;а ( О, а в качестве характеристической строки возьмем строку с аю ) О. Полученная таким образом подтаблица Т~ таблицы Та будет прямо допустимой.
Если Т1 содержит С' (Т~) ( 0 или принадлежит одному из типов, указанных в табл. 6.7, 6.8 или 6.9, то последовательность 8 т. хт 114 Гл. 6. метод ОднОВРеменнОГО Решения подтаблиц обрывается на Т,. Если С' (Т1) ( О, то составим табли- цу Тз из строк, для которых а16 — — О. Столбцами Т, станут те столбцы Т„для которых аа! )~ О.
В качестве характеристического столбца + таблицы Т, возьмем любой 0 столбец Т1, у которого 0 7 т, ао! ( О. Описанная про- 0 цедура схематически изображена на рис, 6.1. столбцы и строки поре- + ставлены, чтобы яснее показать структуру таблиц. Если двойственно допустимая подтаблица Т, содержит нули в характеристической строке, то рассмотрим характеристический столбец и те столбцы Тз, верхние элементы которых равны нулю.
Из этих столбцов выберем элементы, стоя- щие в строках с неположитечьными левыми членами. Эти элементы вместе с характеристической строкой, выбранной из строк Тз с положительными левыми членами, образуют подтаблицу Т,. Р и с. 0.1 Тасаиза й.!О Результат описанного процесса показан в табл. 6.10. Последовательность таблиц обрывается на Т„если Тз имеет вид 6.7 или 6.8, или Л' (Т) ) О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
