1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 12
Текст из файла (страница 12)
Последний алгоритм приводится в следующем параграфе.§ 6. Лексикографический двойственный симплекс-методОписание метода начнем с симплекс-таблицы, форма которой отличаетсяот использовавшейся ранее.Пусть B – двойственно допустимый базис, S ¢ = {t (1), K,t (l )} , l = n - m , –множество номеров небазисных переменных, а S – множество номеров базисных переменных. Перепишем соотношения (7) и (8):(15)xi = zi 0 + å zij (- x j ) , i Î S U {0} .jÎS ¢Добавим к системе уравнений (15) тождественные соотношения xi = xiдля небазисных переменныхxi = (-1)(- xi ) , i Î S ¢.(16)Симплекс-таблица будет состоять из коэффициентов правых частей равенств (15) и (16).61x0MxiMx m +1Mxn1- x m +1K- xnz 00Mzi 0M0z 01Mzi1M-1KKz 0lMzilM0M0M0KM-1KПусть b j = ( z0 j , z1 j ,K, znj )T , j = 0,1,K, l , – столбцы, образующие симплекс-таблицу.
Тогда система (15), (16) эквивалентна векторному уравнению:( x0 , x1,K, xn )T = b 0 +å b j ( - x j ).(17)jÎS ¢Если zrs ¹ 0 , r Î S , s Î S ¢ , то возможно элементарное преобразование базиса, при котором базисная переменная x r заменяется на небазисную переменную xt (s ) . Далее выразим переменную xt (s ) из r -го уравнения системы (15):1( z r 0 + å z rj ( - xt ( j ) ) - x r )z rsjÎS ¢, j ¹ sи заменим ее в правой части (17):zrjæ -1öz÷÷( xr ).( x0 , x1,K, xn )T = ( b 0 - r 0 b s ) + å ( b j b s )( - xt ( j ) ) + ççzrszrsè zrs øjÎS ¢, j ¹ sxt ( s ) =Итак, элементарное преобразование базиса приводит к симплекс-таблице состолбцамиzrjìb s , j ¹ s,ïb ¢j = b j zrsï(18)íï b ¢ = æç - 1 ö÷ b .ïî s çè zrs ÷ø sСимплекс-таблицу будем называть нормальной, если каждый ее столбецb j , j = 1,K, l , лексикографически больше нуля.Описание алгоритма лексикографического двойственного симплексметода.Шаг 0.
Начать с нормальной симплекс-таблицы.Шаг 1. Если симплекс-таблица прямо допустима, то КОНЕЦ (полученооптимальное решение).Шаг 2. Иначе выбрать ведущую строку r по правилу: z r 0 < 0 ,r Î {1,K, n} .62Шаг 3. Если { j | z rj < 0, j Î {1,K, l}} ¹ Æ , то выбрать ведущий столбец sпо правилу:üì 11ïïb s = lex min íb j | z rj < 0, j Î {1, K, l}ý,z rsïþïî z rjиначе КОНЕЦ (задача неразрешима).Шаг 4. Преобразовать симплекс-таблицу, положить t ( s ) := r и перейти нашаг 1.Замечания.1. Если на шаге 3 имеем z rj ³ 0 , j = 1, K, l , то ограничения задачи несовместны.
Действительно, r -ой строке симплекс-таблицы соответствует уравнение xr = zr 0 + å zrj (- x j ) , из которого при x ³ 0 следует x r < 0 .jÎS ¢2. Покажем, что элементарное преобразование симплекс-таблицы на шаге4 сохраняет ее нормальность. Согласно правилу выбора ведущего столбца,æ 1 ö÷÷ b s f 0 . Для доказательz rs < 0 . Так как по условию b s f 0 , то b s¢ = çç è z rs øства лексикографической положительности остальных столбцов b ¢j , j ¹ s ,j Î S ¢ , рассмотрим два случая.а) Если z rj ³ 0 , то b ¢j - b j = -z rjz rsb s ≽ 0 . Следовательно, b ¢j ≽ b j f 0 .æ 1ö1б) Если z rj < 0 , то из (18) следует b ¢j =| z rj | çbj b s ÷ f 0 .
Поç | z rj || z rs | ÷øèследнее неравенство следует из правила выбора ведущего столбца.3. Из описания алгоритма следует zr 0 < 0 , zrs < 0 и b s f 0 . Учитываяz(18), отсюда получим b 0 - b 0¢ = r 0 b s f 0 , то есть b 0¢ f b 0 . Таким образом,zrsбазисы не могут повторяться и, следовательно, метод конечен.§ 7. Геометрическая интерпретация задач линейного программированияПриведем геометрическую интерпретацию задач линейного программирования применительно к следующей паре взаимодвойственных задач, которыеобозначим, соответственно, через P и D :63(c, x) ® min(b, y ) ® maxyA £ c.Ax = b,x ³ 0,Обозначим через A j = ( A j , c j ) T , j = 1,K , n , расширенные вектор-столбцыматрицы A , а через b = (b1, K, bm ,0)T – расширенный вектор правых частейограничений прямой задачи.Определение 12.
Множество K , содержащее с любой своей точкой x всеточки lx при l ³ 0 , называется конусом.Определим линейное преобразование f A : R n ® R m +1 :f A ( x) =nåA jxj ,x Î Rn .(19)j =1Пусть K = f A ( R³n0 ) = {u Î R m +1 u =nå A j x j , x ³ 0} . Очевидны следующиеj =1свойства множества K :1. K – выпуклый конус.2. Вектор (0,K,0) Î K и является его вершиной.3. K порожден конечным числом векторов A j , j = 1, K, n , то есть является множеством точек видаnål j Aj , l j ³ 0 ,j = 1, K, n .j =1Чтобы пояснить введенное определение конуса K , рассмотрим следующую задачу линейного программирования:c1x1 + c2 x2 + c3 x3 ® mina11x1 + a12 x2 + a13 x3 + a14 x4 = b1 ,x j ³ 0, j = 1, K,4 .æ a1 j ö÷ , j = 1, K , 4.Здесь m = 1 , A j = çç÷è cj øu2A1A2A3A4Ku1OРис. 164На рис. 1 приведено множество K для данной задачи.
Очевидно, что конусK порожден крайними лучами, образованными векторами A1 и A4 .Рассмотрим систему уравненийnå Aj x jj =1= (b1 , K, bm , l )T .Будем считать, что вектор c коэффициентов целевой функции прямой задачи P не является линейной комбинацией векторов ai = ( ai1, K , ain ) , таккак в противном случае любое допустимое решение является оптимальным.Тогдаæ ìï nüï öf A ç í x å A j x j = (b, l )T , l Î R ý ÷ = u Î R m +1 u = b + lem +1 , l Î R .çïïþ ÷øè î j= 1Обозначим последнее множество через Q . Оно является прямой в простран-{}стве R m +1 , которая проходит через точку b = (b1, K, bm ,0)T параллельно осиOum +1 . Так как f A ({x | x ³ 0, Ax = b}) =æì nüï öï= f A ({x | x Î R n , x ³ 0}) Ç f A ç í x å A j x j = (b, l ) T , l Î R ý ÷ = K Ç Q ,çç÷ïþ ÷øè ïî j =1то образом множества допустимых решений задачи P при отображении f Aявляется пересечение конуса K и прямой Q .Таким образом, задача P сводится к поиску «крайней» точки пересеченияпрямой Q и конуса K , то есть точки с наименьшей последней координатой.QA1u2A2A3MOB = (b1,0)A4u1Рис.
2На рис. 2 точка M – крайняя точка пересечения K Ç Q , является образомоптимальных решений рассмотренной выше задачи ЛП.Приведем интерпретацию задачи D . Пустьm +1å lk u k = 0k =165(20)уравнение гиперплоскости, проходящей через начало координат. Направляющий вектор (l1 , K, lm +1 ) T гиперплоскости (20) определен с точностьюдо ненулевого множителя.
Будем считать, что lm +1 = -1 . Другими словами,мы не рассматриваем гиперплоскости содержащие ось Oum +1 . Следовательно, существует взаимнооднозначное соответствие между гиперплоскостями,проходящими через ноль, не содержащими ось Oum +1 , и их направляющимивекторами (l1 , K, lm ,-1) T . Пусть y = ( y1,K, yn ) – допустимое решение задачи D , а P y – гиперплоскость, определяемая уравнениемmå yi ui - um +1 = 0 .(21)i =1Подставим A j в (21). Так как y является допустимым решением задачиD , тоmå aij yi - c j £ 0 . Поскольку конусi =1K порожден векторами A j , K ле-жит «над» гиперплоскостью P y , то есть по ту же сторону от гиперплоскости, что и вектор em +1 = (0,K,0,1) .Пустьmå yiui - um +1 = 0– произвольная гиперплоскость, проходящая че-i =1рез O и не содержащая ось Oum +1 .
Если конус K располагается «над» гиперплоскостью, то есть для любой точки u Î Kсправедливоmå yiui - um +1 £ 0 ,=i 1полняетсятогда для любого расширенного вектора условий A j вы-må aij yi £ c j , следовательно,i= 1y = ( y1,K, ym ) является допустимымрешением задачи D .Итак, геометрическим образом множества допустимых решений задачи Dявляется совокупность гиперплоскостей, содержащих начало координат, несодержащих ось Oum +1 и расположенных «под» конусом K .
Это соответствие является взаимнооднозначным и определяется уравнениями (21).Пусть u y Î Q Ç P y . Тогда из определения Q и (21) имеемmumy +1 = å bi yi = z ( y ) .i =1Следовательно, значение целевой функции двойственной задачи на допустимом решении равно расстоянию от точки пересечения прямой Q и гиперплоскости P y до гиперплоскости um +1 = 0 .66Таким образом, с геометрической точки зрения двойственная задача заключается в отыскании такой гиперплоскости, которая содержит началокоординат, не содержит ось Oum+1 , расположена «под» конусом K и пересекает Q в «наивысшей точке» в смысле порядка на оси Oum +1 .§ 8.
Геометрическая интерпретация прямого симплекс-методаРассмотрим б.д.р. x задачи P . Пусть B – его базисная матрица, а N , соответственно, небазисная матрица. Обозначим через P гиперплоскость, натянутую на расширенные вектора базиса As (i ) , i = 1, K , m , и проходящуючерез начало координат. Эта гиперплоскость однозначно определяется базисом B и ее направляющий вектор y есть решение следующей системы уравненийyAs (i ) = cs (i ) , i = 1, K , m ,следовательно, y = c B B -1 .
В параграфе 1 показано, что оценки замещениясимплекс-таблицы, соответствующей б.д.р.x , образуют векторc N - c B B -1 N . Таким образом, если на первом шаге итерации симплекстаблица, соответствующая б.д.р. x , является двойственно допустимой, тоесть c N - yN ³ 0 , то вектор y является допустимым решением двойственнойзадачи, тогда x и y – оптимальные решения.
Их геометрическая интерпретация содержится в предыдущем параграфе.Если существует номер s такой, что c s - yAs < 0 , то это означает, что yнедопустимое решение двойственной задачи, то есть симплекс-таблица недвойственно допустима, а x неоптимальное решение. Геометрически это эквивалентно тому, что вектор As расположен ниже гиперплоскости P .
РассмотримконусKs ,натянутыйmìüK=u å xs ( i ) As (i ) + x s As , x ³ 0 ý .s íu |==i 1îþzis £ 0 , i = 1,K, m , где A s =mнаЕсливектораAs :коэффициенты замещенияå zis A s (i ) , то множествоi =1As (i ) ,K s Ç Q содержит луч,исходящий из точки x . Это следует из существования параметрического семейства векторов x(t ) , которое использовалось при обосновании симплексметода. В этом случае задача (1)-(3) не имеет оптимального решения. Заметим, что это возможно тогда и только тогда, когда конус K s содержит полуось Oum +1 .67Если конусKsне содержит полуосьOum +1 , то тогда{i | zis > 0, i Î {1, K, m}} ¹ Æ и множество K s Ç Q является отрезком, которыйв вырожденном случае может оказаться точкой. Если задача (1)-(3) невырожденная, то отрезок K s Ç Q отличен от точки.
Его крайняя верхняя точка является образом базисного допустимого решения x и лежит на грани K s ,образованной векторами As (i ) , так как yAs (i ) = cs (i ) , i = 1, K, m . Это означает, что эта грань есть пересечение конуса K s с гиперплоскостью P . Тогданижняя точка отрезка K s Ç Q является геометрическим образом нового базисного допустимого решения x(B¢) и лежит на грани, порожденной векторами As (1) , K, As ( r -1) , As , As ( r +1) ,K, As ( m ) , другими словами, B¢ – новыйбазис, образованный векторами As (1) ,K, As ( r -1) , As , As ( r +1) ,K, As ( m) .
Точкипересечения конуса K s и прямой Q являются геометрическими образамирешений, полученных из базисно допустимого решения x элементарнымпреобразованием, которое определяется вектором As .68ГЛАВА 4.ЧИСЛЕННЫЕ МЕТОДЫ УСЛОВНОЙ ОПТИМИЗАЦИИБольшинство существующих методов в нелинейном программированииможно разделить на прямые методы и методы, использующие понятие двойственности.Прямые методы имеют дело с исходной задачей. Они порождают последовательность допустимых решений, обеспечивая монотонное убывание минимизируемой функции, и дают приближенное решение задачи, если итерационный процесс остановить на произвольном шаге.
Их основной недостаток –трудности с доказательством глобальной сходимости.Двойственные методы в этом отношении более сильные. Глобальную сходимость обычно удается получить легче, чем для прямых методов. Их главный недостаток в том, что они не дают приближенного допустимого решения, если метод остановить на произвольном шаге.В данной главе только методы штрафа относятся к двойственным, остальные методы являются прямыми.§ 1. Метод возможных направленийМетоды безусловной оптимизации можно использовать для решения экстремальных задач условной оптимизации. Для этого необходимо доработатьэти методы таким образом, чтобы учитывались ограничения задачи. В этомпараграфе рассмотрен один из таких методов – метод возможных направлений.Пусть имеется точка, удовлетворяющая ограничениям задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
