Указания и задания для контрольной работы по учебной дисциплине «Математика» для специальности: 080110-«Экономика и бухгалтерский учет»

Указания и задания для контрольной работы

по учебной дисциплине «Математика»

для специальности:

080110-«Экономика и бухгалтерский учет»

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

Раздел I. Линейная алгебра

Задача 1. Дана система линейных уравнений

Требуется показать, что система совместна, и найти ее решение тремя способами: а) по формулам Крамера; б) методом Гаусса; в) методом обратной матрицы. Выполнить проверку решения.

Решение.

Система n линейных уравнений с n неизвестными является совместной и имеет единственное решение, так как определитель системы, составленный из коэффициентов при неизвестных не равен нулю. Вычислим определитель системы методом разложения его по элементом строки. Разложим по первой строке:

Так как определитель системы не равен нулю, система уравнений совместна и имеет единственное решение.

а) Найдем решение системы по формулам Крамера

, , ,

где D1 D2 D3 - определители, которые получаются из определителя D системы путем замены в нем соответственно 1-го, 2-го, 3-го столбцов коэффициентов при неизвестных x1 x2 x3 столбцом свободных членов уравнений, стоящих в правой части данной системы. Получим следующие три определителя:

Вычислить неизвестные , , .

Проверим это решение, подставив значения неизвестных во все уравнения системы. Получим Решение верное.

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

1.  Перестановка строк матрицы;

2.  Перестановка столбцов;

3.  Умножение всех элементов строки на одно и то же число;

4.  Сложение элементов любой строки с соответствующими элементами любой другой строки;

5.  Вычеркивание получившихся нулевых строк.

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

Расширенная матрица 1-й шаг 2-шаг

Возвратимся теперь от матричной записи к системе уравнений. Из последней строки матрицы следует уравнение , откуда х3 = -3 Подставляя х3 = -3 в последнее уравнение (вторая строка расширенной матрицы) получим или . Наконец, из первого уравнения системы (первая строка матрицы) найдем Решение такое же, как в случае (а). Оно уже проверено.

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

В основе этого метода лежит следующий алгоритм (строго определенный порядок действий)

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

2.  Каждый элемент, разрешающий строки разделим на разрешающий элемент.

3.  Элементы разрешающего столбца заменим нулями во всех строках матрицы, кроме разрешающей, где он буден равен единице.

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

5.  Остальные элементы пересчитаем по следующему правилу «прямоугольника»:

Р D2 D1 П

Где П – пересчитываемый элемент, Р – Разрешающий, D1 и D2 – “диагональные”, И – искомый. Все эти элементы каждый раз должны быть вершинами воображаемого прямоугольника, образованного параллельными строками и столбцами. Искомый элемент записываем на месте пересчитываемого.

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

Данная расширенная матрица 1-й шаг 2-й шаг

3 - й шаг 4 – й шаг

Если в последней матрице вернуться к записи уравнений, то получим

, , , а это и есть решение данной системы.

Замечания: 1. Кружками обведены разрешающие элементы.

2. При переходе от 2-го шага к 3-му третью строку почленно разделили на 90/7.

в) Решить данную систему методом обратной матрицы.

Решение. Данную систему можно записать в матричном виде АХ = В,

где , ,

Решение матричного уравнения имеет вид Х = А-1 В = N, где А-1 – матрица, обратная матрицы А. Так как определитель матрицы системы D(A) = 180 отличен от нуля то матрица А имеет обратную. Для вычисления обратной матрицы воспользуемся формулой

Где А11, А12, …, А33 – алгебраические дополнения элементов а11, а12, …, а33 матрицы А. Вычислим алгебраические дополнения всех элементов матрицы А:

; ; ;

; ;

; ; .

Составим обратную матрицу

.

Найдем теперь матрицу Х.

Из равенства матриц Х = N или следует решение системы

х1=2, х2 = 1, х3 = -3.

Задача 2. Даны матрицы и . Найти

произведение матриц АВ.

Решение.

Эти матрицы являются соответственными, так как число столбцов первой матрицы равно числу строк второй: их размеры и . В результате умножения матриц получим новую матрицу С размера , а ее элементы будут равны скалярным произведениям векторов-строк первой матрицы на векторы-столбцов второй:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример решения ЗЛП.

1.  Приведем ЗЛП к каноническому виду.

Введем балансовые переменные x3, x4, x5.

2.  Выделим допустимый базис.

Замечаем, что переменные x3, x4, x5 удовлетворяют условию допустимости, так как каждая из них входит только в одно уравнение, и, при этом, свободные члены неотрицательные.

Преобразуем целевую функцию.

3.  Составляем симплекс-таблицы.

Итерация 0.

БП	Св. ч	x1	x2	x3	x4	x5
x3	1	1	-2	1	0	0
x4	2	-2	1	0	1	0	←
x5	3	1	1	0	0	1
f	0	-1	1	0	0	0
			↑

В последней строке есть положительный элемент при столбце переменной x2.

Этот столбец – разрешающий, помечаем его стрелкой.

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

Минимальное симплекс-отношение соответствует строке при переменной x4. Это разрешающая строка, помечаем ее стрелкой.

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

Составляем новую симплекс-таблицу.

Переменную x2 вводим в базисные переменные вместо переменной x4.

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

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

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

Итерация 1.

БП	Св. ч	x1	x2	x3	x4	x5
x3	5	-3	0	1	2	0
x2	2	-2	1	0	1	0
x5	1	5	0	0	-1	1	←
f	-2	1	0	0	-1	0
		↑

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

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

Минимальное симплекс-отношение соответствует строке при переменной x5.

Это разрешающая строка, помечаем ее стрелкой.

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

Составляем новую симплекс-таблицу.

Переменную x1 вводим в базисные переменные вместо переменной x5.

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

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

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

Итерация 2.

БП	Св. ч	x1	x2	x3	x4	x5
x3		0	0	1
x2		0	1	0
x1		1	0	0
f		0	0	0

Так как в последней строке нет положительных элементов, то оптимальное решение найдено.

Переменные x3, x4, x5 не входят в условие задачи, поэтому и в конечном ответе их быте не должно.

Ответ:

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

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

Это процедура продолжается до тех пор, пока не будет найдено оптимальное решение.

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

Для задач небольшой размерности он может использоваться вручную.

Двойственные задачи линейного программирования.

Построение двойственной задачи и ее решение.

I. Двойственные задачи линейного программирования.

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

Обе эти задачи образуют пару двойственных (или сопряженных) задач.

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

Пусть

тогда в матричной форме двойственные задачи имеют вид:

Прямая задача	Двойственная задача
Симметричные пары

Несимметричные пары

II. Алгоритм построения двойственных задач.

1.  Привести все неравенства системы ограничений к одному виду.

Если в исходной задачи ищут максимум целевой функции, то все неравенства системы ограничений привести к виду « ≤ », а если минимум — к виду « ≥ », для чего неравенства, неудовлетворяющие требованиям, умножить на -1.

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

3.  Сформировать матрицу , транспонированную к матрице А1.

4.  Сформировать двойственную задачу на основании полученной

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

II. Примеры.

1. Построить задачу, двойственную данной.

Решение:

1.  Приведем первое ограничение к виду « ≥ », тогда задача примет вид прямой задачи симметричной пары двойственных задач.

2.  Составим расширенную матрицу А1.

3.  Построим матрицу , транспонированную к матрице А1.

4.  По матрице , строим симметричную двойственную задачу.

2. Построить задачу, двойственную данной.

Решение:

Так как первое ограничение — равенство, то двойственная неизвестная y1, ему соответствующая не имеет ограничений по знаку.

Получаем несимметричную двойственную пару.

III. Решение двойственных задач.

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

Справедливы следующие теоремы.

Теорема 1. (Первая теорема двойственности)

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

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

Теорема 2. (Вторая теорема двойственности)

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

Рассмотрим решенную задачу из лекции 4, построим и найдем решение для двойственной ей.

Для составления двойственной пары необходимо все неравенства привести к виду « ≥ »

Прямая задача	Двойственная задача
Введем дополнительные балансовые переменные.
Исходные переменные: Дополнительные переменные:	Исходные переменные: Дополнительные переменные:

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

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

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

БП	Св. ч	x1	x2	x3	x4	x5
x3		0	0	1
x2		0	1	0
x1		1	0	0
f		0	0	0

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

Ответ:

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

2.  ЗАДАЧИ ДЛЯ КОНТРОЛЬНЫХ РАБОТ

Раздел I.

Линейная алгебра.

(номер варианта совпадает с номером фамилии в списке)

1 – 20.	Дана система линейных уравнений. Требуется показать, что система совместна и найти ее решение тремя способами: а) по формулам Крамера, выполнить проверку решения; б) методом Гаусса; в) методом обратной матрицы.
1.	2.
3.	4.
5.	6.
7.	8.
9.	10.
11.	12.
13.	14.
15.	16.
17.	18.
19.	20.
21-40.	Найти произведение матриц , если , даны:
21. ,
22. ,
23. ,
24. ,
25. ,
26. ,
27. ,
28. ,
29. ,
30. ,
31. ,
32. ,
33. ,
34. ,
35. ,
36. ,
37. ,
38. ,
39. ,

40. ,

Раздел II.

Линейное программирование.

41 – 60.	Для данной задачи линейного программирования построить двойственную пару, решить одну из задач и по её решению найти решение второй.
1.	2.
3.	4.
5.	6.
7.	8.
9.	10.
11.	12.
13.	14.
15.	16.
17.	18.
19.	20.

Перечень литературы

Основная:

1. , Соловейчик : Учебное пособие для техникумов.-М.:Высш. Шк., 1991.-480 с.: ил.

2. Сборник задач по высшей математике для экономистов: Учебное пособие/Под ред. .. - М.: ИНФРА – М, 200с. (Высшее образование).

3. Просветов методы в экономике: Учебно-методическое пособие.-М.:издательство РДЛ, 2004.-160 с.

Дополнительная:

4. Филимонова : Учебное пособие для средних специальных учебных заведений.- Ростов и/Д Феникс, 2003,- 384 с.

5. Данко математика в упражнениях и задачах. В 2 ч. Ч. 1. Учеб. Пособие для вузов/, .- 6-е изд.-М.: Издательский дом

«ОНИКС 21 век»: Мир и образование, 2003.-304 с., ил.