Галеев Э.М., Тихомиров В.М. - Краткий курс теории экстремальных задач (1050553), страница 13
Текст из файла (страница 13)
Таким образом, для решения задачи линейного программирования (если оно существует), достаточно перебрать значения функции (с, х) во всех крайних точках множества С. Но нахождение всех этих крайних точек и перебор значений функции— операция довольно трудоемкая. Описываемый ниже метод . (симплекс-метод) решения задачи линейного программирования позволяет начиная с некоторой исходной крайней точки переходить к другой по направлению наибольшего возрастания значения функции.
Задача (зк) называется невырожденной, если любая крайняя точка множества С содержит ровно т положительных координат. Пусть х †крайн точка в невырожденной задаче с т положительными координатами (для определенности первыми) хь...,х . Тогда вектор х можно представлять в виде х=(хв, хн), где ха=(хь...,х ) — базисный вектор, хн=(0,...,0)еп К" — — небазисный вектор.
Аналогично матрицу А можно ' представить в вице А= (Ав, Ан). Будет доказано (п. 3.2.3), что матрица Ав невырожденная. 3.1.2. Правило решения. Для решения невырожденной задачи линейного программирования следует: к 1. Привести задачу к задаче в канонической форме (зк).
2. Отыскать крайнюю точку хе=(хп ..х, 0,...,0)е=й", х~>0, 1=1,...,т, множества допустимых элементов С. Методы нахождения начальной крайней точки будут описаны ниже. 3. Построить снмплексную таблицу для начальной крайне»г; точки хо. Пояснения к таблице. В таблице л+4 столбца и т+4) строки. В первом столбце начиная с третьего по т+2-е место нахо-,', дятся базисные векторы а»,...,а, соответствующие рассматри- ' ваемой начальной крайней точке хо=(х»,...,х, 0,...,0). Во втором столбце на аналогичных местах стоят значение ' с» вектора с с теми же номерами, что и столбцы а».
Первая строка начиная с четвертого столбца — элементы с»,...,с„. Вторая строка начиная с третьего столбца — векторы Ь,. а',...,а". Под ними — разложения этих векторов по базису аа а',...,а'". Ясно, что Ь=Яа»х„а»=а», »=1,...,т на»= 1 а»х»» »=» т=» 1=т+ 1,..., лоха»=Азх»ФРх»=Ая-»а». В предпоследней строке в столбце под вектором Ь запишем,. го=(св, хо), под векторами си»=1,...,л, запишем х»=(св, х). ', Ясно, что го †значен функционала в начальной крайней точ- . ке хо, г» =с», 1=1,..., и. В последней строке записывается разность между элементамн предпоследней строки н элементами первой строки: Л»= = 㻠— с», 1=1,..., л.
4. Исследовать симплексную таблицу. а) Если Л>0, то крайняя точка хо — решение задачи. б) Если прн некотором 1 Л;(О и х»(0, то значение задачи ~ахах — + оо. в) Пусть в строке Л имеются отрицательные числа, а соответствующие столбцы х» содержат положительные числа. Предположим, что ш(пЛ» —— Ли(0. Ясно, что т+1Яое-л Столбец, соответствующий индексу (о, называется разрешаю- "' щим столбцом. Если пппЛ; достигается при нескольких значениях 1, то в качестве разрешающего столбца выбираем столбец ( с любым таким индексом.
Обозначим О»=х»/х»л для хи О, »'= =1, ..., т, О =ш(п(О»(хи,)0, 1»'=1, ..., т)=Ол)0. Строка ' вектора а' называется разреи»ающей. Если ппп О» достигается при нескольких значениях», то в качестве разрешающей строки выбираем строку с любым таким индексом. Элемент х»а„стоящнй в разрешающем столбце н разрешающей строке„ называется-разрешающим элементом таблицы. Далее необходимо из числа базисных векторов исключить вектор а", вместо него взять вектор а» .
Значение функциона-,; ла на новой крайней точке х„, с новымн базнснымн номерами 1,, »о — 1, 1о, »о+1 ..., и возрастает на — О,ЛЬ. 5. Построить новую симплексную таблицу для нового бази- . са а', ..., ໠— ', а», а'»', ...", а,т., е. фактически разложить векторы Ь, а', ..., а" по новому базису. Укажем без обоснования (которое будет' произведено в п. 3.2.3) способ построения 60 новой симплексной таблицы по предыдущей. Элементы таблицы хеь лежащие под векторами Ь, а',...,а" и не лежащие ж разрешающем столбце или разрешающей строке старой симплексной таблицы, вычисляются по правилу прямоугольника:: из числа хм вычесть произведение х~„на хп„деленное на х;,ь Элементы разрешающей строки вычисляются по формуле (хна)„,„х~,1/х~,у„1=1, ..., т.
Ясно, что в разрешающем столбце(,)„, = 1 остальные элементы равны нулю. Далее необходимо вновь исследовать си1рплексную табли- т. е. вернуться к п. 4 и т. д., пока не придем к решениюачи. 3.1.3. Пример. Решить невырожденную задачу линейного граммирования в канонической форме 2х~+ха+ха — х4-~-зцр; х~ — х,+хе — — 1, х;ъО, 1=1, 2, 3, 4, 2х~+хз+х4=3 данной начальной крайней точкой хь=(0, О, 1, 3). Р е ш е н и е. Базисные векторы аз= (1, 0) и а"= (О, 1). Соим первую симплексную таблицу: .1 О О О Из таблицы видно, что в качестве разрешающего столбца можно взять столбцы а' и а'.
Возьмем для определенности 61 столбец аз. Тогда 0=3, разрешающая строка а4. Заменяем в базисе вектор а4 на вектор ат н для нового базиса строим вторую симплексную таблицу: ! — решение зн- о о з Вектор г — сэ-О, поэтому точка х= (О, 3, 4, 0) дачи и Б,х=7. Если бы в качестве разрешающего столбца плексной таблице взяли столбец а', то пришли точке (О, 3, 4, 0), но за большее число шагов. в первой си(нбы к той лйе ~т с;х~+фч —— а, ~„а(х~+Рс=го 1 — — 1, ..., т. уса 3.2.
Обоснование симплекс-метода 3.2.1. Теорема существования. Теорема. Если множество допустимых значений задачи линейного программирования (з) п. 3.!.1 непусто и ее чосленное значение конечно, то ее решение существует. < Рассмотрим мнвжество Кс:11 +', образованное ''такими векторами (а, г), цен)1, зяб'", для каждого из которых,найдется хотя бы один вектор х, такой, что (с, х)«-а, Ах з, т(сно, что К в конус. Л ем м а 1. Конус К вЂ” конечнопорожденный. «~ Покажем, что К=сопе йь..., $„++1), де $1 = (сь .а~',..., а '), ..., Ц„=(с„, а|",...,ам"), оп+1=(1, О, л, 0), Ц +я= =(О, 1,...,0),...,$„; +1 —— (0,...,0, 1).
Нетрудно видеть, что все $~енК, поэтому соне ($ь..., $„+„+1)~К. Действительно, если 1=1, ..., и, то надо взять в качестве х стандартный базисный ,вектор е~, для остальных 1 надо взять х=О. Пусть теперь век-тор с=(а, г) =(а, гь...,г )енК. Тогда для некоторого х= =(х„..., х,) вне" и некоторых ()чъО, ..., р ~0, выполняются соотношения Но это как раз и означает, что $=(а, г)= ~ хД +()Д„+!+ Я(ЗД„+!+„ У=! 1=! т.
е. $=сопе($!," $ + +!) (>(> Лемма 2. (о замкнутости конечнопорожденного конуса) Если х„..., х„~((", К=сапе(х,, ..., хн) =Д Л!х„Л!.Р 0), ! то К вЂ” замкнутый конус. О'0 Положим АЛ= ~~Л;х! для вектора Л=(Л! ...,Лн)ек ' !=-1 ен)(', тогда Аен2" (и", 11"). Образ Ам" (обозначим его Ъ) — конечномерное подпространство в йч.
По лемме о правом обратном (п. 7.2) существует обратный ограниченный оператор М:Š— «$Р, такой, что АоМх=х(тхяЕ, ~Мх)<С~х~. (1) Пусть х~О принадлежит замыканию К (х=ОенК по определению), т. е. существует последовательность (Ль)» и, Лв= =(Л!л,, Ллл), такая, что АЛ!!=! хл-~Х. Тогда найдется йа)0„ такое, что при К>й~х" ~<21х~, и из (1) получаем де! ~Лл) =, ~А !х" ~<С~хз~<2С~х~. Вследствие ограниченности последовательности (Ль)ь и из нее л! можно выбрать сходящуюся подпоследовательность Л "-~- Л. Тогда ы ле! АЛ = 1пп АЛ"! =1пп х"! = х *ф х ен Е. Ясно, что хенК, т.
е. К вЂ” замкнутое множество. (> ~> По условию существует допустимый элемент х, т. е. точка ((с, хЛ Ь)енК. Кроме того, численное значение задачи а) — со (в частности, (с, х))а). Все это означает, что множество А= =(аенй~ (а, Ь)яК) непусто !( а=(п1(а1аенА). Отсюда (а, Ь) принадлежит замыканию К, а по лемме 2 и К. Но это и означает, что существует Х, для которого (с, х)<а, АХ Ь, т. е. Х— решение задачи. (> Совершенно аналогично доказываются теоремы существования для задач линейного программирования, заданных в других формах: ~ Е, ~ <со=~-Агд зчь!с1. Таким же образом доказывается, что минимум существует у полиэдральной функции шах ((с!, х)+Л!)на аффинном многож<н образин (Ьь х>=0, 1<1(т<п (кепи"). 3.2.2. Теорня двойственности н критерий решения. Рассмот:рим задачу линейного программирования п. 3.1.1: <с, х>- !п1; Ах(Ь.
(з) Двойственной к ней называется задача (Ь, у>-~-знр; А'у=с, у(0. (з*) Вывод двойственной задачи дан в п. 11.1,1, Если задачу (з ) представить в виде задачи (з) и искать к ней двойственную, то двойственной к (зь) будет задача (з). Таким образом, по- .-; лучили пару двойственных задач. Легко вывести, что двойственной к задаче в канонической форме является задача (Ь, у>-э!и1; А*у~)с. 'Наиболее симметричными оказываются прямая н двойственная .задачи для задач в нормальной форме: (с, х>-+.зпр; Ах(Ь, х)0, л (Ь, у>-~.!и1; А*у)с, уъ0.
й Здесь векторы Ь и с меняются местами, !п1 заменяется на зпр, н, наоборот, матрица А заменяется на транспонированную, матричные неравенства меняются на неравенства в обратную сторону. ) Теорема 1 (двойственности). Для пары двойственных задач линейного программирования имеет место следующая альтернатива: или значение какой-либо из задач конечно (тогда .значение второй конечно, и оба значения совпадают), или значение одной из задач бесконечно, а другая несовместна. Доказательство дано в и.
11.1.1. Теорем а 2 (критерий решения). Для того чтобы элемент .х являлся решением задачи (з) (х~Агпз), необходимо и достаточно, чтобы нашелся элемент у, допустимый в двойственмой задаче (з*) (уенХ),".), такой, что <с, 2>=(Ь, у>. < Необходим ость. Если 2 есть решение задачи (з), то, разумеется, задача (з) совместна н ее значение конечно. По теореме двойственности значение задачи (з*) конечно (равно значению задачи (з)), и, следовательно, по теореМе существования решение (з ) существует. Обозначим его у. Доказано, что <с„й>=<Ь, У>. Достаточность.
Пусть х н у — допустимые элементы в .задачах (з) н (з*) соответственно. Имеем (учитывая, что .А"у=с, у(0, Ах(Ь) (с, х> = <А*у, ху= (у, Ах))(у, Ь). Таким образом, если (с, х)=<Ь, у>, то Х вЂ” решение (з), в' — реепенне (з*). Нетрудно понять, что теорема 2 справедлива не только для задач (з) и (з*), но и для всех двойственных задач линейного программирования. Используем ее в п. 3.2.3 при обосновании симплекс-метода для задач линейного программирования в канонической форме. 3.2.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
