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