XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 13
Текст из файла (страница 13)
Таким образом, выпуклая линейная комбинация любых двух элементов из Я содержится в нем, и, следовательно, Я вЂ” выпуклое множество. ~ Теорема 3.3. Допустимые базисные решения задачи (2.11) линейного программирования в стандартной форме являются крайними точками множества Ч' ее допустимых решений. т < Пусть Уо = (уо ... Уь~ 0 ... 0) — допустимое базисное решение рассматриваемой задачи линейного программирования. Предположим, что Уо не является крайней точкой множества допустимых решений Я. В этом случае существуют две разт личные точки Уь = (у1ь ... У~я,), и =1, 2, этого множества, для которых Уо = ЛУ1 + (1 — Л)Ут, где 0 < Л < 1. Таким образом, лу,1+ (1 — л)у'= о, 1= ь+~, ю. А так как Л > О, 1 — Л > О, у1 ) 0 и уу ) 0 для всех у = 1, Л1, то у' = у~у = О, 1 = 1,+1, Л1.
Поэтому, если А = (а ... ам), то Б Ь ~ У1а.=В, ~~1 У а =В (у — У.)а. = Оь. Но столбцы а, 1= 1, Х, матрицы А являются линейно независимыми, так как, согласно договоренности, являются базисными. Поэтому у — у = 0,,1 = 1, Ь, и У1 — Уз, что противоречит 1 2 исходному предположению о двух различных допустимых решениях У1 и Уз из Я. Итак, гипотеза о том, что Уо не является крайней точкой множества допустимых решений Я, оказалась ложной. ~в Теорема 3.4.
Крайние точки множества Я допустимых решений задачи (2.11) линейного программирования в стандартной форме соответствуют допустимым базисным решениям. < Пусть матрица А = (а1 ... ая1) Е М1,ы(К) имеет ранг К8А = Ы < Лс. Предположим, что Уо = (уо ... Уо 0 ... 0) — крайняя точка множества Ч допустимых решений и уо > 0 при .1 = 1, ж Докажем, что в < Ь, т.е. что Уо — допустимое базисное решение. Предположим, что в > Ь.
Тогда столбцы а, 1= 1,л, матрицы А являются линейно зависимыми и существуют такие коэффициенты Л,, что ~~1,Луа, = Е~, ,'1 ~Л,~ > О, Пусть 1 С (1, 2, ..., я) — совокупность индексов 1, для кото- рых ~Л,! > О. Если уо р=ппп — ', Л=(Л1 ... Л, 0 ...,0) бК то р > О, АЛ = Оь и векторы Хь = Уо — ( — 1) рЛ, й = 1, 2, 90 3. СИМИЛЕКС-МЕТОД удовлетворяют условию неотрицательности, т.е. Х1 > с1щ и Хз > йк.
Кроме того, Уо б Я, т.е. АУо = В и АХь = АУо — ( — 1)"рАЛ= В, 1= 1,2. Таким образом, ХОХз Е Я и Уе = 0,5(Х1+ Хз). Следовательно, Уо не может быть крайней точкой для Я, что противоречит выбору Уо и означает ошибочность предположения в > Ь. ~и Замечание 3.1. У множества Я допустимых решений, заданного согласно (3.8), где Ь < Ф, число крайних точек, а следовательно, и число допустимых базисных решений, конечно К! и не превышает Ск —— — ' и(ж- ь)Г Замечание 3.2. Если множество Я допустимых решений, определенное согласно (3.8), ограничено, то оно является замкнутым выпуклым множеством с конечным числом крайних точек.
Можно показать, что любая точка такого множества может быть представлена в виде выпуклой комбинации его крайних точек. Теорема 3.5. Если в некоторой точке множества Я допустимых решений задачи линейного программирования (2.11) ее целевая функция достигает максимума, то она будет принимать максимальное значение хотя бы в одной крайней точке множества Я. Если целевая функция достигает максимума в нескольких крайних точках множества Ч, то она достигает максимума и в любой их выпуклой комбинации. ° я Сначала предположим, что множество допустимых решений Я задачи линейного программирования (2.11), определяемое согласно (3.8), является ограниченным.
Пусть Уь, й = 1, К,— крайние точки множества Я и Уе е Я вЂ” точка, в которой целевая функция ( = ГУ достигает своего конечного максимума. Тогда (см. замечание 3.2) существуют Ль, й = 1, К, такие, что К К У=~ ЛУ, С Л=1, Л >0, й=1,К. 3. Ь Оеновнме утвеРждения линейного нрогРаммиро я 91 При этом, если У вЂ” такая крайняя точка множества Я, что ГУ = шахгУе, то ЙеК К К К гу, = ~ л,гу, < ~л,гу = гу'> л, = гу. я=1 Ьи1 Ьи1 Но Уе — точка максимума целевой функции, т.е.
ГУо > ГУ для любого У б Я. Поэтому ГУе = ГУ и существует хотя бы одна крайняя точка (точка У), в которой целевая функция достигает своего максимального значения. Пусть теперь целевая функция 1 = ГУ достигает своего максимального значения Ф в крайних точках У*, 1 = 1, 1, т.е. Ф= ГУ* юбой элемент их выпуклой комбинации имеет вид ~. Л1 = 1, Л, > 0, Зец Таким об разом, значение целевой функции для этого элемента равно: л Г~ =,'~ Л,ГУл=~ 'Л1Ф=Ф~Л,=Ф. 1и1 1=1 йец ~(оказательство утверждения в случае ограниченности множества Я допустимых решений завершено. П усть множество Я допустимых решений не является ограниченным.
Если существует оншилеальиое решение У', то к ограничениям, определяющим множество Я допустимых решезий, всегда можно добавить ограничение У < У', которое не Эовлияет на максимальное значение целевой функции, но пре,вратит Я в ограниченное выпуклое замкнутое множество. ~и В силу основных теорем линейного программирования, доКазанных выше, для нахождения оптимального решения любой адачи линейного программирования достаточно исследовать )лишь ее допустимые базисные решения. Это связано с тем, что З.л.
Симплекс-метод при иэвестиом допустимом бвэисном решении 93 3. СИМПЛЕКС-МЕТОД 92 все допустимые базисные решения являются крайними точками множества допустимых решений (см. теорему 3.3). Число допустимых базисных решений зависит от числа базисных миноров матрицы А и в общем случае может быть достаточно большим. Поэтому полный перебор всех допустимых базисных решений, как метод решения задачи линейного программирования, не эффективен и нужен другой метод, который на каждом этапе своей реализации позволяет переходить от одного допустимого базисного решения к другому, лучшему по сравнению с исходным в смысле значений целевой функции.
3.2. Симплекс-метод при известном допустимом базисном решении В этом параграфе рассмотрим задачу (2.11) линейного программирования в стандартной форме, для которой известно допустимое базисное решение. Ксть общий метод определения допустимого базисного решения (см, 3.3). Однако в частном случае задачи линейного программирования вида (2.1) допустимое базисное решение можно найти непосредственно из системы ограничений задачи. А именно, если в задаче (2.1) нет ограничений типа равенства или типа „больше или равно", т.е. если 1з — — 1з —— О, а 1ь — — 11, 2, ..., т), причем все коэффициенты 6; неотрицательны, то переход к задаче линейного программирования в стандартной форме путем введения неотрицательных переменных х„+ы ..., х„+ (см. 2.2) приводит к задаче п арьхь+х„+,. — — 6;, ь= 1, т; я=1 х .
> О, 1 = 1, о+т Нетрудно увидеть, что в задаче с такими ограничениями вектор У=(0 ... О 6~ ... 6 ) ~К"+ (3АО) является допустимым базисным решением. Отметим, что к описанному случаю сводится задача вида (2.1), в которой нет ограничений типа равенства (1з — — О), а коэффициенты 6; в ограничениях типа неравенства удовлетворяют соотношению 6; > 0 при 1 Е 1ь и соотношению 6, < 0 при ь' б 1з. Действительно, достаточно каждое неравенство с индексом ь' Е 1з умножить на число — 1, в результате чего изменится и тип неравенства, и знак правой части неравенства, т.е. мы придем к случаю 1з = 1з се О и 6; > О, ь' = 1, т.
Приступим к изучению симплекс-метода при известном од пустимом базисном решении, которое будем называть начальным базисным реиьением. Пусть задана задача линейного программирования в стандартной форме (2.11), причем первые Ь столбцов а матрицы А в представлении (2.11) являются базисными столбцами, соответствующими начальному базисному решению. Для удобства дальнейших рассуждений матрицу Аь, столбцами которой являются базисные столбцы А назовем базисом рассматриваемой задачи линейного ььрограммнрованил, или просто базисом.
П ри сделанных допущениях и обозначениях (3.2) уравнение ( . ), связывающее векторы Уь и У, базисных и свободных (3.31 переменных модели, может быть представлено в следующем виде: Уь+Аь ~А У' Аь В (3.11) Р-"*и при записи целевой фднкиии 1(У) = ГУ в (2.11) восп зоваться представлением (ЗА) вектора У и ввести обозначения Гь=(Ъ ... у,) Г,=(т,+, ...
у, ), (3А2) то Г=(Гь Г,) и 1(У) = ГьАь ~В+ (Г, — ГьА ьА,)У,. (3А3) аметим, что матрица коэффициентов при базисных переменных модели уь, /с =1, Ь, в (3.11) является единичной, а в (3.13) 3. СИМПЛЕКС-МЕТОД нулевой. Кроме того, допустимое базисное решение, существо- вание которого предполагается, представимо в виде (3.5) и ему соответствует значение целевой функции Хо = ГьА, 'В, (3.14) определяемое равенством (3.13) при У, = Оу ь. Таким образом, из (3.13), (3.14) следует, что ~(У) = ~о+ (Г, — ГьАь ьА,)У„ (3.15) и коэффициент при свободном переменном у в правой части равенства (3.15) для определения значения целевой функции 1 равен (см.(3.12) и замечание 2.1): (3.16) Н,='б — ГьАь аб у=Ь+1 1У Идея симплекс-метода состоит в том, чтобы исходя из на; чального допустимого базисного решения (3.5) найти новое допустимое базисное решение, исключая для этого некоторой столбец а; из начального базиса Аь и заменяя его одним из не- базисных столбцов а матрицы А, где ь = 1, Ь и у = 5+1, Х.
Условия такой замены состоят в том, чтобы включение аз в новый базис, по крайней мере, не ухудшило значение целевой функции 1, а удаление а, обеспечило получение нового допустимого базисного решения. Согласно проведенным рассуждениям, целевая функция ~(У) может быть записана в виде З.г. Симплекс-метод при известном допустимом базисном решении 95 такой коэффициент называют симтьаеис-разиоспгьто.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
