Evaluation of the solution to linear programming problems with approximate data in Lp-norms

Введение

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

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

Изученность проблемы достаточно полно представлена для систем линейных алгебраических уравнений с приближенными коэффициентами в работах [1-4] и линейных операторов, «возмущения» которых изучались в нормированных пространствах общего вида [5].

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

Научная новизна заключается в том, что исследования проведены в n-мерном пространстве с различными L_p-нормами для задач линейного программирования (ЗЛП) в общем виде, что важно при практическом применении.ЗЛП в математической форме имеет вид:

(1)

где –неотрицательный вектор-столбец искомых переменных ; – матрица известных коэффициентов размера – вектор известных данных ; – заданная линейная целевая функция (см. [7-12]).

Трудность решения вычислительной задачи линейного программирования определяется тем, что как элементы матрицы , так и вектор данных на практике известны неточно, с определенной погрешностью. В некоторых случаях, определяемых структурой матрицы, это может настолько сильно исказить оптимальное решение , что его нельзя будет принять за ответ и использовать в практической деятельности. Такие задачи относят к классу плохо обусловленных вычислительных задач в отличие от некорректных задач, рассмотренных в [13], которые после проведения регуляризации становятся корректными. Считаем, что для каждого n-мерного вектора определена и фиксирована для вещественного числа р, , L_p-норма .Такие пространства мы обозначаем , это полные нормированные пространства (банаховы) [14,15]. Наиболее употребительными являются следующие три пространства, определяемые нормами:

, выбор нормы определяется случаем, когда учитывается суммарная абсолютная величина координат вектора; - евклидова норма; , выбор нормы означает, что учитывается максимальная абсолютная компонента вектора.

Большинство вычислительных задач в математике может быть записано в виде y = А(x), где А – некоторое преобразование, действующее из нормированного пространства в нормированное пространство . Для оценки величин погрешностей приближения к входному данному х и приближенного решения к точному у введены некоторые их меры: абсолютные погрешности (используется норма пространства ), (используется норма пространства ) и относительные погрешности , .

Предполагаем, что вычислительная задача корректна, а именно: 1) для определенного множества допустимых входных данных х из решение у из пространства существует; 2) единственно; 3) устойчиво. Наличие устойчивости означает, что решение у может быть приближено последовательностью элементов с любой точностью. На практике конечные погрешности входных данных могут настолько сильно исказить результат, что его нельзя будет принять за приближение точного решения.

Если между абсолютными погрешностями входных данных и решения вычислительной задачи установлено неравенство , то величина называется абсолютным коэффициентом обусловленности; в частности, величина называется абсолютным числом обусловленности; здесь нормы обратной матриц (см. [3]).Если установлено неравенство между относительными погрешностями данных и решения, то величину n_d называют относительным коэффициентом обусловленности.

Вычислительную задачу А(х) называют хорошо обусловленной, если погрешностям входных данных отвечают погрешности решения, обеспечивающие принятие нами приближенного решения с требуемой точностью, и плохо обусловленной, если возможные погрешности настолько искажают приближенное решение у^*, что его нельзя принять за решение задачи с заданной точностью (см. [4], [16-19].

Приведем пример плохо обусловленной ЗЛП:

,

,

;

;

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

Если изменить вектор данных в первоначальной системе, уменьшив вторую координату на 1, получим ЗЛП ), для которой оптимальное решение ; . Опять имеем плохо обусловленную задачу.

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

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

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

Методология исследования проблемы обусловленности вычислительных задач линейного программирования с приближенно известными данными заключалась в последовательной постановке в начале менее сложной задачи, ее решению, и переходе к решению более сложных задач. Для решения поставленных задач использовались методы линейной алгебры ( [3], [5], [12], [20-22]), исследования операций [6-11], вычислительной математики ( [4], [16-19]) и функционального анализа [14, 15].

1. оценка погрешности решения Злп с приближенно заданной правой частью

Предполагаем, что ЗЛП приведена к канонической форме

,

и известна невырожденная матрица (считаем ранг ) при оптимальном базисном решении (см. [4], [6], [8], [10]). Рассматриваем случай, когда приближенно заданы исходные данные, вектор-столбец а элементы матрицы системы уравнений известны точно.

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

1) Для точного конкретного решения системы верны следующие оценки абсолютной и относительной погрешностей приближения к :

2) Для любого решения системы справедлива оценка

3)Справедлива оценка погрешности значений целевой функции: где показатель q определяется из формулы

Оценку 1) получаем из последовательности следующих преобразований:

Оценку относительной погрешности решения в пункте 2)получаем из неравенств:

Обозначаем через решение системы в которой правая часть есть приближение к , тогда где неотрицательный ортант. Пусть решение системы и Используя неравенство Минковского (см. [14, 15]), получаем оценку абсолютной погрешности 3) значений целевой функции

где .

2. оценка погрешности решения Злп с приближенно заданной матрицей

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

Теорема 2. (Достаточное условие не вырождения матрицы ).

Если абсолютная погрешность матрицы удовлетворяет ограничению

,

то матрица является невырожденной.

Обозначая через матрицу погрешностей, получаем равенство

Отсюда следует, что матрица невырожденная тогда и только тогда, когда невырожденная матрица . Из [3, 5] известно, что если то это верно. Это справедливо и когда

Отсюда получаем оценку , что и требовалось установить. Отметим, что если матрица вырожденная, то

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

Теорема 3. Пусть и есть решения систем и , причем - невырожденная матрица. Если то справедливы следующие оценки абсолютной и относительной погрешностей приближенного решения : , .

В силу теоремы 2 матрица невырожденная и имеет обратную тогда получаем следующую цепочку неравенств:

Отсюда имеем искомую оценку

3. ОЦЕНКА погрешностиРЕШЕНИЯ ЗЛП В ОБЩЕМ СЛУЧАЕ с приближенно ЗАДАННЫМИКОЭФФИЦИЕНТАМИ СИСТЕМЫ ОГРАНИЧЕНИЙ И ПРАВОЙ ЧАСТЬЮ

Предполагаем, что ЗЛП приведена к канонической форме

,

и известна невырожденная матрица (ранг ) при оптимальном базисном решении (см. [4], [6], [8], [10]). Рассматриваем случай, когда приближенно заданы исходные данные, вектор-столбец и элементы матрицы . Пусть А – невырожденная матрица, - возмущенная матрица, то есть , где - произвольная матрица возмущения.

При выполнении указанного в теореме 2 достаточного условия матрица невырожденная, поэтому справедливы равенства:

=

и оценка (используется неравенство верное при ):

. Отсюда получаем следующую оценку относительной погрешности матрицы возмущений :

где есть число обусловленности матрицы . Итак, справедлива

Теорема 4. При малом относительном возмущении матрицы А: (или ) и не слишком большом числе обусловленности матрицы относительная погрешность обратной матрицы возмущений будет мала:

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

.

Это означает, что верна окончательная оценка

.

В полученной формуле важно, чтобы коэффициент обусловленности а также число обусловленности матрицы А, были не слишком большими. В частности, имеем , если , то есть в этом случае нулевая матрица.

Сформулируем основную теорему данного раздела.

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

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

.

В случае отсутствия возмущения основной матрицы А системы, тогда , имеем оценку из теоремы 1: .

Отметим, что когда (много меньше 1), можно использовать более простую, но менее точную формулу:

.

4. Пример исследования обусловленности вычислительной задачи с возмущенной системой ограничений ЗЛП

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

,

,

;

.

Очевидно, задача имеет решение , Находим число обусловленности невырожденной матрицы в норме при , вычислив одним из известных способов обратную матрицу ,

Рассмотрим возмущенную систему ограничений

или .

В первом неравенстве коэффициент 1 при неизвестном заменен на . Для этой задачи решением является вектор , . Разница между решениями по норме (p=1) огромна.

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

Достаточные условия теоремы 3 будут выполнены, если задать ; тогда и справедлива следующая оценка относительной погрешности приближения решения к решению (естественно, считаем ):

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

Чтобы обеспечить вычисление приближенного решения ЗЛП с заданной точностью, например, чтобы относительная погрешность решения составляла величину не больше некоторого постоянного числа , достаточно требовать выполнения неравенств:

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

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

Заключение

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