Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 15
Текст из файла (страница 15)
Среди коэффициентов первой строки а,г = — 3 и агь = — 1 могут служить в качестве ведущих. Поскольку гл. ". двоиствкнный симл;шкс-мктод Таблица «.1 Таблича б.л Хз 1 х! х2 хЗ хз х! Х2 Хз то для ввода в базис выбирается переменная хз. После умножения первой строки на — 1/3 злемент а22 становится равным +1. Затем, используя метод исключения, получаем таблицу 4.2. В табл. 4.2 аз!~)0 (1=1,2,3,4) и а;з- 0 (2=-1,2), таким образом, хз =- 4!3, хз —— 5/3, х, =- х! =- О, з = 3 есть оптимальное решение. Заки!нем задачу, двойственную к задаче (1): максимизировать и2 = — 1 — 4л2+ Зл, при условиях л! <О, — Зл,+л,<3, лз< О, л! .
л2чи о1 л! ~ ~О. (2) Оптимальнып решением двойственной задачи является л! — — — 1, лз -— — О. (Его можно получить при помощи симплекс-метода, превратив предварительно все ограничения-нераненства в уравнения и сделав все переменные задачи неотрицательными (у, уо ) 0) подстанонкой л = у — еу,.) Из 3.3 известно, что верхняя строка симплексной таблицы содеркгит с, = с; — ла!, н если с! ) О, то л — решение днойственной аадачи.
В исходной табл. 4.1 с, .= О, с, = О, а! — — [1, 0), а, = — (О, 1).'Хаким образом, в верхней строке таблицы под х2и х, стоят 0 — ле; .= — л;, в табл. 4.2, например, — л! = 1 и — лз =- О. Итак, оптимальная таблица содержит оптимальные решения как прямой, так и двойственной задач. Всегда имеется возможность выбора: решать ли прямую задачу или двойственну2о, использовать прямой или днойственкый метод.
В приведенном выше примере нецелесообразно было решать днойственную вадачу, поскольку тогда понадобилось бы вводить четыре слабые переменные и задача имела бы семь неотрицательных переменных и четыре уравнения. 1.2. Сто!!вцовлп тлвопопз 4.2. Столбцовая таблица (Бил (81) 2 = аоо + сх при условиях Ах- Ь, х)О. Если ввести слабые переменные з = Ах — Ь ) О, то задачу можно переписать в матричной форме: Н Яп Если — Ь ~ )О, то, полагая з =- — Ь и все небазиспые переменные х =" О, получим прямо допустимое решение.
Подобным же образом, если с ) О, то, полагая з == — Ь и х = О, получим двойственно допустимое решение. Заметим, что 1побая переменная (базисная или нет) выражается через пебазиспые переменные. В исходной таблице базис составляют слабые переменные з =- (2„..., 2„). Перепишем задачу в следующем виде: ШШ2 =аоо Ж1 Жг + ао!з!+ а02х2+ ' ' ' аОоао~ )О, >О, Х0 х„)0, + аоо1. 1 х1+ а01ь 2 хз+ ° .. + а0+ь о х„>~ О, ж„+1 — а0+ь о х0.„а — — ао~., о+ а0+0!, 1х1+ аоод, зхз+... + а„+и, охо >~ О. Симплекс-метод па протяжении всех вычислений сохраняет прямую допустимость ре!пения.
Двойственный симплекс-метод сохраняет двойствеппу1о допустимость. В сиошлекс-методе вначале определяется, какой вектор подлежит вводу в базис, в двойственном симплекс-методе сначала определяется, какой вектор из бависа выводится. Вычисления в обоих методах основываются на методе исключения но строкам. При ш ~ и эксперименты показали, что число итераций, требуемых для решения задачи, обычно колеблется от 2т до Зт. Если по ) п, т. е.
неравенств больше, чем перемеппых, следует использовать метод исключения по столбцам. Рассмотрим следующую задачу: минимизировать гл. о. лвойстввпный симплгкс-катод 90 Табхида 4.8 1 х1 хо хо аа1 ааг ° ° ° аоа аоо хо хо ха+\ Задача сведена в табл.
4.3. Предположим, что исходная таблица двойственно допустима, т. е. но~ ) О (у = 1,..., и). Пусть его —— ш1пайо (в=1, ..., и+их) 4 и ао' =шгп ~и (для всех а„,)О). аоо 3 ао/' Тогда а„, — ведущий элемент. Прибавим к другим столбцам о-й столбец с соответствующим коэффициентом, чтобы аы = О (у = =О,...,и;~~а) и а„,=$. Таким образом, кроме выбора между прямым и двойственным методом, существует выбор между исключением но строкам и по столбцам.
Зто предполагает наличие четырех типов процедур. Унифицировать все таблицы не так просто, и в этом нет необходимости. В практических задачах требуется, чтобы все ограничения имели вид равенств, все переменные были неотрицательными и условия ао~ ~ О и а;о » )О определяли оптимальность таблицы. Процесс решения всегда начинается при аы ) О (нлн аот ) О) и сохраняет это условие для всех таблиц. Проверка отношения выявляет ведущий элемент а„, при помощи критерия Если таблица не является двойственно допустимой, то сначала выбирается ведущий столбец и производится проверка отношения элементов этого столбца к элементам нулевого столбца.
Подобным 4.З. СТОЛБЦОВАЯ ТАБЛИЦА 94 же образом, если таблица пе является прямо допустимой, то выби- рается ведущая строка и производится проверка отноп4епия зле- мептон втой строки к злемеитам пулевой строки. Если проверка отношения дает нуль, т. е. — ~==шш — =О или ~ — ~=пйн — =О, аое ) . аоу аео ' го а„, ~ . а,. ~аее~ 4 а;, то для сохранения прямой или двойственной допустимости таблицы используется лексикографическая упорядочепность. рассмотрим задачу: максимизировать и = 2у, + 4у, + у, + у, при условиях у,.+ Зу, + у4~ (4, 2У4+ Уз (3, уз+ Угуз+ АЗ, уу)О (у = 1, 2, 3, 4).
:1 О 1 — Аа где з — текущие базисные переменные, а х — пебазис44ые переменные. Исключение по столбцам зквивалентпо выбору пового ') Задача (4) енвнвелентне (нмеет то жо онтнмальное решение) задаче минимизации — ш = — 2у, — 4у, — у, — у4 нрн тех же уоловнлх.— Прим. рад, Задача (1) сведена в табл.
4.4. Заметим, что она соответствует минимизации функции — и 4), так что здесь аоу (О. Это означает, что если положить все пебазисвые переменные уу = О (у = 1, 2, 3, 4), то полученное значение и = 2У4 + 4уз + уз + у4 не является максимально допустимым'. В исходной таблице з„л, и г,— базиспые переменные, и таблица прямо допустима. Заметим, что условие аге ~ О соответствует тому, что при равенстве нулю всех пебазискых перемеппых ограничения выцолпяются. Последовательные таблицы 4.5, 4.6 и 4.7 содержат результаты соответствующих итераций метода. Ведущий злемепт уреобразования в каждой таблице помечен звездочкой. Обратите внимание па то, что обозначения строк слева от таблиц не изменяются. Текущие пебазисиые перемеивые ааписываются сверху от таблицы. Проверяя и = яЬ, получаем 13/2 = 1.(2) + 1 (4) + 1)2 (1) + + О (1).
Иак было показано, исходную задачу можно записать в матричной форме: 4,2, СТОЛБЦОВАЯ ТАБЛИЦА множества небазисных переменных. Поэтому можно записать й-И где х' — новые небазисные переменные и 1 а „ +— ага ага ага ага 1 1 Другими словами, Аа умножается справа на Р.
Пусть в задаче линейного программирования ограничения имеют внд равенств, а переменные неотрицательны; тогда, если ограничений меньше, чем переменных, естественно использовать строчную таблицу, а в других случаях — столбцовую таблицу. Несмотря на то что свободную переменную всегда можно заменить двумя неотрицательными, поступать подобным образом пе очень удобно, поскольку общее число переменных при этом увеличивается ').
Поэтому, если исходная задача содержит свободные переменные, большей частью бывает удобнее решать двойственную к ней задачу. Прежде чем записать двойственную задачу, полезно в исходной освободиться от ограничений в виде равенств, поскольку опи будут порождать свободные переменпыс в двойственной задаче. Для этой цели обьгшо используется техника преобразования линейной программы с ограничениями-равенствами в линейную программу с ограничениями-неравенствами, после чего переходят к двойственной задаче.
Преобразованная и исходная задачи должны быть эквивалентны в том смысле, что оптимальные значения их целевых функций равны и моя2но из преобразованной задачи восстановить величины переменных исходной задачи. Имеется четыре следующих стандартных преобразования: 1. Замена уравнения, содержащего неотрицательную перемен- путо а;, неравенством. Предположим, имеется уравнение — 2х, + + 4х2 — 2ха =- 2 и х, ) О. 'когда его можно заменить неравенством 4хэ — 2ха ~ )2.
ГЛ. '. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД 2. Умножение уравнения г на ненулевую константу ) . Подобная операция не изменит исходной аадачи, по двойственная переменная л„', соответствующая новому соотпошенизо, выразится через перемсннузо л„соответствующую старому соотношепизо л/ л ° х 3. Сложение уравнения с другим ограничением (равенством или неравенством). Например, можно прибавить первое уравнение ко второму и полученный результат использовать вместо второго уравнения. Тогда соответствующие двойственные переменные будут связаны следующим образом: л, '= л, — лз, л,' = л,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
