Вычисление производной примеры решения задач Матрица Вычисление предела Векторная алгебра и аналитическая геометрия Вычитание векторов Скалярное произведение векторов Кривые второго порядка Прямая в пространстве

Матрица примеры решения задач

Элементы линейной алгебры

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

Алгебраическое дополнение элемента обозначают . Согласно определению:

Для определителя 3-го порядка знаки алгебраических дополнений определяются по таблице:

+

-

+

-

+

-

+

-

+

Например, алгебраическое дополнение элемента определителя (1.3) равно минору этого элемента, взятому со знаком минус:

.

Из определения определителя 3-го порядка вытекает, что

.

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

Таким образом, имеет место шесть разложений:

(1.4)

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

 Раздел II. Линейное программирование.

  Тема: Решение ЗЛП, используя симплекс- метод.

 Геометрическая интерпретация.

Реальные задачи линейного программирования содержат, как правило, большое число ограничений и неизвестных.

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

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

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

I. Симплекс- метод.

Для применения симплекс – метода к решению задачи линейного программирования требуется ее представление в каноническом, допустимом виде.

Пусть дана система m линейных уравнений с n неизвестными и линейная функция f.

Среди неотрицательных решений системы нужно найти такое, которой минимизирует функцию.

 

 


Система уравнений приведена к допустимому виду, если

Какие-то неизвестные выражены через остальные неизвестные.

Свободные члены уравнений должны быть неотрицательными.

Неизвестные в допустимом виде системы, которые выражены через остальные, называются базисными, а весь набор этих неизвест­ных - допус­тимым базисом неизвестных (обозначим для краткости одной буквой Б).

Остальные неизвестные называются небазисными или свободными.

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

Алгоритм решения ЗЛП по симплекс-методу:

Выделить исходный допустимый базис и заполнить первую таблицу.

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

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

Все свободные переменные в этом случае равны нулю.

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

Столбец, соответствующий этому элементу называется разрешающим.

Если в разрешающем столбце все элементы отрицательные, то задача не имеет решения, (минимум не достигается).

Вычислить отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение).

Найти наименьшее из этих симплекс-отношений, оно соответствует разрешающей строке.

На пересечении разрешающего столбца и разрешающей строки найти разрешающий элемент.

Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них.

То же самое относится к положительным элементам последней строки симплекс-таблицы.

После нахождения разрешающего элемента перейти к следующей таблице.

Заменить переменную, соответствующую разрешающей строке на переменную соответствующую разрешающему столбцу. При этом базисная переменная становится свободной переменной и наоборот.

Все элементы разрешающей строки разделить на разрешающий элемент.

Все элементы разрешающего столбца, кроме разрешающего элемента заменить 0.

Все остальные элементы таблицы рассчитать по правилу прямоугольника.

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

Продолжить выполнение алгоритма с пункта №2.


Скалярное произведение векторов