    
Раздел: Документация
0 ... 35 36 37 38 39 40 41 ... 162 Сформировать блок для решения этой вспомогательной задачи ЛП: Given A-X+iden t i ty[m) Y=C X>0 Y> 0  :=minim±z<s(f, X, У) f(X, Y) = Если оптимальное значение целевой функции f больше нуля, то система АХ = с не имеет неотрицательных базисных решений. В противном случае проверяется линейная независимость столбцов матрицы А, соответствующих положительным координатам найденного вектора х (вектор У должен быть нулевым- см. решение задачи TI6.11): S: = kol<r- 0 foriGl/л if x. . >0 if kol = 0 kol*-l M<- A-" M<r- augment (M,A") otherwise s < "X is oporni" if rank (Ml- cois (M) s <- X is not oporni"otherwise С помощью этого программного блока строится матрица состоящая из столбцов матрицы л, соответствующих положительным координатам вектора х, и затем проверяется линейная независимость столбцов матрицы м с помощью функции rank; функция rank определяет наибольшее число линейно независимых столбцов матрицы (ранг матрицы). К16.1. Ответы: Хт=<0, 0, 4.143 25, 0.916 53, 2.805 24, 0, 0, 0). К16.2. Ответы: система не имеет неотрицательных базисных решений. Глава 17 find  Симплекс-метод Если множество планов задачи (16.1) - (16.2) является многогранником, то благодаря теоремам предьщущего параграфа задачу можно решить так: найти все вершины многогранника (как, например, в задаче П16.1) и выбрать из них ту, в которой целевая функция принимает оптимальное значение. Однако такой тотальный перебор нерационален, поскольку требует значительного объема вычислений. Кроме того, если множество планов задачи - полиэдр, то целевая функция может оказаться неограниченной. Существует процедура направленного перебора вершин полиэдра; если известна какая-либо вершина, то выбирается соседняя с ней вершина, в которой значение целевой функции не хуже, чем в предыдущей, и процесс продолжается до тех пор, пока не будет найдена оптимальная вершина или не будет установлена неограниченность целевой функции. Таким образом, реализация симплекс-метода состоит из следующих этапов: 1.Определение начальной вершины. 2.Проверка признака оптимальности вершины или признака неограниченности функции. 3.Правило перехода к соседней вершине. Для дальнейшего потребуется процедура жордановской перестановки нары переменных. Опишем ее. Пусть даны т линейных уравнений где zb z„-независимые (свободные) переменные, у, ,},„-зависимые переменные. Эти уравнения можно записать в виде так называемой si-таблицы (17.2). У> =ьл "X6 zk, \ =1,2,.... «г (17.1) ~Z\......... -г. \......... --Л ~Ьп..... ~ЬЬ (17.2) Ут = "ml) От этой табличной записи можно легко перейти к обычной- для этого надо ска-лярно умножить верхнюю строку (которая называется строкой свободных переменных) на каждую из строк таблицы, приравняв результаты к соответствующим переменным у\,..., у,„. Предположив, что необходимо поменять ролямипревратить в зависимую переменную, a z3 - в независимую (при условии, что 6„;*0). Естественно, что это приведет к изменению вида системы (17.1) и si-таблицы (17.2). Такое преобразование si-таблицы назовем жордановой перестановкой переменных у, и z„ или жордановой перестановкой с разрешающим элементом h„. Строка и столбец в таблице, содержащие также называются разрешающими. Утверждение 17.1. Результатом жордановой перестановки с разрешающим элементом Ьгл является si-таблица (17.3).
(17.3) Таблица (17.3) получается из (17,2) следующим образом: переменные vr и г, меняются местами; разрешающий элемент заменяется обратной величиной; остальные элементы разрешающей строки делятся на разрешающий элемент; прочие элементы Ьл к Фs) рассчитываются по формулам b. = b.k. Последнее соотношение называется правилом "прямоугольника" из-за определенного расположения чисел, участвующих в пересчете: -Ьл.......ь1х... 0 ... 35 36 37 38 39 40 41 ... 162 |
||||||||||||||||||||||||||||||||||||||
