Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 16
Текст из файла (страница 16)
4. Прибавить одно из уравнений ~а„~хз — Ъ„=- О к целевой функции. Такая процедура не изменит оптимального значения целевой функции, а новая двойственная переменная л„' выразится через старую двойственную переменную л„следуюпрззз образом: л„'=л,+1. С помощью приведенных выше четырех преобразований можно сделать так, что неотрицательная переменная х, останется только в г-и уравнении, а в целевую функцию и другие ограничения входить .не будет. Тогда г-е уравнение нетрудно превратить в неравенство. рассмотрим, например, такую задачу: минимизировать 3 = хз + хз + хз + х, при условиях хз — хз+ 2хз — хз = 2, — х,+2хз — хз =1 хз> О (з = 1, ..., 4).
Очевидно, к этой задаче уже можно применить симплексный алгоритм. Однако мы хотим проиллюстрировать описанную технику уменьшения числа равенств в прямой задаче. Запишем последовательпыс преобразования прямой задачи вместе с соответствующими изменениями двойственных переменяых. 1. Прибавив первое уравнение к целевой функции, получим: минимизировать з=2Х,+Зх,— 2 при условиях х,— х,+2хз — х,=2, л,'=лз+1, — х,+2хз — хз =1 х;>О (1=1, ..., 4). 4.2. СТОЛГЦОВАЯ тлн;1н113 аб 2. Прибавив второе уравнение к керзону, придем к задаче: минимизировать 2=2Х,+Зхз — 2 при условиях П1 =Я1 212 ='12 4). 2, получим: — 2 при условиях 2'2-1- Хг— — 2хг+ 4хг — 2хз ху>0 =2, Ц=1, целевой функции, получим Я! -= и1, 4) 5.
Рассматривая хг п х, как слабые переменные в первом и во втором уравнениях соответстзенпо, получигс минимизировать 2=41хг', хз — 4 при условиях Х2 + Хг «» 4хг — 2х, 2, Х22 Хг» Двойственная задача примет внд: максимизировать Зя,""-)- 2ж,""- 4 при условиях я, — 2я',"<1, я1 Ф л2 >0' Хг -Р хг — хг = 3 — х1+ 2хг — хг = 1, ху»0 Ц= 1, 3. Умногкнв второе уравнение на минимизировать 2 = 2Х, + Зх, 4. Прибавив второе уравнение к задачу: минимизировать 2=4х,+х, при условиях Хг+ Х3 Хг =- 32 — 2Х, -)- 4хг — 2хг - — — 2, ху»0 ~у'.= 1, л,"'= я„ яг = я",.!2, ..., 4). гл.
а двоиствкнныи симплекс-мвтол 99 Оптимальным решением двойственной задачи является я"," = 2 и я"," = 1!2; соответствующим решением прямой задачи будет хз — — 4/3 и хз — — 5/3. Возвращаясь к исходной задаче, необходимо положить х~ — — х, = О. Если бы мы решали задачу, двойственную к исходной: максимизировать при условиях я1 — из~ (1, — я~ + 2яг(~ 1, 2я, — яз(1, — я, (1, яо ят — свободкыс переменпыс, то получили бы решение: я,=1 и из=1. Можно проверить правильность решения, взяв результаты преобразованной двойственной задачи: я~ =я1+ 1 и я~ = +— 4.3. Геометрическая интерпретация (Лемке 1141]) В етом параграфе будет дана геометрическая интерпретация как прямого, так и двойственного симплекс-методов.
Допустим, используется прямой симплекс-метод для решения задачи линейного программирования: минимизировать з= сх при условиях ах;=Ь (Ь=[Ьо ..., Ь ), и>т), з=-~ х~>~0 (1'=1, ..., и), и двойственный симплекс-метод для решения двойственной к ней задачи, т. е. максимизировать тг= яЬ при условиях яа,(с, (1=1, ..., и), я ~ ~О.
(2) Рассмотримт-мерное я-пространство. Уравнения лат= с,([=1,... ..., и) задают и гиперплоскостей в атом пространстве. Пересече- ние и полупространств, определяемых неравенствами яа; ( с;, 4.х гкомктгичяскхя пнткгпгктлцня является выпуклым множеством, которое состоит пз допустимых решений и задачи (2).
11а рис. 4.1 приведен частный случай с т .-- 2 и н -= 6. Па рнс. 4.1 гиперплоскость изображается пряхюй. 11ормаль к гиперплоскости на~ ---. с~ задается вектором а;. Выпуклое множество допустимых рен~ений н заштриховано. Рнс. 4Л. Предположим В == 1а~, ае,..., а"1 — множество линейно независимых векторов.
Тогда сувдествует решение не, удовлетворяющее условшо л'ав = — ср (1 — 1 3 3 или н' — ~ЯВ '. 7 т.хх гл. м двоистввнныи симплвкс-мвтод Такая точка я' называется критической точкой. Она задается пересечением т гиперплоскостей. Среди п векторов а„..., а„ и! существует ' систем по т векторов которые могут опре(я — т)!т! делять критические точки.
На рис. 4.1 приведены 14 таких точек А, В,..., ~У. Критическая точка является крайней точкой выпуклого множества, если в пей выполняется условие я'аз ( с; (1 =- 1,..., я). На рис, 4.1 крайними точками являются .О, Е, б, 1Х, 1 и У. Для каждой системы т линейно независимых векторов В = =- [а„..., а 1 можяо найти другую систему векторов р; (~, суть вектор-строки иатрвцы В '), такую, что ( 1, если ~.=.~', [)ш;=бп, б;;= ~ (3) ~ О, если ю~1. Поскольку вектор Ь моя<ет быть выражен в виде Ь=- ~ Х,ап э=1 то, используя (3), получим ~;Ь = )з, откуда Ь= „" (~~Ъ)а~. ю=~ (4) Таким образом, система т независимых векторов образует допустимый базис для задачи (1), если р;Ь ) О для 1 = 1,, т.
На рис. 4Л имеется пять допустимых решений задачи (1), изображенных точками А, В, С, В и Е. Вектор Р~ ортогонален ко всем вектор-столбцам В, кроме а;; Р;Ь вЂ” скалярное произведение и-Ь, которое неотрицательно для допустимых решений задачи (1). Целевая функция задачи (2) ш = яЪ определяет семейство параллельных гиперплоскостей яЬ = й, где й — параметр. Вентор Ь вЂ” нормаль к этим гиперплоскостям. На рис. 4Л оп изобрачкеп перпендикулярным вектором к прямой яЬ =- з. Это означает, что наибольшее значение целевой функции связано с точкой, занимающей наивысшее положение среди точек на рис.
4.1. Согласно теории двойственности, ппп з = з = шах ш — - ш. Таким образом, гиперплоскость яЬ = и = з делит все пространство на две части, в одной из которых расположены все допустимые решения задачи (1), а в другой — все допустимые решения задачи (2). Критическая точка, принадлея ащая этой гиперплоскости и являющаяся допустимой для задач (1) и (2), будет оптимальным решением обеих задач. На рис.
4.1 такой точкой является точка П. упРА жнени я Если две критические точки принадле>ыат т — 1 гиперплоскостям, то они являются соседними. Так, если точка Х па рис. 4Л— начальное допустимое решение задачи (2), то мы движемся в точку Х и затем в точку Р.
Если начальное допустимое решение есть Н, то мы перемещаемся в точку О, затем в точку Р, затем в В. В прямом симплекс-методе элементарное преобразование связано с заменой в текущем базисе одного из векторов на небазисный. Если точка А — начальное допустимое решение задачи (1), то мы перемещаемся либо в точку Е, либо в точку С, в зависимости от того, какой из векторов,АЕ или АС,составляет меныний угол с вектором ( — Ъ). В любом случае на следующем шаге будет достигнута точка .О. Если начальным допустимым решением является точка В, то на следующем шаге может быть достигнута точка О (или С), поскольку и С и В принадлежат одной гиперплоскости с вектором нормали аз.
Упражнения 1. Рассмотрим задачу минимизировать 3 = — 2хь — Зх, при условиях хь — хз+ хь-Р Зхь=. З, 1 хз ' хз+ 2 хь+ 2хь= 2ь хт> О () = 1,..., 5). Решите эту задачу, использовав в качестве начальных базисных переменных х, и хз, выбрав для ввода в базис лексикографически минимальный столбец. Проверяйте правильность решения посредством вычисления па каждом шаге з = лЬ. 2.
Рассмотрим задачу: Ах= Ь) шьп сх ) (А есть( т х п)-матрипв) ххО ) и двойственную к ней. Предположим, что  — матрица оптимального базиса. Покажите, что я = свВ ' — оптимальное решение. двойственной задачи, где вектор св состоит из компонент вектора с, отвечающих базисным переменным оптимального базиса. Используйте тот факт, что условие сх ) лЬ справедливо для любых допустимых решений х и я прямой и двойственной аадач соответственно. ГЛАВА б модиеицировАнныи симплккс-мнтод 5.1.
Введение (Данциг и Орчард-Хелйс (43)) Б симплекс-методе все эломепты симплексной таблицы иересчитыванзтся на каждой итерации. Допустич, исходные ограничения задаются катриной А размера т Х л, а оптимальное решение получается после г-й итерации. Тогда, естественно, для рсгпепия задачи необходимо последовательно найти ~ (т + 1) (и — ', 1) чисел. При вычислениях, как только получена очередная таблица, можно переходить к следующей итерации. Все предыдущие таблицы, включая исходную, могут быть азабытыа.
Предпотожим, что исходная таблица сохраняется. Какой информацией необходимо располагать в этом случае, чтобы получить все элементы текущей табллщы? Пусть нас интересует 29-я таблица. Тогда достаточно знать матрицу В г, соотвстствулощую 29-й таб:шцс, и индексы текущих базисных переменных. Все остальные элементы 29-й таблицы поясно получить иэ элементов исходной таблицы н обращения текущего базиса В 29-й таблицы. Заметим, что я = саВ-т, т, е. текущий вектор я получается умнон;ением вектора сз из исходной таблицы па обращение текущего базиса В '. (Индексы текущих базисных переменных указывают, какие компоненты входят в сл.) Вектор Ь задаотся произведением В лЬ, где Ь берется из исходной таблицы; лвзбой столбец аз получается умнончепием В-т па ан где аэ — столбец исходной таблицы н В ' — обращение текущего базиса. Таким образом, если заданы В ' и индексы базисных переменных, то, используя исходную таблицу, можно получить все элементы текущей таблицы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
