Основа и основно решение - Studiopedia
В задачата на ЛП основите и основните решения играят ключова роля в организирането на търсенето на оптимално решение, ако то съществува. С тяхна помощ се генерират следващите върхове от областта на допустимите решения и се организира преходът от един връх към друг. Добрият избор на първоначалната основа и основното решение може значително да ускори процеса на търсене.
Ние илюстрираме възможността за такъв избор на примера на задача с ограничения във формата
Ако представим ограниченията на този проблем във форматаAx = b,, тогава матрицатаAще приеме форматаA = [a1, a2, a3],къдетоa1 = (4, 2) T , a2 = (1, 3) T , a3 = (5, 2) T . x = (x1,x2,x3) T. Векторитеa1, a2, a3,, както можете лесно да видите, са линейно независими, така че всеки два от тях могат да бъдат избрани като начална база. Примери за такъв избор са например(2x2)- матрициB1 = [a1, a2], B2 = [a2, a3], B3 = [a1, a3].Тези матрици наистина служат като основа за векторите на матрицатаA.
Чрез разлагане наA=[B, N], матричното уравнениеAx = bсе представя като
или еквивалентно,
Тъй като по дефиниция матрицатаBима обратна матрица, решението на последното уравнение по отношение на векторахB,ще се получи във формата
Като вземем в този изразxN = 0,получаваме основното решение във формата
Ако е неотрицателна, т.е.xB≥ 0, получаваме приемливо основно решение. Това решение съответства на върха на множеството от възможни решения, които могат да бъдат определени като
x 1 = .(4.5)
В този момент стойността на целевата функция еf(x 1 ) = c T x 1 = cB T xB.
Нека разгледаме и трите възможности.
хB = (х1в х2в) Т = В1 -1 b= (0.6, 3.8)Т,
xB = (x2v x3v) T = B2 -1 b= =(16/13,
38/13) T , x 2 = (0, 16/13, 38/13) T ;
xB = (x1v x3v) T = B3 -1 b ==(2, 1) T ,
И трите върха са валидни.
1.5. Табличен симплексен метод (симплексен алгоритъм)
Simplex - методът се основава на итеративен процес на изброяване (или трансформиране) на върховете на областта на възможните решения и проверка на условията за оптималност в тези върхове. Върховете, както е отбелязано по-горе, се генерират с помощта на бази. Табличната версия на алгоритъма е много удобна за машинно броене, тъй като е свързана с трансформирането на таблици - масиви от данни, които съдържат информация за текущата база, основното решение, правилото за спиране и накрая оптималното решение. В процеса на трансформация на таблицата, който е реализация на процедуратапълно елиминиране на Гаус, се формира и информация за двойните променливи на решаваната задача.
Нека проблемът бъде представен в канонична форма
, (5.1)
къдетоcиx савектори с размерност (n x1),т.е. e. sО Е p , хО Е p , А –матрица с размерност(mхп), b – (пх1)– вектор.
Да приемем, че матрицатаAможе да бъде представена катоA=[B, N], където B е (mхm) –матрица с пълен ранг. За простота нека приемем, чеB -е идентичната матрица, т.е.B = I. Това може да стане, например, ако ограниченията на първоначалния проблем саAx ≤ b.В случай на неотрицателен векторb,т.е.b ≥ 0,това предположение помага да се намери първото основно решение във формата
xB = B -! b = I -1 b = b ≥ 0.(5.2)
Тогава първият връх ще бъде
където0p–mобозначава нулевия вектор сp–mкоординати. За изграждане на оригиналната масаозначете сIBиIN,наборите от индекси на вектори отBиN, съответно, и изчислете така наречените симплексни разлики за вектори, принадлежащи наNпо формулата
(СР)j = cj– . (5.4)
Симплекс - разликите съдържат информация за оптималността на текущото основно решение и следователно на текущия връх. Съгласно това правило,ако при решаване на максималния проблем на всяка стъпка (или итерация) на симплексни трансформации,
тогава намереното основно решение е оптимално. Иначе търсенето на решение продължава.
Лесно е да се види, че за всички базисни вектори условието
т.е. векторите отBимат нулев симплекс - разликата на всички етапи на симплексните трансформации.
Нека е необходимо да се реши проблемът
Удобно е следващите действия да се представят като последователност от стъпки на алгоритъма. Състои се от предварителен и основен етап.
Предварителен етап. Представете проблема в канонична форма
Стъпка 1.Разлагане на матрица A. Запишете ограниченията като матрично уравнениеAx = b, x≥ 0 и представете матрицатаAкато
,
избирайки в него(mxm) –матрицаBс пълен ранг. В този случай е удобно да изберете матрицата на идентичностB = [a3, a4, a5] = I,като начална база, следователноN = [a1, a2], IB , IN = .Както можете да видите,B = I –е матрицата на идентичност с размерност(3x3).Ако получаването на основатаBне е възможно, тогава проблемът няма решение.
Стъпка 2.Намиране на основното решение. Началната базаBсъответства на основното решение във формата
Върхът, съответстващ на това основно решение, еx 1=(0, 0, 12, 2, 3) T . Последните три координатиx 1съвпадат със съответните координатиxB,, а първите две координати са равни на нула. Стойността на целевата функция в този момент е
Стъпка 3. Изчисляване на симплекс - разлики и изграждане на правило за спиране.Изчисляване на симплекс - разлики за неосновни вектори отN.Тъй катоIN = ,имаме
(SR)1=c1– ,
(SR)2=c2–.
Лесно е да се види, че поради нулевия векторcB = (0, 0, 0) Tусловието
Тъй като симплекс - разликите(СР)1и(СР)2са положителни, търсенето на оптималното решение продължава.
Стъпка 4. Конструиране и трансформиране на началната таблица Т0.
Първоначалният симплекс - таблица, съответстваща на решаваната задача, е показан на фиг. 2.2.
| i0 = 5 |
| J0 = 2 |
Ориз. 2.2. Оригиналният симплекс е таблица.
Съдържа матриченА,векторb,основно решениеxB = bи така нареченатаиндексна линия,в която първият й елемент е текущата стойност на целевата функцияf(x) = f(xB) = cB T xB,а останалите й елементи са така нареченитеиндекси Dj = - (CP)j, j = 1, …, n,чиято стойност е определена като симплекс - разликата с обратен знак. Цифровата част на симплексна таблица се нарича нейнатаглавна част:и претърпява трансформация от итерация на итерация.
Стъпка 5. Проверка на правилото за спиране
АкоDj ³ 0, j = 1, …, n,стоп; намереното базисно решение е оптимално, а стойността на целевата функция е най-голяма. В този случай и двете стойностиDjса отрицателни. Това означава, че и двете симплексни -разликите(CP)j, j = 1, 2,са положителни, следователно търсенето продължава.
Стъпка 6. Избиране на водеща колона и водещ ред.Водещата колона с индексj0се избира с най-голямата стойност(CP)j > 0.В нашия случай това е(CP)2 = 3,следователноj0 = 2.
.
Съгласно това правило, сред всички релации от типа, къдетоxibса основни променливи (числовите им стойности се съдържат в колонатаb),-са положителни елементи на насочващата колона, се избира най-малката връзка с индексi0. В нашия случай това е редът с индексi0= 5. Ако няма положителни елементи във водещата колона, задачата няма решение, тъй като целевата функция е неограничена.
Изборът на водещия ред и водещата колона съответно с индексиi0иj0съответства на изключването на променливата от основното решение и включването на променливата вместо нея, освен това на новата променлива в базата се присвоява стойност
l0 = .
В текущата таблица елементът се наричаводещ елементи е маркиран с кръгче.
Не намерихте това, което търсихте? Използвайте търсачката: