Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 19
Текст из файла (страница 19)
Пусть г; К К вЂ” выпуклая замкнутая функция и существует точка хе такая, что з(хе) = — оо. Тогда Т(х) = — оо У х Е догп,у. Напомним, что двойственной задачей к задаче линейного программирования в общей форме является следующая задача: (Ьу) шах; А у=с, у <О (Р'*) Тес ма двой ре ствеииости. Для пары двойственных задач линейного программирования (Р) и (Р") ( ) (Р") имеет место следующая алыпгрнатива; или значение одной из задач конечно (и тогда конечно значение другой и оба значения совяадают), или мнозкество допустимых элементов в одной из задач пусто (и тогда другая задача либо несовместна, либо имеет бесконечное значение . Донвззтельство.
!) Пусть )5(6)! < со, тогда поскольку по лемме 3 Я вЂ” выпуклая замкнутая функция, то по лемме 4 5(х) > -сю У а Е К По теореме Фенхеля — Моро п.2.! Я'*(6) = Я(Ь). Это означает, что конечно значение двойственной задачи и оба значения совладают. 105 $ 3. Обоснование симплекс-мепизз 2) Пусть Рр = о (еь 5(Ь) = +со), тогда либо а) существует точка ге такая, что 5(хе) = — оо, тогла Я': — +со, следовательно, Я" = -оо, т.е. Вр- = ю (это означает, что множество допустимых элементов а двойственной задаче пусто), либо Ь) Я(х) > — сю у х Е К, тогда по теореме Фенхеля — Моро 5*'(6) = 5(Ь) = +со (это означает, что двойственная задача имеет бесконечное значение), Критерий решения. Пусть х, у — допустимые элементы в задачах (Р) и (Р*') соответственно (х Е В(Р), у б Р(Р")).
Тогда точки х,у являются решениями в задачах (Р) и (Р") соответственно (х Е Ага Р, у Е АгВР") тогда и только тогда, когда (с, х) = (у, Ь) . Доказательство Необходимость Пусть у Е Агу Р тогда у Е В(Р ) и (у, Ь) = Яр-. Аналогично, х Е АгВР, тогда у Е В(Р") и (с,х) = Яр. Значение задачи (Р) при этом конечно (!Яр! < +со).
Значит по теореме двойственности значение двойственной задачи также конечно и оба значения совпадают (Яр — — Яр-). Следовательно, (с,х) = (у, Ь). Достаточность. Пусть В б Р(Р), и' б Р(Р ') и (с,х) = (у 6). Возьмем произвольные допустимые элементы х Е В(Р), у Е Р(Р*'). Это означает, что Ах < Ь, А'у = с, у < О. В силу этих условий на х и у имеем (с,х) = (А*у,х) = (у, Ах) > (у, Ь), Из этого соотношения вытекает, что (с,х) > (у,6) = (с,х) ч х б В(Р). Это означает, что хб Агу Р. Аналогично доказывается, что уЕАгйР'*.
° 3.2. Свойства множества донустнммх точек Рассмотрим задачу линейного программирования в канонической форме (с,х)- шах; Ах=6, х>0. (Рь) Предложение 1. Пусть х = (хн...,х„, 0,...,0) Е К", х; > О, ! = 1,...,й, — допустимая точка в задаче (Рг) (х Е В(Рь)). Тогда точна х является крайней точкой многкгства допустимых элементов Р(Рь) тогда и только тогда, когда столбцы а',..., а" матрицы А линейно независимы. Доказательство. Необходимость.
Пусть х — крайняя точка. Докажем, что тогда столбцы а',...,а — линейно независимы. Доказательство будем вести от противного. Допустим противное, что столбцы и',...,и — линейно зависимы. Тогда существует ненулевой набор множителей Л„...,Ль такой, что 2 Л,а' = О. Значит АЛ = О для вектора ш! Глава 2. Лииейиое программирование 106 Л = (Л„..., ЛыО,...,О) б К". Поэтому точка х(1): = х + 1Л Е Рр, при малых ! как больше, так и меньше нуля. Зто означает, что точка х не является крайней. Получили противоречие.
Значит, наше допущение, что столбцы а,...,а линейно зависимы — неверно. То есть столбцы ь а,..., а линейно независимы. Дастатачнасть. Пусть столбцы, соответствующие положительным координатам точки х линейно независимы. Для определенности будем считать, что это столбцы а,,а . Докажем, что тогда х — крайняя 1 к точка. Доказательство вновь будем вести от противного. Допустим противное, что х не является крайней точкой.
Тогда существуют точки у Е Р(Рь) и х Е Р(Рь), у ~ х, отличные от х и число ! Е (О, 1) такие, что х = 1у + (1 — 1)х. Из этого равенства и условий х = (хц ...,хь, О,..., 0), х; > О, ь = 1,..., й, у, х > 0 следует, что у = (Уц,уь,0,,0), х = (хн...,х»,0,...,0). А из условий Ау = Ь с» ь ь ь 2,'у;а' = Ь, Аг = Ь с» 2',х;а' = Ь следует, что 2',(уг — х;)аг = О. ш! и=! 1=1 Это означает, что столбцы а',..., а" линейно зависимы. Получили противоречие. Значит, наше допущение, что х не является крайней точкой — неверно. То есть х является крайней точкой.
Поскольку количество линейно независимых столбцов не может превышать количества строк матрицы А, то крайняя точка содержит не более гп положительных элементов. м Предложение 2. Пусть (Рь) — невырахсдвниая задача линейнага программировании в канонической форме, х = (х,,,,,,хь,0,...,0) б К", т, > О, с = 1,..., Ь, — допустимая тачка в задаче (Рь) (х Е Р(Рь)). Тогда а) Ь > пь; Ь) точка х является крайней точкой миаэкгства допустимых элементов В(Рь) тогда и талька тогда, когда 1с = пь.
Докаэатеяьсгао. а) Доказательство будем вести от противного. Допустим противное, что существует допустимая точка, у которой менее гп положительных координат. Для определенности пусть это первые Ь координат (й < пь). Рассмотрим множество В = (у Е Кь ! Ау = Ь, у > О), где А: = (а',..., а") — матрица, состоящая из первых 1с столбцов исходной матрицы А. Отметим, что множество В непусто. Пусть 1) — крайняя точка множества В (докажите самостоятельно ее существование). У нее число положительных координат 1 (1 < й < гп) будет меньше пь и соответствующие столбцы матрицы А по предложению ! линейно независимы.
Тогда вновь по предложению 1 точка х = (у,0,...,0) Е К" будет крайней точкой множества Р(Рь), причем число положительных координат 1 у нее меньше пь. Зто противоречит невырожденности задачи. Значит, наше допущение, что существуетдопустимая точка, у которой имеется менее гп положительных координат, неверно.
То есть Ь > гп. 102 а З, Обаеиоваяьт симплекс-метода Ь) Необходимость непосредственно следует из опрея еления невырожаенной задачи (в невырожденной задаче любая ра к йняя точка имеет Дастатачнасть. Пусть х = (хн.,.,х„„О,, .., ) Вр,, х > ь = 1,..., гп — допустимая точка в задаче (Рь). Докажем, что тогда х— крайняя точка. Доказательство будем вести роги от п вного. Предположим противное, что точка х не является крайней. Тогда по предложению столбцы а,..., а матрицы лине А йно зависимы.
Зто означает, что суй Л ... Л такой, что 2, Лгаь = О. шествует ненулевой набор множителей Значит АЛ = 0 лдя вектора Л = (Лн...,,,..., ) А(х+ 1Л) = Ах + 1АЛ = Ах = Ь э 1, а вектор х +1Л > 0 при малых 1 как Л В . Поскольку х;+1Ль > 0 при больше, так и меньше нуля, т. е.
я+ 1Л Е Вр,. 1 = О, то увеличивая ! '„пр !1!, и идем к случаю, когда еще одна координата жнем больше о а х+1Л обратится а ноль, а все остальные по — прежнему ольше или авняются нулю. Таким образом, при некоторо м 1 допустимая точка или равн х+1Л будет иметь менее гп положительных коорд коо динат. Зто противоречит пункту а) данного предложения. Получил рот и п иворечие. Значит, наше предположение, что точка х не является р к айней — неверно. То есть х является крайней точкой. 3 3 докйэйтедьстио симплекс метода Рассмотрим невырожденную задачу линейн рогра ого п ммирования в канонической форме (с, х) — ьпах; Ах = Ь, х > О. (Рь) Напомним, что двонственной к ней являетс у я след ющая задача: (Ь, у) — пнп; А'у > с.
(Рь"') П ожении правила решения задачи в канонической форме мы При изложении нования, Сейчас мы их докажем, оформив утверждение в виде теоремы. Теорема. Пусть х = (хи..., х„„ крайняя тачк очка мнаэкгства допустимых элементов Р(Рь). Тогда: а вектор а1 если ) Ь > О, та вектор х — решение задачи (Рь), : = сьА ' — решение двойственной задачи (Рь'); У:=сь ь и хг < О, та значение задачи Ь) если для некатарага э' сь < О и Я =+ос; рг иены авиа пп, а) и Ь), та тачка х лвлягтсл с с) если нг выполнены условия пп, а новой крайней тачкой мнаэкгства дапустимых элгмгтпав ала при этом возрастет на величину — сь, а разве»кение аьункциаиала при ввктарав х, а,..., а п, раимодится согласна симплекс-методу.
108 й 3. Обоснование симплекс-метода а х! = ~~ а хб + а х) „ )О )=! !1!О Хззз) ХЧУО з=! ОЗНО )ФО Х;Π— азй > О при з = 1,..., гп; х)ауз ) х! = х, — 1„х;, !а!О х;=0 =за+1,...,п, Х)О гь = — >О. Х)ОУО при з Таким образом, ) х) О ) ХОО! 1 =1,,и. Глава 2. Линейное программирование Доказательство. Напомним, что по предложению 1 з1е! Аь Ф О, т.е. матрица Аь обратима. а) Пусть О."О > О. П реобразуем зто условие с учетом определения векторов ж = сьХ, у: = с»А ' е» уАΠ— — сь и матрицы Х (АьХ = А): /з >Ос» — > л — с О «» а > с «» сьХ > с е» уА»Х > с еу уА > с «» А у > с. ной кз Значит, у является допустимым вектором в зад (Р") аче ( ь ) двойственно к задаче (Рь). Кроме того в силу условия Аьхь = 6 (с,х) = (сь,хь) = (уАь,хь) = (Аьу,хь) = (у,Аьхь) = (у,Ь).
По критерию решения и.3.1 х — рещение в задаче ,'Р ), а — ш в двойственной задаче (Рь'*). ( ь), а у — решение Ь) Положим х(Г): = х — 1(хз,О) ( ): — — (, ) + зе (е„..., е„— канонический базис в ВО). тогда х(1) = (хь — гх',0) + ге > 0 т' м > О в силу условия < 0 и Ах(1) = Ах — 1А»х! +1Ае = Ь вЂ” Фаз + Ьау = Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
