1_theory (732180), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Подставляя в (2.4.12) базовые функции вида f_i(z)=[H( z-z_j )-H( z-z_j+1 )], получим окончательное выражение:

Отметим основное преимущество такого решения. Несмотря на определенную сложность вычислений при решении интегральных уравнений (2.4.2-2.4.8) для расчета градиента импеданса НВТП необходимо решить только две такие задачи.

2.4.2 Отечественные методы решения

Подход, в значительной мере аналогичный работам [45-51] был предложен в работе [41]. Из-за небольшого объема в ней уделено недостсточное внимание вопросам практической реализации, объяснены не все обозначения и не приведены результаты численного моделирования. В целом это значительно снижает практическую ценность статьи. Приведем основные положения этой работы.

Прямая задача

Пусть круговой виток радиусом а с током I находится в точке P=P_s(r,j,z), jÎ(-p,p) вблизи немагнитного ОК, занимающего область V. Пусть ОК обладает электрической проводимостью s=s₀×s(Р) являющейся произвольной функцией координат. Требуется по N измерениям величины э.д.с. определить s как функцию координат точек PÎV. Причем i-ое измерение э.д.с. будем проводить на i-ом измерительном круговом витке с координатами P_i=P_i(r,j,z) i=1,N при неизменных частоте и расположении возбуждающего витка.

В общем случае напряженность электрического поля Е определяется через векторный магнитный потенциал А, причем А = А₀ + А_вн, где А₀ - возбуждающий, а А_вн - вносимый потенциалы.

Вводя функцию Грина G(p,p₀) получим

При этом вносимая напряженность электрического поля

Вносимая э.д.с., наводимая в i-ом витке

где функция Грина G(P,P₀) имеет вид

В дальнейшем рассмотрим случай, при котором V-полупространство (r>0,\j\<p,z<0) с электрической проводимостью s=s₀×s(Р), где s(Р) - произвольная функция координаты z. В этом случае выражение (2.4.17) примет вид

где k²=jwm₀s₀ .

Для напряженности электрического поля Е(Р) справедливо представление

где Е⁰(р) - возбуждающее поле витка.

После проведения серии из N измерений величины e_вн выражение (2.4.19) дает связь между вносимыми ЭДС e_i и s(z)E(r,z). Чтобы определить непосредственно s=s(z), находим E(r,z) при известной функции s(z)E(r,z) из (2.4.20), после чего исключаем E(r,z) из известного.

Обозначим x(p)=-k²s(z)E(r,z), а измеряемую совокупность ЭДС через Fi. Тогда (2.4.19) можно записать в операторной форме как

где d - погрешность измерения.

Обратная задача

Построим функционал Ф(х)=||F-Px||²+a||x-x₀||², где х₀ - некоторое известное ²близкое² к искомому распределение, удовлетворяющее F₀=Px₀. Образуем вариацию функционала Ф(х), используя определение сопряженного оператора (Px,y)=(x,P*y). Для нахождения минимума Ф(х) приравняем его вариацию dФ нулю.

Вводя вспомогательную функцию u=x-x₀ и учитывая F₀=Px₀ проведем ряд преобразований. Искомое распределение s(z) можно найти из равенства

где напряженность электрического поля в точке р для известного распределения s(z) имеет вид

Система алгебраических уравнений для определения коэффициентов С_i имеет вид

3. Прямая задача ВТК для НВТП

3.1 Уравнение Гельмгольца для векторного потенциала

Взаимодействие преобразователя с объектом контроля определяется системой уравнений Максвелла в дифференциальной форме[6] :

где

Дополним систему (3.1) уравнениями связи:

где

Преобразуем систему уравнений (3.1) с учетом следующих предположений[4] :

• ОК неподвижен относительно электромагнитного поля т.е. jпер = 0

• среда изотропна и ее параметры не зависят от напряженностей полей

• воздействия синусоидальны

• последовательность дифференцирования по времени и пространственным координатам можно изменять, а операция дифференцирования линейна

Поскольку ротор градиента любого скаляра тождественно равен нулю, величину в скобках выражения (3.4.2) можно приравнять градиенту некоторого скаляра y , например скалярного потенциала электрического поля :

Заменяя векторы напряженности магнитного и электрического поля в (3.4.1) через векторный потенциал магнитного поля получаем :

Откуда после очевидных преобразований следует:

где

Поскольку векторный потенциал магнитного поля задан с точностью до градиента некоторого скаляра, а потенциал y с точностью до постоянной величины, имеется возможность положить значение величины в квадратных скобках выражения (3.7) равное нулю (так называемая калибровка Лоренца). В результате получаем уравнение Гельмгольца для векторного потенциала магнитного поля :

В дальнейших рассуждениях используем следующие предположения :

• Поле НВТП квазистационарно в том смысле, что волновыми процессами в воздухе можно пренебречь. Это вполне оправдано т.к. размеры НВТП и ОК обычно много меньше длины волны в воздухе, а потери на излучение по сравнению с потерями в ОК малы.

• В проводящем теле будем рассматривать только волновые процессы, обусловленные наличием параметров s и m т.е. токами смещения( пропорциональными w×e×e0 ) как и в воздухе пренебрегаем. Легко показать, что это предположение справедливо не только для металлов, но и для полупроводниковых материалов с удельным сопротивлением r до 50[Ом×см]. В этом случае выражение (3.8) принимает вид : .

3.2 Поле витка над многослойной средой

В цилиндрической системе координат выражение (3.9) имеет следующий вид :

Применяя к (3.10) преобразование Фурье-Бесселя с ядром в виде функции Бесселя первого порядка имеющее вид : получаем

Так как на поверхностях раздела слоев ОК должна сохранятся непрерывность тангенциальных составляющих векторов напряженностей магнитного и электрического поля, дополняем уравнение (3.11) граничными условиями на поверхностях слоев ОК( граничные условия одинаковы для А и А* ) :

Решив уравнение (3.11) с учетом граничных условий (3.12-3.13) и применяя к решению обратное преобразование Фурье-Бесселя имеющее вид : получаем для полупространства над ОК

где j=j( l , m , s ) - функция граничных условий.

3.3 Воздействие проводящего ОК на НВТП

Для большинства инженерных расчетов можно использовать нитевидную модель обмоток НВТП использованную в (п 3.2). При данном упрощении получаем :

Анализируя формулу (3.14) можно заметить, что первый интеграл представляет собой векторный потенциал создаваемый возбуждающей обмоткой, а второй интеграл - векторный потенциал вносимый ОК. В практике ВТК обычно анализируются вносимые параметры НВТП (напряжение, импеданс) поэтому получим выражение для вычисления вносимого напряжение кругового трансформаторного накладного ВТП используя (3.15-3.16):

Подставляя выражение для вносимого векторного потенциала (3.14) в уравнение (3.17) окончательно получаем :

где

Функция граничных условий для m-слойного ОК с плоскопараллельными слоями может быть вычислена по рекуррентной формуле[2]:

где

При анализе годографов для удобства используют нормированные зависимости. Для НВТП нормировку производят по модулю максимального вносимого напряжения, которое соответствует идеально проводящему ОК и вычисляется при j_м = -1:

Такая нормировка обобщает полученные результаты, расширяет область их применения и делает их однозначными.

Отметим, что для получения часто используемого в ВТК значения импеданса НВТП достаточно разделить правую часть (3.18) на величину тока возбуждения I.

4. Обратная задача ВТК для НВТП

Решение обратной задачи ВТК состоит в нахождении зависимости s(h) распределения электропроводности по глубине пластины используя набор из N измеренных с помощью НВТП вносимых напряжений. Математически обратную задачу можно представить интегральным уравнением

Поскольку явного метода решения уравнения (4.1) не существует, применим к нему метод квазирешения (п5.3.2). В постановке для локального в смысле Чебышева критерия получим корректную задачу минимизации функционала невязки:

Учет априорной информации в обратной задачи ВТК удобно проводить в виде интервала [ s_min , s_max ], которому могут принадлежать значения электропроводности. В этом случае можно рассматривать задачу (4.2) как задачу нелинейного программирования вида:

Заметим, что поскольку ограничения в задаче (4.3) являются линейными, разумным представляется применение метода условного градиента (п6.2.1). Рассмотрим процесс решения системы (4.3) в предположении, что электропроводность аппроксимируется по узловым значениям s_j , j=1,M.

Линеаризуем функционал Ф в окрестности исследуемой точки s⁰ разложив его в ряд Тейлора с использованием только первых производных.

Пусть y = maxФ_i’ = Ф_p’ ³ 0. В этом случае мы можем свести задачу (4.4) к эквивалентной задаче линейного программирования, состоящей в условной минимизации функции y. Рассмотрим процесс приведения задачи линейного программирования к каноническому виду.

Раскрывая модуль в (4.5) получаем систему уравнений

Рассмотрим выражение под модулем в (4.5) и введем некоторые обозначения

С учетом системы (4.8 - 4.10) постановка задачи (4.4) принимает вид

Раскрывая скобки в (4.11) и исключая y из первых 2N неравенств кроме р-го получаем систему неравенств

Приведем систему неравенств (4.12) к каноническому виду (6.1). Для этого, в соответствии со стандартным подходом, запишем все неравенства в виде равенств, добавляя в левые части неравенств неотрицательные переменные v.

В матричном виде полученная система имеет вид Ax = b (4.14), где искомый вектор-столбец из 2(N+M)+1 элементов имеет вид x = ( y , z₁ , ... , z_M , v₁ , ... , v_2N+M)^T. В системе линейных алгебраических уравнений (4.13) параметр минимизации y определен строкой с номером p, которую в дальнейшем будем называть базовой.

Рассмотрим алгоритм симплексного метода для решения задачи (4.14):

1. Выбор начального базиса - допустимого решения (4.14). В нашем случае базис должен состоять из 2N+M переменных. Удобно задать начальный базис, присвоив дополнительным переменным v_i значения правых частей b_i тех строк, в которых коэффициент матрицы A при них равен 1. Начальное значение параметра минимизации y равно значению правой части базовой строки. Все остальные компоненты искомого вектора х принимаются равными нулю.

2. Определение переменной, которая должна войти в очередной пробный базис. Для этого проводится анализ базовой строки p матрицы A. Из всех положительных элементов строки p, не являющихся коэффициентами при базисных переменных , выбирается элемент с наибольшим значением. Переменная, у которой этот элемент является коэффициентом, должен войти в очередной пробный базис, т.е. за новую базисную переменную принимается та, которая имеет наибольший вес в функции y. Если в базовой строке p нет небазисных переменных с положительными коэффициентами, то в силу не отрицательности элементов х следует сделать вывод, что оптимальному решению, т.е. минимуму y соответствует выбранный ранее базис. Вычисления завершаются также и при запрете изменения переменных по ограничениям.

3. Определение максимальной допустимой величины новой базисной переменной, не выходящей за пределы имеющихся ограничений. Вычисляются отношения значений правых частей (4.14) к соответствующим значениям коэффициентов при новой базисной переменной во всех строках, кроме базовой. При этом не рассматриваются отношения, в которых знаменатель равен нулю или отрицателен, т.е. при положительной правой части подобные случаи соответствуют бесконечным значениям переменных. Определяется номер строки q, где это отношение наименьшее. Новой базисной переменной присваивается значение отношения в строке q. Переменная, входившая в прежний базис и определявшаяся строкой q, исключается из базиса и приравнивается нулю. Если во всех строках, кроме базовой, коэффициенты при новой переменной равны нулю или отрицательны, то в силу не отрицательности элементов х и ограничения базиса (2N+M) переменными, следует признать, что эта переменная не может на данном шаге вычислений войти в базис. В этом случае необходимо вернуться к пункту 2, не рассматривая запрещенную переменную.

4. Преобразование системы (4.14) таким образом, чтобы в строке q коэффициент при вновь введенном параметре был равен 1, а в остальных строках - 0. Это достигается путем линейных преобразований равенств, входящих в (4.14). Т.к. коэффициенты при параметрах, входящих в новое пробное базисное решение, становятся равными 1 и в каждую строку входит только один базисный параметр, то значение нового базиса определяется правой частью уравнений. Далее следует возврат к пункту 2.

Решая систему (4.14) находим вектор s_min , соответствующий текущему решению задачи(4.13). Возвращаясь к методу условного градиента отметим, что направление спуска определяется как -s_n=s_min - s⁰ , а очередное итерационное решение задачи (4.3) определяется выражением sⁿ⁺¹=sⁿ - a× s_n. Для получения окончательного результата требуется определить оптимальную величину шага a в направлении s_n , что можно осуществить путем одномерной минимизации функции s(a)=sⁿ - a× s_n методом золотого сечения.

5. Некорректные задачи

5.1 Основные понятия. Корректность по Адамару

В самом общем виде большинство обратных задач может быть представлено в виде операторного уравнения

где А - оператор, определенный на непустом множестве некоторого метрического пространства Х с метрикой r_X и действующий в метрическое пространство F с метрикой r_F, а по заданному элементу f требуется определить решение х [10-14].

Введем в пространстве X норму || x ||=Öåx_i² и в пространстве F норму || f ||=Öåf_j². Заметим, что метрики r в соответствующих пространствах будут иметь вид r(x,y)=\\x-y \\.

В нашем случае обозначения в (5.1) имеют следующий смысл:

Согласно классического определения задача (5.1) называется корректной по Адамару если при любой фиксированной правой части ее решение:

• существует в Х

• единственно в Х

• непрерывно зависит от f

В реальных условиях правая часть (5.1) известна всегда с некоторой погрешностью, т.е. f = f0 + df , причем обычно f0 принадлежит пространству гладких функций, а погрешность df выводит ее из этого класса. Вследствие этого получаем постановку задачи, для решения которой невозможно применение обычных методов решения корректных задач, т.к. любой фиксированной правой части (5.1) соответствует бесконечное множество наборов исходных данных т.е. возможных распределений ЭП по глубине пластины.

5.2 Корректность по Тихонову

Задача (5.1) называется корректной по Тихонову на множестве корректности М Ì X если:

• точное решение задачи существует и принадлежит М

• принадлежащее М решение единственно для любой правой части

• принадлежащее М решение непрерывно относительно правой части

В данном подходе к вопросу корректности существование решения и его принадлежность некоторому множеству не доказывается, а постулируется в самой постановке задачи.

Физически гипотеза о принадлежности искомого решения определенному множеству корректности может интерпретироваться для нашей задачи предположениями:

1. Исследуемая среда устроена не слишком сложно, т.е. ее физические характеристики(s,m) являются достаточно гладкими функциями( т.е. их можно моделировать с помощью аппроксимаций типа кусочно-постоянной, кусочно-линейной и т.п.). Предположение основывается на физическом смысле поверхностной обработки.

2. Значения функций находятся во вполне определенных пределах( для s(h) истинность данного предположение не вызывает сомнения ).

5.3 Вариационные методы решения некорректных задач

Вариационные методы решения некорректных задач являются наиболее универсальными из известных способов решения. Практически любая некорректная задача, для которой разработан какой-либо метод решения, может быть решена также и вариационным способом[15].

Для выбора подходящего метода решения обратной задачи рассмотрим постановки наиболее распространенных вариационных методов в терминах вычислительной математики и нашей задачи.

Пусть фиксированный набор данных состоит из измеренных на N частотах N комплексных значений вносимой ЭДС Uiизм, текущее рассчитанное значение которых Ui( s ). Требуется определить для выбранного типа аппроксимации ЭП значения М параметров аппроксимации ( обычно используются узловые значения ).

5.3.1 Метод регуляризации

Метод основан на стабилизации невязки r(Ax,f) при помощи вспомогательного неотрицательного функционала W(x). Идея метода состоит в том, чтобы минимизировать обладающий сглаживающими свойставами функционал Ф(x,f), имеющий следующий вид:

Используя классический регуляризирующий функционал вида в терминах нашей задачи получаем:

Основное преимущество метода состоит в регуляризации простейшим способом, в рамках использования квадратичного функционала. Это позволяет использовать для решения некорректной задачи хорошо известные и легко программируемые методы минимизации квадратичных функционалов [17].

Оборотной стороной достоинств метода являются его недостатки. Требование минимизации нормы решения и, как следствие, выбор гладкой реализации, в нашем случае будет приходить в противоречие с физикой задачи и в принципе не позволит находить решения с выраженным приповерхностным изменением ЭП.

Еще один принципиальный недостаток метода состоит в постановке функционала как квадратичного, единого для всех измерений. Его минимум в общем случае не гарантирует минимизацию отклонения для произвольного i-го измерения в следствии нелокальности условия минимизации.

Кроме того, следует учитывать отсутствие надежных априорных рекомендаций по выбору параметра регуляризации a. Обычно подходящие значения a можно подобрать только после ряда численных экспериментов по решению однотипных задач. Изменение характера искомого решения приводит к необходимости поиска нового значения a.

5.3.2 Метод квазирешений

Метод использует одну из форм критерия невязки и заключается в сведении невязки к минимуму на некотором непустом множестве P, содержащем подмножество искомых решений.

Квазирешением уравнения (5.1) на множестве PÌX называется всякий элемент yÎP для которого справедливо равенство r_F( Ay , f ) = inf( Ax , f ), xÎP. Понятие квазирешения обобщает понятие решения, а для его существования не требуется принадлежность решения множеству P.

Исходя из вышеизложенного получаем постановку метода в виде задачи условной минимизации функционала Ф(x,f):

Отметим, что множество Р может иметь простой вид, например интервала [ x_min , x_max ].

В терминах нашей задачи ВТК постановка задачи (5.4) примет вид:

Для того, чтобы гарантировать минимизацию отклонения для произвольного i-го измерения, можно применить к первому выражению в (5.5) локальный в смысле Чебышева критерий, в соответствии с которым получаем окончательное выражение :

Основное преимущество метода состоит в том, что само понятие квазирешения снимает трудности с требованиями тихоновской корректности: первым (вызывающим переопределенность задачи) и третьим (обычно принадлежность приближенной правой части уравнения (5.1) множеству N=AM неизвестна, а критерии этой принадлежности часто сами бывают неустойчивы).

Кроме этого при рассмотрении задачи в виде (5.6) возможна постановка минимизационной задачи как задачи нелинейного программирования с явно заданными ограничениями на искомые переменные. В этом случае нет необходимости искажать исходный функционал регуляризующими членами как в (п5.3.1), а требования к искомому решению можно удовлетворить, управляя ограничениями на параметры минимизации (в нашем случае - узловые значения ЭП).

5.3.3 Метод невязки

Рассмотрим множество Р формальных решений уравнения (5.1) Р={x : r_F( Ax , f_d ) £ d}, где f_d - приближенная правая часть (5.1), известная с погрешностью d.

В качестве приближенного решения (5.1) нельзя брать произвольный элемент множества Р, т.к. не гарантируется близость Р к множеству точных решений. Для выбора приближенного решения предлагается использовать стабилизирующий функционал W(х) из (п 5.3.1) следующим образом: W( х ) = inf W( х ), xÎP. Этот способ приводит к выбору элементов множества Р имеющих минимально допустимую невязку.

С учетом этого постановка метода состоит в условной минимизации функционала Ф(х):

Как и для метода регуляризации можно использовать стабилизирующий функционал вида W(х)=||x||² , что приводит в обозначениях нашей задачи к системе:

При использовании локального в смысле Чебышева критерия система (5.8) окончательно примет вид:

6. Нелинейное программирование

Содержание нелинейного программирования составляют теория и методы решения задач о нахождении экстремумов нелинейных функций на множествах, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами)[16-29].

Рассмотрим наиболее распространенные методы решения на примере основной задачи нелинейного программирования вида:

6.1 Метод штрафных функций

Идея метода состоит в замене экстремальной задачи с ограничениями (6.1) на задачу безусловной минимизации однопараметрической функции

Непрерывную функцию y(х) называют штрафом, если y(х)=0 для хÎ Х и y(х)>0 в противном случае. Функция y(х) должна быть выбрана таким образом, чтобы решение задачи (6.2) сходилось при b®0 к решению исходной задачи (6.1) или, по крайней мере, стремилось к нему.

Приведем часто используемые выражения для штрафа :

Наибольшее применение находит штраф (6.3). Выражение (6.5) гарантирует конечность метода при любом k>0.

При численной реализации метода штрафных функций возникают проблемы выбора начального значения параметра b и способа его изменения. Сложность состоит в том, что выбор достаточно малого b увеличивает вероятность сходимости решения (6.2) к решению (6.1), а скорость сходимости градиентных методов вычисления точек минимума (6.2), как правило, падает с убыванием величины b .

6.2 Релаксационные методы

Релаксационным методом называют процесс построения последовательности точек {х_k: х_k Î X , j( х_k+1 ) £ j( х_k ) ; k=0,1... }. Основными представителями этого класса являются методы спуска, алгоритм которых состоит из следующих шагов :

1. Выбор начального приближения х₀

2. Выбор в точке х_k направления спуска -s_k

3. Нахождение очередного приближения х_k+1 = х_k - a_k×s_k , где длина шага a_k>0

Различия методов состоят в выборе либо направления спуска, либо способа движения вдоль выбранного направления. В последнем случае обычно используют одномерную минимизацию функции х_k+1(a) = х_k - a×s_k (при этом точность вычисления точки минимума функции х_k+1(a) следует согласовывать с точностью вычисления значений функции j(х)) или способ удвоения a(величина шага удваивается пока выполняется условие j(х_k+1) £ j(х_k) ).

6.2.1 Метод условного градиента

Идея метода заключается в линеаризации нелинейной функции j(х). В этом методе выбор направления спуска осуществляется следующим образом :

1. Линеаризируя функцию j(х) в точке х_К получаем Ф(х)= j( х_k ) + ( j( х_k )’ , х - х_k )

2. Минимизируя линейную функцию Ф(х) на множестве Х находим х_min

3. Направление спуска получаем как -s_k = х_min - х_k

Таким образом итерация метода имеет вид: x_k+1=x_k+a_k×(s_k+1 - x_k) , s_k+1=arg min(Ñf(x_k),x).

Основное преимущество метода проявляется в случае задания допустимого множества с помощью линейных ограничений. В этом случае получаем задачу линейного программирования, решаемую стандартными методами(например симплексным).

6.2.2 Метод проекции градиента

Этот метод является аналогом метода градиентного спуска, используемого в задачах без ограничений. Его идея состоит в проектировании точек, найденных методом наискорейшего спуска, на допустимое множество, определяемое ограничениями. Проекцией точки y на множество Х называется точка P(y)ÎХ такая, что || P(y) - y || £ || x - y || для всех хÎХ. Задача проектирования формализуется как || x - y ||²® min, xÎХ.

Выбор направления спуска осуществляется следующим образом :

1. Находим точку r_k = х_k - a× j’( х_k )

2. Находим проекцию p_k точки r_k на множество Х

3. Направление спуска получаем как -s_k = p_k - х_k

Таким образом итерация метода имеет вид: x_k+1=P_X[ x_k - a_k×Ñf( x_k ) ], где Р_X(у) - ортогональная проекция точки у на множество Х.

Для отыскания направления спуска s_k необходимо решить задачу минимизации квадратичной функции || r_k - х ||² на множестве Х. В общем случае эта задача того же порядка сложности, что и исходная, однако для задач, допустимое множество которых имеет простую геометрическую структуру, отыскание проекции значительно упрщается. Например, для многомерного параллелепипида Q_N={xÎR_N : a £ x £ b }, отыскание проекции осуществляется путем сравнения n чисел и имеет вид P(x)={ a_i, x_ii ; x_i, x_iÎ[ a_i,b_i ] ; b_i, x_i>b_i }.

6.2.3 Метод случайного спуска

Метод характеризуется тем, что в качестве направления спуска s_K выбирается некоторая реализация n-мерной случайной величины S с известным законом распределения. Об эффективности этого метода судить трудно, однако благодаря использованию быстродействующих ЭВМ он оказывается практически полезным.

6.3 Метод множителей Лагранжа

Идея метода состоит в отыскании седловой точки функции Лагранжа задачи (6.1). Для нахождения решения вводится набор переменных l_i , называемых множители Лагранжа, и составляется функция Лагранжа, имеющая вид:

Алгоритм метода состоит в следующем:

1. Составление функции Лагранжа

2. Нахождение частных производных функции Лагранжа

1. Решение системы из n+m уравнений вида

Решениями системы (6.8) являются точки, которые могут быть решениями задачи.

1. Выбор точек, в которых достигается экстремум и вычисление функции j(х) в этих точках.

7. Линейное программирование

Задача линейного программирования в каноническом виде имеет вид[15,16]:

Приведение к каноническому виду любой задачи линейного программирования осуществляется путем введения дополнительных неотрицательных переменных, за счет чего ограничения, имеющие вид неравенств, принимают вид эквивалентных им равенств.

Любая задача линейного программирования может быть решена за конечное число итераций с помощью симплексного метода[17,18]. Следует отметить, что поскольку этот метод разработан для неотрицательных элементов x_j , это условие учитывается неявно и в систему уравнений (7.1) при численной реализации не входит.

7.1 Алгоритм симплексного метода

1. Приведение к каноническому виду

2. Выбор начального базиса

3. Проверка оптимальности базиса

Матрицу А можно рассматривать как совокупность столбцов a^j т.е. åa^j×x_j=b где j=1,N. Не ограничивая общности можно считать, что базис образуют первые m столбцов, тогда остальные можно представить в виде a^k=åa^j×l_jk , j=1,m где l_jk.- некоторые числа.

Рассмотрим коэффициенты D_k=åc^j×l_jk - c_k где j=1,m и k=1,N. Заметим, что для базовых столбцов D_k º 0. Проверка на оптимальность осуществляется следующим образом:

4. Составление нового базиса

4.1 Выбор элемента для введения в базис.

В базис вводится любой столбец, для которого D_k< 0, обозначим его D_p

4.2 Выбор элемента исключаемого из базиса

Из текущего базиса исключается столбец, для которого минимально отношение b_i/A_ip , i=1,M обозначим его b_r/A_rp

1. Преобразование вектора b и матрицы А по методу Жордана-Гаусса

4.4 Переход к пункту 3

Характеристики

Список файлов реферата