Файл: Общее математическое обеспечение для решения задач экономики, статистики и управления на ЭВМ Минск-32 тезисы докладов и сообщений..pdf

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

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

Рассмотренная схема опознавания в настоящее время реали­ зована и функционирует в составе программно-аппаратного комплекса. Объем программного обеспечения — около 12000 команд.

А. А. Кузьмина

РЕАЛИЗАЦИЯ МУЛЬТИПЛИКАТИВНОГО СИМПЛЕКСНОГО АЛГОРИТМА

Для машины «Минск-32» на ЯСК составлена программа решения общей задачи линейного программирования с двусто­ ронними ограничениями на неизвестные.

Формулировка задачи.

Требуется найти вектор х15.. ., х„ максимизирующий линей-

П

ную форму f(x) = £ CjXj и удовлетворяющей системе ограни-

Матрица А = (atj) коэффициентов при неизвестных в ограниче­ ниях (1.1) предполагается заполненной на 15—30%.

Программа составлена для машины в неполном комплекте (с оперативным запоминающим устройством объемом 16384 ячейки). Этим определяются некоторые особенности составленной программы. Составлены вспомогательные программы, работаю-

124

щие независимо от основной программы, которые записывают исходные данные на МЛ. Основная программа, реализующая мультипликативный симплексный алгоритм, состоит из 4-х час­ тей, записанных на МЛ, и поочередно вызываемых головной программой в оперативную память, В каждый момент времени в оперативной памяти находится и работает только одна из этих частей. В памяти машины хранятся только ненулевые элементы исходной и промежуточной информации.

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

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

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

По окончании работы этой части программы мы будем иметь обратную матрицу базиса В~1 в мультипликативном представле­ нии и базисное решение В~ 1Ъ. Может оказаться, что часть переменных не удовлетворяет ограничениям (1.2). В этом случае формируется столбец невязок и вводится в базис с большой отрицательной ценой.

Затем вводится и выполняется часть программы, осущест­ вляющая основные операции симплексного мультипликативного алгоритма. Выбирается минимальное Aj в рассматриваемой

данной части и хк = 0 (хк = fik).

125

Для выбора вектора выводимого из базиса ищется

в = min-l пи

Jx — множество номеров базисных столбцов. Если в = fi, то базис не изменяется, изменяется лишь решение.

Преобразование решения производится по формулам

Если отрицательных Aj в рассматриваемой части исходной матрицы нет, то вызывается следующая часть матрицы и т. д., пока не исследуем все части матрицы. Если ни в одной из частей матрицы отрицательных Дj нет, то в оперативную память вызы­ вается та часть программы, которая осуществляет процедуру «повторения».

«Повторение» необходимо для избавления от возможного накопления ошибок.

При повторном обнаружении ситуации: все Д; 3> 0 — решение считается найденным. Тогда в оперативную память вызывается часть программы, производящая выдачу результатов. Печатается оптимальное решение, значение целевой функции, число итера­ ций, объективно обусловленные оценки, пределы изменения коэффициентов функционала, в которых оптимальное решение не меняется, пределы изменения правых частей ограничений (1,1), в которых объективно обусловленные оценки остаются неизмен­ ными. Печатается также результат подстановки решения в систе­ му ограничений (1,1), равный

тп

Допустимый объем решаемых задач т < 127, п s$ 1000.

126

Е. В. Кузнецова, В. Г. Сырцов

ПРОГРАММА «СИМПЛЕКС-32»

Для решения задач линейного программирования больших размеров составлена программа, реализующая модифицирован­ ный симплекс-метод с мультипликативным представлением об­ ратной матрицы на ЭВМ «Минск-32» с использованием магнит­ ных лент.

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

Предусмотрена возможность повторения счета с любой пор­ ции итераций.

Предусмотрен сброс итераций, который состоит в том, что через некоторое число итераций счет повторяется, но ввод пере­ менной в базис определяется ее наличием в последнем перед сбросом плане.

Ведется анализ: если вектор вводился, то по возможности он в базис не вводится.

Программа «Симплекс-32» снабжена комплексом обслужи­ вающих программ:

—подготовка канонической матрицы ограничений на магнит­ ной ленте;

—вывод на печать промежуточных, опорных и оптимальных планов в упорядоченном виде;

—дублирование магнитных лент.

Я. Г. Новрузбеков, Н. С. Матвеева

ПРОГРАММЫ ДЛЯ ОТЫСКАНИЯ ЛОКАЛЬНОГО МИНИМУМА ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ НА ОСНОВЕ МЕТОДОВ РОЗЕНБРОКА, СОПРЯЖЕННЫХ ГРАДИЕНТОВ И ПОКООРДИНАТНОГО СПУСКА. СРАВНЕНИЕ ЛОКАЛЬНЫХ МЕТОДОВ

Описание метода Розенброка

На минимизирующую функцию сильных ограничений не накладывается. Знания аналитического выражения самой функции

127

и ее производных не требуется достаточно знать значение функции в любой точке. Поиск минимума происходит по ортогональным изменяющимся направлениям. Начальной системой ортогональ­ ных направлений S?, 5 °,.. . S ° являются координатные оси. Движение к минимуму производится по каждому из направлений

S k ( k = 1,л):

х п+1= X'1-{•• ik • Sk

Сначала производится шаг произвольной длины i k. Шаг счи­ тается удачным, если,

/(* " +!) < /(*")

в противном случае шаг неудачный, В случае удачи длина шага увеличивается в а раз. В случае неудачи делается отход на вели­ чину —fi, причем движение осуществляется по направлению (— Sk). Если по каждому из ортогональных направлений S k будет сделано, по крайней мере, по одному успешному и неуспешному шагу, то производится смена ортогональных направлений.

Новые направления определятся следующим образом. При движении по каждому из направлений S k запоминается алгебра­ ическая сумма всех успешных шагов d k

! 2-S

Характеристика программы

Программа составлена на языке АЛГАМС. Начальное зна­ чение шага 1к выбирается в пределах 0,05 -г 0,2.

Через каждые 20 шагов запоминается минимальное значение f(x ) и сравнивается с текущим минимумом, это позволяет уло­ вить момент зацикливания в окрестности точки локального ми­ нимума. Под «зацикливанием» понимаем возврат траектории поиска в исходную точку после некоторого количества смен ортогональных направлений. Зацикливание происходит в том случае, когда в окрестности минимума величина шага 1к оказы­ вается большой. В этом случае 1к уменьшается в 10 раз, и так до следующего зацикливания. Найденная точка считается точкой

f(x ) за последующие 20 шагов.

Вычисление значения функции входит в программу как про­ цедура-функция.

Описание метода сопряженных градиентов

Поиск минимума f(x), где х е Е„, производится по меняю­ щимся ортогональным направлениям. Для того, чтобы построить новое направление, необходимо знать градиент функции в пре­ дыдущем шаге поиска. Новые сопряженные направления опре­ деляются по формулам:

S( + i = — di+i + fii$i

(gj+i> gj+i) i = 0, 1, 2 .. . n— i,

(9t, 9i)

(S0 = — go, go = 9rad f (x0)). Следующее приближение находим так

JC"+1 = x"+ djs„

При этом необходимо выполнение

/(* "+1) < Я**).

129