Шпаргалка по "Математическим методам"

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

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

          Если среди чисел нет положительных, то найденный опорный план является оптимальным. Если же для некоторой свободной клетки >0, то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых >0, и среди данных чисел выбирают максимальное. Клетку, которой это число соответствует, следует заполнить.

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

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

ЗАДАЧИ  НЕЛИНЕЙНОГО ПРОГРАММРОВАНИЯ

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

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

          Задачи нелинейного программирования возникают в естественных и физических науках, технике, экономике, в сфере деловых отношений и в науке управления государством. В экономике рассматриваются задачи о распределении ограниченных ресурсов таким образом, чтобы максимизировать эффективность.  Целевая функция здесь может отражать эффективность, которую мы пытаемся максимизировать, в то время как ограничения могут выражать условия, вызванные недостатком ресурсов.

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

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

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

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

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

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

           Пусть мы имеем функцию или непрерывно дифференцируемую по своим переменным .

           Градиентом в точке M(x)  называется вектор, направленный по нормали к поверхности уровня функции в сторону ее экстремального изменения и координаты которого определяются через частные производные в точке х следующим образом:

   

       Антиградиентом  называется вектор-

          Градиент функции задает в данной точке направление наискорейшего роста функции, а антиградиент - наискорейшего убывания функции. Мы будем рассматривать только   функции с непрерывным градиентом.

          Эти методы предназначены для безусловной минимизации  (максимизации) функции. Эти типы задач являются простейшими в нелинейном программировании. В ряде случаев более общие задачи нелинейного программирования могут быть сведены к рассматриваемому  типу задач.

       Рассмотрим более подробно эти  методы.

       МЕТОД ГРАДИЕНТА

       Пусть точка  - некоторая    начальная точка, а точка - предполагаемая точка минимума функции   , ближайшая к точке М₀   и не совпадающая с ней.  Необходимо определить координаты этой точки М^* и соответствующее ей значение функции. Метод градиента основан на использовании формул ломаных Эйлера:

   

где  - шаг интегрирования, или в векторной форме

       где

Для нахождения максимума функции формула метода имеет вид

     По найденным координатам точки М_k+1   вычисляем значение функции f( М_k+1 )  и проводим сравнение со значением f(M_K). Контрольное условие для нахождения min: , для нахождения max: .

      Правильный выбор шага h  имеет очень существенное значение. Чем меньше h, тем точнее результат поиска, но больше вычислений. Модификации градиентного метода и  состоят в том, что  используются различные способы выбора h . Причем,  если на  каком-либо  этапе f{M_k+1)   не уменьшается,   то это  означает, что мы  “проскочили”  нужную точку.  В этом случае необходимо  вернуться к предыдущей точке и уменьшить h   вдвое.

      При практической реализации поиск по указанной схеме (при условии, что на каждом этапе ) прекращается, если для всех j выполнено условие

где  - некоторая заданная величина, характеризующая точность  нахождения минимума (максимума), или можно ограничиться условиями

Методы  определения экстремальных  путей на графе

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

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

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

Метод Л.Р.Форда

          С помощью метода Форда на любом неориентированном связанном графе может быть найдена цепь минимальной длины от каждого узла  j до некоторого фиксированного узла k.

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

      Шаг 1. Строим матрицу смежности А, элементами которой являются веса (длины) ребер или дуг. Если пара вершин i и j  не смежны, то условимся в матрице смежности А на пересечении i –ой строки  и j –го столбца ставить некоторое большое число; обозначим его буквой М.

         Каждому узлу  j  графа , кроме фиксированного, припишем вес V_j=M, а фиксированному узлу k – все V_k=0

         Шаг 2. Берем  некоторый узел и находим любой соседний узел i, связанный c j ребром или дугой u_ij, имеющий вес a_ij. В начальный момент в качестве узла i целесообразнее выбрать фиксированный узел k. Для j и i проверяем выполнение неравенства:

       Если оно выполняется, то прежний вес V_j  узла j заменяется суммой  . В противном случае вес V_j остается неизменным.

Операция пересчета  производится для всех узлов графа  до тех пор, пока ни один из узлв не сможет принимать нового значения индекса V_j.         

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

          Шаг 1 (предварительный). Каждой вершине j графа (j=1,2,..,N) приписывает индекс .

        Шаг 2 (общий). На этом шаге перевычисляются индексы для всех вершин j графа. Шаг 2 повторяется многократно( один, два и т.д. k раз) до тех пор, пока на очередном k-ом  его повторении ни один из индексов Vj не сможет принимать новое значение . Действие этого шага состоит в следующем. Индекс первой вершины остается без изменения: . Все остальные вершины j (j=2,3,…,N) просматриваем в каком-нибудь порядке и заменяем индексы , вычисленные на предыдущем (k-1)-м повторении шага 2, на новые по формуле

       ,  (i=1,2,..,N-1, j=2,3,..,N)

где i- номера вершин, дуги из которых входят в j-ую вершину, а l равно k или (k-1) в зависимости от того, просматривалась ранее на k-ом повторении шага 2 вершина i или не просматривалась.

Метод Шимбела

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

1. Операция умножения двух величин a и b при возведении матрицы в степень соответствует их алгебраической сумме, т.е. соответствует . Например, соответствует 5+2=7.
2. Произведение бесконечности на любое число равно бесконечности. .
3. Сумма двух величин равна минимальному из слагаемых, т.е. a+b=b+a соответствует min(a,b). Например, 5+2=2+5 соответствует min(2,5)=2.

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

     Возведение матрицы А в степень t можно рассматривать как последовательное  (t-1)-кратное умножение матрицы А на самое себя

        (1)

    Умножая матрицу А на самое себя по обычным правилам умножения, мы получим в общем случае для элементов матрицы следующую формулу:  

    С учетом операций введенных Шимбелом выражение примет  вид:

    

     Элементы матрицы А² представляют собой длины путей, состоящих из одной или двух дуг. Соответственно, элементы матрицы А³ определяют уже длины путей, состоящих из одной, двух или трех дуг в зависимости от значений слагаемых в круглых скобках, Аналогичные рассуждения можно провести для элементов матрицы А⁴, А⁵,… А^t.

        Таким образом., элементы матрицы A^t, вычисленные в общем случае по формуле, определяют длины кратчайших путей, состоящих не более чем из t звеньев (дуг).

           Если в процессе умножения окажется, что A^t-1=A^t, то это говорит, что длины путей минимальных путей, состоящих не более чем из (t-1) звеньев, совпадают с длинами путей, состоящих не более чем из t звеньев. Значит, дальнейшее умножение матриц A^t-1A не целесообразно, так как не приводит к изменению элементов матрицы A^t-1. Таким образом, в процессе умножения матриц выполнение условия говорит о том, что дальнейшие вычисления можно прекратить, и полученная в результате матрица  
A^t-1 будет матрицей кратчайших расстояний (дисперсионной матрицей).