рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Постановка задачи.

Постановка задачи. - раздел Программирование, Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения Решить Систему Линейных Алгебраических Уравнений A11X...

Решить систему линейных алгебраических уравнений

a11x1 + . . . + a1n xn = a10

. . . . . . . . . . . . . . . . . . . . . . (1.1)

am1x1 + . . . + amnxn = am0

что означает:

1.определить, совместимая данная система ли (то есть, имеет ли она хотя бы одно решение);

2.если система совместимая, то, имеет ли она единственное решение, или таких решений множество;

3.найти решение, если он единственный, и найти общее решение в случае существования множества решений.

Вопрос совместимости системы (1.1) решает теорема Кронекера-Капелли, формулировка которой такая:

Система линейных алгебраических уравнений (1.1) совместимая в том и только в том случае, когда совпадают ранги основной и расширенной матриц

a11 . . . a1n a11 . . . a1n a10
А = . . . . . . . . . , A= . . . . . . . . . . . . .
am1 . . . amn am1 . . . amn am0

При этом решение единственное тогда и только затем, когда rang(A)=n. Если же rang(A)=r<n, то обязательно найдутся такие r переменных , что исходная система (1.1) будет эквивалентной системе вида:

(1.2)

где суммирование ведется по j=1...,n, отличных от i1...,ir.

О системе (1.2) говорят, что она решена относительно переменных и имеет каноничный вид.

Общее решение системы (1.2) определяется тривиально:

 

(1.3)

В уравнениях (1.3) переменные xj (j отличное от i1...,ir) — свободные переменные, они могут получать произвольные значения. Каждая совокупность их значений однозначно определяет значение переменных — базисных переменных.

Метод Гаусса является основным законченным методом решить систем линейных алгебраических уравнений (1.1) и заключается в исполнении однотипных превращений исключения.

На 1-м шаге метода находят переменную в 1-м уравнении, коэффициент возле которой не равняется нулю, и исключают эту переменную из всех других уравнений. Если, например, a11 не равняется нулю, то превращения 1-го шага такие: до і-го уравнения прибавить 1-е уравнение, умноженное на число –ai1/a11, i=2...,m.

В результате превращений 1-го шага система (1.1) приобретает вид:

a11x1 + a12x2 + . . . + a1n xn = a10

а¢22х2+ . . . + а¢2nxn = а¢20

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . (1.4)

а¢m2x2 + . . . + а¢mnxn= а¢m0.

На следующем шаге эта же последовательность действий применяется к части системы, что состоит из системы (1.4) без 1-го уравнения и т.д. Упомянутый процесс продолжается до тех пор, пока не будет получена система трапециевидного (в частности, треугольного) вида, или не будет подтвержден признак несовместимости системы.

Описанные превращения составляют прямой ход метода Гаусcа. При прямом ходу превращения выполняются «сверху вниз» — от первого уравнения к последнему. Обратный ход метода Гаусса составляют превращения исключения отделенных при прямом ходу базисных переменных, при этом превращения выполняются в обратном порядке: от последнего уравнения к первому — «снизу вверх».

Прямой и обратный ход метода Гаусса достал название метода полного исключения Жордана-Гаусса.

Кроме основного назначения (как метода решить систем линейных алгебраических уравнений) метод Гаусcа имеет и другие важные применения.

С помощью прямого хода метода Гаусcа можно вычислять численные определители (путем сводки определителя к треугольному виду).

Метод Жордана-Гаусcа позволяет находить обратные матрицы.

Пусть имеем некоторую невырожденную квадратную матрицу:

a11 . . . a1n
A= . . . . . . . . . .
an1 . . . ann

Построим расширенную матрицу вида:

a11 . . . a1n 1 . . . 0
. . . . . . . . . . . . . . . . . .
an1 . . . ann 0 . . . 1

и применим к ней метод Жордана-Гауcса. Если в результате получим матрицу вида:


 

1 . . . 0 b11 . . . b1n
. . . . . . . . . . . . . . . . . . ,
0 . . . 1 bn1 . . . bnn

то

b11 . . . b1n
. . . . . . . . .
bn1 . . . bnn

обратная матрица к исходной матрице А.

Программное обеспечение.

Модуль, который выполняет элементарные превращения матриц, которые лежат в основе метода Гауcса, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Задание.

методом Гауcса системы линейных алгебраических уравнений, расширенные матрицы которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.

методом Гаусса системы линейных алгебраических уравнений, что заданы расширенными матрицами:

1) 2 -2 0 1 -3 2) 1 1 -6 -4 6 3) 2 -1 3 4 5
  2 3 1 -3 -6   3 -1 -6 -4 2   4 -2 5 6 7
  3 4 -1 2 0   2 3 9 2 6   6 -3 7 8 9
  1 3 1 -1 2   3 2 3 8 -7   8 -4 9 10 11

Вычислить следующие определители:

4) 0 1 1 1   5) 1 1 6 4   6) 3 6 5 6 4
  1 0 1 1     3 1 6 4     5 9 7 8 6
  1 1 0 1     2 3 9 2     6 12 13 9 7
  1 1 1 0     3 2 3 8     2 5 4 5 3
                          4 6 6 5 4

Найти обратные к таким матрицам:

7) 1 1 1 1   8) 1 2 3 4   9) 3 6 5 6
  1 1 -1 -1     2 3 1 2     5 9 7 8
  1 -1 1 -1     1 1 1 1     6 12 13 9
  1 -1 -1 1     1 0 2 6     2 5 4 5

 

 


Лабораторная работа 2.

– Конец работы –

Эта тема принадлежит разделу:

Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения

СОДЕРЖАНИЕ... Общие рекомендации по использованию программного обеспечения... Элементарные преобразования матриц Метод Гаусса...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Постановка задачи.

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Программного обеспечения
Программное обеспечение ПО–МО содержит диалоговые обучающие программы из линейных и нелинейных методов оптимизации (математического программирования), каждая из которых вызывается с п

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД
Постановка задачи линейного программирования в стандартной форме (СЗЛП). Найти вектор x=

МОДИФИЦИРОВАН СИМПЛЕКС-МЕТОД.
Изложение модифицированного симплекс-метода. Модифицированный симплекс-метод (МСМ) непосредственно применяется к решению КЗЛП и осуществляет целенапра

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
Изложение двойственного симплекс-метода. Двойственный симплекс-метод (ДСМ) непосредственно применяется к решению почти каноничной задачи линейного програм

Постановка транспортной задачи.
В каждом из пунктов Pi, i=1...,m, производится ai единиц некоторого однородного продукта, а в каждом из пунктов Qj, j=1...,n, потребляется b

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

Свойства транспортной задачи.
1. Сбалансированная транспортная задача всегда допустимая и имеет оптимальное решение. 2. Ранг матрицы А ограничений транспортной

Основные теоремы.
1. Решение транспортной задачи базисное, если из его основных коммуникаций невозможно составить замкнутый маршрут (цикл). 2. ДБР

Метод северо-западного угла.
Метод состоит из однотипных шагов, поэтому его формальное изложение дадим лишь для 1-го шага. Заполняем северо-западную клеточку таблицы, покладая x11 = min{a1,

Алгоритм метода потенциалов.
1. Находится исходное допустимое базисное решение (ДБР), например, с помощью одного из упомянутых выше методов. 2. В дальнейшем метод потенциалов с

Программное обеспечение.
Обучающий модуль, с помощью которого транспортная задача Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО

СПОСОБНОСТЯМИ. МЕТОД ПОТЕНЦИАЛОВ
Постановка транспортной задачи с ограниченными пропускными способностями (ТЗО). В пункте Pi (i=1

Свойства ТЗО и основные теоремы.
1. Ранг сложенной из векторов Aij матрицы А, ограничений транспортной задачи равняется m+n–1, откуда выплывает, чт

Выходной ДБР ТЗО. 1 этап.
На множестве невычеркнутых клеточек транспортной таблицы находят клеточку (i1,j1) с минимальными транспортными расходами

Выходной ДБР ТЗО. II этап.
Пусть X=||xij||, i=1...,m, j=1...,n — матрица перевозок, построенная на первом этапе. Положим xi,n+1 = ai – (

Потенциалы.
Потенциалы строк ui, i=1...,m, и столбцов vj, j=1...,n, определяются как решение системы vj–ui=cij

Оценки.
Оценки Dijпеременных xij для всех небазисных клеточек вычисляются за формулой Dij=cij–vj+ui (оценки базисных переменных — нулевые). Те

Новый ДБР.
Среди всех клеточек (і,j), для присоединяется к совокупности базисных клеточек. которых не выполняется критерий оптимума, избирают клеточку с наибольшим модулем оценки Dij. Пометим та

Алгоритм метода потенциалов.
1. Строится выходной ДБР. 2. Дальше метод потенциалов состоит из однотипных шагов, на каждом из которых: i) Вычисляются потенциалы u

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА СЕТИ. МЕТОД МИНТИ
Постановка задачи о кратчайшем пути на сети. На сети, что задается графом (I,U), где И — множество вершин,

МЕТОД ФОРДА-ФАЛКЕРСОНА
Постановка задачи о максимальном потоке на сети. На сети, что задается графом (I,U), где I — множество вершин,

Постановка целочисленной задачи линейного программирования.
Найти вектор x=(x1...,xn), что минимизирует целевую функцию L(x)= c1x1 + ... + cnxn (9.1)

Изложение метода Гомори-1.
Метод Гомори-1 является одним из методов отсечения, идея которых заключается в следующем. Решается вспомогательная ЗЛП (9.1)–(9.3), которую получают из исходной ЦЗЛП (9.1)–(9

Алгоритм метода Гомори-1.
1. Решаем вспомогательную ЗЛП (9.1)–(9.3). Пусть x(0) — ее оптимальное решение. Если оптимальное решение не существует, то исходная ЦЗЛП также

ПРОГРАММИРОВАНИЯ. МЕТОД ГОМОРИ-2
Постановка частично целочисленной задачи линейного программирования (ЧЦЗЛП). Найти вектор x=(x1...,xn

МЕТОД ГОМОРИ-3
Постановка целочисленной задачи линейного программирования (ЦЗЛП). Найти вектор x=(x1...,xn), что

ПРОГРАММИРОВАНИЯ. МЕТОД ДАЛЬТОНА-ЛЛЕВЕЛИНА
Постановка частично дискретной задачи линейного программирования (ЧДЗЛП). Найти вектор x=(x1...,xn

МЕТОД ВЕТВЕЙ И ГРАНИЦ.
Постановка целочисленной задачи линейного программирования (ЦЗЛП). Найти вектор x=(x1...,xn), что

Изложение метода Ленд-Дойга.
Решается вспомогательная ЗЛП (13.1)–(13.3), которая получена из исходной ЦЗЛП (13.1)–(13.4) отбрасыванием условия целочисленности переменных (13.4) (ветка 0;1

Алгоритм метода Ленд-Дойга.
1. Определяются множества D(k;r) условиями (13.2), (13.3) и дополнительными ограничениями, которые возникают в процессе разветвления

ЗАДАЧА О НАЗНАЧЕНИИ. ВЕНГЕРСКИЙ МЕТОД
Постановка задачи о назначении. Найти вектор (матрицу) X=(xij, і,j=1...,n), что минимизирует целевую функцию

ЗАДАЧА О НАЗНАЧЕНИИ. МЕТОД МАКА
Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4). Алгоритм метода Мака.

МАТРИЧНЫЕ ИГРЫ. СВЯЗЬ С ЗАДАЧЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. МЕТОД БРАУНА-РОБIНСОН
Постановка матричной игры двух лиц с нулевой суммой. Найти цену игры и оптимальные смешанные стратегии игроков для матричной игры двух лиц с нулевой суммой и заданн

Метод золотого сечения.
Метод золотого сечения (МЗС) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм мето

Метод случайного поиска.
Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции y=F(x), что задана в любой допустимой области D.

Метод дихотомии (половинного деления).
Метод дихотомии (МД) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм метода реа

КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД
Постановка задачи нелинейного программирования. Найти вектор x=(x1...,xn), что минимизирует (максимизирует) функцию

Градиентные методы безусловной оптимизации.
Для задачи безусловной минимизации метод заключается в вычислении последовательности приближений x[s] по правилу x[s+1]=

Метод самого быстрого спуска.
Метод самого быстрого спуска представляет собой градиентный метод, в котором величина шага r[s] выбирается по правилу F(x[s]–r

Лiтература
1. Ю.М.Ермольев, И.И.Ляшко, В.С.Михалевич, В.И.Тюптя.Математические методы исследования операций. Киев, «Высшая школа», 1979. 2. Ю.Д.Попов. Линейное и нел

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги