Определители

Понятие «определитель» возникло в связи с задачей решения систем линейных уравнений. Возьмем какое-нибудь поле К и рассмотрим простейшие системы уравнений 1-й степени с двумя и тремя неизвестными с коэффициентами из К. Система двух линейных уравнений с двумя неизвестными записывается в следующем виде:

где - заданные числа из К. Матрицы

называется соответственной основной и расширенной матрицами системы (1). Чтобы исключить неизвестное, умножим первое из уравнений на, второе на и сложим их. В результате получим уравнение

Если, то из этого уравнения и аналогичного уравнения, получающегося путем исключения, получим

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

С помощью определителей формулы (2) можно переписать в виде

Решая аналогичным путем систему трех уравнений

, (5)

с тремя неизвестными, получим

и аналогичные выражения для. Конечно, эти выражения имеют смысл лишь в том случае, когда знаменатель их отличен от нуля. Матрицы

называются снова основной и расширенной матрицами системы уравнений (5). Знаменатель в формуле (6) называется определителем или детерминантом квадратной матрицы 3-го порядка А. Итак, согласно определению

(7)

Объединяя справа члены, содержащие элементы, и вспоминая формулу (3), получим

=. (8)

Формулу (8) легко запомнить. Для краткости вместо того, чтобы говорить определитель матрицы 2-го порядка, 3-го порядка, говорят определитель 2-го, 3-го порядка. Три определителя 2-го порядка в формуле (8) получаются из находящегося в ней определителя 3-го порядка вычеркиванием первой строки и соответственно 1-го, 2-го и 3-го столбцов. Далее, определитель 2-го порядка, получившийся вычеркиванием 1-й строки и j- го столбца, следует умножить на элемент, находящийся в первой строке и j- м столбце, все произведения снабдить чередующимися знаками и сложить. В результате и получится определитель 3-го порядка.

Глава 1

Классификация методов математического программирования

Оптимизация — это целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях. Постановка задачи оптимизации предполагает наличие объекта оптимизации, будь то человеческая деятельность в течение определенного периода времени или производственный процесс. Решение любой задачи оптимизации начинают с выявления цели оптимизации, т. е. формулировки требований, предъявляе­мых к объекту оптимизации. От того, насколько правильно выра­жены эти требования, может зависеть возможность решения за­дачи. Типичным случаем неправильной постановки условий задачи оптимизации является распространенная ошибка, когда предла­гается найти оптимальные значения нескольких величин одновре­менно, например «получить максимальный выход продукции при минимальном расходе сырья». Поскольку минимальный расход сырья, очевидно, равен нулю, ни о каком максимальном выходе продукции здесь нельзя говорить. Правильная постановка оптимальной задачи при этом будет в любом из следующих вариантов: «получить максимальный выход продукции при заданном расходе сырья» или «для заданного вы­хода продукции обеспечить минимальный расход сырья». В каж­дой такой формулировке соблюдается требование нахождения оп­тимального значения только одной величины, что является необ­ходимым условием постановки оптимальной задачи.

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

1) Требование оптимизации только одной величины;

2) Наличие степеней сво­боды у оптимизируемого объекта — управляющих воздействий;

3) Возможность количественной оценки оптимизируемой величины.

Математическое программирование предполагает построение алгоритмов решения задач оптимизации (задач оптимального планирования). В зависимости от свойств целевой функции и ограничений математическое программирование подразделяестся на: линейное; нелинейное (нелинейное при линейных ограничениях: выпуклое; сепарабельное; квадратичное; геометрическое). Это разделение неслучайно. Оно определяется отсутствием универсальных методов решения задач нелинейного программи­рования, для которого разработаны лишь эффективные методы решения отдельных классов задач. Задачи оптимизации связаны с вопросами эффективного использования или распределения ограниченных ресурсов для достижения желаемых целей. Характерной чертой задач оптимизации является большое число реше­ний, удовлетворяющих условиям задачи. Выбор конкретного решения, как "наилучшего", зависит от функции цели (показатель качества, критерий оптимальности, функция качества, критерий эффективности и т.д. - си­нонимы). Задача, допускающая лишь одно решение_, не требует оптимиза­ции.

В общем плане, существующие методы математического программирова­ния подразделяются на аналитические и численные

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

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

Решение задач оптимизации численными методами представляет собой два этапа:

Первый этап - сбор информации об объекте;

Алгоритм сбора информации должен быть

1) прост;

2) должен обеспечивать процедуру решения наиболее полной информацией об объекте;

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

На втором этапе строится процедура решения на базе проанали­зированной информации.

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

Дата добавления: 2014-01-06