Обновлено: 02.07.2024

Данный реферат включает в себя три прямых метода решения систем линейных алгебраических уравнений (СЛАУ): метод Крамера, матричный метод (метод обратной матрицы), метод Гаусса.
Метод решения СЛАУ называют прямым, если он позволяет получить решение после выполнения конечного числа элементарных операций. Основным недостатком прямых методов является то, что для нахождения решения необходимо выполнить большое число операций.

Содержание

Прикрепленные файлы: 1 файл

Referat_Metody_reshenia_SLAU.docx

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

Институт ИПР

Направление подготовки (специальность) Нефтегазовое дело

РЕФЕРАТ

Выполнили студенты гр. 2Б44

Абдурагимов Ф.Р.

Важенин Р.А.

Гасанов Ф.А

Гвоздев Н.С.

Проверил: доцент, кандидат наук Сухотин А.М.

Томск-2014

Содержание

1. Введение………………………………………………………… ………3
2. Определение, понятие, обозначение………………………………….4-5
3. Прямые методы решения СЛАУ……………………………………….6

3.1 Метод Крамера……………………………………………………….. 7,8

3.2. Матричный метод………………………………………………….9,10, 11

3.3. Метод Гаусса………………………………………………………. 12-19

1. Заключение…………………………………………………… ………..20
2. Список используемой литературы……………………………………21

Данный реферат включает в себя три прямых метода решения систем линейных алгебраических уравнений (СЛАУ): метод Крамера, матричный метод (метод обратной матрицы), метод Гаусса.

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

К решению систем линейных алгебраических уравнений сводятся многочисленные практические задачи ( по некоторым оценкам более 75% всех задач). Можно с полным основанием утверждать, что решение линейных систем является одной из самых распространенных и важных задач вычислительной математики.

Конечно, существует много методов и современных пакетов прикладных программ для решения СЛАУ, но для того, чтобы их успешно использовать, необходимо разбираться в основах построения методов и алгоритмов, иметь представления о недостатках и преимуществах используемых методов.

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

ФЕДИРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ ГОУ ВПО

ДАЛЬНИВОСТОЧНЫЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ВЛАДИВОСТОТСКИЙ ИНСТИТУТ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ

Факультет политических наук и социального управления

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

Система линейных уравнений

Студентки группы 1113а

Лариной Натальи Владиславовны

Винокурова Татьяна Васильевна, к. м. н., доцент кафедры математического анализа

Глава 1. Критерий совместимости……………………………………………….3

Глава 4. Матричный метод……………………………………………………. 14

Система линейных уравнений имеет вид:

Здесь а_ij и b_i (i = ; j = ) - заданные, а x_j - неизвестные действительные числа. Используя понятие произведения матриц, можно переписать систему (5.1) в виде:

где A = (а_ij) - матрица, состоящая из коэффициентов при неизвестных системы (5.1), которая называется матрицей системы, X = (x₁, x₂. x_n) T , B = (b₁, b₂. b_m) T - векторы-столбцы, составленные соответственно из неизвестных x_j и из свободных членов b_i..

Упорядоченная совокупность n вещественных чисел (c₁, c₂. c_n) называется решением системы (5.1), если в результате подстановки этих чисел вместо соответствующих переменных x₁, x₂. x_n каждое уравнение системы обратится в арифметическое тождество; другими словами, если существует вектор C= (c₁, c₂. c_n) T такой, что AC ? B.

Система (5.1) называется совместной, или разрешимой, если она имеет по крайней мере одно решение. Система называется несовместной, или неразрешимой, если она не имеет решений.

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

Вопрос о совместности системы (5.1) решается следующей теоремой.

Теорема Кронекера- Капелли. Система линейных уравнений совместна тогда и только тогда, когда ранги матриц A и ? совпадают, т.е.

Для множества М решений системы (5.1) имеются три возможности:

M = ? (в этом случае система несовместна);

M состоит из одного элемента, т.е. система имеет единственное решение (в этом случае система называется определенной);

M состоит более чем из одного элемента (тогда система называется неопределенной). В третьем случае система (5.1) имеет бесчисленное множество решений.

Система имеет единственное решение только в том случае, когда r(A) = n. При этом число уравнений - не меньше числа неизвестных (m ? n); если m > n, то m-n уравнений являются следствиями остальных. Если 0 (1) (если a₂₂ (1) 0)

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

Матрица этой системы имеет вид:

На этом прямой ход метода Гаусса заканчивается. Второй этап – обратный ход, заключается в решении треугольной системы. Из последнего уравнения находим x_m. По найденному x_m из (m-1) уравнения находим x_m-1. Затем по x_m-1 и x_m из (m-2) уравнения находим x_m-2. Процесс продолжаем, пока не найдем x₁ из первого уравнения.

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

Так как прямой ход метода Гаусса прервется, когда уравнения закончатся, а неизвестные еще останутся. В таком случае в каждом уравнении системы перенесем все члены с неизвестными x_k+1,….,x_m в правую часть.

Придавая неизвестным x_k+1,….,x_m (называемым свободными) произвольные значения, получим треугольную систему из которой последовательно найдем все остальные неизвестные (называемые базисными). Так как произвольные значения можно придавать любыми способами, система будет иметь бесчисленное множество значений.

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

Такая модификация метода называется методом Жордана-Гауcса.

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

1 шаг: а) первую строку не меняем б) из второй вычитаем первую, умноженную на 2 в) третью не меняем, т.к. там неизвестное х₁ и так отсутствует.

2 шаг: а) вторую строку делим на - 4 б) из третьей строки вычитаем новую вторую (поделенную на -4).

3 шаг: делим третью строку на (-7/4).

Последней матрице соответствует система:

Метод Крамера состоит в том, что мы последовательно находим главный определитель системы (5.3), т.е. определитель матрицы А

и n вспомогательных определителей D _i (i=), которые получаются из определителя D заменой i-го столбца столбцом свободных членов.

Формулы Крамера имеют вид:

Из (5.4) следует правило Крамера, которое дает исчерпывающий ответ на вопрос о совместности системы (5.3): если главный определитель системы отличен от нуля, то система имеет единственное решение, определяемое по формулам:

Если главный определитель системы D и все вспомогательные определители D _i = 0 (i= ), то система имеет бесчисленное множество решений. Если главный определитель системы D = 0, а хотя бы один вспомогательный определитель отличен от нуля, то система несовместна.

Пример. Решить методом Крамера систему уравнений:

Решение. Главный определитель этой системы:

значит, система имеет единственное решение. Вычислим вспомогательные определители D _i ( i = ), получающиеся из определителя D путем замены в нем столбца, состоящего из коэффициентов при x_i, столбцом из свободных членов:

Отсюда x₁ = D ₁/D = 1, x₂ = D ₂/D = 2, x₃ = D ₃/D = 3, x₄ = D ₄/D = -1, решение системы - вектор С=(1, 2, 3, -1) T .

Если матрица А системы линейных уравнений невырожденная, т.е.
det A ? 0, то матрица А имеет обратную, и решение системы (5.3) совпадает с вектором C = A - 1 B. Иначе говоря, данная система имеет единственное решение. Отыскание решения системы по формуле X=C, C=A - 1 B называют матричным способом решения системы, или решением по методу обратной матрицы.

Пример. Решить матричным способом систему уравнений:

Решение. Обозначим:

Тогда данная система уравнений запишется матричным уравнением AX=B.

Поскольку, то матрица A невырождена и поэтому имеет обратную:

Для получения решения X мы должны умножить вектор-столбец B слева на матрицу A: X = A - 1 B. В данном случае

Выполняя действия над матрицами, получим:

x₂ = 1/5 (-3?6 +1?3 - 1?5) = 1/5 (- 18 + 3 + 5) = -2

x₃ = 1/5 (1?6 - 2?3 + 3?5) = 1/5 (6 -6 + 15) = 3

Итак, С = (1, -2, 3) T .

Г.И. Кручкович. “Сборник задач по курсу высшей математике”, М. “Высшая школа”, 1973 год.

В.СШипачев. “Высшая математика”, М. “Высшая школа”, 1985 год.

Тема моего доклада – различные решения систем линейных уравнений.
Теория уравнений занимает ведущее место в алгебре и математике в целом. Сила теории уравнений в том, что она не только имеет теоретическое значение для познания естественных законов, но и служит практическим целям. Большинство жизненных задач сводится к решению различных видов уравнений, и не редко это системы уравнений.
Проблема исследования заключается в выделении двух важных для начинающих разбираться в данной теме методах решения систем уравнений, метода Гаусса и правила Крамера.
Цель работы состоит в изучении теоретических основ и их практическое применение.

Содержание

II. История возникновения системы
уравнений
III. Системы уравнений
1. Что такое система уравнений?
2. Способы решения систем уравнений
Решение системы способом подстановки
Решение системы способом сравнения
Решение системы способом сложения
Решение системы графическим способом
2.5 Решение системы методом определителей
3. Что такое система линейных уравнений с n неизвестными?
4. Матричный метод решения систем линейных уравнений
5. Правило Крамера
6. Метод Гаусса

Работа содержит 1 файл

Система линейных уравнений.doc

Министерство образования и науки Республики Бурятия
Комитет по образованию
г. Улан-Удэ

Научно-практическая конференция

Работу выполнила Сапунова Анастасия Германовна

Муниципальное образовательное учреждение

средняя общеобразовательная школа №2

с углубленным изучением отдельных предметов

уравнений

• III. Системы уравнений
1. Решение системы способом подстановки
2. Решение системы способом сравнения
3. Решение системы способом сложения
4. Решение системы графическим способом

2.5 Решение системы методом определителей

• 3. Что такое система линейных уравнений с n неизвестными?
• 4. Матричный метод решения систем линейных уравнений
• 5. Правило Крамера
• 6. Метод Гаусса
• IV. Заключение

Тема моего доклада – различные решения систем линейных уравнений.

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

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

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

Выбор способа должен оставаться за учащимся. Каждый ученик должен уметь верно и рационально решать системы уравнений. И для этого необходимо знать все возможные способы решений, которые могут пригодиться на экзамене ЕГЭ, при поступлении в ВУЗы и даже различных жизненных ситуациях.

Все сказанное выше определяет актуальность темы выполненной работы.

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


ЗАДАЧИ ДОКЛАДА


1. Произвести анализ учебно – методической литературы по решению систем линейных уравнений.
2. Произвести анализ различных способов решения систем уравнений
3. Изучить историю развития систем уравнений.
4. Изучить различные способы решения систем уравнений и апробировать материал на практике.

II. ИСТОРИЯ ВОЗНИКНОВЕНИЯ СИСТЕМЫ

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

Некоторые алгебраические приемы решения линейных уравнений были известны еще 4000 лет назад в Древнем Вавилоне.

III. СИСТЕМЫ УРАВНЕНИЙ


Что такое система уравнений?


• Системой уравнений называется некоторое количество уравнений, объединенных фигурной скобкой. Фигурная скобка означает, что все уравнения должны выполняться одновременно
• Каждая пара значений переменных, которая одновременно является решением всех уравнений системы, называется решением системы
• Решением системы уравнений с двумя переменными называется пара значений переменных, обращающая каждое уравнение системы в верное равенство
• Решить систему уравнений - это значит найти все её решения или установить, что их нет

Способы решения систем уравнений


Решение системы способом подстановки

• Из какого-либо уравнения выразить одну переменную через другую
• Подставить полученное выражение для переменной в другое уравнение и решить его
• Сделать подстановку найденного значения переменной и вычислить значение второй переменной
• Записать ответ: х=…; у=… .

Решение системы способом сравнения

• Выразить у через х (или х через у) в каждом уравнении
• Приравнять выражения, полученные для одноимённых переменных
• Решить полученное уравнение и найти значение одной переменной
• Подставить значение найденной переменной в одно из выражений для другой переменной и найти её значение
• Записать ответ: х=…; у=… .

Решение системы способом сложения

• Уравнять модули коэффициентов при какой-нибудь переменной
• Сложить почленно уравнения системы
• Составить новую систему: одно уравнение новое, другое - одно из старых
• Решить новое уравнение и найти значение одной переменной
• Подставить значение найденной переменной в старое уравнение и найти значение другой переменной
• Записать ответ: х=…; у=… .

Решение системы графическим способом

• Выразить у через х в каждом уравнении
• Построить в одной системе координат график каждого уравнения
• Определить координаты точки пересечения
• Записать ответ: х=…; у=… , или (х; у)

Решение системы методом определителей

• Составить табличку (матрицу) коэффициентов при неизвестных и вычислить определитель D .
• Найти - определитель D _x, получаемый из D заменой первого столбца на столбец свободных членов.
• Найти - определитель D _y, получаемый из D заменой второго столбца на столбец свободных членов.
• Найти значение переменной х по формуле D _x / D .
• Найти значение переменной у по формуле D _y / D .
• Записать ответ: х=…; у=… .

Что такое система линейных уравнений с n неизвестными


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

где a_ij и b_i (i=1,…,m; b=1,…,n) – некоторые известные числа, а x₁,…,x_n – неизвестные. В обозначении коэффициентов a_ij первый индекс iобозначает номер уравнения, а второй j – номер неизвестного, при котором стоит этот коэффициент.

Коэффициенты при неизвестных будем записывать в виде матрицы , которую назовём матрицей системы.

Числа, стоящие в правых частях уравнений, b₁,…,b_m называются свободными членами.

Совокупность n чисел c₁,…,c_n называется решением данной системы, если каждое уравнение системы обращается в равенство после подстановки в него чисел c₁,…,c_n вместо соответствующих неизвестных x₁,…,x_n.

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

1. Система может иметь единственное решение.
2. Система может иметь бесконечное множество решений. Например, . Решением этой системы является любая пара чисел, отличающихся знаком.
3. И третий случай, когда система вообще не имеет решения. Например, , если бы решение существовало, то x₁+ x₂ равнялось бы одновременно нулю и единице.

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

Рассмотрим способы нахождения решений системы.

Матричный метод решения систем линейных уравнений


Матрицы дают возможность кратко записать систему линейных уравнений. Пусть дана система из 3-х уравнений с тремя неизвестными:

Рассмотрим матрицу системы и матрицы столбцы неизвестных и свободных членов

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

или короче A∙X=B.

Здесь матрицы A и B известны, а матрица X неизвестна. Её и нужно найти, т.к. её элементы являются решением данной системы. Это уравнение называют матричным уравнением.

Пусть определитель матрицы отличен от нуля |A| ≠ 0. Тогда матричное уравнение решается следующим образом. Умножим обе части уравнения слева на матрицу A -1 , обратную матрице A: . Поскольку A -1 A = E и E∙X = X, то получаем решение матричного уравнения в виде X = A -1 B.

Заметим, что поскольку обратную матрицу можно найти только для квадратных матриц, то матричным методом можно решать только те системы, в которых число уравнений совпадает с числом неизвестных. Однако, матричная запись системы возможна и в случае, когда число уравнений не равно числу неизвестных, тогда матрица A не будет квадратной и поэтому нельзя найти решение системы в виде X = A -1 B.

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







ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РФ
Кафедра математики и финансовых приложений

Курсовая работа

Чанкин Пётр Алексеевич

Профессор Александр Самуилович Солодовников
Москва 2002г

Оглавление

Графический метод .. 3

Метод искусственного базиса .. 8

Принцип двойственности .. 10

Список использованной литературы . 12


Вступление


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



Графический метод

Графический метод заключается в построении множества допустимых решений ЗЛП, и нахождении в данном множестве точки, соответствующей max/min целевой функции.
В связи с ограниченными возможностями наглядного графического представления данный метод применяется только для систем линейных неравенств с двумя неизвестными и систем, которые могут быть приведены к данному виду.
Для того чтобы наглядно продемонстрировать графический метод, решим следующую задачу:


1. На первом этапе надо построить область допустимых решений. Для данного примера удобнее всего выбрать X 2 за абсциссу, а X 1 за ординату и записать неравенства в следующем виде:



Так как и графики и область допустимых решении находятся в первой четверти.
Для того чтобы найти граничные точки решаем уравнения (1)=(2), (1)=(3) и (2)=(3).


Как видно из иллюстрации многогранник ABCDE образует область допустимых решений.

Если область допустимых решений не является замкнутой, то либо max ( f )=+ ∞, либо min ( f )= -∞.

1. Теперь можно перейти к непосредственному нахождению максимума функции f .


Поочерёдно подставляя координаты вершин многогранника в функцию f и сравнивать значения, находим что
f ( C )= f (4;1)=19 – максимум функции.
Такой подход вполне выгоден при малом количестве вершин. Но данная процедура может затянуться если вершин довольно много.
В таком случае удобнее рассмотреть линию уровня вида f = a . При монотонном увеличении числа a от -∞ до +∞ прямые f = a смещаются по вектору нормали [1] . Если при таком перемещении линии уровня существует некоторая точка X – первая общая точка области допустимых решений (многогранник ABCDE ) и линии уровня, то f ( X )- минимум f на множестве ABCDE . Если X - последняя точка пересечения линии уровня и множества ABCDE то f ( X )- максимум на множестве допустимых решений. Если при а→-∞ прямая f = a пересекает множество допустимых решений, то min ( f )= -∞. Если это происходит при а→+∞, то

В нашем примере прямая f = a пересевает область ABCDE в точке С(4;1). Поскольку это последняя точка пересечения, max ( f )= f ( C )= f (4;1)=19.



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


Реальные задачи линейного программирования содержат очень большое число ограничений и неизвестных и выполняются на ЭВМ. Симплекс-метод – наиболее общий алгоритм, использующийся для решения таких задач. Суть метода заключается в том, что после некоторого числа специальных симплекс- преобразований ЗЛП, приведенная к специальному виду, разрешается. Для того, чтобы продемонстрировать симплекс-метод в действии решим, с попутными комментариями следующую задачу:


1. Для того, чтобы приступить к решению ЗЛП симплекс методом, надо привести ЗЛП к специальному виду и заполнить симплекс таблицу.


Система (4) – естественные ограничения и в таблицу не вписываются. Уравнения (1), (2), (3) образуют область допустимых решений. Выражение (5) – целевая функция. Свободные члены в системе ограничений и области допустимых решений должны быть неотрицательны.
В данном примере X 3, X 4, X 5 – базисные неизвестные. Их надо выразить через свободные неизвестные и произвести их замену в целевой функции.


Теперь можно приступить к заполнению симплекс-таблицы:




Б.	X1	X2	X3	X4	X5	C
X3	0	-1	1	1	0	1
X4	0	1	-1	0	1	1
X5	1	1	1	0	0	2
f	0	-6	7	0	0	3


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

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




Б	X1	X2	X3	X4	X5	C
X3	-1	1	1	0	0	1
X4	1	-1	0	1	0	1
X5	1	1	0	0	1	2
f	-6	7	0	0	0	3


Для этого выбираем столбец с отрицательным коэффициентом в последней строке [2] (столбец 3) и составляем для положительных элементов данного столбца отношения свободный член/коэффициент (1/1; 2/1) [3] . Из данных отношений выбираем наименьшее и помечаем соответствующую строку [4] .
Нами выбран элемент в ячейке (3;3). Теперь с помощью метода Гаусса обнуляем другие коэффициенты в данном столбце, это приводит к смене базиса и мы на один шаг приближаемся к оптимальному решению.




Б	X1	X2	X3	X4	X5	C
X3	0	0	1	1	0	2
X 1	1	- 1	0	1	0	1
X5	0	2	0	-1	1	1
f	0	1	0	6	0	9




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




Метод искусственного базиса


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

1. К строкам, в которых отсутствует базисная переменная добавляется по одной искусственной базисной переменной.
2. Новая задача решается Симплекс-методом, причем все искусственные базисные переменные должны стать свободными (выйти из базиса) и их сумма должна равняться нулю, в обратном случае в данной системе невозможно выделить допустимый базис.


Рассмотрим следующий пример:

min(f)-?

1. В первом уравнении нет базисных неизвестных. Введём искусственную базисную неизвестную Y 1 и заполним первую симплекс-таблицу


Для того, чтобы избавится от искусственной базисной неизвестной нам предстоит решить вспомогательную задачу:
F = Y 1→ min
Выражая базисную неизвестную Y 1 через свободные получаем:
F + 4X1 + X2=4 →min




Б	X1	X2	X3	X4	Y1	С
Y1	4	1	0	0	1	4
X4	11	3	-5	-1	0	12
F	4	1	0	0	0	4


Выбираем элемент в ячейке (3;2) и делаем шаг.




Б	X1	X2	X3	X4	Y1	С
X2	4	1	0	0	1	4
X4	-1	0	-5	-1	-3	0
F	0	0	0	0	-1	0


min ( f )=0, все коэффициенты в последней строке меньше или равны нулю, следовательно мы перешли к новому естественному базису. Теперь можно решать основную задачу.



Принцип двойственности


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

max ( f )-? min ( φ )-?
Из данного примера легко просматривается взаимосвязь между исходной и двойственной задачами.
Введя в рассмотрение следующие элементы:

Эту связь можно обозначить следующим образом:

max ( f )-? min ( φ )-?
В двойственной задаче всего 2 переменных. Её можно легко решить графическим методом и, используя вторую теорему двойственности, найти решение исходной.
Пропустим процесс решения двойственной ЗЛП, записав только результаты:
Y1=2 Y2=4 min(φ)=150
Т.к max ( f )= min ( φ ), решение исходной задачи уже известно. Остаётся только найти значения X 1, X 2, X 3, при которых это значение достигается. Здесь мы применим вторую теорему двойственности, которая устанавливает следующее соответствие:

В нашем примере получается следующая вполне тривиальная система линейных уравнений:

Решение данной системы легко находится методом Гаусса и окончательный ответ таков:
Функция f достигает максимума при X ₁ =0, X _2­ =5, X ₃ =10 и max ( f )=150


Список использованной литературы


[1] Вектор нормали имеет координаты (С1;С2), где C 1 и C 2 коэффициенты при неизвестных в целевой функции f = C 1◦ X 1+ C 2◦ X 2+ C 0.



[3] Если положительных элементов не оказалось то данная ЗЛП не имеет решения, т.е max ( f )=+∞ (при задаче на нахождение максимума) или min ( f )=- ∞ (нахождение минимума)


Читайте также:

  
• Социальный аспект греха реферат
  
• Понятие и виды правовых актов иностранных государств реферат
  
• Дейдвудное устройство судна реферат
  
• Общение как условие личностного роста реферат
  
• Реферат дом детского творчества