ПОИСК Статьи Рисунки Таблицы Алгоритм симплексного метода из "Методы оптимизации в химической технологии издание 2" Как уже отмечалось выше, симплексный метод по существу является шаговым циклическим методом, в котором одна и та же совокупность вычислительных операций выполняется для различных массивов цифровой информации. Такими массивами служат матрицы базисных и небазисных векторов, между которыми осуществляется обмен информации после каждого шага симплексного метода, Вследствие этого содержание указанных массивов изменяется в процессе вычислений, что должно найти отражение в формульной записи используемых алгоритмов счета. [c.447] В практике машинных расчетов для реализации циклических процессов счета широко применяется прием размещения информации в так называемых стандартных ячейках памяти. Программа расчета для формульной части задачи при этом записывается в адресах ячеек безотносительно к их фактическому содержанию на данном цикле вычислений. Изменение информации, содержащейся в стандартных ячейках, осуществляется специальной программой обмена (циркуляции) информации между ячейками, алгоритм которой либо содержится в самом методе вычислений, либо разрабатывается специально с учетом применения к конкретной вычислительной машине. [c.447] Ниже при изложении одного из возможных вариантов алгоритма симплексного метода использован прием циркуляции информации в стандартных ячейках, имеющих собственную индексацию. [c.447] Элементы yis (i = 1,. .., т) вектора У8 используются для хранения любого вектора-столбца Up матрицы ограничений (VIII, 196), соответствующего независимой переменной Xj. Остальные три элемента уis (i = т + 1, т + 2, т + 3) применяются для хранения остальной информации задачи, относящейся к этой переменной. Элемент ym+i,s предназначен для хранения значения коэффициента j линейной формы (VIII, 194), отвечающего этой переменной. Элемент ym+i,s служит для хранения значения переменной Xj, которое она имеет на данном этапе вычислений. Наконец, элемент Ут+з, s предназначен для хранения значения индекса / переменной Xj, присвоенного ей в исходной формулировке задачи линейного программирования. [c.448] Матрицу (VIII,205), вообще говоря, не обязательно запоминать целиком в процессе вычислений, о чем сказано ниже. [c.449] Поскольку значения переменных, отвечающих небазисным векторам,. в базисном решении равны нулю, элементы ym+2,k векторов Yh (k = 1,. . . , /г) всегда содержат нули и практически могут быть использованы в качестве рабочих ячеек памяти программы вычислений для записи промежуточных результатов расчета, например для записи маргинальных значений Vh, определяемых для небазисных векторов. [c.450] Вследствие того что матрица, обратная единичной, является также единичной, обратная матрица начального базиса на начальном этапе может считаться известной, а в массиве ячеек, отведенном для размещения обратной матрицы базиса [р ], записывается единичная матрица. [c.450] На этом размещение исходной информации заканчивается и начинается выполнение этапов алгоритма симплексного метода. [c.450] Если при этом для какого-либо столбца xk найти значение QPh нельзя из-за того, что все элементы данного столбца отрицательны, максимальное значение критерия оптимальности (VIII, 194) не ограничено и может быть сделано сколь угодно большим. В этом случае решение задачи прекращается и соответствующая информация выдается на печать. [c.451] Этап 7. Производится обмен информацией между массивами базисных и небазисных векторов. Обобщенный вектор Yn+p пересылается на место обобщенного небазисного вектора Yh и наоборот. При этом элемент ym+z, n+p обобщенного вектора Yn+p, выводимого из базиса, полагается равным нулю, что отвечает исключению данного вектора из числа базисных. Значение же элемента ym+2,h небазисного вектора Yh после пересылки его на место вектора Yh принимается равным величине 0Pk, что соответствует включению этого вектора в базис. [c.452] Применение формул (VIII, 215) требует наличия дополнительной памяти при вычислении обратной матрицы нового базиса. Однако их можно так преобразовать, чтобы вновь рассчитываемые элементы записывать сразу на место прежних. Поскольку каждый элемент обратной матрицы исходного базиса, за исключением элементов р-й строки, только один раз используется в процессе вычислений, поэтому можно следующим образом организовать расчет элементов обратной матрицы нового базиса. [c.452] После окончания этого этапа вычислений производится переход к следующему шагу симплексного метода, т. е. расчет повторяется, начиная с этапа 1. [c.453] В рассмотренном алгоритме предполагалось, что матрица разложения небазисных векторов [х ] по векторам исходного базиса вычисляется сразу и, следовательно, должна быть размещена в запоминающем устройстве вычислительной машины. Это требует дополнительно т2 ячеек памяти, что представляет определенные неудобства при решении задач высокой размерности. [c.453] Однако можно избежать необходимости запоминания всей матрицы коэффициентов разложения небазисных векторов, если объединить выполнение этапов 2—5 ЦИКЛИЧЕСКОЙ программы. Этот вариант требует для хранения коэффициентов разложения небазисных векторов только двух массивов (рабочего и эталонного) по т ячеек в каждом. Основная идея заключается в сравнении приращения критерия оптимальности только для двух небазисных векторов, в результате чего находится вектор, дающий наибольшее приращение, который размещается в эталонном массиве. В дальнейшем каждый следующий- небазисный вектор сравнивается с эталонным, и если он дает большее приращение критерия оптимальности, то его коэффициенты разложения располагаются в эталонном массиве. [c.453] После просмотра всех небазисных векторов в эталонном массиве находятся коэффициенты разложения того небазисного вектора УА, включение которого в исходный базис обеспечивает наибольший прирост критерия оптимальности. Вектор Yn+p, исключаемый из базиса, определяется при этом в процессе отыскания величин Qpk для каждого небазисного вектора по формуле (VIII,213). [c.453] Общий объем памяти, требуемый для размещения числовой информации при решении задачи линейного программирования с п- -т переменными и т ограничениями типа (VIII, 195), исключая память, необходимую для размещения программы вычислений, складывается из массивов 1) для размещения матрицы обобщенных векторов Ys (п + т) (т + 3) ячеек 2) для размещения обратной матрицы исходного базида т2 ячеек 3) для размещения коэффициентов разложения небазисных векторов 2т или т2 ячеек, если матрица коэффициентов разложения небазисных векторов запоминается полностью. [c.453] Вернуться к основной статье