Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Содержание

Линейное программирование – это разновидность математического моделирования, частный случай оптимального программирования.Суть принципа оптимальности состоит в стремлении выбрать такое планово-управленческое решение
ОСНОВЫ    ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Линейное программирование – это разновидность математического моделирования, частный случай оптимального программирования.Суть принципа где       – его компоненты (параметры), которое Слова «наилучшим образом» здесь означают выбор некоторого критерия оптимальности, т. е. некоторого Традиционные критерии оптимальности: «максимум прибыли», «минимум затрат», «максимум рентабельности» и др.Таким образом, (1)(2)где  - математическая запись критерия оптимальности – целевая функция D – область определения задачи. Совокупность чисел (4)(5)Условие (5) необязательно, но его всегда при необходимости можно добиться. Обозначение     говорит о том, что в конкретном ограничении В случае линейного программирования целевая функция (7) Пример 3. Задача о смесях.Стандартом предусмотрено, что октановое число автомобильного бензина А-76 Требуется определить, сколько тонн каждого компонента следует использовать для получения 1000 т РешениеДля решения этой задачи сформулируем ее экономико-математическую модель.Введем необходимые обозначения:пусть , Функциональное ограничение (1) отражает необходимость получения заданного количества смеси (1000 т), (2), Полученная математическая задача-задача линейного программирования. Она может быть решена симплекс-методом, который мы Подставляя найденное решение в целевую функцию, имеем(ден. ед.)Таким образом, оптимальному решению Решение систем алгебраических линейных уравнений Метод Крамера Рассмотрим систему из n линейных уравнений с n неизвестными (определенная система) Определитель системы , составленный из коэффициентов при неизвестных, имеет видЧисла Решением системы (1) называется совокупность чисел Решить систему уравнений (1) можно различными методами, в частности, методом Крамера (Крамер Теорема КрамераЕсли определитель  системы (1) отличен от нуля, то система совместна В этой формуле  является определителем, полученным из определителя системы  путем ПримерРешить систему уравнений РешениеОпределитель системы Система имеет единственное решение. ОТВЕТ: х = 1,5; у = 0,5 Однородная система трех линейных уравненийДля простоты полагаем n = 3Однородная система(1) Система (1) имеет тривиальное решение:но может случиться, что однородная система (1) имеет ТеоремаЛинейная однородная система трех линейных уравнений с 3 неизвестными имеет ненулевое решение ДоказательствоПусть система (1) имеет ненулевое решениеПусть ее определитель   0, тогда Это противоречит предположению. Следовательно,  = 0. Тогда линейная система (1) либо ПримерРешить систему уравнений Система имеет тривиальное решение:Другой способ расчета:ОТВЕТ: (0, 0, 0) ОБРАТНАЯ  МАТРИЦА. РЕШЕНИЕ МАТРИЧНЫХ УРАВНЕНИЙ ОпределениеЕсли определитель  матрицы А равен нулю, то матрица А называется вырожденной; Рассмотрим теперь так называемую обратную матрицу, понятие которой вводится только для квадратной ОпределениеПусть дана матрица Составим матрицу   из алгебраических дополнений к элементам Матрица   называется матрицей, присоединенной к матрице А. ТеоремаЕсли матрица А не вырожденная, то она имеет обратную матрицу, На основании теоремы запишем алгоритм получения обратной матрицы:1. Находим определитель матрицы А: 2. Находим алгебраические дополнения всех элементов   матрицы А и записываем 4. Умножим полученную матрицу   на ПримерНайти матрицу, обратную матрице Решение1. Находим определитель матрицы А: Следовательно, данная матрица А является невырожденной и имеет обратную матрицу.2. Найдем алгебраические дополнения каждого элемента: Получим матрицу          алгебраических Проверим полученный результат:ОТВЕТ: РЕШЕНИЕ МАТРИЧНЫХ УРАВНЕНИЙ ПЕРВОЙ СТЕПЕНИ Пусть для простоты n = 3, имеем систему линейных уравнений (определенная система: Числа aik  коэффициенты системы, а числа bi свободные члены, i = Введем матрицу коэффициентовХ - вектор-столбец из неизвестных, а В – вектор-столбец свободных членов: Согласно правилу умножения матриц данную систему (1) можно записать так:или Используя определение равенства матриц, данную систему (1) можно записать в виде матричного Умножая обе части уравнения (2) слева на А1 А1 АХ = А1 Итак, чтобы решить матричное уравнение, нужноНайти обратную матрицу А1Найти произведение А1 В ЗадачаДана система уравнений решить ее матричным способом. РешениеЗапишем систему в матричной форме АХ = В: Решение системы Х = Выпишем все алгебраические дополнения элементов матрицы А: Запишем новую матрицу Транспонируем ее: присоединенная матрицаУчитывая, что 2. Находим произведение Х = А1 В 3. Итак,,  х1 = 2, х2 = 1, х3 = 3.ОТВЕТ: (2, 1, 3)ЗамечаниеДругой расчет: СИСТЕМА m ЛИНЕЙНЫХ УРАВНЕНИЙ С n ПЕРЕМЕННЫМИ Рассмотрим систему m линейных с n переменными (при  m < n (1)или в краткой записи или в векторной записи:где…, соответствующие вектор-столбцы. Запишем расширенную матрицу этой системы в виде: А1  А2 перестановка любых двух уравнений (строк); умножение обеих частей одного из уравнений на вычеркивание нулевой строки (уравнения с нулевыми коэффициентами и свободным членом, равным 0):Определение. Можно показать, что элементарные преобразования переводят данную систему уравнений в эквивалентную систему. МЕТОД  ГАУССА Рассмотрим решение системы m линейных уравнений с n переменными:(1) Метод Гаусса – метод последовательного исключения переменных – заключается в том, что Предположим, что в системе (1) коэффициент при переменной х1 в первом уравнении и прибавляя последовательно полученные уравнения соответственно ко второму, третьему, …, m–му уравнению Получим(2)где буквами с верхним индексом (1) обозначены новые коэффициенты, полученные после первого шага. Шаг 2. Предположим, что        (если уравнения соответственно к третьему, четвертому, …, m–му уравнению системы, исключим переменную х2 (3) Число нуль в последних m–r уравнениях означает, что их левые части имеют тождествами и их можно не принимать во внимание при решении системы (1).Очевидно, б) б)   (в этом случае система (3) имеет ступенчатый вид).Переход Преобразование Гаусса удобно проводить, осуществляя преобразования не с самими уравнениями, а с расширенной матрицей системы (1) ЗадачаРешить систему уравнений: РешениеРасширенная матрица системы имеет вид:Шаг 1 Так как a11  0. То второй, третьей, четвертой строкам, исключим переменную х1 из всех строк, начиная со Шаг 2  Так как теперь Шаг 3 Учитывая, что     , умножая третью строку Откуда, используя обратный ход метода Гаусса, найдем из четвертого уравнения х4 =
Слайды презентации

Слайд 2
Линейное программирование – это разновидность математического моделирования, частный

Линейное программирование – это разновидность математического моделирования, частный случай оптимального программирования.Суть

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

такое планово-управленческое решение

Слайд 3 где –

где    – его компоненты (параметры), которое наилучшим образом

его компоненты (параметры), которое наилучшим образом учитывало бы внутренние

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

Слайд 4 Слова «наилучшим образом» здесь означают выбор некоторого критерия

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

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

тех или иных планово-управленческих решений.

Слайд 5 Традиционные критерии оптимальности: «максимум прибыли», «минимум затрат», «максимум

Традиционные критерии оптимальности: «максимум прибыли», «минимум затрат», «максимум рентабельности» и др.Таким

рентабельности» и др.
Таким образом, реализовать на практике принцип оптимальности

в планировании и управлении – это значит решить экстремальную задачу вида:







Слайд 6 (1)
(2)
где - математическая запись критерия оптимальности –

(1)(2)где - математическая запись критерия оптимальности – целевая функция

целевая функция


Слайд 7 D – область определения задачи. Совокупность чисел

D – область определения задачи. Совокупность чисел

, удовлетворяющих ограничениям задачи называется допустимым решением (или планом).
Задачу условной оптимизации (1), (2) обычно записывают в виде:
Найти максимум или минимум функции
= (3)
При ограничениях






Слайд 8 (4)
(5)
Условие (5) необязательно, но его всегда при необходимости

(4)(5)Условие (5) необязательно, но его всегда при необходимости можно добиться.

можно добиться.


Слайд 9 Обозначение говорит о том,

Обозначение   говорит о том, что в конкретном ограничении возможен

что в конкретном ограничении возможен один из знаков:

Задача

(3 – 5) – общая задача оптимального (математического) программирования, иначе – математическая модель задачи оптимального программирования.

План , при котором целевая функция задачи принимает максимальное (минимальное) значение, называется оптимальным.


Слайд 10 В случае линейного программирования целевая функция

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

может быть представлена в

виде линейной формы

 заданные постоянные величины, а связь с ограниченными ресурсами описывается линейными уравнениями и неравенствами

Слайд 11 (7)

(7)       (8)

(8)

(6)

Наиболее изучены задачи линейного программирования, для которых разработан универсальный метод решения – метод последовательного улучшения плана (симплекс-метод)


Слайд 12 Пример 3. Задача о смесях.
Стандартом предусмотрено, что октановое

Пример 3. Задача о смесях.Стандартом предусмотрено, что октановое число автомобильного бензина

число автомобильного бензина А-76 должно быть не ниже 76,

а содержание серы в нем – не более 0,3%. Для изготовления такого бензина на заводе используется смесь из четырех компонентов. Данные о ресурсах смешиваемых компонентов, их себестоимости и их октановом числе, а также о содержании серы приведены в таблице.

Слайд 14 Требуется определить, сколько тонн каждого компонента следует использовать

Требуется определить, сколько тонн каждого компонента следует использовать для получения 1000

для получения 1000 т автомобильного бензина А-76, чтобы его

себестоимость была минимальной.

Слайд 15 Решение
Для решения этой задачи сформулируем ее экономико-математическую модель.
Введем

РешениеДля решения этой задачи сформулируем ее экономико-математическую модель.Введем необходимые обозначения:пусть

необходимые обозначения:
пусть

- количество в смеси компонента с номером j. С учетом этих обозначений имеем задачу (критерий оптимальности – «минимум себестоимости»):


Слайд 16 ,

,      (1),   (2),  (3)

(1)
,

(2)

, (3)


Слайд 17 Функциональное ограничение (1) отражает необходимость получения заданного количества

Функциональное ограничение (1) отражает необходимость получения заданного количества смеси (1000 т),

смеси (1000 т), (2), (3) – ограничения по октановому

числу и содержанию серы в смеси, остальные – ограничения на имеющиеся объемы соответствующих ресурсов.

Слайд 18 Полученная математическая задача-задача линейного программирования. Она может быть

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

решена симплекс-методом, который мы рассмотрим позже.
В результате решения получается

оптимальное решение

т,

т,

т,

т,


Слайд 19 Подставляя найденное решение в целевую функцию, имеем
(ден. ед.)
Таким

Подставляя найденное решение в целевую функцию, имеем(ден. ед.)Таким образом, оптимальному решению

образом, оптимальному решению

будет отвечать минимальная себестоимость в 57160 ден. ед.

Слайд 20 Решение систем алгебраических линейных уравнений
Метод Крамера

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

Слайд 21 Рассмотрим систему из n линейных уравнений с n

Рассмотрим систему из n линейных уравнений с n неизвестными (определенная система)

неизвестными (определенная система)


Слайд 22 Определитель системы , составленный из коэффициентов при неизвестных,

Определитель системы , составленный из коэффициентов при неизвестных, имеет видЧисла

имеет вид
Числа

свободные члены.

Система (1) называется однородной, если


Слайд 23 Решением системы (1) называется совокупность чисел

Решением системы (1) называется совокупность чисел

которые обращают все уравнения в тождества.

Система имеющая хотя бы одно решение, называется совместной.
Система, не имеющая решений, называется несовместной.


Слайд 24 Решить систему уравнений (1) можно различными методами, в

Решить систему уравнений (1) можно различными методами, в частности, методом Крамера

частности, методом Крамера (Крамер – швейцарский математик, 1704 –

1752)

Слайд 25 Теорема Крамера
Если определитель  системы (1) отличен от

Теорема КрамераЕсли определитель  системы (1) отличен от нуля, то система

нуля, то система совместна и имеет единственное решение, которое

можно найти по формуле:

Слайд 26 В этой формуле является определителем, полученным из

В этой формуле является определителем, полученным из определителя системы  путем

определителя системы  путем замены столбца j столбцом свободных

членов.

Замечание
Если определитель системы уравнений (1)  = 0, то система (1) или несовместна или имеет бесконечно много решений.


Слайд 27 Пример
Решить систему уравнений
Решение
Определитель системы

Система имеет единственное

ПримерРешить систему уравнений РешениеОпределитель системы Система имеет единственное решение.

решение.


Слайд 28 ОТВЕТ: х = 1,5; у = 0,5

ОТВЕТ: х = 1,5; у = 0,5

Слайд 29 Однородная система трех линейных уравнений
Для простоты полагаем n

Однородная система трех линейных уравненийДля простоты полагаем n = 3Однородная система(1)

= 3
Однородная система
(1)


Слайд 30 Система (1) имеет тривиальное решение:
но может случиться, что

Система (1) имеет тривиальное решение:но может случиться, что однородная система (1)

однородная система (1) имеет и не нулевое решение. Его

называют нетривиальным решением однородной системы (1).

Слайд 31 Теорема
Линейная однородная система трех линейных уравнений с 3

ТеоремаЛинейная однородная система трех линейных уравнений с 3 неизвестными имеет ненулевое

неизвестными имеет ненулевое решение тогда и только тогда, когда

ее определитель  = 0, т. е.

Слайд 32 Доказательство
Пусть система (1) имеет ненулевое решение
Пусть ее определитель

ДоказательствоПусть система (1) имеет ненулевое решениеПусть ее определитель   0,

  0, тогда на основании формул Крамера система

(1) имеет только нулевое решение



Слайд 33 Это противоречит предположению. Следовательно,  = 0. Тогда

Это противоречит предположению. Следовательно,  = 0. Тогда линейная система (1)

линейная система (1) либо несовместна, либо имеет бесконечно много

решений. Но наша система совместна, так как имеется нулевое решение. Следовательно, система (1) допускает бесконечно много решений, в том числе и ненулевые.

Слайд 34 Пример
Решить систему уравнений

ПримерРешить систему уравнений

Слайд 35 Система имеет тривиальное решение:
Другой способ расчета:
ОТВЕТ: (0, 0,

Система имеет тривиальное решение:Другой способ расчета:ОТВЕТ: (0, 0, 0)

Слайд 36 ОБРАТНАЯ МАТРИЦА.
РЕШЕНИЕ МАТРИЧНЫХ УРАВНЕНИЙ

ОБРАТНАЯ МАТРИЦА. РЕШЕНИЕ МАТРИЧНЫХ УРАВНЕНИЙ

Слайд 37 Определение
Если определитель матрицы А равен нулю, то

ОпределениеЕсли определитель матрицы А равен нулю, то матрица А называется вырожденной;

матрица А называется вырожденной; в противном случае матрица А

называется невырожденной.

Слайд 38 Рассмотрим теперь так называемую обратную матрицу, понятие которой

Рассмотрим теперь так называемую обратную матрицу, понятие которой вводится только для

вводится только для квадратной матрицы.
Определение
Если А – квадратная матрица,

то обратной для нее матрицей называется матрица, обозначенная А-1 и удовлетворяющая условиям

, где Е – единичная матрица


Слайд 39 Определение
Пусть дана матрица
Составим матрицу из

ОпределениеПусть дана матрица Составим матрицу  из алгебраических дополнений к элементам транспонированной матрицы  :

алгебраических дополнений к элементам транспонированной матрицы :



Слайд 40 Матрица называется матрицей, присоединенной к матрице

Матрица  называется матрицей, присоединенной к матрице А.

А.


Слайд 41 Теорема
Если матрица А не вырожденная, то она имеет

ТеоремаЕсли матрица А не вырожденная, то она имеет обратную матрицу,

обратную матрицу, которая находится по формуле

или
где

- матрица, присоединенная к матрице А,

Слайд 42 На основании теоремы запишем алгоритм получения обратной матрицы:
1.

На основании теоремы запишем алгоритм получения обратной матрицы:1. Находим определитель матрицы

Находим определитель матрицы А:
Если

, то обратная матрица не существует.

Если , то переходим ко 2 шагу.


Слайд 43 2. Находим алгебраические дополнения всех элементов

2. Находим алгебраические дополнения всех элементов  матрицы А и записываем

матрицы А и записываем новую матрицу составленную из

(алгебраических дополнений).
3. Транспонируем полученную матрицу (меняем местами столбцы полученной матрицы со строками), получаем присоединенную матрицу .

Слайд 44 4. Умножим полученную матрицу на
Пример
Найти

4. Умножим полученную матрицу  на ПримерНайти матрицу, обратную матрице Решение1. Находим определитель матрицы А:

матрицу, обратную матрице
Решение
1. Находим определитель матрицы А:


Слайд 45 Следовательно, данная матрица А является невырожденной и имеет

Следовательно, данная матрица А является невырожденной и имеет обратную матрицу.2. Найдем алгебраические дополнения каждого элемента:

обратную матрицу.
2. Найдем алгебраические дополнения каждого элемента:


Слайд 46 Получим матрицу

Получим матрицу     алгебраических дополнений 3. Транспонируем эту

алгебраических дополнений
3. Транспонируем эту

матрицу, получаем присоединенную матрицу .

4. Умножим полученную матрицу на , т. е. на


Слайд 47 Проверим полученный результат:
ОТВЕТ:

Проверим полученный результат:ОТВЕТ:

Слайд 48 РЕШЕНИЕ МАТРИЧНЫХ УРАВНЕНИЙ ПЕРВОЙ СТЕПЕНИ

РЕШЕНИЕ МАТРИЧНЫХ УРАВНЕНИЙ ПЕРВОЙ СТЕПЕНИ

Слайд 49 Пусть для простоты n = 3, имеем систему

Пусть для простоты n = 3, имеем систему линейных уравнений (определенная

линейных уравнений (определенная система: 3

уравнения, 3 неизвестных):

(1)


Слайд 50 Числа aik  коэффициенты системы, а числа bi

Числа aik  коэффициенты системы, а числа bi свободные члены, i

свободные члены, i = 1, 3, k =

1, 3.
Решением системы (1) называется совокупность чисел x1 = 1, x2 = 2, x3 = 3, которые обращают все уравнения системы в тождества.

Слайд 51 Введем матрицу коэффициентов
Х - вектор-столбец из неизвестных, а

Введем матрицу коэффициентовХ - вектор-столбец из неизвестных, а В – вектор-столбец свободных членов:

В – вектор-столбец свободных членов:


Слайд 52 Согласно правилу умножения матриц данную систему (1) можно

Согласно правилу умножения матриц данную систему (1) можно записать так:или

записать так:
или


Слайд 53 Используя определение равенства матриц, данную систему (1) можно

Используя определение равенства матриц, данную систему (1) можно записать в виде

записать в виде матричного уравнение
АХ = В ,

(1)
Здесь в роли неизвестного выступает матрица Х. Уравнение (2) решается следующим образом. Если А – невырожденная матрица ( ), то можно определить обратную матрицу А1 .

Слайд 54 Умножая обе части уравнения (2) слева на А1

Умножая обе части уравнения (2) слева на А1 А1 АХ =


А1 АХ = А1 В
используем сочетательный закон умножения:
(А1 А

)Х = А1 В , но так как А1 А = Е , то получаем решение матричного уравнения (2) в виде Х = А1В.

Слайд 55 Итак, чтобы решить матричное уравнение, нужно
Найти обратную матрицу

Итак, чтобы решить матричное уравнение, нужноНайти обратную матрицу А1Найти произведение А1

А1
Найти произведение А1 В = Х
Пользуясь определением равных матриц,

записать ответ.

Слайд 56 Задача
Дана система уравнений
решить ее матричным способом.

ЗадачаДана система уравнений решить ее матричным способом.

Слайд 57 Решение

Запишем систему в матричной форме АХ = В:

РешениеЗапишем систему в матричной форме АХ = В: Решение системы Х


Решение системы Х = А1В
1. Найдем обратную матрицу А1



Слайд 58 Выпишем все алгебраические дополнения элементов матрицы А:

Выпишем все алгебраические дополнения элементов матрицы А:

Слайд 60 Запишем новую матрицу
Транспонируем ее:
 присоединенная матрица
Учитывая, что

Запишем новую матрицу Транспонируем ее: присоединенная матрицаУчитывая, что    , запишем обратную матрицу

, запишем обратную

матрицу


Слайд 61 2. Находим произведение Х = А1 В

2. Находим произведение Х = А1 В

Слайд 62 3. Итак,
,  х1 = 2, х2 =

3. Итак,,  х1 = 2, х2 = 1, х3 = 3.ОТВЕТ: (2, 1, 3)ЗамечаниеДругой расчет:

1, х3 = 3.
ОТВЕТ: (2, 1, 3)
Замечание
Другой расчет:


Слайд 63 СИСТЕМА m ЛИНЕЙНЫХ УРАВНЕНИЙ С n ПЕРЕМЕННЫМИ

СИСТЕМА m ЛИНЕЙНЫХ УРАВНЕНИЙ С n ПЕРЕМЕННЫМИ

Слайд 64 Рассмотрим систему m линейных с n переменными (при

Рассмотрим систему m линейных с n переменными (при m < n

m < n такие системы называются неопределенными):
Число уравнений

m не равно, вообще говоря, числу неизвестных n.

Слайд 65 (1)
или в краткой записи

(1)или в краткой записи

Слайд 66 или в векторной записи:
где
…,
соответствующие вектор-столбцы.

или в векторной записи:где…, соответствующие вектор-столбцы.

Слайд 67 Запишем расширенную матрицу этой системы в виде: А1

Запишем расширенную матрицу этой системы в виде: А1 А2  …

А2 … Аn

B

Элементарными преобразованиями системы (1) (или матрицы Ар) называются следующие преобразования:


Слайд 68 перестановка любых двух уравнений (строк);
умножение обеих частей

перестановка любых двух уравнений (строк); умножение обеих частей одного из уравнений

одного из уравнений на любое отличное от нуля число;

прибавление к обеим частям одного уравнения соответствующих частей другого, умноженных на любое число, отличное от нуля;

Слайд 69 вычеркивание нулевой строки (уравнения с нулевыми коэффициентами и

вычеркивание нулевой строки (уравнения с нулевыми коэффициентами и свободным членом, равным

свободным членом, равным 0):
Определение.
Системы уравнений вида (1) называются

эквивалентными (или равносильными), если они имеют одно и то же множество решений.

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

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

уравнений в эквивалентную систему.
При практическом решении системы линейных

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



Слайд 71 МЕТОД ГАУССА

МЕТОД ГАУССА

Слайд 72 Рассмотрим решение системы m линейных уравнений с n

Рассмотрим решение системы m линейных уравнений с n переменными:(1)

переменными:
(1)


Слайд 73 Метод Гаусса – метод последовательного исключения переменных –

Метод Гаусса – метод последовательного исключения переменных – заключается в том,

заключается в том, что с помощью элементарных преобразований система

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

Слайд 74 Предположим, что в системе (1) коэффициент при переменной

Предположим, что в системе (1) коэффициент при переменной х1 в первом

х1 в первом уравнении а11  0 (если это

не так, то перестановкой уравнений местами добьемся того, что а11  0 ).

Шаг 1. Умножая первое уравнение на подходящие числа (а именно на )

…,


Слайд 75 и прибавляя последовательно полученные уравнения соответственно ко второму,

и прибавляя последовательно полученные уравнения соответственно ко второму, третьему, …, m–му

третьему, …, m–му уравнению системы (1), исключим переменную х1

из всех последующих уравнений, начиная со второго.

Слайд 76 Получим
(2)
где буквами с верхним индексом (1) обозначены новые

Получим(2)где буквами с верхним индексом (1) обозначены новые коэффициенты, полученные после первого шага.

коэффициенты, полученные после первого шага.


Слайд 77 Шаг 2.
Предположим, что

Шаг 2. Предположим, что    (если не так, то

(если не так, то соответствующей перестановкой

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

…,

и прибавляя полученные


Слайд 78 уравнения соответственно к третьему, четвертому, …, m–му уравнению

уравнения соответственно к третьему, четвертому, …, m–му уравнению системы, исключим переменную

системы, исключим переменную х2 из всех последующих уравнений, начиная

с третьего.
Продолжая процесс последовательного исключения переменных, после (r1)-го шага получим систему


Слайд 80 Число нуль в последних m–r уравнениях означает, что

Число нуль в последних m–r уравнениях означает, что их левые части

их левые части имеют вид:
Если хотя бы одно

из чисел , … , не равны нулю, то соответствующее равенство противоречиво, и система (1) несовместна.
Таким образом, для любой совместной системы числа , …, в системе (3) равны нулю. В этом случае m–r уравнений в системе (3) являются

Слайд 81 тождествами и их можно не принимать во внимание

тождествами и их можно не принимать во внимание при решении системы

при решении системы (1).
Очевидно, что после отбрасывания «лишних» уравнений

возможны два случая:
а) число уравнений системы (3) равно числу переменных т. е. r = n (в этом случае система (3) имеет треугольный вид);


Слайд 82 б)
б) (в этом случае

б) б)  (в этом случае система (3) имеет ступенчатый вид).Переход

система (3) имеет ступенчатый вид).
Переход системы (1) к равносильной

ей системе (3) называется прямым ходом метода Гаусса, а нахождение переменных из системы (3) – обратным ходом.

Слайд 83 Преобразование Гаусса удобно проводить, осуществляя преобразования не с

Преобразование Гаусса удобно проводить, осуществляя преобразования не с самими уравнениями, а с расширенной матрицей системы (1)

самими уравнениями, а с расширенной матрицей системы (1)


Слайд 84 Задача
Решить систему уравнений:

ЗадачаРешить систему уравнений:

Слайд 85 Решение
Расширенная матрица системы имеет вид:
Шаг 1 Так как

РешениеРасширенная матрица системы имеет вид:Шаг 1 Так как a11  0.

a11  0. То умножая первую строку последовательно на

числа (2), (3), (2) и прибавляя полученные строки соответственно ко

Слайд 86 второй, третьей, четвертой строкам, исключим переменную х1 из

второй, третьей, четвертой строкам, исключим переменную х1 из всех строк, начиная

всех строк, начиная со второй.
Заметив, что в новой

матрице , поменяем местами вторую и третью строки:

̴


Слайд 87 Шаг 2 Так как теперь

Шаг 2 Так как теперь     , то

, то

умножая вторую строку на и прибавляя полученную строку к четвертой, исключим переменную х2 из всех строк, начиная с третьей:

̴


Слайд 88 Шаг 3 Учитывая, что

Шаг 3 Учитывая, что   , умножая третью строку на

, умножая третью строку на

и прибавляя полученную строку к четвертой исключим из нее переменную х3.
Получим (см. последнюю матрицу) систему уравнений


  • Имя файла: osnovy-lineynogo-programmirovaniya.pptx
  • Количество просмотров: 90
  • Количество скачиваний: 2