Пупков К.В. Методы классической и современной теории автоматического управления. Том 2 (2000) (1095389), страница 131
Текст из файла (страница 131)
Областью решений этой системы является треугольник Л АВС, показанный на рис. П2.8, если принять, что А= В=С=)~. Каждой точке треугольника области рис. П2.8 соответствует точка области на рис. П2.9. Рнс. ПЗ.8. Снмнлснс трехмерного пространства Соответствие можно устанавливать, проектируя эту треугольную область на плоскость х,хг. Если придать слабой переменной хз постоянное значение с, то х, и хг должны удовлетворять уравнению х, +хз = Ц -с, которое является уравнением прямой, параллельной х, + хг = 1ь . Если слабая переменная равна нулю, то х, + хг = 1) .
Таким образом, значение слабой переменной может служить мерой близости точки из треугольной области к границе х, +хг = Ь, полупространства, опрелеляемого исходным неравенством. П уложение 2. Математическое п о амму рвание 1основные положения) 693 хе В х| Рис.
Пзд. Область решении неравенства В общем случае в симплекс-методе процедуру поиска начинают с лопустнмой вершины, а затем переходят в соседнюю вершину так, чтобы значение целевой функции «улучшилось». В пространстве векторов свободных переменных возрастание значения одной из свободных переменных от нуля, при котором остальные свободные переменные остаются равными нулю, соответствует движению из начала системы координат, образованной свободными переменными, по одной из координатных осей. При этом, поскольку (и-1) свободных переменных равны нулю, (и — 1) ограничений задач выполняются как равенства. Другими словами, все соседние с началом координат вершины (которые соответствуют текущему решению) связаны с началом координат (и-1) ребрами выпуклого многогранника.
Возрастание от нуля значения некоторой свободной переменной может привести к тому, что эта переменная станет базисной. Для того чтобы получить в качестве решения вершину, необходимо заменить одну из базисных переменных на свободную, т.е. произвести соответствующее перемещение вдоль одной из координатных осей до тех пор, пока не будет достигнута другая вершина.
Если давиться дальше, то будет нарушено условие неотрицательности переменных. Таким образом, в симплекс-методе начинают с локальной координатной системы с началом координат, соответствующим решению, и перемещаются вдоль ребра к соседней вершине„в которой значение целевой функции «улучшается». После перехода в новую вершину рассматривают новую систему координат с началом в этой вершине. Если движение осуществляют согласно критерию (выбирают минимальный отрицательный коэффициент при неизвестных в целевой функции), то это соответствует спуску по самому крутому ребру из всех пересекающихся в начале координат. Величину изменения целевой функции за одну итерацию определяют как углом наклона (крутизной) ребра, так и длиной ребра.
Более точно она равна минимальному значению по 1 величины ! ° с,Ь, /а«~ для данного /, где а; — соответствующий элемент вектора-столбца а, для у' -й свободной переменной. Замечание. Итак, в симплекс-методе всегда считают, что в первую таблицу внесено допустимое базисное решение. В задачах, описывающих реальные системы, допустимое базисное решение подобрать трудно. Для этого решают вспомогательную задачу линейного программирования, которая позволяет не только найти допустимое базисное решение, но н установить, совместна ли система ограничений исходной задачи. Пусть система ограничений исходной задачи записана в следующем виде: л Ь, — х акх =О, 1=1,т, Э си где Ь, > О,! =1,т.
Этого нетрудно добиться, умножив при необходимости уравнения на -1. 694 П уложения Введем новые переменные ~,=Ь,-, 'а,х э=! и рассмотрим целевую функцию (П2.12) у'(г,)=~ Р„-+пни. (П2.13) ~=! Допустимое решение для задачи (П2.12), (П2.13) сразу задано. В процессе решения задачи возможны следующие случаи; 1) пипГ(~)=О, г„=О, !=11,»! (все Ь„стали свободными переменными) — полученное решение х, у = 1,и, является допустимым решением исходной задачи l' линейного программирования; 2) пип г" (г,) > Π— система ограничений исходной задачи несовместна. В первом случае можно отметить две особенности: 1) целевая функция у" (г,) достигла своего минимума, равного нулю, а некоторые из переменных Ь„находятся среди базисных, хотя и равны нулю.
При этом нет необходимости обращать внимание на знаки в строке для целевой функции (можно любую свободную переменную выводить в базисные), т.к. значение целевой функции не изменится, но следует выполнять условия, обеспечивающие допустимость нового базисного решения (рассмотреть минимальное положительное отношение); 2) даже после выполнения предыдущего пункта в строке для базисной переменной г„нет положительных элементов (нельзя получить положительное отношение). Это означает, что переменные, входящие в уравнение для г„с ненулевыми коэффициентами, должны быть равны нулю в данной задаче.
В процессе дальнейшего решения их надо исключать из рассмотрения. Нарялу с решением вспомогательной задачи линейного программирования (П2.12), (П2.13) преобразуется и целевая функция исходной задачи, которая приписывается в задаче (П2.12), (П2.13) в виде дополнительной строки. МЕТОД ПОЛНОГО ИСКЛЮЧЕНИЯ ЖОРДАНА ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ а! ! х, + амхэ ь... + а„х, ь... + а!„х„= Ц; а,! х! + а,зхз +... + а„.х,, +... + а,„х„= Ь,; а, х, + а„, зха в...
в а„„х, +... + а „х„= Ь„,. На каждом шаге симплекс-метода требуется определять новые «наборы» базис- и !х и свободных переменных, т.е, решать системы линейных алгебраических уравнений. Задачи линейного программирования решают с помощью стандартных симплекс-таблиц, формализующих алгоритм перевода базисных переменных в свободные. Этот алгоритм и определяет конкретный вид симплекс-таблиц. Рассмотрим симплекс-таблицы, преобразуемые с помощью метода полного исключения Жордана, получившего наибольшее распространение в линейном программировании. Рассмотри систему а! линейных алгебраических уравнений с л неизвестными П уложение 2. Математическое п о амму рвание основные положения) 695 В методе полного исключения Жардана делают такие преобразования, в результате которых в каждой строке и в каждом столбце матрицы системы линейных алгебраических уравнений остаются по одному неизвестному с коэффициентами, равными едшшце.
Например, мы хотим исключить переменную х,. из всех строк за исключением ьй строки. Элемент аь — коэффициент, стоящий перед переменной х,, называют генеральным элементом, ~ -я строка и л-й столбец — раэрешающимш Прежде всего, разрешающую строку делят на ан и она остается неизменной. Чтобы исключить х, из первого уравнения, умножим разрешающую строку на (-а„) и сложим с первой строкой. В результате получим первую строку с нулевым элементом на месте а„. Аналогично исключаем хь в остальных строках.
Получим новую эквивалентную запись системы алгебраических уравнений. В ней ~'-я строка имеет прежний вид, но все коэффициенты у нее поделены на аи; г -й столбец состоит из нулевых элементов (кроме единицы, стоящей в )-й строке). Остальные элементы матрицы системы и столбец свободных переменных пересчитываются по правилу прямоугольника. Наи аиа,„— аиа,„ пример, новое значение элемента а,„будет равно а,„= а„ а~ !ь аи ..8.. с Г а аи ! аы ! а новое значение Ь столбца свободных членов — Ь„", = аь 1 ! а ! Ь и г а, »3 Из правил прямоугольника следует, что когда в разрешающей строке (столбце) есть нулевые элементы, то элементы столбцов (строк), пересекающих эти нулевые элементы, остаются без изменений.
В процессе решения задач линейного программирования симплекс- методом возможно «зацикливание». Поясним его суть. Пусть в процессе решения задачи линейного программирования на некотором шаге симплекс-метода наименьших положи- 696 П уложения тельных отношений свободных членов к коэффициентам разрешающего столбца оказалось больше одного, т.е. выбор разрешающего элемента неоднозначен. После этого шага все упомянутые свободные члены, за исключением свободного члена разрешающей строки, обратятся в нуль.
Этот случай называют вырождеиным: сливаются две или большее число вершин выпуклого многогранника О, когда ребро (или ребра), соединяющие эти вершины, стягиваются в точку. В алгоритме симплекс-метода каждый шаг означает переход по ребру от данной вершины многогранника В к соседней (расположенной на том же ребре), а при вырождении — совпадении двух соседних вершин — алгоритм может потерять монотонность, т.е. может случиться, что после указанного шага мы остались в той же вершине, только выраженной с помощью другого набора из и уравнений, относящихся к этой вершине.
Если продолжать решение симплекс-методом, то не исключено, что после некоторого числа шагов мы вернемся к уже взятой ранее вершине и процесс начнет повторяться. Произойдет зацикливание. Если в процессе решения проводилось запоминание уже испытанных ребер, то для прерывания зацикливания достаточно сменить генеральный элемент.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
